All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class ninja.xset.Treap 

java.lang.Object
   |
   +----ninja.xset.Treap
public class Treap
extends Object
implements Serializable
Treap structure for insert, lookup, delete and set operations: union, intersection, difference

Constructor Index

o Treap(String)
This method was created by a SmartGuide.
o Treap(String, TreapMerge)
Method to construct a Treap with a name and a merge object

Method Index

o averageDepth()
float averageDepth() ** Method to return the average depth of the treap
o delete(String)
Object delete (String) ** Method to delete node with key k and return the value
o difference(Treap, Treap)
Treap difference(Treap, Treap) ** Method to create a new treap that is the set l - r (non destructive)
o elements()
Enumeration elements() ** The method implementing the elements functionality, similar to the corresponding method in hashtable and vectors.
o insert(String, Object)
insert (String, Object) ** Method to insert (k,v) into treap
o intersection(Treap, Treap)
Treap intersection (Treap, Treap) ** Method that takes the intersection of treaps t1 and t2
o keys()
Enumeration keys() ** The method implementing the keys functionality, similar to the corresponding method in hashtables.
o lookup(String)
Object lookup (String) ** Method that does non-destructive lookup on a key
o maxDepth()
int maxDepth() ** Method returns the maximum depth for the treap
o print()
print() ** Method that prints out the treap values
o rangeLookup(TreapOper)
Vector rangeLookup (TreapOper) ** Method to do a range query on the treap
o setMerge(TreapMerge)
setMerge (TreapMerge) ** Method to set the merge object field in the treap
o size()
int size() ** Method that returns the total number of nodes in the treap
o union(Treap, Treap)
Treap union (Treap, Treap) ** Return the non-destructive union of t1 and t2.

Constructors

o Treap 
 public Treap(String symbolicName)
This method was created by a SmartGuide. Standard constructor giving a name to the Treap

Parameters:
name - String that is the treap's symbolicName
Returns:
newly created Treap
o Treap 
 public Treap(String n,
              TreapMerge m)
Method to construct a Treap with a name and a merge object

Parameters:
n - String that is the treap's symbolicName
m - A TreapMerge object that is associated with the treap

Methods

o averageDepth 
 public float averageDepth()
float averageDepth() ** Method to return the average depth of the treap

Returns:
float the total depth / number of nodes
o elements 
 public Enumeration elements()
Enumeration elements() ** The method implementing the elements functionality, similar to the corresponding method in hashtable and vectors. It calls the recursive traverseElem method, which stores the elements in order.

Returns:
Enumeration of elements from the recursive traverse method
o keys 
 public Enumeration keys()
Enumeration keys() ** The method implementing the keys functionality, similar to the corresponding method in hashtables. It calls the recursive traverseKey method, which stores the keys in order.

Returns:
Enumeration of keys of the treap
o rangeLookup 
 public Vector rangeLookup(TreapOper to)
Vector rangeLookup (TreapOper) ** Method to do a range query on the treap

Parameters:
to - The treap operator encapsulating the query
Returns:
v vector that contains the hashtables
o delete 
 public synchronized Object delete(String k)
Object delete (String) ** Method to delete node with key k and return the value

Parameters:
k - The string key that we're looking for
Returns:
object that is associated with the key k
o difference 
 public static Treap difference(Treap l,
                                Treap r)
Treap difference(Treap, Treap) ** Method to create a new treap that is the set l - r (non destructive)

Parameters:
l - the greater treap to take difference from
r - the smaller treap to subtract away from l
Returns:
The difference represented as a treap
o insert 
 public synchronized void insert(String k,
                                 Object v) throws DuplicateException
insert (String, Object) ** Method to insert (k,v) into treap

Parameters:
k - The string that represents the key
v - The object associated with the key
Throws: DuplicateException
thrown when null values encountered
o intersection 
 public static Treap intersection(Treap t1,
                                  Treap t2)
Treap intersection (Treap, Treap) ** Method that takes the intersection of treaps t1 and t2

Parameters:
l - Treap.Treap
r - Treap.Treap
Returns:
Treap.Treap, the intersection result
o lookup 
 public Object lookup(String k)
Object lookup (String) ** Method that does non-destructive lookup on a key

Parameters:
k - The string that represents the key
Returns:
object that is associated with the key
o maxDepth 
 public int maxDepth()
int maxDepth() ** Method returns the maximum depth for the treap

Returns:
int The maximum depth
o print 
 public void print()
print() ** Method that prints out the treap values

o setMerge 
 public void setMerge(TreapMerge t)
setMerge (TreapMerge) ** Method to set the merge object field in the treap

Parameters:
t - Treap.TreapMerge
o size 
 public int size()
int size() ** Method that returns the total number of nodes in the treap

Returns:
int
o union 
 public static Treap union(Treap t1,
                           Treap t2)
Treap union (Treap, Treap) ** Return the non-destructive union of t1 and t2. It does not generally copy the nodes in the result set, although it does not modify t1 or t2 either. Delete operations on the result can affect t1 or t2.

Parameters:
t1 - treap.Treap
t2 - treap.Treap
Returns:
Treap that is the union 
All Packages  Class Hierarchy  This Package  Previous  Next  Index