0001: /*
0002: * Licensed to the Apache Software Foundation (ASF) under one or more
0003: * contributor license agreements. See the NOTICE file distributed with
0004: * this work for additional information regarding copyright ownership.
0005: * The ASF licenses this file to You under the Apache License, Version 2.0
0006: * (the "License"); you may not use this file except in compliance with
0007: * the License. You may obtain a copy of the License at
0008: *
0009: * http://www.apache.org/licenses/LICENSE-2.0
0010: *
0011: * Unless required by applicable law or agreed to in writing, software
0012: * distributed under the License is distributed on an "AS IS" BASIS,
0013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0014: * See the License for the specific language governing permissions and
0015: * limitations under the License.
0016: */
0017:
0018: package java.util;
0019:
0020: import java.io.Serializable;
0021: import java.lang.reflect.Array;
0022:
0023: /**
0024: * Arrays contains static methods which operate on arrays.
0025: *
0026: * @since 1.2
0027: */
0028: public class Arrays {
0029:
0030: /* Specifies when to switch to insertion sort */
0031: private static final int SIMPLE_LENGTH = 7;
0032:
0033: private static class ArrayList<E> extends AbstractList<E> implements
0034: List<E>, Serializable, RandomAccess {
0035:
0036: private static final long serialVersionUID = -2764017481108945198L;
0037:
0038: private final E[] a;
0039:
0040: ArrayList(E[] storage) {
0041: if (storage == null) {
0042: throw new NullPointerException();
0043: }
0044: a = storage;
0045: }
0046:
0047: @Override
0048: public boolean contains(Object object) {
0049: if (object != null) {
0050: for (E element : a) {
0051: if (object.equals(element)) {
0052: return true;
0053: }
0054: }
0055: } else {
0056: for (E element : a) {
0057: if (element == null) {
0058: return true;
0059: }
0060: }
0061: }
0062: return false;
0063: }
0064:
0065: @Override
0066: public E get(int location) {
0067: try {
0068: return a[location];
0069: } catch (ArrayIndexOutOfBoundsException e) {
0070: throw new IndexOutOfBoundsException();
0071: }
0072: }
0073:
0074: @Override
0075: public int indexOf(Object object) {
0076: if (object != null) {
0077: for (int i = 0; i < a.length; i++) {
0078: if (object.equals(a[i])) {
0079: return i;
0080: }
0081: }
0082: } else {
0083: for (int i = 0; i < a.length; i++) {
0084: if (a[i] == null) {
0085: return i;
0086: }
0087: }
0088: }
0089: return -1;
0090: }
0091:
0092: @Override
0093: public int lastIndexOf(Object object) {
0094: if (object != null) {
0095: for (int i = a.length - 1; i >= 0; i--) {
0096: if (object.equals(a[i])) {
0097: return i;
0098: }
0099: }
0100: } else {
0101: for (int i = a.length - 1; i >= 0; i--) {
0102: if (a[i] == null) {
0103: return i;
0104: }
0105: }
0106: }
0107: return -1;
0108: }
0109:
0110: @Override
0111: public E set(int location, E object) {
0112: try {
0113: E result = a[location];
0114: a[location] = object;
0115: return result;
0116: } catch (ArrayIndexOutOfBoundsException e) {
0117: throw new IndexOutOfBoundsException();
0118: } catch (ArrayStoreException e) {
0119: throw new ClassCastException();
0120: }
0121: }
0122:
0123: @Override
0124: public int size() {
0125: return a.length;
0126: }
0127:
0128: @Override
0129: public Object[] toArray() {
0130: return a.clone();
0131: }
0132:
0133: @Override
0134: @SuppressWarnings("unchecked")
0135: public <T> T[] toArray(T[] contents) {
0136: int size = size();
0137: if (size > contents.length) {
0138: Class<?> ct = contents.getClass().getComponentType();
0139: contents = (T[]) Array.newInstance(ct, size);
0140: }
0141: System.arraycopy(a, 0, contents, 0, size);
0142: if (size < contents.length) {
0143: contents[size] = null;
0144: }
0145: return contents;
0146: }
0147: }
0148:
0149: private Arrays() {
0150: /* empty */
0151: }
0152:
0153: /**
0154: * Answers a List on the objects in the specified array. The size of the
0155: * List cannot be modified, i.e. adding and removing are unsupported, but
0156: * the elements can be set. Setting an element modifies the underlying
0157: * array.
0158: *
0159: * @param array
0160: * the array
0161: * @return a List on the specified array
0162: */
0163: public static <T> List<T> asList(T... array) {
0164: return new ArrayList<T>(array);
0165: }
0166:
0167: /**
0168: * Performs a binary search for the specified element in the specified
0169: * sorted array.
0170: *
0171: * @param array
0172: * the sorted byte array to search
0173: * @param value
0174: * the byte element to find
0175: * @return the non-negative index of the element, or a negative index which
0176: * is the -index - 1 where the element would be inserted
0177: */
0178: public static int binarySearch(byte[] array, byte value) {
0179: int low = 0, mid = -1, high = array.length - 1;
0180: while (low <= high) {
0181: mid = (low + high) >>> 1;
0182: if (value > array[mid]) {
0183: low = mid + 1;
0184: } else if (value == array[mid]) {
0185: return mid;
0186: } else {
0187: high = mid - 1;
0188: }
0189: }
0190: if (mid < 0) {
0191: return -1;
0192: }
0193:
0194: return -mid - (value < array[mid] ? 1 : 2);
0195: }
0196:
0197: /**
0198: * Performs a binary search for the specified element in the specified
0199: * sorted array.
0200: *
0201: * @param array
0202: * the sorted char array to search
0203: * @param value
0204: * the char element to find
0205: * @return the non-negative index of the element, or a negative index which
0206: * is the -index - 1 where the element would be inserted
0207: */
0208: public static int binarySearch(char[] array, char value) {
0209: int low = 0, mid = -1, high = array.length - 1;
0210: while (low <= high) {
0211: mid = (low + high) >>> 1;
0212: if (value > array[mid]) {
0213: low = mid + 1;
0214: } else if (value == array[mid]) {
0215: return mid;
0216: } else {
0217: high = mid - 1;
0218: }
0219: }
0220: if (mid < 0) {
0221: return -1;
0222: }
0223: return -mid - (value < array[mid] ? 1 : 2);
0224: }
0225:
0226: /**
0227: * Performs a binary search for the specified element in the specified
0228: * sorted array.
0229: *
0230: * @param array
0231: * the sorted double array to search
0232: * @param value
0233: * the double element to find
0234: * @return the non-negative index of the element, or a negative index which
0235: * is the -index - 1 where the element would be inserted
0236: */
0237: public static int binarySearch(double[] array, double value) {
0238: long longBits = Double.doubleToLongBits(value);
0239: int low = 0, mid = -1, high = array.length - 1;
0240: while (low <= high) {
0241: mid = (low + high) >>> 1;
0242: if (lessThan(array[mid], value)) {
0243: low = mid + 1;
0244: } else if (longBits == Double.doubleToLongBits(array[mid])) {
0245: return mid;
0246: } else {
0247: high = mid - 1;
0248: }
0249: }
0250: if (mid < 0) {
0251: return -1;
0252: }
0253: return -mid - (lessThan(value, array[mid]) ? 1 : 2);
0254: }
0255:
0256: /**
0257: * Performs a binary search for the specified element in the specified
0258: * sorted array.
0259: *
0260: * @param array
0261: * the sorted float array to search
0262: * @param value
0263: * the float element to find
0264: * @return the non-negative index of the element, or a negative index which
0265: * is the -index - 1 where the element would be inserted
0266: */
0267: public static int binarySearch(float[] array, float value) {
0268: int intBits = Float.floatToIntBits(value);
0269: int low = 0, mid = -1, high = array.length - 1;
0270: while (low <= high) {
0271: mid = (low + high) >>> 1;
0272: if (lessThan(array[mid], value)) {
0273: low = mid + 1;
0274: } else if (intBits == Float.floatToIntBits(array[mid])) {
0275: return mid;
0276: } else {
0277: high = mid - 1;
0278: }
0279: }
0280: if (mid < 0) {
0281: return -1;
0282: }
0283: return -mid - (lessThan(value, array[mid]) ? 1 : 2);
0284: }
0285:
0286: /**
0287: * Performs a binary search for the specified element in the specified
0288: * sorted array.
0289: *
0290: * @param array
0291: * the sorted int array to search
0292: * @param value
0293: * the int element to find
0294: * @return the non-negative index of the element, or a negative index which
0295: * is the -index - 1 where the element would be inserted
0296: */
0297: public static int binarySearch(int[] array, int value) {
0298: int low = 0, mid = -1, high = array.length - 1;
0299: while (low <= high) {
0300: mid = (low + high) >>> 1;
0301: if (value > array[mid]) {
0302: low = mid + 1;
0303: } else if (value == array[mid]) {
0304: return mid;
0305: } else {
0306: high = mid - 1;
0307: }
0308: }
0309: if (mid < 0) {
0310: return -1;
0311: }
0312: return -mid - (value < array[mid] ? 1 : 2);
0313: }
0314:
0315: /**
0316: * Performs a binary search for the specified element in the specified
0317: * sorted array.
0318: *
0319: * @param array
0320: * the sorted long array to search
0321: * @param value
0322: * the long element to find
0323: * @return the non-negative index of the element, or a negative index which
0324: * is the -index - 1 where the element would be inserted
0325: */
0326: public static int binarySearch(long[] array, long value) {
0327: int low = 0, mid = -1, high = array.length - 1;
0328: while (low <= high) {
0329: mid = (low + high) >>> 1;
0330: if (value > array[mid]) {
0331: low = mid + 1;
0332: } else if (value == array[mid]) {
0333: return mid;
0334: } else {
0335: high = mid - 1;
0336: }
0337: }
0338: if (mid < 0) {
0339: return -1;
0340: }
0341: return -mid - (value < array[mid] ? 1 : 2);
0342: }
0343:
0344: /**
0345: * Performs a binary search for the specified element in the specified
0346: * sorted array.
0347: *
0348: * @param array
0349: * the sorted Object array to search
0350: * @param object
0351: * the Object element to find
0352: * @return the non-negative index of the element, or a negative index which
0353: * is the -index - 1 where the element would be inserted
0354: *
0355: * @exception ClassCastException
0356: * when an element in the array or the search element does
0357: * not implement Comparable, or cannot be compared to each
0358: * other
0359: */
0360: @SuppressWarnings("unchecked")
0361: public static int binarySearch(Object[] array, Object object) {
0362: if (array.length == 0) {
0363: return -1;
0364: }
0365:
0366: int low = 0, mid = 0, high = array.length - 1, result = 0;
0367: while (low <= high) {
0368: mid = (low + high) >>> 1;
0369: if ((result = ((Comparable<Object>) array[mid])
0370: .compareTo(object)) < 0) {
0371: low = mid + 1;
0372: } else if (result == 0) {
0373: return mid;
0374: } else {
0375: high = mid - 1;
0376: }
0377: }
0378: return -mid - (result >= 0 ? 1 : 2);
0379: }
0380:
0381: /**
0382: * Performs a binary search for the specified element in the specified
0383: * sorted array using the Comparator to compare elements.
0384: *
0385: * @param array
0386: * the sorted char array to search
0387: * @param object
0388: * the char element to find
0389: * @param comparator
0390: * the Comparator
0391: * @return the non-negative index of the element, or a negative index which
0392: * is the -index - 1 where the element would be inserted
0393: *
0394: * @exception ClassCastException
0395: * when an element in the array and the search element cannot
0396: * be compared to each other using the Comparator
0397: */
0398: public static <T> int binarySearch(T[] array, T object,
0399: Comparator<? super T> comparator) {
0400: if (comparator == null) {
0401: return binarySearch(array, object);
0402: }
0403:
0404: int low = 0, mid = 0, high = array.length - 1, result = 0;
0405: while (low <= high) {
0406: mid = (low + high) >>> 1;
0407: if ((result = comparator.compare(array[mid], object)) < 0) {
0408: low = mid + 1;
0409: } else if (result == 0) {
0410: return mid;
0411: } else {
0412: high = mid - 1;
0413: }
0414: }
0415: return -mid - (result >= 0 ? 1 : 2);
0416: }
0417:
0418: /**
0419: * Performs a binary search for the specified element in the specified
0420: * sorted array.
0421: *
0422: * @param array
0423: * the sorted short array to search
0424: * @param value
0425: * the short element to find
0426: * @return the non-negative index of the element, or a negative index which
0427: * is the -index - 1 where the element would be inserted
0428: */
0429: public static int binarySearch(short[] array, short value) {
0430: int low = 0, mid = -1, high = array.length - 1;
0431: while (low <= high) {
0432: mid = (low + high) >>> 1;
0433: if (value > array[mid]) {
0434: low = mid + 1;
0435: } else if (value == array[mid]) {
0436: return mid;
0437: } else {
0438: high = mid - 1;
0439: }
0440: }
0441: if (mid < 0) {
0442: return -1;
0443: }
0444: return -mid - (value < array[mid] ? 1 : 2);
0445: }
0446:
0447: /**
0448: * Fills the array with the given value.
0449: *
0450: * @param array
0451: * the byte array to fill
0452: * @param value
0453: * the byte element
0454: */
0455: public static void fill(byte[] array, byte value) {
0456: for (int i = 0; i < array.length; i++) {
0457: array[i] = value;
0458: }
0459: }
0460:
0461: /**
0462: * Fills the section of the array between the given indices with the given value.
0463: *
0464: * @param array
0465: * the byte array to fill
0466: * @param start
0467: * the start index
0468: * @param end
0469: * the end index + 1
0470: * @param value
0471: * the byte element
0472: *
0473: * @exception IllegalArgumentException
0474: * when <code>start > end</code>
0475: * @exception ArrayIndexOutOfBoundsException
0476: * when <code>start < 0</code> or
0477: * <code>end > array.size()</code>
0478: */
0479: public static void fill(byte[] array, int start, int end, byte value) {
0480: // Check for null first
0481: int length = array.length;
0482: if (start > end) {
0483: throw new IllegalArgumentException();
0484: }
0485: if (start < 0 || end > length) {
0486: throw new ArrayIndexOutOfBoundsException();
0487: }
0488: for (int i = start; i < end; i++) {
0489: array[i] = value;
0490: }
0491: }
0492:
0493: /**
0494: * Fills the array with the given value.
0495: *
0496: * @param array
0497: * the short array to fill
0498: * @param value
0499: * the short element
0500: */
0501: public static void fill(short[] array, short value) {
0502: for (int i = 0; i < array.length; i++) {
0503: array[i] = value;
0504: }
0505: }
0506:
0507: /**
0508: * Fills the section of the array between the given indices with the given value.
0509: *
0510: * @param array
0511: * the short array to fill
0512: * @param start
0513: * the start index
0514: * @param end
0515: * the end index + 1
0516: * @param value
0517: * the short element
0518: *
0519: * @exception IllegalArgumentException
0520: * when <code>start > end</code>
0521: * @exception ArrayIndexOutOfBoundsException
0522: * when <code>start < 0</code> or
0523: * <code>end > array.size()</code>
0524: */
0525: public static void fill(short[] array, int start, int end,
0526: short value) {
0527: // Check for null first
0528: int length = array.length;
0529: if (start > end) {
0530: throw new IllegalArgumentException();
0531: }
0532: if (start < 0 || end > length) {
0533: throw new ArrayIndexOutOfBoundsException();
0534: }
0535: for (int i = start; i < end; i++) {
0536: array[i] = value;
0537: }
0538: }
0539:
0540: /**
0541: * Fills the array with the given value.
0542: *
0543: * @param array
0544: * the char array to fill
0545: * @param value
0546: * the char element
0547: */
0548: public static void fill(char[] array, char value) {
0549: for (int i = 0; i < array.length; i++) {
0550: array[i] = value;
0551: }
0552: }
0553:
0554: /**
0555: * Fills the section of the array between the given indices with the given value.
0556: *
0557: * @param array
0558: * the char array to fill
0559: * @param start
0560: * the start index
0561: * @param end
0562: * the end index + 1
0563: * @param value
0564: * the char element
0565: *
0566: * @exception IllegalArgumentException
0567: * when <code>start > end</code>
0568: * @exception ArrayIndexOutOfBoundsException
0569: * when <code>start < 0</code> or
0570: * <code>end > array.size()</code>
0571: */
0572: public static void fill(char[] array, int start, int end, char value) {
0573: // Check for null first
0574: int length = array.length;
0575: if (start > end) {
0576: throw new IllegalArgumentException();
0577: }
0578: if (start < 0 || end > length) {
0579: throw new ArrayIndexOutOfBoundsException();
0580: }
0581: for (int i = start; i < end; i++) {
0582: array[i] = value;
0583: }
0584: }
0585:
0586: /**
0587: * Fills the array with the given value.
0588: *
0589: * @param array
0590: * the int array to fill
0591: * @param value
0592: * the int element
0593: */
0594: public static void fill(int[] array, int value) {
0595: for (int i = 0; i < array.length; i++) {
0596: array[i] = value;
0597: }
0598: }
0599:
0600: /**
0601: * Fills the section of the array between the given indices with the given value.
0602: *
0603: * @param array
0604: * the int array to fill
0605: * @param start
0606: * the start index
0607: * @param end
0608: * the end index + 1
0609: * @param value
0610: * the int element
0611: *
0612: * @exception IllegalArgumentException
0613: * when <code>start > end</code>
0614: * @exception ArrayIndexOutOfBoundsException
0615: * when <code>start < 0</code> or
0616: * <code>end > array.size()</code>
0617: */
0618: public static void fill(int[] array, int start, int end, int value) {
0619: // Check for null first
0620: int length = array.length;
0621: if (start > end) {
0622: throw new IllegalArgumentException();
0623: }
0624: if (start < 0 || end > length) {
0625: throw new ArrayIndexOutOfBoundsException();
0626: }
0627: for (int i = start; i < end; i++) {
0628: array[i] = value;
0629: }
0630: }
0631:
0632: /**
0633: * Fills the array with the given value.
0634: *
0635: * @param array
0636: * the long array to fill
0637: * @param value
0638: * the long element
0639: */
0640: public static void fill(long[] array, long value) {
0641: for (int i = 0; i < array.length; i++) {
0642: array[i] = value;
0643: }
0644: }
0645:
0646: /**
0647: * Fills the section of the array between the given indices with the given value.
0648: *
0649: * @param array
0650: * the long array to fill
0651: * @param start
0652: * the start index
0653: * @param end
0654: * the end index + 1
0655: * @param value
0656: * the long element
0657: *
0658: * @exception IllegalArgumentException
0659: * when <code>start > end</code>
0660: * @exception ArrayIndexOutOfBoundsException
0661: * when <code>start < 0</code> or
0662: * <code>end > array.size()</code>
0663: */
0664: public static void fill(long[] array, int start, int end, long value) {
0665: // Check for null first
0666: int length = array.length;
0667: if (start > end) {
0668: throw new IllegalArgumentException();
0669: }
0670: if (start < 0 || end > length) {
0671: throw new ArrayIndexOutOfBoundsException();
0672: }
0673: for (int i = start; i < end; i++) {
0674: array[i] = value;
0675: }
0676: }
0677:
0678: /**
0679: * Fills the array with the given value.
0680: *
0681: * @param array
0682: * the float array to fill
0683: * @param value
0684: * the float element
0685: */
0686: public static void fill(float[] array, float value) {
0687: for (int i = 0; i < array.length; i++) {
0688: array[i] = value;
0689: }
0690: }
0691:
0692: /**
0693: * Fills the section of the array between the given indices with the given value.
0694: *
0695: * @param array
0696: * the float array to fill
0697: * @param start
0698: * the start index
0699: * @param end
0700: * the end index + 1
0701: * @param value
0702: * the float element
0703: *
0704: * @exception IllegalArgumentException
0705: * when <code>start > end</code>
0706: * @exception ArrayIndexOutOfBoundsException
0707: * when <code>start < 0</code> or
0708: * <code>end > array.size()</code>
0709: */
0710: public static void fill(float[] array, int start, int end,
0711: float value) {
0712: // Check for null first
0713: int length = array.length;
0714: if (start > end) {
0715: throw new IllegalArgumentException();
0716: }
0717: if (start < 0 || end > length) {
0718: throw new ArrayIndexOutOfBoundsException();
0719: }
0720: for (int i = start; i < end; i++) {
0721: array[i] = value;
0722: }
0723: }
0724:
0725: /**
0726: * Fills the array with the given value.
0727: *
0728: * @param array
0729: * the float array to fill
0730: * @param value
0731: * the float element
0732: */
0733: public static void fill(double[] array, double value) {
0734: for (int i = 0; i < array.length; i++) {
0735: array[i] = value;
0736: }
0737: }
0738:
0739: /**
0740: * Fills the section of the array between the given indices with the given value.
0741: *
0742: * @param array
0743: * the double array to fill
0744: * @param start
0745: * the start index
0746: * @param end
0747: * the end index + 1
0748: * @param value
0749: * the double element
0750: *
0751: * @exception IllegalArgumentException
0752: * when <code>start > end</code>
0753: * @exception ArrayIndexOutOfBoundsException
0754: * when <code>start < 0</code> or
0755: * <code>end > array.size()</code>
0756: */
0757: public static void fill(double[] array, int start, int end,
0758: double value) {
0759: // Check for null first
0760: int length = array.length;
0761: if (start > end) {
0762: throw new IllegalArgumentException();
0763: }
0764: if (start < 0 || end > length) {
0765: throw new ArrayIndexOutOfBoundsException();
0766: }
0767: for (int i = start; i < end; i++) {
0768: array[i] = value;
0769: }
0770: }
0771:
0772: /**
0773: * Fills the array with the given value.
0774: *
0775: * @param array
0776: * the boolean array to fill
0777: * @param value
0778: * the boolean element
0779: */
0780: public static void fill(boolean[] array, boolean value) {
0781: for (int i = 0; i < array.length; i++) {
0782: array[i] = value;
0783: }
0784: }
0785:
0786: /**
0787: * Fills the section of the array between the given indices with the given value.
0788: *
0789: * @param array
0790: * the boolean array to fill
0791: * @param start
0792: * the start index
0793: * @param end
0794: * the end index + 1
0795: * @param value
0796: * the boolean element
0797: *
0798: * @exception IllegalArgumentException
0799: * when <code>start > end</code>
0800: * @exception ArrayIndexOutOfBoundsException
0801: * when <code>start < 0</code> or
0802: * <code>end > array.size()</code>
0803: */
0804: public static void fill(boolean[] array, int start, int end,
0805: boolean value) {
0806: // Check for null first
0807: int length = array.length;
0808: if (start > end) {
0809: throw new IllegalArgumentException();
0810: }
0811: if (start < 0 || end > length) {
0812: throw new ArrayIndexOutOfBoundsException();
0813: }
0814: for (int i = start; i < end; i++) {
0815: array[i] = value;
0816: }
0817: }
0818:
0819: /**
0820: * Fills the array with the given value.
0821: *
0822: * @param array
0823: * the Object array to fill
0824: * @param value
0825: * the Object element
0826: */
0827: public static void fill(Object[] array, Object value) {
0828: for (int i = 0; i < array.length; i++) {
0829: array[i] = value;
0830: }
0831: }
0832:
0833: /**
0834: * Fills the section of the array between the given indices with the given value.
0835: *
0836: * @param array
0837: * the Object array to fill
0838: * @param start
0839: * the start index
0840: * @param end
0841: * the end index + 1
0842: * @param value
0843: * the Object element
0844: *
0845: * @exception IllegalArgumentException
0846: * when <code>start > end</code>
0847: * @exception ArrayIndexOutOfBoundsException
0848: * when <code>start < 0</code> or
0849: * <code>end > array.size()</code>
0850: */
0851: public static void fill(Object[] array, int start, int end,
0852: Object value) {
0853: // Check for null first
0854: int length = array.length;
0855: if (start > end) {
0856: throw new IllegalArgumentException();
0857: }
0858: if (start < 0 || end > length) {
0859: throw new ArrayIndexOutOfBoundsException();
0860: }
0861: for (int i = start; i < end; i++) {
0862: array[i] = value;
0863: }
0864: }
0865:
0866: /**
0867: * Returns the hash code for the given array.
0868: *
0869: * If Arrays.equals(...) returns true for two arrays then their hash codes
0870: * will also be equal.
0871: *
0872: * The value returned by this method is the same value as the
0873: * {@link List#hashCode()}} method which is invoked on a {@link List}}
0874: * containing a sequence of {@link Boolean}} instances representing the
0875: * elements of array in the same order.
0876: *
0877: * If the array is null the return value will be 0.
0878: *
0879: * @param array
0880: * the array to return the hash code for
0881: * @return the hash code for array
0882: */
0883: public static int hashCode(boolean[] array) {
0884: if (array == null) {
0885: return 0;
0886: }
0887: int hashCode = 1;
0888: for (boolean element : array) {
0889: // 1231, 1237 are hash code values for boolean value
0890: hashCode = 31 * hashCode + (element ? 1231 : 1237);
0891: }
0892: return hashCode;
0893: }
0894:
0895: /**
0896: * Returns the hash code for the given array.
0897: *
0898: * If Arrays.equals(...) returns true for two arrays then their hash codes
0899: * will also be equal.
0900: *
0901: * The value returned by this method is the same value as the
0902: * {@link List#hashCode()}} method which is invoked on a {@link List}}
0903: * containing a sequence of {@link Integer}} instances representing the
0904: * elements of array in the same order.
0905: *
0906: * If the array is null the return value will be 0.
0907: *
0908: * @param array
0909: * the array to return the hash code for
0910: * @return the hash code for array
0911: */
0912: public static int hashCode(int[] array) {
0913: if (array == null) {
0914: return 0;
0915: }
0916: int hashCode = 1;
0917: for (int element : array) {
0918: // the hash code value for integer value is integer value itself
0919: hashCode = 31 * hashCode + element;
0920: }
0921: return hashCode;
0922: }
0923:
0924: /**
0925: * Returns the hash code for the given array.
0926: *
0927: * If Arrays.equals(...) returns true for two arrays then their hash codes
0928: * will also be equal.
0929: *
0930: * The value returned by this method is the same value as the
0931: * {@link List#hashCode()}} method which is invoked on a {@link List}}
0932: * containing a sequence of {@link Short}} instances representing the
0933: * elements of array in the same order.
0934: *
0935: * If the array is null the return value will be 0.
0936: *
0937: * @param array
0938: * the array to return the hash code for
0939: * @return the hash code for array
0940: */
0941: public static int hashCode(short[] array) {
0942: if (array == null) {
0943: return 0;
0944: }
0945: int hashCode = 1;
0946: for (short element : array) {
0947: // the hash code value for short value is its integer value
0948: hashCode = 31 * hashCode + element;
0949: }
0950: return hashCode;
0951: }
0952:
0953: /**
0954: * Returns the hash code for the given array.
0955: *
0956: * If Arrays.equals(...) returns true for two arrays then their hash codes
0957: * will also be equal.
0958: *
0959: * The value returned by this method is the same value as the
0960: * {@link List#hashCode()}} method which is invoked on a {@link List}}
0961: * containing a sequence of {@link Character}} instances representing the
0962: * elements of array in the same order.
0963: *
0964: * If the array is null the return value will be 0.
0965: *
0966: * @param array
0967: * the array to return the hash code for
0968: * @return the hash code for array
0969: */
0970: public static int hashCode(char[] array) {
0971: if (array == null) {
0972: return 0;
0973: }
0974: int hashCode = 1;
0975: for (char element : array) {
0976: // the hash code value for char value is its integer value
0977: hashCode = 31 * hashCode + element;
0978: }
0979: return hashCode;
0980: }
0981:
0982: /**
0983: * Returns the hash code for the given array.
0984: *
0985: * If Arrays.equals(...) returns true for two arrays then their hash codes
0986: * will also be equal.
0987: *
0988: * The value returned by this method is the same value as the
0989: * {@link List#hashCode()}} method which is invoked on a {@link List}}
0990: * containing a sequence of {@link Byte}} instances representing the
0991: * elements of array in the same order.
0992: *
0993: * If the array is null the return value will be 0.
0994: *
0995: * @param array
0996: * the array to return the hash code for
0997: * @return the hash code for array
0998: */
0999: public static int hashCode(byte[] array) {
1000: if (array == null) {
1001: return 0;
1002: }
1003: int hashCode = 1;
1004: for (byte element : array) {
1005: // the hash code value for byte value is its integer value
1006: hashCode = 31 * hashCode + element;
1007: }
1008: return hashCode;
1009: }
1010:
1011: /**
1012: * Returns the hash code for the given array.
1013: *
1014: * If Arrays.equals(...) returns true for two arrays then their hash codes
1015: * will also be equal.
1016: *
1017: * The value returned by this method is the same value as the
1018: * {@link List#hashCode()}} method which is invoked on a {@link List}}
1019: * containing a sequence of {@link Long}} instances representing the
1020: * elements of array in the same order.
1021: *
1022: * If the array is null the return value will be 0.
1023: *
1024: * @param array
1025: * the array to return the hash code for
1026: * @return the hash code for array
1027: */
1028: public static int hashCode(long[] array) {
1029: if (array == null) {
1030: return 0;
1031: }
1032: int hashCode = 1;
1033: for (long elementValue : array) {
1034: /*
1035: * the hash code value for long value is (int) (value ^ (value >>>
1036: * 32))
1037: */
1038: hashCode = 31 * hashCode
1039: + (int) (elementValue ^ (elementValue >>> 32));
1040: }
1041: return hashCode;
1042: }
1043:
1044: /**
1045: * Returns the hash code for the given array.
1046: *
1047: * If Arrays.equals(...) returns true for two arrays then their hash codes
1048: * will also be equal.
1049: *
1050: * The value returned by this method is the same value as the
1051: * {@link List#hashCode()}} method which is invoked on a {@link List}}
1052: * containing a sequence of {@link Float}} instances representing the
1053: * elements of array in the same order.
1054: *
1055: * If the array is null the return value will be 0.
1056: *
1057: * @param array
1058: * the array to return the hash code for
1059: * @return the hash code for array
1060: */
1061: public static int hashCode(float[] array) {
1062: if (array == null) {
1063: return 0;
1064: }
1065: int hashCode = 1;
1066: for (float element : array) {
1067: /*
1068: * the hash code value for float value is
1069: * Float.floatToIntBits(value)
1070: */
1071: hashCode = 31 * hashCode + Float.floatToIntBits(element);
1072: }
1073: return hashCode;
1074: }
1075:
1076: /**
1077: * Returns the hash code for the given array.
1078: *
1079: * If Arrays.equals(...) returns true for two arrays then their hash codes
1080: * will also be equal.
1081: *
1082: * The value returned by this method is the same value as the
1083: * {@link List#hashCode()}} method which is invoked on a {@link List}}
1084: * containing a sequence of {@link Double}} instances representing the
1085: * elements of array in the same order.
1086: *
1087: * If the array is null, the return value will be 0.
1088: *
1089: * @param array
1090: * the array to return the hash code for
1091: * @return the hash code for array
1092: */
1093: public static int hashCode(double[] array) {
1094: if (array == null) {
1095: return 0;
1096: }
1097: int hashCode = 1;
1098:
1099: for (double element : array) {
1100: long v = Double.doubleToLongBits(element);
1101: /*
1102: * the hash code value for double value is (int) (v ^ (v >>> 32))
1103: * where v = Double.doubleToLongBits(value)
1104: */
1105: hashCode = 31 * hashCode + (int) (v ^ (v >>> 32));
1106: }
1107: return hashCode;
1108: }
1109:
1110: /**
1111: * Returns the hash code for the given array. If this array contains other
1112: * arrays, their contents will not be recursively searched so this method
1113: * should be used if the array is likely to contain a reference to itself.
1114: *
1115: * If Arrays.equals(...) returns true for two arrays then their hash codes
1116: * will also be equal.
1117: *
1118: * The value returned by this method is the same value as the method
1119: * Arrays.asList(array).hashCode().
1120: *
1121: * If the array is null, the return value will be 0.
1122: *
1123: * @param array
1124: * the array to return the hash code for
1125: * @return the hash code for array
1126: */
1127: public static int hashCode(Object[] array) {
1128: if (array == null) {
1129: return 0;
1130: }
1131: int hashCode = 1;
1132: for (Object element : array) {
1133: int elementHashCode;
1134:
1135: if (element == null) {
1136: elementHashCode = 0;
1137: } else {
1138: elementHashCode = (element).hashCode();
1139: }
1140: hashCode = 31 * hashCode + elementHashCode;
1141: }
1142: return hashCode;
1143: }
1144:
1145: /**
1146: * Returns the 'deep' hash code for the given array. This means that if this
1147: * array contains other arrays their contents will also be included in the
1148: * hash and so on recursively. This method should not be used if the array
1149: * or any arrays contained within it are likely to contain a reference to
1150: * itself.
1151: *
1152: * If Arrays.deepEquals(...) returns true for two arrays then their deep
1153: * hash codes will also be equal.
1154: *
1155: * If the array is null the return value will be 0.
1156: *
1157: * @param array
1158: * the array to return the hash code for
1159: * @return the hash code for array
1160: */
1161: public static int deepHashCode(Object[] array) {
1162: if (array == null) {
1163: return 0;
1164: }
1165: int hashCode = 1;
1166: for (Object element : array) {
1167: int elementHashCode = deepHashCodeElement(element);
1168: hashCode = 31 * hashCode + elementHashCode;
1169: }
1170: return hashCode;
1171: }
1172:
1173: private static int deepHashCodeElement(Object element) {
1174: Class<?> cl;
1175: if (element == null) {
1176: return 0;
1177: }
1178:
1179: cl = element.getClass().getComponentType();
1180:
1181: if (cl == null) {
1182: return element.hashCode();
1183: }
1184:
1185: /*
1186: * element is an array
1187: */
1188: if (!cl.isPrimitive()) {
1189: return deepHashCode((Object[]) element);
1190: }
1191: if (cl.equals(int.class)) {
1192: return hashCode((int[]) element);
1193: }
1194: if (cl.equals(char.class)) {
1195: return hashCode((char[]) element);
1196: }
1197: if (cl.equals(boolean.class)) {
1198: return hashCode((boolean[]) element);
1199: }
1200: if (cl.equals(byte.class)) {
1201: return hashCode((byte[]) element);
1202: }
1203: if (cl.equals(long.class)) {
1204: return hashCode((long[]) element);
1205: }
1206: if (cl.equals(float.class)) {
1207: return hashCode((float[]) element);
1208: }
1209: if (cl.equals(double.class)) {
1210: return hashCode((double[]) element);
1211: }
1212: return hashCode((short[]) element);
1213: }
1214:
1215: /**
1216: * Compares the two arrays.
1217: *
1218: * @param array1
1219: * the first byte array
1220: * @param array2
1221: * the second byte array
1222: * @return true when the arrays have the same length and the elements at
1223: * each index in the two arrays are equal, false otherwise
1224: */
1225: public static boolean equals(byte[] array1, byte[] array2) {
1226: if (array1 == array2) {
1227: return true;
1228: }
1229: if (array1 == null || array2 == null
1230: || array1.length != array2.length) {
1231: return false;
1232: }
1233: for (int i = 0; i < array1.length; i++) {
1234: if (array1[i] != array2[i]) {
1235: return false;
1236: }
1237: }
1238: return true;
1239: }
1240:
1241: /**
1242: * Compares the two arrays.
1243: *
1244: * @param array1
1245: * the first short array
1246: * @param array2
1247: * the second short array
1248: * @return true when the arrays have the same length and the elements at
1249: * each index in the two arrays are equal, false otherwise
1250: */
1251: public static boolean equals(short[] array1, short[] array2) {
1252: if (array1 == array2) {
1253: return true;
1254: }
1255: if (array1 == null || array2 == null
1256: || array1.length != array2.length) {
1257: return false;
1258: }
1259: for (int i = 0; i < array1.length; i++) {
1260: if (array1[i] != array2[i]) {
1261: return false;
1262: }
1263: }
1264: return true;
1265: }
1266:
1267: /**
1268: * Compares the two arrays.
1269: *
1270: * @param array1
1271: * the first char array
1272: * @param array2
1273: * the second char array
1274: * @return true when the arrays have the same length and the elements at
1275: * each index in the two arrays are equal, false otherwise
1276: */
1277: public static boolean equals(char[] array1, char[] array2) {
1278: if (array1 == array2) {
1279: return true;
1280: }
1281: if (array1 == null || array2 == null
1282: || array1.length != array2.length) {
1283: return false;
1284: }
1285: for (int i = 0; i < array1.length; i++) {
1286: if (array1[i] != array2[i]) {
1287: return false;
1288: }
1289: }
1290: return true;
1291: }
1292:
1293: /**
1294: * Compares the two arrays.
1295: *
1296: * @param array1
1297: * the first int array
1298: * @param array2
1299: * the second int array
1300: * @return true when the arrays have the same length and the elements at
1301: * each index in the two arrays are equal, false otherwise
1302: */
1303: public static boolean equals(int[] array1, int[] array2) {
1304: if (array1 == array2) {
1305: return true;
1306: }
1307: if (array1 == null || array2 == null
1308: || array1.length != array2.length) {
1309: return false;
1310: }
1311: for (int i = 0; i < array1.length; i++) {
1312: if (array1[i] != array2[i]) {
1313: return false;
1314: }
1315: }
1316: return true;
1317: }
1318:
1319: /**
1320: * Compares the two arrays.
1321: *
1322: * @param array1
1323: * the first long array
1324: * @param array2
1325: * the second long array
1326: * @return true when the arrays have the same length and the elements at
1327: * each index in the two arrays are equal, false otherwise
1328: */
1329: public static boolean equals(long[] array1, long[] array2) {
1330: if (array1 == array2) {
1331: return true;
1332: }
1333: if (array1 == null || array2 == null
1334: || array1.length != array2.length) {
1335: return false;
1336: }
1337: for (int i = 0; i < array1.length; i++) {
1338: if (array1[i] != array2[i]) {
1339: return false;
1340: }
1341: }
1342: return true;
1343: }
1344:
1345: /**
1346: * Compares the two arrays. The values are compared in the same manner as
1347: * Float.equals().
1348: *
1349: * @param array1
1350: * the first float array
1351: * @param array2
1352: * the second float array
1353: * @return true when the arrays have the same length and the elements at
1354: * each index in the two arrays are equal, false otherwise
1355: *
1356: * @see Float#equals(Object)
1357: */
1358: public static boolean equals(float[] array1, float[] array2) {
1359: if (array1 == array2) {
1360: return true;
1361: }
1362: if (array1 == null || array2 == null
1363: || array1.length != array2.length) {
1364: return false;
1365: }
1366: for (int i = 0; i < array1.length; i++) {
1367: if (Float.floatToIntBits(array1[i]) != Float
1368: .floatToIntBits(array2[i])) {
1369: return false;
1370: }
1371: }
1372: return true;
1373: }
1374:
1375: /**
1376: * Compares the two arrays. The values are compared in the same manner as
1377: * Double.equals().
1378: *
1379: * @param array1
1380: * the first double array
1381: * @param array2
1382: * the second double array
1383: * @return true when the arrays have the same length and the elements at
1384: * each index in the two arrays are equal, false otherwise
1385: *
1386: * @see Double#equals(Object)
1387: */
1388: public static boolean equals(double[] array1, double[] array2) {
1389: if (array1 == array2) {
1390: return true;
1391: }
1392: if (array1 == null || array2 == null
1393: || array1.length != array2.length) {
1394: return false;
1395: }
1396: for (int i = 0; i < array1.length; i++) {
1397: if (Double.doubleToLongBits(array1[i]) != Double
1398: .doubleToLongBits(array2[i])) {
1399: return false;
1400: }
1401: }
1402: return true;
1403: }
1404:
1405: /**
1406: * Compares the two arrays.
1407: *
1408: * @param array1
1409: * the first boolean array
1410: * @param array2
1411: * the second boolean array
1412: * @return true when the arrays have the same length and the elements at
1413: * each index in the two arrays are equal, false otherwise
1414: */
1415: public static boolean equals(boolean[] array1, boolean[] array2) {
1416: if (array1 == array2) {
1417: return true;
1418: }
1419: if (array1 == null || array2 == null
1420: || array1.length != array2.length) {
1421: return false;
1422: }
1423: for (int i = 0; i < array1.length; i++) {
1424: if (array1[i] != array2[i]) {
1425: return false;
1426: }
1427: }
1428: return true;
1429: }
1430:
1431: /**
1432: * Compares the two arrays.
1433: *
1434: * @param array1
1435: * the first Object array
1436: * @param array2
1437: * the second Object array
1438: * @return true when the arrays have the same length and the elements at
1439: * each index in the two arrays are equal, false otherwise
1440: */
1441: public static boolean equals(Object[] array1, Object[] array2) {
1442: if (array1 == array2) {
1443: return true;
1444: }
1445: if (array1 == null || array2 == null
1446: || array1.length != array2.length) {
1447: return false;
1448: }
1449: for (int i = 0; i < array1.length; i++) {
1450: Object e1 = array1[i], e2 = array2[i];
1451: if (!(e1 == null ? e2 == null : e1.equals(e2))) {
1452: return false;
1453: }
1454: }
1455: return true;
1456: }
1457:
1458: /**
1459: * Returns the 'deep' equals for the two given arrays. This means that if
1460: * either of the arrays contains other arrays then their contents are also
1461: * checked for (deep) equality. If two corresponding elements are arrays of
1462: * a primitive type then the appropriate <code>Arrays.equals</code> method
1463: * is used to determine their equality. Otherwise for two
1464: * <code>Object</code> arrays <code>deepEquals</code> is called
1465: * recursively.
1466: *
1467: * This method should not be used if either of the arrays, or any arrays
1468: * contained within it are likely to contain a reference to itself.
1469: *
1470: * @param array1
1471: * the first Object array
1472: * @param array2
1473: * the second Object array
1474: * @return true when the arrays have the same length and the elements at
1475: * each index in the two arrays are equal, false otherwise
1476: */
1477: public static boolean deepEquals(Object[] array1, Object[] array2) {
1478: if (array1 == array2) {
1479: return true;
1480: }
1481: if (array1 == null || array2 == null
1482: || array1.length != array2.length) {
1483: return false;
1484: }
1485: for (int i = 0; i < array1.length; i++) {
1486: Object e1 = array1[i], e2 = array2[i];
1487:
1488: if (!deepEqualsElements(e1, e2)) {
1489: return false;
1490: }
1491: }
1492: return true;
1493: }
1494:
1495: private static boolean deepEqualsElements(Object e1, Object e2) {
1496: Class<?> cl1, cl2;
1497:
1498: if (e1 == e2) {
1499: return true;
1500: }
1501:
1502: if (e1 == null || e2 == null) {
1503: return false;
1504: }
1505:
1506: cl1 = e1.getClass().getComponentType();
1507: cl2 = e2.getClass().getComponentType();
1508:
1509: if (cl1 != cl2) {
1510: return false;
1511: }
1512:
1513: if (cl1 == null) {
1514: return e1.equals(e2);
1515: }
1516:
1517: /*
1518: * compare as arrays
1519: */
1520: if (!cl1.isPrimitive()) {
1521: return deepEquals((Object[]) e1, (Object[]) e2);
1522: }
1523:
1524: if (cl1.equals(int.class)) {
1525: return equals((int[]) e1, (int[]) e2);
1526: }
1527: if (cl1.equals(char.class)) {
1528: return equals((char[]) e1, (char[]) e2);
1529: }
1530: if (cl1.equals(boolean.class)) {
1531: return equals((boolean[]) e1, (boolean[]) e2);
1532: }
1533: if (cl1.equals(byte.class)) {
1534: return equals((byte[]) e1, (byte[]) e2);
1535: }
1536: if (cl1.equals(long.class)) {
1537: return equals((long[]) e1, (long[]) e2);
1538: }
1539: if (cl1.equals(float.class)) {
1540: return equals((float[]) e1, (float[]) e2);
1541: }
1542: if (cl1.equals(double.class)) {
1543: return equals((double[]) e1, (double[]) e2);
1544: }
1545: return equals((short[]) e1, (short[]) e2);
1546: }
1547:
1548: private static boolean lessThan(double double1, double double2) {
1549: long d1, d2;
1550: long NaNbits = Double.doubleToLongBits(Double.NaN);
1551: if ((d1 = Double.doubleToLongBits(double1)) == NaNbits) {
1552: return false;
1553: }
1554: if ((d2 = Double.doubleToLongBits(double2)) == NaNbits) {
1555: return true;
1556: }
1557: if (double1 == double2) {
1558: if (d1 == d2) {
1559: return false;
1560: }
1561: // check for -0
1562: return d1 < d2;
1563: }
1564: return double1 < double2;
1565: }
1566:
1567: private static boolean lessThan(float float1, float float2) {
1568: int f1, f2;
1569: int NaNbits = Float.floatToIntBits(Float.NaN);
1570: if ((f1 = Float.floatToIntBits(float1)) == NaNbits) {
1571: return false;
1572: }
1573: if ((f2 = Float.floatToIntBits(float2)) == NaNbits) {
1574: return true;
1575: }
1576: if (float1 == float2) {
1577: if (f1 == f2) {
1578: return false;
1579: }
1580: // check for -0
1581: return f1 < f2;
1582: }
1583: return float1 < float2;
1584: }
1585:
1586: private static int med3(byte[] array, int a, int b, int c) {
1587: byte x = array[a], y = array[b], z = array[c];
1588: return x < y ? (y < z ? b : (x < z ? c : a)) : (y > z ? b
1589: : (x > z ? c : a));
1590: }
1591:
1592: private static int med3(char[] array, int a, int b, int c) {
1593: char x = array[a], y = array[b], z = array[c];
1594: return x < y ? (y < z ? b : (x < z ? c : a)) : (y > z ? b
1595: : (x > z ? c : a));
1596: }
1597:
1598: private static int med3(double[] array, int a, int b, int c) {
1599: double x = array[a], y = array[b], z = array[c];
1600: return lessThan(x, y) ? (lessThan(y, z) ? b
1601: : (lessThan(x, z) ? c : a)) : (lessThan(z, y) ? b
1602: : (lessThan(z, x) ? c : a));
1603: }
1604:
1605: private static int med3(float[] array, int a, int b, int c) {
1606: float x = array[a], y = array[b], z = array[c];
1607: return lessThan(x, y) ? (lessThan(y, z) ? b
1608: : (lessThan(x, z) ? c : a)) : (lessThan(z, y) ? b
1609: : (lessThan(z, x) ? c : a));
1610: }
1611:
1612: private static int med3(int[] array, int a, int b, int c) {
1613: int x = array[a], y = array[b], z = array[c];
1614: return x < y ? (y < z ? b : (x < z ? c : a)) : (y > z ? b
1615: : (x > z ? c : a));
1616: }
1617:
1618: private static int med3(long[] array, int a, int b, int c) {
1619: long x = array[a], y = array[b], z = array[c];
1620: return x < y ? (y < z ? b : (x < z ? c : a)) : (y > z ? b
1621: : (x > z ? c : a));
1622: }
1623:
1624: private static int med3(short[] array, int a, int b, int c) {
1625: short x = array[a], y = array[b], z = array[c];
1626: return x < y ? (y < z ? b : (x < z ? c : a)) : (y > z ? b
1627: : (x > z ? c : a));
1628: }
1629:
1630: /**
1631: * Performs a sort on the given array. Elements will be re-ordered into
1632: * ascending order.
1633: *
1634: * @param array
1635: * the byte array to sort
1636: */
1637: public static void sort(byte[] array) {
1638: sort(0, array.length, array);
1639: }
1640:
1641: /**
1642: * Performs a sort on the section of the array between the given indices.
1643: * Elements will be re-ordered into ascending order.
1644: *
1645: * @param array
1646: * the byte array to sort
1647: * @param start
1648: * the start index
1649: * @param end
1650: * the end index + 1
1651: *
1652: * @exception IllegalArgumentException
1653: * when <code>start > end</code>
1654: * @exception ArrayIndexOutOfBoundsException
1655: * when <code>start < 0</code> or
1656: * <code>end > array.size()</code>
1657: */
1658: public static void sort(byte[] array, int start, int end) {
1659: if (array == null) {
1660: throw new NullPointerException();
1661: }
1662: checkBounds(array.length, start, end);
1663: sort(start, end, array);
1664: }
1665:
1666: private static void checkBounds(int arrLength, int start, int end) {
1667: if (start > end) {
1668: throw new IllegalArgumentException("start(" + start //$NON-NLS-1$
1669: + ") > end(" + end + ")"); //$NON-NLS-1$ //$NON-NLS-2$
1670: }
1671: if (start < 0 || end > arrLength) {
1672: throw new ArrayIndexOutOfBoundsException();
1673: }
1674: }
1675:
1676: private static void sort(int start, int end, byte[] array) {
1677: byte temp;
1678: int length = end - start;
1679: if (length < 7) {
1680: for (int i = start + 1; i < end; i++) {
1681: for (int j = i; j > start && array[j - 1] > array[j]; j--) {
1682: temp = array[j];
1683: array[j] = array[j - 1];
1684: array[j - 1] = temp;
1685: }
1686: }
1687: return;
1688: }
1689: int middle = (start + end) / 2;
1690: if (length > 7) {
1691: int bottom = start;
1692: int top = end - 1;
1693: if (length > 40) {
1694: length /= 8;
1695: bottom = med3(array, bottom, bottom + length, bottom
1696: + (2 * length));
1697: middle = med3(array, middle - length, middle, middle
1698: + length);
1699: top = med3(array, top - (2 * length), top - length, top);
1700: }
1701: middle = med3(array, bottom, middle, top);
1702: }
1703: byte partionValue = array[middle];
1704: int a, b, c, d;
1705: a = b = start;
1706: c = d = end - 1;
1707: while (true) {
1708: while (b <= c && array[b] <= partionValue) {
1709: if (array[b] == partionValue) {
1710: temp = array[a];
1711: array[a++] = array[b];
1712: array[b] = temp;
1713: }
1714: b++;
1715: }
1716: while (c >= b && array[c] >= partionValue) {
1717: if (array[c] == partionValue) {
1718: temp = array[c];
1719: array[c] = array[d];
1720: array[d--] = temp;
1721: }
1722: c--;
1723: }
1724: if (b > c) {
1725: break;
1726: }
1727: temp = array[b];
1728: array[b++] = array[c];
1729: array[c--] = temp;
1730: }
1731: length = a - start < b - a ? a - start : b - a;
1732: int l = start;
1733: int h = b - length;
1734: while (length-- > 0) {
1735: temp = array[l];
1736: array[l++] = array[h];
1737: array[h++] = temp;
1738: }
1739: length = d - c < end - 1 - d ? d - c : end - 1 - d;
1740: l = b;
1741: h = end - length;
1742: while (length-- > 0) {
1743: temp = array[l];
1744: array[l++] = array[h];
1745: array[h++] = temp;
1746: }
1747: if ((length = b - a) > 0) {
1748: sort(start, start + length, array);
1749: }
1750: if ((length = d - c) > 0) {
1751: sort(end - length, end, array);
1752: }
1753: }
1754:
1755: /**
1756: * Performs a sort on the given array. Elements will be re-ordered into
1757: * ascending order.
1758: *
1759: * @param array
1760: * the char array to sort
1761: */
1762: public static void sort(char[] array) {
1763: sort(0, array.length, array);
1764: }
1765:
1766: /**
1767: * Performs a sort on the section of the array between the given indices.
1768: * Elements will be re-ordered into ascending order.
1769: *
1770: * @param array
1771: * the char array to sort
1772: * @param start
1773: * the start index
1774: * @param end
1775: * the end index + 1
1776: *
1777: * @exception IllegalArgumentException
1778: * when <code>start > end</code>
1779: * @exception ArrayIndexOutOfBoundsException
1780: * when <code>start < 0</code> or
1781: * <code>end > array.size()</code>
1782: */
1783: public static void sort(char[] array, int start, int end) {
1784: if (array == null) {
1785: throw new NullPointerException();
1786: }
1787: checkBounds(array.length, start, end);
1788: sort(start, end, array);
1789: }
1790:
1791: private static void sort(int start, int end, char[] array) {
1792: char temp;
1793: int length = end - start;
1794: if (length < 7) {
1795: for (int i = start + 1; i < end; i++) {
1796: for (int j = i; j > start && array[j - 1] > array[j]; j--) {
1797: temp = array[j];
1798: array[j] = array[j - 1];
1799: array[j - 1] = temp;
1800: }
1801: }
1802: return;
1803: }
1804: int middle = (start + end) / 2;
1805: if (length > 7) {
1806: int bottom = start;
1807: int top = end - 1;
1808: if (length > 40) {
1809: length /= 8;
1810: bottom = med3(array, bottom, bottom + length, bottom
1811: + (2 * length));
1812: middle = med3(array, middle - length, middle, middle
1813: + length);
1814: top = med3(array, top - (2 * length), top - length, top);
1815: }
1816: middle = med3(array, bottom, middle, top);
1817: }
1818: char partionValue = array[middle];
1819: int a, b, c, d;
1820: a = b = start;
1821: c = d = end - 1;
1822: while (true) {
1823: while (b <= c && array[b] <= partionValue) {
1824: if (array[b] == partionValue) {
1825: temp = array[a];
1826: array[a++] = array[b];
1827: array[b] = temp;
1828: }
1829: b++;
1830: }
1831: while (c >= b && array[c] >= partionValue) {
1832: if (array[c] == partionValue) {
1833: temp = array[c];
1834: array[c] = array[d];
1835: array[d--] = temp;
1836: }
1837: c--;
1838: }
1839: if (b > c) {
1840: break;
1841: }
1842: temp = array[b];
1843: array[b++] = array[c];
1844: array[c--] = temp;
1845: }
1846: length = a - start < b - a ? a - start : b - a;
1847: int l = start;
1848: int h = b - length;
1849: while (length-- > 0) {
1850: temp = array[l];
1851: array[l++] = array[h];
1852: array[h++] = temp;
1853: }
1854: length = d - c < end - 1 - d ? d - c : end - 1 - d;
1855: l = b;
1856: h = end - length;
1857: while (length-- > 0) {
1858: temp = array[l];
1859: array[l++] = array[h];
1860: array[h++] = temp;
1861: }
1862: if ((length = b - a) > 0) {
1863: sort(start, start + length, array);
1864: }
1865: if ((length = d - c) > 0) {
1866: sort(end - length, end, array);
1867: }
1868: }
1869:
1870: /**
1871: * Performs a sort on the given array. Elements will be re-ordered into
1872: * ascending order.
1873: *
1874: * @param array
1875: * the double array to sort
1876: *
1877: * @see #sort(double[], int, int)
1878: */
1879: public static void sort(double[] array) {
1880: sort(0, array.length, array);
1881: }
1882:
1883: /**
1884: * Performs a sort on the section of the array between the given indices.
1885: * Elements will be re-ordered into ascending order.
1886: *
1887: * @param array
1888: * the double array to sort
1889: * @param start
1890: * the start index
1891: * @param end
1892: * the end index + 1
1893: *
1894: * @exception IllegalArgumentException
1895: * when <code>start > end</code>
1896: * @exception ArrayIndexOutOfBoundsException
1897: * when <code>start < 0</code> or
1898: * <code>end > array.size()</code>
1899: *
1900: * @see Double#compareTo(Double)
1901: */
1902: public static void sort(double[] array, int start, int end) {
1903: if (array == null) {
1904: throw new NullPointerException();
1905: }
1906: checkBounds(array.length, start, end);
1907: sort(start, end, array);
1908: }
1909:
1910: private static void sort(int start, int end, double[] array) {
1911: double temp;
1912: int length = end - start;
1913: if (length < 7) {
1914: for (int i = start + 1; i < end; i++) {
1915: for (int j = i; j > start
1916: && lessThan(array[j], array[j - 1]); j--) {
1917: temp = array[j];
1918: array[j] = array[j - 1];
1919: array[j - 1] = temp;
1920: }
1921: }
1922: return;
1923: }
1924: int middle = (start + end) / 2;
1925: if (length > 7) {
1926: int bottom = start;
1927: int top = end - 1;
1928: if (length > 40) {
1929: length /= 8;
1930: bottom = med3(array, bottom, bottom + length, bottom
1931: + (2 * length));
1932: middle = med3(array, middle - length, middle, middle
1933: + length);
1934: top = med3(array, top - (2 * length), top - length, top);
1935: }
1936: middle = med3(array, bottom, middle, top);
1937: }
1938: double partionValue = array[middle];
1939: int a, b, c, d;
1940: a = b = start;
1941: c = d = end - 1;
1942: while (true) {
1943: while (b <= c && !lessThan(partionValue, array[b])) {
1944: if (array[b] == partionValue) {
1945: temp = array[a];
1946: array[a++] = array[b];
1947: array[b] = temp;
1948: }
1949: b++;
1950: }
1951: while (c >= b && !lessThan(array[c], partionValue)) {
1952: if (array[c] == partionValue) {
1953: temp = array[c];
1954: array[c] = array[d];
1955: array[d--] = temp;
1956: }
1957: c--;
1958: }
1959: if (b > c) {
1960: break;
1961: }
1962: temp = array[b];
1963: array[b++] = array[c];
1964: array[c--] = temp;
1965: }
1966: length = a - start < b - a ? a - start : b - a;
1967: int l = start;
1968: int h = b - length;
1969: while (length-- > 0) {
1970: temp = array[l];
1971: array[l++] = array[h];
1972: array[h++] = temp;
1973: }
1974: length = d - c < end - 1 - d ? d - c : end - 1 - d;
1975: l = b;
1976: h = end - length;
1977: while (length-- > 0) {
1978: temp = array[l];
1979: array[l++] = array[h];
1980: array[h++] = temp;
1981: }
1982: if ((length = b - a) > 0) {
1983: sort(start, start + length, array);
1984: }
1985: if ((length = d - c) > 0) {
1986: sort(end - length, end, array);
1987: }
1988: }
1989:
1990: /**
1991: * Performs a sort on the given array. Elements will be re-ordered into
1992: * ascending order.
1993: *
1994: * @param array
1995: * the float array to sort
1996: *
1997: * @see #sort(float[], int, int)
1998: */
1999: public static void sort(float[] array) {
2000: sort(0, array.length, array);
2001: }
2002:
2003: /**
2004: * Performs a sort on the section of the array between the given indices.
2005: * Elements will be re-ordered into ascending order.
2006: *
2007: * @param array
2008: * the float array to sort
2009: * @param start
2010: * the start index
2011: * @param end
2012: * the end index + 1
2013: *
2014: * @exception IllegalArgumentException
2015: * when <code>start > end</code>
2016: * @exception ArrayIndexOutOfBoundsException
2017: * when <code>start < 0</code> or
2018: * <code>end > array.size()</code>
2019: *
2020: * @see Float#compareTo(Float)
2021: */
2022: public static void sort(float[] array, int start, int end) {
2023: if (array == null) {
2024: throw new NullPointerException();
2025: }
2026: checkBounds(array.length, start, end);
2027: sort(start, end, array);
2028: }
2029:
2030: private static void sort(int start, int end, float[] array) {
2031: float temp;
2032: int length = end - start;
2033: if (length < 7) {
2034: for (int i = start + 1; i < end; i++) {
2035: for (int j = i; j > start
2036: && lessThan(array[j], array[j - 1]); j--) {
2037: temp = array[j];
2038: array[j] = array[j - 1];
2039: array[j - 1] = temp;
2040: }
2041: }
2042: return;
2043: }
2044: int middle = (start + end) / 2;
2045: if (length > 7) {
2046: int bottom = start;
2047: int top = end - 1;
2048: if (length > 40) {
2049: length /= 8;
2050: bottom = med3(array, bottom, bottom + length, bottom
2051: + (2 * length));
2052: middle = med3(array, middle - length, middle, middle
2053: + length);
2054: top = med3(array, top - (2 * length), top - length, top);
2055: }
2056: middle = med3(array, bottom, middle, top);
2057: }
2058: float partionValue = array[middle];
2059: int a, b, c, d;
2060: a = b = start;
2061: c = d = end - 1;
2062: while (true) {
2063: while (b <= c && !lessThan(partionValue, array[b])) {
2064: if (array[b] == partionValue) {
2065: temp = array[a];
2066: array[a++] = array[b];
2067: array[b] = temp;
2068: }
2069: b++;
2070: }
2071: while (c >= b && !lessThan(array[c], partionValue)) {
2072: if (array[c] == partionValue) {
2073: temp = array[c];
2074: array[c] = array[d];
2075: array[d--] = temp;
2076: }
2077: c--;
2078: }
2079: if (b > c) {
2080: break;
2081: }
2082: temp = array[b];
2083: array[b++] = array[c];
2084: array[c--] = temp;
2085: }
2086: length = a - start < b - a ? a - start : b - a;
2087: int l = start;
2088: int h = b - length;
2089: while (length-- > 0) {
2090: temp = array[l];
2091: array[l++] = array[h];
2092: array[h++] = temp;
2093: }
2094: length = d - c < end - 1 - d ? d - c : end - 1 - d;
2095: l = b;
2096: h = end - length;
2097: while (length-- > 0) {
2098: temp = array[l];
2099: array[l++] = array[h];
2100: array[h++] = temp;
2101: }
2102: if ((length = b - a) > 0) {
2103: sort(start, start + length, array);
2104: }
2105: if ((length = d - c) > 0) {
2106: sort(end - length, end, array);
2107: }
2108: }
2109:
2110: /**
2111: * Performs a sort on the given array. Elements will be re-ordered into
2112: * ascending order.
2113: *
2114: * @param array
2115: * the int array to sort
2116: */
2117: public static void sort(int[] array) {
2118: sort(0, array.length, array);
2119: }
2120:
2121: /**
2122: * Performs a sort on the section of the array between the given indices.
2123: * Elements will be re-ordered into ascending order.
2124: *
2125: * @param array
2126: * the int array to sort
2127: * @param start
2128: * the start index
2129: * @param end
2130: * the end index + 1
2131: *
2132: * @exception IllegalArgumentException
2133: * when <code>start > end</code>
2134: * @exception ArrayIndexOutOfBoundsException
2135: * when <code>start < 0</code> or
2136: * <code>end > array.size()</code>
2137: */
2138: public static void sort(int[] array, int start, int end) {
2139: if (array == null) {
2140: throw new NullPointerException();
2141: }
2142: checkBounds(array.length, start, end);
2143: sort(start, end, array);
2144: }
2145:
2146: private static void sort(int start, int end, int[] array) {
2147: int temp;
2148: int length = end - start;
2149: if (length < 7) {
2150: for (int i = start + 1; i < end; i++) {
2151: for (int j = i; j > start && array[j - 1] > array[j]; j--) {
2152: temp = array[j];
2153: array[j] = array[j - 1];
2154: array[j - 1] = temp;
2155: }
2156: }
2157: return;
2158: }
2159: int middle = (start + end) / 2;
2160: if (length > 7) {
2161: int bottom = start;
2162: int top = end - 1;
2163: if (length > 40) {
2164: length /= 8;
2165: bottom = med3(array, bottom, bottom + length, bottom
2166: + (2 * length));
2167: middle = med3(array, middle - length, middle, middle
2168: + length);
2169: top = med3(array, top - (2 * length), top - length, top);
2170: }
2171: middle = med3(array, bottom, middle, top);
2172: }
2173: int partionValue = array[middle];
2174: int a, b, c, d;
2175: a = b = start;
2176: c = d = end - 1;
2177: while (true) {
2178: while (b <= c && array[b] <= partionValue) {
2179: if (array[b] == partionValue) {
2180: temp = array[a];
2181: array[a++] = array[b];
2182: array[b] = temp;
2183: }
2184: b++;
2185: }
2186: while (c >= b && array[c] >= partionValue) {
2187: if (array[c] == partionValue) {
2188: temp = array[c];
2189: array[c] = array[d];
2190: array[d--] = temp;
2191: }
2192: c--;
2193: }
2194: if (b > c) {
2195: break;
2196: }
2197: temp = array[b];
2198: array[b++] = array[c];
2199: array[c--] = temp;
2200: }
2201: length = a - start < b - a ? a - start : b - a;
2202: int l = start;
2203: int h = b - length;
2204: while (length-- > 0) {
2205: temp = array[l];
2206: array[l++] = array[h];
2207: array[h++] = temp;
2208: }
2209: length = d - c < end - 1 - d ? d - c : end - 1 - d;
2210: l = b;
2211: h = end - length;
2212: while (length-- > 0) {
2213: temp = array[l];
2214: array[l++] = array[h];
2215: array[h++] = temp;
2216: }
2217: if ((length = b - a) > 0) {
2218: sort(start, start + length, array);
2219: }
2220: if ((length = d - c) > 0) {
2221: sort(end - length, end, array);
2222: }
2223: }
2224:
2225: /**
2226: * Performs a sort on given array. Elements will be re-ordered into
2227: * ascending order.
2228: *
2229: * @param array
2230: * the long array to sort
2231: */
2232: public static void sort(long[] array) {
2233: sort(0, array.length, array);
2234: }
2235:
2236: /**
2237: * Performs a sort on the section of the array between the given indices.
2238: * Elements will be re-ordered into ascending order.
2239: *
2240: * @param array
2241: * the long array to sort
2242: * @param start
2243: * the start index
2244: * @param end
2245: * the end index + 1
2246: *
2247: * @exception IllegalArgumentException
2248: * when <code>start > end</code>
2249: * @exception ArrayIndexOutOfBoundsException
2250: * when <code>start < 0</code> or
2251: * <code>end > array.size()</code>
2252: */
2253: public static void sort(long[] array, int start, int end) {
2254: if (array == null) {
2255: throw new NullPointerException();
2256: }
2257: checkBounds(array.length, start, end);
2258: sort(start, end, array);
2259: }
2260:
2261: private static void sort(int start, int end, long[] array) {
2262: long temp;
2263: int length = end - start;
2264: if (length < 7) {
2265: for (int i = start + 1; i < end; i++) {
2266: for (int j = i; j > start && array[j - 1] > array[j]; j--) {
2267: temp = array[j];
2268: array[j] = array[j - 1];
2269: array[j - 1] = temp;
2270: }
2271: }
2272: return;
2273: }
2274: int middle = (start + end) / 2;
2275: if (length > 7) {
2276: int bottom = start;
2277: int top = end - 1;
2278: if (length > 40) {
2279: length /= 8;
2280: bottom = med3(array, bottom, bottom + length, bottom
2281: + (2 * length));
2282: middle = med3(array, middle - length, middle, middle
2283: + length);
2284: top = med3(array, top - (2 * length), top - length, top);
2285: }
2286: middle = med3(array, bottom, middle, top);
2287: }
2288: long partionValue = array[middle];
2289: int a, b, c, d;
2290: a = b = start;
2291: c = d = end - 1;
2292: while (true) {
2293: while (b <= c && array[b] <= partionValue) {
2294: if (array[b] == partionValue) {
2295: temp = array[a];
2296: array[a++] = array[b];
2297: array[b] = temp;
2298: }
2299: b++;
2300: }
2301: while (c >= b && array[c] >= partionValue) {
2302: if (array[c] == partionValue) {
2303: temp = array[c];
2304: array[c] = array[d];
2305: array[d--] = temp;
2306: }
2307: c--;
2308: }
2309: if (b > c) {
2310: break;
2311: }
2312: temp = array[b];
2313: array[b++] = array[c];
2314: array[c--] = temp;
2315: }
2316: length = a - start < b - a ? a - start : b - a;
2317: int l = start;
2318: int h = b - length;
2319: while (length-- > 0) {
2320: temp = array[l];
2321: array[l++] = array[h];
2322: array[h++] = temp;
2323: }
2324: length = d - c < end - 1 - d ? d - c : end - 1 - d;
2325: l = b;
2326: h = end - length;
2327: while (length-- > 0) {
2328: temp = array[l];
2329: array[l++] = array[h];
2330: array[h++] = temp;
2331: }
2332: if ((length = b - a) > 0) {
2333: sort(start, start + length, array);
2334: }
2335: if ((length = d - c) > 0) {
2336: sort(end - length, end, array);
2337: }
2338: }
2339:
2340: /**
2341: * Performs a sort on the given array. Elements will be re-ordered into
2342: * ascending order.
2343: *
2344: * @param array
2345: * the Object array to sort
2346: *
2347: * @exception ClassCastException
2348: * when an element in the array does not implement Comparable
2349: * or elements cannot be compared to each other
2350: */
2351: public static void sort(Object[] array) {
2352: sort(0, array.length, array);
2353: }
2354:
2355: /**
2356: * Performs a sort on the section of the array between the given indices.
2357: * Elements will be re-ordered into ascending order.
2358: *
2359: * @param array
2360: * the Object array to sort
2361: * @param start
2362: * the start index
2363: * @param end
2364: * the end index + 1
2365: *
2366: * @exception ClassCastException
2367: * when an element in the array does not implement <code>Comparable</code>
2368: * or elements cannot be compared to each other
2369: * @exception IllegalArgumentException
2370: * when <code>start > end</code>
2371: * @exception ArrayIndexOutOfBoundsException
2372: * when <code>start < 0</code> or
2373: * <code>end > array.size()</code>
2374: */
2375: public static void sort(Object[] array, int start, int end) {
2376: if (array == null) {
2377: throw new NullPointerException();
2378: }
2379: checkBounds(array.length, start, end);
2380: sort(start, end, array);
2381: }
2382:
2383: private static void sort(int start, int end, Object[] array) {
2384: int length = end - start;
2385: if (length <= 0) {
2386: return;
2387: }
2388: if (array instanceof String[]) {
2389: stableStringSort((String[]) array, start, end);
2390: } else {
2391: Object[] out = new Object[end];
2392: System.arraycopy(array, start, out, start, length);
2393: mergeSort(out, array, start, end);
2394: }
2395: }
2396:
2397: /**
2398: * Swaps the elements at the given indices in the array.
2399: *
2400: * @param a -
2401: * the index of one element to be swapped.
2402: * @param b -
2403: * the index of the other element to be swapped.
2404: * @param arr -
2405: * the array in which to swap elements.
2406: */
2407: private static void swap(int a, int b, Object[] arr) {
2408: Object tmp = arr[a];
2409: arr[a] = arr[b];
2410: arr[b] = tmp;
2411: }
2412:
2413: /**
2414: * Performs a sort on the section of the array between the given indices
2415: * using a mergesort with exponential search algorithm (in which the merge
2416: * is performed by exponential search). n*log(n) performance is guaranteed
2417: * and in the average case it will be faster then any mergesort in which the
2418: * merge is performed by linear search.
2419: *
2420: * @param in -
2421: * the array for sorting.
2422: * @param out -
2423: * the result, sorted array.
2424: * @param start
2425: * the start index
2426: * @param end
2427: * the end index + 1
2428: */
2429: @SuppressWarnings("unchecked")
2430: private static void mergeSort(Object[] in, Object[] out, int start,
2431: int end) {
2432: int len = end - start;
2433: // use insertion sort for small arrays
2434: if (len <= SIMPLE_LENGTH) {
2435: for (int i = start + 1; i < end; i++) {
2436: Comparable<Object> current = (Comparable<Object>) out[i];
2437: Object prev = out[i - 1];
2438: if (current.compareTo(prev) < 0) {
2439: int j = i;
2440: do {
2441: out[j--] = prev;
2442: } while (j > start
2443: && current.compareTo(prev = out[j - 1]) < 0);
2444: out[j] = current;
2445: }
2446: }
2447: return;
2448: }
2449: int med = (end + start) >>> 1;
2450: mergeSort(out, in, start, med);
2451: mergeSort(out, in, med, end);
2452:
2453: // merging
2454:
2455: // if arrays are already sorted - no merge
2456: if (((Comparable<Object>) in[med - 1]).compareTo(in[med]) <= 0) {
2457: System.arraycopy(in, start, out, start, len);
2458: return;
2459: }
2460: int r = med, i = start;
2461:
2462: // use merging with exponential search
2463: do {
2464: Comparable<Object> fromVal = (Comparable<Object>) in[start];
2465: Comparable<Object> rVal = (Comparable<Object>) in[r];
2466: if (fromVal.compareTo(rVal) <= 0) {
2467: int l_1 = find(in, rVal, -1, start + 1, med - 1);
2468: int toCopy = l_1 - start + 1;
2469: System.arraycopy(in, start, out, i, toCopy);
2470: i += toCopy;
2471: out[i++] = rVal;
2472: r++;
2473: start = l_1 + 1;
2474: } else {
2475: int r_1 = find(in, fromVal, 0, r + 1, end - 1);
2476: int toCopy = r_1 - r + 1;
2477: System.arraycopy(in, r, out, i, toCopy);
2478: i += toCopy;
2479: out[i++] = fromVal;
2480: start++;
2481: r = r_1 + 1;
2482: }
2483: } while ((end - r) > 0 && (med - start) > 0);
2484:
2485: // copy rest of array
2486: if ((end - r) <= 0) {
2487: System.arraycopy(in, start, out, i, med - start);
2488: } else {
2489: System.arraycopy(in, r, out, i, end - r);
2490: }
2491: }
2492:
2493: /**
2494: * Performs a sort on the section of the array between the given indices
2495: * using a mergesort with exponential search algorithm (in which the merge
2496: * is performed by exponential search). n*log(n) performance is guaranteed
2497: * and in the average case it will be faster then any mergesort in which the
2498: * merge is performed by linear search.
2499: *
2500: * @param in -
2501: * the array for sorting.
2502: * @param out -
2503: * the result, sorted array.
2504: * @param start
2505: * the start index
2506: * @param end
2507: * the end index + 1
2508: * @param c -
2509: * the comparator to determine the order of the array.
2510: */
2511: @SuppressWarnings("unchecked")
2512: private static void mergeSort(Object[] in, Object[] out, int start,
2513: int end, Comparator c) {
2514: int len = end - start;
2515: // use insertion sort for small arrays
2516: if (len <= SIMPLE_LENGTH) {
2517: for (int i = start + 1; i < end; i++) {
2518: Object current = out[i];
2519: Object prev = out[i - 1];
2520: if (c.compare(prev, current) > 0) {
2521: int j = i;
2522: do {
2523: out[j--] = prev;
2524: } while (j > start
2525: && (c.compare(prev = out[j - 1], current) > 0));
2526: out[j] = current;
2527: }
2528: }
2529: return;
2530: }
2531: int med = (end + start) >>> 1;
2532: mergeSort(out, in, start, med, c);
2533: mergeSort(out, in, med, end, c);
2534:
2535: // merging
2536:
2537: // if arrays are already sorted - no merge
2538: if (c.compare(in[med - 1], in[med]) <= 0) {
2539: System.arraycopy(in, start, out, start, len);
2540: return;
2541: }
2542: int r = med, i = start;
2543:
2544: // use merging with exponential search
2545: do {
2546: Object fromVal = in[start];
2547: Object rVal = in[r];
2548: if (c.compare(fromVal, rVal) <= 0) {
2549: int l_1 = find(in, rVal, -1, start + 1, med - 1, c);
2550: int toCopy = l_1 - start + 1;
2551: System.arraycopy(in, start, out, i, toCopy);
2552: i += toCopy;
2553: out[i++] = rVal;
2554: r++;
2555: start = l_1 + 1;
2556: } else {
2557: int r_1 = find(in, fromVal, 0, r + 1, end - 1, c);
2558: int toCopy = r_1 - r + 1;
2559: System.arraycopy(in, r, out, i, toCopy);
2560: i += toCopy;
2561: out[i++] = fromVal;
2562: start++;
2563: r = r_1 + 1;
2564: }
2565: } while ((end - r) > 0 && (med - start) > 0);
2566:
2567: // copy rest of array
2568: if ((end - r) <= 0) {
2569: System.arraycopy(in, start, out, i, med - start);
2570: } else {
2571: System.arraycopy(in, r, out, i, end - r);
2572: }
2573: }
2574:
2575: /**
2576: * Finds the place in the given range of specified sorted array, where the
2577: * element should be inserted for getting sorted array. Uses exponential
2578: * search algorithm.
2579: *
2580: * @param arr -
2581: * the array with already sorted range
2582: *
2583: * @param val -
2584: * object to be inserted
2585: *
2586: * @param l -
2587: * the start index
2588: *
2589: * @param r -
2590: * the end index
2591: *
2592: * @param bnd -
2593: * possible values 0,-1. "-1" - val is located at index more then
2594: * elements equals to val. "0" - val is located at index less
2595: * then elements equals to val.
2596: *
2597: */
2598: @SuppressWarnings("unchecked")
2599: private static int find(Object[] arr, Comparable val, int bnd,
2600: int l, int r) {
2601: int m = l;
2602: int d = 1;
2603: while (m <= r) {
2604: if (val.compareTo(arr[m]) > bnd) {
2605: l = m + 1;
2606: } else {
2607: r = m - 1;
2608: break;
2609: }
2610: m += d;
2611: d <<= 1;
2612: }
2613: while (l <= r) {
2614: m = (l + r) >>> 1;
2615: if (val.compareTo(arr[m]) > bnd) {
2616: l = m + 1;
2617: } else {
2618: r = m - 1;
2619: }
2620: }
2621: return l - 1;
2622: }
2623:
2624: /**
2625: * Finds the place of specified range of specified sorted array, where the
2626: * element should be inserted for getting sorted array. Uses exponential
2627: * search algorithm.
2628: *
2629: * @param arr -
2630: * the array with already sorted range
2631: * @param val -
2632: * object to be inserted
2633: * @param l -
2634: * the start index
2635: * @param r -
2636: * the end index
2637: * @param bnd -
2638: * possible values 0,-1. "-1" - val is located at index more then
2639: * elements equals to val. "0" - val is located at index less
2640: * then elements equals to val.
2641: * @param c -
2642: * the comparator used to compare Objects
2643: */
2644: @SuppressWarnings("unchecked")
2645: private static int find(Object[] arr, Object val, int bnd, int l,
2646: int r, Comparator c) {
2647: int m = l;
2648: int d = 1;
2649: while (m <= r) {
2650: if (c.compare(val, arr[m]) > bnd) {
2651: l = m + 1;
2652: } else {
2653: r = m - 1;
2654: break;
2655: }
2656: m += d;
2657: d <<= 1;
2658: }
2659: while (l <= r) {
2660: m = (l + r) >>> 1;
2661: if (c.compare(val, arr[m]) > bnd) {
2662: l = m + 1;
2663: } else {
2664: r = m - 1;
2665: }
2666: }
2667: return l - 1;
2668: }
2669:
2670: /*
2671: * returns the median index.
2672: */
2673: private static int medChar(int a, int b, int c, String[] arr, int id) {
2674: int ac = charAt(arr[a], id);
2675: int bc = charAt(arr[b], id);
2676: int cc = charAt(arr[c], id);
2677: return ac < bc ? (bc < cc ? b : (ac < cc ? c : a))
2678: : (bc < cc ? (ac < cc ? a : c) : b);
2679:
2680: }
2681:
2682: /*
2683: * Returns the char value at the specified index of string or -1 if the
2684: * index more than the length of this string.
2685: */
2686: private static int charAt(String str, int i) {
2687: if (i >= str.length()) {
2688: return -1;
2689: }
2690: return str.charAt(i);
2691: }
2692:
2693: /**
2694: * Copies object from one array to another array with reverse of objects
2695: * order. Source and destination arrays may be the same.
2696: *
2697: * @param src -
2698: * the source array.
2699: * @param from -
2700: * starting position in the source array.
2701: * @param dst -
2702: * the destination array.
2703: * @param to -
2704: * starting position in the destination array.
2705: * @param len -
2706: * the number of array elements to be copied.
2707: */
2708: private static void copySwap(Object[] src, int from, Object[] dst,
2709: int to, int len) {
2710: if (src == dst && from + len > to) {
2711: int new_to = to + len - 1;
2712: for (; from < to; from++, new_to--, len--) {
2713: dst[new_to] = src[from];
2714: }
2715: for (; len > 1; from++, new_to--, len -= 2) {
2716: swap(from, new_to, dst);
2717: }
2718:
2719: } else {
2720: to = to + len - 1;
2721: for (; len > 0; from++, to--, len--) {
2722: dst[to] = src[from];
2723: }
2724: }
2725: }
2726:
2727: /**
2728: * Performs a sort on the given String array. Elements will be re-ordered into
2729: * ascending order.
2730: *
2731: * @param arr -
2732: * the array to sort
2733: * @param start -
2734: * the start index
2735: * @param end -
2736: * the end index + 1
2737: */
2738: private static void stableStringSort(String[] arr, int start,
2739: int end) {
2740: stableStringSort(arr, arr, new String[end], start, end, 0);
2741: }
2742:
2743: /**
2744: * Performs a sort on the given String array. Elements will be re-ordered into
2745: * ascending order. Uses a stable ternary quick sort algorithm.
2746: *
2747: * @param arr -
2748: * the array to sort
2749: * @param src -
2750: * auxiliary array
2751: * @param dst -
2752: * auxiliary array
2753: * @param start -
2754: * the start index
2755: * @param end -
2756: * the end index + 1
2757: * @param chId -
2758: * index of char for current sorting
2759: */
2760: private static void stableStringSort(String[] arr, String[] src,
2761: String[] dst, int start, int end, int chId) {
2762: int length = end - start;
2763: // use insertion sort for small arrays
2764: if (length < SIMPLE_LENGTH) {
2765: if (src == arr) {
2766: for (int i = start + 1; i < end; i++) {
2767: String current = arr[i];
2768: String prev = arr[i - 1];
2769: if (current.compareTo(prev) < 0) {
2770: int j = i;
2771: do {
2772: arr[j--] = prev;
2773: } while (j > start
2774: && current.compareTo(prev = arr[j - 1]) < 0);
2775: arr[j] = current;
2776: }
2777: }
2778: } else {
2779: int actualEnd = end - 1;
2780: dst[start] = src[actualEnd--];
2781: for (int i = start + 1; i < end; i++, actualEnd--) {
2782: String current = src[actualEnd];
2783: String prev;
2784: int j = i;
2785: while (j > start
2786: && current.compareTo(prev = dst[j - 1]) < 0) {
2787: dst[j--] = prev;
2788: }
2789: dst[j] = current;
2790: }
2791: }
2792: return;
2793: }
2794: // Approximate median
2795: int s;
2796: int mid = start + length / 2;
2797: int lo = start;
2798: int hi = end - 1;
2799: if (length > 40) {
2800: s = length / 8;
2801: lo = medChar(lo, lo + s, lo + s * 2, src, chId);
2802: mid = medChar(mid - s, mid, mid + s, src, chId);
2803: hi = medChar(hi, hi - s, hi - s * 2, src, chId);
2804: }
2805: mid = medChar(lo, mid, hi, src, chId);
2806: // median found
2807: // create 4 pointers <a (in star of src) ,
2808: // =b(in start of dst), >c (in end of dst)
2809: // i - current element;
2810: int midVal = charAt(src[mid], chId);
2811: int a, b, c;
2812: a = b = start;
2813: c = end - 1;
2814: int cmp;
2815:
2816: for (int i = start; i < end; i++) {
2817: String el = src[i];
2818: cmp = charAt(el, chId) - midVal;
2819: if (cmp < 0) {
2820: src[a] = el;
2821: a++;
2822: } else if (cmp > 0) {
2823: dst[c] = el;
2824: c--;
2825: } else {
2826: dst[b] = el;
2827: b++;
2828: }
2829: }
2830:
2831: s = b - start;
2832: if (s > 0) {
2833: if (arr == src) {
2834: System.arraycopy(dst, start, arr, a, s);
2835: } else {
2836: copySwap(dst, start, arr, a, s);
2837: }
2838:
2839: if (b >= end && midVal == -1) {
2840: return;
2841: }
2842: stableStringSort(arr, arr, arr == dst ? src : dst, a,
2843: a + s, chId + 1);
2844: }
2845:
2846: s = a - start;
2847: if (s > 0) {
2848: stableStringSort(arr, src, dst, start, a, chId);
2849: }
2850:
2851: c++;
2852: s = end - c;
2853: if (s > 0) {
2854: stableStringSort(arr, dst, src, c, end, chId);
2855: }
2856: }
2857:
2858: /**
2859: * Performs a sort on the section of the array between the given indices.
2860: * Elements will be re-ordered into ascending order according to the given
2861: * Comparator.
2862: *
2863: * @param array
2864: * the Object array to sort
2865: * @param start
2866: * the start index
2867: * @param end
2868: * the end index + 1
2869: * @param comparator
2870: * the Comparator
2871: *
2872: * @exception ClassCastException
2873: * when elements in the array cannot be compared to each
2874: * other using the Comparator
2875: * @exception IllegalArgumentException
2876: * when <code>start > end</code>
2877: * @exception ArrayIndexOutOfBoundsException
2878: * when <code>start < 0</code> or
2879: * <code>end > array.size()</code>
2880: */
2881: public static <T> void sort(T[] array, int start, int end,
2882: Comparator<? super T> comparator) {
2883: if (array == null) {
2884: throw new NullPointerException();
2885: }
2886: checkBounds(array.length, start, end);
2887: sort(start, end, array, comparator);
2888: }
2889:
2890: private static <T> void sort(int start, int end, T[] array,
2891: Comparator<? super T> comparator) {
2892: if (comparator == null) {
2893: sort(start, end, array);
2894: } else {
2895: int length = end - start;
2896: Object[] out = new Object[end];
2897: System.arraycopy(array, start, out, start, length);
2898: mergeSort(out, array, start, end, comparator);
2899: }
2900: }
2901:
2902: /**
2903: * Performs a sort on the given array. Elements will be re-ordered into
2904: * ascending order according to the given Comparator.
2905: *
2906: * @param array
2907: * the Object array to sort
2908: * @param comparator
2909: * the Comparator
2910: *
2911: * @exception ClassCastException
2912: * when elements in the array cannot be compared to each
2913: * other using the Comparator
2914: */
2915: public static <T> void sort(T[] array,
2916: Comparator<? super T> comparator) {
2917: sort(0, array.length, array, comparator);
2918: }
2919:
2920: /**
2921: * Performs a sort on the given array. Elements will be re-ordered into
2922: * ascending order.
2923: *
2924: * @param array
2925: * the short array to sort
2926: */
2927: public static void sort(short[] array) {
2928: sort(0, array.length, array);
2929: }
2930:
2931: /**
2932: * Performs a sort on the given array. Elements will be re-ordered into
2933: * ascending order.
2934: *
2935: * @param array
2936: * the short array to sort
2937: * @param start
2938: * the start index
2939: * @param end
2940: * the end index + 1
2941: *
2942: * @exception IllegalArgumentException
2943: * when <code>start > end</code>
2944: * @exception ArrayIndexOutOfBoundsException
2945: * when <code>start < 0</code> or
2946: * <code>end > array.size()</code>
2947: */
2948: public static void sort(short[] array, int start, int end) {
2949: if (array == null) {
2950: throw new NullPointerException();
2951: }
2952: checkBounds(array.length, start, end);
2953: sort(start, end, array);
2954: }
2955:
2956: private static void sort(int start, int end, short[] array) {
2957: short temp;
2958: int length = end - start;
2959: if (length < 7) {
2960: for (int i = start + 1; i < end; i++) {
2961: for (int j = i; j > start && array[j - 1] > array[j]; j--) {
2962: temp = array[j];
2963: array[j] = array[j - 1];
2964: array[j - 1] = temp;
2965: }
2966: }
2967: return;
2968: }
2969: int middle = (start + end) / 2;
2970: if (length > 7) {
2971: int bottom = start;
2972: int top = end - 1;
2973: if (length > 40) {
2974: length /= 8;
2975: bottom = med3(array, bottom, bottom + length, bottom
2976: + (2 * length));
2977: middle = med3(array, middle - length, middle, middle
2978: + length);
2979: top = med3(array, top - (2 * length), top - length, top);
2980: }
2981: middle = med3(array, bottom, middle, top);
2982: }
2983: short partionValue = array[middle];
2984: int a, b, c, d;
2985: a = b = start;
2986: c = d = end - 1;
2987: while (true) {
2988: while (b <= c && array[b] <= partionValue) {
2989: if (array[b] == partionValue) {
2990: temp = array[a];
2991: array[a++] = array[b];
2992: array[b] = temp;
2993: }
2994: b++;
2995: }
2996: while (c >= b && array[c] >= partionValue) {
2997: if (array[c] == partionValue) {
2998: temp = array[c];
2999: array[c] = array[d];
3000: array[d--] = temp;
3001: }
3002: c--;
3003: }
3004: if (b > c) {
3005: break;
3006: }
3007: temp = array[b];
3008: array[b++] = array[c];
3009: array[c--] = temp;
3010: }
3011: length = a - start < b - a ? a - start : b - a;
3012: int l = start;
3013: int h = b - length;
3014: while (length-- > 0) {
3015: temp = array[l];
3016: array[l++] = array[h];
3017: array[h++] = temp;
3018: }
3019: length = d - c < end - 1 - d ? d - c : end - 1 - d;
3020: l = b;
3021: h = end - length;
3022: while (length-- > 0) {
3023: temp = array[l];
3024: array[l++] = array[h];
3025: array[h++] = temp;
3026: }
3027: if ((length = b - a) > 0) {
3028: sort(start, start + length, array);
3029: }
3030: if ((length = d - c) > 0) {
3031: sort(end - length, end, array);
3032: }
3033: }
3034:
3035: /**
3036: * <p>
3037: * Creates a <code>String</code> representation of the
3038: * <code>boolean[]</code> passed. The result is surrounded by brackets (<code>"[]"</code>),
3039: * each element is converted to a <code>String</code> via the
3040: * {@link String#valueOf(boolean)} and separated by
3041: * <code>", "</code>. If the array is <code>null</code>,
3042: * then <code>"null"</code> is returned.
3043: * </p>
3044: *
3045: * @param array
3046: * The <code>boolean</code> array to convert.
3047: * @return The <code>String</code> representation of <code>array</code>.
3048: * @since 1.5
3049: */
3050: public static String toString(boolean[] array) {
3051: if (array == null) {
3052: return "null"; //$NON-NLS-1$
3053: }
3054: if (array.length == 0) {
3055: return "[]"; //$NON-NLS-1$
3056: }
3057: StringBuilder sb = new StringBuilder(2 + array.length * 5);
3058: sb.append('[');
3059: sb.append(array[0]);
3060: for (int i = 1; i < array.length; i++) {
3061: sb.append(", "); //$NON-NLS-1$
3062: sb.append(array[i]);
3063: }
3064: sb.append(']');
3065: return sb.toString();
3066: }
3067:
3068: /**
3069: * Creates a <code>String</code> representation of the <code>byte[]</code>
3070: * passed.
3071: *
3072: * The result is surrounded by brackets (<code>"[]"</code>),
3073: * each element is converted to a <code>String</code> via the
3074: * {@link String#valueOf(int)} and separated by <code>", "</code>.
3075: * If the array is <code>null</code>, then <code>"null"</code>
3076: * is returned.
3077: *
3078: * @param array
3079: * The <code>byte</code> array to convert.
3080: * @return The <code>String</code> representation of <code>array</code>.
3081: * @since 1.5
3082: */
3083: public static String toString(byte[] array) {
3084: if (array == null) {
3085: return "null"; //$NON-NLS-1$
3086: }
3087: if (array.length == 0) {
3088: return "[]"; //$NON-NLS-1$
3089: }
3090: StringBuilder sb = new StringBuilder(2 + array.length * 3);
3091: sb.append('[');
3092: sb.append(array[0]);
3093: for (int i = 1; i < array.length; i++) {
3094: sb.append(", "); //$NON-NLS-1$
3095: sb.append(array[i]);
3096: }
3097: sb.append(']');
3098: return sb.toString();
3099: }
3100:
3101: /**
3102: * <p>
3103: * Creates a <code>String</code> representation of the <code>char[]</code>
3104: * passed. The result is surrounded by brackets (<code>"[]"</code>),
3105: * each element is converted to a <code>String</code> via the
3106: * {@link String#valueOf(char)} and separated by <code>", "</code>.
3107: * If the array is <code>null</code>, then <code>"null"</code>
3108: * is returned.
3109: * </p>
3110: *
3111: * @param array
3112: * The <code>char</code> array to convert.
3113: * @return The <code>String</code> representation of <code>array</code>.
3114: * @since 1.5
3115: */
3116: public static String toString(char[] array) {
3117: if (array == null) {
3118: return "null"; //$NON-NLS-1$
3119: }
3120: if (array.length == 0) {
3121: return "[]"; //$NON-NLS-1$
3122: }
3123: StringBuilder sb = new StringBuilder(2 + array.length * 2);
3124: sb.append('[');
3125: sb.append(array[0]);
3126: for (int i = 1; i < array.length; i++) {
3127: sb.append(", "); //$NON-NLS-1$
3128: sb.append(array[i]);
3129: }
3130: sb.append(']');
3131: return sb.toString();
3132: }
3133:
3134: /**
3135: * <p>
3136: * Creates a <code>String</code> representation of the
3137: * <code>double[]</code> passed. The result is surrounded by brackets (<code>"[]"</code>),
3138: * each element is converted to a <code>String</code> via the
3139: * {@link String#valueOf(double)} and separated by
3140: * <code>", "</code>. If the array is <code>null</code>,
3141: * then <code>"null"</code> is returned.
3142: * </p>
3143: *
3144: * @param array
3145: * The <code>double</code> array to convert.
3146: * @return The <code>String</code> representation of <code>array</code>.
3147: * @since 1.5
3148: */
3149: public static String toString(double[] array) {
3150: if (array == null) {
3151: return "null"; //$NON-NLS-1$
3152: }
3153: if (array.length == 0) {
3154: return "[]"; //$NON-NLS-1$
3155: }
3156: StringBuilder sb = new StringBuilder(2 + array.length * 5);
3157: sb.append('[');
3158: sb.append(array[0]);
3159: for (int i = 1; i < array.length; i++) {
3160: sb.append(", "); //$NON-NLS-1$
3161: sb.append(array[i]);
3162: }
3163: sb.append(']');
3164: return sb.toString();
3165: }
3166:
3167: /**
3168: * <p>
3169: * Creates a <code>String</code> representation of the
3170: * <code>float[]</code> passed. The result is surrounded by brackets (<code>"[]"</code>),
3171: * each element is converted to a <code>String</code> via the
3172: * {@link String#valueOf(float)} and separated by
3173: * <code>", "</code>. If the array is <code>null</code>,
3174: * then <code>"null"</code> is returned.
3175: * </p>
3176: *
3177: * @param array
3178: * The <code>float</code> array to convert.
3179: * @return The <code>String</code> representation of <code>array</code>.
3180: * @since 1.5
3181: */
3182: public static String toString(float[] array) {
3183: if (array == null) {
3184: return "null"; //$NON-NLS-1$
3185: }
3186: if (array.length == 0) {
3187: return "[]"; //$NON-NLS-1$
3188: }
3189: StringBuilder sb = new StringBuilder(2 + array.length * 5);
3190: sb.append('[');
3191: sb.append(array[0]);
3192: for (int i = 1; i < array.length; i++) {
3193: sb.append(", "); //$NON-NLS-1$
3194: sb.append(array[i]);
3195: }
3196: sb.append(']');
3197: return sb.toString();
3198: }
3199:
3200: /**
3201: * <p>
3202: * Creates a <code>String</code> representation of the <code>int[]</code>
3203: * passed. The result is surrounded by brackets (<code>"[]"</code>),
3204: * each element is converted to a <code>String</code> via the
3205: * {@link String#valueOf(int)} and separated by <code>", "</code>.
3206: * If the array is <code>null</code>, then <code>"null"</code>
3207: * is returned.
3208: * </p>
3209: *
3210: * @param array
3211: * The <code>int</code> array to convert.
3212: * @return The <code>String</code> representation of <code>array</code>.
3213: * @since 1.5
3214: */
3215: public static String toString(int[] array) {
3216: if (array == null) {
3217: return "null"; //$NON-NLS-1$
3218: }
3219: if (array.length == 0) {
3220: return "[]"; //$NON-NLS-1$
3221: }
3222: StringBuilder sb = new StringBuilder(2 + array.length * 4);
3223: sb.append('[');
3224: sb.append(array[0]);
3225: for (int i = 1; i < array.length; i++) {
3226: sb.append(", "); //$NON-NLS-1$
3227: sb.append(array[i]);
3228: }
3229: sb.append(']');
3230: return sb.toString();
3231: }
3232:
3233: /**
3234: * <p>
3235: * Creates a <code>String</code> representation of the <code>long[]</code>
3236: * passed. The result is surrounded by brackets (<code>"[]"</code>),
3237: * each element is converted to a <code>String</code> via the
3238: * {@link String#valueOf(long)} and separated by <code>", "</code>.
3239: * If the array is <code>null</code>, then <code>"null"</code>
3240: * is returned.
3241: * </p>
3242: *
3243: * @param array
3244: * The <code>long</code> array to convert.
3245: * @return The <code>String</code> representation of <code>array</code>.
3246: * @since 1.5
3247: */
3248: public static String toString(long[] array) {
3249: if (array == null) {
3250: return "null"; //$NON-NLS-1$
3251: }
3252: if (array.length == 0) {
3253: return "[]"; //$NON-NLS-1$
3254: }
3255: StringBuilder sb = new StringBuilder(2 + array.length * 4);
3256: sb.append('[');
3257: sb.append(array[0]);
3258: for (int i = 1; i < array.length; i++) {
3259: sb.append(", "); //$NON-NLS-1$
3260: sb.append(array[i]);
3261: }
3262: sb.append(']');
3263: return sb.toString();
3264: }
3265:
3266: /**
3267: * Creates a <code>String</code> representation of the
3268: * <code>short[]</code> passed.
3269: *
3270: * The result is surrounded by brackets (<code>"[]"</code>),
3271: * each element is converted to a <code>String</code> via the
3272: * {@link String#valueOf(int)} and separated by <code>", "</code>.
3273: * If the array is <code>null</code>, then <code>"null"</code>
3274: * is returned.
3275: *
3276: * @param array
3277: * The <code>short</code> array to convert.
3278: * @return The <code>String</code> representation of <code>array</code>.
3279: * @since 1.5
3280: */
3281: public static String toString(short[] array) {
3282: if (array == null) {
3283: return "null"; //$NON-NLS-1$
3284: }
3285: if (array.length == 0) {
3286: return "[]"; //$NON-NLS-1$
3287: }
3288: StringBuilder sb = new StringBuilder(2 + array.length * 4);
3289: sb.append('[');
3290: sb.append(array[0]);
3291: for (int i = 1; i < array.length; i++) {
3292: sb.append(", "); //$NON-NLS-1$
3293: sb.append(array[i]);
3294: }
3295: sb.append(']');
3296: return sb.toString();
3297: }
3298:
3299: /**
3300: * <p>
3301: * Creates a <code>String</code> representation of the
3302: * <code>Object[]</code> passed. The result is surrounded by brackets (<code>"[]"</code>),
3303: * each element is converted to a <code>String</code> via the
3304: * {@link String#valueOf(Object)} and separated by
3305: * <code>", "</code>. If the array is <code>null</code>,
3306: * then <code>"null"</code> is returned.
3307: * </p>
3308: *
3309: * @param array
3310: * The <code>Object</code> array to convert.
3311: * @return The <code>String</code> representation of <code>array</code>.
3312: * @since 1.5
3313: */
3314: public static String toString(Object[] array) {
3315: if (array == null) {
3316: return "null"; //$NON-NLS-1$
3317: }
3318: if (array.length == 0) {
3319: return "[]"; //$NON-NLS-1$
3320: }
3321: StringBuilder sb = new StringBuilder(2 + array.length * 5);
3322: sb.append('[');
3323: sb.append(array[0]);
3324: for (int i = 1; i < array.length; i++) {
3325: sb.append(", "); //$NON-NLS-1$
3326: sb.append(array[i]);
3327: }
3328: sb.append(']');
3329: return sb.toString();
3330: }
3331:
3332: /**
3333: * <p>
3334: * Creates a <i>"deep"</i> <code>String</code> representation of the
3335: * <code>Object[]</code> passed, such that if the array contains other
3336: * arrays, the <code>String</code> representation of those arrays is
3337: * generated as well.
3338: * </p>
3339: * <p>
3340: * If any of the elements are primitive arrays, the generation is delegated
3341: * to the other <code>toString</code> methods in this class. If any
3342: * element contains a reference to the original array, then it will be
3343: * represented as <code>"[...]"</code>. If an element is an
3344: * <code>Object[]</code>, then its representation is generated by a
3345: * recursive call to this method. All other elements are converted via the
3346: * {@link String#valueOf(Object)} method.
3347: * </p>
3348: *
3349: * @param array
3350: * The <code>Object</code> array to convert.
3351: * @return The <code>String</code> representation of <code>array</code>.
3352: * @since 1.5
3353: */
3354: public static String deepToString(Object[] array) {
3355: // delegate this to the recursive method
3356: return deepToStringImpl(array, new Object[] { array }, null);
3357: }
3358:
3359: /**
3360: * <p>
3361: * Implementation method used by {@link #deepToString(Object[])}.
3362: * </p>
3363: *
3364: * @param array
3365: * The <code>Object[]</code> to dive into.
3366: * @param original
3367: * The original <code>Object[]</code>; used to test for self
3368: * references.
3369: * @param sb
3370: * The <code>StringBuilder</code> instance to append to or
3371: * <code>null</code> one hasn't been created yet.
3372: * @return The result.
3373: * @see #deepToString(Object[])
3374: */
3375: private static String deepToStringImpl(Object[] array,
3376: Object[] origArrays, StringBuilder sb) {
3377: if (array == null) {
3378: return "null"; //$NON-NLS-1$
3379: }
3380: if (array.length == 0) {
3381: return "[]"; //$NON-NLS-1$
3382: }
3383:
3384: if (sb == null) {
3385: sb = new StringBuilder(2 + array.length * 5);
3386: }
3387: sb.append('[');
3388:
3389: for (int i = 0; i < array.length; i++) {
3390: if (i != 0) {
3391: sb.append(", "); //$NON-NLS-1$
3392: }
3393: // establish current element
3394: Object elem = array[i];
3395: if (elem == null) {
3396: // element is null
3397: sb.append("null"); //$NON-NLS-1$
3398: } else {
3399: // get the Class of the current element
3400: Class<?> elemClass = elem.getClass();
3401: if (elemClass.isArray()) {
3402: // element is an array type
3403:
3404: // get the declared Class of the array (element)
3405: Class<?> elemElemClass = elemClass
3406: .getComponentType();
3407: if (elemElemClass.isPrimitive()) {
3408: // element is a primitive array
3409: if (boolean.class.equals(elemElemClass)) {
3410: sb.append(toString((boolean[]) elem));
3411: } else if (byte.class.equals(elemElemClass)) {
3412: sb.append(toString((byte[]) elem));
3413: } else if (char.class.equals(elemElemClass)) {
3414: sb.append(toString((char[]) elem));
3415: } else if (double.class.equals(elemElemClass)) {
3416: sb.append(toString((double[]) elem));
3417: } else if (float.class.equals(elemElemClass)) {
3418: sb.append(toString((float[]) elem));
3419: } else if (int.class.equals(elemElemClass)) {
3420: sb.append(toString((int[]) elem));
3421: } else if (long.class.equals(elemElemClass)) {
3422: sb.append(toString((long[]) elem));
3423: } else if (short.class.equals(elemElemClass)) {
3424: sb.append(toString((short[]) elem));
3425: } else {
3426: // no other possible primitives, so we assert that
3427: throw new AssertionError();
3428: }
3429: } else {
3430: // element is an Object[], so we assert that
3431: assert elem instanceof Object[];
3432: if (deepToStringImplContains(origArrays, elem)) {
3433: sb.append("[...]"); //$NON-NLS-1$
3434: } else {
3435: Object[] newArray = (Object[]) elem;
3436: Object[] newOrigArrays = new Object[origArrays.length + 1];
3437: System
3438: .arraycopy(origArrays, 0,
3439: newOrigArrays, 0,
3440: origArrays.length);
3441: newOrigArrays[origArrays.length] = newArray;
3442: // make the recursive call to this method
3443: deepToStringImpl(newArray, newOrigArrays,
3444: sb);
3445: }
3446: }
3447: } else { // element is NOT an array, just an Object
3448: sb.append(array[i]);
3449: }
3450: }
3451: }
3452: sb.append(']');
3453: return sb.toString();
3454: }
3455:
3456: /**
3457: * <p>
3458: * Utility method used to assist the implementation of
3459: * {@link #deepToString(Object[])}.
3460: * </p>
3461: *
3462: * @param origArrays
3463: * An array of Object[] references.
3464: * @param array
3465: * An Object[] reference to look for in <code>origArrays</code>.
3466: * @return A value of <code>true</code> if <code>array</code> is an
3467: * element in <code>origArrays</code>.
3468: */
3469: private static boolean deepToStringImplContains(
3470: Object[] origArrays, Object array) {
3471: if (origArrays == null || origArrays.length == 0) {
3472: return false;
3473: }
3474: for (Object element : origArrays) {
3475: if (element == array) {
3476: return true;
3477: }
3478: }
3479: return false;
3480: }
3481: }
|