001package org.hl7.fhir.utilities;
002
003/*
004 NaturalOrderComparator.java -- Perform 'natural order' comparisons of strings in Java.
005 Copyright (C) 2003 by Pierre-Luc Paour <natorder@paour.com>
006
007 Based on the C version by Martin Pool, of which this is more or less a straight conversion.
008 Copyright (C) 2000 by Martin Pool <mbp@humbug.org.au>
009
010 This software is provided 'as-is', without any express or implied
011 warranty.  In no event will the authors be held liable for any damages
012 arising from the use of this software.
013
014 Permission is granted to anyone to use this software for any purpose,
015 including commercial applications, and to alter it and redistribute it
016 freely, subject to the following restrictions:
017
018 1. The origin of this software must not be misrepresented; you must not
019 claim that you wrote the original software. If you use this software
020 in a product, an acknowledgment in the product documentation would be
021 appreciated but is not required.
022 2. Altered source versions must be plainly marked as such, and must not be
023 misrepresented as being the original software.
024 3. This notice may not be removed or altered from any source distribution.
025 */
026
027import java.util.*;
028
029public class NaturalOrderComparator<T extends String> implements Comparator<T> {
030
031  int compareRight(String a, String b) {
032    int bias = 0, ia = 0, ib = 0;
033
034    // The longest run of digits wins. That aside, the greatest
035    // value wins, but we can't know that it will until we've scanned
036    // both numbers to know that they have the same magnitude, so we
037    // remember it in BIAS.
038    for (;; ia++, ib++)
039    {
040      char ca = charAt(a, ia);
041      char cb = charAt(b, ib);
042
043      if (!isDigit(ca) && !isDigit(cb)) {
044        return bias;
045      }
046      if (!isDigit(ca)) {
047        return -1;
048      }
049      if (!isDigit(cb)) {
050        return +1;
051      }
052      if (ca == 0 && cb == 0) {
053        return bias;
054      }
055
056      if (bias == 0) {
057        if (ca < cb) {
058          bias = -1;
059        } else if (ca > cb) {
060          bias = +1;
061        }
062      }
063    }
064  }
065
066  public int compare(String a, String b) {
067    int ia = 0, ib = 0;
068    int nza = 0, nzb = 0;
069    char ca, cb;
070
071    while (true) {
072      // Only count the number of zeroes leading the last number compared
073      nza = nzb = 0;
074
075      ca = charAt(a, ia);
076      cb = charAt(b, ib);
077
078      // skip over leading spaces or zeros
079      while (Character.isSpaceChar(ca) || ca == '0') {
080        if (ca == '0') {
081          nza++;
082        } else {
083          // Only count consecutive zeroes
084          nza = 0;
085        }
086
087        ca = charAt(a, ++ia);
088      }
089
090      while (Character.isSpaceChar(cb) || cb == '0') {
091        if (cb == '0') {
092          nzb++;
093        } else {
094          // Only count consecutive zeroes
095          nzb = 0;
096        }
097
098        cb = charAt(b, ++ib);
099      }
100
101      // Process run of digits
102      if (Character.isDigit(ca) && Character.isDigit(cb)) {
103        int bias = compareRight(a.substring(ia), b.substring(ib));
104        if (bias != 0) {
105          return bias;
106        }
107      }
108
109      if (ca == 0 && cb == 0) {
110        // The strings compare the same. Perhaps the caller
111        // will want to call strcmp to break the tie.
112        return compareEqual(a, b, nza, nzb);
113      }
114      if (ca < cb) {
115        return -1;
116      }
117      if (ca > cb) {
118        return +1;
119      }
120
121      ++ia;
122      ++ib;
123    }
124  }
125
126  static boolean isDigit(char c) {
127    return Character.isDigit(c) || c == '.' || c == ',';
128  }
129
130  static char charAt(String s, int i) {
131    return i >= s.length() ? 0 : s.charAt(i);
132  }
133
134  static int compareEqual(String a, String b, int nza, int nzb) {
135    if (nza - nzb != 0)
136      return nza - nzb;
137
138    if (a.length() == b.length())
139      return a.compareTo(b);
140
141    return a.length() - b.length();
142  }
143
144}