001 /* JAPI - (Yet anothr (hopefully) useful) Java API
002 *
003 * Copyright (C) 2004-2006 Christian Hujer
004 *
005 * This program is free software; you can redistribute it and/or
006 * modify it under the terms of the GNU General Public License as
007 * published by the Free Software Foundation; either version 2 of the
008 * License, or (at your option) any later version.
009 *
010 * This program is distributed in the hope that it will be useful, but
011 * WITHOUT ANY WARRANTY; without even the implied warranty of
012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013 * General Public License for more details.
014 *
015 * You should have received a copy of the GNU General Public License
016 * along with this program; if not, write to the Free Software
017 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
018 * 02111-1307, USA.
019 */
020
021 package net.sf.japi.util;
022
023 import java.lang.reflect.Array;
024 import java.util.ArrayList;
025 import java.util.Arrays;
026 import java.util.Collection;
027 import java.util.List;
028 import java.util.Comparator;
029
030 /**
031 * This class provides some additional utility methods you might miss in {@link Arrays}.
032 * It is named Arrays2 so you have no problems using both, this class and <code>java.util.Arrays</code> (no name conflict).
033 * @author <a href="mailto:Christian.Hujer@itcqis.com">Christian Hujer</a>
034 * @see Arrays
035 */
036 public final class Arrays2 {
037
038 /**
039 * Concatenate Arrays together.
040 * @param a Arrays to concatenate
041 * @return new Array containing all elements of all arrays
042 */
043 public static double[] concat(final double[]... a) {
044 int ns = 0;
045 for (final double[] anA : a) {
046 ns += anA.length;
047 }
048 final double[] na = new double[ns];
049 for (int i = 0, np = 0; i < a.length; np += a[i].length, i++) {
050 System.arraycopy(a[i], 0, na, np, a[i].length);
051 }
052 return na;
053 }
054
055 /**
056 * Concatenate Arrays together.
057 * @param a Arrays to concatenate
058 * @return new Array containing all elements of all arrays
059 */
060 public static float[] concat(final float[]... a) {
061 int ns = 0;
062 for (final float[] anA : a) {
063 ns += anA.length;
064 }
065 final float[] na = new float[ns];
066 for (int i = 0, np = 0; i < a.length; np += a[i].length, i++) {
067 System.arraycopy(a[i], 0, na, np, a[i].length);
068 }
069 return na;
070 }
071
072 /**
073 * Concatenate Arrays together.
074 * @param a Arrays to concatenate
075 * @return new Array containing all elements of all arrays
076 */
077 public static long[] concat(final long[]... a) {
078 int ns = 0;
079 for (final long[] anA : a) {
080 ns += anA.length;
081 }
082 final long[] na = new long[ns];
083 for (int i = 0, np = 0; i < a.length; np += a[i].length, i++) {
084 System.arraycopy(a[i], 0, na, np, a[i].length);
085 }
086 return na;
087 }
088
089 /**
090 * Concatenate Arrays together.
091 * @param a Arrays to concatenate
092 * @return new Array containing all elements of all arrays
093 */
094 public static int[] concat(final int[]... a) {
095 int ns = 0;
096 for (final int[] anA : a) {
097 ns += anA.length;
098 }
099 final int[] na = new int[ns];
100 for (int i = 0, np = 0; i < a.length; np += a[i].length, i++) {
101 System.arraycopy(a[i], 0, na, np, a[i].length);
102 }
103 return na;
104 }
105
106 /**
107 * Concatenate Arrays together.
108 * @param a Arrays to concatenate
109 * @return new Array containing all elements of all arrays
110 */
111 public static short[] concat(final short[]... a) {
112 int ns = 0;
113 for (final short[] anA : a) {
114 ns += anA.length;
115 }
116 final short[] na = new short[ns];
117 for (int i = 0, np = 0; i < a.length; np += a[i].length, i++) {
118 System.arraycopy(a[i], 0, na, np, a[i].length);
119 }
120 return na;
121 }
122
123 /**
124 * Concatenate Arrays together.
125 * @param a Arrays to concatenate
126 * @return new Array containing all elements of all arrays
127 */
128 public static char[] concat(final char[]... a) {
129 int ns = 0;
130 for (final char[] anA : a) {
131 ns += anA.length;
132 }
133 final char[] na = new char[ns];
134 for (int i = 0, np = 0; i < a.length; np += a[i].length, i++) {
135 System.arraycopy(a[i], 0, na, np, a[i].length);
136 }
137 return na;
138 }
139
140 /**
141 * Concatenate Arrays together.
142 * @param a Arrays to concatenate
143 * @return new Array containing all elements of all arrays
144 */
145 public static byte[] concat(final byte[]... a) {
146 int ns = 0;
147 for (final byte[] anA : a) {
148 ns += anA.length;
149 }
150 final byte[] na = new byte[ns];
151 for (int i = 0, np = 0; i < a.length; np += a[i].length, i++) {
152 System.arraycopy(a[i], 0, na, np, a[i].length);
153 }
154 return na;
155 }
156
157 /**
158 * Concatenate Arrays together.
159 * @param a Arrays to concatenate
160 * @return new Array containing all elements of all arrays
161 */
162 public static boolean[] concat(final boolean[]... a) {
163 int ns = 0;
164 for (final boolean[] anA : a) {
165 ns += anA.length;
166 }
167 final boolean[] na = new boolean[ns];
168 for (int i = 0, np = 0; i < a.length; np += a[i].length, i++) {
169 System.arraycopy(a[i], 0, na, np, a[i].length);
170 }
171 return na;
172 }
173
174 /**
175 * Concatenate Arrays together.
176 * @param a Arrays to concatenate
177 * @return new Array containing all elements of all arrays
178 */
179 public static <T> T[] concat(final T[]... a) {
180 int ns = 0;
181 for (final T[] anA : a) {
182 ns += anA.length;
183 }
184 final T[] na = (T[]) Array.newInstance(a[0].getClass().getComponentType(), ns);
185 for (int i = 0, np = 0; i < a.length; np += a[i].length, i++) {
186 System.arraycopy(a[i], 0, na, np, a[i].length);
187 }
188 return na;
189 }
190
191 /**
192 * Returns an array only containing those elements accepted by the given filter.
193 * The original array remains unmodified.
194 * @param a Elements to filter
195 * @param filter Filter to use for <var>a</var>
196 * @return array containing only those elements from <var>a</var> accepted by <var>filter</var>
197 * @see Collections2#filter(Collection,Filter)
198 */
199 public static <T> T[] filter(final Filter<T> filter, final T... a) {
200 //Class<?> ct = a.getClass().getComponentType();
201 //T[] t = (T[]) Array.newInstance(ct, 0);
202 //List<T> tl = Arrays.asList(a);
203 //List<T> tf = Collections2.filter(tl, filter);
204 //T[] nt = tf.toArray(t);
205 //return nt;
206 //return Collections2.filter(Arrays.asList(a), filter).toArray((T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), 0));
207 final List<T> tl = new ArrayList<T>();
208 for (final T t : a) {
209 if (filter.accept(t)) {
210 tl.add(t);
211 }
212 }
213 return tl.toArray((T[]) Array.newInstance(a.getClass().getComponentType(), 0));
214 } // eventually add filters for primitive types and provide correspondig methods
215
216 /**
217 * Count elements in an array that are accepted by the given filter.
218 * @param a Elements to count in
219 * @param filter Filter to use for <var>a</var>
220 * @return number of elements in <var>a</var> accepted by <var>filter</var>
221 */
222 public static <T> int count(final Filter<T> filter, final T... a) {
223 int n = 0;
224 for (final T t : a) {
225 if (filter.accept(t)) {
226 n++;
227 }
228 }
229 return n;
230 } // eventually add filters for primitive types and provide corresponding methods
231
232 /** Searches the specified array of ints for the specified value using the binary search algorithm.
233 * The array <strong>must</strong> be sorted (as by the <tt>sort</tt> method, above) prior to making this call.
234 * If it is not sorted, the results are undefined (even a runtime exception might occur).
235 * If the array contains multiple elements with the specified value, there is no guarantee which one will be found.
236 * @param a the array to be searched.
237 * @param key the value to be searched for.
238 * @param low lower border (must be <code>>= 0</code>)
239 * @param high upper border (must be <code>< a.length</code>)
240 * @return index of the search key, if it is contained in the list;
241 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
242 * <i>insertion point</i> is defined as the point at which the
243 * key would be inserted into the list: the index of the first
244 * element greater than the key, or <tt>list.size()</tt>, if all
245 * elements in the list are less than the specified key. Note
246 * that this guarantees that the return value will be >= 0 if
247 * and only if the key is found.
248 * @throws ArrayIndexOutOfBoundsException if <code>low < 0</code> or <code>high >= a.length</code>
249 * @see Arrays#binarySearch(int[],int)
250 * @see Arrays#sort(int[])
251 */
252 public static int binarySearch(final int[] a, final int key, int low, int high) {
253 while (low <= high) {
254 final int mid = low + high >> 1;
255 final int midVal = a[mid];
256 if (midVal < key) {
257 low = mid + 1;
258 } else if (midVal > key) {
259 high = mid - 1;
260 } else {
261 return mid; // key found
262 }
263 }
264 return -(low + 1); // key not found.
265 }
266
267 /** Perform a linear search on an array of booleans.
268 * @param z boolean to find in <var>data</var>
269 * @param data array of booleans to perform linear search on
270 * @return index of <var>n</var> in <var>data</var> or -1 if not found
271 */
272 public static int linearSearch(final boolean z, final boolean[] data) {
273 return linearSearch(z, 0, data.length, data);
274 }
275
276 /** Perform a linear search on an array of chars.
277 * @param c char to find in <var>data</var>
278 * @param data array of chars to perform linear search on
279 * @return index of <var>n</var> in <var>data</var> or -1 if not found
280 */
281 public static int linearSearch(final char c, final char[] data) {
282 return linearSearch(c, 0, data.length, data);
283 }
284
285 /** Perform a linear search on an array of doubles.
286 * @param d double to find in <var>data</var>
287 * @param data array of doubles to perform linear search on
288 * @return index of <var>n</var> in <var>data</var> or -1 if not found
289 */
290 public static int linearSearch(final double d, final double[] data) {
291 return linearSearch(d, 0, data.length, data);
292 }
293
294 /** Perform a linear search on an array of floats.
295 * @param f float to find in <var>data</var>
296 * @param data array of floats to perform linear search on
297 * @return index of <var>n</var> in <var>data</var> or -1 if not found
298 */
299 public static int linearSearch(final float f, final float[] data) {
300 return linearSearch(f, 0, data.length, data);
301 }
302
303 /** Perform a linear search on an array of longs.
304 * @param l long to find in <var>data</var>
305 * @param data array of longs to perform linear search on
306 * @return index of <var>n</var> in <var>data</var> or -1 if not found
307 */
308 public static int linearSearch(final long l, final long[] data) {
309 return linearSearch(l, 0, data.length, data);
310 }
311
312 /** Perform a linear search on an array of ints.
313 * @param n int to find in <var>data</var>
314 * @param data array of ints to perform linear search on
315 * @return index of <var>n</var> in <var>data</var> or -1 if not found
316 */
317 public static int linearSearch(final int n, final int[] data) {
318 return linearSearch(n, 0, data.length, data);
319 }
320
321 /** Perform a linear search on an array of shorts.
322 * @param s short to find in <var>data</var>
323 * @param data array of shorts to perform linear search on
324 * @return index of <var>n</var> in <var>data</var> or -1 if not found
325 */
326 public static int linearSearch(final short s, final short[] data) {
327 return linearSearch(s, 0, data.length, data);
328 }
329
330 /** Perform a linear search on an array of bytes.
331 * @param b byte to find in <var>data</var>
332 * @param data array of bytes to perform linear search on
333 * @return index of <var>n</var> in <var>data</var> or -1 if not found
334 */
335 public static int linearSearch(final byte b, final byte[] data) {
336 return linearSearch(b, 0, data.length, data);
337 }
338
339 /** Perform a linear search on an array of booleans.
340 * @param z boolean to find in <var>data</var>
341 * @param start start index within <var>data</var>
342 * @param end end index within <var>data</var>
343 * @param data array of booleans to perform linear search on
344 * @return index of <var>n</var> in <var>data</var> or -1 if not found
345 * @throws ArrayIndexOutOfBoundsException in case <code><var>start</var> < 0</code> or <code><var>end</var> >= data.length</code>
346 */
347 public static int linearSearch(final boolean z, final int start, final int end, final boolean[] data) {
348 for (int i = start; i < end; i++) {
349 if (data[i] == z) {
350 return i;
351 }
352 }
353 return -1;
354 }
355
356 /** Perform a linear search on an array of chars.
357 * @param c char to find in <var>data</var>
358 * @param start start index within <var>data</var>
359 * @param end end index within <var>data</var>
360 * @param data array of chars to perform linear search on
361 * @return index of <var>n</var> in <var>data</var> or -1 if not found
362 * @throws ArrayIndexOutOfBoundsException in case <code><var>start</var> < 0</code> or <code><var>end</var> >= data.length</code>
363 */
364 public static int linearSearch(final char c, final int start, final int end, final char[] data) {
365 for (int i = start; i < end; i++) {
366 if (data[i] == c) {
367 return i;
368 }
369 }
370 return -1;
371 }
372
373 /** Perform a linear search on an array of doubles.
374 * @param d double to find in <var>data</var>
375 * @param start start index within <var>data</var>
376 * @param end end index within <var>data</var>
377 * @param data array of doubles to perform linear search on
378 * @return index of <var>n</var> in <var>data</var> or -1 if not found
379 * @throws ArrayIndexOutOfBoundsException in case <code><var>start</var> < 0</code> or <code><var>end</var> >= data.length</code>
380 */
381 public static int linearSearch(final double d, final int start, final int end, final double[] data) {
382 for (int i = start; i < end; i++) {
383 if (data[i] == d) {
384 return i;
385 }
386 }
387 return -1;
388 }
389
390 /** Perform a linear search on an array of floats.
391 * @param f float to find in <var>data</var>
392 * @param start start index within <var>data</var>
393 * @param end end index within <var>data</var>
394 * @param data array of floats to perform linear search on
395 * @return index of <var>n</var> in <var>data</var> or -1 if not found
396 * @throws ArrayIndexOutOfBoundsException in case <code><var>start</var> < 0</code> or <code><var>end</var> >= data.length</code>
397 */
398 public static int linearSearch(final float f, final int start, final int end, final float[] data) {
399 for (int i = start; i < end; i++) {
400 if (data[i] == f) {
401 return i;
402 }
403 }
404 return -1;
405 }
406
407 /** Perform a linear search on an array of longs.
408 * @param l long to find in <var>data</var>
409 * @param start start index within <var>data</var>
410 * @param end end index within <var>data</var>
411 * @param data array of longs to perform linear search on
412 * @return index of <var>n</var> in <var>data</var> or -1 if not found
413 * @throws ArrayIndexOutOfBoundsException in case <code><var>start</var> < 0</code> or <code><var>end</var> >= data.length</code>
414 */
415 public static int linearSearch(final long l, final int start, final int end, final long[] data) {
416 for (int i = start; i < end; i++) {
417 if (data[i] == l) {
418 return i;
419 }
420 }
421 return -1;
422 }
423
424 /** Perform a linear search on an array of ints.
425 * @param n int to find in <var>data</var>
426 * @param start start index within <var>data</var>
427 * @param end end index within <var>data</var>
428 * @param data array of ints to perform linear search on
429 * @return index of <var>n</var> in <var>data</var> or -1 if not found
430 * @throws ArrayIndexOutOfBoundsException in case <code><var>start</var> < 0</code> or <code><var>end</var> >= data.length</code>
431 */
432 public static int linearSearch(final int n, final int start, final int end, final int[] data) {
433 for (int i = start; i < end; i++) {
434 if (data[i] == n) {
435 return i;
436 }
437 }
438 return -1;
439 }
440
441 /** Perform a linear search on an array of shorts.
442 * @param s short to find in <var>data</var>
443 * @param start start index within <var>data</var>
444 * @param end end index within <var>data</var>
445 * @param data array of shorts to perform linear search on
446 * @return index of <var>n</var> in <var>data</var> or -1 if not found
447 * @throws ArrayIndexOutOfBoundsException in case <code><var>start</var> < 0</code> or <code><var>end</var> >= data.length</code>
448 */
449 public static int linearSearch(final short s, final int start, final int end, final short[] data) {
450 for (int i = start; i < end; i++) {
451 if (data[i] == s) {
452 return i;
453 }
454 }
455 return -1;
456 }
457
458 /** Perform a linear search on an array of bytes.
459 * @param b byte to find in <var>data</var>
460 * @param start start index within <var>data</var>
461 * @param end end index within <var>data</var>
462 * @param data array of bytes to perform linear search on
463 * @return index of <var>n</var> in <var>data</var> or -1 if not found
464 * @throws ArrayIndexOutOfBoundsException in case <code><var>start</var> < 0</code> or <code><var>end</var> >= data.length</code>
465 */
466 public static int linearSearch(final byte b, final int start, final int end, final byte[] data) {
467 for (int i = start; i < end; i++) {
468 if (data[i] == b) {
469 return i;
470 }
471 }
472 return -1;
473 }
474
475 /** Perform a linear search on an array of Objects.
476 * @param o Object to find in <var>data</var>
477 * @param data array of Objects to perform linear search on
478 * @return index of <var>n</var> in <var>data</var> or -1 if not found
479 */
480 public static int linearIdentitySearch(final Object o, final Object[] data) {
481 return linearIdentitySearch(o, 0, data.length, data);
482 }
483
484 /** Perform a linear search on an array of Objects.
485 * @param o Object to find in <var>data</var>
486 * @param start start index within <var>data</var>
487 * @param end end index within <var>data</var>
488 * @param data array of Objects to perform linear search on
489 * @return index of <var>n</var> in <var>data</var> or -1 if not found
490 * @throws ArrayIndexOutOfBoundsException in case <code><var>start</var> < 0</code> or <code><var>end</var> >= data.length</code>
491 */
492 public static int linearIdentitySearch(final Object o, final int start, final int end, final Object[] data) {
493 for (int i = start; i < end; i++) {
494 if (data[i] == o) {
495 return i;
496 }
497 }
498 return -1;
499 }
500
501 /** Perform a linear search on an array of Objects.
502 * @param o Object to find in <var>data</var>
503 * @param data array of Objects to perform linear search on
504 * @return index of <var>n</var> in <var>data</var> or -1 if not found
505 */
506 public static int linearEqualitySearch(final Object o, final Object[] data) {
507 return linearEqualitySearch(o, 0, data.length, data);
508 }
509
510 /** Perform a linear search on an array of Objects.
511 * @param o Object to find in <var>data</var>
512 * @param start start index within <var>data</var>
513 * @param end end index within <var>data</var>
514 * @param data array of Objects to perform linear search on
515 * @return index of <var>n</var> in <var>data</var> or -1 if not found
516 * @throws ArrayIndexOutOfBoundsException in case <code><var>start</var> < 0</code> or <code><var>end</var> >= data.length</code>
517 */
518 public static int linearEqualitySearch(final Object o, final int start, final int end, final Object[] data) {
519 for (int i = start; i < end; i++) {
520 if (o == null && data[i] == null || data[i].equals(o)) {
521 return i;
522 }
523 }
524 return -1;
525 }
526
527 /** Perform a linear search on an array of Objects.
528 * @param o Object to find in <var>data</var>
529 * @param data array of Objects to perform linear search on
530 * @return index of <var>n</var> in <var>data</var> or -1 if not found
531 */
532 public static <T> int linearComparisonSearch(final T o, final T[] data, final Comparator<? super T> comp) {
533 return linearComparisonSearch(o, 0, data.length, data, comp);
534 }
535
536 /** Perform a linear search on an array of Objects.
537 * @param o Object to find in <var>data</var>
538 * @param start start index within <var>data</var>
539 * @param end end index within <var>data</var>
540 * @param data array of Objects to perform linear search on
541 * @return index of <var>n</var> in <var>data</var> or -1 if not found
542 * @throws ArrayIndexOutOfBoundsException in case <code><var>start</var> < 0</code> or <code><var>end</var> >= data.length</code>
543 */
544 public static <T> int linearComparisonSearch(final T o, final int start, final int end, final T[] data, final Comparator<? super T> comp) {
545 for (int i = start; i < end; i++) {
546 if (comp.compare(o, data[i]) == 0) {
547 return i;
548 }
549 }
550 return -1;
551 }
552
553 /** Private constructor - no instances needed. */
554 private Arrays2() {
555 }
556
557 /* Planned methods for future versions:
558 * - shuffle for all types of arrays
559 * - shuffle for all types of arrays with ranges
560 * - shuffle for all types of arrays with specified random
561 * - shuffle for all types of arrays with specified random with ranges
562 * - frequency for all types of arrays (unsorted)
563 * - frequency for all types of arrays (unsorted) with ranges
564 * - frequency for sorted arrays
565 * - min for all types of arrays (unsorted; for sorted use a[0])
566 * - min for all types of arrays (unsorted; for sorted use a[0]) with ranges
567 * - avg for numeric types of arrays (unsorted; primitives, Number, Character, Color, Date, Calendar)
568 * - avg for numeric types of arrays (unsorted; primitives, Number, Character, Color, Date, Calendar) with ranges
569 * - max for all types of arrays (unsorted; for sorted use a[a.length - 1])
570 * - max for all types of arrays (unsorted; for sorted use a[a.length - 1]) with ranges
571 * - sum for numeric types of arrays (unsorted; primitives, Number, Character, Color, Date, Calendar)
572 * - sum for numeric types of arrays (unsorted; primitives, Number, Character, Color, Date, Calendar) with ranges
573 * - med (median) for numeric types of arrays (unsorted; primitives, Number, Character, Color, Date, Calendar)
574 * - med (median) for numeric types of arrays (unsorted; primitives, Number, Character, Color, Date, Calendar) with ranges
575 * - product for numeric types of arrays (unsorted; primitives, Number, Character, Color, Date, Calendar)
576 * - product for numeric types of arrays (unsorted; primitives, Number, Character, Color, Date, Calendar) with ranges
577 * - binarySearch for all types of arrays (sorted) with ranges with Comparators
578 * - binarySearch for all types of arrays (sorted) with ranges without Comparators
579 * - equals for all types of arrays with ranges
580 * - hashCode for all types of arrays with ranges
581 * - toString for all types of arrays with ranges
582 * - asList for all types of arrays with ranges
583 * - replaceAll for all types of arrays
584 * - replaceAll for all types of arrays with ranges
585 * - replaceFirst for all types of arrays
586 * - replaceFirst for all types of arrays with ranges
587 * - replaceLast for all types of arrays
588 * - replaceLast for all types of arrays with ranges
589 * - subarray (create a new array as part of an old array) for all types of arrays with ranges
590 * - isSorted for all types of arrays with and without Comparators
591 * - reverse for all types of arrays
592 * - create an array by repeating an element
593 *
594 * Eventually provide native implementation of some methods for performance reasons.
595 */
596
597 } // class Arrays2