/**
 * NaturalOrderComparator.java -- Perform 'natural order' comparisons of strings in Java.
 * Copyright (C) 2003 by Pierre-Luc Paour <natorder@paour.com>
 * 
 * Based on the C version by Martin Pool, of which this is more or less a straight conversion.
 * Copyright (C) 2000 by Martin Pool <mbp@humbug.org.au>
 * 
 * This software is provided 'as-is', without any express or implied
 * warranty.  In no event will the authors be held liable for any damages
 * arising from the use of this software.
 * 
 * Permission is granted to anyone to use this software for any purpose,
 * including commercial applications, and to alter it and redistribute it
 * freely, subject to the following restrictions:
 * 
 * 1. The origin of this software must not be misrepresented; you must not
 * claim that you wrote the original software. If you use this software
 * in a product, an acknowledgment in the product documentation would be
 * appreciated but is not required.
 * 2. Altered source versions must be plainly marked as such, and must not be
 * misrepresented as being the original software.
 * 3. This notice may not be removed or altered from any source distribution.
 */
package content;

import java.util.*;

/**
 * @author john
 *
 */
public class NaturalOrderComparator implements Comparator<Object> {

	/**
	 * @param a
	 * @param b
	 * @return
	 */
	int compareRight(String a, String b)
	{
		int bias = 0;
		int ia = 0;
		int ib = 0;

		// The longest run of digits wins.  That aside, the greatest
		// value wins, but we can't know that it will until we've scanned
		// both numbers to know that they have the same magnitude, so we
		// remember it in BIAS.
		for (;; ia++, ib++) {
			char ca = charAt(a, ia);
			char cb = charAt(b, ib);

			if (!Character.isDigit(ca)
					&& !Character.isDigit(cb)) {
				return bias;
			} else if (!Character.isDigit(ca)) {
				return -1;
			} else if (!Character.isDigit(cb)) {
				return +1;
			} else if (ca < cb) {
				if (bias == 0) {
					bias = -1;
				}
			} else if (ca > cb) {
				if (bias == 0)
					bias = +1;
			} else if (ca == 0 && cb == 0) {
				return bias;
			}
		}
	}
	
	/**
	 * 
	 */
	public NaturalOrderComparator() {
		// TODO Auto-generated constructor stub
	}

	@Override
	public int compare(Object arg0, Object arg1) {
		String a = arg0.toString();
		String b = arg1.toString();

		int ia = 0, ib = 0;
		int nza = 0, nzb = 0;
		char ca, cb;
		int result;

		while (true) {
			// only count the number of zeroes leading the last number compared
			nza = nzb = 0;

			ca = charAt(a, ia); cb = charAt(b, ib);

			// skip over leading spaces or zeros
			while (Character.isSpaceChar(ca) || ca == '0') {
				if (ca == '0') {
					nza++;
				} else {
					// only count consecutive zeroes
					nza = 0;
				}

				ca = charAt(a, ++ia);
			}

			while (Character.isSpaceChar(cb) || cb == '0') {
				if (cb == '0') {
					nzb++;
				} else {
					// only count consecutive zeroes
					nzb = 0;
				}

				cb = charAt(b, ++ib);
			}

			// process run of digits
			if (Character.isDigit(ca) && Character.isDigit(cb)) {
				if ((result = compareRight(a.substring(ia), b.substring(ib))) != 0) {
					return result;
				}
			}

			if (ca == 0 && cb == 0) {
				// The strings compare the same.  Perhaps the caller
				// will want to call strcmp to break the tie.
				return nza - nzb;
			}

			if (ca < cb) {
				return -1;
			} else if (ca > cb) {
				return +1;
			}

			++ia; ++ib;
		}
	}

	static char charAt(String s, int i) {
		if (i >= s.length()) {
			return 0;
		} else {
			return s.charAt(i);
		}
	}
}

@@ -1227,17 +1227,18 @@
  john%0A *
+ 
 %0A
-
  */%0Apubl
@@ -1387,18 +1387,17 @@
 tring b)
-%0A%09
+ 
 %7B%0A%09%09int 
@@ -1471,17 +1471,16 @@
 ts wins.
- 
  That as
@@ -1768,22 +1768,17 @@
 igit(ca)
-%0A%09%09%09%09%09
+ 
 && !Char
@@ -2122,10 +2122,9 @@
 %0A%09%7D%0A
-%09
 %0A
+
 %09/**
@@ -2540,17 +2540,20 @@
 (a, ia);
- 
+%0A%09%09%09
 cb = cha
@@ -3239,17 +3239,16 @@
 he same.
- 
  Perhaps
@@ -3424,17 +3424,20 @@
 %09%09%09++ia;
- 
+%0A%09%09%09
 ++ib;%0A%09%09

Standardize formatting for number comparison