All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class com.trumphurst.utils.PatriciaTree 

java.lang.Object
   |
   +----java.util.Dictionary
           |
           +----com.trumphurst.utils.PatriciaTree
public class PatriciaTree
extends Dictionary
A Dictionary which stores String/Object pairs in a radix trie structure, enabling them to be retrieved in sorted order. For details of the Patricia algorithm, see "Algorithms" by Robert Sedgewick (Addison-Wesley). Comparisons are made at the bit level, and only enough bits to uniquely identify an individual key need to be compared to find it. This makes it a very efficient way of storing items with large keys.

Note that the other Dictionaries in Java can use arbitrary Objects as keys, because they do not sort in order, and thus only need hashCode and isequal to compare keys, both of which exist for all objects. This class needs to access arbitrary bits in the key to do its comparisons. As most keys in real-life are Strings, PatriciaTree merely calls toString on its key to convert it to a String (a no-effect operation if the key is already a String), and uses the String as its real key. Unfortunately, this precludes using (say) Integers directly as keys (they would be sorted in alphabetical order, so that 100 is less than 2). It would be necessary to create a new class whose toString method returned a String which would sort in the correct order.

The alternative would be to create an interface containing the necessary comparison functions, and force the key to implement the interface. However this precludes using any existing class as the key, forcing even the most common case (Strings as keys) to do extra work.

Constructor Index

o PatriciaTree()

Method Index

o elements()
Returns an enumeration of the elements.
o get(Object)
Gets the object associated with the specified key in the PatriciaTree.
o isEmpty()
Returns true if the PatriciaTree contains no elements.
o keys()
Returns an enumeration of the PatriciaTree's keys.
o print()
Function to print the tree to System.out.
o put(Object, Object)
Puts the specified element into the PatriciaTree, using the specified key.
o remove(Object)
This function is supposed to remove items from the tree, but it is not implemented yet, and does nothing but return null.
o size()
Returns the number of elements contained within the PatriciaTree.

Constructors

o PatriciaTree 
 public PatriciaTree()

Methods

o print 
 public void print()
Function to print the tree to System.out. Not used in a production environment, but helps to understand what is going on during debugging of PatriciaTree itself.

o elements 
 public Enumeration elements()
Returns an enumeration of the elements. Use the Enumeration methods on the returned object to fetch the elements sequentially in key order.

Overrides:
elements in class Dictionary
See Also:
keys, Enumeration
o get 
 public Object get(Object key)
Gets the object associated with the specified key in the PatriciaTree.

Parameters:
key - the key in the hash table. Note that key.toString() is the used as the actual key (as Strings can be ranked in order).
Returns:
s the element for the key, or null if the key is not defined in the hash table.
Overrides:
get in class Dictionary
See Also:
put, toString, toString
o isEmpty 
 public final boolean isEmpty()
Returns true if the PatriciaTree contains no elements.

Overrides:
isEmpty in class Dictionary
o keys 
 public Enumeration keys()
Returns an enumeration of the PatriciaTree's keys. Use the Enumeration methods on the returned object to fetch the keys sequentially in order.

Overrides:
keys in class Dictionary
See Also:
elements, Enumeration
o put 
 public Object put(Object key,
                   Object value)
Puts the specified element into the PatriciaTree, using the specified key. The element may be retrieved by doing a get() with the same key. The key and the element cannot be null.

Parameters:
key - the specified key. Note that key.toString() is the used as the actual key (as Strings can be ranked in order).
value - the specified element
Returns:
the old value of the key, or null if it did not have one.
Throws: NullPointerException
If the value of the specified key or element is null.
Overrides:
put in class Dictionary
See Also:
get, toString, toString
o remove 
 public Object remove(Object key)
This function is supposed to remove items from the tree, but it is not implemented yet, and does nothing but return null.

Overrides:
remove in class Dictionary
o size 
 public final int size()
Returns the number of elements contained within the PatriciaTree.

Overrides:
size in class Dictionary 
All Packages  Class Hierarchy  This Package  Previous  Next  Index