jopt.csp.util
Class SortableIntList

java.lang.Object
  org.apache.commons.collections.primitives.AbstractIntCollection
      org.apache.commons.collections.primitives.RandomAccessIntList
          org.apache.commons.collections.primitives.ArrayIntList
              jopt.csp.util.SortableIntList

All Implemented Interfaces:

org.apache.commons.collections.primitives.IntCollection, org.apache.commons.collections.primitives.IntList, java.io.Serializable

public class SortableIntList

extends org.apache.commons.collections.primitives.ArrayIntList

A flexible, sortable list of int primitives. Borrows much of its functionality from the ArrayIntList implementation given in the Commons Primitives project (http://jakarta.apache.org/commons/primitives/index.html)

Author:

Chris Johnson

See Also:

Serialized Form

Constructor Summary

SortableIntList()
Construct an empty list with the default initial capacity.

SortableIntList(int initialCapacity)
Construct an empty list with the given initial capacity.

SortableIntList(org.apache.commons.collections.primitives.IntCollection that)
Constructs a list containing the elements of the given collection, in the order they are returned by that collection's iterator.

Method Summary

void	add(int index, int element) Inserts the specified element at the specified position (optional operation).
int	binarySearch(int key) Searches the list for the specified key via Arrays.binarySearch(int[], int)
void	ensureCapacity(int mincap) Increases my capacity, if necessary, to ensure that I can hold at least the number of elements specified by the minimum capacity argument without growing.
int	get(int index)
int	removeElementAt(int index) Removes the element at the specified position in (optional operation).
void	reverse() Reverses the order of the elements
int	set(int index, int element) Replaces the element at the specified position in me with the specified element (optional operation).
int	size()
void	sort() Sorts the list into ascending numerical order via Arrays.sort(int[])
void	sort(int fromIndex, int toIndex) Sorts the specified range of the list into ascending numerical order via Arrays.sort(int[], int, int)
void	swap(int i, int j) Swaps the two specified elements.
void	trimToSize() Reduce my capacity, if necessary, to match my current size.

Methods inherited from class org.apache.commons.collections.primitives.RandomAccessIntList

add, addAll, equals, hashCode, indexOf, iterator, lastIndexOf, listIterator, listIterator, subList, toString

Methods inherited from class org.apache.commons.collections.primitives.AbstractIntCollection

addAll, clear, contains, containsAll, isEmpty, removeAll, removeElement, retainAll, toArray, toArray

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.apache.commons.collections.primitives.IntList

add, addAll, equals, hashCode, indexOf, iterator, lastIndexOf, listIterator, listIterator, subList

Methods inherited from interface org.apache.commons.collections.primitives.IntCollection

addAll, clear, contains, containsAll, isEmpty, removeAll, removeElement, retainAll, toArray, toArray

Constructor Detail

SortableIntList

public SortableIntList()

Construct an empty list with the default initial capacity.

SortableIntList

public SortableIntList(int initialCapacity)

Construct an empty list with the given initial capacity.

Throws:

java.lang.IllegalArgumentException - when initialCapacity is negative

SortableIntList

public SortableIntList(org.apache.commons.collections.primitives.IntCollection that)

Constructs a list containing the elements of the given collection, in the order they are returned by that collection's iterator.

Parameters:

that - the non-null collection of ints to add

Throws:

java.lang.NullPointerException - if that is null

See Also:

AbstractIntCollection.addAll(org.apache.commons.collections.primitives.IntCollection)

Method Detail

get

public int get(int index)

size

public int size()

removeElementAt

public int removeElementAt(int index)

Removes the element at the specified position in (optional operation). Any subsequent elements are shifted to the left, subtracting one from their indices. Returns the element that was removed.

Parameters:

index - the index of the element to remove

Returns:

the value of the element that was removed

Throws:

java.lang.UnsupportedOperationException - when this operation is not supported

java.lang.IndexOutOfBoundsException - if the specified index is out of range

set

public int set(int index,
               int element)

Replaces the element at the specified position in me with the specified element (optional operation). If specified index is beyond the current size, the list grows to accommodate it. No IndexOutOfBoundsException will occur during the set operation.

Parameters:

index - the index of the element to change

element - the value to be stored at the specified position

Returns:

the value previously stored at the specified position

Throws:

java.lang.UnsupportedOperationException - when this operation is not supported

add

public void add(int index,
                int element)

Inserts the specified element at the specified position (optional operation). Shifts the element currently at that position (if any) and any subsequent elements to the right, increasing their indices. If the specified index is beyond the current size, this method behaves like a call to set(int, int).

Parameters:

index - the index at which to insert the element

element - the value to insert

Throws:

java.lang.UnsupportedOperationException - when this operation is not supported

java.lang.IllegalArgumentException - if some aspect of the specified element prevents it from being added to me

ensureCapacity

public void ensureCapacity(int mincap)

Increases my capacity, if necessary, to ensure that I can hold at least the number of elements specified by the minimum capacity argument without growing.

trimToSize

public void trimToSize()

Reduce my capacity, if necessary, to match my current size.

sort

public void sort()

Sorts the list into ascending numerical order via Arrays.sort(int[])

Sorts the list of ints into ascending numerical order. The sorting algorithm is a tuned quicksort, adapted from 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 offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

reverse

public void reverse()

Reverses the order of the elements

swap

public void swap(int i,
                 int j)

Swaps the two specified elements. (If the specified positions are equal, invoking this method leaves the list unchanged.)

binarySearch

public int binarySearch(int key)

Searches the list for the specified key via Arrays.binarySearch(int[], int)

The array must be sorted (as by the sort method, above) prior to making this call. If it is not sorted, the results are undefined. If the list contains multiple elements with the specified value, there is no guarantee which one will be found.

Parameters:

key - the value to be searched for

Returns:

index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1)

sort

public void sort(int fromIndex,
                 int toIndex)

Sorts the specified range of the list into ascending numerical order via Arrays.sort(int[], int, int)

Parameters:

fromIndex - the index of the first element (inclusive) to be sorted

toIndex - the index of the last element (exclusive) to be sorted