KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > fr > dyade > aaa > util > Arrays


1 /*
2  * Copyright (C) 1996 - 2000 BULL
3  * Copyright (C) 1996 - 2000 INRIA
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2.1 of the License, or any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
18  * USA.
19  */
20 package fr.dyade.aaa.util;
21
22 /**
23  * This class contains various methods for sorting and searching int arrays.
24  */
25 public class Arrays {
26   /**
27    * Sorts the specified array of ints into ascending numerical order.
28    * The sorting algorithm is a tuned quicksort.
29    *
30    * @param a the array to be sorted.
31    */
32   public static void sort(short[] a) {
33     sort1(a, 0, a.length);
34   }
35
36   /**
37    * Sorts the specified range of the specified array of ints into
38    * ascending numerical order.
39    */
40   public static void sort(short[] a, int fromIndex, int toIndex) {
41     rangeCheck(a.length, fromIndex, toIndex);
42     sort1(a, fromIndex, toIndex-fromIndex);
43   }
44
45   /**
46    * Sorts the specified sub-array of integers into ascending order.
47    */
48   private static void sort1(short x[], int off, int len) {
49     // Insertion sort on smallest arrays
50 if (len < 7) {
51       for (int i=off; i<len+off; i++)
52         for (int j=i; j>off && x[j-1]>x[j]; j--)
53           swap(x, j, j-1);
54       return;
55     }
56
57     // Choose a partition element, v
58 int m = off + len/2; // Small arrays, middle element
59 if (len > 7) {
60       int l = off;
61       int n = off + len - 1;
62       if (len > 40) { // Big arrays, pseudomedian of 9
63 int s = len/8;
64         l = med3(x, l, l+s, l+2*s);
65         m = med3(x, m-s, m, m+s);
66         n = med3(x, n-2*s, n-s, n);
67       }
68       m = med3(x, l, m, n); // Mid-size, med of 3
69 }
70     int v = x[m];
71
72     // Establish Invariant: v* (<v)* (>v)* v*
73 int a = off, b = a, c = off + len - 1, d = c;
74     while(true) {
75       while (b <= c && x[b] <= v) {
76         if (x[b] == v)
77           swap(x, a++, b);
78         b++;
79       }
80       while (c >= b && x[c] >= v) {
81         if (x[c] == v)
82           swap(x, c, d--);
83         c--;
84       }
85       if (b > c)
86         break;
87       swap(x, b++, c--);
88     }
89
90     // Swap partition elements back to middle
91 int s, n = off + len;
92     s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
93     s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
94
95     // Recursively sort non-partition-elements
96 if ((s = b-a) > 1)
97       sort1(x, off, s);
98     if ((s = d-c) > 1)
99       sort1(x, n-s, s);
100   }
101
102   /**
103    * Swaps x[a] with x[b].
104    */
105   private static void swap(short x[], int a, int b) {
106     short t = x[a];
107     x[a] = x[b];
108     x[b] = t;
109   }
110
111   /**
112    * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
113    */
114   private static void vecswap(short x[], int a, int b, int n) {
115     for (int i=0; i<n; i++, a++, b++)
116       swap(x, a, b);
117   }
118
119   /**
120    * Returns the index of the median of the three indexed integers.
121    */
122   private static int med3(short x[], int a, int b, int c) {
123     return (x[a] < x[b] ?
124             (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
125             (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
126   }
127
128   /**
129    * Check that fromIndex and toIndex are in range, and throw an
130    * appropriate exception if they aren't.
131    */
132   private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {
133     if (fromIndex > toIndex)
134       throw new IllegalArgumentException JavaDoc("fromIndex(" + fromIndex +
135                                          ") > toIndex(" + toIndex+")");
136     if (fromIndex < 0)
137       throw new ArrayIndexOutOfBoundsException JavaDoc(fromIndex);
138     if (toIndex > arrayLen)
139       throw new ArrayIndexOutOfBoundsException JavaDoc(toIndex);
140   }
141
142   /**
143    * Searches the specified array of ints for the specified value using the
144    * binary search algorithm. The array <strong>must</strong> be sorted (as
145    * by the <tt>sort</tt> method, above) prior to making this call.
146    */
147   public static int binarySearch(short[] a, int key) {
148     int low = 0;
149     int high = a.length-1;
150
151     while (low <= high) {
152       int mid =(low + high)/2;
153       int midVal = a[mid];
154
155       if (midVal < key)
156         low = mid + 1;
157       else if (midVal > key)
158         high = mid - 1;
159       else
160         return mid; // key found
161 }
162     return -(low + 1); // key not found.
163 }
164
165   /**
166    * Returns <tt>true</tt> if the two specified arrays of shorts are
167    * <i>equal</i> to one another.
168    */
169   public static boolean equals(short[] a, short a2[]) {
170     if (a==a2)
171       return true;
172     if (a==null || a2==null)
173       return false;
174
175     int length = a.length;
176     if (a2.length != length)
177       return false;
178
179     for (int i=0; i<length; i++)
180       if (a[i] != a2[i])
181         return false;
182
183     return true;
184   }
185 }
186
Popular Tags