structure5
Class PriorityVector<E extends java.lang.Comparable<E>>

java.lang.Object
  structure5.PriorityVector<E>

All Implemented Interfaces:

PriorityQueue<E>

public class PriorityVector<E extends java.lang.Comparable<E>>
extends java.lang.Object
implements PriorityQueue<E>

A vector-based implementation of a priority queue. Similar to an ordered vector, except that only the smallest value may be accessed in this structure.

Example usage:

To print out a list of programmers sorted by age we could use the following:

 public static void main(String[] argv){
      //initialize a new fib heap
      PriorityVector programmers = new PriorityVector();

      //add programmers and their ages to heap
      //ages current of 7/22/2002
        programmers.add(new ComparableAssociation(new Integer(22), "Evan"));
      programmers.add(new ComparableAssociation(new Integer(19), "Chris"));
      programmers.add(new ComparableAssociation(new Integer(20), "Shimon"));
      programmers.add(new ComparableAssociation(new Integer(21), "Diane"));
      programmers.add(new ComparableAssociation(new Integer(21), "Lida"));    
      programmers.add(new ComparableAssociation(new Integer(20), "Rob"));     
      programmers.add(new ComparableAssociation(new Integer(20), "Sean"));    

      //print out programmers 
      while(!programmers.isEmpty()){
          ComparableAssociation p = (ComparableAssociation)programmers.remove();
          System.out.println(p.getValue() + " is " + p.getKey() + " years old.");
      }
 }
 

See Also:

structure.OrderedVector

Field Summary

protected Vector<E>

data The vector of data that is maintained in increasing order.

Constructor Summary

PriorityVector()
Construct an empty priority queue.

Method Summary

void	add(E value) Add a comparable value to the priority queue.
void	clear() Remove all the values from the priority queue.
E	getFirst() Fetch the smallest value of the priority queue.
protected int	indexOf(E target)
boolean	isEmpty() Determine if the priority queue is empty.
E	remove() Remove the smallest value of the structure.
int	size() Determine the size of the priority queue.
java.lang.String	toString() Construct a string representation of the priority vector.

Methods inherited from class java.lang.Object

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

Field Detail

data

protected Vector<E extends java.lang.Comparable<E>> data

The vector of data that is maintained in increasing order.

Constructor Detail

PriorityVector

public PriorityVector()

Construct an empty priority queue.

Postcondition:

constructs a new priority queue

Method Detail

getFirst

public E getFirst()

Fetch the smallest value of the priority queue.

Specified by:

getFirst in interface PriorityQueue<E extends java.lang.Comparable<E>>

Returns:

The smallest value of the structure.

Precondition:

!isEmpty()

Postcondition:

returns the minimum value in the priority queue

remove

public E remove()

Remove the smallest value of the structure.

Specified by:

remove in interface PriorityQueue<E extends java.lang.Comparable<E>>

Returns:

The smallest value of the structure.

Precondition:

!isEmpty()

Postcondition:

removes and returns minimum value in priority queue

add

public void add(E value)

Add a comparable value to the priority queue.

Specified by:

add in interface PriorityQueue<E extends java.lang.Comparable<E>>

Parameters:

value - The comparable value to be added.

Precondition:

value is non-null

Postcondition:

inserts value in priority queue leaves elements in order

indexOf

protected int indexOf(E target)

isEmpty

public boolean isEmpty()

Determine if the priority queue is empty.

Specified by:

isEmpty in interface PriorityQueue<E extends java.lang.Comparable<E>>

Returns:

True iff there are no elements in the priority queue.

Postcondition:

returns true iff the priority queue is empty

size

public int size()

Determine the size of the priority queue.

Specified by:

size in interface PriorityQueue<E extends java.lang.Comparable<E>>

Returns:

The number of elements in the priority queue.

Postcondition:

returns number of elements in priority queue

clear

public void clear()

Remove all the values from the priority queue.

Specified by:

clear in interface PriorityQueue<E extends java.lang.Comparable<E>>

Postcondition:

removes all elements from priority queue

toString

public java.lang.String toString()

Construct a string representation of the priority vector.

Overrides:

toString in class java.lang.Object

Returns:

String describing priority vector.

Postcondition:

returns string representation of priority vector