1 /*
  2  * To change this license header, choose License Headers in Project Properties.
  3  * To change this template file, choose Tools | Templates
  4  * and open the template in the editor.
  5  */
  6 package ibcompsciinternalassessment;
  7 
  8 /***
  9  * <copyright>
 10  *
 11  *  Copyright 1997-2007 BBNT Solutions, LLC
 12  *  under sponsorship of the Defense Advanced Research Projects
 13  *  Agency (DARPA).
 14  *
 15  *  You can redistribute this software and/or modify it under the
 16  *  terms of the Cougaar Open Source License as published on the
 17  *  Cougaar Open Source Website (www.cougaar.org).
 18  *
 19  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 20  *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 21  *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 22  *  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 23  *  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 24  *  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 25  *  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 26  *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 27  *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 28  *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 29  *  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 30  *
 31  * </copyright>
 32  */
 33 /*
 34 NaturalOrderComparator.java -- Perform 'natural order' comparisons of strings in Java.
 35 Copyright (C) 2003 by Pierre-Luc Paour <natorder@paour.com>
 36 
 37 Based on the C version by Martin Pool, of which this is more or less a straight conversion.
 38 Copyright (C) 2000 by Martin Pool <mbp@humbug.org.au>
 39 
 40 This software is provided 'as-is', without any express or implied
 41 warranty.  In no event will the authors be held liable for any damages
 42 arising from the use of this software.
 43 
 44 Permission is granted to anyone to use this software for any purpose,
 45 including commercial applications, and to alter it and redistribute it
 46 freely, subject to the following restrictions:
 47 
 48 1. The origin of this software must not be misrepresented; you must not
 49 claim that you wrote the original software. If you use this software
 50 in a product, an acknowledgment in the product documentation would be
 51 appreciated but is not required.
 52 2. Altered source versions must be plainly marked as such, and must not be
 53 misrepresented as being the original software.
 54 3. This notice may not be removed or altered from any source distribution.
 55  */
 56 //package org.cougaar.util;
 57 
 58 //CHANGES: KD - added case sensitive ordering capability
 59 // Made comparison so it doesn't treat spaces as special characters
 60 
 61 //CHANGES:
 62 //   set package to "org.cougaar.util"
 63 //   replaced "import java.util.*" with explicit imports,
 64 //   added "main" file reader support
 65 
 66         //THIS CLASS IS USED IN MY COMPUTER SCIENCE IA
 67         //CHANGES: 
 68         //  set package to "package ibcompsciinternalassessment;"
 69         //  constructor class set to public
 70 
 71 
 72 import java.util.Comparator;
 73 
 74 /**
 75  * A sorting comparator to sort strings numerically,
 76  * ie [1, 2, 10], as opposed to [1, 10, 2].
 77  */
 78 public final class NaturalOrderComparator<T> implements  Comparator<T> {
 79 
 80     public static final Comparator<String> NUMERICAL_ORDER = new NaturalOrderComparator<String>(false);
 81     public static final Comparator<String> CASEINSENSITIVE_NUMERICAL_ORDER = new NaturalOrderComparator<String>(true);
 82 
 83     private final boolean caseInsensitive;
 84 
 85     public NaturalOrderComparator(boolean caseInsensitive) {
 86         this.caseInsensitive = caseInsensitive;
 87     }
 88 
 89     int compareRight(String a, String b) {
 90         int bias = 0;
 91         int ia = 0;
 92         int ib = 0;
 93 
 94         // The longest run of digits wins.  That aside, the greatest
 95         // value wins, but we can't know that it will until we've scanned
 96         // both numbers to know that they have the same magnitude, so we
 97         // remember it in BIAS.
 98         for (;; ia++, ib++) {
 99             char ca = charAt(a, ia);
100             char cb = charAt(b, ib);
101 
102             if (!Character.isDigit(ca) && !Character.isDigit(cb)) {
103                 return bias;
104             } else if (!Character.isDigit(ca)) {
105                 return -1;
106             } else if (!Character.isDigit(cb)) {
107                 return +1;
108             } else if (ca < cb) {
109                 if (bias == 0) {
110                     bias = -1;
111                 }
112             } else if (ca > cb) {
113                 if (bias == 0)
114                     bias = +1;
115             } else if (ca == 0 && cb == 0) {
116                 return bias;
117             }
118         }
119     }
120 
121     public int compare(T o1, T o2) {
122         String a = o1.toString();
123         String b = o2.toString();
124 
125         int ia = 0, ib = 0;
126         int nza = 0, nzb = 0;
127         char ca, cb;
128         int result;
129 
130         while (true) {
131             // only count the number of zeroes leading the last number compared
132             nza = nzb = 0;
133 
134             ca = charAt(a, ia);
135             cb = charAt(b, ib);
136 
137             // skip over leading zeros
138             while (ca == '0') {
139                 if (ca == '0') {
140                     nza++;
141                 } else {
142                     // only count consecutive zeroes
143                     nza = 0;
144                 }
145 
146                 // if the next character isn't a digit, then we've had a run of only zeros
147                 // we still need to treat this as a 0 for comparison purposes
148                 if (!Character.isDigit(charAt(a, ia+1)))
149                     break;
150 
151                 ca = charAt(a, ++ia);
152             }
153 
154             while (cb == '0') {
155                 if (cb == '0') {
156                     nzb++;
157                 } else {
158                     // only count consecutive zeroes
159                     nzb = 0;
160                 }
161 
162                 // if the next character isn't a digit, then we've had a run of only zeros
163                 // we still need to treat this as a 0 for comparison purposes
164                 if (!Character.isDigit(charAt(b, ib+1)))
165                     break;
166 
167                 cb = charAt(b, ++ib);
168             }
169 
170             // process run of digits
171             if (Character.isDigit(ca) && Character.isDigit(cb)) {
172                 if ((result = compareRight(a.substring(ia), b
173                         .substring(ib))) != 0) {
174                     return result;
175                 }
176             }
177 
178             if (ca == 0 && cb == 0) {
179                 // The strings compare the same.  Perhaps the caller
180                 // will want to call strcmp to break the tie.
181                 return nza - nzb;
182             }
183 
184             if (ca < cb) {
185                 return -1;
186             } else if (ca > cb) {
187                 return +1;
188             }
189 
190             ++ia;
191             ++ib;
192         }
193     }
194 
195     private char charAt(String s, int i) {
196         if (i >= s.length()) {
197             return 0;
198         } else {
199             return caseInsensitive ? Character.toUpperCase(s.charAt(i)) : s.charAt(i);
200         }
201     }
202 
203 
204 }