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}