/*
* @(#)RapidQueue.java 1.0 2009/11/08
*
* Copyright (c) 2009 Ashish Nawal Saharia (Ashish.Saharia@yahoo.co.in)
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
* THE SOFTWARE.
*/
package com.infant.common;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.RandomAccess;
/**
* Resizable array based implementation of the List and
* Queue interfaces, specifically designed to perform faster than
* ArrayList, Vector, LinkedList, and ConcurrentLinkedQueue, when used as a
* simple queue. Must be synchronized externally, when used in
* multi-threaded applications. Stores elements in the order of insertion.
* Adding elements to any position other than the end (tail) of the queue, is
* allowed, but not recommended. Removing elements from any position other
* than the beginning (head) or end (tail) of the queue, is allowed, but not
* recommended. Duplicates are allowed. Null elements are not allowed.
* Uses more memory than ArrayList, Vector, LinkedList, and
* ConcurrentLinkedQueue.
*
* In most cases, it should be possible to use this class as a drop-in
* replacement for Queues and ArrayLists. One notable difference is in the
* implementation of the subList function - unlike an ArrayList, this
* function returns a new RapidQueue object - not a reference to
* a sub-section of the underlying array. Also, the initial size and
* load factor cannot be specified by the user.
*
* This class is best suited for applications that only need to perform add
* operations at the tail of the queue, remove operations from the head or
* tail of the queue, and calls to check whether or not a specified object
* exists in the queue. In such applications, depending on the
* equals() and hashCode() implementations of the objects
* that are stored in this queue, this class can potentially offer a
* tremendous performance benefit.
*
* Using the iterators of this class is not recommended. Since this class
* supports index-based element access, there shouldn't be a need to access
* its elements using iterators.
*
*
* @author Ashish (Ashish.Saharia@yahoo.co.in)
* @version 1.0 - November 08, 2009, Mumbai (Bombay), India.
*
*/
public class RapidQueue implements List, Queue, RandomAccess, java.io.Serializable
{
private static final long serialVersionUID = 200810095738801648L;
private final int INITIAL_CAPACITY = 2048;
private final int INITIAL_HTABLE_SIZE = 16384;
private final float LOAD_FACTOR = 0.64F;
private transient Object[] ba; // Base Array
private transient Object[] htable = new Object[INITIAL_HTABLE_SIZE]; // Hash Table
private int so = 0; // Start Offset
private int size = 0;
private int selfhash = 0;
private boolean updateselfhash = true;
private boolean useHash = true;
private transient int modCount = 0;
/**
* Default constructor, creates an instance of this class that uses a
* hashcode-based index to speed up searches performed using a call to the
* contains method. New elements can usually be added at the
* end (tail) of the queue in amortized constant time. Elements can
* usually be removed from the beginning (head) of the queue in amortized
* constant time. Calls to the contains function can be executed
* significantly faster, as compared to non-indexed collections,
* like ArrayList, Vector, LinkedList, and ConcurrentLinkedQueue, when
* this instance is used to store objects with good, or even
* moderately good, hashCode() implementations. Index-based
* inserts and removals, however, can be expensive.
*/
public RapidQueue()
{
ba = new Object[INITIAL_CAPACITY];
}
/**
* Calling this constructor with useHash set to false, creates an instance
* of this class that does not make use of its hashcode-based indexing
* capabilities. Arbitrary inserts and removals will be marginally faster,
* but a call to the contains will be significantly slower, as
* compared to an instance of this class that does use hashcode-based
* indexing. Not recommended, unless there is a requirement for a fast,
* basic queue that is not likely to be checked for the presence of
* objects. Setting useHash to true will make this instance behave as
* though it was created using the default constructor.
*/
public RapidQueue(boolean useHash)
{
ba = new Object[INITIAL_CAPACITY];
this.useHash = useHash;
}
/**
* Creates a new instance of RapidQueue, that contains all the elements
* present in the specified collection. Uses a hashcode-based index to
* speed up searches performed using a call to the contains
* method. Throws an IllegalArgumentException if the specified collection
* contains a null element.
*/
public RapidQueue(Collection c)
{
Object[] oa = c.toArray();
if (arrayContainsNull(oa, 0, oa.length))
{
throw new IllegalArgumentException("Collection contains null element !");
}
ba = new Object[c.size() + INITIAL_CAPACITY];
System.arraycopy(oa, 0, ba, 0, oa.length);
rebuildIndex();
size = oa.length;
}
/**
* Calling this constructor with useHash set to false, creates an instance
* of this class that does not make use of its hashcode-based indexing
* capabilities. If useHash is set to true, a hashcode-based index will be
* used to speed up searches performed using a call to the
* contains method. The new instance will contain all the
* elements present in the specified collection. Throws an
* IllegalArgumentException if the specified collection contains a null
* element.
*/
public RapidQueue(Collection c, boolean useHash)
{
Object[] oa = c.toArray();
if (arrayContainsNull(oa, 0, oa.length))
{
throw new IllegalArgumentException("Collection contains null element !");
}
ba = new Object[c.size() + INITIAL_CAPACITY];
System.arraycopy(oa, 0, ba, 0, oa.length);
rebuildIndex();
size = oa.length;
this.useHash = useHash;
}
/**
* Creates a new instance of RapidQueue, that contains all the elements
* present in the specified array. Uses a hashcode-based index to
* speed up searches performed using a call to the contains
* method. Throws an IllegalArgumentException if the specified array
* contains a null element.
*/
public RapidQueue(E[] oa)
{
if (arrayContainsNull(oa, 0, oa.length))
{
throw new IllegalArgumentException("Array contains null element !");
}
ba = new Object[oa.length + INITIAL_CAPACITY];
System.arraycopy(oa, 0, ba, 0, oa.length);
rebuildIndex();
size = oa.length;
}
/**
* Calling this constructor with useHash set to false, creates an instance
* of this class that does not make use of its hashcode-based indexing
* capabilities. If useHash is set to true, a hashcode-based index will be
* used to speed up searches performed using a call to the
* contains method. The new instance will contain all the
* elements present in the specified array. Throws an
* IllegalArgumentException if the specified array contains a null
* element.
*/
public RapidQueue(E[] oa, boolean useHash)
{
if (arrayContainsNull(oa, 0, oa.length))
{
throw new IllegalArgumentException("Array contains null element !");
}
ba = new Object[oa.length + INITIAL_CAPACITY];
System.arraycopy(oa, 0, ba, 0, oa.length);
rebuildIndex();
size = oa.length;
this.useHash = useHash;
}
/**
* Returns the number of elements in this collection. Runs in constant
* time.
*/
public int size()
{
return size;
}
private int getHashIndex(int hash)
{
return (hash & 0x7FFFFFFF) % htable.length;
}
/**
* Builds or rebuilds the entire hash table (index).
*/
private void rebuildIndex()
{
if (size < (htable.length * LOAD_FACTOR))
{
htable = new Object[htable.length];
}
else
{
htable = new Object[htable.length * 2];
}
if (size > 0)
{
int m = so + size;
for (int i = so; i < m; ++i)
{
Object obj = ba[i];
int hash = obj.hashCode();
int htindex = getHashIndex(hash);
HashNode newNode = new HashNode();
newNode.elemIndex = i;
if (htable[htindex] == null)
{
HashList hashList = new HashList();
hashList.addNode(newNode);
htable[htindex] = hashList;
}
else
{
HashList hashList = (HashList) htable[htindex];
hashList.addNode(newNode);
}
}
}
}
private void addEntryToHashTable(int hashCode, int index)
{
int htindex = getHashIndex(hashCode);
HashNode newNode = new HashNode();
newNode.elemIndex = index;
if (htable[htindex] == null)
{
HashList hashList = new HashList();
hashList.addNode(newNode);
htable[htindex] = hashList;
}
else
{
HashList hashList = (HashList) htable[htindex];
hashList.addNode(newNode);
}
}
private void deleteEntryFromHashTable(int hashCode, int index)
{
int htindex = getHashIndex(hashCode);
HashList hashList = (HashList) htable[htindex];
HashNode node = new HashNode();
node.elemIndex = index;
hashList.deleteNode(node);
if (hashList.size() == 0)
{
htable[htindex] = null;
}
}
/**
* Resizes the base array, if necessary. Returns a boolean value
* indicating whether or not the entire index has to be rebuilt, as a
* result of resizing the base array.
*/
private boolean ensureCapacity(int additionalCapacity)
{
boolean rebuildFullIndex = false;
if (additionalCapacity > 0)
{
int mincap = (so + size + additionalCapacity); // Minimum Capacity Required
if (mincap >= (ba.length * LOAD_FACTOR))
{
int newSize = ba.length * 2;
if (newSize <= mincap)
{
newSize = mincap + INITIAL_CAPACITY;
}
Object[] bacopy = new Object[newSize];
if (size < (htable.length * LOAD_FACTOR) && so < (ba.length / 2))
{
System.arraycopy(ba, so, bacopy, so, size);
ba = bacopy;
}
else
{
System.arraycopy(ba, so, bacopy, 0, size);
ba = bacopy;
so = 0;
rebuildFullIndex = true;
}
}
}
return rebuildFullIndex;
}
/**
* Adds the specified object at the last position in this collection.
*/
public boolean add(E obj)
{
if (obj == null)
{
return false;
}
boolean rbfi = ensureCapacity(1);
ba[so + size] = obj;
size++;
if (useHash)
{
if (!rbfi)
{
addEntryToHashTable(obj.hashCode(), (so + (size - 1)));
}
else
{
rebuildIndex();
}
}
modCount++;
updateselfhash = true;
return true;
}
/**
* Adds the specified object at the specified position in this list.
*/
public void add(int index, E obj) throws IndexOutOfBoundsException
{
if (index == this.size() || obj == null)
{
this.add(obj);
}
if (index < 0 || index > size)
{
throw new IndexOutOfBoundsException("Index " + index);
}
ensureCapacity(1);
System.arraycopy(ba, (so + index), ba, ((so + index) + 1), (size - index));
ba[so + index] = obj;
size++;
if (useHash)
{
rebuildIndex();
}
modCount++;
}
/**
* Adds all the elements in the specified collection at the end of this
* list.
*
* @throws NullPointerException if the specified collection is null.
* @throws IllegalArgumentException if the specified collection contains a
* null element.
*/
public boolean addAll(Collection c) throws NullPointerException
{
if (c == null)
{
throw new NullPointerException();
}
Object[] oa;
oa = c.toArray();
if (arrayContainsNull(oa, 0, oa.length))
{
throw new IllegalArgumentException("Collection contains null element !");
}
if (oa.length == 0)
{
return false;
}
boolean rbfi = ensureCapacity(oa.length);
System.arraycopy(oa, 0, ba, (so + size), oa.length);
size += oa.length;
if (useHash)
{
if (!rbfi)
{
for (int i = (so + (size - oa.length)); i < (so + size); ++i)
{
addEntryToHashTable(ba[i].hashCode(), i);
}
}
else
{
rebuildIndex();
}
}
modCount++;
return true;
}
/**
* Adds all the elements in the specified collection at the specified
* position in this list.
*/
public boolean addAll(int index, Collection c) throws NullPointerException, IndexOutOfBoundsException
{
if (c == null)
{
throw new NullPointerException();
}
if (index < 0 || index > this.size())
{
throw new IndexOutOfBoundsException("Index " + index);
}
Object[] oa;
oa = c.toArray();
if (arrayContainsNull(oa, 0, oa.length))
{
throw new IllegalArgumentException("Collection contains null element !");
}
if (oa.length == 0)
{
return false;
}
ensureCapacity(oa.length);
System.arraycopy(ba, (so + index), ba, (so + index + oa.length), (size - index));
System.arraycopy(oa, 0, ba, (so + index), oa.length);
size += oa.length;
if (useHash)
{
rebuildIndex();
}
modCount++;
return true;
}
/**
* Returns, but does not remove, the object at the specified position.
*/
@SuppressWarnings("unchecked")
public E get(int index)
{
if (index < 0 || index >= size)
{
throw new IndexOutOfBoundsException("Index " + index);
}
return (E) ba[(so + index)];
}
/**
* Replaces the element at the specified index with the specified element,
* and returns the old element.
*/
@SuppressWarnings("unchecked")
public E set(int index, E element)
{
if (index < 0 || index >= size)
{
throw new IndexOutOfBoundsException("Index " + index);
}
Object obj = ba[(so + index)];
ba[(so + index)] = element;
if (useHash)
{
deleteEntryFromHashTable(obj.hashCode(), (so + index));
addEntryToHashTable(element.hashCode(), (so + index));
}
modCount++;
return (E) obj;
}
/**
* Returns, but does not remove, the element at the head of this queue.
* Returns null if the queue is empty.
*/
public E peek()
{
return ((this.size() == 0) ? null : this.get(0));
}
/**
* Returns, but does not remove, the element at the head of this queue.
* Similar to the peek function, but throws NoSuchElementException if the
* queue is empty, instead of returning null.
*/
public E element() throws NoSuchElementException
{
if (this.size() == 0)
{
throw new NoSuchElementException("Queue Empty !");
}
return this.get(0);
}
/**
* Removes and returns the element at the head of this queue. Returns
* null if the queue is empty.
*/
public E poll()
{
return pullOutNextElement();
}
/**
* Removes and returns the element at the head of this queue. Similar to
* the poll function, but throws NoSuchElementException if the
* queue is empty, instead of returning null.
*/
public E remove() throws NoSuchElementException
{
if (this.size() == 0)
{
throw new NoSuchElementException("Queue Empty !");
}
return this.poll();
}
/**
* Removes and returns the element at the specified index.
*/
@SuppressWarnings("unchecked")
public E remove(int index) throws IndexOutOfBoundsException
{
if (index >= size || index < 0)
{
throw new IndexOutOfBoundsException();
}
if (index == 0)
{
return pullOutNextElement();
}
Object obj = ba[(so + index)];
if (useHash)
{
if (index == (size - 1))
{
ba[so + (--size)] = null;
deleteEntryFromHashTable(obj.hashCode(), (so + index));
}
else
{
System.arraycopy(ba, ((so + index) + 1), ba, (so + index), (size - (index + 1)));
ba[so + (--size)] = null;
rebuildIndex();
}
}
else
{
if (index != (size - 1))
{
System.arraycopy(ba, ((so + index) + 1), ba, (so + index), (size - (index + 1)));
}
ba[so + (--size)] = null;
}
modCount++;
return (E) obj;
}
/**
* Removes the first instance of the specified object found in the
* underlying array.
*/
public boolean remove(Object obj)
{
int index = this.indexOf(obj);
if (index == -1)
{
return false;
}
this.remove(index);
return true;
}
/**
* Removes all instances of the specified object from the underlying array.
*/
public int removeAll(Object obj)
{
int[] objIndexes = this.allIndexesOf(obj);
for (int i = 0; i < objIndexes.length; ++i)
{
this.remove(objIndexes[i]);
}
return objIndexes.length;
}
/**
* Removes all instances of all elements in the specified collection from
* the underlying array.
*/
public boolean removeAll(Collection c)
{
if (c == null || c.size() == 0)
{
return false;
}
Object[] oa = c.toArray();
for (int i = 0; i < oa.length; ++i)
{
this.removeAll(oa[i]);
}
return true;
}
/**
* Removes the specified range - between fromIndex (inclusive) and
* toIndex (exclusive) - from the underlying array.
*/
public void removeRange(int fromIndex, int toIndex)
{
if (fromIndex < 0 || toIndex < fromIndex || toIndex >= this.size())
{
throw new IndexOutOfBoundsException("From " + fromIndex + " ** To " + toIndex);
}
Object[] bacopy = new Object[ba.length];
System.arraycopy(ba, so, bacopy, 0, fromIndex);
if ((toIndex + 1) < this.size())
{
System.arraycopy(ba, (so + toIndex), bacopy, fromIndex, (this.size() - toIndex));
}
ba = bacopy;
size -= (toIndex - fromIndex);
so = 0;
if (useHash)
{
rebuildIndex();
}
modCount++;
}
/**
* Same as the set function.
*/
public E replace(int index, E element)
{
return this.set(index, element);
}
/**
* Replaces the specified range - between fromIndex (inclusive) and
* toIndex (exclusive) - from the underlying array, with the elements of
* the specified array. The underlying array will be resized,
* if necessary, to accommodate all the elements from the specified array.
*/
public void replaceRange(int fromIndex, int toIndex, Object[] oa)
{
if (fromIndex < 0 || toIndex < fromIndex || toIndex >= this.size())
{
throw new IndexOutOfBoundsException("From " + fromIndex + " ** To " + toIndex);
}
if (oa.length > 0)
{
if (arrayContainsNull(oa, 0, oa.length))
{
throw new IllegalArgumentException("Array contains null element !");
}
ensureCapacity(oa.length - (toIndex - fromIndex));
System.arraycopy(ba, (so + toIndex), ba, (so + fromIndex + oa.length), (size - toIndex));
System.arraycopy(oa, 0, ba, so + fromIndex, oa.length);
size += (oa.length - (toIndex - fromIndex));
if (useHash)
{
rebuildIndex();
}
}
modCount++;
}
/**
* Retains in the underlying list, all instances of all elements present
* in the specified collection, and discards the rest.
*/
public boolean retainAll(Collection c)
{
if (c == null)
{
return false;
}
if (c.size() == 0)
{
this.clear();
}
Object[] oa = c.toArray();
int[] toRetain = new int[this.size()];
int indexCount = 0;
for (int i = 0; i < oa.length; ++i)
{
int[] indexes = allIndexesOf(oa[i]);
if (indexes.length > 0)
{
for (int j = 0; j < indexes.length; ++j)
{
if (!this.arrayContainsValue(toRetain, 0, indexCount, indexes[j]))
{
toRetain[indexCount] = indexes[j];
indexCount++;
}
}
}
}
Object[] bacopy = new Object[indexCount + INITIAL_CAPACITY];
for (int i = 0; i < indexCount; ++i)
{
bacopy[i] = ba[toRetain[i]];
}
ba = bacopy;
size = indexCount;
so = 0;
if (useHash)
{
rebuildIndex();
}
modCount++;
return true;
}
/**
* Returns true only if all elements from the specified
* collection are found in the underlying list.
*/
public boolean containsAll(Collection c)
{
boolean b = true;
if (c == null || c.size() == 0)
{
return false;
}
Object[] oa = c.toArray();
for (int i = 0; i < oa.length; ++i)
{
if (!this.contains(oa[i]))
{
b = false;
break;
}
}
return b;
}
private boolean arrayContainsValue(int[] ia, int from, int length, int value)
{
boolean found = false;
if (from < 0 || (from + length) >= ia.length)
{
throw new ArrayIndexOutOfBoundsException();
}
for (int i = from; i < length; ++i)
{
if (ia[i] == value)
{
found = true;
break;
}
}
return found;
}
private boolean arrayContainsNull(Object[] oa, int from, int length)
{
boolean found = false;
if (from < 0 || (from + length) > oa.length)
{
throw new ArrayIndexOutOfBoundsException();
}
for (int i = from; i < length; ++i)
{
if (oa[i] == null)
{
found = true;
break;
}
}
return found;
}
/**
* Similar to the add function, but throws a
* NullPointerException if the specified object is
* null.
*/
public boolean offer(E obj)
{
if (obj == null)
{
throw new NullPointerException();
}
return this.add(obj);
}
/**
* Same as the add function.
*/
protected boolean push(E obj)
{
return this.add(obj);
}
/**
* Removes and returns the element at the tail of this queue. Returns
* null if the stack is empty.
*/
protected E pop()
{
return ((this.size() == 0) ? null : this.get(size - 1));
}
/**
* Empties the underlying collection.
*/
public void clear()
{
ba = new Object[INITIAL_CAPACITY];
size = 0;
so = 0;
htable = new Object[INITIAL_HTABLE_SIZE];
useHash = true;
modCount++;
System.gc(); System.gc();
}
/**
* Returns true only if the underlying collection is empty.
*/
public boolean isEmpty()
{
return (this.size() == 0);
}
/**
* Returns the index of the first instance of the specified object, from
* the underlying collection; returns -1 if the object is not found.
*/
public int indexOf(Object obj)
{
return this.indexOf(0, obj);
}
/**
* Returns the index of the first instance of the specified object, from
* the underlying collection, starting at fromIndex; returns -1 if the
* object is not found.
*/
public int indexOf(int fromIndex, Object obj)
{
int foundAt = -1;
if (useHash)
{
int htindex = getHashIndex(obj.hashCode());
if (htable[htindex] != null)
{
HashList hashList = (HashList) htable[htindex];
HashNode node = hashList.firstNode;
for (int i = 0; i < hashList.size(); ++i)
{
if (ba[node.elemIndex].equals(obj))
{
if (node.elemIndex >= (so + fromIndex))
{
foundAt = node.elemIndex;
break;
}
}
node = node.nextNode;
}
}
}
else
{
Object bael = null;
for (int i = (so + fromIndex); i < ba.length; ++i)
{
bael = ba[i];
if (bael == null)
{
break;
}
if (bael.hashCode() == obj.hashCode())
{
if (bael.equals(obj))
{
foundAt = i;
break;
}
}
}
}
return foundAt;
}
private int[] allIndexesOf(Object obj)
{
int[] indexes = new int[size];
int objCount = 0;
if (useHash)
{
int htindex = getHashIndex(obj.hashCode());
if (htable[htindex] != null)
{
HashList hashList = (HashList) htable[htindex];
HashNode node = hashList.firstNode;
for (int i = 0; i < hashList.size(); ++i)
{
if (ba[node.elemIndex].equals(obj))
{
indexes[objCount] = node.elemIndex;
objCount++;
}
node = node.nextNode;
}
}
}
else
{
int objIndex = 0;
while ((objIndex = this.indexOf(objIndex, obj)) != -1)
{
indexes[objCount] = objIndex;
objCount++;
}
}
return this.copyArray(indexes, 0, objCount);
}
/**
* Returns the index of the last instance of the specified object, from
* the underlying collection; returns -1 if the object is not found.
*/
public int lastIndexOf(Object obj)
{
int foundAt = -1;
if (useHash)
{
int htindex = getHashIndex(obj.hashCode());
if (htable[htindex] != null)
{
HashList hashList = (HashList) htable[htindex];
HashNode node = hashList.lastNode;
for (int i = (hashList.size() - 1); i >= 0; --i)
{
if (ba[node.elemIndex].equals(obj))
{
foundAt = node.elemIndex;
break;
}
node = node.previousNode;
}
}
}
else
{
Object bael = null;
for (int i = (ba.length - 1); i >= 0; --i)
{
bael = ba[i];
if (bael == null)
{
break;
}
if (bael.hashCode() == obj.hashCode())
{
if (bael.equals(obj))
{
foundAt = i;
break;
}
}
}
}
return foundAt;
}
/**
* Returns a new RapidQueue object populated with values from a
* sub-section of the underlying array.
*/
@SuppressWarnings("unchecked")
public List subList(int fromIndex, int toIndex)
{
List sublist;
int slsize = toIndex - fromIndex;
E[] oa = (E[]) new Object[slsize];
System.arraycopy(ba, (so + fromIndex), oa, 0, slsize);
sublist = new RapidQueue(oa);
return sublist;
}
/**
* Returns the underlying collection as an array of Objects.
*/
public Object[] toArray()
{
return this.copyArray(ba, so, this.size());
}
/**
* Attempts to return the underlying collection as an array of Objects of
* type T.
*/
@SuppressWarnings("unchecked")
public T[] toArray(T[] a)
{
return (T[]) this.copyArray(ba, so, this.size());
}
/**
* Removes and returns the element at the head of this queue. Returns
* null if the queue is empty.
*/
@SuppressWarnings("unchecked")
private E pullOutNextElement()
{
if (this.size() > 0)
{
E obj = (E) ba[so];
if (useHash)
{
deleteEntryFromHashTable(obj.hashCode(), so);
}
ba[so] = null;
so++;
modCount++;
size--;
return obj;
}
return null;
}
/**
* Returns true only if at least one instance of the specified
* object is found in this collection.
*/
public boolean contains(Object obj)
{
Object bael = null;
boolean found = false;
if (useHash)
{
int hash = obj.hashCode();
int htindex = getHashIndex(hash);
if (htable[htindex] != null)
{
HashList hashList = (HashList) htable[htindex];
HashNode node = hashList.firstNode;
for (int i = 0; i < hashList.size(); ++i)
{
bael = ba[node.elemIndex];
if (bael.hashCode() == hash && bael.equals(obj))
{
found = true;
break;
}
node = node.nextNode;
}
}
}
else
{
for (int i = so; i < (so + size); ++i)
{
bael = ba[i];
if (bael == null)
{
continue;
}
if (bael.hashCode() == obj.hashCode())
{
if (bael.equals(obj))
{
found = true;
break;
}
}
}
}
return found;
}
/**
* Returns true only if the specified object is an instance of this class,
* has the same number of elements as this instance, and contains the same
* elements, in the same order, as this instance.
*/
public boolean equals(Object obj)
{
RapidQueue rq = null;
boolean isEqual = false;
if (obj == this)
{
return true;
}
if (!(obj instanceof RapidQueue))
{
return false;
}
rq = (RapidQueue) obj;
if (rq.size() != this.size() || rq.hashCode() != this.hashCode())
{
return false;
}
isEqual = true;
for (int i = 0; i < rq.size(); ++i)
{
if ((rq.get(i).hashCode() != this.get(i).hashCode()) || (!rq.get(i).equals(this.get(i))))
{
isEqual = false;
break;
}
}
return isEqual;
}
/**
* Returns the Hash Code computed for the current instance of this class.
*/
public int hashCode()
{
if (updateselfhash)
{
selfhash = 0;
for (int i = so; i < this.size(); ++i)
{
selfhash = selfhash ^ ba[i].hashCode();
}
selfhash = selfhash ^ this.size();
updateselfhash = false;
}
return selfhash;
}
private int[] copyArray(int[] src, int start, int length)
{
int[] oa = new int[length];
System.arraycopy(src, start, oa, 0, length);
return oa;
}
private Object[] copyArray(Object[] src, int start, int length)
{
Object[] oa = new Object[length];
System.arraycopy(src, start, oa, 0, length);
return oa;
}
// Code For Iterators
/**
* Returns a ListIterator object that can be used to iterate over the
* underlying collection. Note that using iterators of this class is not
* recommended. Since this class supports index-based element access,
* there shouldn't be a need to access its elements using iterators.
*/
public ListIterator listIterator()
{
return listIterator(0);
}
/**
* Returns a ListIterator object that can be used to iterate over the
* underlying collection, starting at the specified index. Note that using
* iterators of this class is not recommended. Since this class supports
* index-based element access, there shouldn't be a need to access its
* elements using iterators.
*/
public ListIterator listIterator(int index)
{
return new RQueueListIterator(index);
}
/**
* Returns an Iterator object that can be used to iterate over the
* underlying collection. Note that using iterators of this class is not
* recommended. Since this class supports index-based element access,
* there shouldn't be a need to access its elements using iterators.
*/
public Iterator iterator()
{
return new RQueueIterator();
}
/**
* Implementation of the Iterator interface. Note that using iterators of
* this class is not recommended. Since this class supports index-based
* element access, there shouldn't be a need to access its elements using
* iterators.
*/
private class RQueueIterator implements Iterator
{
protected int startIndex = 0;
protected int iterCount = 0;
protected boolean allowRemove = false;
protected transient int lastRet = -1;
protected transient boolean iterModified = false;
protected int expectedModCount = 0;
/**
* Default constructor.
*/
public RQueueIterator()
{
expectedModCount = modCount;
}
protected void checkForConcurrentModification()
{
if (expectedModCount != modCount)
{
throw new ConcurrentModificationException();
}
}
/**
* Removes from the underlying collection, the element that was last
* returned by a call to next() or previous(). Note
* that using iterators of this class is not recommended. Since this
* class supports index-based element access, there shouldn't be a
* need to access its elements using iterators.
*/
public void remove()
{
if (allowRemove)
{
if (iterModified)
{
throw new IllegalStateException();
}
if (lastRet >= RapidQueue.this.size() || lastRet < 0)
{
throw new IndexOutOfBoundsException();
}
checkForConcurrentModification();
RapidQueue.this.remove(lastRet);
iterCount--;
expectedModCount++;
iterModified = true;
allowRemove = false;
}
}
/**
* Returns the next element in this collection. Note that using
* iterators of this class is not recommended. Since this class
* supports index-based element access, there shouldn't be a need to
* access its elements using iterators.
*/
public E next() throws NoSuchElementException
{
if (iterCount >= RapidQueue.this.size())
{
throw new NoSuchElementException();
}
checkForConcurrentModification();
E obj = RapidQueue.this.get(iterCount);
lastRet = iterCount;
iterCount++;
allowRemove = true;
iterModified = false;
return obj;
}
/**
* Returns true only if the next call to next() would not
* throw a NoSuchElementException. Note that using
* iterators of this class is not recommended. Since this class
* supports index-based element access, there shouldn't be a need to
* access its elements using iterators.
*/
public boolean hasNext()
{
boolean nextFound = (iterCount < RapidQueue.this.size());
return nextFound;
}
}
/**
* Implementation of the ListIterator interface. Note that using iterators
* of this class is not recommended. Since this class supports index-based
* element access, there shouldn't be a need to access its elements using
* iterators.
*/
private class RQueueListIterator extends RQueueIterator implements ListIterator
{
/**
* Default constructor.
*/
public RQueueListIterator()
{
}
/**
* Creates a new ListIterator (RQueueListIterator) object that can be
* used to iterate over the underlying collection, starting at the
* specified index.
*/
public RQueueListIterator(int i)
{
if (i < 0 || i >= RapidQueue.this.size())
{
throw new IndexOutOfBoundsException();
}
startIndex = i;
}
/**
* Adds the specified object to the underlying collection, immediately
* after the element that was last returned by a call to
* next() or previous(). If no call has been made to
* next or previous, the element will be added at the beginning of the
* list (index 0). Note that using iterators of this class is not
* recommended. Since this class supports index-based element access,
* there shouldn't be a need to access its elements using iterators.
*/
public void add(E obj)
{
if (obj != null)
{
checkForConcurrentModification();
RapidQueue.this.add((lastRet + 1), obj);
expectedModCount++;
}
}
/**
* Replaces the element that was last returned by a call to
* next() or previous(), with the specified element.
* Note that using iterators of this class is not recommended. Since
* this class supports index-based element access, there shouldn't be
* a need to access its elements using iterators.
*/
public void set(E element)
{
if (iterModified || lastRet == -1)
{
throw new IllegalStateException();
}
checkForConcurrentModification();
RapidQueue.this.set(lastRet, element);
expectedModCount++;
}
/**
* Returns the index of the element that would be returned by the next
* call to previous. Returns -1 if this iterator is at the
* beginning of the underlying list. Note that using iterators of this
* class is not recommended. Since this class supports index-based
* element access, there shouldn't be a need to access its elements
* using iterators.
*/
public int previousIndex()
{
return (iterCount - 1);
}
/**
* Returns the index of the element that would be returned by the next
* call to next(). Returns the size of the underlying list if
* this iterator is at the end of the list. Note that using iterators
* of this class is not recommended. Since this class supports
* index-based element access, there shouldn't be a need to access its
* elements using iterators.
*/
public int nextIndex()
{
return iterCount;
}
/**
* Returns the previous element in this collection. Note that using
* iterators of this class is not recommended. Since this class
* supports index-based element access, there shouldn't be a need to
* access its elements using iterators.
*/
public E previous() throws NoSuchElementException
{
if (iterCount <= startIndex)
{
throw new NoSuchElementException();
}
E obj = RapidQueue.this.get((iterCount - 1));
lastRet = iterCount;
iterCount--;
allowRemove = true;
iterModified = false;
return obj;
}
/**
* Returns true only if the next call to previous()
* would not throw a NoSuchElementException. Note that using
* iterators of this class is not recommended. Since this class
* supports index-based element access, there shouldn't be a
* need to access its elements using iterators.
*/
public boolean hasPrevious()
{
if (iterCount > startIndex)
{
return true;
}
return false;
}
}
// End Of Code For Iterators
/**
* Circular Doubly Linked-List to store indexes of hash collisions and
* equal objects. Stores elements in the order of insertion.
*/
private class HashList
{
private HashNode firstNode = null;
private HashNode lastNode = null;
private int nodeCount = 0;
/**
* Default constructor.
*/
public HashList()
{
}
/**
* Adds the specified node to this linked-list.
*/
public void addNode(HashNode node)
{
if (firstNode == null)
{
firstNode = node;
}
else
{
lastNode.nextNode = node;
}
node.previousNode = lastNode;
lastNode = node;
lastNode.nextNode = firstNode;
firstNode.previousNode = lastNode;
nodeCount++;
}
/**
* Returns the node just before the specified node in this
* linked-list. Returns null if the specified node is not found in the
* list.
*/
public HashNode previous(HashNode node)
{
HashNode p = null;
if (nodeCount <= 1)
{
return p;
}
HashNode h = firstNode;
if (node.elemIndex == h.elemIndex)
{
p = h.previousNode;
}
else
{
for (int i = 0; i < nodeCount; ++i)
{
h = h.nextNode;
if (node.elemIndex == h.elemIndex)
{
p = h.previousNode;
break;
}
}
}
return p;
}
/**
* Returns the node immediately after the specified node in this
* linked-list. Returns null if the specified node is not found in the
* list.
*/
public HashNode next(HashNode node)
{
HashNode n = null;
if (nodeCount <= 1)
{
return n;
}
HashNode h = firstNode;
if (node.elemIndex == h.elemIndex)
{
n = h.nextNode;
}
else
{
for (int i = 0; i < nodeCount; ++i)
{
h = h.nextNode;
if (node.elemIndex == h.elemIndex)
{
n = h.nextNode;
break;
}
}
}
return n;
}
/**
* Deletes the specified node from this linked-list. Has no effect if
* the specified node is not found in the list.
*/
public void deleteNode(HashNode node)
{
if (nodeCount == 1)
{
if (node.elemIndex == firstNode.elemIndex)
{
firstNode = null;
lastNode = null;
nodeCount = 0;
}
}
else if (nodeCount >= 2)
{
HashNode p = this.previous(node);
HashNode n = this.next(node);
if (p != null && n != null)
{
p.nextNode = n;
n.previousNode = p;
if (nodeCount == 2)
{
firstNode = p;
lastNode = n;
}
else
{
if (node.elemIndex == firstNode.elemIndex)
{
firstNode = firstNode.nextNode;
}
else if (node.elemIndex == lastNode.elemIndex)
{
lastNode = lastNode.previousNode;
}
}
nodeCount--;
}
}
}
/**
* Returns the number of elements (nodes) in this linked-list.
*/
public int size()
{
return nodeCount;
}
}
/**
* Linked-List node.
*/
private class HashNode
{
private int elemIndex;
private HashNode nextNode = null;
private HashNode previousNode = null;
/**
* Default constructor.
*/
public HashNode()
{
}
}
// Code For Serialization
private void writeObject(java.io.ObjectOutputStream oos) throws java.io.IOException
{
int expectedModCount = modCount;
if (so > 0)
{
Object[] bacopy = new Object[size + INITIAL_CAPACITY];
System.arraycopy(ba, so, bacopy, 0, size);
ba = bacopy;
if (useHash)
{
rebuildIndex();
}
so = 0;
}
oos.defaultWriteObject();
for (int i = 0; i < size; ++i)
{
oos.writeObject(ba[i]);
}
if (useHash) // Serialize the index too.
{
oos.writeInt(htable.length);
for (int i = 0; i < htable.length; ++i)
{
oos.writeObject(htable[i]);
}
}
if (expectedModCount != modCount)
{
throw new ConcurrentModificationException();
}
}
private void readObject(java.io.ObjectInputStream ois) throws java.io.IOException, ClassNotFoundException
{
ois.defaultReadObject();
ba = new Object[size + INITIAL_CAPACITY];
for (int i = 0; i < size; ++i)
{
ba[i] = ois.readObject();
}
if (useHash)
{
int htsize = ois.readInt();
htable = new Object[htsize];
for (int i = 0; i < htable.length; ++i)
{
htable[i] = ois.readObject();
}
}
}
// End Of Code For Serialization
}