All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class jdsl.core.ref.BTHeap 

java.lang.Object
   |
   +----jdsl.core.ref.BTHeap
public class BTHeap
extends Object
implements PriorityQueue, ComparatorBased
A Heap implementation of PriorityQueue. This heap is based on a Binary Tree.

Version:
$Revision: 1.19 $, $Date: 1998/07/08 21:55:46 $
Author:
Mike Boilen (mgb)

Constructor Index

o BTHeap()
Class constructor.
o BTHeap(Comparator)
Class constructor.

Method Index

o comparator()
Retrieves the Comparator.
o downheap(Position)
Performs the downheap operation starting at p.
o elements()
Returns an Enumeration of all the elements within this Container.
o getBinaryTree()
Returns the underlying binary tree() in this heap.
o getTree()
Returns the underlying InspectableBinaryTree.
o insert(Locator)
Inserts a Locator into this Container.
o insert(Object, Object)
Inserts a <key, element> pair into this Container.
o insertItem(Object, Object)
Add a (key,element) pair to the set maintained by the priority queue, making whatever internal adjustments are necessary.
o isEmpty()
Tests if the container is empty.
o keys()
Returns an Enumeration of all the keys within this Container.
o locators()
Returns an Enumeration of all the Locators within this Container.
o makeLocator(Object, Object)
For when you need a locator that can be inserted into this KeyBasedContainer but don't want to insert it quite yet.
o min()
Allows access to element with first priority without removing it from the PriorityQueue.

o minElement()
Inspect the element (not the key) with first priority, without modifying the priority queue.
o minKey()
Inspect the key with first priority, without modifying the priority queue.
o newContainer()
o nextInsert()
Retrieves the Position that the Heap will insert at next.
o nextInsert(Position)
Changes the position that the Heap will insert at next
o remove(Locator)
Removes an element from this Container.
o removeMinElement()
Remove a (key,element) pair with first priority, making whatever internal adjustments are necessary.
o replaceElement(Locator, Object)
Takes constant time -- even in key-based containers, since the element can be changed independently of the key.
o replaceKey(Locator, Object)
Changes the mapping of a Locator's element to a new key.
o setComparator(Comparator)
This method establishes a ContainerInterfaces.Comparator that an ordered container should use to compare its elements.
o size()
Number of elements in the container.
o size(int)
Changes the current size.
o tree()
Retrieve the BinaryTree.
o upheap(Position)
Performs the upheap operation starting at p.

Constructors

o BTHeap 
 public BTHeap()
Class constructor. Constructs an empty Priority Queue with no comparator().

o BTHeap 
 public BTHeap(Comparator comparator)
Class constructor. Constructs an empty Priority Queue with the given comparator().

Methods

o tree 
 protected BinaryTree tree()
Retrieve the BinaryTree. Different from getBinaryTree because it is not part of the BinaryTreeBased interface and the return type is different.

Returns:
The underlying BinaryTree
See Also:
getBinaryTree
o comparator 
 public Comparator comparator()
Retrieves the Comparator.

Returns:
the Comparator that is used by this PriorityQueue.
o nextInsert 
 protected Position nextInsert()
Retrieves the Position that the Heap will insert at next.

Returns:
The current Position to insert at.
o nextInsert 
 protected void nextInsert(Position p)
Changes the position that the Heap will insert at next

Parameters:
p - The new next insertion Position
o size 
 protected void size(int size)
Changes the current size.

Parameters:
size - The new size.
o min 
 public Locator min() throws EmptyContainerException
Allows access to element with first priority without removing it from the PriorityQueue.

Returns:
Locator to the element with first priority
Throws: BoundaryViolationException
if the container is empty
o minElement 
 public Object minElement() throws EmptyContainerException
Inspect the element (not the key) with first priority, without modifying the priority queue.

Returns:
The client element associated with a key of first priority
Throws: EmptyContainerException
if the container is empty
o minKey 
 public Object minKey() throws EmptyContainerException
Inspect the key with first priority, without modifying the priority queue.

Returns:
A key of first priority among those in the priority queue
Throws: EmptyContainerException
if the container is empty
o insertItem 
 public void insertItem(Object key,
                        Object element) throws InvalidKeyException
Add a (key,element) pair to the set maintained by the priority queue, making whatever internal adjustments are necessary.

Parameters:
key - An object comparable under the implementation's comparison scheme
element - An arbitrary object the client associates with the key
Throws: InvalidKeyException
if the key is not comparable by this container's comparator().
o removeMinElement 
 public Object removeMinElement() throws EmptyContainerException
Remove a (key,element) pair with first priority, making whatever internal adjustments are necessary.

Returns:
The client element (not the key) removed
Throws: EmptyContainerException
if the container is empty
o getTree 
 public InspectableBinaryTree getTree()
Returns the underlying InspectableBinaryTree.

Returns:
the underlying InspectableBinaryTree.
o setComparator 
 public Comparator setComparator(Comparator c)
This method establishes a ContainerInterfaces.Comparator that an ordered container should use to compare its elements. It must be called after a container is instantiated. It should not be called thereafter, because containers are not guaranteed to update themselves if a new comparator() is installed.

Parameters:
c - A ContainerInterfaces.Comparator appropriate to the elements stored by the container
Returns:
The old Comparator
o getBinaryTree 
 public InspectableBinaryTree getBinaryTree()
Returns the underlying binary tree() in this heap.

Returns:
the binary tree().
o upheap 
 protected void upheap(Position p)
Performs the upheap operation starting at p.

Parameters:
p - The Position to start upheaping at.
o downheap 
 protected void downheap(Position p)
Performs the downheap operation starting at p.

Parameters:
p - The Position to start downheaping at.
o insert 
 public void insert(Locator locator) throws InvalidKeyException, InvalidLocatorException, ContainedLocatorException
Inserts a Locator into this Container.

Parameters:
locator - The Locator that is inserted into this Container.
Throws: InvalidkeyException
If the key referenced by locator is not a type accepted by this Container. (For instance, if the container's Comparator can't compare the element, or if the container should have a comparator() but doesn't.)
Throws: InvalidLocatorException
If locator cannot be inserted into this container.
o insert 
 public Locator insert(Object key,
                       Object element) throws InvalidKeyException
Inserts a <key, element> pair into this Container. Here, key is an explicit key. That is, it is mapped to element and used to position element within this Container.

Parameters:
key - The key used to position the element within this Container.
element - The element to be inserted into this Container.
Returns:
A Locator which points to element within this Container.
Throws: InvalidKeyException
If key is not a type accepted by this Container (For example: This Container is unable to use key as a key).
o remove 
 public void remove(Locator locator) throws InvalidLocatorException, UncontainedLocatorException
Removes an element from this Container. This method provides the only guaranteed way of removing a particular element from a KeyBasedContainer. The Container may make no guarantee about the uniqueness of its keys or stored elements. Many elements may be mapped to the same key and vice versa depending upon the particular implementaion.

Parameters:
locator - The Locator which points to a particular element within this Container.
Throws: InvalidLocatorException
If locator is invalid (For example: It does not actually reference an element in this Container).
Throws: UncontainedLocatorException
if locator is not contained.
o replaceKey 
 public Object replaceKey(Locator locator,
                          Object key) throws InvalidLocatorException, InvalidKeyException, UncontainedLocatorException
Changes the mapping of a Locator's element to a new key. That is, within this Container locator's element will now be mapped to key. The original key this element was mapped to is returned Note: this method does not necessarily remove the old key (other elements within this Container may be mapped to it).

Parameters:
locator - The Locator which points to a particular element within this Container.
key - The new key to which locator's element should be mapped.
Returns:
The old key to which locator's element was mapped.
Throws: InvalidLocatorException
If locator is invalid (For example: It does not actually reference an element in this Container).
Throws: InvalidKeyException
If key is not a type accepted by this Container (e.g. If this Container is unable to use key as a key).
Throws: UncontainedLocatorException
if locator isn't contained.
o replaceElement 
 public Object replaceElement(Locator loc,
                              Object newElement) throws InvalidLocatorException, UncontainedLocatorException
Takes constant time -- even in key-based containers, since the element can be changed independently of the key.

Parameters:
loc - Locator at which replacement should occur
newElement - Element now to be stored at Locator loc
Returns:
Old element, previously stored at Locator loc
Throws: UncontainedLocatorException
if loc is uncontained.
o locators 
 public Enumeration locators()
Returns an Enumeration of all the Locators within this Container. If this Container is empty then an empty Enumeration is returned.

Returns:
An Enumeration of all the Locators stored in the container. Note: this Enumeration may be empty.
See Also:
elements, Enumeration
o keys 
 public Enumeration keys()
Returns an Enumeration of all the keys within this Container. If this Container is empty then an empty Enumeration is returned.

Returns:
An Enumeration of all the keys stored in the container. Note: this Enumeration may be empty.
See Also:
elements, Enumeration
o makeLocator 
 public Locator makeLocator(Object key,
                            Object element) throws InvalidKeyException
For when you need a locator that can be inserted into this KeyBasedContainer but don't want to insert it quite yet.

Parameters:
key - the key that represents the element in this locator.
element - the element for this locator.
o elements 
 public Enumeration elements()
Returns an Enumeration of all the elements within this Container. If this Container is empty then an empty Enumeration is returned.

Returns:
An Enumeration of all the Locators stored in the container. Note: this Enumeration may be empty.
See Also:
locators, Enumeration
o newContainer 
 public Container newContainer()
o size 
 public int size()
Number of elements in the container. May be of order N, in containers that support split and splice operations.

Returns:
Number of elements in the container, where each occurrence of a duplicated element adds 1 to the size() of the container.
o isEmpty 
 public boolean isEmpty()
Tests if the container is empty. Guaranteed to be a constant-time operation.

Returns:
Whether there are no elements in the container 
All Packages  Class Hierarchy  This Package  Previous  Next  Index