org.egothor.util

Class QueueAbstract<T>

java.lang.Object

org.egothor.util.QueueAbstract<T>

Direct Known Subclasses:

Queue

public abstract class QueueAbstract<T>
extends 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

Fields

Modifier and Type	Field and Description
int	factor

Method Summary

Modifier and Type	Method and Description
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.
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

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

factor

public final 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 (log_n ).

Returns:

the first element in the queue

up

public void up()

When the first element changes, this method resizes the queue structure in O (log_n ).

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.