Class order.Treap
All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class order.Treap

java.lang.Object
   |
   +----order.Treap

public class Treap
extends Object
implements Cloneable
An implentation of an ordered dictionary data structure, based on the randomized search trees (treaps) by Seidel and Aragon.
R. Seidel and C. R. Aragon. Randomized Binary Search Trees. Algorithmica, 16(4/5):464-497, 1996.
This class implements an ordered dictionary that maps keys to values. Any non-null object can be used as a value, but the keys must be non-null objects that implement the Ordered interface. The methods are similar to the ones in java.util.Hashtable. In addition, efficient methods for finding the minimum and maximum keys and their values are included. The enumeration returns the keys in sorted order.

Most methods run in O(log n) randomized time, where n is the number of keys in the treap; the exceptions are clone() and toString() that run in time proportional to the size of their output.

Version:
1.0, 22 April 1997
Author:
Stefan.Nilsson@hut.fi
See Also:
Ordered

Constructor Index

 o Treap()
Constructs a new empty treap.

Method Index

 o clear()
Clear the treap so that it contains no mappings.
 o clone()
Creates a shallow copy of this treap.
 o elements()
Returns an enumeration of the elemets in this treap.
 o elements(boolean)
Returns an enumeration of the elemets in this treap.
 o get(Ordered)
Gets the object associated with the specified key in the treap.
 o getMaxKey()
Returns the maximum key of the treap.
 o getMaxValue()
Returns the value to which the maximum key of the treap is mapped.
 o getMinKey()
Returns the minimum key of the treap.
 o getMinValue()
Returns the value to which the minimum key of the treap is mapped.
 o isEmpty()
Returns true if this treap contains no mappings.
 o keys()
Returns an ordered enumeration of the keys in this treap.
 o keys(boolean)
Returns an ordered enumeration of the keys in this treap.
 o printDebug()
Prints the treap on stderr, displaying the tree structure and the priority numbers.
 o put(Ordered, Object)
Maps the key to the specified value in this treap.
 o remove(Ordered)
Removes tke key (and its corresponding value) from this treap.
 o removeMax()
Removes tke maximum key (and its corresponding value) from this treap.
 o removeMin()
Removes tke minimum key (and its corresponding value) from this treap.
 o size()
Returns the number of keys in this treap.
 o toString()
Returns a string representation of this treap.

Constructors

 o Treap
  public Treap()
Constructs a new empty treap.

Methods

 o put
  public synchronized Object put(Ordered key,
                                 Object value)
Maps the key to the specified value in this treap. Neither the key, nor the value can be null.
Returns:
the previous value to which the key was mapped, or null if the key did not have a previous mapping in the treap.
 o get
  public synchronized Object get(Ordered key)
Gets the object associated with the specified key in the treap.
Returns:
the value to which the key is mapped in the treap, or null if the key is not mapped to any value in this treap.
 o getMinKey
  public synchronized Ordered getMinKey()
Returns the minimum key of the treap.
Throws: NoSuchElementException
if the treap is empty.
 o getMaxKey
  public synchronized Ordered getMaxKey()
Returns the maximum key of the treap.
Throws: NoSuchElementException
if the treap is empty.
 o getMinValue
  public synchronized Object getMinValue()
Returns the value to which the minimum key of the treap is mapped.
Throws: NoSuchElementException
if the treap is empty.
 o getMaxValue
  public synchronized Object getMaxValue()
Returns the value to which the maximum key of the treap is mapped.
Throws: NoSuchElementException
if the treap is empty.
 o keys
  public synchronized Enumeration keys()
Returns an ordered enumeration of the keys in this treap. The enumeration will list the keys in ascending order.
See Also:
Enumeration
 o keys
  public synchronized Enumeration keys(boolean ascending)
Returns an ordered enumeration of the keys in this treap. The enumeration will list the keys in ascending order if ascending is true, otherwise the keys will be listed in descending order.
See Also:
Enumeration
 o elements
  public synchronized Enumeration elements()
Returns an enumeration of the elemets in this treap. The enumeration will list the elements in ascending order (according to the corresponding keys).
See Also:
Enumeration
 o elements
  public synchronized Enumeration elements(boolean ascending)
Returns an enumeration of the elemets in this treap. The enumeration will list the elements in ascending order (according to the corresponding keys) if ascending is true, otherwise the elements will be listed in descending order.
See Also:
Enumeration
 o isEmpty
  public boolean isEmpty()
Returns true if this treap contains no mappings.
 o remove
  public synchronized Object remove(Ordered key)
Removes tke key (and its corresponding value) from this treap. This method does nothing if the key is not in the treap.
Returns:
the value to which the key had been mapped in this treap, or null if the key did not have a mapping.
 o removeMin
  public synchronized Object removeMin()
Removes tke minimum key (and its corresponding value) from this treap. This method does nothing if the treap is empty.
Returns:
the value to which the minimum key had been mapped in this treap, or null if the treap was empty.
 o removeMax
  public synchronized Object removeMax()
Removes tke maximum key (and its corresponding value) from this treap. This method does nothing if the treap is empty.
Returns:
the value to which the maximum key had been mapped in this treap, or null if the treap was empty.
 o clear
  public synchronized void clear()
Clear the treap so that it contains no mappings.
 o size
  public int size()
Returns the number of keys in this treap.
 o toString
  public synchronized String toString()
Returns a string representation of this treap. This routine is inefficient and primarily intended for debugging. To access the elements in the treap in sorted order use the keys() and elements()
Overrides:
toString in class Object
See Also:
keys, elements
 o clone
  public synchronized Object clone()
Creates a shallow copy of this treap. The keys and the values themselves are not cloned.
Returns:
a clone of this treap.
Overrides:
clone in class Object
 o printDebug
  public synchronized void printDebug()
Prints the treap on stderr, displaying the tree structure and the priority numbers.

All Packages  Class Hierarchy  This Package  Previous  Next  Index