com.limegroup.gnutella.util
Class FixedsizePriorityQueue

java.lang.Object
  com.limegroup.gnutella.util.FixedsizePriorityQueue

public class FixedsizePriorityQueue

extends java.lang.Object

A priority queue with bounded size. Similar to BinaryHeap, but implemented with a balanced tree instead of a binary heap. This results in some subtle differences:

1. FixedsizePriorityQueue guarantees that the lowest priority element is ejected when exceeding capacity. BinaryHeap provides no such guarantees.
2. Fetching the max element takes O(lg N) time, where N is the number of elements. Compare with O(1) for BinaryHeap. Extracting and adding elements is still O(lg N) time.
3. FixedsizePriorityQueue can provide operations for extracting the minimum and the maximum element. Note, however, that this is still considered a "max heap", for reasons in (1).
4. FixedsizePriorityQueue REQUIRES an explicit Comparator; it won't use the natural ordering of values.

This class is not synchronized; that is up to the user.

See Also:

BinaryHeap

Constructor Summary

FixedsizePriorityQueue(java.util.Comparator comparator, int capacity)
Creates a new FixedsizePriorityQueue that will hold at most capacity elements.

Method Summary

int	capacity() Returns the maximum number of elements this can hold.
boolean	contains(java.lang.Object o) Returns true if this contains o.
java.lang.Object	getMax() Returns the highest priority element of this.
java.lang.Object	getMin() Returns the lowest priority element of this.
java.lang.Object	insert(java.lang.Object x) Adds x to this, possibly removing some lower priority entry if necessary to ensure this.size()<=this.capacity().
java.util.Iterator	iterator() Returns an iterator of the elements in this, from worst to best.
boolean	remove(java.lang.Object o) Removes the first occurence of o.
protected void	repOk()
int	size() Returns the number of elements in this.
java.lang.String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

FixedsizePriorityQueue

public FixedsizePriorityQueue(java.util.Comparator comparator,
                              int capacity)
                       throws java.lang.IllegalArgumentException

Creates a new FixedsizePriorityQueue that will hold at most capacity elements.

Parameters:

comparator - expresses priority. Note that comaparator.compareTo(a,b)==0 does not imply that a.equals(b).

capacity - the maximum number of elements

Throws:

java.lang.IllegalArgumentException - capacity negative

Method Detail

insert

public java.lang.Object insert(java.lang.Object x)

Adds x to this, possibly removing some lower priority entry if necessary to ensure this.size()<=this.capacity(). If this has capacity, x will be added even if already in this (possibly with a different priority).

Parameters:

x - the entry to add

Returns:

the element ejected, possibly x, or null if none

getMax

public java.lang.Object getMax()
                        throws java.util.NoSuchElementException

Returns the highest priority element of this.

Throws:

java.util.NoSuchElementException - this.size()==0

getMin

public java.lang.Object getMin()
                        throws java.util.NoSuchElementException

Returns the lowest priority element of this.

Throws:

java.util.NoSuchElementException - this.size()==0

contains

public boolean contains(java.lang.Object o)

Returns true if this contains o. Runs in O(N) time, where N is number of elements in this.

remove

public boolean remove(java.lang.Object o)

Removes the first occurence of o. Runs in O(N) time, where N is number of elements in this.

iterator

public java.util.Iterator iterator()

Returns an iterator of the elements in this, from worst to best.

size

public int size()

Returns the number of elements in this.

capacity

public int capacity()

Returns the maximum number of elements this can hold.

Returns:

the value passed to this constructor

repOk

protected void repOk()

toString

public java.lang.String toString()