NaturalOrderComparator.java

package com.cmosis.test;

import java.util.Comparator;

public class NaturalOrderComparator implements Comparator<String>
{
    static char charAt(String s, int i)
    {
        if (i >= s.length())
            return 0;
        
        return s.charAt(i);
    }
    
    static int compareRight(String a, String b)
    {
        for (int ia = 0, ib = 0, bias = 0;; ia++, ib++)
        {
            char ca = charAt(a, ia);
            char cb = charAt(b, ib);
            
            if (!isDigit(ca) && !isDigit(cb))
                return bias;
            if (!isDigit(ca))
                return -1;
            if (!isDigit(cb))
                return +1;
            
            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;
        }
    }
    
    private static boolean isDigit(char c)
    {
        return c >= '0' && c <= '9';
    }
    
    private static boolean isSpace(char c)
    {
        return c == ' ' || c == '\t' || c == '\r' || c == '\n';
    }
    
    @Override
    public int compare(String a, String b)
    {
        for (int ia = 0, ib = 0;; ia++, ib++)
        {
            int nza = 0;
            int nzb = 0;
            
            char ca = charAt(a, ia);
            char cb = charAt(b, ib);
            
            while (isSpace(ca) || ca == '0')
            {
                nza = ca == '0' ? nza + 1 : 0;
                ca = charAt(a, ++ia);
            }
            
            while (isSpace(cb) || cb == '0')
            {
                nzb = cb == '0' ? nzb + 1 : 0;
                cb = charAt(b, ++ib);
            }
            
            int result;
            if (isDigit(ca) && isDigit(cb))
                if ((result = compareRight(a.substring(ia), b.substring(ib))) != 0)
                    return result;
            
            if (ca == 0 && cb == 0)
                return nza - nzb;
            
            if (ca < cb)
                return -1;
            if (ca > cb)
                return +1;
        }
    }
}