001    /*
002     * Sort
003     * 
004     * Copyright (c) 2001, 2002, 2003 Marco Schmidt.
005     * All rights reserved.
006     */
007    
008    package net.sourceforge.jiu.util;
009    
010    import net.sourceforge.jiu.util.ComparatorInterface;
011    
012    /**
013     * Provides sorting of an Object array.
014     * @author Marco Schmidt
015     */
016    public class Sort
017    {
018            /**
019             * This class is supposed to have static methods only.
020             * To hide any constructor, we define an empty private one.
021             */
022            private Sort()
023            {
024            }
025    
026            /**
027             * Sorts some (or all) elements of an Object array according to a specified comparator.
028             * This method does exactly the same as java.util.Arrays.sort(Object[], int, int, Comparator).
029             * Unfortunately, this method is not available in Java 1.1, so it must be provided here.
030             * <p>
031             * As for the implementation of this method, it is taken from Arrays.java as found in 
032             * Classpath 0.0.2 (2001-01-06).
033             * Go to <a href="http://www.classpath.org">www.classpath.org</a> to learn more
034             * about the project, which implements the Java core libraries under the GPL.
035             *
036             * @param a the array which is to be sorted
037             * @param from the index value of the first element of the interval to be sorted
038             * @param to the index value of the last element of the interval to be sorted
039             * @param c the comparator used to query the relation between two objects
040             */
041            public static void sort(Object[] a, int from, int to, ComparatorInterface c)
042            {
043                    if (a == null)
044                    {
045                            throw new IllegalArgumentException("The object array to be sorted must be non-null.");
046                    }
047                    if (from > to)
048                    {
049                            throw new IllegalArgumentException("The from parameter (" + from + ") must be smaller than or equal to the to parameter (" + to + ").");
050                    }
051                    if (to >= a.length)
052                    {
053                            throw new IllegalArgumentException("The to parameter (" + to + ") must be smaller than the array length (" + a.length + ").");
054                    }
055                    if (c == null)
056                    {
057                            throw new IllegalArgumentException("The comparator parameter must be non-null.");
058                    }
059                    // First presort the array in chunks of length 6 with insertion sort. 
060                    // mergesort would give too much overhead for this length.
061                    for (int chunk = from; chunk < to; chunk += 6)
062                    {
063                            int end = Math.min(chunk + 6, to);
064                            for (int i = chunk + 1; i < end; i++)
065                            {
066                                    if (c.compare(a[i - 1], a[i]) > 0)
067                                    {
068                                            // not already sorted
069                                            int j = i;
070                                            Object elem = a[j];
071                                            do
072                      {
073                        a[j] = a[j - 1];
074                        j--;
075                      }
076                    while (j > chunk && c.compare(a[j - 1], elem) > 0);
077                    a[j] = elem;
078                  }
079              }
080          }
081    
082        int len = to - from;
083        // If length is smaller or equal 6 we are done.
084        if (len <= 6)
085          return;
086    
087        Object[]src = a;
088        Object[]dest = new Object[len];
089        Object[]t = null;           // t is used for swapping src and dest
090    
091        // The difference of the fromIndex of the src and dest array.
092        int srcDestDiff = -from;
093    
094        // The merges are done in this loop
095        for (int size = 6; size < len; size <<= 1)
096          {
097            for (int start = from; start < to; start += size << 1)
098              {
099                // mid ist the start of the second sublist;
100                // end the start of the next sublist (or end of array).
101                int mid = start + size;
102                int end = Math.min(to, mid + size);
103    
104                // The second list is empty or the elements are already in
105                // order - no need to merge
106                if (mid >= end || c.compare(src[mid - 1], src[mid]) <= 0)
107                  {
108                    System.arraycopy(src, start,
109                                     dest, start + srcDestDiff, end - start);
110    
111                    // The two halves just need swapping - no need to merge
112                  }
113                else if (c.compare(src[start], src[end - 1]) > 0)
114                  {
115                    System.arraycopy(src, start,
116                                     dest, end - size + srcDestDiff, size);
117                    System.arraycopy(src, mid,
118                                     dest, start + srcDestDiff, end - mid);
119    
120                  }
121                else
122                  {
123                    // Declare a lot of variables to save repeating
124                    // calculations.  Hopefully a decent JIT will put these
125                    // in registers and make this fast
126                    int p1 = start;
127                    int p2 = mid;
128                    int i = start + srcDestDiff;
129    
130                    // The main merge loop; terminates as soon as either
131                    // half is ended
132                    while (p1 < mid && p2 < end)
133                      {
134                        dest[i++] =
135                          src[c.compare(src[p1], src[p2]) <= 0 ? p1++ : p2++];
136                      }
137    
138                    // Finish up by copying the remainder of whichever half
139                    // wasn't finished.
140                    if (p1 < mid)
141                      System.arraycopy(src, p1, dest, i, mid - p1);
142                    else
143                      System.arraycopy(src, p2, dest, i, end - p2);
144                  }
145              }
146            // swap src and dest ready for the next merge
147            t = src;
148            src = dest;
149            dest = t;
150            from += srcDestDiff;
151            to += srcDestDiff;
152            srcDestDiff = -srcDestDiff;
153                    }
154    
155            // make sure the result ends up back in the right place.  Note
156                // that src and dest may have been swapped above, so src 
157            // contains the sorted array.
158            if (src != a)
159            {
160                            // Note that from == 0.
161                            System.arraycopy(src, 0, a, srcDestDiff, to);
162                    }
163            }
164    
165            /**
166             * Sort the complete argument array according to the argument comparator.
167             * Simply calls <code>sort(a, 0, a.length - 1, comparator);</code>
168             * @param a array to be sorted
169             * @param comparator the comparator used to compare to array entries
170             */
171            public static void sort(Object[] a, ComparatorInterface comparator)
172            {
173                    sort(a, 0, a.length - 1, comparator);
174            }
175    }