Java Tutorial/Collections/Array Sort Search

Содержание

1 FastQSorts the [l,r] partition (inclusive) of the specfied array of Rows, using the comparator.
2 Finds the index of the given object in the array.
3 Finds the index of the given object in the array starting at the given index.
4 Finds the last index of the given object in the array starting at the given index.
5 Finds the value in the range (start,limit) of the largest element (rank) where the count of all smaller elements in that range is less than or equals target.
6 Get the element index or last index among a boolean type array
7 Get the index and last index of an int type value array
8 Object Arrays: Searching for elements in a sorted object array
9 Produces a new array containing the elements between the start and end indices.
10 Returns an index into arra (or -1) where the character is not in the charset byte array.
11 Returns an int[] array of length segments containing the distribution count of the elements in unsorted int[] array with values between min and max (range).
12 Returns the minimum value in an array.
13 Returns true if all the references in array1 are equal to all the references in array2 (two null references are considered equal for this test).
14 Searching Arrays
15 Sort array utilities
16 Sorting Arrays
17 Sorting arrays of objects
18 Sorting a subset of array elements
19 Test the equality of two object arrays

FastQSorts the [l,r] partition (inclusive) of the specfied array of Rows, using the comparator.

   <source lang="java">

* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* Redistributions of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer.
*
* Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* Neither the name of the Hypersonic SQL Group nor the names of its
* contributors may be used to endorse or promote products derived from this
* software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE HYPERSONIC SQL GROUP,
* OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* This software consists of voluntary contributions made by many individuals
* on behalf of the Hypersonic SQL Group.
*
*
* For work added by the HSQL Development Group:
*
* Copyright (c) 2001-2009, The HSQL Development Group
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* Redistributions of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer.
*
* Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* Neither the name of the HSQL Development Group nor the names of its
* contributors may be used to endorse or promote products derived from this
* software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
* OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

/**

* FastQSorts the [l,r] partition (inclusive) of the specfied array of Rows,
* using the comparator.
* 
* Modified from the original method in Hypersonic with the addition of the
* comparator. (fredt@users)
* 
* @author Thomas Mueller (Hypersonic SQL Group)
* @version 1.7.2
* @since 1.7.2
*/

public class Sort {

 public static final void sort(Object[] w, ObjectComparator comparator, int l, int r) {
   int i;
   int j;
   Object p;
   if (l > r) {
     return;
   }
   while (r - l > 10) {
     i = (r + l) >>> 1;
     if (comparator.rupare(w[l], w[r]) > 0) {
       swap(w, l, r);
     }
     if (comparator.rupare(w[i], w[l]) < 0) {
       swap(w, l, i);
     } else if (comparator.rupare(w[i], w[r]) > 0) {
       swap(w, i, r);
     }
     j = r - 1;
     swap(w, i, j);
     p = w[j];
     i = l;
     while (true) {
       while (comparator.rupare(w[++i], p) < 0) {
         ;
       }
       while (comparator.rupare(w[--j], p) > 0) {
         ;
       }
       if (i >= j) {
         break;
       }
       swap(w, i, j);
     }
     swap(w, i, r - 1);
     sort(w, comparator, l, i - 1);
     l = i + 1;
   }
   for (i = l + 1; i <= r; i++) {
     Object t = w[i];
     for (j = i - 1; j >= l && comparator.rupare(w[j], t) > 0; j--) {
       w[j + 1] = w[j];
     }
     w[j + 1] = t;
   }
 }
 /**
  * Swaps the a"th and b"th elements of the specified Row array.
  */
 private static void swap(Object[] w, int a, int b) {
   Object t = w[a];
   w[a] = w[b];
   w[b] = t;
 }

} interface ObjectComparator {

 int compare(Object a, Object b);

}</source>

Finds the index of the given object in the array.

   <source lang="java">

*
*   Licensed under the Apache License, Version 2.0 (the "License");
*   you may not use this file except in compliance with the License.
*   You may obtain a copy of the License at
*
*       http://www.apache.org/licenses/LICENSE-2.0
*
*   Unless required by applicable law or agreed to in writing, software
*   distributed under the License is distributed on an "AS IS" BASIS,
*   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
*   See the License for the specific language governing permissions and
*  limitations under the License.
*/

import java.lang.reflect.Array;

/**

* Operations on arrays, primitive arrays (like int[]) and
* primitive wrapper arrays (like Integer[]).
* 
* This class tries to handle null input gracefully.
* An exception will not be thrown for a null
* array input. However, an Object array that contains a null
* element may throw an exception. Each method documents its behaviour.
*
* @author Stephen Colebourne
* @author Moritz Petersen
* @author 
* @author Maarten Coene
* @since 2.0
* @version $Id: ArrayUtils.java 632503 2008-03-01 00:21:52Z ggregory $
*/

public class Main {

 /**
  * Finds the index of the given object in the array.
  *
  * This method returns {@link #INDEX_NOT_FOUND} (-1) for a null input array.
  * 
  * @param array  the array to search through for the object, may be null
  * @param objectToFind  the object to find, may be null
  * @return the index of the object within the array, 
  *  {@link #INDEX_NOT_FOUND} (-1) if not found or null array input
  */
 public static int indexOf(Object[] array, Object objectToFind) {
     return indexOf(array, objectToFind, 0);
 }
 /**
  * Finds the index of the given object in the array starting at the given index.
  *
  * This method returns {@link #INDEX_NOT_FOUND} (-1) for a null input array.
  *
  * A negative startIndex is treated as zero. A startIndex larger than the array
  * length will return {@link #INDEX_NOT_FOUND} (-1).
  * 
  * @param array  the array to search through for the object, may be null
  * @param objectToFind  the object to find, may be null
  * @param startIndex  the index to start searching at
  * @return the index of the object within the array starting at the index,
  *  {@link #INDEX_NOT_FOUND} (-1) if not found or null array input
  */
 public static int indexOf(Object[] array, Object objectToFind, int startIndex) {
     if (array == null) {
         return -1;
     }
     if (startIndex < 0) {
         startIndex = 0;
     }
     if (objectToFind == null) {
         for (int i = startIndex; i < array.length; i++) {
             if (array[i] == null) {
                 return i;
             }
         }
     } else {
         for (int i = startIndex; i < array.length; i++) {
             if (objectToFind.equals(array[i])) {
                 return i;
             }
         }
     }
     return -1;
 }

}</source>

Finds the index of the given object in the array starting at the given index.

   <source lang="java">

*
*   Licensed under the Apache License, Version 2.0 (the "License");
*   you may not use this file except in compliance with the License.
*   You may obtain a copy of the License at
*
*       http://www.apache.org/licenses/LICENSE-2.0
*
*   Unless required by applicable law or agreed to in writing, software
*   distributed under the License is distributed on an "AS IS" BASIS,
*   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
*   See the License for the specific language governing permissions and
*  limitations under the License.
*/

import java.lang.reflect.Array;

/**

* Operations on arrays, primitive arrays (like int[]) and
* primitive wrapper arrays (like Integer[]).
* 
* This class tries to handle null input gracefully.
* An exception will not be thrown for a null
* array input. However, an Object array that contains a null
* element may throw an exception. Each method documents its behaviour.
*
* @author Stephen Colebourne
* @author Moritz Petersen
* @author 
* @author Maarten Coene
* @since 2.0
* @version $Id: ArrayUtils.java 632503 2008-03-01 00:21:52Z ggregory $
*/

public class Main {

 /**
  * Finds the index of the given object in the array starting at the given index.
  *
  * This method returns {@link #INDEX_NOT_FOUND} (-1) for a null input array.
  *
  * A negative startIndex is treated as zero. A startIndex larger than the array
  * length will return {@link #INDEX_NOT_FOUND} (-1).
  * 
  * @param array  the array to search through for the object, may be null
  * @param objectToFind  the object to find, may be null
  * @param startIndex  the index to start searching at
  * @return the index of the object within the array starting at the index,
  *  {@link #INDEX_NOT_FOUND} (-1) if not found or null array input
  */
 public static int indexOf(Object[] array, Object objectToFind, int startIndex) {
     if (array == null) {
         return -1;
     }
     if (startIndex < 0) {
         startIndex = 0;
     }
     if (objectToFind == null) {
         for (int i = startIndex; i < array.length; i++) {
             if (array[i] == null) {
                 return i;
             }
         }
     } else {
         for (int i = startIndex; i < array.length; i++) {
             if (objectToFind.equals(array[i])) {
                 return i;
             }
         }
     }
     return -1;
 }

}</source>

Finds the last index of the given object in the array starting at the given index.

   <source lang="java">

*
*   Licensed under the Apache License, Version 2.0 (the "License");
*   you may not use this file except in compliance with the License.
*   You may obtain a copy of the License at
*
*       http://www.apache.org/licenses/LICENSE-2.0
*
*   Unless required by applicable law or agreed to in writing, software
*   distributed under the License is distributed on an "AS IS" BASIS,
*   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
*   See the License for the specific language governing permissions and
*  limitations under the License.
*/

import java.lang.reflect.Array;

/**

* Operations on arrays, primitive arrays (like int[]) and
* primitive wrapper arrays (like Integer[]).
* 
* This class tries to handle null input gracefully.
* An exception will not be thrown for a null
* array input. However, an Object array that contains a null
* element may throw an exception. Each method documents its behaviour.
*
* @author Stephen Colebourne
* @author Moritz Petersen
* @author 
* @author Maarten Coene
* @since 2.0
* @version $Id: ArrayUtils.java 632503 2008-03-01 00:21:52Z ggregory $
*/

public class Main {

 /**
  * Finds the last index of the given object in the array starting at the given index.
  *
  * This method returns {@link #INDEX_NOT_FOUND} (-1) for a null input array.
  *
  * A negative startIndex will return {@link #INDEX_NOT_FOUND} (-1). A startIndex larger than
  * the array length will search from the end of the array.
  * 
  * @param array  the array to traverse for looking for the object, may be null
  * @param objectToFind  the object to find, may be null
  * @param startIndex  the start index to travers backwards from
  * @return the last index of the object within the array,
  *  {@link #INDEX_NOT_FOUND} (-1) if not found or null array input
  */
 public static int lastIndexOf(Object[] array, Object objectToFind, int startIndex) {
     if (array == null) {
         return -1;
     }
     if (startIndex < 0) {
         return -1;
     } else if (startIndex >= array.length) {
         startIndex = array.length - 1;
     }
     if (objectToFind == null) {
         for (int i = startIndex; i >= 0; i--) {
             if (array[i] == null) {
                 return i;
             }
         }
     } else {
         for (int i = startIndex; i >= 0; i--) {
             if (objectToFind.equals(array[i])) {
                 return i;
             }
         }
     }
     return -1;
 }

}</source>

Finds the value in the range (start,limit) of the largest element (rank) where the count of all smaller elements in that range is less than or equals target.

   <source lang="java">

* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* Redistributions of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer.
*
* Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* Neither the name of the HSQL Development Group nor the names of its
* contributors may be used to endorse or promote products derived from this
* software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
* OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

/**

* Collection of routines for counting the distribution of the values
* in an int[] array.
*
* @author Fred Toussi (fredt@users dot sourceforge.net)
* @version 1.7.2
* @since 1.7.2
*/

public class ArrayCounter {

   /**
    * Returns an int[] array of length segments containing the distribution
    * count of the elements in unsorted int[] array with values between min
    * and max (range). Values outside the min-max range are ignored
    *
    * A usage example is determining the count of people of each age group
    * in a large int[] array containing the age of each person. Called with
    * (array, 16,0,79), it will return an int[16] with the first element
    * the count of people aged 0-4, the second element the count of those
    * aged 5-9, and so on. People above the age of 79 are excluded. If the
    * range is not a multiple of segments, the last segment will be cover a
    * smaller sub-range than the rest.
    *
    */
   public static int[] countSegments(int[] array, int elements,
                                     int segments, int start, int limit) {
       int[] counts   = new int[segments];
       long  interval = calcInterval(segments, start, limit);
       int   index    = 0;
       int   element  = 0;
       if (interval <= 0) {
           return counts;
       }
       for (int i = 0; i < elements; i++) {
           element = array[i];
           if (element < start || element >= limit) {
               continue;
           }
           index = (int) ((element - start) / interval);
           counts[index]++;
       }
       return counts;
   }
   /**
    * With an unsorted int[] array and with target a positive integer in the
    * range (1,array.length), finds the value in the range (start,limit) of the
    * largest element (rank) where the count of all smaller elements in that
    * range is less than or equals target. Parameter margin indicates the
    * margin of error in target
    *
    * In statistics, this can be used to calculate a median or quadrile value.
    * A usage example applied to an array of age values is to determine
    * the maximum age of a given number of people. With the example array
    * given in countSegments, rank(array, c, 6000, 18, 65, 0) will return an age
    * value between 18-64 (inclusive) and the count of all people aged between
    * 18 and the returned value(exclusive) will be less than or equal 6000.
    *
    */
   public static int rank(int[] array, int elements, int target, int start,
                          int limit, int margin) {
       final int segments     = 256;
       int       elementCount = 0;
       int       currentLimit = limit;
       for (;;) {
           long interval = calcInterval(segments, start, currentLimit);
           int[] counts = countSegments(array, elements, segments, start,
                                        currentLimit);
           for (int i = 0; i < counts.length; i++) {
               if (elementCount + counts[i] < target) {
                   elementCount += counts[i];
                   start        += interval;
               } else {
                   break;
               }
           }
           if (elementCount + margin >= target) {
               return start;
           }
           if (interval <= 1) {
               return start;
           }
           currentLimit = start + interval < limit ? (int) (start + interval)
                                                   : limit;
       }
   }
   /**
    * Helper method to calculate the span of the sub-interval. Simply returns
    * the cieling of ((limit - start) / segments) and accounts for invalid
    * start and limit combinations.
    */
   static long calcInterval(int segments, int start, int limit) {
       long range = limit - start;
       if (range < 0) {
           return 0;
       }
       int partSegment = (range % segments) == 0 ? 0
                                                 : 1;
       return (range / segments) + partSegment;
   }

}</source>

Get the element index or last index among a boolean type array

   <source lang="java">

*
*   Licensed under the Apache License, Version 2.0 (the "License");
*   you may not use this file except in compliance with the License.
*   You may obtain a copy of the License at
*
*       http://www.apache.org/licenses/LICENSE-2.0
*
*   Unless required by applicable law or agreed to in writing, software
*   distributed under the License is distributed on an "AS IS" BASIS,
*   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
*   See the License for the specific language governing permissions and
*  limitations under the License.
*/

import java.lang.reflect.Array;

/**

* Operations on arrays, primitive arrays (like int[]) and
* primitive wrapper arrays (like Integer[]).
* 
* This class tries to handle null input gracefully.
* An exception will not be thrown for a null
* array input. However, an Object array that contains a null
* element may throw an exception. Each method documents its behaviour.
*
* @author Stephen Colebourne
* @author Moritz Petersen
* @author 
* @author Maarten Coene
* @since 2.0
* @version $Id: ArrayUtils.java 632503 2008-03-01 00:21:52Z ggregory $
*/

public class Main {

 /**
  * The index value when an element is not found in a list or array: -1.
  * This value is returned by methods in this class and can also be used in comparisons with values returned by
  * various method from {@link java.util.List}.
  */
 public static final int INDEX_NOT_FOUND = -1;
 // boolean IndexOf
 //-----------------------------------------------------------------------
 /**
  * Finds the index of the given value in the array.
  *
  * This method returns {@link #INDEX_NOT_FOUND} (-1) for a null input array.
  * 
  * @param array  the array to search through for the object, may be null
  * @param valueToFind  the value to find
  * @return the index of the value within the array,
  *  {@link #INDEX_NOT_FOUND} (-1) if not found or null array input
  */
 public static int indexOf(boolean[] array, boolean valueToFind) {
     return indexOf(array, valueToFind, 0);
 }
 /**
  * Finds the index of the given value in the array starting at the given index.
  *
  * This method returns {@link #INDEX_NOT_FOUND} (-1) for a null input array.
  *
  * A negative startIndex is treated as zero. A startIndex larger than the array
  * length will return {@link #INDEX_NOT_FOUND} (-1).
  * 
  * @param array  the array to search through for the object, may be null
  * @param valueToFind  the value to find
  * @param startIndex  the index to start searching at
  * @return the index of the value within the array,
  *  {@link #INDEX_NOT_FOUND} (-1) if not found or null
  *  array input
  */
 public static int indexOf(boolean[] array, boolean valueToFind, int startIndex) {
     if (isEmpty(array)) {
         return INDEX_NOT_FOUND;
     }
     if (startIndex < 0) {
         startIndex = 0;
     }
     for (int i = startIndex; i < array.length; i++) {
         if (valueToFind == array[i]) {
             return i;
         }
     }
     return INDEX_NOT_FOUND;
 }
 /**
  * Finds the last index of the given value within the array.
  *
  * This method returns {@link #INDEX_NOT_FOUND} (-1) if 
  * null array input.
  * 
  * @param array  the array to travers backwords looking for the object, may be null
  * @param valueToFind  the object to find
  * @return the last index of the value within the array,
  *  {@link #INDEX_NOT_FOUND} (-1) if not found or null array input
  */
 public static int lastIndexOf(boolean[] array, boolean valueToFind) {
     return lastIndexOf(array, valueToFind, Integer.MAX_VALUE);
 }
 /**
  * Finds the last index of the given value in the array starting at the given index.
  *
  * This method returns {@link #INDEX_NOT_FOUND} (-1) for a null input array.
  *
  * A negative startIndex will return {@link #INDEX_NOT_FOUND} (-1). A startIndex larger than 
  * the array length will search from the end of the array.
  * 
  * @param array  the array to traverse for looking for the object, may be null
  * @param valueToFind  the value to find
  * @param startIndex  the start index to travers backwards from
  * @return the last index of the value within the array,
  *  {@link #INDEX_NOT_FOUND} (-1) if not found or null array input
  */
 public static int lastIndexOf(boolean[] array, boolean valueToFind, int startIndex) {
     if (isEmpty(array)) {
         return INDEX_NOT_FOUND;
     }
     if (startIndex < 0) {
         return INDEX_NOT_FOUND;
     } else if (startIndex >= array.length) {
         startIndex = array.length - 1;
     }
     for (int i = startIndex; i >= 0; i--) {
         if (valueToFind == array[i]) {
             return i;
         }
     }
     return INDEX_NOT_FOUND;
 }
 /**
  * Checks if the value is in the given array.
  *
  * The method returns false if a null array is passed in.
  * 
  * @param array  the array to search through
  * @param valueToFind  the value to find
  * @return true if the array contains the object
  */
 public static boolean contains(boolean[] array, boolean valueToFind) {
     return indexOf(array, valueToFind) != INDEX_NOT_FOUND;
 }

 /**
  * Checks if an array of primitive doubles is empty or null.
  *
  * @param array  the array to test
  * @return true if the array is empty or null
  * @since 2.1
  */
 public static boolean isEmpty(boolean[] array) {
     if (array == null || array.length == 0) {
         return true;
     }
     return false;
 }

}</source>

Get the index and last index of an int type value array

   <source lang="java">

*
*   Licensed under the Apache License, Version 2.0 (the "License");
*   you may not use this file except in compliance with the License.
*   You may obtain a copy of the License at
*
*       http://www.apache.org/licenses/LICENSE-2.0
*
*   Unless required by applicable law or agreed to in writing, software
*   distributed under the License is distributed on an "AS IS" BASIS,
*   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
*   See the License for the specific language governing permissions and
*  limitations under the License.
*/

import java.lang.reflect.Array;

/**

* Operations on arrays, primitive arrays (like int[]) and
* primitive wrapper arrays (like Integer[]).
* 
* This class tries to handle null input gracefully.
* An exception will not be thrown for a null
* array input. However, an Object array that contains a null
* element may throw an exception. Each method documents its behaviour.
*
* @author Stephen Colebourne
* @author Moritz Petersen
* @author 
* @author Maarten Coene
* @since 2.0
* @version $Id: ArrayUtils.java 632503 2008-03-01 00:21:52Z ggregory $
*/

public class Main {

 /**
  * The index value when an element is not found in a list or array: -1.
  * This value is returned by methods in this class and can also be used in comparisons with values returned by
  * various method from {@link java.util.List}.
  */
 public static final int INDEX_NOT_FOUND = -1;
 // int IndexOf
 //-----------------------------------------------------------------------
 /**
  * Finds the index of the given value in the array.
  *
  * This method returns {@link #INDEX_NOT_FOUND} (-1) for a null input array.
  * 
  * @param array  the array to search through for the object, may be null
  * @param valueToFind  the value to find
  * @return the index of the value within the array,
  *  {@link #INDEX_NOT_FOUND} (-1) if not found or null array input
  */
 public static int indexOf(int[] array, int valueToFind) {
     return indexOf(array, valueToFind, 0);
 }
 /**
  * Finds the index of the given value in the array starting at the given index.
  *
  * This method returns {@link #INDEX_NOT_FOUND} (-1) for a null input array.
  *
  * A negative startIndex is treated as zero. A startIndex larger than the array
  * length will return {@link #INDEX_NOT_FOUND} (-1).
  * 
  * @param array  the array to search through for the object, may be null
  * @param valueToFind  the value to find
  * @param startIndex  the index to start searching at
  * @return the index of the value within the array,
  *  {@link #INDEX_NOT_FOUND} (-1) if not found or null array input
  */
 public static int indexOf(int[] array, int valueToFind, int startIndex) {
     if (array == null) {
         return INDEX_NOT_FOUND;
     }
     if (startIndex < 0) {
         startIndex = 0;
     }
     for (int i = startIndex; i < array.length; i++) {
         if (valueToFind == array[i]) {
             return i;
         }
     }
     return INDEX_NOT_FOUND;
 }
 /**
  * Finds the last index of the given value within the array.
  *
  * This method returns {@link #INDEX_NOT_FOUND} (-1) for a null input array.
  * 
  * @param array  the array to travers backwords looking for the object, may be null
  * @param valueToFind  the object to find
  * @return the last index of the value within the array,
  *  {@link #INDEX_NOT_FOUND} (-1) if not found or null array input
  */
 public static int lastIndexOf(int[] array, int valueToFind) {
     return lastIndexOf(array, valueToFind, Integer.MAX_VALUE);
 }
 /**
  * Finds the last index of the given value in the array starting at the given index.
  *
  * This method returns {@link #INDEX_NOT_FOUND} (-1) for a null input array.
  *
  * A negative startIndex will return {@link #INDEX_NOT_FOUND} (-1). A startIndex larger than the
  * array length will search from the end of the array.
  * 
  * @param array  the array to traverse for looking for the object, may be null
  * @param valueToFind  the value to find
  * @param startIndex  the start index to travers backwards from
  * @return the last index of the value within the array,
  *  {@link #INDEX_NOT_FOUND} (-1) if not found or null array input
  */
 public static int lastIndexOf(int[] array, int valueToFind, int startIndex) {
     if (array == null) {
         return INDEX_NOT_FOUND;
     }
     if (startIndex < 0) {
         return INDEX_NOT_FOUND;
     } else if (startIndex >= array.length) {
         startIndex = array.length - 1;
     }
     for (int i = startIndex; i >= 0; i--) {
         if (valueToFind == array[i]) {
             return i;
         }
     }
     return INDEX_NOT_FOUND;
 }
 /**
  * Checks if the value is in the given array.
  *
  * The method returns false if a null array is passed in.
  * 
  * @param array  the array to search through
  * @param valueToFind  the value to find
  * @return true if the array contains the object
  */
 public static boolean contains(int[] array, int valueToFind) {
     return indexOf(array, valueToFind) != INDEX_NOT_FOUND;
 }

}</source>

Object Arrays: Searching for elements in a sorted object array

   <source lang="java">

public static int binarySearch(Object array[], Object key) public static int binarySearch(Object array[], Object key, Comparator c)</source>

B
H
I
L
M
N
R
Found M @ 4

Produces a new array containing the elements between the start and end indices.

   <source lang="java">

import java.lang.reflect.Array; /*

* Licensed to the Apache Software Foundation (ASF) under one or more
*  contributor license agreements.  See the NOTICE file distributed with
*  this work for additional information regarding copyright ownership.
*  The ASF licenses this file to You under the Apache License, Version 2.0
*  (the "License"); you may not use this file except in compliance with
*  the License.  You may obtain a copy of the License at
*
*      http://www.apache.org/licenses/LICENSE-2.0
*
*  Unless required by applicable law or agreed to in writing, software
*  distributed under the License is distributed on an "AS IS" BASIS,
*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
*  See the License for the specific language governing permissions and
*  limitations under the License.
*
*
*/

/**

* @author Stephen Colebourne
* @author Moritz Petersen
* @author 
* @author Maarten Coene
* @since 2.0
* @version $Id: ArrayUtils.java 632503 2008-03-01 00:21:52Z ggregory $
*/

public class Main {

 // Subarrays
 //-----------------------------------------------------------------------
 /**
  * Produces a new array containing the elements between
  * the start and end indices.
  *
  * The start index is inclusive, the end index exclusive.
  * Null array input produces null output.
  *
  * The component type of the subarray is always the same as
  * that of the input array. Thus, if the input is an array of type
  * Date, the following usage is envisaged:
  *

*

   * Date[] someDates = (Date[])ArrayUtils.subarray(allDates, 2, 5);
   *

  *
  * @param array  the array
  * @param startIndexInclusive  the starting index. Undervalue (<0)
  *      is promoted to 0, overvalue (>array.length) results
  *      in an empty array.
  * @param endIndexExclusive  elements up to endIndex-1 are present in the
  *      returned subarray. Undervalue (< startIndex) produces
  *      empty array, overvalue (>array.length) is demoted to
  *      array length.
  * @return a new array containing the elements between
  *      the start and end indices.
  * @since 2.1
  */
 public static Object[] subarray(Object[] array, int startIndexInclusive, int endIndexExclusive) {
     if (array == null) {
         return null;
     }
     if (startIndexInclusive < 0) {
         startIndexInclusive = 0;
     }
     if (endIndexExclusive > array.length) {
         endIndexExclusive = array.length;
     }
     int newSize = endIndexExclusive - startIndexInclusive;
     Class type = array.getClass().getComponentType();
     if (newSize <= 0) {
         return (Object[]) Array.newInstance(type, 0);
     }
     Object[] subarray = (Object[]) Array.newInstance(type, newSize);
     System.arraycopy(array, startIndexInclusive, subarray, 0, newSize);
     return subarray;
 }

}</source>

Returns an index into arra (or -1) where the character is not in the charset byte array.

   <source lang="java">

* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* Redistributions of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer.
*
* Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* Neither the name of the HSQL Development Group nor the names of its
* contributors may be used to endorse or promote products derived from this
* software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
* OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

/**

* Collection of static methods for operations on arrays
*
* @author Fred Toussi (fredt@users dot sourceforge.net)
* @version 1.9.0
* @since 1.7.2
*/

public class Main {

 /**
  * Returns an index into arra (or -1) where the character is not in the
  * charset byte array.
  */
 public static int findNotIn(byte[] arra, int start, int limit,
                             byte[] charset) {
     int k = 0;
     for (; k < limit; k++) {
         for (int i = 0; i < charset.length; i++) {
             if (arra[k] == charset[i]) {
                 continue;
             }
         }
         return k;
     }
     return -1;
 }

}</source>

Returns an int[] array of length segments containing the distribution count of the elements in unsorted int[] array with values between min and max (range).

   <source lang="java">

* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* Redistributions of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer.
*
* Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* Neither the name of the HSQL Development Group nor the names of its
* contributors may be used to endorse or promote products derived from this
* software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
* OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

/**

* Collection of routines for counting the distribution of the values
* in an int[] array.
*
* @author Fred Toussi (fredt@users dot sourceforge.net)
* @version 1.7.2
* @since 1.7.2
*/

public class ArrayCounter {

   /**
    * Returns an int[] array of length segments containing the distribution
    * count of the elements in unsorted int[] array with values between min
    * and max (range). Values outside the min-max range are ignored
    *
    * A usage example is determining the count of people of each age group
    * in a large int[] array containing the age of each person. Called with
    * (array, 16,0,79), it will return an int[16] with the first element
    * the count of people aged 0-4, the second element the count of those
    * aged 5-9, and so on. People above the age of 79 are excluded. If the
    * range is not a multiple of segments, the last segment will be cover a
    * smaller sub-range than the rest.
    *
    */
   public static int[] countSegments(int[] array, int elements,
                                     int segments, int start, int limit) {
       int[] counts   = new int[segments];
       long  interval = calcInterval(segments, start, limit);
       int   index    = 0;
       int   element  = 0;
       if (interval <= 0) {
           return counts;
       }
       for (int i = 0; i < elements; i++) {
           element = array[i];
           if (element < start || element >= limit) {
               continue;
           }
           index = (int) ((element - start) / interval);
           counts[index]++;
       }
       return counts;
   }
   /**
    * With an unsorted int[] array and with target a positive integer in the
    * range (1,array.length), finds the value in the range (start,limit) of the
    * largest element (rank) where the count of all smaller elements in that
    * range is less than or equals target. Parameter margin indicates the
    * margin of error in target
    *
    * In statistics, this can be used to calculate a median or quadrile value.
    * A usage example applied to an array of age values is to determine
    * the maximum age of a given number of people. With the example array
    * given in countSegments, rank(array, c, 6000, 18, 65, 0) will return an age
    * value between 18-64 (inclusive) and the count of all people aged between
    * 18 and the returned value(exclusive) will be less than or equal 6000.
    *
    */
   public static int rank(int[] array, int elements, int target, int start,
                          int limit, int margin) {
       final int segments     = 256;
       int       elementCount = 0;
       int       currentLimit = limit;
       for (;;) {
           long interval = calcInterval(segments, start, currentLimit);
           int[] counts = countSegments(array, elements, segments, start,
                                        currentLimit);
           for (int i = 0; i < counts.length; i++) {
               if (elementCount + counts[i] < target) {
                   elementCount += counts[i];
                   start        += interval;
               } else {
                   break;
               }
           }
           if (elementCount + margin >= target) {
               return start;
           }
           if (interval <= 1) {
               return start;
           }
           currentLimit = start + interval < limit ? (int) (start + interval)
                                                   : limit;
       }
   }
   /**
    * Helper method to calculate the span of the sub-interval. Simply returns
    * the cieling of ((limit - start) / segments) and accounts for invalid
    * start and limit combinations.
    */
   static long calcInterval(int segments, int start, int limit) {
       long range = limit - start;
       if (range < 0) {
           return 0;
       }
       int partSegment = (range % segments) == 0 ? 0
                                                 : 1;
       return (range / segments) + partSegment;
   }

}</source>

Returns the minimum value in an array.

   <source lang="java">

/*

* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements.  See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License.  You may obtain a copy of the License at
* 
*      http://www.apache.org/licenses/LICENSE-2.0
* 
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/

/**

* Provides extra functionality for Java Number classes.
*
* @author 
* @since 2.0
* @version $Id: NumberUtils.java 609475 2008-01-06 23:58:59Z bayard $
*/

public class Main {

 /**
  * Returns the minimum value in an array.
  * 
  * @param array  an array, must not be null or empty
  * @return the minimum value in the array
  * @throws IllegalArgumentException if array is null
  * @throws IllegalArgumentException if array is empty
  */
 public static long min(long[] array) {
     // Validates input
     if (array == null) {
         throw new IllegalArgumentException("The Array must not be null");
     } else if (array.length == 0) {
         throw new IllegalArgumentException("Array cannot be empty.");
     }
 
     // Finds and returns min
     long min = array[0];
     for (int i = 1; i < array.length; i++) {
         if (array[i] < min) {
             min = array[i];
         }
     }
 
     return min;
 }

}</source>

Returns true if all the references in array1 are equal to all the references in array2 (two null references are considered equal for this test).

   <source lang="java">

/*

* JCommon : a free general purpose class library for the Java(tm) platform
* 
*
* (C) Copyright 2000-2005, by Object Refinery Limited and Contributors.
*
* Project Info:  http://www.jfree.org/jcommon/index.html
*
* This library is free software; you can redistribute it and/or modify it
* under the terms of the GNU Lesser General Public License as published by
* the Free Software Foundation; either version 2.1 of the License, or
* (at your option) any later version.
*
* This library is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
* License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301,
* USA.
*
* [Java is a trademark or registered trademark of Sun Microsystems, Inc.
* in the United States and other countries.]
*
* -------------------
* ArrayUtilities.java
* -------------------
* (C) Copyright 2003-2005, by Object Refinery Limited.
*
* Original Author:  David Gilbert (for Object Refinery Limited);
* Contributor(s):   -;
*
* $Id: ArrayUtilities.java,v 1.7 2008/09/10 09:21:30 mungady Exp $
*
* Changes
* -------
* 21-Aug-2003 : Version 1 (DG);
* 04-Oct-2004 : Renamed ArrayUtils --> ArrayUtilities (DG);
*
*/

public class Main {

 /**
  * Returns true if all the references in array1
  * are equal to all the references in array2 (two
  * null references are considered equal for this test).
  *
  * @param array1  the first array (null permitted).
  * @param array2  the second array (null permitted).
  *
  * @return A boolean.
  */
 public static boolean equalReferencesInArrays(final Object[] array1,
                                               final Object[] array2) {
     if (array1 == null) {
         return (array2 == null);
     }
     if (array2 == null) {
         return false;
     }
     if (array1.length != array2.length) {
         return false;
     }
     for (int i = 0; i < array1.length; i++) {
         if (array1[i] == null) {
             if (array2[i] != null) {
                 return false;
             }
         }
         if (array2[i] == null) {
             if (array1[i] != null) {
                 return false;
             }
         }
         if (array1[i] != array2[i]) {
             return false;
         }
     }
     return true;
 }

}</source>

Searching Arrays

   <source lang="java">

public static int binarySearch(byte array[], byte key) public static int binarySearch(char array[], char key) public static int binarySearch(double array[], double key) public static int binarySearch(float array[], float key) public static int binarySearch(int array[], int key) public static int binarySearch(long array[], long key) public static int binarySearch(short array[], short key)</source>

Sorted array: [length: 10]
-9, -7, -3, -2, 0, 2, 4, 5, 6, 8
Found 2 @ 5
Didn"t find 1 @ -6
With 1 added: [length: 11]
-9, -7, -3, -2, 0, 1, 2, 4, 5, 6, 8

Sort array utilities

   <source lang="java">

/*

* Copyright 2004, 2005, 2006 Odysseus Software GmbH
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
*     http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/

import java.util.Arrays; import java.util.ruparator; import java.util.Iterator; import java.util.List; /**

* Utility class providing some useful static sort methods. The sort routines
* all return index permutations p such that data[p[0]],..,data[p[data.length-1]]
* is in sorted order. The data array itself is not modified.
* To actually rearrange the array elements, the inverse of p can be used to
* permute the array, such that data[0],..,data[data.length-1] is in sorted
* order. Use getIterator(p, data) to iterate in sorted order.
* A code example may show you what to do next:

*

 * String[] colors = { "red", "green", "blue" };
 * int[] p = SortUtils.sort(colors, new StringComparator());
 * // --> (colors[p[0]], colors[p[1]], colors[p[2]]) == ("blue","green","red")
 * Iterator iter = SortUtils.getIterator(p, colors)
 * // --> (iter.next(), iter.next(), iter.next()) == ("blue","green","red")
 * SortUtils.permute(SortUtils.inverse(p), colors, true);
 * // --> (colors[0], colors[1], colors[2]) == ("blue","green","red")
 *

* Stable sorts (preserving order of equal elements) are supported.
* Sorting is done using quick-sort mith median of 3 (and insertion-sort
* for small ranges).
*
* @author Christoph Beck
*/

public class SortUtils {

 /**
  * Helper class used to perform quicksort.
  *
  * @author Christoph Beck
  */
 static final class QuickSorter {
   private static final int INSERTIONSORT_THRESHOLD = 7;
   private final Object[] data;
   QuickSorter(Object[] data) {
     this.data = data;
   }
   private int compare(Comparator cmp, boolean stable, int i, int j) {
     int result = cmp.rupare(data[i], data[j]);
     if (result == 0 && stable && i != j) {
       result = i < j ? -1 : 1;
     }
     return result;
   }
   private int med3(Comparator cmp, int a, int b, int c) {
       return  (compare(cmp, false, a, b) < 0 ?
           (compare(cmp, false, b, c) < 0 ? b : compare(cmp, false, a, c) < 0 ? c : a) :
           (compare(cmp, false, b, c) > 0 ? b : compare(cmp, false, a, c) < 0 ? c : a));
   }
   private int pivot(int[] indices, Comparator cmp, int lo, int hi) {
     return med3(cmp, indices[lo + 1], indices[(lo + hi) / 2], indices[hi - 1]);
   }
   private void swap(int[] indices, int i, int j) {
     int tmp = indices[i];
     indices[i] = indices[j];
     indices[j] = tmp;
   }
   private void insertionSort(int[] indices, Comparator cmp, boolean stable, int lo, int hi) {
     for (int i = lo; i <= hi; i++) {
           for (int j = i; j > lo && compare(cmp, stable, indices[j-1], indices[j]) > 0; j--) {
             swap(indices, j-1, j);
           }
         }
   }
   private void quickSort(int[] indices, Comparator cmp, boolean stable, int lo0, int hi0) {
     int pivot = pivot(indices, cmp, lo0, hi0);
     int lo = lo0, hi = hi0;
     while (lo <= hi) {
       while (lo < hi0 && compare(cmp, stable, pivot, indices[lo]) > 0)
         ++lo;
       while (hi > lo0 && compare(cmp, stable, pivot, indices[hi]) < 0)
         --hi;
       if (lo <= hi) {
         swap(indices, lo++, hi--);
       }
     }
     sort(indices, cmp, stable, lo0, hi);
     sort(indices, cmp, stable, lo, hi0);
   }
   void sort(int[] indices, Comparator cmp, boolean stable, int lo, int hi) {
     if (hi - lo < INSERTIONSORT_THRESHOLD) {
       insertionSort(indices, cmp, stable, lo, hi);
     } else {
       quickSort(indices, cmp, stable, lo, hi);
     }
   }
   void sort(int[] indices, Comparator cmp, boolean stable) {
     sort(indices, cmp, stable, 0, indices.length - 1);
   }
   int[] sort(Comparator cmp, boolean stable) {
     int[] indices = identity(data.length);
     sort(indices, cmp, stable);
     return indices;
   }
 }
 /**
  * Create identity permutation, that is {0, 1, ..., n}
  */
 public static int[] identity(int n) {
   int[] indices = new int[n];
   for (int i = 0; i < n; i++)
     indices[i] = i;
   return indices;
 }
 /**
  * Create reverse permutation, that is {n-1, .... 1, 0}
  */
 public static int[] reverse(int n) {
   int[] indices = new int[n];
   for (int i = 0; i < n; i++)
     indices[i] = n - i - 1;
   return indices;
 }
 /**
  * Compute inverse permutation
  */
 public static int[] inverse(int[] p) {
   int[] pi = new int[p.length];
   for (int i = 0; i < pi.length; i++)
     pi[p[i]] = i;
   return pi;
 }
 /**
  * Rearrange the specified data according to the specified permutation.
  * That is, the array is rearranged, such that
  * data_after[p[i]] == data_before[i].
  * @param data data to be permuted
  * @param p the permutation
  * @param clone if true, rearrange a clone instead of the original data;
  * @return the permuted array (which is the original reference if clone == false)
  */
 public static Object[] permute(int[] p, Object[] data, boolean clone) {
   Object[] permuted = null;
   if (clone) {
     permuted = (Object[])data.clone();
     for (int i = 0; i < data.length; i++)
       permuted[p[i]] = data[i];
   } else {
     // run thru cycles
     int i = 0;
     while (i < p.length) {
       if (p[i] < 0 || p[i] == i) // skip already handled and cycles of length 1
         ++i;
       else { // start a new cycle
         int j = p[i];
         Object save = data[i];
         while (p[j] >= 0) {
           Object tmp = data[j];
           data[j] = save;
           save = tmp;
           i = j;
           j = p[j];
           p[i] = -1;
         }
       }
     }
     permuted = data;
   }
   return permuted;
 }
 /**
  * Answer iterator, which iterates over specified data array according
  * to the specified permutation, that is
  * data[p[0]],..,data[p[data.length-1]]
  */
 public static Iterator getIterator(final int[] p, final Object[] data) {
   return new Iterator() {
     int pos = 0;
     public boolean hasNext() {
       return pos < data.length;
     }
     public Object next() {
       return data[p[pos++]];
     }
     public void remove() {
       throw new UnsupportedOperationException("Cannot remove from immutable iterator!");
     }
   };
 }
 /**
  * Answer iterator, which iterates over specified data list according
  * to the specified permutation, that is
  * data.get(p[0]),..,data.get(p[data.length-1])
  */
 public static Iterator getIterator(final int[] p, final List data) {
   return new Iterator() {
     int pos = 0;
     public boolean hasNext() {
       return pos < data.size();
     }
     public Object next() {
       return data.get(p[pos++]);
     }
     public void remove() {
       throw new UnsupportedOperationException("Cannot remove from immutable iterator!");
     }
   };
 }

// /** // * An improved heap builder. // * Assumes children of i at 2i and 2i+1 (requires i>0) // */ // private static void cheap(int[] indices, Object[] data, Comparator comparator, int i, int j) { // int k = (i << 1); // if (k > j) // return; // while (k < j) { // if (comparator.rupare(data[indices[k]], data[indices[k + 1]]) < 0) // k++; // k <<= 1; // } // if (k > j) // k >>= 1; // while (comparator.rupare(data[indices[k]], data[indices[i]]) < 0) // k >>= 1; // int t1 = indices[i], t2; // while (k > i) { // t2 = indices[k]; // indices[k] = t1; // k >>= 1; // t1 = indices[k]; // indices[k] = t2; // k >>= 1; // } // if (k == i) // indices[i] = t1; // } // // /** // * Do a (clever) heapsort. // * // * @param comparator Comparator object specifying the sort order. // */ // public static void cheapSort(int[] indices, Object[] data, Comparator comparator) { // int n = data.length; // if (n > 1) { // int i; // int m = 0; // for (i = 1; i < n; i++) // if (comparator.rupare(data[indices[i]], data[indices[m]]) < 0) // m = i; // if (m > 0) { // int t = indices[0]; // indices[0] = indices[m]; // indices[m] = t; // } // if (n > 2) { // for (i = n / 2; i > 1; i--) // cheap(indices, data, comparator, i, n - 1); // for (i = n - 1; i > 1; i--) { // cheap(indices, data, comparator, 1, i); // int t = indices[1]; // indices[1] = indices[i]; // indices[i] = t; // } // } // } // } // // /** // * Perform a cheapsort // */ // public static int[] cheapSort(Object[] data, Comparator comparator) { // int[] indices = identity(data.length); // cheapSort(indices, data, comparator); // return indices; // }

 /**
  * Do a sort on indices.
  * @param data data to be sorted
  * @param comparator comparator to use
  * @param stable do a stable sort iff true
  * @param indices into data (any permutation of 0,..data.length-1).
  */
 public static void sort(int[] indices, Object[] data, Comparator comparator, boolean stable) {
   new QuickSorter(data).sort(indices, comparator, stable);
 }
 /**
  * Do a sort on indices.
  * @param data data to be sorted
  * @param comparator comparator to use
  * @param stable do a stable sort iff true
  * @return permutation p such that data[p[0]],..,data[p[data.length-1]] is in sorted order
  */
 public static int[] sort(Object[] data, Comparator comparator, boolean stable) {
   int[] indices = identity(data.length);
   sort(indices, data, comparator, stable);
   return indices;
 }
 /**
  * Do an unstable sort.
  * @param data data to be sorted
  * @param comparator comparator to use
  * @return permutation p such that data[p[0]],..,data[p[data.length-1]] is in sorted order
  */
 public static int[] sort(Object[] data, Comparator comparator) {
   return sort(data, comparator, false);
 }
 /**
  * Do an unstable sort.
  * @param data data to be sorted
  * @param indices into data (permutation of 0,..data.length-1).
  */
 public static void sort(int[] indices, Object[] data, Comparator comparator) {
   sort(indices, data, comparator, false);
 }
 /**
  * Test method
  */
 public static void main(String[] args) {
   Comparator cmp = new Comparator() {
     public int compare(Object o1, Object o2) {
       return ((Comparable)o1).rupareTo(o2);
     }
   };
   int n = 1000000;
   if (args.length == 1)
     try {
       n = Integer.parseInt(args[0]);
     } catch (Exception e) {
       System.err.println(e);
     }
   System.out.println("Generating " + n + " random integers...");
   java.util.Random random = new java.util.Random();
   Integer[] data = new Integer[n];
   for (int i = 0; i < n; i++) {
     data[i] = new Integer(Math.abs(random.nextInt()));

// data[i] = new Integer(i);

   }
   int[] indices;
   long time;
   System.out.print("Arrays.sort...");
   time = System.currentTimeMillis();
   Integer[] clone = (Integer[])data.clone();
   Arrays.sort(clone, cmp);
   System.out.println(System.currentTimeMillis()-time  + "ms");
   System.out.print("quicksort...");
   indices = identity(n);
   time = System.currentTimeMillis();
   sort(indices, data, cmp, false);
   System.out.println(System.currentTimeMillis()-time  + "ms");
   for (int i = 1; i < n; i++)
     if (cmp.rupare(data[indices[i-1]], data[indices[i]]) > 0)
       System.err.println("proplem: quickSort at " + i);
   System.out.print("quicksort stable...");

// indices = identity(n);

   time = System.currentTimeMillis();
   sort(indices, data, cmp, true);
   System.out.println(System.currentTimeMillis()-time + "ms");
   for (int i = 1; i < n; i++) {
     int res = cmp.rupare(data[indices[i-1]], data[indices[i]]);
     if (res > 0)
       System.err.println("proplem: quickSort stable at " + i);
     if (res == 0 && indices[i-1] > indices[i])
       System.err.println("proplem: quickSort stable (not stable) at " + i);
   }

// System.out.print("cheapsort..."); // time = System.currentTimeMillis(); // indices = cheapSort(data, cmp); // System.out.println(System.currentTimeMillis()-time + "ms"); // for (int i = 1; i < n; i++) // if (cmp.rupare(data[indices[i-1]], data[indices[i]]) > 0) // System.err.println("proplem: cheapSort at " + i);

   System.out.print("permutate copy...");
   time = System.currentTimeMillis();
   Object[] data_copy = permute(inverse(indices), data, true);
   System.out.println(System.currentTimeMillis()-time + "ms");
   for (int i = 1; i < n; i++)
     if (cmp.rupare(data_copy[i-1], data_copy[i]) > 0)
       System.err.println("proplem: permute copy at " + i);
   System.out.print("permutate original...");
   time = System.currentTimeMillis();
   permute(inverse(indices), data, false);
   System.out.println(System.currentTimeMillis()-time + "ms");
   for (int i = 1; i < n; i++)
     if (cmp.rupare(data[i-1], data[i]) > 0)
       System.err.println("proplem: permute original at " + i);
 }

}</source>

Sorting Arrays

   <source lang="java">

public static void sort(byte array[]) public static void sort(byte array[], int fromIndex, int toIndex) public static void sort(char array[]) public static void sort(char array[], int fromIndex, int toIndex) public static void sort(double array[]) public static void sort(double array[], int fromIndex, int toIndex) public static void sort(float array[]) public static void sort(float array[], int fromIndex, int toIndex) public static void sort(int array[]) public static void sort(int array[], int fromIndex, int toIndex) public static void sort(long array[]) public static void sort(long array[], int fromIndex, int toIndex) public static void sort(short array[]) public static void sort(short array[], int fromIndex, int toIndex)</source>

Sorting arrays of objects

   <source lang="java">

public static void sort(Object array[]) public static void sort(Object array[], int fromIndex, int toIndex) public static void sort(Object array[], Comparator c) public static void sort(Object array[], int fromIndex, int toIndex, Comparator c)</source>

A
B
C

Sorting a subset of array elements

   <source lang="java">

import java.util.Arrays; public class MainClass {

 public static void main(String[] a) {
   int array[] = { 2, 5, -2, 6, -3, 8, 0, -7, -9, 4 };
   Arrays.sort(array, 3, 7);
   for (int i : array) {
     System.out.println(i);
   }
 }

}</source>

Test the equality of two object arrays

   <source lang="java">

import java.lang.reflect.Array; /*

* JBoss, Home of Professional Open Source
* Copyright 2005, JBoss Inc., and individual contributors as indicated
* by the @authors tag. See the copyright.txt in the distribution for a
* full listing of individual contributors.
*
* This is free software; you can redistribute it and/or modify it
* under the terms of the GNU Lesser General Public License as
* published by the Free Software Foundation; either version 2.1 of
* the License, or (at your option) any later version.
*
* This software is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this software; if not, write to the Free
* Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
* 02110-1301 USA, or see the FSF site: http://www.fsf.org.
*/

public class Main {

 /**
  * Test the equality of two object arrays.
  *
  * @param a       The first array.
  * @param b       The second array.
  * @param deep    True to traverse elements which are arrays.
  * @return        True if arrays are equal.
  */
 public static boolean equals(final Object[] a, final Object[] b,
                              final boolean deep)
 {
    if (a == b) return true;
    if (a == null || b == null) return false;
    if (a.length != b.length) return false;
    for (int i=0; i<a.length; i++) {
       Object x = a[i];
       Object y = b[i];
       if (x != y) return false;
       if (x == null || y == null) return false;
       if (deep) {
          if (x instanceof Object[] && y instanceof Object[]) {
             if (! equals((Object[])x, (Object[])y, true)) return false;
          }
          else {
             return false;
          }
       }
       if (! x.equals(y)) return false;
    }
    return true;
 }
 /**
  * Test the equality of two object arrays.
  *
  * @param a    The first array.
  * @param b    The second array.
  * @return     True if arrays are equal.
  */
 public static boolean equals(final Object[] a, final Object[] b) {
    return equals(a, b, true);
 }

}</source>

Java Tutorial/Collections/Array Sort Search

Содержание

FastQSorts the [l,r] partition (inclusive) of the specfied array of Rows, using the comparator.

Finds the index of the given object in the array.

Finds the index of the given object in the array starting at the given index.

Finds the last index of the given object in the array starting at the given index.

Finds the value in the range (start,limit) of the largest element (rank) where the count of all smaller elements in that range is less than or equals target.

Get the element index or last index among a boolean type array

Get the index and last index of an int type value array

Object Arrays: Searching for elements in a sorted object array

Produces a new array containing the elements between the start and end indices.

Returns an index into arra (or -1) where the character is not in the charset byte array.

Returns an int[] array of length segments containing the distribution count of the elements in unsorted int[] array with values between min and max (range).

Returns the minimum value in an array.

Returns true if all the references in array1 are equal to all the references in array2 (two null references are considered equal for this test).

Searching Arrays

Sort array utilities

Sorting Arrays

Sorting arrays of objects

Sorting a subset of array elements

Test the equality of two object arrays

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Разделы

Навигация

Инструменты