com.scottlogic.util
Class UnsortedList<T>

java.lang.Object
  extended by java.util.AbstractCollection<E>
      extended by java.util.AbstractList<T>
          extended by com.scottlogic.util.SortedList<T>
              extended by com.scottlogic.util.UnsortedList<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>

public class UnsortedList<T>
extends SortedList<T>

Implementation of a regular list that uses an AVL tree. Supports all optional operations.

Performs the operations: add(int, Object), get and remove(int) operations in in time O(log(n)) and the contains(Object) and remove(Object) operations in time O(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.0
Author:
Mark Rhodes
See Also:
Collection, AbstractList, Serialized Form

Nested Class Summary
protected  class UnsortedList.UnsortedNode
          Class representing the individual nodes of an unsorted list extends the regular SortedList.Node class by storing the position of the node in the tree.
 
Nested classes/interfaces inherited from class com.scottlogic.util.SortedList
SortedList.Node
 
Field Summary
 
Fields inherited from class java.util.AbstractList
modCount
 
Constructor Summary
UnsortedList()
          Constructs a new UnsortedList.
 
Method Summary
 void add(int index, T element)
          Inserts the specified element at the specified position in this list.
 boolean add(T object)
          Adds the given object to the end of this UnsortedList, which can be null.
 void addToHead(T element)
          Adds the given element to the head of this list.
 boolean contains(java.lang.Object obj)
          Returns whether or not the given object whether or not the given object is present in this UnsortedList.
 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.
 T set(int index, T element)
          Replaces the element at the specified position in this list with the specified element.
 
Methods inherited from class com.scottlogic.util.SortedList
add, clear, findFirstNodeWithValue, findNodeAtIndex, get, getRoot, isEmpty, iterator, remove, remove, size, toArray, toArray
 
Methods inherited from class java.util.AbstractList
addAll, equals, hashCode, indexOf, lastIndexOf, listIterator, listIterator, removeRange, 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

UnsortedList

public UnsortedList()
Constructs a new UnsortedList.

Method Detail

set

public T set(int index,
             T element)
Replaces the element at the specified position in this list with the specified element.

Specified by:
set in interface java.util.List<T>
Overrides:
set in class java.util.AbstractList<T>
Parameters:
index - the index in this UnsortedList to add this given element.
element - the object to add to this UnsortedList.
Returns:
the element that was replaced at the given index.
Throws:
java.lang.IllegalArgumentException - in the case that the element is null.
java.lang.IndexOutOfBoundsException - in the case that (0 <= index < size()) does not hold.

contains

public boolean contains(java.lang.Object obj)
Returns whether or not the given object whether or not the given object is present in this UnsortedList.

This implementation takes O(n) time, where n is the number of element in this list.

Specified by:
contains in interface java.util.Collection<T>
Specified by:
contains in interface java.util.List<T>
Overrides:
contains in class SortedList<T>
Parameters:
obj - the object to check for.
Returns:
true if the given object is present in this UnsortedList and false otherwise.

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. Works in time O(n), where i is the number of elements in this UnsortedList.

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 SortedList<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.

add

public void add(int index,
                T element)
Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

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

Specified by:
add in interface java.util.List<T>
Overrides:
add in class java.util.AbstractList<T>
Parameters:
index - at which the element should be added.
element - the object to by inserted.
Throws:
java.lang.IllegalArgumentException - in the case that the given element is null.
java.lang.IndexOutOfBoundsException - in the case that (0 <= index <= size()) does not hold.

addToHead

public void addToHead(T element)
Adds the given element to the head of this list. Shifts the elements currently in the list (if any) to the right (adds one to their indices).

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

Parameters:
element - the object to by inserted.
Throws:
java.lang.IllegalArgumentException - in the case that the given element is null.

add

public boolean add(T object)
Adds the given object to the end of this UnsortedList, which can be null.

Specified by:
add in interface java.util.Collection<T>
Specified by:
add in interface java.util.List<T>
Overrides:
add in class SortedList<T>
Parameters:
object - the object to add.
Returns:
true.