0001: /*
0002: * Copyright 2007 Google Inc.
0003: *
0004: * Licensed under the Apache License, Version 2.0 (the "License"); you may not
0005: * use this file except in compliance with the License. You may obtain a copy of
0006: * the License at
0007: *
0008: * http://www.apache.org/licenses/LICENSE-2.0
0009: *
0010: * Unless required by applicable law or agreed to in writing, software
0011: * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
0012: * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
0013: * License for the specific language governing permissions and limitations under
0014: * the License.
0015: */
0016:
0017: package java.util;
0018:
0019: import com.google.gwt.core.client.JavaScriptObject;
0020: import com.google.gwt.lang.Array;
0021:
0022: /**
0023: * Utility methods related to native arrays. <a
0024: * href="http://java.sun.com/j2se/1.5.0/docs/api/java/util/Arrays.html">[Sun
0025: * docs]</a>
0026: */
0027: public class Arrays {
0028:
0029: public static <T> List<T> asList(T... array) {
0030: List<T> accum = new ArrayList<T>();
0031: for (int i = 0; i < array.length; i++) {
0032: accum.add(array[i]);
0033: }
0034: return accum;
0035: }
0036:
0037: /**
0038: * Perform a binary search on a sorted byte array.
0039: *
0040: * @param sortedArray byte array to search
0041: * @param key value to search for
0042: * @return the index of an element with a matching value, or a negative number
0043: * which is the index of the next larger value (or just past the end
0044: * of the array if the searched value is larger than all elements in
0045: * the array) minus 1 (to ensure error returns are negative)
0046: */
0047: public static int binarySearch(final byte[] sortedArray,
0048: final byte key) {
0049: int low = 0;
0050: int high = sortedArray.length - 1;
0051:
0052: while (low <= high) {
0053: final int mid = low + ((high - low) / 2);
0054: final byte midVal = sortedArray[mid];
0055:
0056: if (midVal < key) {
0057: low = mid + 1;
0058: } else if (midVal > key) {
0059: high = mid - 1;
0060: } else {
0061: // key found
0062: return mid;
0063: }
0064: }
0065: // key not found.
0066: return -low - 1;
0067: }
0068:
0069: /**
0070: * Perform a binary search on a sorted char array.
0071: *
0072: * @param a char array to search
0073: * @param key value to search for
0074: * @return the index of an element with a matching value, or a negative number
0075: * which is the index of the next larger value (or just past the end
0076: * of the array if the searched value is larger than all elements in
0077: * the array) minus 1 (to ensure error returns are negative)
0078: */
0079: public static int binarySearch(final char[] a, final char key) {
0080: int low = 0;
0081: int high = a.length - 1;
0082:
0083: while (low <= high) {
0084: final int mid = low + ((high - low) / 2);
0085: final char midVal = a[mid];
0086:
0087: if (midVal < key) {
0088: low = mid + 1;
0089: } else if (midVal > key) {
0090: high = mid - 1;
0091: } else {
0092: // key found
0093: return mid;
0094: }
0095: }
0096: // key not found.
0097: return -low - 1;
0098: }
0099:
0100: /**
0101: * Perform a binary search on a sorted double array.
0102: *
0103: * @param sortedArray double array to search
0104: * @param key value to search for
0105: * @return the index of an element with a matching value, or a negative number
0106: * which is the index of the next larger value (or just past the end
0107: * of the array if the searched value is larger than all elements in
0108: * the array) minus 1 (to ensure error returns are negative)
0109: */
0110: public static int binarySearch(final double[] sortedArray,
0111: final double key) {
0112: int low = 0;
0113: int high = sortedArray.length - 1;
0114:
0115: while (low <= high) {
0116: final int mid = low + ((high - low) / 2);
0117: final double midVal = sortedArray[mid];
0118:
0119: if (midVal < key) {
0120: low = mid + 1;
0121: } else if (midVal > key) {
0122: high = mid - 1;
0123: } else {
0124: // key found
0125: return mid;
0126: }
0127: }
0128: // key not found.
0129: return -low - 1;
0130: }
0131:
0132: /**
0133: * Perform a binary search on a sorted float array.
0134: *
0135: * Note that some underlying JavaScript interpreters do not actually implement
0136: * floats (using double instead), so you may get slightly different behavior
0137: * regarding values that are very close (or equal) since conversion errors
0138: * to/from double may change the values slightly.
0139: *
0140: * @param sortedArray float array to search
0141: * @param key value to search for
0142: * @return the index of an element with a matching value, or a negative number
0143: * which is the index of the next larger value (or just past the end
0144: * of the array if the searched value is larger than all elements in
0145: * the array) minus 1 (to ensure error returns are negative)
0146: */
0147: public static int binarySearch(final float[] sortedArray,
0148: final float key) {
0149: int low = 0;
0150: int high = sortedArray.length - 1;
0151:
0152: while (low <= high) {
0153: final int mid = low + ((high - low) / 2);
0154: final float midVal = sortedArray[mid];
0155:
0156: if (midVal < key) {
0157: low = mid + 1;
0158: } else if (midVal > key) {
0159: high = mid - 1;
0160: } else {
0161: // key found
0162: return mid;
0163: }
0164: }
0165: // key not found.
0166: return -low - 1;
0167: }
0168:
0169: /**
0170: * Perform a binary search on a sorted int array.
0171: *
0172: * @param sortedArray int array to search
0173: * @param key value to search for
0174: * @return the index of an element with a matching value, or a negative number
0175: * which is the index of the next larger value (or just past the end
0176: * of the array if the searched value is larger than all elements in
0177: * the array) minus 1 (to ensure error returns are negative)
0178: */
0179: public static int binarySearch(final int[] sortedArray,
0180: final int key) {
0181: int low = 0;
0182: int high = sortedArray.length - 1;
0183:
0184: while (low <= high) {
0185: final int mid = low + ((high - low) / 2);
0186: final int midVal = sortedArray[mid];
0187:
0188: if (midVal < key) {
0189: low = mid + 1;
0190: } else if (midVal > key) {
0191: high = mid - 1;
0192: } else {
0193: // key found
0194: return mid;
0195: }
0196: }
0197: // key not found.
0198: return -low - 1;
0199: }
0200:
0201: /**
0202: * Perform a binary search on a sorted long array.
0203: *
0204: * Note that most underlying JavaScript interpreters do not actually implement
0205: * longs, so the values must be stored in doubles instead. This means that
0206: * certain legal values cannot be represented, and comparison of two unequal
0207: * long values may result in unexpected results if they are not also
0208: * representable as doubles.
0209: *
0210: * @param sortedArray long array to search
0211: * @param key value to search for
0212: * @return the index of an element with a matching value, or a negative number
0213: * which is the index of the next larger value (or just past the end
0214: * of the array if the searched value is larger than all elements in
0215: * the array) minus 1 (to ensure error returns are negative)
0216: */
0217: public static int binarySearch(final long[] sortedArray,
0218: final long key) {
0219: int low = 0;
0220: int high = sortedArray.length - 1;
0221:
0222: while (low <= high) {
0223: final int mid = low + ((high - low) / 2);
0224: final long midVal = sortedArray[mid];
0225:
0226: if (midVal < key) {
0227: low = mid + 1;
0228: } else if (midVal > key) {
0229: high = mid - 1;
0230: } else {
0231: // key found
0232: return mid;
0233: }
0234: }
0235: // key not found.
0236: return -low - 1;
0237: }
0238:
0239: /**
0240: * Perform a binary search on a sorted object array, using natural ordering.
0241: *
0242: * @param sortedArray object array to search
0243: * @param key value to search for
0244: * @return the index of an element with a matching value, or a negative number
0245: * which is the index of the next larger value (or just past the end
0246: * of the array if the searched value is larger than all elements in
0247: * the array) minus 1 (to ensure error returns are negative)
0248: * @throws ClassCastException if <code>key</code> is not comparable to
0249: * <code>sortedArray</code>'s elements.
0250: */
0251: public static int binarySearch(final Object[] sortedArray,
0252: final Object key) {
0253: return binarySearch(sortedArray, key, Comparators.natural());
0254: }
0255:
0256: /**
0257: * Perform a binary search on a sorted short array.
0258: *
0259: * @param sortedArray short array to search
0260: * @param key value to search for
0261: * @return the index of an element with a matching value, or a negative number
0262: * which is the index of the next larger value (or just past the end
0263: * of the array if the searched value is larger than all elements in
0264: * the array) minus 1 (to ensure error returns are negative)
0265: */
0266: public static int binarySearch(final short[] sortedArray,
0267: final short key) {
0268: int low = 0;
0269: int high = sortedArray.length - 1;
0270:
0271: while (low <= high) {
0272: final int mid = low + ((high - low) / 2);
0273: final short midVal = sortedArray[mid];
0274:
0275: if (midVal < key) {
0276: low = mid + 1;
0277: } else if (midVal > key) {
0278: high = mid - 1;
0279: } else {
0280: // key found
0281: return mid;
0282: }
0283: }
0284: // key not found.
0285: return -low - 1;
0286: }
0287:
0288: /**
0289: * Perform a binary search on a sorted object array, using a user-specified
0290: * comparison function.
0291: *
0292: * @param sortedArray object array to search
0293: * @param key value to search for
0294: * @param comparator comparision function, <code>null</code> indicates
0295: * <i>natural ordering</i> should be used.
0296: * @return the index of an element with a matching value, or a negative number
0297: * which is the index of the next larger value (or just past the end
0298: * of the array if the searched value is larger than all elements in
0299: * the array) minus 1 (to ensure error returns are negative)
0300: * @throws ClassCastException if <code>key</code> and
0301: * <code>sortedArray</code>'s elements cannot be compared by
0302: * <code>comparator</code>.
0303: */
0304: public static <T> int binarySearch(final T[] sortedArray,
0305: final T key, Comparator<? super T> comparator) {
0306: if (comparator == null) {
0307: comparator = Comparators.natural();
0308: }
0309: int low = 0;
0310: int high = sortedArray.length - 1;
0311:
0312: while (low <= high) {
0313: final int mid = low + ((high - low) / 2);
0314: final T midVal = sortedArray[mid];
0315: final int compareResult = comparator.compare(midVal, key);
0316:
0317: if (compareResult < 0) {
0318: low = mid + 1;
0319: } else if (compareResult > 0) {
0320: high = mid - 1;
0321: } else {
0322: // key found
0323: return mid;
0324: }
0325: }
0326: // key not found.
0327: return -low - 1;
0328: }
0329:
0330: public static boolean deepEquals(Object[] a1, Object[] a2) {
0331: if (a1 == a2) {
0332: return true;
0333: }
0334:
0335: if (a1 == null || a2 == null) {
0336: return false;
0337: }
0338:
0339: if (a1.length != a2.length) {
0340: return false;
0341: }
0342:
0343: for (int i = 0, n = a1.length; i < n; ++i) {
0344:
0345: Object obj1 = a1[i];
0346: Object obj2 = a2[i];
0347: if (obj1 == obj2) {
0348: continue;
0349: }
0350: if (obj1 == null || obj2 == null) {
0351: return false;
0352: }
0353: if (obj1.equals(obj2)) {
0354: continue;
0355: }
0356: String class1 = obj1.getClass().getName();
0357: String class2 = obj2.getClass().getName();
0358:
0359: // We have to test and see if these are two arrays of the same type,
0360: // then see what types of arrays they are and dispatch to the
0361: // appropriate equals
0362:
0363: if (!class1.startsWith("[") || !class1.equals(class2)) {
0364: return false;
0365: }
0366:
0367: if (obj1 instanceof Object[]) {
0368: if (!deepEquals((Object[]) obj1, (Object[]) obj2)) {
0369: return false;
0370: }
0371: } else if (obj1 instanceof boolean[]) {
0372: if (!equals((boolean[]) obj1, (boolean[]) obj2)) {
0373: return false;
0374: }
0375: } else if (obj1 instanceof byte[]) {
0376: if (!equals((byte[]) obj1, (byte[]) obj2)) {
0377: return false;
0378: }
0379: } else if (obj1 instanceof char[]) {
0380: if (!equals((char[]) obj1, (char[]) obj2)) {
0381: return false;
0382: }
0383: } else if (obj1 instanceof short[]) {
0384: if (!equals((short[]) obj1, (short[]) obj2)) {
0385: return false;
0386: }
0387: } else if (obj1 instanceof int[]) {
0388: if (!equals((int[]) obj1, (int[]) obj2)) {
0389: return false;
0390: }
0391: } else if (obj1 instanceof long[]) {
0392: if (!equals((long[]) obj1, (long[]) obj2)) {
0393: return false;
0394: }
0395: } else if (obj1 instanceof float[]) {
0396: if (!equals((float[]) obj1, (float[]) obj2)) {
0397: return false;
0398: }
0399: } else if (obj1 instanceof double[]) {
0400: if (!equals((double[]) obj1, (double[]) obj2)) {
0401: return false;
0402: }
0403: }
0404: }
0405:
0406: return true;
0407: }
0408:
0409: public static int deepHashCode(Object[] a) {
0410: if (a == null) {
0411: return 0;
0412: }
0413:
0414: int hashCode = 1;
0415:
0416: for (int i = 0, n = a.length; i < n; ++i) {
0417: Object obj = a[i];
0418: int hash;
0419:
0420: if (obj instanceof Object[]) {
0421: hash = deepHashCode((Object[]) obj);
0422: } else if (obj instanceof boolean[]) {
0423: hash = hashCode((boolean[]) obj);
0424: } else if (obj instanceof byte[]) {
0425: hash = hashCode((byte[]) obj);
0426: } else if (obj instanceof char[]) {
0427: hash = hashCode((char[]) obj);
0428: } else if (obj instanceof short[]) {
0429: hash = hashCode((short[]) obj);
0430: } else if (obj instanceof int[]) {
0431: hash = hashCode((int[]) obj);
0432: } else if (obj instanceof long[]) {
0433: hash = hashCode((long[]) obj);
0434: } else if (obj instanceof float[]) {
0435: hash = hashCode((float[]) obj);
0436: } else if (obj instanceof double[]) {
0437: hash = hashCode((double[]) obj);
0438: } else {
0439: hash = obj.hashCode();
0440: }
0441:
0442: // nasty trick related to JS and lack of integer rollover
0443: hashCode = (31 * hashCode + hash) | 0;
0444: }
0445:
0446: return hashCode;
0447: }
0448:
0449: public static String deepToString(Object[] a) {
0450: return deepToString(a, new HashSet<Object[]>());
0451: }
0452:
0453: public static boolean equals(boolean[] array1, boolean[] array2) {
0454: if (array1 == array2) {
0455: return true;
0456: }
0457:
0458: if (array1 == null || array2 == null) {
0459: return false;
0460: }
0461:
0462: if (array1.length != array2.length) {
0463: return false;
0464: }
0465:
0466: for (int i = 0; i < array1.length; ++i) {
0467: if (array1[i] != array2[i]) {
0468: return false;
0469: }
0470: }
0471:
0472: return true;
0473: }
0474:
0475: public static boolean equals(byte[] array1, byte[] array2) {
0476: if (array1 == array2) {
0477: return true;
0478: }
0479:
0480: if (array1 == null || array2 == null) {
0481: return false;
0482: }
0483:
0484: if (array1.length != array2.length) {
0485: return false;
0486: }
0487:
0488: for (int i = 0; i < array1.length; ++i) {
0489: if (array1[i] != array2[i]) {
0490: return false;
0491: }
0492: }
0493:
0494: return true;
0495: }
0496:
0497: public static boolean equals(char[] array1, char[] array2) {
0498: if (array1 == array2) {
0499: return true;
0500: }
0501:
0502: if (array1 == null || array2 == null) {
0503: return false;
0504: }
0505:
0506: if (array1.length != array2.length) {
0507: return false;
0508: }
0509:
0510: for (int i = 0; i < array1.length; ++i) {
0511: if (array1[i] != array2[i]) {
0512: return false;
0513: }
0514: }
0515:
0516: return true;
0517: }
0518:
0519: public static boolean equals(double[] array1, double[] array2) {
0520: if (array1 == array2) {
0521: return true;
0522: }
0523:
0524: if (array1 == null || array2 == null) {
0525: return false;
0526: }
0527:
0528: if (array1.length != array2.length) {
0529: return false;
0530: }
0531:
0532: for (int i = 0; i < array1.length; ++i) {
0533: if (array1[i] != array2[i]) {
0534: return false;
0535: }
0536: }
0537:
0538: return true;
0539: }
0540:
0541: public static boolean equals(float[] array1, float[] array2) {
0542: if (array1 == array2) {
0543: return true;
0544: }
0545:
0546: if (array1 == null || array2 == null) {
0547: return false;
0548: }
0549:
0550: if (array1.length != array2.length) {
0551: return false;
0552: }
0553:
0554: for (int i = 0; i < array1.length; ++i) {
0555: if (array1[i] != array2[i]) {
0556: return false;
0557: }
0558: }
0559:
0560: return true;
0561: }
0562:
0563: public static boolean equals(int[] array1, int[] array2) {
0564: if (array1 == array2) {
0565: return true;
0566: }
0567:
0568: if (array1 == null || array2 == null) {
0569: return false;
0570: }
0571:
0572: if (array1.length != array2.length) {
0573: return false;
0574: }
0575:
0576: for (int i = 0; i < array1.length; ++i) {
0577: if (array1[i] != array2[i]) {
0578: return false;
0579: }
0580: }
0581:
0582: return true;
0583: }
0584:
0585: public static boolean equals(long[] array1, long[] array2) {
0586: if (array1 == array2) {
0587: return true;
0588: }
0589:
0590: if (array1 == null || array2 == null) {
0591: return false;
0592: }
0593:
0594: if (array1.length != array2.length) {
0595: return false;
0596: }
0597:
0598: for (int i = 0; i < array1.length; ++i) {
0599: if (array1[i] != array2[i]) {
0600: return false;
0601: }
0602: }
0603:
0604: return true;
0605: }
0606:
0607: public static boolean equals(Object[] array1, Object[] array2) {
0608: if (array1 == array2) {
0609: return true;
0610: }
0611:
0612: if (array1 == null || array2 == null) {
0613: return false;
0614: }
0615:
0616: if (array1.length != array2.length) {
0617: return false;
0618: }
0619:
0620: for (int i = 0; i < array1.length; ++i) {
0621: Object val1 = array1[i];
0622: Object val2 = array2[i];
0623: if (!val1.equals(val2)) {
0624: return false;
0625: }
0626: }
0627:
0628: return true;
0629: }
0630:
0631: public static boolean equals(short[] array1, short[] array2) {
0632: if (array1 == array2) {
0633: return true;
0634: }
0635:
0636: if (array1 == null || array2 == null) {
0637: return false;
0638: }
0639:
0640: if (array1.length != array2.length) {
0641: return false;
0642: }
0643:
0644: for (int i = 0; i < array1.length; ++i) {
0645: if (array1[i] != array2[i]) {
0646: return false;
0647: }
0648: }
0649:
0650: return true;
0651: }
0652:
0653: public static void fill(boolean[] a, boolean val) {
0654: fill(a, 0, a.length, val);
0655: }
0656:
0657: public static void fill(boolean[] a, int fromIndex, int toIndex,
0658: boolean val) {
0659: for (int i = fromIndex; i < toIndex; ++i) {
0660: a[i] = val;
0661: }
0662: }
0663:
0664: public static void fill(byte[] a, byte val) {
0665: fill(a, 0, a.length, val);
0666: }
0667:
0668: public static void fill(byte[] a, int fromIndex, int toIndex,
0669: byte val) {
0670: for (int i = fromIndex; i < toIndex; ++i) {
0671: a[i] = val;
0672: }
0673: }
0674:
0675: public static void fill(char[] a, char val) {
0676: fill(a, 0, a.length, val);
0677: }
0678:
0679: public static void fill(char[] a, int fromIndex, int toIndex,
0680: char val) {
0681: for (int i = fromIndex; i < toIndex; ++i) {
0682: a[i] = val;
0683: }
0684: }
0685:
0686: public static void fill(double[] a, double val) {
0687: fill(a, 0, a.length, val);
0688: }
0689:
0690: public static void fill(double[] a, int fromIndex, int toIndex,
0691: double val) {
0692: for (int i = fromIndex; i < toIndex; ++i) {
0693: a[i] = val;
0694: }
0695: }
0696:
0697: public static void fill(float[] a, float val) {
0698: fill(a, 0, a.length, val);
0699: }
0700:
0701: public static void fill(float[] a, int fromIndex, int toIndex,
0702: float val) {
0703: for (int i = fromIndex; i < toIndex; ++i) {
0704: a[i] = val;
0705: }
0706: }
0707:
0708: public static void fill(int[] a, int val) {
0709: fill(a, 0, a.length, val);
0710: }
0711:
0712: public static void fill(int[] a, int fromIndex, int toIndex, int val) {
0713: for (int i = fromIndex; i < toIndex; ++i) {
0714: a[i] = val;
0715: }
0716: }
0717:
0718: public static void fill(long[] a, int fromIndex, int toIndex,
0719: long val) {
0720: for (int i = fromIndex; i < toIndex; ++i) {
0721: a[i] = val;
0722: }
0723: }
0724:
0725: public static void fill(long[] a, long val) {
0726: fill(a, 0, a.length, val);
0727: }
0728:
0729: public static void fill(Object[] a, int fromIndex, int toIndex,
0730: Object val) {
0731: for (int i = fromIndex; i < toIndex; ++i) {
0732: a[i] = val;
0733: }
0734: }
0735:
0736: public static void fill(Object[] a, Object val) {
0737: fill(a, 0, a.length, val);
0738: }
0739:
0740: public static void fill(short[] a, int fromIndex, int toIndex,
0741: short val) {
0742: for (int i = fromIndex; i < toIndex; ++i) {
0743: a[i] = val;
0744: }
0745: }
0746:
0747: public static void fill(short[] a, short val) {
0748: fill(a, 0, a.length, val);
0749: }
0750:
0751: public static int hashCode(boolean[] a) {
0752: if (a == null) {
0753: return 0;
0754: }
0755: int hashCode = 1;
0756: for (int i = 0, n = a.length; i < n; ++i) {
0757: hashCode = (31 * hashCode + (Boolean.valueOf(a[i])
0758: .hashCode())) | 0;
0759: }
0760:
0761: return hashCode;
0762: }
0763:
0764: public static int hashCode(byte[] a) {
0765: if (a == null) {
0766: return 0;
0767: }
0768: int hashCode = 1;
0769: for (int i = 0, n = a.length; i < n; ++i) {
0770: hashCode = (31 * hashCode + Byte.hashCode(a[i])) | 0;
0771: }
0772:
0773: return hashCode;
0774: }
0775:
0776: public static int hashCode(char[] a) {
0777: if (a == null) {
0778: return 0;
0779: }
0780: int hashCode = 1;
0781: for (int i = 0, n = a.length; i < n; ++i) {
0782: hashCode = (31 * hashCode + Character.hashCode(a[i])) | 0;
0783: }
0784:
0785: return hashCode;
0786: }
0787:
0788: public static int hashCode(double[] a) {
0789: if (a == null) {
0790: return 0;
0791: }
0792: int hashCode = 1;
0793: for (int i = 0, n = a.length; i < n; ++i) {
0794: hashCode = (31 * hashCode + Double.hashCode(a[i])) | 0;
0795: }
0796:
0797: return hashCode;
0798: }
0799:
0800: public static int hashCode(float[] a) {
0801: if (a == null) {
0802: return 0;
0803: }
0804: int hashCode = 1;
0805: for (int i = 0, n = a.length; i < n; ++i) {
0806: hashCode = (31 * hashCode + Float.hashCode(a[i])) | 0;
0807: }
0808:
0809: return hashCode;
0810: }
0811:
0812: public static int hashCode(int[] a) {
0813: if (a == null) {
0814: return 0;
0815: }
0816: int hashCode = 1;
0817: for (int i = 0, n = a.length; i < n; ++i) {
0818: hashCode = (31 * hashCode + Integer.hashCode(a[i])) | 0;
0819: }
0820:
0821: return hashCode;
0822: }
0823:
0824: public static int hashCode(long[] a) {
0825: if (a == null) {
0826: return 0;
0827: }
0828: int hashCode = 1;
0829: for (int i = 0, n = a.length; i < n; ++i) {
0830: hashCode = (31 * hashCode + Long.hashCode(a[i])) | 0;
0831: }
0832:
0833: return hashCode;
0834: }
0835:
0836: public static int hashCode(Object[] a) {
0837: if (a == null) {
0838: return 0;
0839: }
0840: int hashCode = 1;
0841: for (int i = 0, n = a.length; i < n; ++i) {
0842: hashCode = (31 * hashCode + a[i].hashCode()) | 0;
0843: }
0844:
0845: return hashCode;
0846: }
0847:
0848: public static int hashCode(short[] a) {
0849: if (a == null) {
0850: return 0;
0851: }
0852: int hashCode = 1;
0853: for (int i = 0, n = a.length; i < n; ++i) {
0854: hashCode = (31 * hashCode + Short.hashCode(a[i])) | 0;
0855: }
0856:
0857: return hashCode;
0858: }
0859:
0860: public static void sort(byte[] array) {
0861: nativeNumberSort(array);
0862: }
0863:
0864: public static void sort(byte[] array, int fromIndex, int toIndex) {
0865: verifySortIndices(fromIndex, toIndex, array.length);
0866: nativeNumberSort(array, fromIndex, toIndex);
0867: }
0868:
0869: public static void sort(double[] array) {
0870: nativeNumberSort(array);
0871: }
0872:
0873: public static void sort(double[] array, int fromIndex, int toIndex) {
0874: verifySortIndices(fromIndex, toIndex, array.length);
0875: nativeNumberSort(array, fromIndex, toIndex);
0876: }
0877:
0878: public static void sort(float[] array) {
0879: nativeNumberSort(array);
0880: }
0881:
0882: public static void sort(float[] array, int fromIndex, int toIndex) {
0883: verifySortIndices(fromIndex, toIndex, array.length);
0884: nativeNumberSort(array, fromIndex, toIndex);
0885: }
0886:
0887: public static void sort(int[] array) {
0888: nativeNumberSort(array);
0889: }
0890:
0891: public static void sort(int[] array, int fromIndex, int toIndex) {
0892: verifySortIndices(fromIndex, toIndex, array.length);
0893: nativeNumberSort(array, fromIndex, toIndex);
0894: }
0895:
0896: public static void sort(long[] array) {
0897: /*
0898: * TODO: if we emulate long in JS rather than using a native primitive, we
0899: * will need to change this.
0900: */
0901: nativeNumberSort(array);
0902: }
0903:
0904: public static void sort(long[] array, int fromIndex, int toIndex) {
0905: /*
0906: * TODO: if we emulate long in JS rather than using a native primitive, we
0907: * will need to change this.
0908: */
0909: verifySortIndices(fromIndex, toIndex, array.length);
0910: nativeNumberSort(array, fromIndex, toIndex);
0911: }
0912:
0913: public static void sort(Object[] array) {
0914: // Commented out implementation that uses the native sort with a fixup.
0915:
0916: // nativeObjSort(array, 0, array.length, getNativeComparator(array,
0917: // Comparators.natural()));
0918: mergeSort(array, 0, array.length, Comparators.natural());
0919: }
0920:
0921: public static void sort(Object[] x, int fromIndex, int toIndex) {
0922: // Commented out implementation that uses the native sort with a fixup.
0923:
0924: // nativeObjSort(x, fromIndex, toIndex, getNativeComparator(x,
0925: // Comparators.natural()));
0926: mergeSort(x, fromIndex, toIndex, Comparators.natural());
0927: }
0928:
0929: public static void sort(short[] array) {
0930: nativeNumberSort(array);
0931: }
0932:
0933: public static void sort(short[] array, int fromIndex, int toIndex) {
0934: verifySortIndices(fromIndex, toIndex, array.length);
0935: nativeNumberSort(array, fromIndex, toIndex);
0936: }
0937:
0938: public static <T> void sort(T[] x, Comparator<? super T> c) {
0939: // Commented out implementation that uses the native sort with a fixup.
0940:
0941: // nativeObjSort(x, 0, x.length, getNativeComparator(x, c != null ? c :
0942: // Comparators.natural()));
0943: mergeSort(x, 0, x.length, c != null ? c : Comparators.natural());
0944: }
0945:
0946: public static <T> void sort(T[] x, int fromIndex, int toIndex,
0947: Comparator<? super T> c) {
0948: // Commented out implementation that uses the native sort with a fixup.
0949:
0950: verifySortIndices(fromIndex, toIndex, x.length);
0951: // nativeObjSort(x, fromIndex, toIndex, getNativeComparator(x, c != null ? c
0952: // : Comparators.natural()));
0953: mergeSort(x, fromIndex, toIndex, c != null ? c : Comparators
0954: .natural());
0955: }
0956:
0957: public static String toString(boolean[] a) {
0958: if (a == null) {
0959: return "null";
0960: }
0961:
0962: StringBuffer b = new StringBuffer("[");
0963: for (int i = 0; i < a.length; i++) {
0964: if (i != 0) {
0965: b.append(", ");
0966: }
0967: b.append(String.valueOf(a[i]));
0968: }
0969: b.append("]");
0970: return b.toString();
0971: }
0972:
0973: public static String toString(byte[] a) {
0974: if (a == null) {
0975: return "null";
0976: }
0977:
0978: StringBuffer b = new StringBuffer("[");
0979: for (int i = 0; i < a.length; i++) {
0980: if (i != 0) {
0981: b.append(", ");
0982: }
0983: b.append(String.valueOf(a[i]));
0984: }
0985: b.append("]");
0986: return b.toString();
0987: }
0988:
0989: public static String toString(char[] a) {
0990: if (a == null) {
0991: return "null";
0992: }
0993:
0994: StringBuffer b = new StringBuffer("[");
0995: for (int i = 0; i < a.length; i++) {
0996: if (i != 0) {
0997: b.append(", ");
0998: }
0999: b.append(String.valueOf(a[i]));
1000: }
1001: b.append("]");
1002: return b.toString();
1003: }
1004:
1005: public static String toString(double[] a) {
1006: if (a == null) {
1007: return "null";
1008: }
1009:
1010: StringBuffer b = new StringBuffer("[");
1011: for (int i = 0; i < a.length; i++) {
1012: if (i != 0) {
1013: b.append(", ");
1014: }
1015: b.append(String.valueOf(a[i]));
1016: }
1017: b.append("]");
1018: return b.toString();
1019: }
1020:
1021: public static String toString(float[] a) {
1022: if (a == null) {
1023: return "null";
1024: }
1025:
1026: StringBuffer b = new StringBuffer("[");
1027: for (int i = 0; i < a.length; i++) {
1028: if (i != 0) {
1029: b.append(", ");
1030: }
1031: b.append(String.valueOf(a[i]));
1032: }
1033: b.append("]");
1034: return b.toString();
1035: }
1036:
1037: public static String toString(int[] a) {
1038: if (a == null) {
1039: return "null";
1040: }
1041:
1042: StringBuffer b = new StringBuffer("[");
1043: for (int i = 0; i < a.length; i++) {
1044: if (i != 0) {
1045: b.append(", ");
1046: }
1047: b.append(String.valueOf(a[i]));
1048: }
1049: b.append("]");
1050: return b.toString();
1051: }
1052:
1053: public static String toString(long[] a) {
1054: if (a == null) {
1055: return "null";
1056: }
1057:
1058: StringBuffer b = new StringBuffer("[");
1059: for (int i = 0; i < a.length; i++) {
1060: if (i != 0) {
1061: b.append(", ");
1062: }
1063: b.append(String.valueOf(a[i]));
1064: }
1065: b.append("]");
1066: return b.toString();
1067: }
1068:
1069: public static String toString(Object[] x) {
1070: if (x == null) {
1071: return "null";
1072: }
1073:
1074: return Arrays.asList(x).toString();
1075: }
1076:
1077: public static String toString(short[] a) {
1078: if (a == null) {
1079: return "null";
1080: }
1081:
1082: StringBuffer b = new StringBuffer("[");
1083: for (int i = 0; i < a.length; i++) {
1084: if (i != 0) {
1085: b.append(", ");
1086: }
1087: b.append(String.valueOf(a[i]));
1088: }
1089: b.append("]");
1090: return b.toString();
1091: }
1092:
1093: /**
1094: * Recursive helper function for {@link deepToString(Object[])}.
1095: */
1096: private static String deepToString(Object[] a,
1097: Set<Object[]> arraysIveSeen) {
1098: if (a == null) {
1099: return "null";
1100: }
1101:
1102: if (arraysIveSeen.contains(a)) {
1103: return "[...]";
1104: }
1105:
1106: arraysIveSeen.add(a);
1107:
1108: StringBuffer b = new StringBuffer("[");
1109: for (int i = 0; i < a.length; i++) {
1110: if (i != 0) {
1111: b.append(", ");
1112: }
1113: Object obj = a[i];
1114: if (obj == null) {
1115: b.append("null");
1116: } else if (obj.getClass().getName().startsWith("[")) {
1117: if (obj instanceof Object[]) {
1118: if (arraysIveSeen.contains(obj)) {
1119: b.append("[...]");
1120: } else {
1121: Object[] objArray = (Object[]) obj;
1122: HashSet<Object[]> tempSet = new HashSet<Object[]>(
1123: arraysIveSeen);
1124: b.append(deepToString(objArray, tempSet));
1125: }
1126: } else if (obj instanceof boolean[]) {
1127: b.append(toString((byte[]) obj));
1128: } else if (obj instanceof byte[]) {
1129: b.append(toString((byte[]) obj));
1130: } else if (obj instanceof char[]) {
1131: b.append(toString((char[]) obj));
1132: } else if (obj instanceof short[]) {
1133: b.append(toString((short[]) obj));
1134: } else if (obj instanceof int[]) {
1135: b.append(toString((int[]) obj));
1136: } else if (obj instanceof long[]) {
1137: b.append(toString((long[]) obj));
1138: } else if (obj instanceof float[]) {
1139: b.append(toString((float[]) obj));
1140: } else if (obj instanceof double[]) {
1141: b.append(toString((double[]) obj));
1142: }
1143:
1144: assert false : "Unexpected array type: "
1145: + obj.getClass().getName();
1146: } else {
1147: b.append(String.valueOf(obj));
1148: }
1149: }
1150: b.append("]");
1151: return b.toString();
1152: }
1153:
1154: /**
1155: * Return a JavaScript function object which will compare elements of the
1156: * specified object array.
1157: *
1158: * Note that this function isn't currently used but is kept because the native
1159: * sort/fixup approach is faster everywhere but IE. In the future, we may
1160: * choose to use deferred binding in the JRE to make those platforms faster.
1161: *
1162: * @param array the array of objects to compare
1163: * @param comp the Comparator to use to compare individual objects.
1164: * @return a JavaScript function object taking indices into the array to
1165: * compare. Returns the result of the comparator, or the comparison of
1166: * the indices if the comparator indicates equality so the sort is
1167: * stable. The comparator has a property <code>swap</code> which is
1168: * true if any elements were discovered to be out of order.
1169: */
1170: @SuppressWarnings("unused")
1171: // see above
1172: private static native JavaScriptObject getNativeComparator(
1173: Object array, Comparator<?> comp) /*-{
1174: function compare(a,b) {
1175: var elementCompare = comp.@java.util.Comparator::compare(Ljava/lang/Object;Ljava/lang/Object;)(array[a], array[b]);
1176: var indexCompare = a - b;
1177: // If elements compare equal, use the index comparison.
1178: elementCompare = elementCompare || indexCompare;
1179: // Keep track of having seen out-of-order elements. Note that we don't
1180: // have to worry about the sort algorithm comparing an element to itself
1181: // since it can't be swapped anyway, so we can just check for less-than.
1182: compare.swap = compare.swap || (elementCompare < 0 != indexCompare < 0);
1183: return elementCompare;
1184: }
1185: compare.swap = false;
1186: return compare;
1187: }-*/;
1188:
1189: /**
1190: * Sort a small subsection of an array by insertion sort.
1191: *
1192: * @param array array to sort
1193: * @param low lower bound of range to sort
1194: * @param high upper bound of range to sort
1195: * @param comp comparator to use
1196: */
1197: private static void insertionSort(Object[] array, int low,
1198: int high, Comparator<Object> comp) {
1199: for (int i = low + 1; i < high; ++i) {
1200: for (int j = i; j > low
1201: && comp.compare(array[j - 1], array[j]) > 0; --j) {
1202: Object t = array[j];
1203: array[j] = array[j - 1];
1204: array[j - 1] = t;
1205: }
1206: }
1207: }
1208:
1209: /**
1210: * Merge the two sorted subarrays (srcLow,srcMid] and (srcMid,srcHigh] into
1211: * dest.
1212: *
1213: * @param src source array for merge
1214: * @param srcLow lower bound of bottom sorted half
1215: * @param srcMid upper bound of bottom sorted half & lower bound of top sorted
1216: * half
1217: * @param srcHigh upper bound of top sorted half
1218: * @param dest destination array for merge
1219: * @param destLow lower bound of destination
1220: * @param destHigh upper bound of destination
1221: * @param comp comparator to use
1222: */
1223: private static void merge(Object[] src, int srcLow, int srcMid,
1224: int srcHigh, Object[] dest, int destLow, int destHigh,
1225: Comparator<Object> comp) {
1226: // can't destroy srcMid because we need it as a bound on the lower half
1227: int topIdx = srcMid;
1228: while (destLow < destHigh) {
1229: if (topIdx >= srcHigh
1230: || (srcLow < srcMid && comp.compare(src[srcLow],
1231: src[topIdx]) <= 0)) {
1232: dest[destLow++] = src[srcLow++];
1233: } else {
1234: dest[destLow++] = src[topIdx++];
1235: }
1236: }
1237: }
1238:
1239: /**
1240: * Performs a merge sort on the specified portion of an object array.
1241: *
1242: * Uses O(n) temporary space to perform the merge, but is stable.
1243: */
1244: private static void mergeSort(Object[] x, int fromIndex,
1245: int toIndex, Comparator<?> comp) {
1246: Object[] temp = Array.cloneSubrange(x, fromIndex, toIndex);
1247: mergeSort(temp, x, fromIndex, toIndex, -fromIndex,
1248: (Comparator<Object>) comp);
1249: }
1250:
1251: /**
1252: * Recursive helper function for
1253: * {@link mergeSort(Object[],int,int,Comparator<?>)}.
1254: *
1255: * @param temp temporary space, as large as the range of elements being sorted. On
1256: * entry, temp should contain a copy of the sort range from array.
1257: * @param array array to sort
1258: * @param low lower bound of range to sort
1259: * @param high upper bound of range to sort
1260: * @param ofs offset to convert an array index into a temp index
1261: * @param comp comparison function
1262: */
1263: private static void mergeSort(Object[] temp, Object[] array,
1264: int low, int high, int ofs, Comparator<Object> comp) {
1265: int length = high - low;
1266:
1267: // insertion sort for small arrays
1268: if (length < 7) {
1269: insertionSort(array, low, high, comp);
1270: return;
1271: }
1272:
1273: // recursively sort both halves, using the array as temp space
1274: int tempLow = low + ofs;
1275: int tempHigh = high + ofs;
1276: int tempMid = tempLow + ((tempHigh - tempLow) / 2);
1277: mergeSort(array, temp, tempLow, tempMid, -ofs, comp);
1278: mergeSort(array, temp, tempMid, tempHigh, -ofs, comp);
1279:
1280: // Skip merge if already in order - just copy from temp
1281: if (comp.compare(temp[tempMid - 1], temp[tempMid]) <= 0) {
1282: // TODO(jat): use System.arraycopy when that is implemented and more
1283: // efficient than this
1284: while (low < high) {
1285: array[low++] = temp[tempLow++];
1286: }
1287: return;
1288: }
1289:
1290: // merge sorted halves
1291: merge(temp, tempLow, tempMid, tempHigh, array, low, high, comp);
1292: }
1293:
1294: /**
1295: * Sort an entire array of number primitives.
1296: */
1297: private static native void nativeNumberSort(Object array) /*-{
1298: array.sort(function(a,b) { return a - b; });
1299: }-*/;
1300:
1301: /**
1302: * Sort a subset of an array of number primitives.
1303: */
1304: private static native void nativeNumberSort(Object array,
1305: int fromIndex, int toIndex) /*-{
1306: var temp = array.slice(fromIndex, toIndex);
1307: temp.sort(function(a,b) { return a - b; });
1308: var n = toIndex - fromIndex;
1309: // Do the equivalent of array.splice(fromIndex, n, temp.slice(0, n)) except
1310: // flattening the temp slice.
1311: Array.prototype.splice.apply(array, [fromIndex, n].concat(temp.slice(0, n)));
1312: }-*/;
1313:
1314: /**
1315: * Sort a subset of an array with the specified comparison function. Note that
1316: * the array is also referenced via closure in the comparison function.
1317: *
1318: * This implementation sorts it using the native (unstable) sort using an
1319: * index array and comparing the indices if they are otherwise equal, then
1320: * making another pass through the array to put them into the proper order.
1321: * This adds O(2*n) space for the index array and a temporary copy for
1322: * re-ordering (one of which is required anyway since JavaScript can't sort
1323: * subsets of an array), and the re-order pass takes O(n) time.
1324: *
1325: * Note that this function isn't currently used but is kept because the native
1326: * sort/fixup approach is faster everywhere but IE. In the future, we may
1327: * choose to use deferred binding in the JRE to make those platforms faster.
1328: *
1329: * @param array an array of either Java primitives or Object references
1330: * @param fromIndex the start of the range to sort
1331: * @param toIndex one past the end of the range to sort
1332: * @param comp a JavaScript comparison function (which holds reference to the
1333: * array to sort), which will be passed indices into the array. The
1334: * comparison function must also have a property swap which is true
1335: * if any elements were out of order.
1336: */
1337: @SuppressWarnings("unused")
1338: // see above
1339: private static native void nativeObjSort(Object array,
1340: int fromIndex, int toIndex, JavaScriptObject comp) /*-{
1341: var n = toIndex - fromIndex;
1342: var indexArray = new Array(n);
1343: var arrayIdx = fromIndex;
1344: for (var i = 0; i < n; ++i) {
1345: indexArray[i] = arrayIdx++;
1346: }
1347: indexArray.sort(comp);
1348: if (comp.swap) { // only reorder elements if we made a swap
1349: var temp = array.slice(fromIndex, toIndex);
1350: arrayIdx = fromIndex;
1351: for (var i = 0; i < n; ++i) {
1352: array[arrayIdx++] = temp[indexArray[i] - fromIndex];
1353: }
1354: }
1355: }-*/;
1356:
1357: /**
1358: * Performs the checks specified by the JRE docs and throws appropriate
1359: * exceptions.
1360: *
1361: * @param fromIndex beginning of the range to sort
1362: * @param toIndex past the end of the range to sort
1363: * @param length size of the array to sort
1364: *
1365: * @throws IllegalArgumentException if fromIndex > toIndex
1366: * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or toIndex > length
1367: */
1368: private static void verifySortIndices(int fromIndex, int toIndex,
1369: int length) {
1370: if (fromIndex > toIndex) {
1371: throw new IllegalArgumentException("fromIndex(" + fromIndex
1372: + ") > toIndex(" + toIndex + ")");
1373: }
1374: if (fromIndex < 0 || toIndex > length) {
1375: throw new ArrayIndexOutOfBoundsException("fromIndex("
1376: + fromIndex + ") or toIndex(" + toIndex
1377: + ") out of bounds (0 - " + length + ")");
1378: }
1379: }
1380: }
|