org.egothor.util
Class QueueAbstract<T>

java.lang.Object
  extended by org.egothor.util.QueueAbstract<T>
Direct Known Subclasses:
Queue

public abstract class QueueAbstract<T>
extends java.lang.Object

This class represents a priority queue (heap). The Queue object is used to aid in the merger of indices constructed for any number of document collections. This class is abstract, and it does not care about the heap storage method.

Author:
Leo Galambos

Field Summary
 int factor
           
 
Constructor Summary
protected QueueAbstract(int factor)
           
 
Method Summary
abstract  void append(T item)
          Appends a new object to the heap's array (at the end).
abstract  int capacity()
          Return the maximum capacity of this Queue.
abstract  void cutOffLast()
          Cuts off the last element of the heap's array, and reduces the array size by one.
 void down()
          Resize the queue beginning at the last Object.
protected  void down(int now)
          Resize the Queue after an Object is pushed into it.
 void expand()
          If push is called and we have not any space for a new element, this method is executed to enlarge the capacity of this queue.
abstract  T item(int index)
          Returns the object that is stored in index-th cell of the heap's array.
abstract  void itemto(int index, T obj)
          Saves the object to the given index-th cell of the heap's array.
abstract  boolean lessThan(T a, T b)
          Test whether a is less than b..
 int lowestSonOf(int father)
          Find an item with the lowest value amongst sons of a father.
 T peek()
          Return the first element in the queue.
 T pop()
          Removes and returns the first element in the queue.
 void push(T o)
          Insert a new object in the queue.
 T replace(T what, T by)
          Replace what (this object must be directly in this queue) with by.
abstract  int size()
          Returns the number of elements in the queue.
 void up()
          When the first element changes, this method resizes the queue structure in O (logn ).
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

factor

public final int factor
Constructor Detail

QueueAbstract

protected QueueAbstract(int factor)
Method Detail

lowestSonOf

public int lowestSonOf(int father)
Find an item with the lowest value amongst sons of a father.

Returns:
the index of the lowest value

size

public abstract int size()
Returns the number of elements in the queue.

Returns:
the number of elements in the queue

item

public abstract T item(int index)
Returns the object that is stored in index-th cell of the heap's array.

Parameters:
index - Description of the Parameter
Returns:
Description of the Return Value

itemto

public abstract void itemto(int index,
                            T obj)
Saves the object to the given index-th cell of the heap's array.

Parameters:
index - Description of the Parameter
obj - Description of the Parameter

replace

public final T replace(T what,
                       T by)
Replace what (this object must be directly in this queue) with by. The replacement operation is achieved in time O (size+log size ).

Parameters:
what - what will be replaced
by - this will replace what
Returns:
the object that is the maximum of the queue, as defined by the Queue.lessThan method.

capacity

public abstract int capacity()
Return the maximum capacity of this Queue.

Returns:
the capacity

append

public abstract void append(T item)
Appends a new object to the heap's array (at the end).

Parameters:
item - Description of the Parameter

expand

public void expand()
If push is called and we have not any space for a new element, this method is executed to enlarge the capacity of this queue. By default, it does nothing which means that push will not place the item onto the queue.


push

public void push(T o)
Insert a new object in the queue. This occurs in time O (log size ). If the Queue is full as defined in the constructor the method will return without executing.

Parameters:
o - the Object to insert

peek

public final T peek()
Return the first element in the queue. This occurs in time O (1).

Returns:
the first element in the queue

cutOffLast

public abstract void cutOffLast()
Cuts off the last element of the heap's array, and reduces the array size by one.


pop

public final T pop()
Removes and returns the first element in the queue. The removal is achieved in time O (logn ).

Returns:
the first element in the queue

up

public void up()
When the first element changes, this method resizes the queue structure in O (logn ).


lessThan

public abstract boolean lessThan(T a,
                                 T b)
Test whether a is less than b..

Parameters:
a - the first Object to compare
b - the Object to compare param a to
Returns:
true if a<b, false otherwise

down

public final void down()
Resize the queue beginning at the last Object.


down

protected final void down(int now)
Resize the Queue after an Object is pushed into it.

Parameters:
now - the last position in the Queue's array