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 randomized time, where
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
-
Treap()
- Constructs a new empty treap.
-
clear()
- Clear the treap so that it contains no mappings.
-
clone()
- Creates a shallow copy of this treap.
-
elements()
- Returns an enumeration of the elemets in this treap.
-
elements(boolean)
- Returns an enumeration of the elemets in this treap.
-
get(Ordered)
- Gets the object associated with the specified key in the treap.
-
getMaxKey()
- Returns the maximum key of the treap.
-
getMaxValue()
- Returns the value to which the maximum key of the treap is mapped.
-
getMinKey()
- Returns the minimum key of the treap.
-
getMinValue()
- Returns the value to which the minimum key of the treap is mapped.
-
isEmpty()
- Returns
true
if this treap contains no mappings.
-
keys()
- Returns an ordered enumeration of the keys in this treap.
-
keys(boolean)
- Returns an ordered enumeration of the keys in this treap.
-
printDebug()
- Prints the treap on stderr, displaying the tree structure
and the priority numbers.
-
put(Ordered, Object)
- Maps the key to the specified value in this treap.
-
remove(Ordered)
- Removes tke key (and its corresponding value) from this treap.
-
removeMax()
- Removes tke maximum key (and its corresponding value) from
this treap.
-
removeMin()
- Removes tke minimum key (and its corresponding value) from
this treap.
-
size()
- Returns the number of keys in this treap.
-
toString()
- Returns a string representation of this treap.
Treap
public Treap()
- Constructs a new empty treap.
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.
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.
getMinKey
public synchronized Ordered getMinKey()
- Returns the minimum key of the treap.
- Throws: NoSuchElementException
- if the treap is empty.
getMaxKey
public synchronized Ordered getMaxKey()
- Returns the maximum key of the treap.
- Throws: NoSuchElementException
- if the treap is empty.
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.
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.
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
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
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
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
isEmpty
public boolean isEmpty()
- Returns
true
if this treap contains no mappings.
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.
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.
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.
clear
public synchronized void clear()
- Clear the treap so that it contains no mappings.
size
public int size()
- Returns the number of keys in this treap.
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
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
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