org.limewire.collection
Class BucketQueue<E>

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

All Implemented Interfaces:

Cloneable, Iterable<E>

public class BucketQueue<E>
extends Object
implements Cloneable, Iterable<E>

Provides a discrete-case priority queue. BucketQueue is designed to be a replacement for a binary heap for the special case when there are only a small number of positive priorities. (Priorities are zero based and therefore, when priority is set to 3, the values are [0, 1, 2]. Also, larger numbers are higher priority.)

You determine how many element cases per priority are allowed in the queue. When the queue attempts to add an element more than the maximum capacity for the priority, the first element is removed upon insert(Object, int).

This class is not thread-safe.

                                        //priorities, capacity
    BucketQueue<String> bq = new BucketQueue<String>(3,2);

    bq.insert("Abby", 1);
    bq.insert("Bob", 1);
    System.out.println(bq);

    String returnFromInsert ;
    returnFromInsert = bq.insert("Chris", 1);
    if(returnFromInsert != null)
        System.out.println("Element " + returnFromInsert + " popped because there are already 2 elements of priority 1.");

    System.out.println(bq);
    bq.insert("Dan", 2);
    bq.insert("Eric", 2);
    bq.insert("Fred", 0);

    System.out.println("Max: " + bq.getMax().toString() + " and bq is " + bq);      

    Output:    
        [[], [Bob, Abby], []]
        Element Abby popped because there are already 2 elements of priority 1.
        [[], [Chris, Bob], []]
        Max: Eric and bq is [[Eric, Dan], [Chris, Bob], [Fred]]

 

Constructor Summary

BucketQueue(BucketQueue<? extends E> other)
"Copy constructor": constructs a a new shallow copy of other.

BucketQueue(int[] capacities)

BucketQueue(int priorities, int capacityPerPriority)

Method Summary

void	clear() Removes all elements from the queue.
BucketQueue<E>	clone() Returns a shallow copy of this, of type BucketQueue
E	extractMax()
E	getMax()
E	insert(E o, int priority)
boolean	isEmpty()
Iterator<E>	iterator()
Iterator<E>	iterator(int startPriority, int n)
boolean	removeAll(Object o)
int	size()
int	size(int priority)
String	toString()

Methods inherited from class java.lang.Object

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

Constructor Detail

BucketQueue

public BucketQueue(int priorities,
                   int capacityPerPriority)
            throws IllegalArgumentException

Throws:

IllegalArgumentException - priorities or capacityPerPriority is non-positive.

BucketQueue

public BucketQueue(int[] capacities)
            throws IllegalArgumentException

Throws:

IllegalArgumentException - capacities.length<=0 or capacities[i]<=0 for any i

BucketQueue

public BucketQueue(BucketQueue<? extends E> other)

"Copy constructor": constructs a a new shallow copy of other.

Method Detail

clear

public void clear()

Removes all elements from the queue.

insert

public E insert(E o,
                int priority)

Throws:

IllegalArgumentException - priority is not a legal priority, as determined by this' constructor

removeAll

public boolean removeAll(Object o)

extractMax

public E extractMax()
             throws NoSuchElementException

Throws:

NoSuchElementException

getMax

public E getMax()
         throws NoSuchElementException

Throws:

NoSuchElementException

size

public int size()

size

public int size(int priority)
         throws IllegalArgumentException

Throws:

IllegalArgumentException - priority is not a legal priority, as determined by this' constructor

isEmpty

public boolean isEmpty()

iterator

public Iterator<E> iterator()

Specified by:

iterator in interface Iterable<E>

iterator

public Iterator<E> iterator(int startPriority,
                            int n)
                     throws IllegalArgumentException

Throws:

IllegalArgumentException - startPriority is not a legal priority as determined by this' constructor

clone

public BucketQueue<E> clone()
                     throws CloneNotSupportedException

Returns a shallow copy of this, of type BucketQueue

Overrides:

clone in class Object

Throws:

CloneNotSupportedException

toString

public String toString()

Overrides:

toString in class Object