home *** CD-ROM | disk | FTP | other *** search
/ Java 1.2 How-To / JavaHowTo.iso / 3rdParty / jbuilder / unsupported / JDK1.2beta3 / SOURCE / SRC.ZIP / java / util / Arrays.java < prev    next >
Encoding:
Java Source  |  1998-03-20  |  48.5 KB  |  1,624 lines
  1. /*
  2.  * @(#)Arrays.java    1.17 98/03/18
  3.  *
  4.  * Copyright 1997, 1998 by Sun Microsystems, Inc.,
  5.  * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
  6.  * All rights reserved.
  7.  *
  8.  * This software is the confidential and proprietary information
  9.  * of Sun Microsystems, Inc. ("Confidential Information").  You
  10.  * shall not disclose such Confidential Information and shall use
  11.  * it only in accordance with the terms of the license agreement
  12.  * you entered into with Sun.
  13.  */
  14.  
  15. package java.util;
  16.  
  17. /**
  18.  * This class contains various methods for manipulating arrays (such as
  19.  * sorting and searching).  It also contains a static factory that allows
  20.  * arrays to be viewed as Lists.
  21.  *
  22.  * @author  Josh Bloch
  23.  * @version 1.17 03/18/98
  24.  * @see Comparable
  25.  * @see Comparator
  26.  * @since   JDK1.2
  27.  */
  28.  
  29. public class Arrays {
  30.     // Sorting
  31.  
  32.     /**
  33.      * Sorts the specified array of longs into ascending numerical order.
  34.      * The sorting algorithm is a tuned quicksort, adapted from Jon
  35.      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  36.      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  37.      * 1993).  This algorithm offers n*log(n) performance on many data sets
  38.      * that cause other quicksorts to degrade to quadratic performance.
  39.      *
  40.      * @param a the array to be sorted.
  41.      */
  42.     public static void sort(long[] a) {
  43.     sort1(a, 0, a.length);
  44.     }
  45.  
  46.     /**
  47.      * Sorts the specified array of ints into ascending numerical order.
  48.      * The sorting algorithm is a tuned quicksort, adapted from Jon
  49.      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  50.      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  51.      * 1993).  This algorithm offers n*log(n) performance on many data sets
  52.      * that cause other quicksorts to degrade to quadratic performance.
  53.      *
  54.      * @param a the array to be sorted.
  55.      */
  56.     public static void sort(int[] a) {
  57.     sort1(a, 0, a.length);
  58.     }
  59.  
  60.     /**
  61.      * Sorts the specified array of shorts into ascending numerical order.
  62.      * The sorting algorithm is a tuned quicksort, adapted from Jon
  63.      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  64.      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  65.      * 1993).  This algorithm offers n*log(n) performance on many data sets
  66.      * that cause other quicksorts to degrade to quadratic performance.
  67.      *
  68.      * @param a the array to be sorted.
  69.      */
  70.     public static void sort(short[] a) {
  71.     sort1(a, 0, a.length);
  72.     }
  73.  
  74.     /**
  75.      * Sorts the specified array of chars into ascending numerical order.
  76.      * The sorting algorithm is a tuned quicksort, adapted from Jon
  77.      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  78.      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  79.      * 1993).  This algorithm offers n*log(n) performance on many data sets
  80.      * that cause other quicksorts to degrade to quadratic performance.
  81.      *
  82.      * @param a the array to be sorted.
  83.      */
  84.     public static void sort(char[] a) {
  85.     sort1(a, 0, a.length);
  86.     }
  87.  
  88.     /**
  89.      * Sorts the specified array of bytes into ascending numerical order.
  90.      * The sorting algorithm is a tuned quicksort, adapted from Jon
  91.      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  92.      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  93.      * 1993).  This algorithm offers n*log(n) performance on many data sets
  94.      * that cause other quicksorts to degrade to quadratic performance.
  95.      *
  96.      * @param a the array to be sorted.
  97.      */
  98.     public static void sort(byte[] a) {
  99.     sort1(a, 0, a.length);
  100.     }
  101.  
  102.     /**
  103.      * Sorts the specified array of doubles into ascending numerical order.
  104.      * The sorting algorithm is a tuned quicksort, adapted from Jon
  105.      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  106.      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  107.      * 1993).  This algorithm offers n*log(n) performance on many data sets
  108.      * that cause other quicksorts to degrade to quadratic performance.
  109.      *
  110.      * @param a the array to be sorted.
  111.      */
  112.     public static void sort(double[] a) {
  113.     sort1(a, 0, a.length);
  114.     }
  115.  
  116.     /**
  117.      * Sorts the specified array of floats into ascending numerical order.
  118.      * The sorting algorithm is a tuned quicksort, adapted from Jon
  119.      * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
  120.      * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
  121.      * 1993).  This algorithm offers n*log(n) performance on many data sets
  122.      * that cause other quicksorts to degrade to quadratic performance.
  123.      *
  124.      * @param a the array to be sorted.
  125.      */
  126.     public static void sort(float[] a) {
  127.     sort1(a, 0, a.length);
  128.     }
  129.  
  130.     /*
  131.      * The code for each of the seven primitive types is identical.
  132.      * C'est la vie.
  133.      */
  134.  
  135.     /**
  136.      * Sorts the specified sub-array of longs into ascending order.
  137.      */
  138.     private static void sort1(long x[], int off, int len) {
  139.     // Insertion sort on smallest arrays
  140.     if (len < 7) {
  141.         for (int i=off; i<len+off; i++)
  142.         for (int j=i; j>off && x[j-1]>x[j]; j--)
  143.             swap(x, j, j-1);
  144.         return;
  145.     }
  146.  
  147.     // Choose a partition element, v
  148.     int m = off + len/2;       // Small arrays, middle element
  149.     if (len > 7) {
  150.         int l = off;
  151.         int n = off + len - 1;
  152.         if (len > 40) {        // Big arrays, pseudomedian of 9
  153.         int s = len/8;
  154.         l = med3(x, l,     l+s, l+2*s);
  155.         m = med3(x, m-s,   m,   m+s);
  156.         n = med3(x, n-2*s, n-s, n);
  157.         }
  158.         m = med3(x, l, m, n); // Mid-size, med of 3
  159.     }
  160.     long v = x[m];
  161.  
  162.     // Establish Invariant: v* (<v)* (>v)* v*
  163.     int a = off, b = a, c = off + len - 1, d = c;
  164.     while(true) {
  165.         while (b <= c && x[b] <= v) {
  166.         if (x[b] == v)
  167.             swap(x, a++, b);
  168.         b++;
  169.         }
  170.         while (c >= b && x[c] >= v) {
  171.         if (x[c] == v)
  172.             swap(x, c, d--);
  173.         c--;
  174.         }
  175.         if (b > c)
  176.         break;
  177.         swap(x, b++, c--);
  178.     }
  179.  
  180.     // Swap partition elements back to middle
  181.     int s, n = off + len;
  182.     s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
  183.     s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);
  184.  
  185.     // Recursively sort non-partition-elements
  186.     if ((s = b-a) > 1)
  187.         sort1(x, off, s);
  188.     if ((s = d-c) > 1)
  189.         sort1(x, n-s, s);
  190.     }
  191.  
  192.     /**
  193.      * Swaps x[a] with x[b].
  194.      */
  195.     private static void swap(long x[], int a, int b) {
  196.     long t = x[a];
  197.     x[a] = x[b];
  198.     x[b] = t;
  199.     }
  200.  
  201.     /**
  202.      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
  203.      */
  204.     private static void vecswap(long x[], int a, int b, int n) {
  205.     for (int i=0; i<n; i++, a++, b++)
  206.         swap(x, a, b);
  207.     }
  208.  
  209.     /**
  210.      * Returns the index of the median of the three indexed longs.
  211.      */
  212.     private static int med3(long x[], int a, int b, int c) {
  213.     return (x[a] < x[b] ?
  214.         (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
  215.         (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
  216.     }
  217.  
  218.     /**
  219.      * Sorts the specified sub-array of integers into ascending order.
  220.      */
  221.     private static void sort1(int x[], int off, int len) {
  222.     // Insertion sort on smallest arrays
  223.     if (len < 7) {
  224.         for (int i=off; i<len+off; i++)
  225.         for (int j=i; j>off && x[j-1]>x[j]; j--)
  226.             swap(x, j, j-1);
  227.         return;
  228.     }
  229.  
  230.     // Choose a partition element, v
  231.     int m = off + len/2;       // Small arrays, middle element
  232.     if (len > 7) {
  233.         int l = off;
  234.         int n = off + len - 1;
  235.         if (len > 40) {        // Big arrays, pseudomedian of 9
  236.         int s = len/8;
  237.         l = med3(x, l,     l+s, l+2*s);
  238.         m = med3(x, m-s,   m,   m+s);
  239.         n = med3(x, n-2*s, n-s, n);
  240.         }
  241.         m = med3(x, l, m, n); // Mid-size, med of 3
  242.     }
  243.     int v = x[m];
  244.  
  245.     // Establish Invariant: v* (<v)* (>v)* v*
  246.     int a = off, b = a, c = off + len - 1, d = c;
  247.     while(true) {
  248.         while (b <= c && x[b] <= v) {
  249.         if (x[b] == v)
  250.             swap(x, a++, b);
  251.         b++;
  252.         }
  253.         while (c >= b && x[c] >= v) {
  254.         if (x[c] == v)
  255.             swap(x, c, d--);
  256.         c--;
  257.         }
  258.         if (b > c)
  259.         break;
  260.         swap(x, b++, c--);
  261.     }
  262.  
  263.     // Swap partition elements back to middle
  264.     int s, n = off + len;
  265.     s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
  266.     s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);
  267.  
  268.     // Recursively sort non-partition-elements
  269.     if ((s = b-a) > 1)
  270.         sort1(x, off, s);
  271.     if ((s = d-c) > 1)
  272.         sort1(x, n-s, s);
  273.     }
  274.  
  275.     /**
  276.      * Swaps x[a] with x[b].
  277.      */
  278.     private static void swap(int x[], int a, int b) {
  279.     int t = x[a];
  280.     x[a] = x[b];
  281.     x[b] = t;
  282.     }
  283.  
  284.     /**
  285.      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
  286.      */
  287.     private static void vecswap(int x[], int a, int b, int n) {
  288.     for (int i=0; i<n; i++, a++, b++)
  289.         swap(x, a, b);
  290.     }
  291.  
  292.     /**
  293.      * Returns the index of the median of the three indexed integers.
  294.      */
  295.     private static int med3(int x[], int a, int b, int c) {
  296.     return (x[a] < x[b] ?
  297.         (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
  298.         (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
  299.     }
  300.  
  301.     /**
  302.      * Sorts the specified sub-array of shorts into ascending order.
  303.      */
  304.     private static void sort1(short x[], int off, int len) {
  305.     // Insertion sort on smallest arrays
  306.     if (len < 7) {
  307.         for (int i=off; i<len+off; i++)
  308.         for (int j=i; j>off && x[j-1]>x[j]; j--)
  309.             swap(x, j, j-1);
  310.         return;
  311.     }
  312.  
  313.     // Choose a partition element, v
  314.     int m = off + len/2;       // Small arrays, middle element
  315.     if (len > 7) {
  316.         int l = off;
  317.         int n = off + len - 1;
  318.         if (len > 40) {        // Big arrays, pseudomedian of 9
  319.         int s = len/8;
  320.         l = med3(x, l,     l+s, l+2*s);
  321.         m = med3(x, m-s,   m,   m+s);
  322.         n = med3(x, n-2*s, n-s, n);
  323.         }
  324.         m = med3(x, l, m, n); // Mid-size, med of 3
  325.     }
  326.     short v = x[m];
  327.  
  328.     // Establish Invariant: v* (<v)* (>v)* v*
  329.     int a = off, b = a, c = off + len - 1, d = c;
  330.     while(true) {
  331.         while (b <= c && x[b] <= v) {
  332.         if (x[b] == v)
  333.             swap(x, a++, b);
  334.         b++;
  335.         }
  336.         while (c >= b && x[c] >= v) {
  337.         if (x[c] == v)
  338.             swap(x, c, d--);
  339.         c--;
  340.         }
  341.         if (b > c)
  342.         break;
  343.         swap(x, b++, c--);
  344.     }
  345.  
  346.     // Swap partition elements back to middle
  347.     int s, n = off + len;
  348.     s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
  349.     s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);
  350.  
  351.     // Recursively sort non-partition-elements
  352.     if ((s = b-a) > 1)
  353.         sort1(x, off, s);
  354.     if ((s = d-c) > 1)
  355.         sort1(x, n-s, s);
  356.     }
  357.  
  358.     /**
  359.      * Swaps x[a] with x[b].
  360.      */
  361.     private static void swap(short x[], int a, int b) {
  362.     short t = x[a];
  363.     x[a] = x[b];
  364.     x[b] = t;
  365.     }
  366.  
  367.     /**
  368.      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
  369.      */
  370.     private static void vecswap(short x[], int a, int b, int n) {
  371.     for (int i=0; i<n; i++, a++, b++)
  372.         swap(x, a, b);
  373.     }
  374.  
  375.     /**
  376.      * Returns the index of the median of the three indexed shorts.
  377.      */
  378.     private static int med3(short x[], int a, int b, int c) {
  379.     return (x[a] < x[b] ?
  380.         (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
  381.         (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
  382.     }
  383.  
  384.  
  385.     /**
  386.      * Sorts the specified sub-array of chars into ascending order.
  387.      */
  388.     private static void sort1(char x[], int off, int len) {
  389.     // Insertion sort on smallest arrays
  390.     if (len < 7) {
  391.         for (int i=off; i<len+off; i++)
  392.         for (int j=i; j>off && x[j-1]>x[j]; j--)
  393.             swap(x, j, j-1);
  394.         return;
  395.     }
  396.  
  397.     // Choose a partition element, v
  398.     int m = off + len/2;       // Small arrays, middle element
  399.     if (len > 7) {
  400.         int l = off;
  401.         int n = off + len - 1;
  402.         if (len > 40) {        // Big arrays, pseudomedian of 9
  403.         int s = len/8;
  404.         l = med3(x, l,     l+s, l+2*s);
  405.         m = med3(x, m-s,   m,   m+s);
  406.         n = med3(x, n-2*s, n-s, n);
  407.         }
  408.         m = med3(x, l, m, n); // Mid-size, med of 3
  409.     }
  410.     char v = x[m];
  411.  
  412.     // Establish Invariant: v* (<v)* (>v)* v*
  413.     int a = off, b = a, c = off + len - 1, d = c;
  414.     while(true) {
  415.         while (b <= c && x[b] <= v) {
  416.         if (x[b] == v)
  417.             swap(x, a++, b);
  418.         b++;
  419.         }
  420.         while (c >= b && x[c] >= v) {
  421.         if (x[c] == v)
  422.             swap(x, c, d--);
  423.         c--;
  424.         }
  425.         if (b > c)
  426.         break;
  427.         swap(x, b++, c--);
  428.     }
  429.  
  430.     // Swap partition elements back to middle
  431.     int s, n = off + len;
  432.     s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
  433.     s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);
  434.  
  435.     // Recursively sort non-partition-elements
  436.     if ((s = b-a) > 1)
  437.         sort1(x, off, s);
  438.     if ((s = d-c) > 1)
  439.         sort1(x, n-s, s);
  440.     }
  441.  
  442.     /**
  443.      * Swaps x[a] with x[b].
  444.      */
  445.     private static void swap(char x[], int a, int b) {
  446.     char t = x[a];
  447.     x[a] = x[b];
  448.     x[b] = t;
  449.     }
  450.  
  451.     /**
  452.      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
  453.      */
  454.     private static void vecswap(char x[], int a, int b, int n) {
  455.     for (int i=0; i<n; i++, a++, b++)
  456.         swap(x, a, b);
  457.     }
  458.  
  459.     /**
  460.      * Returns the index of the median of the three indexed chars.
  461.      */
  462.     private static int med3(char x[], int a, int b, int c) {
  463.     return (x[a] < x[b] ?
  464.         (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
  465.         (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
  466.     }
  467.  
  468.  
  469.     /**
  470.      * Sorts the specified sub-array of bytes into ascending order.
  471.      */
  472.     private static void sort1(byte x[], int off, int len) {
  473.     // Insertion sort on smallest arrays
  474.     if (len < 7) {
  475.         for (int i=off; i<len+off; i++)
  476.         for (int j=i; j>off && x[j-1]>x[j]; j--)
  477.             swap(x, j, j-1);
  478.         return;
  479.     }
  480.  
  481.     // Choose a partition element, v
  482.     int m = off + len/2;       // Small arrays, middle element
  483.     if (len > 7) {
  484.         int l = off;
  485.         int n = off + len - 1;
  486.         if (len > 40) {        // Big arrays, pseudomedian of 9
  487.         int s = len/8;
  488.         l = med3(x, l,     l+s, l+2*s);
  489.         m = med3(x, m-s,   m,   m+s);
  490.         n = med3(x, n-2*s, n-s, n);
  491.         }
  492.         m = med3(x, l, m, n); // Mid-size, med of 3
  493.     }
  494.     byte v = x[m];
  495.  
  496.     // Establish Invariant: v* (<v)* (>v)* v*
  497.     int a = off, b = a, c = off + len - 1, d = c;
  498.     while(true) {
  499.         while (b <= c && x[b] <= v) {
  500.         if (x[b] == v)
  501.             swap(x, a++, b);
  502.         b++;
  503.         }
  504.         while (c >= b && x[c] >= v) {
  505.         if (x[c] == v)
  506.             swap(x, c, d--);
  507.         c--;
  508.         }
  509.         if (b > c)
  510.         break;
  511.         swap(x, b++, c--);
  512.     }
  513.  
  514.     // Swap partition elements back to middle
  515.     int s, n = off + len;
  516.     s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
  517.     s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);
  518.  
  519.     // Recursively sort non-partition-elements
  520.     if ((s = b-a) > 1)
  521.         sort1(x, off, s);
  522.     if ((s = d-c) > 1)
  523.         sort1(x, n-s, s);
  524.     }
  525.  
  526.     /**
  527.      * Swaps x[a] with x[b].
  528.      */
  529.     private static void swap(byte x[], int a, int b) {
  530.     byte t = x[a];
  531.     x[a] = x[b];
  532.     x[b] = t;
  533.     }
  534.  
  535.     /**
  536.      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
  537.      */
  538.     private static void vecswap(byte x[], int a, int b, int n) {
  539.     for (int i=0; i<n; i++, a++, b++)
  540.         swap(x, a, b);
  541.     }
  542.  
  543.     /**
  544.      * Returns the index of the median of the three indexed bytes.
  545.      */
  546.     private static int med3(byte x[], int a, int b, int c) {
  547.     return (x[a] < x[b] ?
  548.         (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
  549.         (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
  550.     }
  551.  
  552.  
  553.     /**
  554.      * Sorts the specified sub-array of doubles into ascending order.
  555.      */
  556.     private static void sort1(double x[], int off, int len) {
  557.     // Insertion sort on smallest arrays
  558.     if (len < 7) {
  559.         for (int i=off; i<len+off; i++)
  560.         for (int j=i; j>off && x[j-1]>x[j]; j--)
  561.             swap(x, j, j-1);
  562.         return;
  563.     }
  564.  
  565.     // Choose a partition element, v
  566.     int m = off + len/2;       // Small arrays, middle element
  567.     if (len > 7) {
  568.         int l = off;
  569.         int n = off + len - 1;
  570.         if (len > 40) {        // Big arrays, pseudomedian of 9
  571.         int s = len/8;
  572.         l = med3(x, l,     l+s, l+2*s);
  573.         m = med3(x, m-s,   m,   m+s);
  574.         n = med3(x, n-2*s, n-s, n);
  575.         }
  576.         m = med3(x, l, m, n); // Mid-size, med of 3
  577.     }
  578.     double v = x[m];
  579.  
  580.     // Establish Invariant: v* (<v)* (>v)* v*
  581.     int a = off, b = a, c = off + len - 1, d = c;
  582.     while(true) {
  583.         while (b <= c && x[b] <= v) {
  584.         if (x[b] == v)
  585.             swap(x, a++, b);
  586.         b++;
  587.         }
  588.         while (c >= b && x[c] >= v) {
  589.         if (x[c] == v)
  590.             swap(x, c, d--);
  591.         c--;
  592.         }
  593.         if (b > c)
  594.         break;
  595.         swap(x, b++, c--);
  596.     }
  597.  
  598.     // Swap partition elements back to middle
  599.     int s, n = off + len;
  600.     s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
  601.     s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);
  602.  
  603.     // Recursively sort non-partition-elements
  604.     if ((s = b-a) > 1)
  605.         sort1(x, off, s);
  606.     if ((s = d-c) > 1)
  607.         sort1(x, n-s, s);
  608.     }
  609.  
  610.     /**
  611.      * Swaps x[a] with x[b].
  612.      */
  613.     private static void swap(double x[], int a, int b) {
  614.     double t = x[a];
  615.     x[a] = x[b];
  616.     x[b] = t;
  617.     }
  618.  
  619.     /**
  620.      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
  621.      */
  622.     private static void vecswap(double x[], int a, int b, int n) {
  623.     for (int i=0; i<n; i++, a++, b++)
  624.         swap(x, a, b);
  625.     }
  626.  
  627.     /**
  628.      * Returns the index of the median of the three indexed doubles.
  629.      */
  630.     private static int med3(double x[], int a, int b, int c) {
  631.     return (x[a] < x[b] ?
  632.         (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
  633.         (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
  634.     }
  635.  
  636.  
  637.     /**
  638.      * Sorts the specified sub-array of floats into ascending order.
  639.      */
  640.     private static void sort1(float x[], int off, int len) {
  641.     // Insertion sort on smallest arrays
  642.     if (len < 7) {
  643.         for (int i=off; i<len+off; i++)
  644.         for (int j=i; j>off && x[j-1]>x[j]; j--)
  645.             swap(x, j, j-1);
  646.         return;
  647.     }
  648.  
  649.     // Choose a partition element, v
  650.     int m = off + len/2;       // Small arrays, middle element
  651.     if (len > 7) {
  652.         int l = off;
  653.         int n = off + len - 1;
  654.         if (len > 40) {        // Big arrays, pseudomedian of 9
  655.         int s = len/8;
  656.         l = med3(x, l,     l+s, l+2*s);
  657.         m = med3(x, m-s,   m,   m+s);
  658.         n = med3(x, n-2*s, n-s, n);
  659.         }
  660.         m = med3(x, l, m, n); // Mid-size, med of 3
  661.     }
  662.     float v = x[m];
  663.  
  664.     // Establish Invariant: v* (<v)* (>v)* v*
  665.     int a = off, b = a, c = off + len - 1, d = c;
  666.     while(true) {
  667.         while (b <= c && x[b] <= v) {
  668.         if (x[b] == v)
  669.             swap(x, a++, b);
  670.         b++;
  671.         }
  672.         while (c >= b && x[c] >= v) {
  673.         if (x[c] == v)
  674.             swap(x, c, d--);
  675.         c--;
  676.         }
  677.         if (b > c)
  678.         break;
  679.         swap(x, b++, c--);
  680.     }
  681.  
  682.     // Swap partition elements back to middle
  683.     int s, n = off + len;
  684.     s = Math.min(a-off, b-a  );  vecswap(x, off, b-s, s);
  685.     s = Math.min(d-c,   n-d-1);  vecswap(x, b,   n-s, s);
  686.  
  687.     // Recursively sort non-partition-elements
  688.     if ((s = b-a) > 1)
  689.         sort1(x, off, s);
  690.     if ((s = d-c) > 1)
  691.         sort1(x, n-s, s);
  692.     }
  693.  
  694.     /**
  695.      * Swaps x[a] with x[b].
  696.      */
  697.     private static void swap(float x[], int a, int b) {
  698.     float t = x[a];
  699.     x[a] = x[b];
  700.     x[b] = t;
  701.     }
  702.  
  703.     /**
  704.      * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
  705.      */
  706.     private static void vecswap(float x[], int a, int b, int n) {
  707.     for (int i=0; i<n; i++, a++, b++)
  708.         swap(x, a, b);
  709.     }
  710.  
  711.     /**
  712.      * Returns the index of the median of the three indexed floats.
  713.      */
  714.     private static int med3(float x[], int a, int b, int c) {
  715.     return (x[a] < x[b] ?
  716.         (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
  717.         (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
  718.     }
  719.  
  720.  
  721.     /**
  722.      * Sorts the specified array of objects into ascending order, according
  723.      * to the <i>natural comparison method</i> of its elements.  All
  724.      * elements in the array must implement the Comparable interface.
  725.      * Furthermore, all elements in the array must be <i>mutually
  726.      * comparable</i> (that is, e1.compareTo(e2) must not throw a
  727.      * typeMismatchException for any elements e1 and e2 in the array).
  728.      * <p>
  729.      * This sort is guaranteed to be <em>stable</em>:  equal elements will
  730.      * not be reordered as a result of the sort.
  731.      * <p>
  732.      * The sorting algorithm is a modified mergesort (in which the merge is
  733.      * omitted if the highest element in the low sublist is less than the
  734.      * lowest element in the high sublist).  This algorithm offers guaranteed
  735.      * n*log(n) performance, and can approach linear performance on nearly
  736.      * sorted lists.
  737.      * 
  738.      * @param a the array to be sorted.
  739.      * @exception ClassCastException array contains elements that are not
  740.      *          <i>mutually comparable</i> (for example, Strings and
  741.      *          Integers).
  742.      * @see Comparable
  743.      */
  744.     public static void sort(Object[] a) {
  745.         Object aux[] = (Object[])a.clone();
  746.         mergeSort(aux, a, 0, a.length);
  747.     }
  748.  
  749.     private static void mergeSort(Object src[], Object dest[],
  750.                                   int low, int high) {
  751.     int length = high - low;
  752.  
  753.     // Insertion sort on smallest arrays
  754.     if (length < 7) {
  755.         for (int i=low; i<high; i++)
  756.         for (int j=i; j>low &&
  757.                  ((Comparable)dest[j-1]).compareTo((Comparable)dest[j])>0; j--)
  758.             swap(dest, j, j-1);
  759.         return;
  760.     }
  761.  
  762.         // Recursively sort halves of dest into src
  763.         int mid = (low + high)/2;
  764.         mergeSort(dest, src, low, mid);
  765.         mergeSort(dest, src, mid, high);
  766.  
  767.         // If list is already sorted, just copy from src to dest.  This is an
  768.         // optimization that results in faster sorts for nearly ordered lists.
  769.         if (((Comparable)src[mid-1]).compareTo((Comparable)src[mid]) <= 0) {
  770.            System.arraycopy(src, low, dest, low, length);
  771.            return;
  772.         }
  773.  
  774.         // Merge sorted halves (now in src) into dest
  775.         for(int i = low, p = low, q = mid; i < high; i++) {
  776.             if (q>=high || p<mid && ((Comparable)src[p]).compareTo(src[q])<=0)
  777.                 dest[i] = src[p++];
  778.             else
  779.                 dest[i] = src[q++];
  780.         }
  781.     }
  782.  
  783.     /**
  784.      * Swaps x[a] with x[b].
  785.      */
  786.     private static void swap(Object x[], int a, int b) {
  787.     Object t = x[a];
  788.     x[a] = x[b];
  789.     x[b] = t;
  790.     }
  791.  
  792.     /**
  793.      * Sorts the specified array of objects according to the order induced by
  794.      * the specified Comparator.  All elements in the array must be
  795.      * <i>mutually comparable</i> by the specified comparator (that is,
  796.      * comparator.compare(e1, e2) must not throw a typeMismatchException for
  797.      * any elements e1 and e2 in the array).
  798.      * <p>
  799.      * This sort is guaranteed to be <em>stable</em>:  equal elements will
  800.      * not be reordered as a result of the sort.
  801.      * <p>
  802.      * The sorting algorithm is a modified mergesort (in which the merge is
  803.      * omitted if the highest element in the low sublist is less than the
  804.      * lowest element in the high sublist).  This algorithm offers guaranteed
  805.      * n*log(n) performance, and can approach linear performance on nearly
  806.      * sorted lists.
  807.      *
  808.      * @param a the array to be sorted.
  809.      * @param c the Comparator to determine the order of the array.
  810.      * @exception ClassCastException array contains elements that are not
  811.      *          <i>mutually comparable</i> with the specified Comparator.
  812.      * @see Comparator
  813.      */
  814.     public static void sort(Object[] a, Comparator c) {
  815.         Object aux[] = (Object[])a.clone();
  816.         mergeSort(aux, a, 0, a.length, c);
  817.     }
  818.  
  819.     private static void mergeSort(Object src[], Object dest[],
  820.                                   int low, int high, Comparator c) {
  821.     int length = high - low;
  822.  
  823.     // Insertion sort on smallest arrays
  824.     if (length < 7) {
  825.         for (int i=low; i<high; i++)
  826.         for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
  827.             swap(dest, j, j-1);
  828.         return;
  829.     }
  830.  
  831.         // Recursively sort halves of dest into src
  832.         int mid = (low + high)/2;
  833.         mergeSort(dest, src, low, mid, c);
  834.         mergeSort(dest, src, mid, high, c);
  835.  
  836.         // If list is already sorted, just copy from src to dest.  This is an
  837.         // optimization that results in faster sorts for nearly ordered lists.
  838.         if (c.compare(src[mid-1], src[mid]) <= 0) {
  839.            System.arraycopy(src, low, dest, low, length);
  840.            return;
  841.         }
  842.  
  843.         // Merge sorted halves (now in src) into dest
  844.         for(int i = low, p = low, q = mid; i < high; i++) {
  845.             if (q>=high || p<mid && c.compare(src[p], src[q]) <= 0)
  846.                 dest[i] = src[p++];
  847.             else
  848.                 dest[i] = src[q++];
  849.         }
  850.     }
  851.  
  852.     // Searching
  853.  
  854.     /**
  855.      * Searches the specified array of longs for the specified value using
  856.      * the binary search algorithm.  The array must <strong>must</strong> be
  857.      * sorted (as by the sort method, above) prior to making this call.  If
  858.      * it is not sorted, the results are undefined: in particular, the call
  859.      * may enter an infinite loop.  If the array contains multiple elements
  860.      * equal to the specified object, there is no guarantee which instance
  861.      * will be found.
  862.      *
  863.      * @param a the array to be searched.
  864.      * @param key the value to be searched for.
  865.      * @return index of the search key, if it is contained in the array;
  866.      *           otherwise, (-(<i>insertion point</i>) - 1).  The <i>insertion
  867.      *           point</i> is defined as the the point at which the value would
  868.      *            be inserted into the array: the index of the first element
  869.      *           greater than the value, or a.length, if all elements in 
  870.      *           the array are less than the specified value.  Note that this
  871.      *           guarantees that the return value will be >= 0 if and only
  872.      *           if the object is found.
  873.      * @see #sort(long[])
  874.      */
  875.     public static int binarySearch(long[] a, long key) {
  876.     int low = 0;
  877.     int high = a.length-1;
  878.  
  879.     while (low <= high) {
  880.         int mid =(low + high)/2;
  881.         long midVal = a[mid];
  882.  
  883.         if (midVal < key)
  884.         low = mid + 1;
  885.         else if (midVal > key)
  886.         high = mid - 1;
  887.         else
  888.         return mid; // key found
  889.     }
  890.     return -(low + 1);  // key not found.
  891.     }
  892.  
  893.     /**
  894.      * Searches the specified array of ints for the specified value using
  895.      * the binary search algorithm.  The array must <strong>must</strong> be
  896.      * sorted (as by the sort method, above) prior to making this call.  If
  897.      * it is not sorted, the results are undefined: in particular, the call
  898.      * may enter an infinite loop.  If the array contains multiple elements
  899.      * equal to the specified object, there is no guarantee which instance
  900.      * will be found.
  901.      *
  902.      * @param a the array to be searched.
  903.      * @param key the value to be searched for.
  904.      * @return index of the search key, if it is contained in the array;
  905.      *           otherwise, (-(the "insertion point") - 1).
  906.      * @see #sort(int[])
  907.      */
  908.     public static int binarySearch(int[] a, int key) {
  909.     int low = 0;
  910.     int high = a.length-1;
  911.  
  912.     while (low <= high) {
  913.         int mid =(low + high)/2;
  914.         int midVal = a[mid];
  915.  
  916.         if (midVal < key)
  917.         low = mid + 1;
  918.         else if (midVal > key)
  919.         high = mid - 1;
  920.         else
  921.         return mid; // key found
  922.     }
  923.     return -(low + 1);  // key not found.
  924.     }
  925.  
  926.     /**
  927.      * Searches the specified array of shorts for the specified value using
  928.      * the binary search algorithm.  The array must <strong>must</strong> be
  929.      * sorted (as by the sort method, above) prior to making this call.  If
  930.      * it is not sorted, the results are undefined: in particular, the call
  931.      * may enter an infinite loop.  If the array contains multiple elements
  932.      * equal to the specified object, there is no guarantee which instance
  933.      * will be found.
  934.      *
  935.      * @param a the array to be searched.
  936.      * @param key the value to be searched for.
  937.      * @return index of the search key, if it is contained in the array;
  938.      *           otherwise, (-(the "insertion point") - 1).
  939.      * @see #sort(short[])
  940.      */
  941.     public static int binarySearch(short[] a, short key) {
  942.     int low = 0;
  943.     int high = a.length-1;
  944.  
  945.     while (low <= high) {
  946.         int mid =(low + high)/2;
  947.         short midVal = a[mid];
  948.  
  949.         if (midVal < key)
  950.         low = mid + 1;
  951.         else if (midVal > key)
  952.         high = mid - 1;
  953.         else
  954.         return mid; // key found
  955.     }
  956.     return -(low + 1);  // key not found.
  957.     }
  958.  
  959.     /**
  960.      * Searches the specified array of chars for the specified value using
  961.      * the binary search algorithm.  The array must <strong>must</strong> be
  962.      * sorted (as by the sort method, above) prior to making this call.  If
  963.      * it is not sorted, the results are undefined: in particular, the call
  964.      * may enter an infinite loop.  If the array contains multiple elements
  965.      * equal to the specified object, there is no guarantee which instance
  966.      * will be found.
  967.      *
  968.      * @param a the array to be searched.
  969.      * @param key the value to be searched for.
  970.      * @return index of the search key, if it is contained in the array;
  971.      *           otherwise, (-(the "insertion point") - 1).
  972.      * @see #sort(char[])
  973.      */
  974.     public static int binarySearch(char[] a, char key) {
  975.     int low = 0;
  976.     int high = a.length-1;
  977.  
  978.     while (low <= high) {
  979.         int mid =(low + high)/2;
  980.         char midVal = a[mid];
  981.  
  982.         if (midVal < key)
  983.         low = mid + 1;
  984.         else if (midVal > key)
  985.         high = mid - 1;
  986.         else
  987.         return mid; // key found
  988.     }
  989.     return -(low + 1);  // key not found.
  990.     }
  991.  
  992.     /**
  993.      * Searches the specified array of bytes for the specified value using
  994.      * the binary search algorithm.  The array must <strong>must</strong> be
  995.      * sorted (as by the sort method, above) prior to making this call.  If
  996.      * it is not sorted, the results are undefined: in particular, the call
  997.      * may enter an infinite loop.  If the array contains multiple elements
  998.      * equal to the specified object, there is no guarantee which instance
  999.      * will be found.
  1000.      *
  1001.      * @param a the array to be searched.
  1002.      * @param key the value to be searched for.
  1003.      * @return index of the search key, if it is contained in the array;
  1004.      *           otherwise, (-(the "insertion point") - 1).
  1005.      * @see #sort(byte[])
  1006.      */
  1007.     public static int binarySearch(byte[] a, byte key) {
  1008.     int low = 0;
  1009.     int high = a.length-1;
  1010.  
  1011.     while (low <= high) {
  1012.         int mid =(low + high)/2;
  1013.         byte midVal = a[mid];
  1014.  
  1015.         if (midVal < key)
  1016.         low = mid + 1;
  1017.         else if (midVal > key)
  1018.         high = mid - 1;
  1019.         else
  1020.         return mid; // key found
  1021.     }
  1022.     return -(low + 1);  // key not found.
  1023.     }
  1024.  
  1025.     /**
  1026.      * Searches the specified array of doubles for the specified value using
  1027.      * the binary search algorithm.  The array must <strong>must</strong> be
  1028.      * sorted (as by the sort method, above) prior to making this call.  If
  1029.      * it is not sorted, the results are undefined: in particular, the call
  1030.      * may enter an infinite loop.  If the array contains multiple elements
  1031.      * equal to the specified object, there is no guarantee which instance
  1032.      * will be found.
  1033.      *
  1034.      * @param a the array to be searched.
  1035.      * @param key the value to be searched for.
  1036.      * @return index of the search key, if it is contained in the array;
  1037.      *           otherwise, (-(the "insertion point") - 1).
  1038.      * @see #sort(double[])
  1039.      */
  1040.     public static int binarySearch(double[] a, double key) {
  1041.     int low = 0;
  1042.     int high = a.length-1;
  1043.  
  1044.     while (low <= high) {
  1045.         int mid =(low + high)/2;
  1046.         double midVal = a[mid];
  1047.  
  1048.         if (midVal < key)
  1049.         low = mid + 1;
  1050.         else if (midVal > key)
  1051.         high = mid - 1;
  1052.         else
  1053.         return mid; // key found
  1054.     }
  1055.     return -(low + 1);  // key not found.
  1056.     }
  1057.  
  1058.     /**
  1059.      * Searches the specified array of floats for the specified value using
  1060.      * the binary search algorithm.  The array must <strong>must</strong> be
  1061.      * sorted (as by the sort method, above) prior to making this call.  If
  1062.      * it is not sorted, the results are undefined: in particular, the call
  1063.      * may enter an infinite loop.  If the array contains multiple elements
  1064.      * equal to the specified object, there is no guarantee which instance
  1065.      * will be found.
  1066.      *
  1067.      * @param a the array to be searched.
  1068.      * @param key the value to be searched for.
  1069.      * @return index of the search key, if it is contained in the array;
  1070.      *           otherwise, (-(the "insertion point") - 1).
  1071.      * @see #sort(float[])
  1072.      */
  1073.     public static int binarySearch(float[] a, float key) {
  1074.     int low = 0;
  1075.     int high = a.length-1;
  1076.  
  1077.     while (low <= high) {
  1078.         int mid =(low + high)/2;
  1079.         float midVal = a[mid];
  1080.  
  1081.         if (midVal < key)
  1082.         low = mid + 1;
  1083.         else if (midVal > key)
  1084.         high = mid - 1;
  1085.         else
  1086.         return mid; // key found
  1087.     }
  1088.     return -(low + 1);  // key not found.
  1089.     }
  1090.  
  1091.     /**
  1092.      * Searches the specified array for the specified Object using the binary
  1093.      * search algorithm.  The array must be sorted into ascending order
  1094.      * according to the <i>natural comparison method</i> of its elements (as by
  1095.      * Sort(Object[]), above) prior to making this call. The array must
  1096.      * <strong>must</strong> be sorted (as by the sort method, above) prior to
  1097.      * making this call.  If it is not sorted, the results are undefined: in
  1098.      * particular, the call may enter an infinite loop.  If the array contains
  1099.      * multiple elements equal to the specified object, there is no guarantee
  1100.      * which instance will be found.
  1101.      *
  1102.      * @param a the array to be searched.
  1103.      * @param key the value to be searched for.
  1104.      * @return index of the search key, if it is contained in the array;
  1105.      *           otherwise, (-(the "insertion point") - 1).
  1106.      * @exception ClassCastException array contains elements that are not
  1107.      *          <i>mutually comparable</i> (for example, Strings and
  1108.      *          Integers), or the search key in not mutually comparable
  1109.      *          with the elements of the array.
  1110.      * @see Comparable
  1111.      * @see #sort(Object[])
  1112.      */
  1113.     public static int binarySearch(Object[] a, Object key) {
  1114.     int low = 0;
  1115.     int high = a.length-1;
  1116.  
  1117.     while (low <= high) {
  1118.         int mid =(low + high)/2;
  1119.         Object midVal = a[mid];
  1120.         int cmp = ((Comparable)midVal).compareTo(key);
  1121.  
  1122.         if (cmp < 0)
  1123.         low = mid + 1;
  1124.         else if (cmp > 0)
  1125.         high = mid - 1;
  1126.         else
  1127.         return mid; // key found
  1128.     }
  1129.     return -(low + 1);  // key not found.
  1130.     }
  1131.  
  1132.     /**
  1133.      * Searches the specified array for the specified Object using the binary
  1134.      * search algorithm.  The array must be sorted into ascending order
  1135.      * according to the specified Comparator (as by Sort(Object[], Comparator),
  1136.      * above), prior to making this call.  If it is not sorted, the results are
  1137.      * undefined: in particular, the call may enter an infinite loop.  If the
  1138.      * array contains multiple elements equal to the specified object, there is
  1139.      * no guarantee which instance will be found.
  1140.      *
  1141.      * @param a the array to be searched.
  1142.      * @param key the value to be searched for.
  1143.      * @param c the Comparator to determine the order of the array.
  1144.      * @return index of the search key, if it is contained in the array;
  1145.      *           otherwise, (-(the "insertion point") - 1).
  1146.      * @exception ClassCastException array contains elements that are not
  1147.      *          <i>mutually comparable</i> with the specified Comparator,
  1148.      *          or the search key in not mutually comparable with the
  1149.      *          elements of the array using this Comparator.
  1150.      * @see Comparable
  1151.      * @see #sort(Object[], Comparator)
  1152.      */
  1153.     public static int binarySearch(Object[] a, Object key, Comparator c) {
  1154.     int low = 0;
  1155.     int high = a.length-1;
  1156.  
  1157.     while (low <= high) {
  1158.         int mid =(low + high)/2;
  1159.         Object midVal = a[mid];
  1160.         int cmp = c.compare(midVal, key);
  1161.  
  1162.         if (cmp < 0)
  1163.         low = mid + 1;
  1164.         else if (cmp > 0)
  1165.         high = mid - 1;
  1166.         else
  1167.         return mid; // key found
  1168.     }
  1169.     return -(low + 1);  // key not found.
  1170.     }
  1171.  
  1172.  
  1173.     // Equality Testing
  1174.  
  1175.     /**
  1176.      * Returns true if the the specified array of long is <em>equal</em>
  1177.      * to the given object.  The array and the object are considered equal
  1178.      * if the object is of type long[], both arrays contain the same number
  1179.      * of elements, and all corresponding pairs of elements in the two arrays
  1180.      * are equal.  In other words, the two arrays are equal if they contain the
  1181.      * same elements in the same order.  Also, the array is considered equal
  1182.      * to the object if both are null.
  1183.      *
  1184.      * @param a the array to be tested for equality.
  1185.      * @param o the object to be tested for equality.
  1186.      * @return true if the array and the object are equal.
  1187.      */
  1188.     public static boolean equals(long[] a, Object o) {
  1189.         if (a == o)
  1190.             return true;
  1191.         if (a==null || !(o instanceof long[]))
  1192.             return false;
  1193.  
  1194.     long[] a2 = (long[])o;
  1195.         int length = a.length;
  1196.         if (a2.length != length)
  1197.             return false;
  1198.  
  1199.         for (int i=0; i<length; i++)
  1200.             if (a[i] != a2[i])
  1201.                 return false;
  1202.  
  1203.         return true;
  1204.     }
  1205.  
  1206.     /**
  1207.      * Returns true if the the specified array of int is <em>equal</em>
  1208.      * to the given object.  The array and the object are considered equal
  1209.      * if the object is of type int[], both arrays contain the same number
  1210.      * of elements, and all corresponding pairs of elements in the two arrays
  1211.      * are equal.  In other words, the two arrays are equal if they contain the
  1212.      * same elements in the same order.  Also, the array is considered equal
  1213.      * to the object if both are null.
  1214.      *
  1215.      * @param a the array to be tested for equality.
  1216.      * @param o the object to be tested for equality.
  1217.      * @return true if the array and the object are equal.
  1218.      */
  1219.     public static boolean equals(int[] a, Object o) {
  1220.         if (a == o)
  1221.             return true;
  1222.         if (a==null || !(o instanceof int[]))
  1223.             return false;
  1224.  
  1225.     int[] a2 = (int[])o;
  1226.         int length = a.length;
  1227.         if (a2.length != length)
  1228.             return false;
  1229.  
  1230.         for (int i=0; i<length; i++)
  1231.             if (a[i] != a2[i])
  1232.                 return false;
  1233.  
  1234.         return true;
  1235.     }
  1236.  
  1237.     /**
  1238.      * Returns true if the the specified array of short is <em>equal</em>
  1239.      * to the given object.  The array and the object are considered equal
  1240.      * if the object is of type short[], both arrays contain the same number
  1241.      * of elements, and all corresponding pairs of elements in the two arrays
  1242.      * are equal.  In other words, the two arrays are equal if they contain the
  1243.      * same elements in the same order.  Also, the array is considered equal
  1244.      * to the object if both are null.
  1245.      *
  1246.      * @param a the array to be tested for equality.
  1247.      * @param o the object to be tested for equality.
  1248.      * @return true if the array and the object are equal.
  1249.      */
  1250.     public static boolean equals(short[] a, Object o) {
  1251.         if (a == o)
  1252.             return true;
  1253.         if (a==null || !(o instanceof short[]))
  1254.             return false;
  1255.  
  1256.     short[] a2 = (short[])o;
  1257.         int length = a.length;
  1258.         if (a2.length != length)
  1259.             return false;
  1260.  
  1261.         for (int i=0; i<length; i++)
  1262.             if (a[i] != a2[i])
  1263.                 return false;
  1264.  
  1265.         return true;
  1266.     }
  1267.  
  1268.     /**
  1269.      * Returns true if the the specified array of char is <em>equal</em>
  1270.      * to the given object.  The array and the object are considered equal
  1271.      * if the object is of type char[], both arrays contain the same number
  1272.      * of elements, and all corresponding pairs of elements in the two arrays
  1273.      * are equal.  In other words, the two arrays are equal if they contain the
  1274.      * same elements in the same order.  Also, the array is considered equal
  1275.      * to the object if both are null.
  1276.      *
  1277.      * @param a the array to be tested for equality.
  1278.      * @param o the object to be tested for equality.
  1279.      * @return true if the array and the object are equal.
  1280.      */
  1281.     public static boolean equals(char[] a, Object o) {
  1282.         if (a == o)
  1283.             return true;
  1284.         if (a==null || !(o instanceof char[]))
  1285.             return false;
  1286.  
  1287.     char[] a2 = (char[])o;
  1288.         int length = a.length;
  1289.         if (a2.length != length)
  1290.             return false;
  1291.  
  1292.         for (int i=0; i<length; i++)
  1293.             if (a[i] != a2[i])
  1294.                 return false;
  1295.  
  1296.         return true;
  1297.     }
  1298.  
  1299.     /**
  1300.      * Returns true if the the specified array of byte is <em>equal</em>
  1301.      * to the given object.  The array and the object are considered equal
  1302.      * if the object is of type byte[], both arrays contain the same number
  1303.      * of elements, and all corresponding pairs of elements in the two arrays
  1304.      * are equal.  In other words, the two arrays are equal if they contain the
  1305.      * same elements in the same order.  Also, the array is considered equal
  1306.      * to the object if both are null.
  1307.      *
  1308.      * @param a the array to be tested for equality.
  1309.      * @param o the object to be tested for equality.
  1310.      * @return true if the array and the object are equal.
  1311.      */
  1312.     public static boolean equals(byte[] a, Object o) {
  1313.         if (a == o)
  1314.             return true;
  1315.         if (a==null || !(o instanceof byte[]))
  1316.             return false;
  1317.  
  1318.     byte[] a2 = (byte[])o;
  1319.         int length = a.length;
  1320.         if (a2.length != length)
  1321.             return false;
  1322.  
  1323.         for (int i=0; i<length; i++)
  1324.             if (a[i] != a2[i])
  1325.                 return false;
  1326.  
  1327.         return true;
  1328.     }
  1329.  
  1330.     /**
  1331.      * Returns true if the the specified array of boolean is <em>equal</em>
  1332.      * to the given object.  The array and the object are considered equal
  1333.      * if the object is of type boolean[], both arrays contain the same number
  1334.      * of elements, and all corresponding pairs of elements in the two arrays
  1335.      * are equal.  In other words, the two arrays are equal if they contain the
  1336.      * same elements in the same order.  Also, the array is considered equal
  1337.      * to the object if both are null.
  1338.      *
  1339.      * @param a the array to be tested for equality.
  1340.      * @param o the object to be tested for equality.
  1341.      * @return true if the array and the object are equal.
  1342.      */
  1343.     public static boolean equals(boolean[] a, Object o) {
  1344.         if (a == o)
  1345.             return true;
  1346.         if (a==null || !(o instanceof boolean[]))
  1347.             return false;
  1348.  
  1349.     boolean[] a2 = (boolean[])o;
  1350.         int length = a.length;
  1351.         if (a2.length != length)
  1352.             return false;
  1353.  
  1354.         for (int i=0; i<length; i++)
  1355.             if (a[i] != a2[i])
  1356.                 return false;
  1357.  
  1358.         return true;
  1359.     }
  1360.  
  1361.     /**
  1362.      * Returns true if the the specified array of double is <em>equal</em>
  1363.      * to the given object.  The array and the object are considered equal
  1364.      * if the object is of type double[], both arrays contain the same number
  1365.      * of elements, and all corresponding pairs of elements in the two arrays
  1366.      * are equal.  In other words, the two arrays are equal if they contain the
  1367.      * same elements in the same order.  Also, the array is considered equal
  1368.      * to the object if both are null.
  1369.      *
  1370.      * @param a the array to be tested for equality.
  1371.      * @param o the object to be tested for equality.
  1372.      * @return true if the array and the object are equal.
  1373.      */
  1374.     public static boolean equals(double[] a, Object o) {
  1375.         if (a == o)
  1376.             return true;
  1377.         if (a==null || !(o instanceof double[]))
  1378.             return false;
  1379.  
  1380.     double[] a2 = (double[])o;
  1381.         int length = a.length;
  1382.         if (a2.length != length)
  1383.             return false;
  1384.  
  1385.         for (int i=0; i<length; i++)
  1386.             if (a[i] != a2[i])
  1387.                 return false;
  1388.  
  1389.         return true;
  1390.     }
  1391.  
  1392.     /**
  1393.      * Returns true if the the specified array of float is <em>equal</em>
  1394.      * to the given object.  The array and the object are considered equal
  1395.      * if the object is of type float[], both arrays contain the same number
  1396.      * of elements, and all corresponding pairs of elements in the two arrays
  1397.      * are equal.  In other words, the two arrays are equal if they contain the
  1398.      * same elements in the same order.  Also, the array is considered equal
  1399.      * to the object if both are null.
  1400.      *
  1401.      * @param a the array to be tested for equality.
  1402.      * @param o the object to be tested for equality.
  1403.      * @return true if the array and the object are equal.
  1404.      */
  1405.     public static boolean equals(float[] a, Object o) {
  1406.         if (a == o)
  1407.             return true;
  1408.         if (a==null || !(o instanceof float[]))
  1409.             return false;
  1410.  
  1411.     float[] a2 = (float[])o;
  1412.         int length = a.length;
  1413.         if (a2.length != length)
  1414.             return false;
  1415.  
  1416.         for (int i=0; i<length; i++)
  1417.             if (a[i] != a2[i])
  1418.                 return false;
  1419.  
  1420.         return true;
  1421.     }
  1422.  
  1423.     /**
  1424.      * Returns true if the the specified array of Object is <em>equal</em>
  1425.      * to the given object.  The array and the object are considered equal
  1426.      * if the object is of type Object[], both arrays contain the same number
  1427.      * of elements, and all corresponding pairs of elements in the two arrays
  1428.      * are equal.  In other words, the two arrays are equal if they contain the
  1429.      * same elements in the same order.  Also, the array is considered equal
  1430.      * to the object if both are null.
  1431.      *
  1432.      * @param a the array to be tested for equality.
  1433.      * @param o the object to be tested for equality.
  1434.      * @return true if the array and the object are equal.
  1435.      */
  1436.     public static boolean equals(Object[] a, Object o) {
  1437.         if (a == o)
  1438.             return true;
  1439.         if (a==null || !(o instanceof Object[]))
  1440.             return false;
  1441.  
  1442.     Object[] a2 = (Object[])o;
  1443.         int length = a.length;
  1444.         if (a2.length != length)
  1445.             return false;
  1446.  
  1447.         for (int i=0; i<length; i++) {
  1448.             Object o1 = a[i];
  1449.             Object o2 = a2[i];
  1450.             if (!(o1==null ? o2==null : o1.equals(o2)))
  1451.                 return false;
  1452.         }
  1453.  
  1454.         return true;
  1455.     }
  1456.  
  1457.  
  1458.     // Filling
  1459.  
  1460.     /**
  1461.      * Sets each element of the specified array of longs with the specified
  1462.      * long value.
  1463.      *
  1464.      * @param a the array to be filled.
  1465.      * @param val the value to be stored in all elements of the array.
  1466.      */
  1467.     public static void fill(long[] a, long val) {
  1468.         int length = a.length;
  1469.         for (int i=0; i<length; i++)
  1470.             a[i] = val;
  1471.     }
  1472.  
  1473.     /**
  1474.      * Sets each element of the specified array of ints with the specified
  1475.      * int value.
  1476.      *
  1477.      * @param a the array to be filled.
  1478.      * @param val the value to be stored in all elements of the array.
  1479.      */
  1480.     public static void fill(int[] a, int val) {
  1481.         int length = a.length;
  1482.         for (int i=0; i<length; i++)
  1483.             a[i] = val;
  1484.     }
  1485.  
  1486.     /**
  1487.      * Sets each element of the specified array of shorts with the specified
  1488.      * short value.
  1489.      *
  1490.      * @param a the array to be filled.
  1491.      * @param val the value to be stored in all elements of the array.
  1492.      */
  1493.     public static void fill(short[] a, short val) {
  1494.         int length = a.length;
  1495.         for (int i=0; i<length; i++)
  1496.             a[i] = val;
  1497.     }
  1498.  
  1499.     /**
  1500.      * Sets each element of the specified array of chars with the specified
  1501.      * char value.
  1502.      *
  1503.      * @param a the array to be filled.
  1504.      * @param val the value to be stored in all elements of the array.
  1505.      */
  1506.     public static void fill(char[] a, char val) {
  1507.         int length = a.length;
  1508.         for (int i=0; i<length; i++)
  1509.             a[i] = val;
  1510.     }
  1511.  
  1512.     /**
  1513.      * Sets each element of the specified array of bytes with the specified
  1514.      * byte value.
  1515.      *
  1516.      * @param a the array to be filled.
  1517.      * @param val the value to be stored in all elements of the array.
  1518.      */
  1519.     public static void fill(byte[] a, byte val) {
  1520.         int length = a.length;
  1521.         for (int i=0; i<length; i++)
  1522.             a[i] = val;
  1523.     }
  1524.  
  1525.     /**
  1526.      * Sets each element of the specified array of booleans with the specified
  1527.      * boolean value.
  1528.      *
  1529.      * @param a the array to be filled.
  1530.      * @param val the value to be stored in all elements of the array.
  1531.      */
  1532.     public static void fill(boolean[] a, boolean val) {
  1533.         int length = a.length;
  1534.         for (int i=0; i<length; i++)
  1535.             a[i] = val;
  1536.     }
  1537.  
  1538.     /**
  1539.      * Sets each element of the specified array of doubles with the specified
  1540.      * double value.
  1541.      *
  1542.      * @param a the array to be filled.
  1543.      * @param val the value to be stored in all elements of the array.
  1544.      */
  1545.     public static void fill(double[] a, double val) {
  1546.         int length = a.length;
  1547.         for (int i=0; i<length; i++)
  1548.             a[i] = val;
  1549.     }
  1550.  
  1551.     /**
  1552.      * Sets each element of the specified array of floats with the specified
  1553.      * float value.
  1554.      *
  1555.      * @param a the array to be filled.
  1556.      * @param val the value to be stored in all elements of the array.
  1557.      */
  1558.     public static void fill(float[] a, float val) {
  1559.         int length = a.length;
  1560.         for (int i=0; i<length; i++)
  1561.             a[i] = val;
  1562.     }
  1563.  
  1564.     /**
  1565.      * Sets each element of the specified array of Objects with the specified
  1566.      * Object value.
  1567.      *
  1568.      * @param a the array to be filled.
  1569.      * @param val the value to be stored in all elements of the array.
  1570.      */
  1571.     public static void fill(Object[] a, Object val) {
  1572.         int length = a.length;
  1573.         for (int i=0; i<length; i++)
  1574.             a[i] = val;
  1575.     }
  1576.  
  1577.  
  1578.     // Misc
  1579.  
  1580.     /**
  1581.      * Returns a fixed-size List backed by the specified array.  (Changes to
  1582.      * the returned List "write through" to the array.)  This method acts
  1583.      * as bridge between array-based and Collection-based APIs, in
  1584.      * combination with Collection.toArray.
  1585.      *
  1586.      * @param a the array by which the List will be backed.
  1587.      * @return a List view of the specified array.
  1588.      * @see Collection#toArray()
  1589.      */
  1590.     public static List toList(Object[] a) {
  1591.     return new ArrayList(a);
  1592.     }
  1593.  
  1594.     private static class ArrayList extends AbstractList implements Cloneable {
  1595.     private Object[] a;
  1596.  
  1597.     ArrayList(Object[] array) {
  1598.         a = array;
  1599.     }
  1600.  
  1601.     public int size() {
  1602.         return a.length;
  1603.     }
  1604.  
  1605.     public Object[] toArray() {
  1606.         return (Object[]) a.clone();
  1607.     }
  1608.  
  1609.     public Object get(int index) {
  1610.         return a[index];
  1611.     }
  1612.  
  1613.     public Object set(int index, Object element) {
  1614.         Object oldValue = a[index];
  1615.         a[index] = element;
  1616.         return oldValue;
  1617.     }
  1618.  
  1619.     public Object clone() {
  1620.         return new ArrayList(toArray());
  1621.     }
  1622.     }
  1623. }
  1624.