com.scottlogic.util
Class SortedList<T>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractList<T>
          com.scottlogic.util.SortedList<T>

Type Parameters:

T - the type of element that this sorted list will store.

All Implemented Interfaces:

java.io.Serializable, java.lang.Iterable<T>, java.util.Collection<T>, java.util.List<T>

Direct Known Subclasses:

NaturalSortedList, UnsortedList

public class SortedList<T>
extends java.util.AbstractList<T>
implements java.io.Serializable

SortedList is an implementation of a List, backed by an AVL tree. Does not support any optional operations, with the exception of: remove(int), remove(Object), clear and add().

Performs all the main operations: contains, add, remove and get in time O(log(n)), where n is the number of elements in the list.

This implementation is not synchronised so if you need multi-threaded access then consider wrapping it using the Collections.synchronizedList(java.util.List) method.

The iterators this list provides are fail-fast, so any structural modification, other than through the iterator itself, cause it to throw a ConcurrentModificationException.

Version:

1.3

Author:

Mark Rhodes

See Also:

List, Collection, AbstractList, Serialized Form

Nested Class Summary

protected class

SortedList.Node Inner class used to represent positions in the tree.

Field Summary

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

SortedList(java.util.Comparator<? super T> comparator)
Constructs a new, empty SortedList which sorts the elements according to the given Comparator.

Method Summary

protected void	add(SortedList.Node toAdd) Add the given Node to this SortedList.
boolean	add(T object) Inserts the given object into this {code SortedList} at the appropriate location, so as to ensure that the elements in the list are kept in the order specified by the given Comparator.
void	clear() Removes all elements from the list, leaving it empty.
boolean	contains(java.lang.Object obj) Returns whether or not the given object is present in this SortedList.
protected SortedList.Node	findFirstNodeWithValue(T value) Returns the node representing the given value in the tree, which can be null if no such node exists.
protected SortedList.Node	findNodeAtIndex(int index) Returns the Node at the given index.
T	get(int index) Returns the element at the given index in this SortedList.
protected SortedList.Node	getRoot() Returns the root node of this SortedList, which is null in the case that this list is empty.
boolean	isEmpty() Returns whether or not the list contains any elements.
java.util.Iterator<T>	iterator() Provides an Iterator which provides the elements of this SortedList in the order determined by the given Comparator.
T	remove(int index) Removes and returns the element at the given index in this SortedList.
boolean	remove(java.lang.Object value) Removes the first element in the list with the given value, if such a node exists, otherwise does nothing.
protected void	remove(SortedList.Node toRemove) Removes the given Node from this SortedList, re-balancing if required, adds to modCount too.
int	size() Returns the number of elements in this SortedList.
java.lang.Object[]	toArray() Returns a new array containing all the elements in this SortedList.
<E> E[]	toArray(E[] holder) Copies the elements in the SortedList to the given array if it is large enough to store them, otherwise it returns a new array of the same type with the elements in it.

Methods inherited from class java.util.AbstractList

add, addAll, equals, hashCode, indexOf, lastIndexOf, listIterator, listIterator, removeRange, set, subList

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, removeAll, retainAll, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.List

addAll, containsAll, removeAll, retainAll

Constructor Detail

SortedList

public SortedList(java.util.Comparator<? super T> comparator)

Constructs a new, empty SortedList which sorts the elements according to the given Comparator.

Parameters:

comparator - the Comparator to sort the elements by.

Method Detail

add

public boolean add(T object)

Inserts the given object into this {code SortedList} at the appropriate location, so as to ensure that the elements in the list are kept in the order specified by the given Comparator.

This method only allows non-null values to be added, if the given object is null, the list remains unaltered and false returned.

Specified by:

add in interface java.util.Collection<T>

Specified by:

add in interface java.util.List<T>

Overrides:

add in class java.util.AbstractList<T>

Parameters:

object - the object to add.

Returns:

false when the given object is null and true otherwise.

add

protected void add(SortedList.Node toAdd)

Add the given Node to this SortedList.

This method can be overridden by a subclass in order to change the definition of the Nodes that this List will store.

This implementation uses the Node#compareTo(Node) method in order to ascertain where the given Node should be stored. It also increments the modCount for this list.

Parameters:

toAdd - the Node to add.

iterator

public java.util.Iterator<T> iterator()

Provides an Iterator which provides the elements of this SortedList in the order determined by the given Comparator.

This implementation allows the entire list to be iterated over in time O(n), where n is the number of elements in the list.

Specified by:

iterator in interface java.lang.Iterable<T>

Specified by:

iterator in interface java.util.Collection<T>

Specified by:

iterator in interface java.util.List<T>

Overrides:

iterator in class java.util.AbstractList<T>

Returns:

an Iterator which provides the elements of this SortedList in the order determined by the given Comparator.

size

public int size()

Returns the number of elements in this SortedList.

Specified by:

size in interface java.util.Collection<T>

Specified by:

size in interface java.util.List<T>

Specified by:

size in class java.util.AbstractCollection<T>

Returns:

the number of elements stored in this SortedList.

getRoot

protected SortedList.Node getRoot()

Returns the root node of this SortedList, which is null in the case that this list is empty.

Returns:

the root node of this SortedList, which is null in the case that this list is empty.

contains

public boolean contains(java.lang.Object obj)

Returns whether or not the given object is present in this SortedList. The comparison check uses the Object#equals(Object) method and work under the assumption that the given obj must have type T to be equal to the elements in this SortedList. Works in time O(log(n)), where n is the number of elements in the list.

Specified by:

contains in interface java.util.Collection<T>

Specified by:

contains in interface java.util.List<T>

Overrides:

contains in class java.util.AbstractCollection<T>

Parameters:

obj - the object to check for.

Returns:

true if the given object is present in this {code SortedList}.

findFirstNodeWithValue

protected SortedList.Node findFirstNodeWithValue(T value)

Returns the node representing the given value in the tree, which can be null if no such node exists.

This method performs a binary search using the given comparator, and hence works in time O(log(n)).

Parameters:

value - the value to search for.

Returns:

the first node in this list with the given value.

remove

public T remove(int index)

Removes and returns the element at the given index in this SortedList. Since the list is sorted this is the "index"-th smallest element, counting from 0-n-1.

For example, calling remove(0) will remove the smallest element in the list.

Specified by:

remove in interface java.util.List<T>

Overrides:

remove in class java.util.AbstractList<T>

Parameters:

index - the index of the element to remove.

Returns:

the element which was removed from the list.

Throws:

java.lang.IllegalArgumentException - in the case that the index is not a valid index.

remove

public boolean remove(java.lang.Object value)

Removes the first element in the list with the given value, if such a node exists, otherwise does nothing. Comparisons on elements are done using the given comparator.

Returns whether or not a matching element was found and removed or not.

Specified by:

remove in interface java.util.Collection<T>

Specified by:

remove in interface java.util.List<T>

Overrides:

remove in class java.util.AbstractCollection<T>

Parameters:

value - the object to remove from this SortedList.

Returns:

true if the given object was found in this SortedList and removed, false otherwise.

remove

protected void remove(SortedList.Node toRemove)

Removes the given Node from this SortedList, re-balancing if required, adds to modCount too.

Operates in time O(log(n)), where n is the number of elements in the list.

Parameters:

toRemove - the Node, which must be a Node in this SortedList.

get

public T get(int index)

Returns the element at the given index in this SortedList. Since the list is sorted, this is the "index"th smallest element, counting from 0-n-1.

For example, calling get(0) will return the smallest element in the list.

Specified by:

get in interface java.util.List<T>

Specified by:

get in class java.util.AbstractList<T>

Parameters:

index - the index of the element to get.

Returns:

the element at the given index in this SortedList.

Throws:

java.lang.IllegalArgumentException - in the case that the index is not a valid index.

findNodeAtIndex

protected SortedList.Node findNodeAtIndex(int index)

Returns the Node at the given index.

Parameters:

index - the index to search for.

Returns:

the Node object at the specified index.

Throws:

java.lang.IllegalArgumentException - in the case that the the index is not valid.

isEmpty

public boolean isEmpty()

Returns whether or not the list contains any elements.

Specified by:

isEmpty in interface java.util.Collection<T>

Specified by:

isEmpty in interface java.util.List<T>

Overrides:

isEmpty in class java.util.AbstractCollection<T>

Returns:

true if the list has no element in it and false otherwise.

clear

public void clear()

Removes all elements from the list, leaving it empty.

Specified by:

clear in interface java.util.Collection<T>

Specified by:

clear in interface java.util.List<T>

Overrides:

clear in class java.util.AbstractList<T>

toArray

public java.lang.Object[] toArray()

Returns a new array containing all the elements in this SortedList.

Specified by:

toArray in interface java.util.Collection<T>

Specified by:

toArray in interface java.util.List<T>

Overrides:

toArray in class java.util.AbstractCollection<T>

Returns:

an array representation of this list.

toArray

public <E> E[] toArray(E[] holder)

Copies the elements in the SortedList to the given array if it is large enough to store them, otherwise it returns a new array of the same type with the elements in it.

If the length of the given array is larger than the size of this SortedList then, the elements in this list are put into the start of the given array and the rest of the array is left untouched.

Specified by:

toArray in interface java.util.Collection<T>

Specified by:

toArray in interface java.util.List<T>

Overrides:

toArray in class java.util.AbstractCollection<T>

Returns:

an array representation of this list.

Throws:

java.lang.ClassCastException - in the case that the provided array can not hold objects of this type stored in this SortedList.