Java > Open Source Codes > prefuse > util > ArrayLib


1 package prefuse.util;
2
3 import java.io.BufferedReader ;
4 import java.io.FileReader ;
5 import java.util.Comparator ;
6 import java.util.Random ;
7 import java.util.StringTokenizer ;
8
9 /**
10  * Library of supplementary array routines not
11  * supported by the java.util.Arrays class.
12  *
13  * @author jeffrey heer
14  */
15 public abstract class ArrayLib {
16     
17     /**
18      * Arrays with lengths beneath this value will be insertion sorted.
19      */
20     public static final int SORT_THRESHOLD = 30;
21     
22     // ------------------------------------------------------------------------
23 // Shuffle
24
25     /**
26      * Randomly permute the contents of an array.
27      * @param a the array to shuffle
28      * @param r the source of randomness to use
29      */
30     public static final void shuffle(int[] a, Random r) {
31         shuffle(a, 0, a.length, r);
32     }
33     
34     /**
35      * Randomly permute the contents of a range an array.
36      * @param a the array to shuffle
37      * @param start the starting index of the range to shuffle
38      * @param len then length of the range to shuffle
39      * @param r the source of randomness to use
40      */
41     public static final void shuffle(int[] a, int start, int len, Random r) {
42         for ( int i=start+len; --i>0; ) {
43             int t = a[i], j = r.nextInt(i);
44             a[i] = a[j];
45             a[j] = t;
46         }
47     }
48     
49     /**
50      * Randomly permute the contents of an array.
51      * @param a the array to shuffle
52      * @param r the source of randomness to use
53      */
54     public static final void shuffle(long[] a, Random r) {
55         shuffle(a, 0, a.length, r);
56     }
57     
58     /**
59      * Randomly permute the contents of a range an array.
60      * @param a the array to shuffle
61      * @param start the starting index of the range to shuffle
62      * @param len then length of the range to shuffle
63      * @param r the source of randomness to use
64      */
65     public static final void shuffle(long[] a, int start, int len, Random r) {
66         for ( int i=start+len; i>1; --i ) {
67             long t = a[i];
68             int j = r.nextInt(i);
69             a[i] = a[j];
70             a[j] = t;
71         }
72     }
73     
74     /**
75      * Randomly permute the contents of an array.
76      * @param a the array to shuffle
77      * @param r the source of randomness to use
78      */
79     public static final void shuffle(float[] a, Random r) {
80         shuffle(a, 0, a.length, r);
81     }
82     
83     /**
84      * Randomly permute the contents of a range an array.
85      * @param a the array to shuffle
86      * @param start the starting index of the range to shuffle
87      * @param len then length of the range to shuffle
88      * @param r the source of randomness to use
89      */
90     public static final void shuffle(float[] a, int start, int len, Random r) {
91         for ( int i=start+len; i>1; --i ) {
92             float t = a[i];
93             int j = r.nextInt(i);
94             a[i] = a[j];
95             a[j] = t;
96         }
97     }
98     
99     /**
100      * Randomly permute the contents of an array.
101      * @param a the array to shuffle
102      * @param r the source of randomness to use
103      */
104     public static final void shuffle(double[] a, Random r) {
105         shuffle(a, 0, a.length, r);
106     }
107     
108     /**
109      * Randomly permute the contents of a range an array.
110      * @param a the array to shuffle
111      * @param start the starting index of the range to shuffle
112      * @param len then length of the range to shuffle
113      * @param r the source of randomness to use
114      */
115     public static final void shuffle(double[] a, int start, int len, Random r) {
116         for ( int i=start+len; i>1; --i ) {
117             double t = a[i];
118             int j = r.nextInt(i);
119             a[i] = a[j];
120             a[j] = t;
121         }
122     }
123     
124     /**
125      * Randomly permute the contents of an array.
126      * @param a the array to shuffle
127      * @param r the source of randomness to use
128      */
129     public static final void shuffle(Object [] a, Random r) {
130         shuffle(a, 0, a.length, r);
131     }
132     
133     /**
134      * Randomly permute the contents of a range an array.
135      * @param a the array to shuffle
136      * @param start the starting index of the range to shuffle
137      * @param len then length of the range to shuffle
138      * @param r the source of randomness to use
139      */
140     public static final void shuffle(Object [] a, int start, int len, Random r) {
141         for ( int i=start+len; i>1; --i ) {
142             Object t = a[i];
143             int j = r.nextInt(i);
144             a[i] = a[j];
145             a[j] = t;
146         }
147     }
148     
149     // ------------------------------------------------------------------------
150 // Max / Min / Sum
151
152     /**
153      * Find the maximum value in an array.
154      * @param a the array
155      * @return the maximum value in the array
156      */
157     public static final double max(double[] a) {
158         double max = Double.NEGATIVE_INFINITY;
159         for ( int i=0; i<a.length; ++i ) {
160             if ( a[i] > max )
161                 max = a[i];
162         }
163         return max;
164     }
165
166     /**
167      * Find the minimum value in an array.
168      * @param a the array
169      * @return the minimum value in the array
170      */
171     public static final double min(double[] a) {
172         double min = Double.POSITIVE_INFINITY;
173         for ( int i=0; i<a.length; ++i ) {
174             if ( a[i] < min )
175                 min = a[i];
176         }
177         return min;
178     }
179     
180     /**
181      * Compute the sum of the values in an array.
182      * @param a the array
183      * @return the sum of the values in the array
184      */
185     public static final double sum(double[] a) {
186         double sum = 0;
187         for ( int i=0; i<a.length; ++i ) {
188             sum += a[i];
189         }
190         return sum;
191     }
192     
193     //// -----------------------------------------------
194 //// -- Searching Functions ------------------------
195
196     /**
197      * Perform a binary search over a sorted array for the given key.
198      * @param a the array to search
199      * @param key the key to search for
200      * @return the index of the given key if it exists in the array,
201      * otherwise -1 times the index value at the insertion point that
202      * would be used if the key were added to the array.
203      */
204     public static final int binarySearch(int[] a, int key) {
205         int x1 = 0;
206         int x2 = a.length;
207         int i = x2 / 2;
208         while (x1 < x2) {
209             if (a[i] == key) {
210                 return i;
211             } else if (a[i] < key) {
212                 x1 = i + 1;
213             } else {
214                 x2 = i;
215             }
216             i = x1 + (x2 - x1) / 2;
217         }
218         return -1*(i+1);
219     }
220
221     /**
222      * Perform a binary search over a sorted range of an array for the given
223      * key. The range is assumed to start at index 0.
224      * @param a the array to search
225      * @param key the key to search for
226      * @param length the the length of the range to search over.
227      * @return the index of the given key if it exists in the array,
228      * otherwise -1 times the index value at the insertion point that
229      * would be used if the key were added to the array.
230      */
231     public static final int binarySearch(int[] a, int key, int length) {
232         int x1 = 0;
233         int x2 = length;
234         int i = x2 / 2;
235
236         while (x1 < x2) {
237             if (a[i] == key) {
238                 return i;
239             } else if (a[i] < key) {
240                 x1 = i + 1;
241             } else {
242                 x2 = i;
243             }
244             i = x1 + (x2 - x1) / 2;
245         }
246         return -1*(i+1);
247     }
248
249     /**
250      * Perform a binary search over a sorted range of an array for the given
251      * key.
252      * @param a the array to search
253      * @param key the key to search for
254      * @param begin the starting index of the range
255      * @param end the ending index of the range, exclusive
256      * @return the index of the given key if it exists in the array,
257      * otherwise -1 times the index value at the insertion point that
258      * would be used if the key were added to the array.
259      */
260     public static final int binarySearch(int[] a, int key, int begin, int end) {
261         int x1 = begin;
262         int x2 = end;
263         int i = x1 + (x2 - x1) / 2;
264
265         while (x1 < x2) {
266             if (a[i] == key) {
267                 return i;
268             } else if (a[i] < key) {
269                 x1 = i + 1;
270             } else {
271                 x2 = i;
272             }
273             i = x1 + (x2 - x1) / 2;
274         }
275
276         return -1*(i+1);
277     }
278
279     /**
280      * Perform a binary search over a sorted array for the given key.
281      * @param a the array to search
282      * @param key the key to search for
283      * @return the index of the given key if it exists in the array,
284      * otherwise -1 times the index value at the insertion point that
285      * would be used if the key were added to the array.
286      */
287     public static final int binarySearch(Object [] a, Object key) {
288         int x1 = 0;
289         int x2 = a.length;
290         int i = x2 / 2, c;
291         while (x1 < x2) {
292             c = ((Comparable )a[i]).compareTo(key);
293             if (c == 0) {
294                 return i;
295             } else if (c < 0) {
296                 x1 = i + 1;
297             } else {
298                 x2 = i;
299             }
300             i = x1 + (x2 - x1) / 2;
301         }
302         return -1*(i+1);
303     }
304
305     /**
306      * Perform a binary search over a sorted range of an array for the given
307      * key. The range is assumed to start at index 0.
308      * @param a the array to search
309      * @param key the key to search for
310      * @param length the the length of the range to search over.
311      * @return the index of the given key if it exists in the array,
312      * otherwise -1 times the index value at the insertion point that
313      * would be used if the key were added to the array.
314      */
315     public static final int binarySearch(Object [] a, Object key, int length) {
316         int x1 = 0;
317         int x2 = length;
318         int i = x2 / 2, c;
319
320         while (x1 < x2) {
321             c = ((Comparable )a[i]).compareTo(key);
322             if (c == 0) {
323                 return i;
324             } else if (c < 0) {
325                 x1 = i + 1;
326             } else {
327                 x2 = i;
328             }
329             i = x1 + (x2 - x1) / 2;
330         }
331         return -1*(i+1);
332     }
333
334     /**
335      * Perform a binary search over a sorted range of an array for the given
336      * key.
337      * @param a the array to search
338      * @param key the key to search for
339      * @param begin the starting index of the range
340      * @param end the ending index of the range, exclusive
341      * @return the index of the given key if it exists in the array,
342      * otherwise -1 times the index value at the insertion point that
343      * would be used if the key were added to the array.
344      */
345     public static final int binarySearch(Object [] a, Object key, int begin, int end) {
346         int x1 = begin;
347         int x2 = end;
348         int i = x1 + (x2 - x1) / 2, c;
349
350         while (x1 < x2) {
351             c = ((Comparable )a[i]).compareTo(key);
352             if (c == 0) {
353                 return i;
354             } else if (c < 0) {
355                 x1 = i + 1;
356             } else {
357                 x2 = i;
358             }
359             i = x1 + (x2 - x1) / 2;
360         }
361
362         return -1*(i+1);
363     }
364
365     /**
366      * Perform a binary search over a sorted array for the given key.
367      * @param a the array to search
368      * @param key the key to search for
369      * @param cp the comparator to use to compare key values
370      * @return the index of the given key if it exists in the array,
371      * otherwise -1 times the index value at the insertion point that
372      * would be used if the key were added to the array.
373      */
374     public static final int binarySearch(Object [] a, Object key, Comparator cp) {
375         int x1 = 0;
376         int x2 = a.length;
377         int i = x2 / 2, c;
378         while (x1 < x2) {
379             c = cp.compare(a[i], key);
380             if (c == 0) {
381                 return i;
382             } else if (c < 0) {
383                 x1 = i + 1;
384             } else {
385                 x2 = i;
386             }
387             i = x1 + (x2 - x1) / 2;
388         }
389         return -1*(i+1);
390     }
391
392     /**
393      * Perform a binary search over a sorted range of an array for the given
394      * key. The range is assumed to start at index 0.
395      * @param a the array to search
396      * @param key the key to search for
397      * @param cp the comparator to use to compare key values
398      * @param length the the length of the range to search over.
399      * @return the index of the given key if it exists in the array,
400      * otherwise -1 times the index value at the insertion point that
401      * would be used if the key were added to the array.
402      */
403     public static final int binarySearch(Object [] a, Object key, Comparator cp, int length) {
404         int x1 = 0;
405         int x2 = length;
406         int i = x2 / 2, c;
407
408         while (x1 < x2) {
409             c = cp.compare(a[i], key);
410             if (c == 0) {
411                 return i;
412             } else if (c < 0) {
413                 x1 = i + 1;
414             } else {
415                 x2 = i;
416             }
417             i = x1 + (x2 - x1) / 2;
418         }
419         return -1*(i+1);
420     }
421
422     /**
423      * Perform a binary search over a sorted range of an array for the given
424      * key.
425      * @param a the array to search
426      * @param key the key to search for
427      * @param cp the comparator to use to compare key values
428      * @param begin the starting index of the range
429      * @param end the ending index of the range, exclusive
430      * @return the index of the given key if it exists in the array,
431      * otherwise -1 times the index value at the insertion point that
432      * would be used if the key were added to the array.
433      */
434     public static final int binarySearch(Object [] a, Object key, Comparator cp, int begin, int end) {
435         int x1 = begin;
436         int x2 = end;
437         int i = x1 + (x2 - x1) / 2, c;
438
439         while (x1 < x2) {
440             c = cp.compare(a[i], key);
441             if (c == 0) {
442                 return i;
443             } else if (c < 0) {
444                 x1 = i + 1;
445             } else {
446                 x2 = i;
447             }
448             i = x1 + (x2 - x1) / 2;
449         }
450
451         return -1*(i+1);
452     }
453
454     //// -----------------------------------------------
455 //// -- Finding Functions --------------------------
456
457     /**
458      * Linearly search an array for a given key value.
459      * @param a the array to search
460      * @param key the key to search for
461      * @return the index of the first occurrence of the key in the array,
462      * of -1 if the key is not found.
463      */
464     public static final int find(int[] a, int key) {
465         for (int i = 0; i < a.length; i++) {
466             if (a[i] == key) {
467                 return i;
468             }
469         }
470         return -1;
471     }
472
473     /**
474      * Linearly search an array range for a given key value. Assumes that
475      * the range begins at index 0.
476      * @param a the array to search
477      * @param key the key to search for
478      * @param length the length of the range to search over
479      * @return the index of the first occurrence of the key in the array,
480      * of -1 if the key is not found.
481      */
482     public static final int find(int[] a, int key, int length) {
483         for (int i = 0; i < length; i++) {
484             if (a[i] == key) {
485                 return i;
486             }
487         }
488         return -1;
489     }
490
491     /**
492      * Linearly search an array range for a given key value.
493      * @param a the array to search
494      * @param key the key to search for
495      * @param begin the starting index of the range
496      * @param end the ending index of the range, exclusive
497      * @return the index of the first occurrence of the key in the array,
498      * of -1 if the key is not found.
499      */
500     public static final int find(int[] a, int key, int begin, int end) {
501         for (int i = begin; i < end; i++) {
502             if (a[i] == key) {
503                 return i;
504             }
505         }
506         return -1;
507     }
508
509     //// -----------------------------------------------
510 //// -- Resizing Functions -------------------------
511
512     /**
513      * Resize the given array as needed to meet a target size.
514      * @param a the array to potentially resize
515      * @param size the minimum size of the target array
516      * @return the resized array, if the original array meets the size
517      * requirement, it is simply return, otherwise a new array is
518      * allocated and the contents of the original array are copied over.
519      */
520     public static final int[] resize(int[] a, int size) {
521         if ( a.length >= size ) return a;
522         int[] b = new int[size];
523         System.arraycopy(a, 0, b, 0, a.length);
524         return b;
525     }
526     
527     /**
528      * Resize the given array as needed to meet a target size.
529      * @param a the array to potentially resize
530      * @param size the minimum size of the target array
531      * @return the resized array, if the original array meets the size
532      * requirement, it is simply return, otherwise a new array is
533      * allocated and the contents of the original array are copied over.
534      */
535     public static final float[] resize(float[] a, int size) {
536         if ( a.length >= size ) return a;
537         float[] b = new float[size];
538         System.arraycopy(a, 0, b, 0, a.length);
539         return b;
540     }
541     
542     /**
543      * Resize the given array as needed to meet a target size.
544      * @param a the array to potentially resize
545      * @param size the minimum size of the target array
546      * @return the resized array, if the original array meets the size
547      * requirement, it is simply return, otherwise a new array is
548      * allocated and the contents of the original array are copied over.
549      */
550     public static final double[] resize(double[] a, int size) {
551         if ( a.length >= size ) return a;
552         double[] b = new double[size];
553         System.arraycopy(a, 0, b, 0, a.length);
554         return b;
555     }
556     
557     /**
558      * Resize the given array as needed to meet a target size.
559      * @param a the array to potentially resize
560      * @param size the minimum size of the target array
561      * @return the resized array, if the original array meets the size
562      * requirement, it is simply return, otherwise a new array is
563      * allocated and the contents of the original array are copied over.
564      */
565     public static final Object [] resize(Object [] a, int size) {
566         if ( a.length >= size ) return a;
567         Object [] b = new Object [size];
568         System.arraycopy(a, 0, b, 0, a.length);
569         return b;
570     }
571
572     /**
573      * Trims an array to be exactly the target a size.
574      * @param a the array to trim
575      * @param size the desired size of the array. This value must be lesser
576      * than or equal to the size of the input array.
577      * @return a trimmed array instance
578      */
579     public static final int[] trim(int[] a, int size) {
580         //assert (size <= a.length);
581 if ( a.length == size ) {
582             return a;
583         } else {
584             int[] b = new int[size];
585             System.arraycopy(a, 0, b, 0, size);
586             return b;
587         }
588     }
589
590     /**
591      * Trims an array to be exactly the target a size.
592      * @param a the array to trim
593      * @param size the desired size of the array. This value must be lesser
594      * than or equal to the size of the input array.
595      * @return a trimmed array instance
596      */
597     public static final float[] trim(float[] a, int size) {
598         //assert (size <= a.length);
599 if ( a.length == size ) {
600             return a;
601         } else {
602             float[] b = new float[size];
603             System.arraycopy(a, 0, b, 0, size);
604             return b;
605         }
606     }
607     
608     /**
609      * Trims an array to be exactly the target a size.
610      * @param a the array to trim
611      * @param size the desired size of the array. This value must be lesser
612      * than or equal to the size of the input array.
613      * @return a trimmed array instance
614      */
615     public static final double[] trim(double[] a, int size) {
616         //assert (size <= a.length);
617 if ( a.length == size ) {
618             return a;
619         } else {
620             double[] b = new double[size];
621             System.arraycopy(a, 0, b, 0, size);
622             return b;
623         }
624     }
625     
626     /**
627      * Trims an array to be exactly the target a size.
628      * @param a the array to trim
629      * @param size the desired size of the array. This value must be lesser
630      * than or equal to the size of the input array.
631      * @return a trimmed array instance
632      */
633     public static final Object [] trim(Object [] a, int size) {
634         //assert (size <= a.length);
635 if ( a.length == size ) {
636             return a;
637         } else {
638             Object [] b = new Object [size];
639             System.arraycopy(a, 0, b, 0, size);
640             return b;
641         }
642     }
643     
644     //// -----------------------------------------------
645 //// -- Sorting Functions --------------------------
646
647     // -- int / double sorting ------------------------------------------
648
649     /**
650      * Sort two arrays simultaneously, using the sort order of the values
651      * in the first array to determine the sort order for both arrays.
652      * @param a the array to sort by
653      * @param b the array to re-arrange based on the sort order of the
654      * first array.
655      */
656     public static final void sort(int[] a, double[] b) {
657         mergesort(a, b, 0, a.length - 1);
658     }
659
660     /**
661      * Sort two arrays simultaneously, using the sort order of the values
662      * in the first array to determine the sort order for both arrays.
663      * @param a the array to sort by
664      * @param b the array to re-arrange based on the sort order of the
665      * first array.
666      * @param length the array range length to sort over
667      */
668     public static final void sort(int[] a, double[] b, int length) {
669         mergesort(a, b, 0, length - 1);
670     }
671
672     /**
673      * Sort two arrays simultaneously, using the sort order of the values
674      * in the first array to determine the sort order for both arrays.
675      * @param a the array to sort by
676      * @param b the array to re-arrange based on the sort order of the
677      * first array.
678      * @param begin the start index of the range to sort
679      * @param end the end index, exclusive, of the range to sort
680      */
681     public static final void sort(int[] a, double[] b, int begin, int end) {
682         mergesort(a, b, begin, end - 1);
683     }
684
685     // -- Insertion Sort --
686
687     protected static final void insertionsort(int[] a, double[] b, int p, int r) {
688         for (int j = p + 1; j <= r; ++j) {
689             int key = a[j];
690             double val = b[j];
691             int i = j - 1;
692             while (i >= p && a[i] > key) {
693                 a[i + 1] = a[i];
694                 b[i + 1] = b[i];
695                 i--;
696             }
697             a[i + 1] = key;
698             b[i + 1] = val;
699         }
700     }
701
702     // -- Mergesort --
703
704     protected static final void mergesort(int[] a, double[] b, int p, int r) {
705         if (p >= r) {
706             return;
707         }
708         if (r - p + 1 < SORT_THRESHOLD) {
709             insertionsort(a, b, p, r);
710         } else {
711             int q = (p + r) / 2;
712             mergesort(a, b, p, q);
713             mergesort(a, b, q + 1, r);
714             merge(a, b, p, q, r);
715         }
716     }
717
718     protected static final void merge(int[] a, double[] b, int p, int q, int r) {
719         int[] t = new int[r - p + 1];
720         double[] v = new double[r - p + 1];
721         int i, p1 = p, p2 = q + 1;
722         for (i = 0; p1 <= q && p2 <= r; ++i) {
723             if (a[p1] < a[p2]) {
724                 v[i] = b[p1];
725                 t[i] = a[p1++];
726             } else {
727                 v[i] = b[p2];
728                 t[i] = a[p2++];
729             }
730         }
731         for (; p1 <= q; ++p1, ++i) {
732             v[i] = b[p1];
733             t[i] = a[p1];
734         }
735         for (; p2 <= r; ++p2, ++i) {
736             v[i] = b[p2];
737             t[i] = a[p2];
738         }
739         for (i = 0, p1 = p; i < t.length; ++i, ++p1) {
740             b[p1] = v[i];
741             a[p1] = t[i];
742         }
743     }
744
745     // -- int / int sorting ---------------------------------------------
746
747     /**
748      * Sort two arrays simultaneously, using the sort order of the values
749      * in the first array to determine the sort order for both arrays.
750      * @param a the array to sort by
751      * @param b the array to re-arrange based on the sort order of the
752      * first array.
753      */
754     public static final void sort(int[] a, int[] b) {
755         mergesort(a, b, 0, a.length - 1);
756     }
757
758     /**
759      * Sort two arrays simultaneously, using the sort order of the values
760      * in the first array to determine the sort order for both arrays.
761      * @param a the array to sort by
762      * @param b the array to re-arrange based on the sort order of the
763      * first array.
764      * @param length the array range length to sort over
765      */
766     public static final void sort(int[] a, int[] b, int length) {
767         mergesort(a, b, 0, length - 1);
768     }
769
770     /**
771      * Sort two arrays simultaneously, using the sort order of the values
772      * in the first array to determine the sort order for both arrays.
773      * @param a the array to sort by
774      * @param b the array to re-arrange based on the sort order of the
775      * first array.
776      * @param begin the start index of the range to sort
777      * @param end the end index, exclusive, of the range to sort
778      */
779     public static final void sort(int[] a, int[] b, int begin, int end) {
780         mergesort(a, b, begin, end - 1);
781     }
782
783     // -- Insertion Sort --
784
785     protected static final void insertionsort(int[] a, int[] b, int p, int r) {
786         for (int j = p + 1; j <= r; ++j) {
787             int key = a[j];
788             int val = b[j];
789             int i = j - 1;
790             while (i >= p && a[i] > key) {
791                 a[i + 1] = a[i];
792                 b[i + 1] = b[i];
793                 i--;
794             }
795             a[i + 1] = key;
796             b[i + 1] = val;
797         }
798     }
799
800     // -- Mergesort --
801
802     protected static final void mergesort(int[] a, int[] b, int p, int r) {
803         if (p >= r) {
804             return;
805         }
806         if (r - p + 1 < SORT_THRESHOLD) {
807             insertionsort(a, b, p, r);
808         } else {
809             int q = (p + r) / 2;
810             mergesort(a, b, p, q);
811             mergesort(a, b, q + 1, r);
812             merge(a, b, p, q, r);
813         }
814     }
815
816     protected static final void merge(int[] a, int[] b, int p, int q, int r) {
817         int[] t = new int[r - p + 1];
818         int[] v = new int[r - p + 1];
819         int i, p1 = p, p2 = q + 1;
820         for (i = 0; p1 <= q && p2 <= r; ++i) {
821             if (a[p1] < a[p2]) {
822                 v[i] = b[p1];
823                 t[i] = a[p1++];
824             } else {
825                 v[i] = b[p2];
826                 t[i] = a[p2++];
827             }
828         }
829         for (; p1 <= q; ++p1, ++i) {
830             v[i] = b[p1];
831             t[i] = a[p1];
832         }
833         for (; p2 <= r; ++p2, ++i) {
834             v[i] = b[p2];
835             t[i] = a[p2];
836         }
837         for (i = 0, p1 = p; i < t.length; ++i, ++p1) {
838             b[p1] = v[i];
839             a[p1] = t[i];
840         }
841     }
842
843     // -- int / Object sorting ---------------------------------------------
844
845     /**
846      * Sort two arrays simultaneously, using the sort order of the values
847      * in the first array to determine the sort order for both arrays.
848      * @param a the array to sort by
849      * @param b the array to re-arrange based on the sort order of the
850      * first array.
851      * @param begin the start index of the range to sort
852      * @param end the end index, exclusive, of the range to sort
853      */
854     public static final void sort(int[] a, Object [] b, int begin, int end) {
855         int length = end-begin;
856         
857         if ( length < SORT_THRESHOLD ) {
858             insertionsort(a, b, begin, end-1);
859             return;
860         }
861         
862         // allocate source arrays
863 int[] ks = new int[length];
864         Object [] vs = new Object [length];
865         for ( int i=0, idx=begin; i<length; ++i, ++idx ) {
866             ks[i] = a[idx];
867             vs[i] = b[idx];
868         }
869         mergesort(ks, a, vs, b, begin, end, -begin);
870     }
871     
872     /**
873      * Sort two arrays simultaneously, using the sort order of the values
874      * in the first array to determine the sort order for both arrays.
875      * @param a the array to sort by
876      * @param b the array to re-arrange based on the sort order of the
877      * first array.
878      * @param abuf a buffer array to perform the sorting without
879      * allocating any additional memory
880      * @param bbuf a buffer array to perform the sorting without
881      * allocating any additional memory
882      * @param begin the start index of the range to sort
883      * @param end the end index, exclusive, of the range to sort
884      */
885     public static final void sort(int[] a, Object [] b,
886             int[] abuf, Object [] bbuf, int begin, int end)
887     {
888         int length = end-begin;
889         
890         if ( length < SORT_THRESHOLD ) {
891             insertionsort(a, b, begin, end-1);
892             return;
893         }
894         
895         // allocate source arrays
896 for ( int i=0, idx=begin; i<length; ++i, ++idx ) {
897             abuf[i] = a[idx];
898             bbuf[i] = b[idx];
899         }
900         mergesort(abuf, a, bbuf, b, begin, end, -begin);
901     }
902
903     // -- Insertion Sort --
904
905     protected static final void insertionsort(int[] a, Object [] b, int p, int r) {
906         int i, key;
907         Object val;
908         for (int j = p + 1; j <= r; ++j) {
909             key = a[j];
910             val = b[j];
911             i = j - 1;
912             while (i >= p && a[i] > key) {
913                 a[i + 1] = a[i];
914                 b[i + 1] = b[i];
915                 i--;
916             }
917             a[i + 1] = key;
918             b[i + 1] = val;
919         }
920     }
921
922     // -- Mergesort --
923
924     protected static void mergesort(int ks[], int kd[], Object [] vs,
925             Object [] vd, int lo, int hi, int off)
926     {
927         int length = hi-lo;
928
929         if (length < SORT_THRESHOLD) {
930             insertionsort(kd, vd, lo, hi-1);
931             return;
932         }
933
934         // Recursively sort halves of dest into src
935 int dlo = lo;
936         int dhi = hi;
937         lo += off;
938         hi += off;
939         int mid = (lo + hi) >> 1;
940         mergesort(kd, ks, vd, vs, lo, mid, -off);
941         mergesort(kd, ks, vd, vs, mid, hi, -off);
942
943         // If list is already sorted, just copy from src to dest. This is an
944 // optimization that results in faster sorts for nearly ordered lists.
945 if ( ks[mid-1] <= ks[mid] ) {
946             System.arraycopy(ks, lo, kd, dlo, length);
947             System.arraycopy(vs, lo, vd, dlo, length);
948             return;
949         }
950
951         // Merge sorted halves (now in src) into dest
952 for (int i = dlo, p = lo, q = mid; i < dhi; i++) {
953             if (q >= hi || p < mid && ks[p] <= ks[q] ) {
954                 vd[i] = vs[p];
955                 kd[i] = ks[p++];
956             } else {
957                 vd[i] = vs[q];
958                 kd[i] = ks[q++];
959             }
960         }
961     }
962     
963     protected static final void merge(int[] a, Object [] b, int p, int q, int r) {
964         int[] t = new int[r - p + 1];
965         Object [] v = new Object [r - p + 1];
966         int i, p1 = p, p2 = q + 1;
967         for (i = 0; p1 <= q && p2 <= r; ++i) {
968             if (a[p1] < a[p2]) {
969                 v[i] = b[p1];
970                 t[i] = a[p1++];
971             } else {
972                 v[i] = b[p2];
973                 t[i] = a[p2++];
974             }
975         }
976         for (; p1 <= q; ++p1, ++i) {
977             v[i] = b[p1];
978             t[i] = a[p1];
979         }
980         for (; p2 <= r; ++p2, ++i) {
981             v[i] = b[p2];
982             t[i] = a[p2];
983         }
984         for (i = 0, p1 = p; i < t.length; ++i, ++p1) {
985             b[p1] = v[i];
986             a[p1] = t[i];
987         }
988     }
989
990     // -- double / int sorting -------------------------------------------
991
992     /**
993      * Sort two arrays simultaneously, using the sort order of the values
994      * in the first array to determine the sort order for both arrays.
995      * @param a the array to sort by
996      * @param b the array to re-arrange based on the sort order of the
997      * first array.
998      */
999     public static final void sort(double[] a, int[] b) {
1000        mergesort(a, b, 0, a.length - 1);
1001    }
1002
1003    /**
1004     * Sort two arrays simultaneously, using the sort order of the values
1005     * in the first array to determine the sort order for both arrays.
1006     * @param a the array to sort by
1007     * @param b the array to re-arrange based on the sort order of the
1008     * first array.
1009     * @param length the length of the range to be sorted
1010     */
1011    public static final void sort(double[] a, int[] b, int length) {
1012        mergesort(a, b, 0, length - 1);
1013    }
1014
1015    /**
1016     * Sort two arrays simultaneously, using the sort order of the values
1017     * in the first array to determine the sort order for both arrays.
1018     * @param a the array to sort by
1019     * @param b the array to re-arrange based on the sort order of the
1020     * first array.
1021     * @param begin the start index of the range to sort
1022     * @param end the end index, exclusive, of the range to sort
1023     */
1024    public static final void sort(double[] a, int[] b, int begin, int end) {
1025        mergesort(a, b, begin, end - 1);
1026    }
1027
1028    // -- Insertion Sort --
1029
1030    protected static final void insertionsort(double[] a, int[] b, int p, int r) {
1031        for (int j = p + 1; j <= r; ++j) {
1032            double key = a[j];
1033            int val = b[j];
1034            int i = j - 1;
1035            while (i >= p && a[i] > key) {
1036                a[i + 1] = a[i];
1037                b[i + 1] = b[i];
1038                --i;
1039            }
1040            a[i + 1] = key;
1041            b[i + 1] = val;
1042        }
1043    }
1044
1045    // -- Mergesort --
1046
1047    protected static final void mergesort(double[] a, int[] b, int p, int r) {
1048        if (p >= r) {
1049            return;
1050        }
1051        if (r - p + 1 < SORT_THRESHOLD) {
1052            insertionsort(a, b, p, r);
1053        } else {
1054            int q = (p + r) / 2;
1055            mergesort(a, b, p, q);
1056            mergesort(a, b, q + 1, r);
1057            merge(a, b, p, q, r);
1058        }
1059    }
1060
1061    protected static final void merge(double[] a, int[] b, int p, int q, int r) {
1062        double[] t = new double[r - p + 1];
1063        int[] v = new int[r - p + 1];
1064        int i, p1 = p, p2 = q + 1;
1065        for (i = 0; p1 <= q && p2 <= r; ++i) {
1066            if (a[p1] < a[p2]) {
1067                v[i] = b[p1];
1068                t[i] = a[p1++];
1069            } else {
1070                v[i] = b[p2];
1071                t[i] = a[p2++];
1072            }
1073        }
1074        for (; p1 <= q; ++p1, ++i) {
1075            v[i] = b[p1];
1076            t[i] = a[p1];
1077        }
1078        for (; p2 <= r; ++p2, ++i) {
1079            v[i] = b[p2];
1080            t[i] = a[p2];
1081        }
1082        for (i = 0, p1 = p; i < t.length; i++, p1++) {
1083            b[p1] = v[i];
1084            a[p1] = t[i];
1085        }
1086    }
1087    
1088    // -- float / int sorting -------------------------------------------
1089
1090    /**
1091     * Sort two arrays simultaneously, using the sort order of the values
1092     * in the first array to determine the sort order for both arrays.
1093     * @param a the array to sort by
1094     * @param b the array to re-arrange based on the sort order of the
1095     * first array.
1096     */
1097    public static final void sort(float[] a, int[] b) {
1098        mergesort(a, b, 0, a.length - 1);
1099    }
1100
1101    /**
1102     * Sort two arrays simultaneously, using the sort order of the values
1103     * in the first array to determine the sort order for both arrays.
1104     * @param a the array to sort by
1105     * @param b the array to re-arrange based on the sort order of the
1106     * first array.
1107     * @param length the length of the range to be sorted
1108     */
1109    public static final void sort(float[] a, int[] b, int length) {
1110        mergesort(a, b, 0, length - 1);
1111    }
1112
1113    /**
1114     * Sort two arrays simultaneously, using the sort order of the values
1115     * in the first array to determine the sort order for both arrays.
1116     * @param a the array to sort by
1117     * @param b the array to re-arrange based on the sort order of the
1118     * first array.
1119     * @param begin the start index of the range to sort
1120     * @param end the end index, exclusive, of the range to sort
1121     */
1122    public static final void sort(float[] a, int[] b, int begin, int end) {
1123        mergesort(a, b, begin, end - 1);
1124    }
1125
1126    // -- Insertion Sort --
1127
1128    protected static final void insertionsort(float[] a, int[] b, int p, int r) {
1129        for (int j = p + 1; j <= r; ++j) {
1130            float key = a[j];
1131            int val = b[j];
1132            int i = j - 1;
1133            while (i >= p && a[i] > key) {
1134                a[i + 1] = a[i];
1135                b[i + 1] = b[i];
1136                --i;
1137            }
1138            a[i + 1] = key;
1139            b[i + 1] = val;
1140        }
1141    }
1142
1143    // -- Mergesort --
1144
1145    protected static final void mergesort(float[] a, int[] b, int p, int r) {
1146        if (p >= r) {
1147            return;
1148        }
1149        if (r - p + 1 < SORT_THRESHOLD) {
1150            insertionsort(a, b, p, r);
1151        } else {
1152            int q = (p + r) / 2;
1153            mergesort(a, b, p, q);
1154            mergesort(a, b, q + 1, r);
1155            merge(a, b, p, q, r);
1156        }
1157    }
1158
1159    protected static final void merge(float[] a, int[] b, int p, int q, int r) {
1160        float[] t = new float[r - p + 1];
1161        int[] v = new int[r - p + 1];
1162        int i, p1 = p, p2 = q + 1;
1163        for (i = 0; p1 <= q && p2 <= r; ++i) {
1164            if (a[p1] < a[p2]) {
1165                v[i] = b[p1];
1166                t[i] = a[p1++];
1167            } else {
1168                v[i] = b[p2];
1169                t[i] = a[p2++];
1170            }
1171        }
1172        for (; p1 <= q; ++p1, ++i) {
1173            v[i] = b[p1];
1174            t[i] = a[p1];
1175        }
1176        for (; p2 <= r; ++p2, ++i) {
1177            v[i] = b[p2];
1178            t[i] = a[p2];
1179        }
1180        for (i = 0, p1 = p; i < t.length; i++, p1++) {
1181            b[p1] = v[i];
1182            a[p1] = t[i];
1183        }
1184    }
1185
1186    // -- Object / int sorting ------------------------------------------------
1187
1188    /**
1189     * Sort two arrays simultaneously, using the sort order of the values
1190     * in the first array to determine the sort order for both arrays.
1191     * @param a the array to sort by
1192     * @param b the array to re-arrange based on the sort order of the
1193     * first array.
1194     * @param cmp the comparator to use to compare key values
1195     */
1196    public static final void sort(Object [] a, int[] b, Comparator cmp) {
1197        mergesort(a, b, 0, a.length - 1, cmp);
1198    }
1199
1200    /**
1201     * Sort two arrays simultaneously, using the sort order of the values
1202     * in the first array to determine the sort order for both arrays.
1203     * @param a the array to sort by
1204     * @param b the array to re-arrange based on the sort order of the
1205     * first array.
1206     * @param length the length of the range to be sorted
1207     * @param cmp the comparator to use to compare key values
1208     */
1209    public static final void sort(Object [] a, int[] b, int length,
1210            Comparator cmp)
1211    {
1212        mergesort(a, b, 0, length - 1, cmp);
1213    }
1214
1215    /**
1216     * Sort two arrays simultaneously, using the sort order of the values
1217     * in the first array to determine the sort order for both arrays.
1218     * @param a the array to sort by
1219     * @param b the array to re-arrange based on the sort order of the
1220     * first array.
1221     * @param begin the start index of the range to sort
1222     * @param end the end index, exclusive, of the range to sort
1223     * @param cmp the comparator to use to compare key values
1224     */
1225    public static final void sort(Object [] a, int[] b, int begin, int end,
1226            Comparator cmp)
1227    {
1228        mergesort(a, b, begin, end - 1, cmp);
1229    }
1230
1231    // -- Insertion Sort --
1232
1233    protected static final void insertionsort(Object [] a, int[] b, int p, int r,
1234            Comparator cmp)
1235    {
1236        for (int j = p + 1; j <= r; ++j) {
1237            Object key = a[j];
1238            int val = b[j];
1239            int i = j - 1;
1240            while (i >= p && cmp.compare(a[i],key) > 0 ) {
1241                a[i + 1] = a[i];
1242                b[i + 1] = b[i];
1243                --i;
1244            }
1245            a[i + 1] = key;
1246            b[i + 1] = val;
1247        }
1248    }
1249
1250    // -- Mergesort --
1251
1252    protected static final void mergesort(Object [] a, int[] b, int p, int r,
1253            Comparator cmp)
1254    {
1255        if (p >= r) {
1256            return;
1257        }
1258        if (r - p + 1 < SORT_THRESHOLD) {
1259            insertionsort(a, b, p, r, cmp);
1260        } else {
1261            int q = (p + r) / 2;
1262            mergesort(a, b, p, q, cmp);
1263            mergesort(a, b, q + 1, r, cmp);
1264            merge(a, b, p, q, r, cmp);
1265        }
1266    }
1267
1268    protected static final void merge(Object [] a, int[] b, int p, int q, int r,
1269            Comparator cmp)
1270    {
1271        Object [] t = new Object [r - p + 1];
1272        int[] v = new int[r - p + 1];
1273        int i, p1 = p, p2 = q + 1;
1274        for (i = 0; p1 <= q && p2 <= r; ++i) {
1275            if ( cmp.compare(a[p1],a[p2]) < 0 ) {
1276                v[i] = b[p1];
1277                t[i] = a[p1++];
1278            } else {
1279                v[i] = b[p2];
1280                t[i] = a[p2++];
1281            }
1282        }
1283        for (; p1 <= q; ++p1, ++i) {
1284            v[i] = b[p1];
1285            t[i] = a[p1];
1286        }
1287        for (; p2 <= r; ++p2, ++i) {
1288            v[i] = b[p2];
1289            t[i] = a[p2];
1290        }
1291        for (i = 0, p1 = p; i < t.length; i++, p1++) {
1292            b[p1] = v[i];
1293            a[p1] = t[i];
1294        }
1295    }
1296    
1297    // ------------------------------------------------------------------------
1298 // Array File I/O
1299
1300    /**
1301     * Read in a text file as an array of integers. Uses the default java
1302     * StringTokenizer to segment the text file. Additionally, tokens beginning
1303     * with the '#' character are ignored.
1304     * @param filename the name of the file to read in
1305     * @return an array of integers parsed from the file
1306     */
1307    public static int[] getIntArray(String filename) {
1308        int[] array = null;
1309        try {
1310            BufferedReader br = new BufferedReader (new FileReader (filename));
1311            String line = br.readLine();
1312            StringTokenizer st = new StringTokenizer (line);
1313            int maxlen = st.countTokens();
1314            int len = 0;
1315            array = new int[maxlen];
1316            while ( st.hasMoreTokens() ) {
1317                String tok = st.nextToken();
1318                if ( tok.startsWith("#") ) // commented int
1319 continue;
1320                array[len++] = Integer.parseInt(tok);
1321            }
1322            if ( len != maxlen )
1323                array = ArrayLib.trim(array, len);
1324            return array;
1325        } catch ( Exception e ) {
1326            e.printStackTrace();
1327            return null;
1328        }
1329    }
1330
1331} // end of class ArrayLib
1332

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags