daoadresseservice/util/NaturalOrderComparator.java

package dk.daoas.daoadresseservice.util;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/*
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.
*/


public class NaturalOrderComparator<T> implements Comparator<T>
{
    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 int compare(T o1, T o2)
    {
        String a = o1.toString();
        String b = o2.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);
        }
    }

    public static void main(String[] args)
    {
        String[] strings = new String[] { "1-2", "1-02", "1-20", "10-20", "fred", "jane", "pic01",
            "pic2", "pic02", "pic02a", "pic3", "pic4", "pic 4 else", "pic 5", "pic05", "pic 5",
            "pic 5 something", "pic 6", "pic   7", "pic100", "pic100a", "pic120", "pic121",
            "pic02000", "tom", "x2-g8", "x2-y7", "x2-y08", "x8-y8" };

        List orig = Arrays.asList(strings);

        System.out.println("Original: " + orig);

        List scrambled = Arrays.asList(strings);
        Collections.shuffle(scrambled);

        System.out.println("Scrambled: " + scrambled);

        Collections.sort(scrambled, new NaturalOrderComparator());

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