1/*
2 * ProGuard -- shrinking, optimization, obfuscation, and preverification
3 *             of Java bytecode.
4 *
5 * Copyright (c) 2002-2014 Eric Lafortune (eric@graphics.cornell.edu)
6 *
7 * This program is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License as published by the Free
9 * Software Foundation; either version 2 of the License, or (at your option)
10 * any later version.
11 *
12 * This program is distributed in the hope that it will be useful, but WITHOUT
13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
15 * more details.
16 *
17 * You should have received a copy of the GNU General Public License along
18 * with this program; if not, write to the Free Software Foundation, Inc.,
19 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 */
21package proguard.util;
22
23import java.lang.reflect.Array;
24import java.util.Arrays;
25
26/**
27 * This class contains utility methods operating on arrays.
28 */
29public class ArrayUtil
30{
31    /**
32     * Returns whether the elements of the two given arrays are the same.
33     * @param array1 the first array.
34     * @param array2 the second array.
35     * @param size   the size of the arrays to be checked.
36     * @return whether the elements are the same.
37     */
38    public static boolean equal(byte[] array1, byte[] array2, int size)
39    {
40        for (int index = 0; index < size; index++)
41        {
42            if (array1[index] != array2[index])
43            {
44                return false;
45            }
46        }
47
48        return true;
49    }
50
51
52    /**
53     * Returns whether the elements of the two given arrays are the same.
54     * @param array1 the first array.
55     * @param array2 the second array.
56     * @param size   the size of the arrays to be checked.
57     * @return whether the elements are the same.
58     */
59    public static boolean equal(short[] array1, short[] array2, int size)
60    {
61        for (int index = 0; index < size; index++)
62        {
63            if (array1[index] != array2[index])
64            {
65                return false;
66            }
67        }
68
69        return true;
70    }
71
72
73    /**
74     * Returns whether the elements of the two given arrays are the same.
75     * @param array1 the first array.
76     * @param array2 the second array.
77     * @param size   the size of the arrays to be checked.
78     * @return whether the elements are the same.
79     */
80    public static boolean equal(int[] array1, int[] array2, int size)
81    {
82        for (int index = 0; index < size; index++)
83        {
84            if (array1[index] != array2[index])
85            {
86                return false;
87            }
88        }
89
90        return true;
91    }
92
93
94    /**
95     * Returns whether the elements of the two given arrays are the same.
96     * @param array1 the first array.
97     * @param array2 the second array.
98     * @param size   the size of the arrays to be checked.
99     * @return whether the elements are the same.
100     */
101    public static boolean equal(Object[] array1, Object[] array2, int size)
102    {
103        for (int index = 0; index < size; index++)
104        {
105            if (!array1[index].equals(array2[index]))
106            {
107                return false;
108            }
109        }
110
111        return true;
112    }
113
114
115    /**
116     * Returns whether the elements of the two given arrays are the same, or
117     * both arrays are null.
118     * @param array1 the first array.
119     * @param array2 the second array.
120     * @return whether the elements are the same.
121     */
122    public static boolean equalOrNull(Object[] array1, Object[] array2)
123    {
124        return array1 == null ? array2 == null :
125            equalOrNull(array1, array2, array1.length);
126    }
127
128
129    /**
130     * Returns whether the elements of the two given arrays are the same, or
131     * both arrays are null.
132     * @param array1 the first array.
133     * @param array2 the second array.
134     * @param size   the size of the arrays to be checked.
135     * @return whether the elements are the same.
136     */
137    public static boolean equalOrNull(Object[] array1, Object[] array2, int size)
138    {
139        return array1 == null ? array2 == null :
140            array2 != null &&
141            equal(array1, array2, size);
142    }
143
144
145    /**
146     * Returns a hash code for the elements of the given array.
147     * @param array the array.
148     * @param size  the size of the array to be taken into account.
149     * @return a hash code.
150     */
151    public static int hashCode(byte[] array, int size)
152    {
153        int hashCode = 0;
154
155        for (int index = 0; index < size; index++)
156        {
157            hashCode ^= array[index];
158        }
159
160        return hashCode;
161    }
162
163
164    /**
165     * Returns a hash code for the elements of the given array.
166     * @param array the array.
167     * @param size  the size of the array to be taken into account.
168     * @return a hash code.
169     */
170    public static int hashCode(short[] array, int size)
171    {
172        int hashCode = 0;
173
174        for (int index = 0; index < size; index++)
175        {
176            hashCode ^= array[index];
177        }
178
179        return hashCode;
180    }
181
182
183    /**
184     * Returns a hash code for the elements of the given array.
185     * @param array the array.
186     * @param size  the size of the array to be taken into account.
187     * @return a hash code.
188     */
189    public static int hashCode(int[] array, int size)
190    {
191        int hashCode = 0;
192
193        for (int index = 0; index < size; index++)
194        {
195            hashCode ^= array[index];
196        }
197
198        return hashCode;
199    }
200
201
202    /**
203     * Returns a hash code for the elements of the given array.
204     * @param array the array.
205     * @param size  the size of the array to be taken into account.
206     * @return a hash code.
207     */
208    public static int hashCode(Object[] array, int size)
209    {
210        int hashCode = 0;
211
212        for (int index = 0; index < size; index++)
213        {
214            hashCode ^= array[index].hashCode();
215        }
216
217        return hashCode;
218    }
219
220
221    /**
222     * Returns a hash code for the elements of the given array, or 0 if it is
223     * null.
224     * @param array the array.
225     * @return a hash code.
226     */
227    public static int hashCodeOrNull(Object[] array)
228    {
229        return array == null ? 0 : hashCode(array, array.length);
230    }
231
232
233    /**
234     * Returns a hash code for the elements of the given array, or 0 if it is
235     * null.
236     * @param array the array.
237     * @param size  the size of the array to be taken into account.
238     * @return a hash code.
239     */
240    public static int hashCodeOrNull(Object[] array, int size)
241    {
242        return array == null ? 0 : hashCode(array, size);
243    }
244
245
246    /**
247     * Compares the elements of the two given arrays.
248     * @param array1 the first array.
249     * @param size1  the size of the first array.
250     * @param array2 the second array.
251     * @param size2  the size of the second array.
252     * @return 0 if all elements are the same,
253     *          -1 if the first different element in the first array is smaller
254     *          than the corresponding element in the second array,
255     *          or 1 if it is larger.
256     */
257    public static int compare(byte[] array1, int size1,
258                              byte[] array2, int size2)
259    {
260        int minSize = Math.min(size1, size2);
261
262        for (int index = 0; index < minSize; index++)
263        {
264            if (array1[index] < array2[index])
265            {
266                return -1;
267            }
268            else if (array1[index] > array2[index])
269            {
270                return 1;
271            }
272        }
273
274        return size1 <  size2 ? -1 :
275               size1 == size2 ?  0 :
276                                 1;
277    }
278
279
280    /**
281     * Compares the elements of the two given arrays.
282     * @param array1 the first array.
283     * @param size1  the size of the first array.
284     * @param array2 the second array.
285     * @param size2  the size of the second array.
286     * @return 0 if all elements are the same,
287     *          -1 if the first different element in the first array is smaller
288     *          than the corresponding element in the second array,
289     *          or 1 if it is larger.
290     */
291    public static int compare(short[] array1, int size1,
292                              short[] array2, int size2)
293    {
294        int minSize = Math.min(size1, size2);
295
296        for (int index = 0; index < minSize; index++)
297        {
298            if (array1[index] < array2[index])
299            {
300                return -1;
301            }
302            else if (array1[index] > array2[index])
303            {
304                return 1;
305            }
306        }
307
308        return size1 <  size2 ? -1 :
309               size1 == size2 ?  0 :
310                                 1;
311    }
312
313
314    /**
315     * Compares the elements of the two given arrays.
316     * @param array1 the first array.
317     * @param size1  the size of the first array.
318     * @param array2 the second array.
319     * @param size2  the size of the second array.
320     * @return 0 if all elements are the same,
321     *          -1 if the first different element in the first array is smaller
322     *          than the corresponding element in the second array,
323     *          or 1 if it is larger.
324     */
325    public static int compare(int[] array1, int size1,
326                              int[] array2, int size2)
327    {
328        int minSize = Math.min(size1, size2);
329
330        for (int index = 0; index < minSize; index++)
331        {
332            if (array1[index] < array2[index])
333            {
334                return -1;
335            }
336            else if (array1[index] > array2[index])
337            {
338                return 1;
339            }
340        }
341
342        return size1 <  size2 ? -1 :
343               size1 == size2 ?  0 :
344                                 1;
345    }
346
347
348    /**
349     * Compares the elements of the two given arrays.
350     * @param array1 the first array.
351     * @param size1  the size of the first array.
352     * @param array2 the second array.
353     * @param size2  the size of the second array.
354     * @return 0 if all elements are the same,
355     *          -1 if the first different element in the first array is smaller
356     *          than the corresponding element in the second array,
357     *          or 1 if it is larger.
358     */
359    public static int compare(Comparable[] array1, int size1,
360                              Comparable[] array2, int size2)
361    {
362        int minSize = Math.min(size1, size2);
363
364        for (int index = 0; index < minSize; index++)
365        {
366            int comparison = ObjectUtil.compare(array1[index], array2[index]);
367            if (comparison != 0)
368            {
369                return comparison;
370            }
371        }
372
373        return size1 <  size2 ? -1 :
374               size1 == size2 ?  0 :
375                                 1;
376    }
377
378
379    /**
380     * Ensures the given array has a given size.
381     * @param array the array.
382     * @param size  the target size of the array.
383     * @return      the original array, or a copy if it had to be extended.
384     */
385    public static boolean[] extendArray(boolean[] array, int size)
386    {
387        // Reuse the existing array if possible.
388        if (array.length >= size)
389        {
390            return array;
391        }
392
393        // Otherwise create and initialize a new array.
394        boolean[] newArray = new boolean[size];
395
396        System.arraycopy(array, 0,
397                         newArray, 0,
398                         array.length);
399
400        return newArray;
401    }
402
403
404    /**
405     * Ensures the given array has a given size.
406     * @param array        the array.
407     * @param size         the target size of the array.
408     * @param initialValue the initial value of the elements.
409     * @return             the original array, or a copy if it had to be
410     *                     extended.
411     */
412    public static boolean[] ensureArraySize(boolean[] array,
413                                            int       size,
414                                            boolean   initialValue)
415    {
416        // Is the existing array large enough?
417        if (array.length >= size)
418        {
419            // Reinitialize the existing array.
420            Arrays.fill(array, 0, size, initialValue);
421        }
422        else
423        {
424            // Otherwise create and initialize a new array.
425            array = new boolean[size];
426
427            if (initialValue)
428            {
429                Arrays.fill(array, 0, size, initialValue);
430            }
431        }
432
433        return array;
434    }
435
436
437    /**
438     * Adds the given element to the given array.
439     * The array is extended if necessary.
440     * @param array   the array.
441     * @param size    the original size of the array.
442     * @param element the element to be added.
443     * @return        the original array, or a copy if it had to be extended.
444     */
445    public static byte[] add(byte[] array, int size, byte element)
446    {
447        array = extendArray(array, size + 1);
448
449        array[size] = element;
450
451        return array;
452    }
453
454
455    /**
456     * Inserts the given element in the given array.
457     * The array is extended if necessary.
458     * @param array   the array.
459     * @param size    the original size of the array.
460     * @param index   the index at which the element is to be added.
461     * @param element the element to be added.
462     * @return        the original array, or a copy if it had to be extended.
463     */
464    public static byte[] insert(byte[] array, int size, int index, byte element)
465    {
466        array = extendArray(array, size + 1);
467
468        // Move the last part.
469        System.arraycopy(array, index,
470                         array, index + 1,
471                         size - index);
472
473        array[index] = element;
474
475        return array;
476    }
477
478
479    /**
480     * Removes the specified element from the given array.
481     * @param array the array.
482     * @param size  the original size of the array.
483     * @param index the index of the element to be removed.
484     */
485    public static void remove(byte[] array, int size, int index)
486    {
487        System.arraycopy(array, index + 1,
488                         array, index,
489                         array.length - index - 1);
490
491        array[size - 1] = 0;
492    }
493
494
495    /**
496     * Ensures the given array has a given size.
497     * @param array the array.
498     * @param size  the target size of the array.
499     * @return      the original array, or a copy if it had to be extended.
500     */
501    public static byte[] extendArray(byte[] array, int size)
502    {
503        // Reuse the existing array if possible.
504        if (array.length >= size)
505        {
506            return array;
507        }
508
509        // Otherwise create and initialize a new array.
510        byte[] newArray = new byte[size];
511
512        System.arraycopy(array, 0,
513                         newArray, 0,
514                         array.length);
515
516        return newArray;
517    }
518
519
520    /**
521     * Ensures the given array has a given size.
522     * @param array        the array.
523     * @param size         the target size of the array.
524     * @param initialValue the initial value of the elements.
525     * @return             the original array, or a copy if it had to be
526     *                     extended.
527     */
528    public static byte[] ensureArraySize(byte[] array,
529                                         int    size,
530                                         byte   initialValue)
531    {
532        // Is the existing array large enough?
533        if (array.length >= size)
534        {
535            // Reinitialize the existing array.
536            Arrays.fill(array, 0, size, initialValue);
537        }
538        else
539        {
540            // Otherwise create and initialize a new array.
541            array = new byte[size];
542
543            if (initialValue != 0)
544            {
545                Arrays.fill(array, 0, size, initialValue);
546            }
547        }
548
549        return array;
550    }
551
552
553    /**
554     * Adds the given element to the given array.
555     * The array is extended if necessary.
556     * @param array   the array.
557     * @param size    the original size of the array.
558     * @param element the element to be added.
559     * @return        the original array, or a copy if it had to be extended.
560     */
561    public static short[] add(short[] array, int size, short element)
562    {
563        array = extendArray(array, size + 1);
564
565        array[size] = element;
566
567        return array;
568    }
569
570
571    /**
572     * Inserts the given element in the given array.
573     * The array is extended if necessary.
574     * @param array   the array.
575     * @param size    the original size of the array.
576     * @param index   the index at which the element is to be added.
577     * @param element the element to be added.
578     * @return        the original array, or a copy if it had to be extended.
579     */
580    public static short[] insert(short[] array, int size, int index, short element)
581    {
582        array = extendArray(array, size + 1);
583
584        // Move the last part.
585        System.arraycopy(array, index,
586                         array, index + 1,
587                         size - index);
588
589        array[index] = element;
590
591        return array;
592    }
593
594
595    /**
596     * Removes the specified element from the given array.
597     * @param array the array.
598     * @param size  the original size of the array.
599     * @param index the index of the element to be removed.
600     */
601    public static void remove(short[] array, int size, int index)
602    {
603        System.arraycopy(array, index + 1,
604                         array, index,
605                         array.length - index - 1);
606
607        array[size - 1] = 0;
608    }
609
610
611    /**
612     * Ensures the given array has a given size.
613     * @param array the array.
614     * @param size  the target size of the array.
615     * @return      the original array, or a copy if it had to be extended.
616     */
617    public static short[] extendArray(short[] array, int size)
618    {
619        // Reuse the existing array if possible.
620        if (array.length >= size)
621        {
622            return array;
623        }
624
625        // Otherwise create and initialize a new array.
626        short[] newArray = new short[size];
627
628        System.arraycopy(array, 0,
629                         newArray, 0,
630                         array.length);
631
632        return newArray;
633    }
634
635
636    /**
637     * Ensures the given array has a given size.
638     * @param array        the array.
639     * @param size         the target size of the array.
640     * @param initialValue the initial value of the elements.
641     * @return             the original array, or a copy if it had to be
642     *                     extended.
643     */
644    public static short[] ensureArraySize(short[] array,
645                                          int     size,
646                                          short   initialValue)
647    {
648        // Is the existing array large enough?
649        if (array.length >= size)
650        {
651            // Reinitialize the existing array.
652            Arrays.fill(array, 0, size, initialValue);
653        }
654        else
655        {
656            // Otherwise create and initialize a new array.
657            array = new short[size];
658
659            if (initialValue != 0)
660            {
661                Arrays.fill(array, 0, size, initialValue);
662            }
663        }
664
665        return array;
666    }
667
668
669    /**
670     * Adds the given element to the given array.
671     * The array is extended if necessary.
672     * @param array   the array.
673     * @param size    the original size of the array.
674     * @param element the element to be added.
675     * @return        the original array, or a copy if it had to be extended.
676     */
677    public static int[] add(int[] array, int size, int element)
678    {
679        array = extendArray(array, size + 1);
680
681        array[size] = element;
682
683        return array;
684    }
685
686
687    /**
688     * Inserts the given element in the given array.
689     * The array is extended if necessary.
690     * @param array   the array.
691     * @param size    the original size of the array.
692     * @param index   the index at which the element is to be added.
693     * @param element the element to be added.
694     * @return        the original array, or a copy if it had to be extended.
695     */
696    public static int[] insert(int[] array, int size, int index, int element)
697    {
698        array = extendArray(array, size + 1);
699
700        // Move the last part.
701        System.arraycopy(array, index,
702                         array, index + 1,
703                         size - index);
704
705        array[index] = element;
706
707        return array;
708    }
709
710
711    /**
712     * Removes the specified element from the given array.
713     * @param array the array.
714     * @param size  the original size of the array.
715     * @param index the index of the element to be removed.
716     */
717    public static void remove(int[] array, int size, int index)
718    {
719        System.arraycopy(array, index + 1,
720                         array, index,
721                         array.length - index - 1);
722
723        array[size - 1] = 0;
724    }
725
726
727    /**
728     * Ensures the given array has a given size.
729     * @param array the array.
730     * @param size  the target size of the array.
731     * @return      the original array, or a copy if it had to be extended.
732     */
733    public static int[] extendArray(int[] array, int size)
734    {
735        // Reuse the existing array if possible.
736        if (array.length >= size)
737        {
738            return array;
739        }
740
741        // Otherwise create and initialize a new array.
742        int[] newArray = new int[size];
743
744        System.arraycopy(array, 0,
745                         newArray, 0,
746                         array.length);
747
748        return newArray;
749    }
750
751
752    /**
753     * Ensures the given array has a given size.
754     * @param array        the array.
755     * @param size         the target size of the array.
756     * @param initialValue the initial value of the elements.
757     * @return             the original array, or a copy if it had to be
758     *                     extended.
759     */
760    public static int[] ensureArraySize(int[] array,
761                                        int   size,
762                                        int   initialValue)
763    {
764        // Is the existing array large enough?
765        if (array.length >= size)
766        {
767            // Reinitialize the existing array.
768            Arrays.fill(array, 0, size, initialValue);
769        }
770        else
771        {
772            // Otherwise create and initialize a new array.
773            array = new int[size];
774
775            if (initialValue != 0)
776            {
777                Arrays.fill(array, 0, size, initialValue);
778            }
779        }
780
781        return array;
782    }
783
784
785    /**
786     * Adds the given element to the given array.
787     * The array is extended if necessary.
788     * @param array   the array.
789     * @param size    the original size of the array.
790     * @param element the element to be added.
791     * @return        the original array, or a copy if it had to be extended.
792     */
793    public static long[] add(long[] array, int size, long element)
794    {
795        array = extendArray(array, size + 1);
796
797        array[size] = element;
798
799        return array;
800    }
801
802
803    /**
804     * Inserts the given element in the given array.
805     * The array is extended if necessary.
806     * @param array   the array.
807     * @param size    the original size of the array.
808     * @param index   the index at which the element is to be added.
809     * @param element the element to be added.
810     * @return        the original array, or a copy if it had to be extended.
811     */
812    public static long[] insert(long[] array, int size, int index, long element)
813    {
814        array = extendArray(array, size + 1);
815
816        // Move the last part.
817        System.arraycopy(array, index,
818                         array, index + 1,
819                         size - index);
820
821        array[index] = element;
822
823        return array;
824    }
825
826
827    /**
828     * Removes the specified element from the given array.
829     * @param array the array.
830     * @param size  the original size of the array.
831     * @param index the index of the element to be removed.
832     */
833    public static void remove(long[] array, int size, int index)
834    {
835        System.arraycopy(array, index + 1,
836                         array, index,
837                         array.length - index - 1);
838
839        array[size - 1] = 0;
840    }
841
842
843    /**
844     * Ensures the given array has a given size.
845     * @param array the array.
846     * @param size  the target size of the array.
847     * @return      the original array, or a copy if it had to be extended.
848     */
849    public static long[] extendArray(long[] array, int size)
850    {
851        // Reuse the existing array if possible.
852        if (array.length >= size)
853        {
854            return array;
855        }
856
857        // Otherwise create and initialize a new array.
858        long[] newArray = new long[size];
859
860        System.arraycopy(array, 0,
861                         newArray, 0,
862                         array.length);
863
864        return newArray;
865    }
866
867
868    /**
869     * Ensures the given array has a given size.
870     * @param array        the array.
871     * @param size         the target size of the array.
872     * @param initialValue the initial value of the elements.
873     * @return             the original array, or a copy if it had to be
874     *                     extended.
875     */
876    public static long[] ensureArraySize(long[] array,
877                                         int    size,
878                                         long   initialValue)
879    {
880        // Is the existing array large enough?
881        if (array.length >= size)
882        {
883            // Reinitialize the existing array.
884            Arrays.fill(array, 0, size, initialValue);
885        }
886        else
887        {
888            // Otherwise create and initialize a new array.
889            array = new long[size];
890
891            if (initialValue != 0L)
892            {
893                Arrays.fill(array, 0, size, initialValue);
894            }
895        }
896
897        return array;
898    }
899
900
901    /**
902     * Adds the given element to the given array.
903     * The array is extended if necessary.
904     * @param array   the array.
905     * @param size    the original size of the array.
906     * @param element the element to be added.
907     * @return        the original array, or a copy if it had to be extended.
908     */
909    public static Object[] add(Object[] array, int size, Object element)
910    {
911        array = extendArray(array, size + 1);
912
913        array[size] = element;
914
915        return array;
916    }
917
918
919    /**
920     * Inserts the given element in the given array.
921     * The array is extended if necessary.
922     * @param array   the array.
923     * @param size    the original size of the array.
924     * @param index   the index at which the element is to be added.
925     * @param element the element to be added.
926     * @return        the original array, or a copy if it had to be extended.
927     */
928    public static Object[] insert(Object[] array, int size, int index, Object element)
929    {
930        array = extendArray(array, size + 1);
931
932        // Move the last part.
933        System.arraycopy(array, index,
934                         array, index + 1,
935                         size - index);
936
937        array[index] = element;
938
939        return array;
940    }
941
942
943    /**
944     * Removes the specified element from the given array.
945     * @param array the array.
946     * @param size  the original size of the array.
947     * @param index the index of the element to be removed.
948     */
949    public static void remove(Object[] array, int size, int index)
950    {
951        System.arraycopy(array, index + 1,
952                         array, index,
953                         array.length - index - 1);
954
955        array[size - 1] = null;
956    }
957
958
959    /**
960     * Ensures the given array has a given size.
961     * @param array the array.
962     * @param size  the target size of the array.
963     * @return      the original array, or a copy if it had to be extended.
964     */
965    public static Object[] extendArray(Object[] array, int size)
966    {
967        // Reuse the existing array if possible.
968        if (array.length >= size)
969        {
970            return array;
971        }
972
973        // Otherwise create and initialize a new array.
974        Object[] newArray = (Object[])Array.newInstance(array.getClass().getComponentType(), size);
975
976        System.arraycopy(array, 0,
977                         newArray, 0,
978                         array.length);
979
980        return newArray;
981    }
982
983
984    /**
985     * Ensures the given array has a given size.
986     * @param array        the array.
987     * @param size         the target size of the array.
988     * @param initialValue the initial value of the elements.
989     * @return             the original array, or a copy if it had to be
990     *                     extended.
991     */
992    public static Object[] ensureArraySize(Object[] array,
993                                           int      size,
994                                           Object   initialValue)
995    {
996        // Is the existing array large enough?
997        if (array.length >= size)
998        {
999            // Reinitialize the existing array.
1000            Arrays.fill(array, 0, size, initialValue);
1001        }
1002        else
1003        {
1004            // Otherwise create and initialize a new array.
1005            array = (Object[])Array.newInstance(array.getClass().getComponentType(), size);
1006
1007            if (initialValue != null)
1008            {
1009                Arrays.fill(array, 0, size, initialValue);
1010            }
1011        }
1012
1013        return array;
1014    }
1015}
1016