ccs.utils
Class SortedArrayList<E>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractList<E>
          java.util.ArrayList<E>
              ccs.utils.SortedArrayList<E>

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<E>, java.util.Collection<E>, java.util.List<E>, java.util.RandomAccess

public class SortedArrayList<E>
extends java.util.ArrayList<E>
implements java.util.RandomAccess

An array-backed list which maintains its elements in order: either their natural order (if they all implement Comparable) or the order provided by a specified Comparator. This structure is useful for lists which are not expected to become very large; for large structures you should probably look at a more sophisticated structure (eg. a TreeSet) instead. MT-UNSAFE.

See Also:

Serialized Form

Field Summary

static int

INITCAP The default initial capacity.

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

SortedArrayList()
An empty list using natural ordering and a default initial capacity.

SortedArrayList(java.util.Comparator<? super E> c)
An empty list using a comparator and default initial capacity.

SortedArrayList(int initcap, java.util.Comparator<? super E> c)
An empty list using a comparator and an initial capacity.

Method Summary

boolean	add(E o) Add the object, in its correct location (NB. not necessarily at the end).
void	add(int idx, E o) In order to ensure ordering, this method is not supported.
int	firstIndexOf(java.lang.Object o) Return the index of the first (guaranteed) object equal to that supplied.
E	get(java.lang.Object o) Return an object from the list which is equal to the specified object, if present; otherwise null.
int	indexOf(java.lang.Object o) Return the index of the object, if present, or -1 if not.
int	lastIndexOf(java.lang.Object o) Return the index of the last (guaranteed) object equal to that supplied.
void	removeRange(int fromIdx, int toIdx) Remove a range of members.
protected int	seek(java.lang.Object o) Find the index of the specified object, if present; if not, returns -(x+1) where x is the index where the object should be inserted.
E	set(int idx, E o) Replace the existing element at the specified index with a new one.

Methods inherited from class java.util.ArrayList

addAll, addAll, clear, clone, contains, ensureCapacity, get, isEmpty, remove, remove, size, toArray, toArray, trimToSize

Methods inherited from class java.util.AbstractList

equals, hashCode, iterator, listIterator, listIterator, subList

Methods inherited from class java.util.AbstractCollection

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

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

Field Detail

INITCAP

public static final int INITCAP

The default initial capacity.

See Also:

Constant Field Values

Constructor Detail

SortedArrayList

public SortedArrayList()

An empty list using natural ordering and a default initial capacity.

SortedArrayList

public SortedArrayList(java.util.Comparator<? super E> c)

An empty list using a comparator and default initial capacity.

SortedArrayList

public SortedArrayList(int initcap,
                       java.util.Comparator<? super E> c)

An empty list using a comparator and an initial capacity.

Parameters:

initcap - The initial capacity.

c - The comparator. Supply null for natural ordering.

Method Detail

add

public boolean add(E o)

Add the object, in its correct location (NB. not necessarily at the end). In order to ensure that the array stays sorted, add at arbitrary index is not supported. If the object, or an object equal to it according to the comparator / natural ordering, is already present, the new object will be inserted consistent with the ordering, but its position relative to its equal/s is undefined.

Specified by:

add in interface java.util.Collection<E>

Specified by:

add in interface java.util.List<E>

Overrides:

add in class java.util.ArrayList<E>

Returns:

true (per Collection.add)

add

public void add(int idx,
                E o)

In order to ensure ordering, this method is not supported.

Specified by:

add in interface java.util.List<E>

Overrides:

add in class java.util.ArrayList<E>

get

public E get(java.lang.Object o)

Return an object from the list which is equal to the specified object, if present; otherwise null.

set

public E set(int idx,
             E o)

Replace the existing element at the specified index with a new one.

Specified by:

set in interface java.util.List<E>

Overrides:

set in class java.util.ArrayList<E>

Throws:

java.lang.IllegalArgumentException - if the new object would not be in order with respect to its neighbours.

indexOf

public int indexOf(java.lang.Object o)

Return the index of the object, if present, or -1 if not. This method is efficient, O(log N). NB. Where multiple equal objects are present, this is *not* guaranteed to be the first instance; you'll get one arbitrarily.

Specified by:

indexOf in interface java.util.List<E>

Overrides:

indexOf in class java.util.ArrayList<E>

firstIndexOf

public int firstIndexOf(java.lang.Object o)

Return the index of the first (guaranteed) object equal to that supplied. If there are many equal objects in the list, this may be significantly slower than indexOf.

lastIndexOf

public int lastIndexOf(java.lang.Object o)

Return the index of the last (guaranteed) object equal to that supplied. If there are many equal objects in the list, this may be significantly slower than indexOf.

Specified by:

lastIndexOf in interface java.util.List<E>

Overrides:

lastIndexOf in class java.util.ArrayList<E>

removeRange

public void removeRange(int fromIdx,
                        int toIdx)

Remove a range of members.

Overrides:

removeRange in class java.util.ArrayList<E>

Parameters:

fromIdx - The first index to remove (ie. inclusive).

toIdx - The first subsequent index to *leave* (ie. exclusive). If fromIdx >= toIdx the method does nothing.

seek

protected int seek(java.lang.Object o)

Find the index of the specified object, if present; if not, returns -(x+1) where x is the index where the object should be inserted.