com.limegroup.gnutella.util
Class FixedsizePriorityQueue

java.lang.Object
  extended bycom.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()