goldman.collection.positional
Class SinglyLinkedList<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
      extended by goldman.collection.positional.AbstractPositionalCollection<E>
          extended by goldman.collection.positional.SinglyLinkedList<E>
All Implemented Interfaces:
Collection<E>, PositionalCollection<E>, Tracked<E>, Iterable<E>
Direct Known Subclasses:
DoublyLinkedList

public class SinglyLinkedList<E>
extends AbstractPositionalCollection<E>
implements Tracked<E>

The simplest of the list-based positional collections, SinglyLinkedList maintains a linked list where each list node only references the next element in the list. Our implementation also maintains a reference to the last item in the list. It is a tracked implementation. When using a locator to iterate through the collection, in constant time a new element can be added or the next element in the collection can be removed. The primary drawback of using a singly linked list is that it takes O(p) time to locate the element at position p for 0 ≤ p ≤ n-2. Another weakness of SinglyLinkedList is that it takes O(p) time to find the element that precedes the element at position p. Hence, the retreat method cannot be efficiently implemented. Moreover, in order to efficiently remove a tracked element from position p of the collection, it takes O(p) time.


Nested Class Summary
static class SinglyLinkedList.ListItem<E>
          The ListItem interface must be supported by any class defining objects to be used in a singly linked list or a doubly linked list.
protected  class SinglyLinkedList.Tracker
           
 
Nested classes/interfaces inherited from class goldman.collection.AbstractCollection
AbstractCollection.AbstractLocator<T extends E>, AbstractCollection.VisitingIterator
 
Field Summary
protected  int CUTOFF
          Quicksort is only applied to a subcollection with a size greater than the constant CUTOFF.
protected  SinglyLinkedList.ListItem<E> head
           
 
Fields inherited from class goldman.collection.AbstractCollection
comp, DEFAULT_CAPACITY, FORE, NOT_FOUND, size, version
 
Constructor Summary
SinglyLinkedList()
          Creates an empty collection
 
Method Summary
 void add(E value)
          Inserts it at the end of the positional collection.
 void add(int p, E value)
          Inserts value at position p and increments the position number for the elements that were at positions p to size-1.
protected  void addItemLast(SinglyLinkedList.ListItem<E> x)
           
 Locator<E> addTracked(E value)
          Inserts value into the collection at an arbitrary position.
 void bucketsort(Bucketizer<? super E> bucketizer)
          Sorts this collection using bucket sort with the given bucketizer.
 void clear()
          Removes all elements from the collection.
 boolean contains(E value)
          This implementation for contains takes linear time, so it is overridden by a more efficient method in most data structure implementations.
 E get(int p)
          Returns the element at position p.
 PositionalCollectionLocator<E> getLocator(E element)
          Returns a locator that has been initialized to an element equivalent to target.
protected  SinglyLinkedList.ListItem<E> getPtr(int p)
           
protected  SinglyLinkedList.ListItem<E> getPtrForPrevElement(E value)
           
 void heapsort()
          Uses the default comparator to order the elements
 void heapsort(Comparator<? super E> comp)
          Sorts this collection with heap sort using the provided comparator.
 void heapsortImpl(Comparator sorter)
          Is the implementation of heap sort
protected  PositionalCollectionLocator<E> insertAfter(SinglyLinkedList.ListItem<E> ptr, E value)
          Inserts a list item holding the new element after the list item referenced by ptr
 void insertionsort()
          Sorts this collection with insertion sort using the default comparator.
 void insertionsort(Comparator<? super E> comp)
          Sorts this collection with insertion sort using the default comparator.
 PositionalCollectionLocator<E> iterator()
          Creates a new marker that is at FORE.
 PositionalCollectionLocator<E> iteratorAt(int pos)
          Returns a new marker that is at the given position.
 PositionalCollectionLocator<E> iteratorAtEnd()
          Creates a new marker that is at AFT.
protected  SinglyLinkedList.ListItem<E> merge(Comparator<? super E> comp, SinglyLinkedList.ListItem<E> ptr1, SinglyLinkedList.ListItem<E> ptr2)
          Merges the two lists and
 void mergesort()
          Uses the default comparator to order the elements
 void mergesort(Comparator<? super E> comp)
          Sorts the list using mergesort
protected  SinglyLinkedList.ListItem<E> mergesortImpl(Comparator<? super E> comp, int n, SinglyLinkedList.ListItem<E> ptr)
           
protected  void partition(SinglyLinkedList.ListItem<E> loc, SinglyLinkedList.ListItem<E> beforeEnd, goldman.collection.positional.SinglyLinkedList.Divider divider, Comparator<? super E> comp)
          Partitions the subcollection from loc +1 to beforeEnd+1 (inclusive)
protected  void placeListItemFirst(SinglyLinkedList.ListItem<E> x)
           
 int positionOf(E value)
          Returns the position of the first occurrence (if any) of an element equivalent to value.
 void quicksort()
          Sorts this collection with quicksort using the default comparator.
 void quicksort(Comparator<? super E> comp)
          Sorts the array in place
 void radixsort(Digitizer<? super E> digitizer)
          Sorts this collection using radix sort with the provided digitizer.
 boolean remove(E value)
          Removes the first element in the collection equivalent to value
 E remove(int p)
          Removes the element at position p and decrements the positions of u_{p+1}, ..., u_{size-1} by one.
 E removeFirst()
          Removes the element at position 0 and decrements the position for the elements that were at positions 1 to size-1.
 E removeLast()
          Removes the element at position size-1
protected  E removeNext(SinglyLinkedList.ListItem<E> ptr)
           
 void removeRange(int fromPos, int toPos)
          Requires 0 ≤ fromPostoPos < size.
 E repositionElementByRank(int r)
          Modifies the positional collection so element in position r is in its proper sorted order when using the default comparator, and returns that element.
 E repositionElementByRank(int r, Comparator<? super E> comp)
          Modifies the positional collection so element in position r is in its proper sorted order when using the provided comparator, and returns this element.
protected  void resetList()
          Update the list to be empty without changing the value of size
 E set(int p, E value)
          Replaces the element at position p by the given value, and returns the element that had been in position p.
protected  void setLast(SinglyLinkedList.ListItem<E> last)
           
 void swap(int a, int b)
          Swaps the elements held in positions a and b
protected  void swapAfter(SinglyLinkedList.ListItem<E> aPrev, SinglyLinkedList.ListItem<E> bPrev)
           
 void treesort()
          Uses the default comparator to order the elements
 void treesort(Comparator<? super E> comp)
          Sorts this collection with tree sort using the provided comparator.
protected  void treesortImpl(Comparator sorter)
          Is the implementation of tree sort
 
Methods inherited from class goldman.collection.positional.AbstractPositionalCollection
addFirst, addLast, toString
 
Methods inherited from class goldman.collection.AbstractCollection
accept, addAll, checkRep, compare, ensureCapacity, equivalent, getCapacity, getComparator, getElementAtRank, getElementAtRank, getEquivalentElement, getSize, isEmpty, retainAll, toArray, toArray, traverseForVisitor, trimToSize, writeElements
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface goldman.collection.Collection
accept, addAll, checkRep, ensureCapacity, getCapacity, getComparator, getEquivalentElement, getSize, isEmpty, retainAll, toArray, toArray, toString, trimToSize
 

Field Detail

head

protected SinglyLinkedList.ListItem<E> head

CUTOFF

protected final int CUTOFF
Quicksort is only applied to a subcollection with a size greater than the constant CUTOFF.

See Also:
Constant Field Values
Constructor Detail

SinglyLinkedList

public SinglyLinkedList()
Creates an empty collection

Method Detail

getPtr

protected SinglyLinkedList.ListItem<E> getPtr(int p)
Parameters:
p - a valid user position or -1
Returns:
a reference to the element in the collection at position p or the head sentinel if p = -1

get

public E get(int p)
Description copied from interface: PositionalCollection
Returns the element at position p. It is required that 0 ≤ p ≤ size-1 (i.e., that the position exists in the collection). Otherwise a PositionOutOfBoundsException is thrown.

Specified by:
get in interface PositionalCollection<E>
Parameters:
p - a valid user position
Returns:
the object at the position p
Throws:
PositionOutOfBoundsException - the p is not a valid position

getPtrForPrevElement

protected SinglyLinkedList.ListItem<E> getPtrForPrevElement(E value)
Parameters:
value - the target
Returns:
a reference to the first reachable list item that immediately precedes one holding an element equivalent to value. The method returns null, if there is no equivalent element.

contains

public boolean contains(E value)
Description copied from class: AbstractCollection
This implementation for contains takes linear time, so it is overridden by a more efficient method in most data structure implementations.

Specified by:
contains in interface Collection<E>
Overrides:
contains in class AbstractCollection<E>
Parameters:
value - the target
Returns:
true if and only if an element equivalent to value exists in the collection

positionOf

public int positionOf(E value)
Description copied from interface: PositionalCollection
Returns the position of the first occurrence (if any) of an element equivalent to value. It throws a NoSuchElementException if there is no equivalent element. (The Java collections return -1 when there is no element with the given value, but throwing an exception will better enable a problem to be detected if an application program did not consider the possibility of -1 being returned.)

Specified by:
positionOf in interface PositionalCollection<E>
Parameters:
value - the target
Returns:
the position in the collection for the first occurrence (if any) of an element equivalent to value.
Throws:
NoSuchElementException - no element in the collection is equivalent to value

setLast

protected void setLast(SinglyLinkedList.ListItem<E> last)
Parameters:
last - the list element that is last in the collection.

set

public E set(int p,
             E value)
Description copied from interface: PositionalCollection
Replaces the element at position p by the given value, and returns the element that had been in position p. It is required that 0 ≤ psize-1. Otherwise, a PositionOutOfBoundsException is thrown.

Specified by:
set in interface PositionalCollection<E>
Parameters:
p - a valid user position
value - the element to put at position p
Returns:
the prior element at position p
Throws:
PositionOutOfBoundsException - p is not a valid position

swapAfter

protected void swapAfter(SinglyLinkedList.ListItem<E> aPrev,
                         SinglyLinkedList.ListItem<E> bPrev)
Parameters:
aPrev - a reference to list item before the one to be swapped
bPrev - a reference to the list item before the other one to be swapped

swap

public void swap(int a,
                 int b)
Swaps the elements held in positions a and b

Specified by:
swap in interface PositionalCollection<E>
Parameters:
a - a valid position
b - a valid position
Throws:
PositionOutOfBoundsException - either a or b is not a valid position

insertAfter

protected PositionalCollectionLocator<E> insertAfter(SinglyLinkedList.ListItem<E> ptr,
                                                     E value)
Inserts a list item holding the new element after the list item referenced by ptr

Parameters:
ptr - a reference to a list item in the collection (possibly the sentinel head)
value - the element to insert
Returns:
a tracker to the new element

add

public void add(int p,
                E value)
Inserts value at position p and increments the position number for the elements that were at positions p to size-1.

Specified by:
add in interface PositionalCollection<E>
Parameters:
p - the position where the element is to be placed
value - the element to insert
Throws:
PositionOutofBoundsException - p is neither size nor a valid position

add

public void add(E value)
Inserts it at the end of the positional collection.

Specified by:
add in interface Collection<E>
Parameters:
value - the new element

addTracked

public Locator<E> addTracked(E value)
Inserts value into the collection at an arbitrary position.

Specified by:
addTracked in interface Tracked<E>
Parameters:
value - the new element
Returns:
a tracker that tracks the new element

removeNext

protected E removeNext(SinglyLinkedList.ListItem<E> ptr)
Parameters:
ptr - a reference to the list item (possibly the sentinel head item) preceding the one to remove
REQUIRES: ptr references head or a reachable list item.
Returns:
the removed element
Throws:
NoSuchElementException - ptr references the last list item

removeRange

public void removeRange(int fromPos,
                        int toPos)
Requires 0 ≤ fromPostoPos < size. It removes the elements at positions fromPos, ..., toPos, inclusive, from the collection and decrements the positions of the elements at positions toPos+1 to size-1 by toPos-fromPos+1 (the number of elements being removed)

Specified by:
removeRange in interface PositionalCollection<E>
Parameters:
fromPos - a valid position
toPos - a valid position
Throws:
PositionOutOfBoundsException - either of the arguments is not a valid position
IllegalArgumentException - fromPos is greater than toPos

remove

public E remove(int p)
Removes the element at position p and decrements the positions of u_{p+1}, ..., u_{size-1} by one.

Specified by:
remove in interface PositionalCollection<E>
Parameters:
p - a valid position
Returns:
the removed element
Throws:
PositionOutOfBoundsException - p is not a valid position

removeFirst

public E removeFirst()
Removes the element at position 0 and decrements the position for the elements that were at positions 1 to size-1.

Specified by:
removeFirst in interface PositionalCollection<E>
Returns:
the removed element
Throws:
NoSuchElementException - the collection is empty

removeLast

public E removeLast()
Removes the element at position size-1

Specified by:
removeLast in interface PositionalCollection<E>
Returns:
the removed element
Throws:
NoSuchElementException - the collection is empty

remove

public boolean remove(E value)
Removes the first element in the collection equivalent to value

Specified by:
remove in interface Collection<E>
Parameters:
value - the element to remove
Returns:
true if and only if an element is removed.

clear

public void clear()
Removes all elements from the collection.

Specified by:
clear in interface Collection<E>
Overrides:
clear in class AbstractCollection<E>

iterator

public PositionalCollectionLocator<E> iterator()
Creates a new marker that is at FORE.

Specified by:
iterator in interface Collection<E>
Specified by:
iterator in interface PositionalCollection<E>
Specified by:
iterator in interface Iterable<E>
Specified by:
iterator in class AbstractPositionalCollection<E>

iteratorAtEnd

public PositionalCollectionLocator<E> iteratorAtEnd()
Creates a new marker that is at AFT.

Specified by:
iteratorAtEnd in interface PositionalCollection<E>
Specified by:
iteratorAtEnd in class AbstractPositionalCollection<E>

iteratorAt

public PositionalCollectionLocator<E> iteratorAt(int pos)
Returns a new marker that is at the given position.

Specified by:
iteratorAt in class AbstractPositionalCollection<E>
Parameters:
pos - the user position of an element
Throws:
NoSuchElementException - the given position is not a valid user position.

getLocator

public PositionalCollectionLocator<E> getLocator(E element)
Description copied from interface: Collection
Returns a locator that has been initialized to an element equivalent to target. Like the iterator method, this method enables navigation, but from a specified starting point. This method throws a NoSuchElementException if there is no equivalent element in the collection.

Specified by:
getLocator in interface Collection<E>
Parameters:
element - the element to track
Returns:
a tracker that has been initialized at the given element.
Throws:
NoSuchElementException - the given element is not in the collection.

addItemLast

protected void addItemLast(SinglyLinkedList.ListItem<E> x)
Parameters:
x - the item to be placed at the end of the list

insertionsort

public void insertionsort()
Description copied from interface: PositionalCollection
Sorts this collection with insertion sort using the default comparator.

Specified by:
insertionsort in interface PositionalCollection<E>

insertionsort

public void insertionsort(Comparator<? super E> comp)
Description copied from interface: PositionalCollection
Sorts this collection with insertion sort using the default comparator.

Specified by:
insertionsort in interface PositionalCollection<E>

mergesort

public void mergesort()
Uses the default comparator to order the elements

Specified by:
mergesort in interface PositionalCollection<E>

mergesort

public void mergesort(Comparator<? super E> comp)
Sorts the list using mergesort

Specified by:
mergesort in interface PositionalCollection<E>
Parameters:
comp - the comparator to use to order the elements

mergesortImpl

protected SinglyLinkedList.ListItem<E> mergesortImpl(Comparator<? super E> comp,
                                                     int n,
                                                     SinglyLinkedList.ListItem<E> ptr)
Parameters:
comp - the comparator to use to order the elements
n - the number of elements in this portion of this list
ptr - the pointer to the first item in the list
Returns:
a reference to the first list item in the sorted list

merge

protected SinglyLinkedList.ListItem<E> merge(Comparator<? super E> comp,
                                             SinglyLinkedList.ListItem<E> ptr1,
                                             SinglyLinkedList.ListItem<E> ptr2)
Merges the two lists and

Parameters:
comp - the comparator to use to order the elements
ptr1 - the pointer to the first item in the first list to merge
ptr2 - the pointer to the first item in the second list to merge
Returns:
a reference to the first item in the merged list, which will be one of the two list items passed in as parameters.

resetList

protected void resetList()
Update the list to be empty without changing the value of size


heapsort

public void heapsort()
Uses the default comparator to order the elements

Specified by:
heapsort in interface PositionalCollection<E>

heapsort

public void heapsort(Comparator<? super E> comp)
Description copied from interface: PositionalCollection
Sorts this collection with heap sort using the provided comparator.

Specified by:
heapsort in interface PositionalCollection<E>
Parameters:
comp - the comparator to use to order the elements

heapsortImpl

public void heapsortImpl(Comparator sorter)
Is the implementation of heap sort

Parameters:
sorter - the comparator defined over list items to use

treesort

public void treesort()
Uses the default comparator to order the elements

Specified by:
treesort in interface PositionalCollection<E>

treesort

public void treesort(Comparator<? super E> comp)
Description copied from interface: PositionalCollection
Sorts this collection with tree sort using the provided comparator.

Specified by:
treesort in interface PositionalCollection<E>
Parameters:
comp - the comparator to use to order the elements

treesortImpl

protected void treesortImpl(Comparator sorter)
Is the implementation of tree sort

Parameters:
sorter - the comparator to use

quicksort

public void quicksort()
Description copied from interface: PositionalCollection
Sorts this collection with quicksort using the default comparator.

Specified by:
quicksort in interface PositionalCollection<E>

quicksort

public void quicksort(Comparator<? super E> comp)
Sorts the array in place

Specified by:
quicksort in interface PositionalCollection<E>
Parameters:
comp - the comparator to use to order the elements in the positional collection

partition

protected void partition(SinglyLinkedList.ListItem<E> loc,
                         SinglyLinkedList.ListItem<E> beforeEnd,
                         goldman.collection.positional.SinglyLinkedList.Divider divider,
                         Comparator<? super E> comp)
Partitions the subcollection from loc +1 to beforeEnd+1 (inclusive)

Parameters:
loc - a reference to the list item that references the start of the subcollection to partition
beforeEnd - a reference to the second to last list item in the subcollection to partition

placeListItemFirst

protected void placeListItemFirst(SinglyLinkedList.ListItem<E> x)
Parameters:
x - a reference to the list item to insert to the front of the list

radixsort

public void radixsort(Digitizer<? super E> digitizer)
Description copied from interface: PositionalCollection
Sorts this collection using radix sort with the provided digitizer.

Specified by:
radixsort in interface PositionalCollection<E>
Parameters:
digitizer - the digitizer to use in radix sort

bucketsort

public void bucketsort(Bucketizer<? super E> bucketizer)
Description copied from interface: PositionalCollection
Sorts this collection using bucket sort with the given bucketizer.

Specified by:
bucketsort in interface PositionalCollection<E>
Parameters:
bucketizer - the bucketizer to use

repositionElementByRank

public E repositionElementByRank(int r)
Description copied from interface: PositionalCollection
Modifies the positional collection so element in position r is in its proper sorted order when using the default comparator, and returns that element. This method does not completely sort the collection, but it may mutate it.

Specified by:
repositionElementByRank in interface PositionalCollection<E>
Parameters:
r - the rank of the desired element in the sorted order of the elements
Returns:
the element at rank r when using the default comparator
Throws:
PositionOutOfBoundsException - r is not a valid position

repositionElementByRank

public E repositionElementByRank(int r,
                                 Comparator<? super E> comp)
Description copied from interface: PositionalCollection
Modifies the positional collection so element in position r is in its proper sorted order when using the provided comparator, and returns this element. This method does not completely sort the collection, but it may mutate it.

Specified by:
repositionElementByRank in interface PositionalCollection<E>
Parameters:
r - the rank of the desired element in the sorted order of the elements
comp - the comparator to use for determining the order
Returns:
the element at rank r when using the given comparator
Throws:
NoSuchElementException - the collection is empty or r is not a valid position