|
1
|
1 package de.mpiwg.itgroup.ismi.utils;
|
|
|
2
|
|
|
3 /*
|
|
|
4 NaturalOrderComparator.java -- Perform 'natural order' comparisons of strings in Java.
|
|
|
5 Copyright (C) 2003 by Pierre-Luc Paour <natorder@paour.com>
|
|
|
6
|
|
|
7 Based on the C version by Martin Pool, of which this is more or less a straight conversion.
|
|
|
8 Copyright (C) 2000 by Martin Pool <mbp@humbug.org.au>
|
|
|
9
|
|
|
10 This software is provided 'as-is', without any express or implied
|
|
|
11 warranty. In no event will the authors be held liable for any damages
|
|
|
12 arising from the use of this software.
|
|
|
13
|
|
|
14 Permission is granted to anyone to use this software for any purpose,
|
|
|
15 including commercial applications, and to alter it and redistribute it
|
|
|
16 freely, subject to the following restrictions:
|
|
|
17
|
|
|
18 1. The origin of this software must not be misrepresented; you must not
|
|
|
19 claim that you wrote the original software. If you use this software
|
|
|
20 in a product, an acknowledgment in the product documentation would be
|
|
|
21 appreciated but is not required.
|
|
|
22 2. Altered source versions must be plainly marked as such, and must not be
|
|
|
23 misrepresented as being the original software.
|
|
|
24 3. This notice may not be removed or altered from any source distribution.
|
|
|
25 */
|
|
|
26
|
|
|
27 import java.util.*;
|
|
|
28
|
|
|
29 public class NaturalOrderComparator
|
|
|
30 {
|
|
|
31 private static int compareRight(String a, String b)
|
|
|
32 {
|
|
|
33 int bias = 0;
|
|
|
34 int ia = 0;
|
|
|
35 int ib = 0;
|
|
|
36
|
|
|
37 // The longest run of digits wins. That aside, the greatest
|
|
|
38 // value wins, but we can't know that it will until we've scanned
|
|
|
39 // both numbers to know that they have the same magnitude, so we
|
|
|
40 // remember it in BIAS.
|
|
|
41 for (;; ia++, ib++)
|
|
|
42 {
|
|
|
43 char ca = charAt(a, ia);
|
|
|
44 char cb = charAt(b, ib);
|
|
|
45
|
|
|
46 if (!Character.isDigit(ca) && !Character.isDigit(cb))
|
|
|
47 {
|
|
|
48 return bias;
|
|
|
49 }
|
|
|
50 else if (!Character.isDigit(ca))
|
|
|
51 {
|
|
|
52 return -1;
|
|
|
53 }
|
|
|
54 else if (!Character.isDigit(cb))
|
|
|
55 {
|
|
|
56 return +1;
|
|
|
57 }
|
|
|
58 else if (ca < cb)
|
|
|
59 {
|
|
|
60 if (bias == 0)
|
|
|
61 {
|
|
|
62 bias = -1;
|
|
|
63 }
|
|
|
64 }
|
|
|
65 else if (ca > cb)
|
|
|
66 {
|
|
|
67 if (bias == 0)
|
|
|
68 bias = +1;
|
|
|
69 }
|
|
|
70 else if (ca == 0 && cb == 0)
|
|
|
71 {
|
|
|
72 return bias;
|
|
|
73 }
|
|
|
74 }
|
|
|
75 }
|
|
|
76
|
|
|
77
|
|
|
78
|
|
|
79 public static int compare(String a, String b)
|
|
|
80 {
|
|
|
81 //String a = o1.toString();
|
|
|
82 //String b = o2.toString();
|
|
|
83
|
|
|
84 int ia = 0, ib = 0;
|
|
|
85 int nza = 0, nzb = 0;
|
|
|
86 char ca, cb;
|
|
|
87 int result;
|
|
|
88
|
|
|
89 while (true)
|
|
|
90 {
|
|
|
91 // only count the number of zeroes leading the last number compared
|
|
|
92 nza = nzb = 0;
|
|
|
93
|
|
|
94 ca = charAt(a, ia);
|
|
|
95 cb = charAt(b, ib);
|
|
|
96
|
|
|
97 // skip over leading spaces or zeros
|
|
|
98 while (Character.isSpaceChar(ca) || ca == '0')
|
|
|
99 {
|
|
|
100 if (ca == '0')
|
|
|
101 {
|
|
|
102 nza++;
|
|
|
103 }
|
|
|
104 else
|
|
|
105 {
|
|
|
106 // only count consecutive zeroes
|
|
|
107 nza = 0;
|
|
|
108 }
|
|
|
109
|
|
|
110 ca = charAt(a, ++ia);
|
|
|
111 }
|
|
|
112
|
|
|
113 while (Character.isSpaceChar(cb) || cb == '0')
|
|
|
114 {
|
|
|
115 if (cb == '0')
|
|
|
116 {
|
|
|
117 nzb++;
|
|
|
118 }
|
|
|
119 else
|
|
|
120 {
|
|
|
121 // only count consecutive zeroes
|
|
|
122 nzb = 0;
|
|
|
123 }
|
|
|
124
|
|
|
125 cb = charAt(b, ++ib);
|
|
|
126 }
|
|
|
127
|
|
|
128 // process run of digits
|
|
|
129 if (Character.isDigit(ca) && Character.isDigit(cb))
|
|
|
130 {
|
|
|
131 if ((result = compareRight(a.substring(ia), b.substring(ib))) != 0)
|
|
|
132 {
|
|
|
133 return result;
|
|
|
134 }
|
|
|
135 }
|
|
|
136
|
|
|
137 if (ca == 0 && cb == 0)
|
|
|
138 {
|
|
|
139 // The strings compare the same. Perhaps the caller
|
|
|
140 // will want to call strcmp to break the tie.
|
|
|
141 return nza - nzb;
|
|
|
142 }
|
|
|
143
|
|
|
144 if (ca < cb)
|
|
|
145 {
|
|
|
146 return -1;
|
|
|
147 }
|
|
|
148 else if (ca > cb)
|
|
|
149 {
|
|
|
150 return +1;
|
|
|
151 }
|
|
|
152
|
|
|
153 ++ia;
|
|
|
154 ++ib;
|
|
|
155 }
|
|
|
156 }
|
|
|
157
|
|
|
158 static char charAt(String s, int i)
|
|
|
159 {
|
|
|
160 if (i >= s.length())
|
|
|
161 {
|
|
|
162 return 0;
|
|
|
163 }
|
|
|
164 else
|
|
|
165 {
|
|
|
166 return s.charAt(i);
|
|
|
167 }
|
|
|
168 }
|
|
|
169
|
|
|
170 /*
|
|
|
171 public static void main(String[] args)
|
|
|
172 {
|
|
|
173 String[] strings = new String[] { "1-2", "1-02", "1-20", "10-20", "fred", "jane", "pic01",
|
|
|
174 "pic2", "pic02", "pic02a", "pic3", "pic4", "pic 4 else", "pic 5", "pic05", "pic 5",
|
|
|
175 "pic 5 something", "pic 6", "pic 7", "pic100", "pic100a", "pic120", "pic121",
|
|
|
176 "pic02000", "tom", "x2-g8", "x2-y7", "x2-y08", "x8-y8" };
|
|
|
177
|
|
|
178 List orig = Arrays.asList(strings);
|
|
|
179
|
|
|
180 System.out.println("Original: " + orig);
|
|
|
181
|
|
|
182 List scrambled = Arrays.asList(strings);
|
|
|
183 Collections.shuffle(scrambled);
|
|
|
184
|
|
|
185 System.out.println("Scrambled: " + scrambled);
|
|
|
186
|
|
|
187 Collections.sort(scrambled, new NaturalOrderComparator());
|
|
|
188
|
|
|
189 System.out.println("Sorted: " + scrambled);
|
|
|
190 }
|
|
|
191 */
|
|
|
192 } |
