Java Tutorial/Collections/Array Sort Search
Версия от 17:44, 31 мая 2010; (обсуждение)
Содержание
- 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.
/* Copyright (c) 1995-2000, The Hypersonic SQL 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 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);
}
Finds the index of the given object in the array.
/* Copyright 2004 The Apache Software Foundation
*
* 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 <code>int[]</code>) and
* primitive wrapper arrays (like <code>Integer[]</code>).
*
* This class tries to handle <code>null</code> input gracefully.
* An exception will not be thrown for a <code>null</code>
* array input. However, an Object array that contains a <code>null</code>
* 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} (<code>-1</code>) for a <code>null</code> input array.
*
* @param array the array to search through for the object, may be <code>null</code>
* @param objectToFind the object to find, may be <code>null</code>
* @return the index of the object within the array,
* {@link #INDEX_NOT_FOUND} (<code>-1</code>) if not found or <code>null</code> 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} (<code>-1</code>) for a <code>null</code> input array.
*
* A negative startIndex is treated as zero. A startIndex larger than the array
* length will return {@link #INDEX_NOT_FOUND} (<code>-1</code>).
*
* @param array the array to search through for the object, may be <code>null</code>
* @param objectToFind the object to find, may be <code>null</code>
* @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} (<code>-1</code>) if not found or <code>null</code> 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;
}
}
Finds the index of the given object in the array starting at the given index.
/* Copyright 2004 The Apache Software Foundation
*
* 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 <code>int[]</code>) and
* primitive wrapper arrays (like <code>Integer[]</code>).
*
* This class tries to handle <code>null</code> input gracefully.
* An exception will not be thrown for a <code>null</code>
* array input. However, an Object array that contains a <code>null</code>
* 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} (<code>-1</code>) for a <code>null</code> input array.
*
* A negative startIndex is treated as zero. A startIndex larger than the array
* length will return {@link #INDEX_NOT_FOUND} (<code>-1</code>).
*
* @param array the array to search through for the object, may be <code>null</code>
* @param objectToFind the object to find, may be <code>null</code>
* @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} (<code>-1</code>) if not found or <code>null</code> 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;
}
}
Finds the last index of the given object in the array starting at the given index.
/* Copyright 2004 The Apache Software Foundation
*
* 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 <code>int[]</code>) and
* primitive wrapper arrays (like <code>Integer[]</code>).
*
* This class tries to handle <code>null</code> input gracefully.
* An exception will not be thrown for a <code>null</code>
* array input. However, an Object array that contains a <code>null</code>
* 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} (<code>-1</code>) for a <code>null</code> input array.
*
* A negative startIndex will return {@link #INDEX_NOT_FOUND} (<code>-1</code>). 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 <code>null</code>
* @param objectToFind the object to find, may be <code>null</code>
* @param startIndex the start index to travers backwards from
* @return the last index of the object within the array,
* {@link #INDEX_NOT_FOUND} (<code>-1</code>) if not found or <code>null</code> 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;
}
}
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.
/* 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.
*/
/**
* 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;
}
}
Get the element index or last index among a boolean type array
/* Copyright 2004 The Apache Software Foundation
*
* 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 <code>int[]</code>) and
* primitive wrapper arrays (like <code>Integer[]</code>).
*
* This class tries to handle <code>null</code> input gracefully.
* An exception will not be thrown for a <code>null</code>
* array input. However, an Object array that contains a <code>null</code>
* 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: <code>-1</code>.
* 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} (<code>-1</code>) for a <code>null</code> input array.
*
* @param array the array to search through for the object, may be <code>null</code>
* @param valueToFind the value to find
* @return the index of the value within the array,
* {@link #INDEX_NOT_FOUND} (<code>-1</code>) if not found or <code>null</code> 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} (<code>-1</code>) for a <code>null</code> input array.
*
* A negative startIndex is treated as zero. A startIndex larger than the array
* length will return {@link #INDEX_NOT_FOUND} (<code>-1</code>).
*
* @param array the array to search through for the object, may be <code>null</code>
* @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} (<code>-1</code>) if not found or <code>null</code>
* 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} (<code>-1</code>) if
* <code>null</code> array input.
*
* @param array the array to travers backwords looking for the object, may be <code>null</code>
* @param valueToFind the object to find
* @return the last index of the value within the array,
* {@link #INDEX_NOT_FOUND} (<code>-1</code>) if not found or <code>null</code> 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} (<code>-1</code>) for a <code>null</code> input array.
*
* A negative startIndex will return {@link #INDEX_NOT_FOUND} (<code>-1</code>). 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 <code>null</code>
* @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} (<code>-1</code>) if not found or <code>null</code> 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 <code>false</code> if a <code>null</code> array is passed in.
*
* @param array the array to search through
* @param valueToFind the value to find
* @return <code>true</code> 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 <code>null</code>.
*
* @param array the array to test
* @return <code>true</code> if the array is empty or <code>null</code>
* @since 2.1
*/
public static boolean isEmpty(boolean[] array) {
if (array == null || array.length == 0) {
return true;
}
return false;
}
}
Get the index and last index of an int type value array
/* Copyright 2004 The Apache Software Foundation
*
* 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 <code>int[]</code>) and
* primitive wrapper arrays (like <code>Integer[]</code>).
*
* This class tries to handle <code>null</code> input gracefully.
* An exception will not be thrown for a <code>null</code>
* array input. However, an Object array that contains a <code>null</code>
* 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: <code>-1</code>.
* 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} (<code>-1</code>) for a <code>null</code> input array.
*
* @param array the array to search through for the object, may be <code>null</code>
* @param valueToFind the value to find
* @return the index of the value within the array,
* {@link #INDEX_NOT_FOUND} (<code>-1</code>) if not found or <code>null</code> 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} (<code>-1</code>) for a <code>null</code> input array.
*
* A negative startIndex is treated as zero. A startIndex larger than the array
* length will return {@link #INDEX_NOT_FOUND} (<code>-1</code>).
*
* @param array the array to search through for the object, may be <code>null</code>
* @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} (<code>-1</code>) if not found or <code>null</code> 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} (<code>-1</code>) for a <code>null</code> input array.
*
* @param array the array to travers backwords looking for the object, may be <code>null</code>
* @param valueToFind the object to find
* @return the last index of the value within the array,
* {@link #INDEX_NOT_FOUND} (<code>-1</code>) if not found or <code>null</code> 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} (<code>-1</code>) for a <code>null</code> input array.
*
* A negative startIndex will return {@link #INDEX_NOT_FOUND} (<code>-1</code>). 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 <code>null</code>
* @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} (<code>-1</code>) if not found or <code>null</code> 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 <code>false</code> if a <code>null</code> array is passed in.
*
* @param array the array to search through
* @param valueToFind the value to find
* @return <code>true</code> if the array contains the object
*/
public static boolean contains(int[] array, int valueToFind) {
return indexOf(array, valueToFind) != INDEX_NOT_FOUND;
}
}
Object Arrays: Searching for elements in a sorted object array
public static int binarySearch(Object array[], Object key)
public static int binarySearch(Object array[], Object key, Comparator c)
B H I L M N R Found M @ 4
Produces a new array containing the elements between the start and end indices.
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
* <code>Date</code>, the following usage is envisaged:
*
* <pre>
* Date[] someDates = (Date[])ArrayUtils.subarray(allDates, 2, 5);
* </pre>
*
* @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;
}
}
Returns an index into arra (or -1) where the character is not in the charset byte array.
/* 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.
*/
/**
* 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;
}
}
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).
/* 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.
*/
/**
* 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;
}
}
Returns the minimum value in an 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.
*/
/**
* 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 <code>array</code> is <code>null</code>
* @throws IllegalArgumentException if <code>array</code> 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;
}
}
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).
/*
* 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 <code>true</code> if all the references in <code>array1</code>
* are equal to all the references in <code>array2</code> (two
* <code>null</code> references are considered equal for this test).
*
* @param array1 the first array (<code>null</code> permitted).
* @param array2 the second array (<code>null</code> 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;
}
}
Searching Arrays
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)
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
/*
* 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 <code>getIterator(p, data)</code> to iterate in sorted order.
* A code example may show you what to do next:
* <pre>
* 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")
* </pre>
* 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 <code>{0, 1, ..., n}</code>
*/
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 <code>{n-1, .... 1, 0}</code>
*/
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
* <code>data_after[p[i]] == data_before[i]</code>.
* @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
* <code>data[p[0]],..,data[p[data.length-1]]</code>
*/
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
* <code>data.get(p[0]),..,data.get(p[data.length-1])</code>
*/
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);
}
}
Sorting Arrays
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)
-3 -2 2 5 6
Sorting arrays of objects
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)
A B C
Sorting a subset of array elements
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);
}
}
}
2 5 -2 -3 0 6 8 -7 -9 4
Test the equality of two object arrays
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);
}
}
