001: /*
002: * <copyright>
003: *
004: * Copyright 1997-2007 BBNT Solutions, LLC
005: * under sponsorship of the Defense Advanced Research Projects
006: * Agency (DARPA).
007: *
008: * You can redistribute this software and/or modify it under the
009: * terms of the Cougaar Open Source License as published on the
010: * Cougaar Open Source Website (www.cougaar.org).
011: *
012: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
013: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
014: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
015: * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
016: * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
017: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
018: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
019: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
020: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
021: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
022: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
023: *
024: * </copyright>
025: */
026: /*
027: NaturalOrderComparator.java -- Perform 'natural order' comparisons of strings in Java.
028: Copyright (C) 2003 by Pierre-Luc Paour <natorder@paour.com>
029:
030: Based on the C version by Martin Pool, of which this is more or less a straight conversion.
031: Copyright (C) 2000 by Martin Pool <mbp@humbug.org.au>
032:
033: This software is provided 'as-is', without any express or implied
034: warranty. In no event will the authors be held liable for any damages
035: arising from the use of this software.
036:
037: Permission is granted to anyone to use this software for any purpose,
038: including commercial applications, and to alter it and redistribute it
039: freely, subject to the following restrictions:
040:
041: 1. The origin of this software must not be misrepresented; you must not
042: claim that you wrote the original software. If you use this software
043: in a product, an acknowledgment in the product documentation would be
044: appreciated but is not required.
045: 2. Altered source versions must be plainly marked as such, and must not be
046: misrepresented as being the original software.
047: 3. This notice may not be removed or altered from any source distribution.
048: */
049: package org.cougaar.util;
050:
051: // CHANGES:
052: // set package to "org.cougaar.util"
053: // replaced "import java.util.*" with explicit imports,
054: // added "main" file reader support
055:
056: import java.io.BufferedReader;
057: import java.io.FileReader;
058: import java.util.ArrayList;
059: import java.util.Arrays;
060: import java.util.Collections;
061: import java.util.Comparator;
062: import java.util.List;
063:
064: /**
065: * A sorting comparator to sort strings numerically,
066: * ie [1, 2, 10], as opposed to [1, 10, 2].
067: */
068: public final class NaturalOrderComparator implements Comparator {
069:
070: public static final Comparator NUMERICAL_ORDER = new NaturalOrderComparator();
071:
072: private NaturalOrderComparator() {
073: // no-arg constructor
074: }
075:
076: int compareRight(String a, String b) {
077: int bias = 0;
078: int ia = 0;
079: int ib = 0;
080:
081: // The longest run of digits wins. That aside, the greatest
082: // value wins, but we can't know that it will until we've scanned
083: // both numbers to know that they have the same magnitude, so we
084: // remember it in BIAS.
085: for (;; ia++, ib++) {
086: char ca = charAt(a, ia);
087: char cb = charAt(b, ib);
088:
089: if (!Character.isDigit(ca) && !Character.isDigit(cb)) {
090: return bias;
091: } else if (!Character.isDigit(ca)) {
092: return -1;
093: } else if (!Character.isDigit(cb)) {
094: return +1;
095: } else if (ca < cb) {
096: if (bias == 0) {
097: bias = -1;
098: }
099: } else if (ca > cb) {
100: if (bias == 0)
101: bias = +1;
102: } else if (ca == 0 && cb == 0) {
103: return bias;
104: }
105: }
106: }
107:
108: public int compare(Object o1, Object o2) {
109: String a = o1.toString();
110: String b = o2.toString();
111:
112: int ia = 0, ib = 0;
113: int nza = 0, nzb = 0;
114: char ca, cb;
115: int result;
116:
117: while (true) {
118: // only count the number of zeroes leading the last number compared
119: nza = nzb = 0;
120:
121: ca = charAt(a, ia);
122: cb = charAt(b, ib);
123:
124: // skip over leading spaces or zeros
125: while (Character.isSpaceChar(ca) || ca == '0') {
126: if (ca == '0') {
127: nza++;
128: } else {
129: // only count consecutive zeroes
130: nza = 0;
131: }
132:
133: ca = charAt(a, ++ia);
134: }
135:
136: while (Character.isSpaceChar(cb) || cb == '0') {
137: if (cb == '0') {
138: nzb++;
139: } else {
140: // only count consecutive zeroes
141: nzb = 0;
142: }
143:
144: cb = charAt(b, ++ib);
145: }
146:
147: // process run of digits
148: if (Character.isDigit(ca) && Character.isDigit(cb)) {
149: if ((result = compareRight(a.substring(ia), b
150: .substring(ib))) != 0) {
151: return result;
152: }
153: }
154:
155: if (ca == 0 && cb == 0) {
156: // The strings compare the same. Perhaps the caller
157: // will want to call strcmp to break the tie.
158: return nza - nzb;
159: }
160:
161: if (ca < cb) {
162: return -1;
163: } else if (ca > cb) {
164: return +1;
165: }
166:
167: ++ia;
168: ++ib;
169: }
170: }
171:
172: static char charAt(String s, int i) {
173: if (i >= s.length()) {
174: return 0;
175: } else {
176: return s.charAt(i);
177: }
178: }
179:
180: public static void main(String[] args) {
181: String[] strings;
182: if (args.length > 0) {
183: String filename = args[0];
184: try {
185: List data = new ArrayList();
186: BufferedReader br = new BufferedReader(new FileReader(
187: filename));
188: while (true) {
189: String line = br.readLine();
190: if (line == null)
191: break;
192: int sep = line.indexOf("#");
193: if (sep >= 0) {
194: line = line.substring(0, sep);
195: }
196: line = line.trim();
197: if (line.length() == 0)
198: continue;
199: data.add(line);
200: }
201: br.close();
202: strings = (String[]) data.toArray(new String[data
203: .size()]);
204: } catch (Exception e) {
205: System.err.println("Unable to read " + filename);
206: e.printStackTrace();
207: System.exit(-1);
208: return;
209: }
210: } else {
211: strings = new String[] { "1-2", "1-02", "1-20", "10-20",
212: "fred", "jane", "pic01", "pic2", "pic02", "pic02a",
213: "pic3", "pic4", "pic 4 else", "pic 5", "pic05",
214: "pic 5", "pic 5 something", "pic 6", "pic 7",
215: "pic100", "pic100a", "pic120", "pic121",
216: "pic02000", "tom", "x2-g8", "x2-y7", "x2-y08",
217: "x8-y8" };
218: }
219:
220: List orig = Arrays.asList(strings);
221:
222: System.out.println("Original: " + orig);
223:
224: List scrambled = Arrays.asList(strings);
225: Collections.shuffle(scrambled);
226:
227: System.out.println("Scrambled: " + scrambled);
228:
229: Collections.sort(scrambled,
230: NaturalOrderComparator.NUMERICAL_ORDER);
231:
232: System.out.println("Sorted: " + scrambled);
233: }
234: }
|