com.samskivert.util
Class SortableArrayList<T>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractList<E>
          com.samskivert.util.BaseArrayList<T>
              com.samskivert.util.SortableArrayList<T>

All Implemented Interfaces:

Serializable, Cloneable, Iterable<T>, Collection<T>, List<T>, RandomAccess

Direct Known Subclasses:

ComparableArrayList

public class SortableArrayList<T>
extends BaseArrayList<T>

Provides a mechanism (sort(java.util.Comparator)) for sorting the contents of the list that doesn't involve creating two object arrays. Two copies of the elements array are made if you called Collections.sort(java.util.List) (the first is when BaseArrayList.toArray() is called on the collection and the second is when Arrays.sort(long[]) clones the supplied array so that it can do a merge sort).

See Also:

Serialized Form

Field Summary

Fields inherited from class com.samskivert.util.BaseArrayList

_elements, _size

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

SortableArrayList()

Method Summary

int	binarySearch(T key, Comparator<? super T> comp) Performs a binary search, attempting to locate the specified object.
int	insertSorted(T value, Comparator<? super T> comp) Inserts the specified item into the list into a position that preserves the sorting of the list according to the supplied Comparator.
void	sort(Comparator<? super T> comp) Sorts the elements in this list with the supplied element comparator using the quick sort algorithm (which does not involve any object allocation).

Methods inherited from class com.samskivert.util.BaseArrayList

add, add, clear, clone, contains, get, indexOf, isEmpty, rangeCheck, remove, remove, set, size, toArray, toArray

Methods inherited from class java.util.AbstractList

addAll, equals, hashCode, iterator, lastIndexOf, listIterator, listIterator, removeRange, subList

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, removeAll, retainAll, toString

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.List

addAll, addAll, containsAll, equals, hashCode, iterator, lastIndexOf, listIterator, listIterator, removeAll, retainAll, subList

Constructor Detail

SortableArrayList

public SortableArrayList()

Method Detail

sort

public void sort(Comparator<? super T> comp)

Sorts the elements in this list with the supplied element comparator using the quick sort algorithm (which does not involve any object allocation). The elements must all be mutually comparable.

insertSorted

public int insertSorted(T value,
                        Comparator<? super T> comp)

Inserts the specified item into the list into a position that preserves the sorting of the list according to the supplied Comparator. The list must be sorted (via the supplied comparator) prior to the call to this method (an empty list built up entirely via calls to insertSorted(T, java.util.Comparator) will be properly sorted).

Returns:

the index at which the element was inserted.

binarySearch

public int binarySearch(T key,
                        Comparator<? super T> comp)

Performs a binary search, attempting to locate the specified object. The array must be in the sort order defined by the supplied Comparator for this to operate correctly.

Returns:

the index of the object in question or (-(insertion point) - 1) (always a negative value) if the object was not found in the list.