diff options
Diffstat (limited to 'libjava/java/util')
| -rw-r--r-- | libjava/java/util/AbstractCollection.java | 339 | ||||
| -rw-r--r-- | libjava/java/util/AbstractList.java | 558 | ||||
| -rw-r--r-- | libjava/java/util/Arrays.java | 1757 |
3 files changed, 2654 insertions, 0 deletions
diff --git a/libjava/java/util/AbstractCollection.java b/libjava/java/util/AbstractCollection.java new file mode 100644 index 00000000000..800204441de --- /dev/null +++ b/libjava/java/util/AbstractCollection.java @@ -0,0 +1,339 @@ +/* AbstractCollection.java -- Abstract implementation of most of Collection + Copyright (C) 1998 Free Software Foundation, Inc. + +This file is part of GNU Classpath. + +GNU Classpath is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU Classpath 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 +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Classpath; see the file COPYING. If not, write to the +Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA +02111-1307 USA. + +As a special exception, if you link this library with other files to +produce an executable, this library does not by itself cause the +resulting executable to be covered by the GNU General Public License. +This exception does not however invalidate any other reasons why the +executable file might be covered by the GNU General Public License. */ + + +package java.util; + +import java.lang.reflect.Array; + +/** + * A basic implementation of most of the methods in the Collection interface to + * make it easier to create a collection. To create an unmodifiable Collection, + * just subclass AbstractCollection and provide implementations of the + * iterator() and size() methods. The Iterator returned by iterator() need only + * provide implementations of hasNext() and next() (that is, it may throw an + * UnsupportedOperationException if remove() is called). To create a modifiable + * Collection, you must in addition provide an implementation of the + * add(Object) method and the Iterator returned by iterator() must provide an + * implementation of remove(). Other methods should be overridden if the + * backing data structure allows for a more efficient implementation. The + * precise implementation used by AbstractCollection is documented, so that + * subclasses can tell which methods could be implemented more efficiently. + */ +public abstract class AbstractCollection implements Collection { + + /** + * Return an Iterator over this collection. The iterator must provide the + * hasNext and next methods and should in addition provide remove if the + * collection is modifiable. + */ + public abstract Iterator iterator(); + + /** + * Return the number of elements in this collection. + */ + public abstract int size(); + + /** + * Add an object to the collection. This implementation always throws an + * UnsupportedOperationException - it should be overridden if the collection + * is to be modifiable. + * + * @param o the object to add + * @return true if the add operation caused the Collection to change + * @exception UnsupportedOperationException if the add operation is not + * supported on this collection + */ + public boolean add(Object o) { + throw new java.lang.UnsupportedOperationException(); + } + + /** + * Add all the elements of a given collection to this collection. This + * implementation obtains an Iterator over the given collection and iterates + * over it, adding each element with the add(Object) method (thus this method + * will fail with an UnsupportedOperationException if the add method does). + * + * @param c the collection to add the elements of to this collection + * @return true if the add operation caused the Collection to change + * @exception UnsupportedOperationException if the add operation is not + * supported on this collection + */ + public boolean addAll(Collection c) { + Iterator i = c.iterator(); + boolean modified = false; + while (i.hasNext()) { + modified |= add(i.next()); + } + return modified; + } + + /** + * Remove all elements from the collection. This implementation obtains an + * iterator over the collection and calls next and remove on it repeatedly + * (thus this method will fail with an UnsupportedOperationException if the + * Iterator's remove method does) until there are no more elements to remove. + * Many implementations will have a faster way of doing this. + * + * @exception UnsupportedOperationException if the Iterator returned by + * iterator does not provide an implementation of remove + */ + public void clear() { + Iterator i = iterator(); + while (i.hasNext()) { + i.next(); + i.remove(); + } + } + + /** + * Test whether this collection contains a given object. That is, if the + * collection has an element e such that (o == null ? e == null : + * o.equals(e)). This implementation obtains an iterator over the collection + * and iterates over it, testing each element for equality with the given + * object. If it is equal, true is returned. Otherwise false is returned when + * the end of the collection is reached. + * + * @param o the object to remove from this collection + * @return true if this collection contains an object equal to o + */ + public boolean contains(Object o) { + Iterator i = iterator(); + + // This looks crazily inefficient, but it takes the test o==null outside + // the loop, saving time, and also saves needing to store the result of + // i.next() each time. + if (o == null) { + while (i.hasNext()) { + if (i.next() == null) { + return true; + } + } + } else { + while (i.hasNext()) { + if (o.equals(i.next())) { + return true; + } + } + } + return false; + } + + /** + * Tests whether this collection contains all the elements in a given + * collection. This implementation iterates over the given collection, + * testing whether each element is contained in this collection. If any one + * is not, false is returned. Otherwise true is returned. + * + * @param c the collection to test against + * @return true if this collection contains all the elements in the given + * collection + */ + public boolean containsAll(Collection c) { + Iterator i = c.iterator(); + while (i.hasNext()) { + if (!contains(i.next())) { + return false; + } + } + return true; + } + + /** + * Test whether this collection is empty. This implementation returns + * size() == 0. + * + * @return true if this collection is empty. + */ + public boolean isEmpty() { + return size() == 0; + } + + /** + * Remove a single instance of an object from this collection. That is, + * remove one element e such that (o == null ? e == null : o.equals(e)), if + * such an element exists. This implementation obtains an iterator over the + * collection and iterates over it, testing each element for equality with + * the given object. If it is equal, it is removed by the iterator's remove + * method (thus this method will fail with an UnsupportedOperationException + * if the Iterator's remove method does). After the first element has been + * removed, true is returned; if the end of the collection is reached, false + * is returned. + * + * @param o the object to remove from this collection + * @return true if the remove operation caused the Collection to change, or + * equivalently if the collection did contain o. + * @exception UnsupportedOperationException if this collection's Iterator + * does not support the remove method + */ + public boolean remove(Object o) { + Iterator i = iterator(); + + // This looks crazily inefficient, but it takes the test o==null outside + // the loop, saving time, and also saves needing to store the result of + // i.next() each time. + if (o == null) { + while (i.hasNext()) { + if (i.next() == null) { + i.remove(); + return true; + } + } + } else { + while (i.hasNext()) { + if (o.equals(i.next())) { + i.remove(); + return true; + } + } + } + return false; + } + + /** + * Remove from this collection all its elements that are contained in a given + * collection. This implementation iterates over this collection, and for + * each element tests if it is contained in the given collection. If so, it + * is removed by the Iterator's remove method (thus this method will fail + * with an UnsupportedOperationException if the Iterator's remove method + * does). + * + * @param c the collection to remove the elements of + * @return true if the remove operation caused the Collection to change + * @exception UnsupportedOperationException if this collection's Iterator + * does not support the remove method + */ + public boolean removeAll(Collection c) { + Iterator i = iterator(); + boolean changed = false; + while (i.hasNext()) { + if (c.contains(i.next())) { + i.remove(); + changed = true; + } + } + return changed; + } + + /** + * Remove from this collection all its elements that are not contained in a + * given collection. This implementation iterates over this collection, and + * for each element tests if it is contained in the given collection. If not, + * it is removed by the Iterator's remove method (thus this method will fail + * with an UnsupportedOperationException if the Iterator's remove method + * does). + * + * @param c the collection to retain the elements of + * @return true if the remove operation caused the Collection to change + * @exception UnsupportedOperationException if this collection's Iterator + * does not support the remove method + */ + public boolean retainAll(Collection c) { + Iterator i = iterator(); + boolean changed = false; + while (i.hasNext()) { + if (!c.contains(i.next())) { + i.remove(); + changed = true; + } + } + return changed; + } + + /** + * Return an array containing the elements of this collection. This + * implementation creates an Object array of size size() and then iterates + * over the collection, setting each element of the array from the value + * returned by the iterator. + * + * @return an array containing the elements of this collection + */ + public Object[] toArray() { + Object[] a = new Object[size()]; + Iterator i = iterator(); + for (int pos = 0; pos < a.length; pos++) { + a[pos] = i.next(); + } + return a; + } + + /** + * Copy the collection into a given array if it will fit, or into a + * dynamically created array of the same run-time type as the given array if + * not. If there is space remaining in the array, the first element after the + * end of the collection is set to null (this is only useful if the + * collection is known to contain no null elements, however). This + * implementation first tests whether the given array is large enough to hold + * all the elements of the collection. If not, the reflection API is used to + * allocate a new array of the same run-time type. Next an iterator is + * obtained over the collection and the elements are placed in the array as + * they are returned by the iterator. Finally the first spare element, if + * any, of the array is set to null, and the created array is returned. + * + * @param a the array to copy into, or of the correct run-time type + * @return the array that was produced + * @exception ClassCastException if the type of the array precludes holding + * one of the elements of the Collection + */ + public Object[] toArray(Object[] a) { + final int n = size(); + if (a.length < n) { + a = (Object[])Array.newInstance(a.getClass().getComponentType(), n); + } + Iterator i = iterator(); + for (int pos = 0; pos < n; pos++) { + a[pos] = i.next(); + } + if (a.length > n) { + a[n] = null; + } + return a; + } + + /** + * Creates a String representation of the Collection. The string returned is + * of the form "[a, b, ...]" where a and b etc are the results of calling + * toString on the elements of the collection. This implementation obtains an + * Iterator over the Collection and adds each element to a StringBuffer as it + * is returned by the iterator. + * + * @return a String representation of the Collection + */ + public String toString() { + StringBuffer s = new StringBuffer(); + s.append('['); + Iterator i = iterator(); + boolean more = i.hasNext(); + while(more) { + s.append(i.next()); + if (more = i.hasNext()) { + s.append(", "); + } + } + s.append(']'); + return s.toString(); + } +} diff --git a/libjava/java/util/AbstractList.java b/libjava/java/util/AbstractList.java new file mode 100644 index 00000000000..da76a8b3104 --- /dev/null +++ b/libjava/java/util/AbstractList.java @@ -0,0 +1,558 @@ +/* AbstractList.java -- Abstract implementation of most of List + Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc. + +This file is part of GNU Classpath. + +GNU Classpath is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU Classpath 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 +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Classpath; see the file COPYING. If not, write to the +Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA +02111-1307 USA. + +As a special exception, if you link this library with other files to +produce an executable, this library does not by itself cause the +resulting executable to be covered by the GNU General Public License. +This exception does not however invalidate any other reasons why the +executable file might be covered by the GNU General Public License. */ + + +// TO DO: +// ~ Doc comments for almost everything. +// ~ Better general commenting + +package java.util; + +/** + * A basic implementation of most of the methods in the List interface to make + * it easier to create a List based on a random-access data structure. To + * create an unmodifiable list, it is only necessary to override the size() and + * get(int) methods (this contrasts with all other abstract collection classes + * which require an iterator to be provided). To make the list modifiable, the + * set(int, Object) method should also be overridden, and to make the list + * resizable, the add(int, Object) and remove(int) methods should be overridden + * too. Other methods should be overridden if the backing data structure allows + * for a more efficient implementation. The precise implementation used by + * AbstractList is documented, so that subclasses can tell which methods could + * be implemented more efficiently. + */ +public abstract class AbstractList extends AbstractCollection implements List { + + /** + * A count of the number of structural modifications that have been made to + * the list (that is, insertions and removals). + */ + protected transient int modCount = 0; + + public abstract Object get(int index); + + public void add(int index, Object o) { + throw new UnsupportedOperationException(); + } + + public boolean add(Object o) { + add(size(), o); + return true; + } + + public boolean addAll(int index, Collection c) { + Iterator i = c.iterator(); + if (i.hasNext()) { + do { + add(index++, i.next()); + } while (i.hasNext()); + return true; + } else { + return false; + } + } + + public void clear() { + removeRange(0, size()); + } + + public boolean equals(Object o) { + if (o == this) { + return true; + } else if (!(o instanceof List)) { + return false; + } else { + Iterator i1 = iterator(); + Iterator i2 = ((List)o).iterator(); + while (i1.hasNext()) { + if (!i2.hasNext()) { + return false; + } else { + Object e = i1.next(); + if (e == null ? i2.next() != null : !e.equals(i2.next())) { + return false; + } + } + } + if (i2.hasNext()) { + return false; + } else { + return true; + } + } + } + + public int hashCode() { + int hashCode = 1; + Iterator i = iterator(); + while (i.hasNext()) { + Object obj = i.next(); + hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode()); + } + return hashCode; + } + + public int indexOf(Object o) { + int index = 0; + ListIterator i = listIterator(); + if (o == null) { + while (i.hasNext()) { + if (i.next() == null) { + return index; + } + index++; + } + } else { + while (i.hasNext()) { + if (o.equals(i.next())) { + return index; + } + index++; + } + } + return -1; + } + + public Iterator iterator() { + return new Iterator() { + private int knownMod = modCount; + private int position = 0; + boolean removed = true; + + private void checkMod() { + if (knownMod != modCount) { + throw new ConcurrentModificationException(); + } + } + + public boolean hasNext() { + checkMod(); + return position < size(); + } + + public Object next() { + checkMod(); + removed = false; + try { + return get(position++); + } catch (IndexOutOfBoundsException e) { + throw new NoSuchElementException(); + } + } + + public void remove() { + checkMod(); + if (removed) { + throw new IllegalStateException(); + } + AbstractList.this.remove(--position); + knownMod = modCount; + removed = true; + } + }; + } + + public int lastIndexOf(Object o) { + int index = size(); + ListIterator i = listIterator(index); + if (o == null) { + while (i.hasPrevious()) { + index--; + if (i.previous() == null) { + return index; + } + } + } else { + while (i.hasPrevious()) { + index--; + if (o.equals(i.previous())) { + return index; + } + } + } + return -1; + } + + public ListIterator listIterator() { + return listIterator(0); + } + + public ListIterator listIterator(final int index) { + + if (index < 0 || index > size()) { + throw new IndexOutOfBoundsException(); + } + + return new ListIterator() { + private int knownMod = modCount; + private int position = index; + private int lastReturned = -1; + + private void checkMod() { + if (knownMod != modCount) { + throw new ConcurrentModificationException(); + } + } + + public boolean hasNext() { + checkMod(); + return position < size(); + } + + public boolean hasPrevious() { + checkMod(); + return position > 0; + } + + public Object next() { + checkMod(); + if (hasNext()) { + lastReturned = position++; + return get(lastReturned); + } else { + throw new NoSuchElementException(); + } + } + + public Object previous() { + checkMod(); + if (hasPrevious()) { + lastReturned = --position; + return get(lastReturned); + } else { + throw new NoSuchElementException(); + } + } + + public int nextIndex() { + checkMod(); + return position; + } + + public int previousIndex() { + checkMod(); + return position - 1; + } + + public void remove() { + checkMod(); + if (lastReturned < 0) { + throw new IllegalStateException(); + } + AbstractList.this.remove(lastReturned); + knownMod = modCount; + position = lastReturned; + lastReturned = -1; + } + + public void set(Object o) { + checkMod(); + if (lastReturned < 0) { + throw new IllegalStateException(); + } + AbstractList.this.set(lastReturned, o); + } + + public void add(Object o) { + checkMod(); + AbstractList.this.add(position++, o); + lastReturned = -1; + knownMod = modCount; + } + }; + } + + public Object remove(int index) { + throw new UnsupportedOperationException(); + } + + /** + * Remove a subsection of the list. This is called by the clear and + * removeRange methods of the class which implements subList, which are + * difficult for subclasses to override directly. Therefore, this method + * should be overridden instead by the more efficient implementation, if one + * exists. + * <p> + * This implementation first checks for illegal or out of range arguments. It + * then obtains a ListIterator over the list using listIterator(fromIndex). + * It then calls next() and remove() on this iterator repeatedly, toIndex - + * fromIndex times. + * + * @param fromIndex the index, inclusive, to remove from. + * @param toIndex the index, exclusive, to remove to. + * @exception UnsupportedOperationException if this list does not support + * the removeRange operation. + * @exception IndexOutOfBoundsException if fromIndex > toIndex || fromIndex < + * 0 || toIndex > size(). + */ + protected void removeRange(int fromIndex, int toIndex) { + if (fromIndex > toIndex) { + throw new IllegalArgumentException(); + } else if (fromIndex < 0 || toIndex > size()) { + throw new IndexOutOfBoundsException(); + } else { + ListIterator i = listIterator(fromIndex); + for (int index = fromIndex; index < toIndex; index++) { + i.next(); + i.remove(); + } + } + } + + public Object set(int index, Object o) { + throw new UnsupportedOperationException(); + } + + public List subList(final int fromIndex, final int toIndex) { + if (fromIndex > toIndex) + throw new IllegalArgumentException(); + if (fromIndex < 0 || toIndex > size()) + throw new IndexOutOfBoundsException(); + return new SubList(this, fromIndex, toIndex); + } + + static class SubList extends AbstractList { + + private AbstractList backingList; + private int offset; + private int size; + + public SubList(AbstractList backing, int fromIndex, int toIndex) { + backingList = backing; + upMod(); + offset = fromIndex; + size = toIndex - fromIndex; + } + + // Note that within this class two fields called modCount are inherited - + // one from the superclass, and one from the outer class. + // The code uses both these two fields and *no other* to provide fail-fast + // behaviour. For correct operation, the two fields should contain equal + // values. Therefore, if this.modCount != backingList.modCount, there + // has been a concurrent modification. This is all achieved purely by using + // the modCount field, precisely according to the docs of AbstractList. + // See the methods upMod and checkMod. + + /** + * This method checks the two modCount fields to ensure that there has + * not been a concurrent modification. It throws an exception if there + * has been, and otherwise returns normally. + * Note that since this method is private, it will be inlined. + * + * @exception ConcurrentModificationException if there has been a + * concurrent modification. + */ + private void checkMod() { + if (this.modCount != backingList.modCount) { + throw new ConcurrentModificationException(); + } + } + + /** + * This method is called after every method that causes a structural + * modification to the backing list. It updates the local modCount field + * to match that of the backing list. + * Note that since this method is private, it will be inlined. + */ + private void upMod() { + this.modCount = backingList.modCount; + } + + /** + * This method checks that a value is between 0 and size (inclusive). If + * it is not, an exception is thrown. + * Note that since this method is private, it will be inlined. + * + * @exception IndexOutOfBoundsException if the value is out of range. + */ + private void checkBoundsInclusive(int index) { + if (index < 0 || index > size) { + throw new IndexOutOfBoundsException(); + } + } + + /** + * This method checks that a value is between 0 (inclusive) and size + * (exclusive). If it is not, an exception is thrown. + * Note that since this method is private, it will be inlined. + * + * @exception IndexOutOfBoundsException if the value is out of range. + */ + private void checkBoundsExclusive(int index) { + if (index < 0 || index >= size) { + throw new IndexOutOfBoundsException(); + } + } + + public int size() { + checkMod(); + return size; + } + + public Iterator iterator() { + return listIterator(); + } + + public ListIterator listIterator(final int index) { + + checkMod(); + checkBoundsInclusive(index); + + return new ListIterator() { + ListIterator i = backingList.listIterator(index + offset); + int position = index; + + public boolean hasNext() { + checkMod(); + return position < size; + } + + public boolean hasPrevious() { + checkMod(); + return position > 0; + } + + public Object next() { + if (position < size) { + Object o = i.next(); + position++; + return o; + } else { + throw new NoSuchElementException(); + } + } + + public Object previous() { + if (position > 0) { + Object o = i.previous(); + position--; + return o; + } else { + throw new NoSuchElementException(); + } + } + + public int nextIndex() { + return offset + i.nextIndex(); + } + + public int previousIndex() { + return offset + i.previousIndex(); + } + + public void remove() { + i.remove(); + upMod(); + size--; + position = nextIndex(); + } + + public void set(Object o) { + i.set(o); + } + + public void add(Object o) { + i.add(o); + upMod(); + size++; + position++; + } + + // Here is the reason why the various modCount fields are mostly + // ignored in this wrapper listIterator. + // IF the backing listIterator is failfast, then the following holds: + // Using any other method on this list will call a corresponding + // method on the backing list *after* the backing listIterator + // is created, which will in turn cause a ConcurrentModException + // when this listIterator comes to use the backing one. So it is + // implicitly failfast. + // If the backing listIterator is NOT failfast, then the whole of + // this list isn't failfast, because the modCount field of the + // backing list is not valid. It would still be *possible* to + // make the iterator failfast wrt modifications of the sublist + // only, but somewhat pointless when the list can be changed under + // us. + // Either way, no explicit handling of modCount is needed. + // However upMod() must be called in add and remove, and size + // must also be updated in these two methods, since they do not go + // through the corresponding methods of the subList. + + }; + } + + public Object set(int index, Object o) { + checkMod(); + checkBoundsExclusive(index); + o = backingList.set(index + offset, o); + upMod(); + return o; + } + + public Object get(int index) { + checkMod(); + checkBoundsExclusive(index); + return backingList.get(index + offset); + } + + public void add(int index, Object o) { + checkMod(); + checkBoundsInclusive(index); + backingList.add(index + offset, o); + upMod(); + size++; + } + + public Object remove(int index) { + checkMod(); + checkBoundsExclusive(index); + Object o = backingList.remove(index + offset); + upMod(); + size--; + return o; + } + + public void removeRange(int fromIndex, int toIndex) { + checkMod(); + checkBoundsExclusive(fromIndex); + checkBoundsInclusive(toIndex); + + // this call will catch the toIndex < fromIndex condition + backingList.removeRange(offset + fromIndex, offset + toIndex); + upMod(); + size -= toIndex - fromIndex; + } + + public boolean addAll(int index, Collection c) { + checkMod(); + checkBoundsInclusive(index); + int s = backingList.size(); + boolean result = backingList.addAll(offset + index, c); + upMod(); + size += backingList.size() - s; + return result; + } + } +} diff --git a/libjava/java/util/Arrays.java b/libjava/java/util/Arrays.java new file mode 100644 index 00000000000..fc51d3886ea --- /dev/null +++ b/libjava/java/util/Arrays.java @@ -0,0 +1,1757 @@ +/* Arrays.java -- Utility class with methods to operate on arrays + Copyright (C) 1998, 1999 Free Software Foundation, Inc. + +This file is part of GNU Classpath. + +GNU Classpath is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU Classpath 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 +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Classpath; see the file COPYING. If not, write to the +Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA +02111-1307 USA. + +As a special exception, if you link this library with other files to +produce an executable, this library does not by itself cause the +resulting executable to be covered by the GNU General Public License. +This exception does not however invalidate any other reasons why the +executable file might be covered by the GNU General Public License. */ + + +// TO DO: +// ~ Fix the behaviour of sort and binarySearch as applied to float and double +// arrays containing NaN values. See the JDC, bug ID 4143272. + +package java.util; + +/** + * This class contains various static utility methods performing operations on + * arrays, and a method to provide a List "view" of an array to facilitate + * using arrays with Collection-based APIs. + */ +public class Arrays { + + /** + * This class is non-instantiable. + */ + private Arrays() { + } + + private static Comparator defaultComparator = new Comparator() { + public int compare(Object o1, Object o2) { + return ((Comparable)o1).compareTo(o2); + } + }; + + /** + * Perform a binary search of a byte array for a key. The array must be + * sorted (as by the sort() method) - if it is not, the behaviour of this + * method is undefined, and may be an infinite loop. If the array contains + * the key more than once, any one of them may be found. Note: although the + * specification allows for an infinite loop if the array is unsorted, it + * will not happen in this implementation. + * + * @param a the array to search (must be sorted) + * @param key the value to search for + * @returns the index at which the key was found, or -n-1 if it was not + * found, where n is the index of the first value higher than key or + * a.length if there is no such value. + */ + public static int binarySearch(byte[] a, byte key) { + int low = 0; + int hi = a.length - 1; + int mid = 0; + while (low <= hi) { + mid = (low + hi) >> 1; + final byte d = a[mid]; + if (d == key) { + return mid; + } else if (d > key) { + hi = mid - 1; + } else { + low = ++mid; // This gets the insertion point right on the last loop + } + } + return -mid - 1; + } + + /** + * Perform a binary search of a char array for a key. The array must be + * sorted (as by the sort() method) - if it is not, the behaviour of this + * method is undefined, and may be an infinite loop. If the array contains + * the key more than once, any one of them may be found. Note: although the + * specification allows for an infinite loop if the array is unsorted, it + * will not happen in this implementation. + * + * @param a the array to search (must be sorted) + * @param key the value to search for + * @returns the index at which the key was found, or -n-1 if it was not + * found, where n is the index of the first value higher than key or + * a.length if there is no such value. + */ + public static int binarySearch(char[] a, char key) { + int low = 0; + int hi = a.length - 1; + int mid = 0; + while (low <= hi) { + mid = (low + hi) >> 1; + final char d = a[mid]; + if (d == key) { + return mid; + } else if (d > key) { + hi = mid - 1; + } else { + low = ++mid; // This gets the insertion point right on the last loop + } + } + return -mid - 1; + } + + /** + * Perform a binary search of a double array for a key. The array must be + * sorted (as by the sort() method) - if it is not, the behaviour of this + * method is undefined, and may be an infinite loop. If the array contains + * the key more than once, any one of them may be found. Note: although the + * specification allows for an infinite loop if the array is unsorted, it + * will not happen in this implementation. + * + * @param a the array to search (must be sorted) + * @param key the value to search for + * @returns the index at which the key was found, or -n-1 if it was not + * found, where n is the index of the first value higher than key or + * a.length if there is no such value. + */ + public static int binarySearch(double[] a, double key) { + int low = 0; + int hi = a.length - 1; + int mid = 0; + while (low <= hi) { + mid = (low + hi) >> 1; + final double d = a[mid]; + if (d == key) { + return mid; + } else if (d > key) { + hi = mid - 1; + } else { + low = ++mid; // This gets the insertion point right on the last loop + } + } + return -mid - 1; + } + + /** + * Perform a binary search of a float array for a key. The array must be + * sorted (as by the sort() method) - if it is not, the behaviour of this + * method is undefined, and may be an infinite loop. If the array contains + * the key more than once, any one of them may be found. Note: although the + * specification allows for an infinite loop if the array is unsorted, it + * will not happen in this implementation. + * + * @param a the array to search (must be sorted) + * @param key the value to search for + * @returns the index at which the key was found, or -n-1 if it was not + * found, where n is the index of the first value higher than key or + * a.length if there is no such value. + */ + public static int binarySearch(float[] a, float key) { + int low = 0; + int hi = a.length - 1; + int mid = 0; + while (low <= hi) { + mid = (low + hi) >> 1; + final float d = a[mid]; + if (d == key) { + return mid; + } else if (d > key) { + hi = mid - 1; + } else { + low = ++mid; // This gets the insertion point right on the last loop + } + } + return -mid - 1; + } + + /** + * Perform a binary search of an int array for a key. The array must be + * sorted (as by the sort() method) - if it is not, the behaviour of this + * method is undefined, and may be an infinite loop. If the array contains + * the key more than once, any one of them may be found. Note: although the + * specification allows for an infinite loop if the array is unsorted, it + * will not happen in this implementation. + * + * @param a the array to search (must be sorted) + * @param key the value to search for + * @returns the index at which the key was found, or -n-1 if it was not + * found, where n is the index of the first value higher than key or + * a.length if there is no such value. + */ + public static int binarySearch(int[] a, int key) { + int low = 0; + int hi = a.length - 1; + int mid = 0; + while (low <= hi) { + mid = (low + hi) >> 1; + final int d = a[mid]; + if (d == key) { + return mid; + } else if (d > key) { + hi = mid - 1; + } else { + low = ++mid; // This gets the insertion point right on the last loop + } + } + return -mid - 1; + } + + /** + * Perform a binary search of a long array for a key. The array must be + * sorted (as by the sort() method) - if it is not, the behaviour of this + * method is undefined, and may be an infinite loop. If the array contains + * the key more than once, any one of them may be found. Note: although the + * specification allows for an infinite loop if the array is unsorted, it + * will not happen in this implementation. + * + * @param a the array to search (must be sorted) + * @param key the value to search for + * @returns the index at which the key was found, or -n-1 if it was not + * found, where n is the index of the first value higher than key or + * a.length if there is no such value. + */ + public static int binarySearch(long[] a, long key) { + int low = 0; + int hi = a.length - 1; + int mid = 0; + while (low <= hi) { + mid = (low + hi) >> 1; + final long d = a[mid]; + if (d == key) { + return mid; + } else if (d > key) { + hi = mid - 1; + } else { + low = ++mid; // This gets the insertion point right on the last loop + } + } + return -mid - 1; + } + + /** + * Perform a binary search of a short array for a key. The array must be + * sorted (as by the sort() method) - if it is not, the behaviour of this + * method is undefined, and may be an infinite loop. If the array contains + * the key more than once, any one of them may be found. Note: although the + * specification allows for an infinite loop if the array is unsorted, it + * will not happen in this implementation. + * + * @param a the array to search (must be sorted) + * @param key the value to search for + * @returns the index at which the key was found, or -n-1 if it was not + * found, where n is the index of the first value higher than key or + * a.length if there is no such value. + */ + public static int binarySearch(short[] a, short key) { + int low = 0; + int hi = a.length - 1; + int mid = 0; + while (low <= hi) { + mid = (low + hi) >> 1; + final short d = a[mid]; + if (d == key) { + return mid; + } else if (d > key) { + hi = mid - 1; + } else { + low = ++mid; // This gets the insertion point right on the last loop + } + } + return -mid - 1; + } + + /** + * This method does the work for the Object binary search methods. + * @exception NullPointerException if the specified comparator is null. + * @exception ClassCastException if the objects are not comparable by c. + */ + private static int objectSearch(Object[] a, Object key, final Comparator c) { + int low = 0; + int hi = a.length - 1; + int mid = 0; + while (low <= hi) { + mid = (low + hi) >> 1; + final int d = c.compare(key, a[mid]); + if (d == 0) { + return mid; + } else if (d < 0) { + hi = mid - 1; + } else { + low = ++mid; // This gets the insertion point right on the last loop + } + } + return -mid - 1; + } + + /** + * Perform a binary search of an Object array for a key, using the natural + * ordering of the elements. The array must be sorted (as by the sort() + * method) - if it is not, the behaviour of this method is undefined, and may + * be an infinite loop. Further, the key must be comparable with every item + * in the array. If the array contains the key more than once, any one of + * them may be found. Note: although the specification allows for an infinite + * loop if the array is unsorted, it will not happen in this (JCL) + * implementation. + * + * @param a the array to search (must be sorted) + * @param key the value to search for + * @returns the index at which the key was found, or -n-1 if it was not + * found, where n is the index of the first value higher than key or + * a.length if there is no such value. + * @exception ClassCastException if key could not be compared with one of the + * elements of a + * @exception NullPointerException if a null element has compareTo called + */ + public static int binarySearch(Object[] a, Object key) { + return objectSearch(a, key, defaultComparator); + } + + /** + * Perform a binary search of an Object array for a key, using a supplied + * Comparator. The array must be sorted (as by the sort() method with the + * same Comparator) - if it is not, the behaviour of this method is + * undefined, and may be an infinite loop. Further, the key must be + * comparable with every item in the array. If the array contains the key + * more than once, any one of them may be found. Note: although the + * specification allows for an infinite loop if the array is unsorted, it + * will not happen in this (JCL) implementation. + * + * @param a the array to search (must be sorted) + * @param key the value to search for + * @param c the comparator by which the array is sorted + * @returns the index at which the key was found, or -n-1 if it was not + * found, where n is the index of the first value higher than key or + * a.length if there is no such value. + * @exception ClassCastException if key could not be compared with one of the + * elements of a + */ + public static int binarySearch(Object[] a, Object key, Comparator c) { + return objectSearch(a, key, c); + } + + /** + * Compare two byte arrays for equality. + * + * @param a1 the first array to compare + * @param a2 the second array to compare + * @returns true if a1 and a2 are both null, or if a2 is of the same length + * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] + */ + public static boolean equals(byte[] a1, byte[] a2) { + + // Quick test which saves comparing elements of the same array, and also + // catches the case that both are null. + if (a1 == a2) { + return true; + } + try { + + // If they're the same length, test each element + if (a1.length == a2.length) { + for (int i = 0; i < a1.length; i++) { + if (a1[i] != a2[i]) { + return false; + } + } + return true; + } + + // If a1 == null or a2 == null but not both then we will get a NullPointer + } catch (NullPointerException e) { + } + + return false; + } + + /** + * Compare two char arrays for equality. + * + * @param a1 the first array to compare + * @param a2 the second array to compare + * @returns true if a1 and a2 are both null, or if a2 is of the same length + * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] + */ + public static boolean equals(char[] a1, char[] a2) { + + // Quick test which saves comparing elements of the same array, and also + // catches the case that both are null. + if (a1 == a2) { + return true; + } + try { + + // If they're the same length, test each element + if (a1.length == a2.length) { + for (int i = 0; i < a1.length; i++) { + if (a1[i] != a2[i]) { + return false; + } + } + return true; + } + + // If a1 == null or a2 == null but not both then we will get a NullPointer + } catch (NullPointerException e) { + } + + return false; + } + + /** + * Compare two double arrays for equality. + * + * @param a1 the first array to compare + * @param a2 the second array to compare + * @returns true if a1 and a2 are both null, or if a2 is of the same length + * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] + */ + public static boolean equals(double[] a1, double[] a2) { + + // Quick test which saves comparing elements of the same array, and also + // catches the case that both are null. + if (a1 == a2) { + return true; + } + try { + + // If they're the same length, test each element + if (a1.length == a2.length) { + for (int i = 0; i < a1.length; i++) { + if (a1[i] != a2[i]) { + return false; + } + } + return true; + } + + // If a1 == null or a2 == null but not both then we will get a NullPointer + } catch (NullPointerException e) { + } + + return false; + } + + /** + * Compare two float arrays for equality. + * + * @param a1 the first array to compare + * @param a2 the second array to compare + * @returns true if a1 and a2 are both null, or if a2 is of the same length + * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] + */ + public static boolean equals(float[] a1, float[] a2) { + + // Quick test which saves comparing elements of the same array, and also + // catches the case that both are null. + if (a1 == a2) { + return true; + } + try { + + // If they're the same length, test each element + if (a1.length == a2.length) { + for (int i = 0; i < a1.length; i++) { + if (a1[i] != a2[i]) { + return false; + } + } + return true; + } + + // If a1 == null or a2 == null but not both then we will get a NullPointer + } catch (NullPointerException e) { + } + + return false; + } + + /** + * Compare two long arrays for equality. + * + * @param a1 the first array to compare + * @param a2 the second array to compare + * @returns true if a1 and a2 are both null, or if a2 is of the same length + * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] + */ + public static boolean equals(long[] a1, long[] a2) { + + // Quick test which saves comparing elements of the same array, and also + // catches the case that both are null. + if (a1 == a2) { + return true; + } + try { + + // If they're the same length, test each element + if (a1.length == a2.length) { + for (int i = 0; i < a1.length; i++) { + if (a1[i] != a2[i]) { + return false; + } + } + return true; + } + + // If a1 == null or a2 == null but not both then we will get a NullPointer + } catch (NullPointerException e) { + } + + return false; + } + + /** + * Compare two short arrays for equality. + * + * @param a1 the first array to compare + * @param a2 the second array to compare + * @returns true if a1 and a2 are both null, or if a2 is of the same length + * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] + */ + public static boolean equals(short[] a1, short[] a2) { + + // Quick test which saves comparing elements of the same array, and also + // catches the case that both are null. + if (a1 == a2) { + return true; + } + try { + + // If they're the same length, test each element + if (a1.length == a2.length) { + for (int i = 0; i < a1.length; i++) { + if (a1[i] != a2[i]) { + return false; + } + } + return true; + } + + // If a1 == null or a2 == null but not both then we will get a NullPointer + } catch (NullPointerException e) { + } + + return false; + } + + /** + * Compare two boolean arrays for equality. + * + * @param a1 the first array to compare + * @param a2 the second array to compare + * @returns true if a1 and a2 are both null, or if a2 is of the same length + * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] + */ + public static boolean equals(boolean[] a1, boolean[] a2) { + + // Quick test which saves comparing elements of the same array, and also + // catches the case that both are null. + if (a1 == a2) { + return true; + } + try { + + // If they're the same length, test each element + if (a1.length == a2.length) { + for (int i = 0; i < a1.length; i++) { + if (a1[i] != a2[i]) { + return false; + } + } + return true; + } + + // If a1 == null or a2 == null but not both then we will get a NullPointer + } catch (NullPointerException e) { + } + + return false; + } + + /** + * Compare two int arrays for equality. + * + * @param a1 the first array to compare + * @param a2 the second array to compare + * @returns true if a1 and a2 are both null, or if a2 is of the same length + * as a1, and for each 0 <= i < a1.length, a1[i] == a2[i] + */ + public static boolean equals(int[] a1, int[] a2) { + + // Quick test which saves comparing elements of the same array, and also + // catches the case that both are null. + if (a1 == a2) { + return true; + } + try { + + // If they're the same length, test each element + if (a1.length == a2.length) { + for (int i = 0; i < a1.length; i++) { + if (a1[i] != a2[i]) { + return false; + } + } + return true; + } + + // If a1 == null or a2 == null but not both then we will get a NullPointer + } catch (NullPointerException e) { + } + + return false; + } + + /** + * Compare two Object arrays for equality. + * + * @param a1 the first array to compare + * @param a2 the second array to compare + * @returns true if a1 and a2 are both null, or if a1 is of the same length + * as a2, and for each 0 <= i < a.length, a1[i] == null ? a2[i] == null : + * a1[i].equals(a2[i]). + */ + public static boolean equals(Object[] a1, Object[] a2) { + + // Quick test which saves comparing elements of the same array, and also + // catches the case that both are null. + if (a1 == a2) { + return true; + } + try { + + // If they're the same length, test each element + if (a1.length == a2.length) { + for (int i = 0; i < a1.length; i++) { + if (!(a1[i] == null ? a2[i] == null : a1[i].equals(a2[i]))) { + return false; + } + } + return true; + } + + // If a1 == null or a2 == null but not both then we will get a NullPointer + } catch (NullPointerException e) { + } + + return false; + } + + /** + * Fill an array with a boolean value. + * + * @param a the array to fill + * @param val the value to fill it with + */ + public static void fill(boolean[] a, boolean val) { + // This implementation is slightly inefficient timewise, but the extra + // effort over inlining it is O(1) and small, and I refuse to repeat code + // if it can be helped. + fill(a, 0, a.length, val); + } + + /** + * Fill a range of an array with a boolean value. + * + * @param a the array to fill + * @param fromIndex the index to fill from, inclusive + * @param toIndex the index to fill to, exclusive + * @param val the value to fill with + */ + public static void fill(boolean[] a, int fromIndex, int toIndex, + boolean val) { + for (int i = fromIndex; i < toIndex; i++) { + a[i] = val; + } + } + + /** + * Fill an array with a byte value. + * + * @param a the array to fill + * @param val the value to fill it with + */ + public static void fill(byte[] a, byte val) { + // This implementation is slightly inefficient timewise, but the extra + // effort over inlining it is O(1) and small, and I refuse to repeat code + // if it can be helped. + fill(a, 0, a.length, val); + } + + /** + * Fill a range of an array with a byte value. + * + * @param a the array to fill + * @param fromIndex the index to fill from, inclusive + * @param toIndex the index to fill to, exclusive + * @param val the value to fill with + */ + public static void fill(byte[] a, int fromIndex, int toIndex, byte val) { + for (int i = fromIndex; i < toIndex; i++) { + a[i] = val; + } + } + + /** + * Fill an array with a char value. + * + * @param a the array to fill + * @param val the value to fill it with + */ + public static void fill(char[] a, char val) { + // This implementation is slightly inefficient timewise, but the extra + // effort over inlining it is O(1) and small, and I refuse to repeat code + // if it can be helped. + fill(a, 0, a.length, val); + } + + /** + * Fill a range of an array with a char value. + * + * @param a the array to fill + * @param fromIndex the index to fill from, inclusive + * @param toIndex the index to fill to, exclusive + * @param val the value to fill with + */ + public static void fill(char[] a, int fromIndex, int toIndex, char val) { + for (int i = fromIndex; i < toIndex; i++) { + a[i] = val; + } + } + + /** + * Fill an array with a double value. + * + * @param a the array to fill + * @param val the value to fill it with + */ + public static void fill(double[] a, double val) { + // This implementation is slightly inefficient timewise, but the extra + // effort over inlining it is O(1) and small, and I refuse to repeat code + // if it can be helped. + fill(a, 0, a.length, val); + } + + /** + * Fill a range of an array with a double value. + * + * @param a the array to fill + * @param fromIndex the index to fill from, inclusive + * @param toIndex the index to fill to, exclusive + * @param val the value to fill with + */ + public static void fill(double[] a, int fromIndex, int toIndex, double val) { + for (int i = fromIndex; i < toIndex; i++) { + a[i] = val; + } + } + + /** + * Fill an array with a float value. + * + * @param a the array to fill + * @param val the value to fill it with + */ + public static void fill(float[] a, float val) { + // This implementation is slightly inefficient timewise, but the extra + // effort over inlining it is O(1) and small, and I refuse to repeat code + // if it can be helped. + fill(a, 0, a.length, val); + } + + /** + * Fill a range of an array with a float value. + * + * @param a the array to fill + * @param fromIndex the index to fill from, inclusive + * @param toIndex the index to fill to, exclusive + * @param val the value to fill with + */ + public static void fill(float[] a, int fromIndex, int toIndex, float val) { + for (int i = fromIndex; i < toIndex; i++) { + a[i] = val; + } + } + + /** + * Fill an array with an int value. + * + * @param a the array to fill + * @param val the value to fill it with + */ + public static void fill(int[] a, int val) { + // This implementation is slightly inefficient timewise, but the extra + // effort over inlining it is O(1) and small, and I refuse to repeat code + // if it can be helped. + fill(a, 0, a.length, val); + } + + /** + * Fill a range of an array with an int value. + * + * @param a the array to fill + * @param fromIndex the index to fill from, inclusive + * @param toIndex the index to fill to, exclusive + * @param val the value to fill with + */ + public static void fill(int[] a, int fromIndex, int toIndex, int val) { + for (int i = fromIndex; i < toIndex; i++) { + a[i] = val; + } + } + + /** + * Fill an array with a long value. + * + * @param a the array to fill + * @param val the value to fill it with + */ + public static void fill(long[] a, long val) { + // This implementation is slightly inefficient timewise, but the extra + // effort over inlining it is O(1) and small, and I refuse to repeat code + // if it can be helped. + fill(a, 0, a.length, val); + } + + /** + * Fill a range of an array with a long value. + * + * @param a the array to fill + * @param fromIndex the index to fill from, inclusive + * @param toIndex the index to fill to, exclusive + * @param val the value to fill with + */ + public static void fill(long[] a, int fromIndex, int toIndex, long val) { + for (int i = fromIndex; i < toIndex; i++) { + a[i] = val; + } + } + + /** + * Fill an array with a short value. + * + * @param a the array to fill + * @param val the value to fill it with + */ + public static void fill(short[] a, short val) { + // This implementation is slightly inefficient timewise, but the extra + // effort over inlining it is O(1) and small, and I refuse to repeat code + // if it can be helped. + fill(a, 0, a.length, val); + } + + /** + * Fill a range of an array with a short value. + * + * @param a the array to fill + * @param fromIndex the index to fill from, inclusive + * @param toIndex the index to fill to, exclusive + * @param val the value to fill with + */ + public static void fill(short[] a, int fromIndex, int toIndex, short val) { + for (int i = fromIndex; i < toIndex; i++) { + a[i] = val; + } + } + + /** + * Fill an array with an Object value. + * + * @param a the array to fill + * @param val the value to fill it with + * @exception ClassCastException if val is not an instance of the element + * type of a. + */ + public static void fill(Object[] a, Object val) { + // This implementation is slightly inefficient timewise, but the extra + // effort over inlining it is O(1) and small, and I refuse to repeat code + // if it can be helped. + fill(a, 0, a.length, val); + } + + /** + * Fill a range of an array with an Object value. + * + * @param a the array to fill + * @param fromIndex the index to fill from, inclusive + * @param toIndex the index to fill to, exclusive + * @param val the value to fill with + * @exception ClassCastException if val is not an instance of the element + * type of a. + */ + public static void fill(Object[] a, int fromIndex, int toIndex, Object val) { + for (int i = fromIndex; i < toIndex; i++) { + a[i] = val; + } + } + + // Thanks to Paul Fisher <rao@gnu.org> for finding this quicksort algorithm + // as specified by Sun and porting it to Java. + + /** + * Sort a byte array into ascending order. The sort algorithm is an optimised + * quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's + * "Engineering a Sort Function", Software-Practice and Experience, Vol. + * 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n) + * performance on many arrays that would take quadratic time with a standard + * quicksort. + * + * @param a the array to sort + */ + public static void sort(byte[] a) { + qsort(a, 0, a.length); + } + + private static short cmp(byte i, byte j) { + return (short)(i-j); + } + + private static int med3(int a, int b, int c, byte[] d) { + return cmp(d[a], d[b]) < 0 ? + (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a) + : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a); + } + + private static void swap(int i, int j, byte[] a) { + byte c = a[i]; + a[i] = a[j]; + a[j] = c; + } + + private static void qsort(byte[] a, int start, int n) { + // use an insertion sort on small arrays + if (n < 7) { + for (int i = start + 1; i < start + n; i++) + for (int j = i; j > 0 && cmp(a[j-1], a[j]) > 0; j--) + swap(j, j-1, a); + return; + } + + int pm = n/2; // small arrays, middle element + if (n > 7) { + int pl = start; + int pn = start + n-1; + + if (n > 40) { // big arrays, pseudomedian of 9 + int s = n/8; + pl = med3(pl, pl+s, pl+2*s, a); + pm = med3(pm-s, pm, pm+s, a); + pn = med3(pn-2*s, pn-s, pn, a); + } + pm = med3(pl, pm, pn, a); // mid-size, med of 3 + } + + int pa, pb, pc, pd, pv; + short r; + + pv = start; swap(pv, pm, a); + pa = pb = start; + pc = pd = start + n-1; + + for (;;) { + while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0) { + if (r == 0) { swap(pa, pb, a); pa++; } + pb++; + } + while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0) { + if (r == 0) { swap(pc, pd, a); pd--; } + pc--; + } + if (pb > pc) break; + swap(pb, pc, a); + pb++; + pc--; + } + int pn = start + n; + int s; + s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a); + s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a); + if ((s = pb-pa) > 1) qsort(a, start, s); + if ((s = pd-pc) > 1) qsort(a, pn-s, s); + } + + private static void vecswap(int i, int j, int n, byte[] a) { + for (; n > 0; i++, j++, n--) + swap(i, j, a); + } + + /** + * Sort a char array into ascending order. The sort algorithm is an optimised + * quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's + * "Engineering a Sort Function", Software-Practice and Experience, Vol. + * 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n) + * performance on many arrays that would take quadratic time with a standard + * quicksort. + * + * @param a the array to sort + */ + public static void sort(char[] a) { + qsort(a, 0, a.length); + } + + private static int cmp(char i, char j) { + return i-j; + } + + private static int med3(int a, int b, int c, char[] d) { + return cmp(d[a], d[b]) < 0 ? + (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a) + : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a); + } + + private static void swap(int i, int j, char[] a) { + char c = a[i]; + a[i] = a[j]; + a[j] = c; + } + + private static void qsort(char[] a, int start, int n) { + // use an insertion sort on small arrays + if (n < 7) { + for (int i = start + 1; i < start + n; i++) + for (int j = i; j > 0 && cmp(a[j-1], a[j]) > 0; j--) + swap(j, j-1, a); + return; + } + + int pm = n/2; // small arrays, middle element + if (n > 7) { + int pl = start; + int pn = start + n-1; + + if (n > 40) { // big arrays, pseudomedian of 9 + int s = n/8; + pl = med3(pl, pl+s, pl+2*s, a); + pm = med3(pm-s, pm, pm+s, a); + pn = med3(pn-2*s, pn-s, pn, a); + } + pm = med3(pl, pm, pn, a); // mid-size, med of 3 + } + + int pa, pb, pc, pd, pv; + int r; + + pv = start; swap(pv, pm, a); + pa = pb = start; + pc = pd = start + n-1; + + for (;;) { + while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0) { + if (r == 0) { swap(pa, pb, a); pa++; } + pb++; + } + while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0) { + if (r == 0) { swap(pc, pd, a); pd--; } + pc--; + } + if (pb > pc) break; + swap(pb, pc, a); + pb++; + pc--; + } + int pn = start + n; + int s; + s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a); + s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a); + if ((s = pb-pa) > 1) qsort(a, start, s); + if ((s = pd-pc) > 1) qsort(a, pn-s, s); + } + + private static void vecswap(int i, int j, int n, char[] a) { + for (; n > 0; i++, j++, n--) + swap(i, j, a); + } + + /** + * Sort a double array into ascending order. The sort algorithm is an + * optimised quicksort, as described in Jon L. Bentley and M. Douglas + * McIlroy's "Engineering a Sort Function", Software-Practice and Experience, + * Vol. 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n) + * performance on many arrays that would take quadratic time with a standard + * quicksort. Note that this implementation, like Sun's, has undefined + * behaviour if the array contains any NaN values. + * + * @param a the array to sort + */ + public static void sort(double[] a) { + qsort(a, 0, a.length); + } + + private static double cmp(double i, double j) { + return i-j; + } + + private static int med3(int a, int b, int c, double[] d) { + return cmp(d[a], d[b]) < 0 ? + (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a) + : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a); + } + + private static void swap(int i, int j, double[] a) { + double c = a[i]; + a[i] = a[j]; + a[j] = c; + } + + private static void qsort(double[] a, int start, int n) { + // use an insertion sort on small arrays + if (n < 7) { + for (int i = start + 1; i < start + n; i++) + for (int j = i; j > 0 && cmp(a[j-1], a[j]) > 0; j--) + swap(j, j-1, a); + return; + } + + int pm = n/2; // small arrays, middle element + if (n > 7) { + int pl = start; + int pn = start + n-1; + + if (n > 40) { // big arrays, pseudomedian of 9 + int s = n/8; + pl = med3(pl, pl+s, pl+2*s, a); + pm = med3(pm-s, pm, pm+s, a); + pn = med3(pn-2*s, pn-s, pn, a); + } + pm = med3(pl, pm, pn, a); // mid-size, med of 3 + } + + int pa, pb, pc, pd, pv; + double r; + + pv = start; swap(pv, pm, a); + pa = pb = start; + pc = pd = start + n-1; + + for (;;) { + while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0) { + if (r == 0) { swap(pa, pb, a); pa++; } + pb++; + } + while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0) { + if (r == 0) { swap(pc, pd, a); pd--; } + pc--; + } + if (pb > pc) break; + swap(pb, pc, a); + pb++; + pc--; + } + int pn = start + n; + int s; + s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a); + s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a); + if ((s = pb-pa) > 1) qsort(a, start, s); + if ((s = pd-pc) > 1) qsort(a, pn-s, s); + } + + private static void vecswap(int i, int j, int n, double[] a) { + for (; n > 0; i++, j++, n--) + swap(i, j, a); + } + + /** + * Sort a float array into ascending order. The sort algorithm is an + * optimised quicksort, as described in Jon L. Bentley and M. Douglas + * McIlroy's "Engineering a Sort Function", Software-Practice and Experience, + * Vol. 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n) + * performance on many arrays that would take quadratic time with a standard + * quicksort. Note that this implementation, like Sun's, has undefined + * behaviour if the array contains any NaN values. + * + * @param a the array to sort + */ + public static void sort(float[] a) { + qsort(a, 0, a.length); + } + + private static float cmp(float i, float j) { + return i-j; + } + + private static int med3(int a, int b, int c, float[] d) { + return cmp(d[a], d[b]) < 0 ? + (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a) + : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a); + } + + private static void swap(int i, int j, float[] a) { + float c = a[i]; + a[i] = a[j]; + a[j] = c; + } + + private static void qsort(float[] a, int start, int n) { + // use an insertion sort on small arrays + if (n < 7) { + for (int i = start + 1; i < start + n; i++) + for (int j = i; j > 0 && cmp(a[j-1], a[j]) > 0; j--) + swap(j, j-1, a); + return; + } + + int pm = n/2; // small arrays, middle element + if (n > 7) { + int pl = start; + int pn = start + n-1; + + if (n > 40) { // big arrays, pseudomedian of 9 + int s = n/8; + pl = med3(pl, pl+s, pl+2*s, a); + pm = med3(pm-s, pm, pm+s, a); + pn = med3(pn-2*s, pn-s, pn, a); + } + pm = med3(pl, pm, pn, a); // mid-size, med of 3 + } + + int pa, pb, pc, pd, pv; + float r; + + pv = start; swap(pv, pm, a); + pa = pb = start; + pc = pd = start + n-1; + + for (;;) { + while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0) { + if (r == 0) { swap(pa, pb, a); pa++; } + pb++; + } + while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0) { + if (r == 0) { swap(pc, pd, a); pd--; } + pc--; + } + if (pb > pc) break; + swap(pb, pc, a); + pb++; + pc--; + } + int pn = start + n; + int s; + s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a); + s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a); + if ((s = pb-pa) > 1) qsort(a, start, s); + if ((s = pd-pc) > 1) qsort(a, pn-s, s); + } + + private static void vecswap(int i, int j, int n, float[] a) { + for (; n > 0; i++, j++, n--) + swap(i, j, a); + } + + /** + * Sort an int array into ascending order. The sort algorithm is an optimised + * quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's + * "Engineering a Sort Function", Software-Practice and Experience, Vol. + * 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n) + * performance on many arrays that would take quadratic time with a standard + * quicksort. + * + * @param a the array to sort + */ + public static void sort(int[] a) { + qsort(a, 0, a.length); + } + + private static long cmp(int i, int j) { + return (long)i-(long)j; + } + + private static int med3(int a, int b, int c, int[] d) { + return cmp(d[a], d[b]) < 0 ? + (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a) + : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a); + } + + private static void swap(int i, int j, int[] a) { + int c = a[i]; + a[i] = a[j]; + a[j] = c; + } + + private static void qsort(int[] a, int start, int n) { + // use an insertion sort on small arrays + if (n < 7) { + for (int i = start + 1; i < start + n; i++) + for (int j = i; j > 0 && cmp(a[j-1], a[j]) > 0; j--) + swap(j, j-1, a); + return; + } + + int pm = n/2; // small arrays, middle element + if (n > 7) { + int pl = start; + int pn = start + n-1; + + if (n > 40) { // big arrays, pseudomedian of 9 + int s = n/8; + pl = med3(pl, pl+s, pl+2*s, a); + pm = med3(pm-s, pm, pm+s, a); + pn = med3(pn-2*s, pn-s, pn, a); + } + pm = med3(pl, pm, pn, a); // mid-size, med of 3 + } + + int pa, pb, pc, pd, pv; + long r; + + pv = start; swap(pv, pm, a); + pa = pb = start; + pc = pd = start + n-1; + + for (;;) { + while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0) { + if (r == 0) { swap(pa, pb, a); pa++; } + pb++; + } + while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0) { + if (r == 0) { swap(pc, pd, a); pd--; } + pc--; + } + if (pb > pc) break; + swap(pb, pc, a); + pb++; + pc--; + } + int pn = start + n; + int s; + s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a); + s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a); + if ((s = pb-pa) > 1) qsort(a, start, s); + if ((s = pd-pc) > 1) qsort(a, pn-s, s); + } + + private static void vecswap(int i, int j, int n, int[] a) { + for (; n > 0; i++, j++, n--) + swap(i, j, a); + } + + /** + * Sort a long array into ascending order. The sort algorithm is an optimised + * quicksort, as described in Jon L. Bentley and M. Douglas McIlroy's + * "Engineering a Sort Function", Software-Practice and Experience, Vol. + * 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n) + * performance on many arrays that would take quadratic time with a standard + * quicksort. + * + * @param a the array to sort + */ + public static void sort(long[] a) { + qsort(a, 0, a.length); + } + + // The "cmp" method has been removed from here and replaced with direct + // compares in situ, to avoid problems with overflow if the difference + // between two numbers is bigger than a long will hold. + // One particular change as a result is the use of r1 and r2 in qsort + + private static int med3(int a, int b, int c, long[] d) { + return d[a] < d[b] ? + (d[b] < d[c] ? b : d[a] < d[c] ? c : a) + : (d[b] > d[c] ? b : d[a] > d[c] ? c : a); + } + + private static void swap(int i, int j, long[] a) { + long c = a[i]; + a[i] = a[j]; + a[j] = c; + } + + private static void qsort(long[] a, int start, int n) { + // use an insertion sort on small arrays + if (n < 7) { + for (int i = start + 1; i < start + n; i++) + for (int j = i; j > 0 && a[j-1] > a[j]; j--) + swap(j, j-1, a); + return; + } + + int pm = n/2; // small arrays, middle element + if (n > 7) { + int pl = start; + int pn = start + n-1; + + if (n > 40) { // big arrays, pseudomedian of 9 + int s = n/8; + pl = med3(pl, pl+s, pl+2*s, a); + pm = med3(pm-s, pm, pm+s, a); + pn = med3(pn-2*s, pn-s, pn, a); + } + pm = med3(pl, pm, pn, a); // mid-size, med of 3 + } + + int pa, pb, pc, pd, pv; + long r1, r2; + + pv = start; swap(pv, pm, a); + pa = pb = start; + pc = pd = start + n-1; + + for (;;) { + while (pb <= pc && (r1 = a[pb]) <= (r2 = a[pv])) { + if (r1 == r2) { swap(pa, pb, a); pa++; } + pb++; + } + while (pc >= pb && (r1 = a[pc]) >= (r2 = a[pv])) { + if (r1 == r2) { swap(pc, pd, a); pd--; } + pc--; + } + if (pb > pc) break; + swap(pb, pc, a); + pb++; + pc--; + } + int pn = start + n; + int s; + s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a); + s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a); + if ((s = pb-pa) > 1) qsort(a, start, s); + if ((s = pd-pc) > 1) qsort(a, pn-s, s); + } + + private static void vecswap(int i, int j, int n, long[] a) { + for (; n > 0; i++, j++, n--) + swap(i, j, a); + } + + /** + * Sort a short array into ascending order. The sort algorithm is an + * optimised quicksort, as described in Jon L. Bentley and M. Douglas + * McIlroy's "Engineering a Sort Function", Software-Practice and Experience, + * Vol. 23(11) P. 1249-1265 (November 1993). This algorithm gives nlog(n) + * performance on many arrays that would take quadratic time with a standard + * quicksort. + * + * @param a the array to sort + */ + public static void sort(short[] a) { + qsort(a, 0, a.length); + } + + private static int cmp(short i, short j) { + return i-j; + } + + private static int med3(int a, int b, int c, short[] d) { + return cmp(d[a], d[b]) < 0 ? + (cmp(d[b], d[c]) < 0 ? b : cmp(d[a], d[c]) < 0 ? c : a) + : (cmp(d[b], d[c]) > 0 ? b : cmp(d[a], d[c]) > 0 ? c : a); + } + + private static void swap(int i, int j, short[] a) { + short c = a[i]; + a[i] = a[j]; + a[j] = c; + } + + private static void qsort(short[] a, int start, int n) { + // use an insertion sort on small arrays + if (n < 7) { + for (int i = start + 1; i < start + n; i++) + for (int j = i; j > 0 && cmp(a[j-1], a[j]) > 0; j--) + swap(j, j-1, a); + return; + } + + int pm = n/2; // small arrays, middle element + if (n > 7) { + int pl = start; + int pn = start + n-1; + + if (n > 40) { // big arrays, pseudomedian of 9 + int s = n/8; + pl = med3(pl, pl+s, pl+2*s, a); + pm = med3(pm-s, pm, pm+s, a); + pn = med3(pn-2*s, pn-s, pn, a); + } + pm = med3(pl, pm, pn, a); // mid-size, med of 3 + } + + int pa, pb, pc, pd, pv; + int r; + + pv = start; swap(pv, pm, a); + pa = pb = start; + pc = pd = start + n-1; + + for (;;) { + while (pb <= pc && (r = cmp(a[pb], a[pv])) <= 0) { + if (r == 0) { swap(pa, pb, a); pa++; } + pb++; + } + while (pc >= pb && (r = cmp(a[pc], a[pv])) >= 0) { + if (r == 0) { swap(pc, pd, a); pd--; } + pc--; + } + if (pb > pc) break; + swap(pb, pc, a); + pb++; + pc--; + } + int pn = start + n; + int s; + s = Math.min(pa-start, pb-pa); vecswap(start, pb-s, s, a); + s = Math.min(pd-pc, pn-pd-1); vecswap(pb, pn-s, s, a); + if ((s = pb-pa) > 1) qsort(a, start, s); + if ((s = pd-pc) > 1) qsort(a, pn-s, s); + } + + private static void vecswap(int i, int j, int n, short[] a) { + for (; n > 0; i++, j++, n--) + swap(i, j, a); + } + + /** + * The bulk of the work for the object sort routines. In general, + * the code attempts to be simple rather than fast, the idea being + * that a good optimising JIT will be able to optimise it better + * than I can, and if I try it will make it more confusing for the + * JIT. + */ + private static void mergeSort(Object[] a, int from, int to, Comparator c) + { + // First presort the array in chunks of length 6 with insertion sort. + // mergesort would give too much overhead for this length. + for (int chunk = from; chunk < to; chunk += 6) + { + int end = Math.min(chunk+6, to); + for (int i = chunk + 1; i < end; i++) + { + if (c.compare(a[i-1], a[i]) > 0) + { + // not already sorted + int j=i; + Object elem = a[j]; + do + { + a[j] = a[j-1]; + j--; + } + while (j>chunk && c.compare(a[j-1], elem) > 0); + a[j] = elem; + } + } + } + + int len = to - from; + // If length is smaller or equal 6 we are done. + if (len <= 6) + return; + + Object[] src = a; + Object[] dest = new Object[len]; + Object[] t = null; // t is used for swapping src and dest + + // The difference of the fromIndex of the src and dest array. + int srcDestDiff = -from; + + // The merges are done in this loop + for (int size = 6; size < len; size <<= 1) + { + for (int start = from; start < to; start += size << 1) + { + // mid ist the start of the second sublist; + // end the start of the next sublist (or end of array). + int mid = start + size; + int end = Math.min(to, mid + size); + + // The second list is empty or the elements are already in + // order - no need to merge + if (mid >= end || c.compare(src[mid - 1], src[mid]) <= 0) { + System.arraycopy(src, start, + dest, start + srcDestDiff, end - start); + + // The two halves just need swapping - no need to merge + } else if (c.compare(src[start], src[end - 1]) > 0) { + System.arraycopy(src, start, + dest, end - size + srcDestDiff, size); + System.arraycopy(src, mid, + dest, start + srcDestDiff, end - mid); + + } else { + // Declare a lot of variables to save repeating + // calculations. Hopefully a decent JIT will put these + // in registers and make this fast + int p1 = start; + int p2 = mid; + int i = start + srcDestDiff; + + // The main merge loop; terminates as soon as either + // half is ended + while (p1 < mid && p2 < end) + { + dest[i++] = + src[c.compare(src[p1], src[p2]) <= 0 ? p1++ : p2++]; + } + + // Finish up by copying the remainder of whichever half + // wasn't finished. + if (p1 < mid) + System.arraycopy(src, p1, dest, i, mid - p1); + else + System.arraycopy(src, p2, dest, i, end - p2); + } + } + // swap src and dest ready for the next merge + t = src; src = dest; dest = t; + from += srcDestDiff; + to += srcDestDiff; + srcDestDiff = -srcDestDiff; + } + + // make sure the result ends up back in the right place. Note + // that src and dest may have been swapped above, so src + // contains the sorted array. + if (src != a) + { + // Note that from == 0. + System.arraycopy(src, 0, a, srcDestDiff, to); + } + } + + /** + * Sort an array of Objects according to their natural ordering. The sort is + * guaranteed to be stable, that is, equal elements will not be reordered. + * The sort algorithm is a mergesort with the merge omitted if the last + * element of one half comes before the first element of the other half. This + * algorithm gives guaranteed O(nlog(n)) time, at the expense of making a + * copy of the array. + * + * @param a the array to be sorted + * @exception ClassCastException if any two elements are not mutually + * comparable + * @exception NullPointerException if an element is null (since + * null.compareTo cannot work) + */ + public static void sort(Object[] a) { + mergeSort(a, 0, a.length, defaultComparator); + } + + /** + * Sort an array of Objects according to a Comparator. The sort is + * guaranteed to be stable, that is, equal elements will not be reordered. + * The sort algorithm is a mergesort with the merge omitted if the last + * element of one half comes before the first element of the other half. This + * algorithm gives guaranteed O(nlog(n)) time, at the expense of making a + * copy of the array. + * + * @param a the array to be sorted + * @param c a Comparator to use in sorting the array + * @exception ClassCastException if any two elements are not mutually + * comparable by the Comparator provided + */ + public static void sort(Object[] a, Comparator c) { + mergeSort(a, 0, a.length, c); + } + + /** + * Sort an array of Objects according to their natural ordering. The sort is + * guaranteed to be stable, that is, equal elements will not be reordered. + * The sort algorithm is a mergesort with the merge omitted if the last + * element of one half comes before the first element of the other half. This + * algorithm gives guaranteed O(nlog(n)) time, at the expense of making a + * copy of the array. + * + * @param a the array to be sorted + * @param fromIndex the index of the first element to be sorted. + * @param toIndex the index of the last element to be sorted plus one. + * @exception ClassCastException if any two elements are not mutually + * comparable by the Comparator provided + * @exception ArrayIndexOutOfBoundsException, if fromIndex and toIndex + * are not in range. + * @exception IllegalArgumentException if fromIndex > toIndex + */ + public static void sort(Object[] a, int fromIndex, + int toIndex) { + if (fromIndex > toIndex) + throw new IllegalArgumentException("fromIndex "+fromIndex + +" > toIndex "+toIndex); + mergeSort(a, fromIndex, toIndex, defaultComparator); + } + + /** + * Sort an array of Objects according to a Comparator. The sort is + * guaranteed to be stable, that is, equal elements will not be reordered. + * The sort algorithm is a mergesort with the merge omitted if the last + * element of one half comes before the first element of the other half. This + * algorithm gives guaranteed O(nlog(n)) time, at the expense of making a + * copy of the array. + * + * @param a the array to be sorted + * @param fromIndex the index of the first element to be sorted. + * @param toIndex the index of the last element to be sorted plus one. + * @param c a Comparator to use in sorting the array + * @exception ClassCastException if any two elements are not mutually + * comparable by the Comparator provided + * @exception ArrayIndexOutOfBoundsException, if fromIndex and toIndex + * are not in range. + * @exception IllegalArgumentException if fromIndex > toIndex + */ + public static void sort(Object[] a, int fromIndex, + int toIndex, Comparator c) { + if (fromIndex > toIndex) + throw new IllegalArgumentException("fromIndex "+fromIndex + +" > toIndex "+toIndex); + mergeSort(a, fromIndex, toIndex, c); + } + + /** + * Returns a list "view" of the specified array. This method is intended to + * make it easy to use the Collections API with existing array-based APIs and + * programs. + * + * @param a the array to return a view of + * @returns a fixed-size list, changes to which "write through" to the array + */ + public static List asList(final Object[] a) { + + if (a == null) { + throw new NullPointerException(); + } + + return new ListImpl( a ); + } + + + /** + * Inner class used by asList(Object[]) to provide a list interface + * to an array. The methods are all simple enough to be self documenting. + * Note: When Sun fully specify serialized forms, this class will have to + * be renamed. + */ + private static class ListImpl extends AbstractList { + + ListImpl(Object[] a) { + this.a = a; + } + + public Object get(int index) { + return a[index]; + } + + public int size() { + return a.length; + } + + public Object set(int index, Object element) { + Object old = a[index]; + a[index] = element; + return old; + } + + private Object[] a; + } + +} |