org.dhmp.util
Class CircularQueue

java.lang.Object
  extended byorg.dhmp.util.AbstractCollection
      extended byorg.dhmp.util.AbstractList
          extended byorg.dhmp.util.AbstractSequentialList
              extended byorg.dhmp.util.LinkedList
                  extended byorg.dhmp.util.CircularQueue
All Implemented Interfaces:
java.lang.Cloneable, java.util.Collection, java.util.List, java.io.Serializable

public class CircularQueue
extends org.dhmp.util.LinkedList

Circular Queue is a queue implemented using linked list that reuse the existent entries to store new data or appends new entry if all existent entries are not free (for instance value has added but still has not read). Once the value has read using get(), the corresponding entry is freed. Therefore the size of this linkedlist is the number of entries in a queue during the peak. Use shrink() to free-up unused entries.

Author:
hideyuki
See Also:
Serialized Form

Nested Class Summary
 class CircularQueue.CircularQueueEntry
           
protected static class LinkedList.Entry
          Class to represent an entry in the list.
 
Field Summary
protected  LinkedList.Entry first
          The first element in the list.
protected  CircularQueue.CircularQueueEntry head
           
protected  LinkedList.Entry last
          The last element in the list.
protected  int modCount
          A count of the number of structural modifications that have been made to the list (that is, insertions and removals).
protected  int size
          The current length of the list.
protected  CircularQueue.CircularQueueEntry tail
           
 
Constructor Summary
CircularQueue()
          Creates a new instance of CircularQueue
 
Method Summary
 void add(int index, java.lang.Object o)
          Inserts an element in the given position in the list.
 boolean add(java.lang.Object o)
          Adds an element to the end of the list.
protected  void addAfter(LinkedList.Entry e, java.lang.Object o)
           
 boolean addAll(java.util.Collection c)
          Append the elements of the collection in iteration order to the end of this list.
 boolean addAll(int index, java.util.Collection c)
          Insert the elements of the collection in iteration order at the given index of this list.
 void addFirst(java.lang.Object o)
          Insert an element at the first of the list.
 void addLast(java.lang.Object o)
          Insert an element at the last of the list.
 void clear()
          Remove all elements from this list.
 java.lang.Object clone()
          Create a shallow copy of this LinkedList (the elements are not cloned).
 boolean contains(java.lang.Object o)
          Returns true if the list contains the given object.
 boolean containsAll(java.util.Collection c)
          Tests whether this collection contains all the elements in a given collection.
 boolean equals(java.lang.Object o)
          Test whether this list is equal to another object.
 java.lang.Object get()
           
 java.lang.Object get(int index)
          Return the element at index.
protected  LinkedList.Entry getEntry()
           
 java.lang.Object getFirst()
          Returns the first element in the list.
 java.lang.Object getLast()
          Returns the last element in the list.
 int hashCode()
          Obtains a hash code for this list.
 int indexOf(java.lang.Object o)
          Returns the first index where the element is located in the list, or -1.
 boolean isEmpty()
          Test whether this collection is empty.
 java.util.Iterator iterator()
          Obtain an Iterator over this list, whose sequence is the list order.
 int lastIndexOf(java.lang.Object o)
          Returns the last index where the element is located in the list, or -1.
 java.util.ListIterator listIterator()
          Obtain a ListIterator over this list, starting at the beginning.
 java.util.ListIterator listIterator(int index)
          Obtain a ListIterator over this list, starting at a given index.
 LinkedList.Entry newEntry(java.lang.Object o)
          Extension point for inferited class.
 java.lang.Object remove(int index)
          Removes the element at the given position from the list.
 boolean remove(java.lang.Object o)
          Removes the entry at the lowest index in the list that matches the given object, comparing by if o equals null, then compare if e equals null otherwise return o equals e.
 boolean removeAll(java.util.Collection c)
          Remove from this collection all its elements that are contained in a given collection (optional operation).
 java.lang.Object removeFirst()
          Remove and return the first element in the list.
 java.lang.Object removeLast()
          Remove and return the last element in the list.
protected  void removeRange(int fromIndex, int toIndex)
          Remove a subsection of the list.
 boolean retainAll(java.util.Collection c)
          Remove from this collection all its elements that are not contained in a given collection (optional operation).
 java.lang.Object set(int index, java.lang.Object o)
          Replace the element at the given location in the list.
 void shrink()
           
 int size()
          Returns the size of the list.
 java.util.List subList(int fromIndex, int toIndex)
          Obtain a List view of a subsection of this list, from fromIndex (inclusive) to toIndex (exclusive).
 java.lang.Object[] toArray()
          Returns an array which contains the elements of the list in order.
 java.lang.Object[] toArray(java.lang.Object[] a)
          Returns an Array whose component type is the runtime component type of the passed-in Array.
 java.lang.String toString()
          Creates a String representation of the Collection.
 
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, removeAll, retainAll, subList
 

Field Detail

head

protected CircularQueue.CircularQueueEntry head

tail

protected CircularQueue.CircularQueueEntry tail

first

protected transient LinkedList.Entry first
The first element in the list.


last

protected transient LinkedList.Entry last
The last element in the list.


size

protected transient int size
The current length of the list.


modCount

protected transient int modCount
A count of the number of structural modifications that have been made to the list (that is, insertions and removals). Structural modifications are ones which change the list size or affect how iterations would behave. This field is available for use by Iterator and ListIterator, in order to throw a ConcurrentModificationException in response to the next operation on the iterator. This fail-fast behavior saves the user from many subtle bugs otherwise possible from concurrent modification during iteration.

To make lists fail-fast, increment this field by just 1 in the add(int, Object) and remove(int) methods. Otherwise, this field may be ignored.

Constructor Detail

CircularQueue

public CircularQueue()
Creates a new instance of CircularQueue

Method Detail

add

public boolean add(java.lang.Object o)
Description copied from class: org.dhmp.util.LinkedList
Adds an element to the end of the list.

Parameters:
o - the entry to add
Returns:
true, as it always succeeds

addAfter

protected void addAfter(LinkedList.Entry e,
                        java.lang.Object o)

get

public java.lang.Object get()

getEntry

protected LinkedList.Entry getEntry()

isEmpty

public boolean isEmpty()
Description copied from class: org.dhmp.util.AbstractCollection
Test whether this collection is empty. This implementation returns size() == 0.

Returns:
true if this collection is empty.
See Also:
AbstractCollection.size()

shrink

public void shrink()

newEntry

public LinkedList.Entry newEntry(java.lang.Object o)
Description copied from class: org.dhmp.util.LinkedList
Extension point for inferited class.

Parameters:
o - the object associated to the entry
Returns:
new Entry

getFirst

public java.lang.Object getFirst()
Returns the first element in the list.

Returns:
the first list element
Throws:
java.util.NoSuchElementException - if the list is empty

getLast

public java.lang.Object getLast()
Returns the last element in the list.

Returns:
the last list element
Throws:
java.util.NoSuchElementException - if the list is empty

removeFirst

public java.lang.Object removeFirst()
Remove and return the first element in the list.

Returns:
the former first element in the list
Throws:
java.util.NoSuchElementException - if the list is empty

removeLast

public java.lang.Object removeLast()
Remove and return the last element in the list.

Returns:
the former last element in the list
Throws:
java.util.NoSuchElementException - if the list is empty

addFirst

public void addFirst(java.lang.Object o)
Insert an element at the first of the list.

Parameters:
o - the element to insert

addLast

public void addLast(java.lang.Object o)
Insert an element at the last of the list.

Parameters:
o - the element to insert

contains

public boolean contains(java.lang.Object o)
Returns true if the list contains the given object. Comparison is done by o == null ? e = null : o.equals(e).

Specified by:
contains in interface java.util.List
Parameters:
o - the element to look for
Returns:
true if it is found

size

public int size()
Returns the size of the list.

Specified by:
size in interface java.util.List
Returns:
the list size

remove

public boolean remove(java.lang.Object o)
Removes the entry at the lowest index in the list that matches the given object, comparing by if o equals null, then compare if e equals null otherwise return o equals e.

Specified by:
remove in interface java.util.List
Parameters:
o - the object to remove
Returns:
true if an instance of the object was removed
See Also:
Iterator.remove()

addAll

public boolean addAll(java.util.Collection c)
Append the elements of the collection in iteration order to the end of this list. If this list is modified externally (for example, if this list is the collection), behavior is unspecified.

Specified by:
addAll in interface java.util.List
Parameters:
c - the collection to append
Returns:
true if the list was modified
Throws:
java.lang.NullPointerException - if c is null
See Also:
AbstractCollection.add(Object)

addAll

public boolean addAll(int index,
                      java.util.Collection c)
Insert the elements of the collection in iteration order at the given index of this list. If this list is modified externally (for example, if this list is the collection), behavior is unspecified.

Specified by:
addAll in interface java.util.List
Parameters:
c - the collection to append
index - the location to insert the collection
Returns:
true if the list was modified
Throws:
java.lang.NullPointerException - if c is null
java.lang.IndexOutOfBoundsException - if index < 0 || index > size()
See Also:
AbstractSequentialList.add(int, Object)

clear

public void clear()
Remove all elements from this list.

Specified by:
clear in interface java.util.List
See Also:
AbstractList.remove(int), AbstractList.removeRange(int, int)

get

public java.lang.Object get(int index)
Return the element at index.

Specified by:
get in interface java.util.List
Parameters:
index - the place to look
Returns:
the element at index
Throws:
java.lang.IndexOutOfBoundsException - if index < 0 || index >= size()

set

public java.lang.Object set(int index,
                            java.lang.Object o)
Replace the element at the given location in the list.

Specified by:
set in interface java.util.List
Parameters:
index - which index to change
o - the new element
Returns:
the prior element
Throws:
java.lang.IndexOutOfBoundsException - if index < 0 || index >= size()

add

public void add(int index,
                java.lang.Object o)
Inserts an element in the given position in the list.

Specified by:
add in interface java.util.List
Parameters:
index - where to insert the element
o - the element to insert
Throws:
java.lang.IndexOutOfBoundsException - if index < 0 || index > size()

remove

public java.lang.Object remove(int index)
Removes the element at the given position from the list.

Specified by:
remove in interface java.util.List
Parameters:
index - the location of the element to remove
Returns:
the removed element
Throws:
java.lang.IndexOutOfBoundsException - if index < 0 || index > size()

indexOf

public int indexOf(java.lang.Object o)
Returns the first index where the element is located in the list, or -1.

Specified by:
indexOf in interface java.util.List
Parameters:
o - the element to look for
Returns:
its position, or -1 if not found

lastIndexOf

public int lastIndexOf(java.lang.Object o)
Returns the last index where the element is located in the list, or -1.

Specified by:
lastIndexOf in interface java.util.List
Parameters:
o - the element to look for
Returns:
its position, or -1 if not found

listIterator

public java.util.ListIterator listIterator(int index)
Obtain a ListIterator over this list, starting at a given index. The ListIterator returned by this method supports the add, remove and set methods.

Specified by:
listIterator in interface java.util.List
Parameters:
index - the index of the element to be returned by the first call to next(), or size() to be initially positioned at the end of the list
Returns:
the list iterator
Throws:
java.lang.IndexOutOfBoundsException - if index < 0 || index > size()

clone

public java.lang.Object clone()
Create a shallow copy of this LinkedList (the elements are not cloned).

Returns:
an object of the same class as this object, containing the same elements in the same order

toArray

public java.lang.Object[] toArray()
Returns an array which contains the elements of the list in order.

Specified by:
toArray in interface java.util.List
Returns:
an array containing the list elements

toArray

public java.lang.Object[] toArray(java.lang.Object[] a)
Returns an Array whose component type is the runtime component type of the passed-in Array. The returned Array is populated with all of the elements in this LinkedList. If the passed-in Array is not large enough to store all of the elements in this List, a new Array will be created and returned; if the passed-in Array is larger than the size of this List, then size() index will be set to null.

Specified by:
toArray in interface java.util.List
Parameters:
a - the passed-in Array
Returns:
an array representation of this list
Throws:
java.lang.ArrayStoreException - if the runtime type of a does not allow an element in this list
java.lang.NullPointerException - if a is null

iterator

public java.util.Iterator iterator()
Obtain an Iterator over this list, whose sequence is the list order. This implementation returns listIterator().

Returns:
an Iterator over the elements of this list, in order
See Also:
AbstractList.modCount

equals

public boolean equals(java.lang.Object o)
Test whether this list is equal to another object. A List is defined to be equal to an object if and only if that object is also a List, and the two lists have the same sequence. Two lists l1 and l2 are equal if and only if l1.size() == l2.size(), and for every integer n between 0 and l1.size() - 1 inclusive, l1.get(n) == null ? l2.get(n) == null : l1.get(n).equals(l2.get(n)).

This implementation returns true if the object is this, or false if the object is not a List. Otherwise, it iterates over both lists (with iterator()), returning false if two elements compare false or one list is shorter, and true if the iteration completes successfully.

Specified by:
equals in interface java.util.List
Parameters:
o - the object to test for equality with this list
Returns:
true if o is equal to this list
See Also:
Object.equals(Object), AbstractList.hashCode()

hashCode

public int hashCode()
Obtains a hash code for this list. In order to obey the general contract of the hashCode method of class Object, this value is calculated as follows:
hashCode = 1;
Iterator i = list.iterator();
while (i.hasNext())
{
  Object obj = i.next();
  hashCode = 31 * hashCode + (obj == null ? 0 : obj.hashCode());
}
This ensures that the general contract of Object.hashCode() is adhered to.

Specified by:
hashCode in interface java.util.List
Returns:
the hash code of this list
See Also:
Object.hashCode(), AbstractList.equals(Object)

listIterator

public java.util.ListIterator listIterator()
Obtain a ListIterator over this list, starting at the beginning. This implementation returns listIterator(0).

Specified by:
listIterator in interface java.util.List
Returns:
a ListIterator over the elements of this list, in order, starting at the beginning

removeRange

protected void removeRange(int fromIndex,
                           int toIndex)
Remove a subsection of the list. This is called by the clear and removeRange methods of the class which implements subList, which are difficult for subclasses to override directly. Therefore, this method should be overridden instead by the more efficient implementation, if one exists. Overriding this can reduce quadratic efforts to constant time in some cases!

This implementation first checks for illegal or out of range arguments. It then obtains a ListIterator over the list using listIterator(fromIndex). It then calls next() and remove() on this iterator repeatedly, toIndex - fromIndex times.

Parameters:
fromIndex - the index, inclusive, to remove from.
toIndex - the index, exclusive, to remove to.
Throws:
java.lang.UnsupportedOperationException - if the list does not support removing elements.

subList

public java.util.List subList(int fromIndex,
                              int toIndex)
Obtain a List view of a subsection of this list, from fromIndex (inclusive) to toIndex (exclusive). If the two indices are equal, the sublist is empty. The returned list should be modifiable if and only if this list is modifiable. Changes to the returned list should be reflected in this list. If this list is structurally modified in any way other than through the returned list, the result of any subsequent operations on the returned list is undefined.

This implementation returns a subclass of AbstractList. It stores, in private fields, the offset and size of the sublist, and the expected modCount of the backing list. If the backing list implements RandomAccess, the sublist will also.

The subclass's set(int, Object), get(int), add(int, Object), remove(int), addAll(int, Collection) and removeRange(int, int) methods all delegate to the corresponding methods on the backing abstract list, after bounds-checking the index and adjusting for the offset. The addAll(Collection c) method merely returns addAll(size, c). The listIterator(int) method returns a "wrapper object" over a list iterator on the backing list, which is created with the corresponding method on the backing list. The iterator() method merely returns listIterator(), and the size() method merely returns the subclass's size field.

All methods first check to see if the actual modCount of the backing list is equal to its expected value, and throw a ConcurrentModificationException if it is not.

Specified by:
subList in interface java.util.List
Parameters:
fromIndex - the index that the returned list should start from (inclusive)
toIndex - the index that the returned list should go to (exclusive)
Returns:
a List backed by a subsection of this list
Throws:
java.lang.IndexOutOfBoundsException - if fromIndex < 0 || toIndex > size()
java.lang.IllegalArgumentException - if fromIndex > toIndex
See Also:
ConcurrentModificationException, RandomAccess

containsAll

public boolean containsAll(java.util.Collection c)
Tests whether this collection contains all the elements in a given collection. This implementation iterates over the given collection, testing whether each element is contained in this collection. If any one is not, false is returned. Otherwise true is returned.

Specified by:
containsAll in interface java.util.Collection
Parameters:
c - the collection to test against
Returns:
true if this collection contains all the elements in the given collection
Throws:
java.lang.NullPointerException - if the given collection is null
See Also:
AbstractCollection.contains(Object)

removeAll

public boolean removeAll(java.util.Collection c)
Remove from this collection all its elements that are contained in a given collection (optional operation). This implementation iterates over this collection, and for each element tests if it is contained in the given collection. If so, it is removed by the Iterator's remove method (thus this method will fail with an UnsupportedOperationException if the Iterator's remove method does).

Specified by:
removeAll in interface java.util.Collection
Parameters:
c - the collection to remove the elements of
Returns:
true if the remove operation caused the Collection to change
Throws:
java.lang.UnsupportedOperationException - if this collection's Iterator does not support the remove method
java.lang.NullPointerException - if the collection, c, is null.
See Also:
Iterator.remove()

retainAll

public boolean retainAll(java.util.Collection c)
Remove from this collection all its elements that are not contained in a given collection (optional operation). This implementation iterates over this collection, and for each element tests if it is contained in the given collection. If not, it is removed by the Iterator's remove method (thus this method will fail with an UnsupportedOperationException if the Iterator's remove method does).

Specified by:
retainAll in interface java.util.Collection
Parameters:
c - the collection to retain the elements of
Returns:
true if the remove operation caused the Collection to change
Throws:
java.lang.UnsupportedOperationException - if this collection's Iterator does not support the remove method
java.lang.NullPointerException - if the collection, c, is null.
See Also:
Iterator.remove()

toString

public java.lang.String toString()
Creates a String representation of the Collection. The string returned is of the form "[a, b, ...]" where a and b etc are the results of calling toString on the elements of the collection. This implementation obtains an Iterator over the Collection and adds each element to a StringBuffer as it is returned by the iterator. "" is inserted when the collection contains itself (only works for direct containment, not for collections inside collections).

Returns:
a String representation of the Collection