org.limewire.collection
Class FixedsizePriorityQueue<E>

java.lang.Object
  org.limewire.collection.FixedsizePriorityQueue<E>

All Implemented Interfaces:

Iterable<E>

public class FixedsizePriorityQueue<E>
extends Object
implements Iterable<E>

Provides a priority queue with bounded size in an AVL tree. FixedsizePriorityQueue guarantees the lowest priority element is ejected when exceeding capacity.

FixedsizePriorityQueue provides extractMax() to extract the maximum element. FixedsizePriorityQueue requires an explicit Comparator; FixedsizePriorityQueue won't use the natural ordering of values.

Fetching the max element takes O(lg N) time, where N is the number of elements. Also, extracting and adding elements is O(lg N) time.

This class is not thread-safe.

    FixedsizePriorityQueue<String> fpq = 
        new FixedsizePriorityQueue<String>(Comparators.stringComparator(), 3);
    fpq.insert("Abby");
    fpq.insert("Bob");
    fpq.insert("Chris");
    System.out.println(fpq);
    System.out.println("Inserting another String pushes out an element (" + fpq.insert("Dan") + ") since the max. size was reached.");
    System.out.println(fpq);

    System.out.println("Minimum element: " + fpq.getMin());
    System.out.println("Maximum element: " + fpq.getMax());
    fpq.extractMax();
    System.out.println(fpq);

    Output:
        [Abby, Bob, Chris]
        Inserting another String pushes out an element (Abby) since the max. size was reached.
        [Bob, Chris, Dan]
        Minimum element: Bob
        Maximum element: Dan
        [Bob, Chris]

Constructor Summary

FixedsizePriorityQueue(Comparator<? super E> 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.
void	clear()
boolean	contains(E o) Returns true if this contains o.
E	extractMax()
E	getMax() Returns the highest priority element of this.
E	getMin() Returns the lowest priority element of this.
E	insert(E x) Adds x to this, possibly removing some lower priority entry if necessary to ensure this.size()<=this.capacity().
boolean	isFull()
Iterator<E>	iterator() Returns an iterator of the elements in this, from worst to best.
boolean	remove(E o) Removes the first occurrence of o.
int	size() Returns the number of elements in this.
String	toString()

Methods inherited from class java.lang.Object

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

Constructor Detail

FixedsizePriorityQueue

public FixedsizePriorityQueue(Comparator<? super E> comparator,
                              int capacity)
                       throws 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:

IllegalArgumentException - capacity negative

Method Detail

clear

public void clear()

isFull

public boolean isFull()

insert

public E insert(E 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

extractMax

public E extractMax()

getMax

public E getMax()
         throws NoSuchElementException

Returns the highest priority element of this.

Throws:

NoSuchElementException - this.size()==0

getMin

public E getMin()
         throws NoSuchElementException

Returns the lowest priority element of this.

Throws:

NoSuchElementException - this.size()==0

contains

public boolean contains(E o)

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

Parameters:

o - this contains a x s.t. o.equals(x). Note that priority is ignored in this operation.

remove

public boolean remove(E o)

Removes the first occurrence of o.

Returns:

true this contained an x such that o.equals(x).

iterator

public Iterator<E> iterator()

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

Specified by:

iterator in interface Iterable<E>

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

toString

public String toString()

Overrides:

toString in class Object