structure
Class PriorityVector

java.lang.Object
  |
  +--structure.PriorityVector

All Implemented Interfaces:

PriorityQueue

public class PriorityVector

extends Object

implements PriorityQueue

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:

OrderedVector

Field Summary

protected Vector

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

Constructor Summary

PriorityVector()
Construct an empty priority queue.

Method Summary

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

Methods inherited from class java.lang.Object

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

Field Detail

data

protected Vector data

The vector of data that is maintained in increasing order.

Constructor Detail

PriorityVector

public PriorityVector()

Construct an empty priority queue.

Method Detail

getFirst

public Comparable getFirst()

Fetch the smallest value of the priority queue.

Specified by:

getFirst in interface PriorityQueue

Precondition:

!isEmpty()

Postcondition:

returns the minimum value in the priority queue

Returns:

The smallest value of the structure.

remove

public Comparable remove()

Remove the smallest value of the structure.

Specified by:

remove in interface PriorityQueue

Precondition:

!isEmpty()

Postcondition:

removes and returns minimum value in priority queue

Returns:

The smallest value of the structure.

add

public void add(Comparable value)

Add a comparable value to the priority queue.

Specified by:

add in interface PriorityQueue

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(Comparable target)

isEmpty

public boolean isEmpty()

Determine if the priority queue is empty.

Specified by:

isEmpty in interface PriorityQueue

Postcondition:

returns true iff the priority queue is empty

Returns:

True iff there are no elements in the priority queue.

size

public int size()

Determine the size of the priority queue.

Specified by:

size in interface PriorityQueue

Postcondition:

returns number of elements in priority queue

Returns:

The number of elements in the priority queue.

clear

public void clear()

Remove all the values from the priority queue.

Specified by:

clear in interface PriorityQueue

Postcondition:

removes all elements from priority queue

toString

public String toString()

Construct a string representation of the priority vector.

Overrides:

toString in class Object

Postcondition:

returns string representation of priority vector

Returns:

String describing priority vector.