org.egothor.util
Class BiQueue<T>

java.lang.Object
  org.egothor.util.BiQueue<T>

Direct Known Subclasses:

ResultList

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

The Queue class should be extended by any class wishing to implement a priority queue (heap). The Queue object is used to aid in the merger of indices constructed for any number of document collections.

Author:

Leo Galambos

Constructor Summary

BiQueue(int max)
Constructor for the Queue object.

BiQueue(int init_size, int delta)
Constructor for the Queue object

Method Summary

void	append(T obj) Add the given object to the end of the queue.
int	capacity() Return the capacity of this Queue as defined in the constructor.
void	clear() Description of the Method
void	cutOffLast() Shrink the Queue by 1 (the last) position.
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.
T	item(int index) Return the object at the given position in the Queue.
void	itemto(int index, T obj) Insert the given object in the Queue at the specified position.
abstract boolean	lessThan(T a, T b) Test whether a is less than b..
int	linearize() Transform this structure to a linear structure.
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.
int	size() Return 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

Constructor Detail

BiQueue

public BiQueue(int max)

Constructor for the Queue object.

Parameters:

max - the maximum size desired for the Queue

BiQueue

public BiQueue(int init_size,
               int delta)

Constructor for the Queue object

Parameters:

init_size - Description of the Parameter

delta - Description of the Parameter

Method Detail

clear

public final void clear()

Description of the Method

expand

public final 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.

size

public final int size()

Return the number of elements in the queue.

Returns:

the number of elements in the queue

item

public final T item(int index)

Return the object at the given position in the Queue.

Parameters:

index - the position of the desired object

Returns:

the object at the given position in the Queue

capacity

public final int capacity()

Return the capacity of this Queue as defined in the constructor.

Returns:

the capacity

itemto

public final void itemto(int index,
                         T obj)

Insert the given object in the Queue at the specified position.

Parameters:

index - the position at which to insert

obj - the object to insert

cutOffLast

public final void cutOffLast()

Shrink the Queue by 1 (the last) position.

append

public final void append(T obj)

Add the given object to the end of the queue.

Parameters:

obj - the object to append

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.

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

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.

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

linearize

public int linearize()

Transform this structure to a linear structure.