util
Class StringTreeTable

java.lang.Object
  |
  +--util.StringTreeTable
All Implemented Interfaces:
Serializable

public class StringTreeTable
extends Object
implements Serializable

A data structure which allows prefix and wildcard lookup. The table is indexed by strings, and a divider substring ("." by default) is used to create a tree structure. Performing a lookup then gives the matching entry and/or any parents in the tree. The empty string "" is always the root key. For example, a StringTreeTable with `apple', `apple.pie' and `apple.juice' as keys has the following internal structure:

 [empty string] ---> apple +--> apple.juice
                           |
                           +--> apple.pie
 
Performing a lookup on "apple.pie" will yield the objects for "apple.pie", "apple", and the empty string "". A get("anteater") will yield a match for just the empty string key.

You can also add a wildcard character ("*" by default) to store "*.pie" in the table and get anything that matches the wildcard. Note that this works on the path components, not on part of the path component. (i.e., you'll match "apple.pie" if you store "*.pie" in the table, but not if you stored "*le.pie")

StringTreeTable allows there to be more than one value for a given key; it will return all such values with the get() method.

See Also:
Serializable, Serialized Form

Field Summary
static String DEFAULT_WHITE
           
static String DEFAULT_WILDCARD
           
 
Constructor Summary
StringTreeTable()
          Creates a StringTreeTable using the default divider string (".") and default wildcard ("*").
StringTreeTable(String divider, String wildcard)
          Creates a StringTreeTable with the given parameters as the divider and wildcard.
 
Method Summary
 void add(String nm, Object o)
          Adds a new key,object pair into the tree.
 Set get(String nm)
          Gets the set of matching objects in the tree structure.
 Set getChildren(String nm)
           
static void main(String[] args)
           
 Iterator nodes()
          Returns all the keys in the tree.
 int nuke(Object o)
          Removes an object from all keys in the tree.
 boolean remove(String nm, Object o)
          Removes a given key,value pair.
 String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

DEFAULT_WHITE

public static final String DEFAULT_WHITE

DEFAULT_WILDCARD

public static final String DEFAULT_WILDCARD
Constructor Detail

StringTreeTable

public StringTreeTable()
Creates a StringTreeTable using the default divider string (".") and default wildcard ("*").

StringTreeTable

public StringTreeTable(String divider,
                       String wildcard)
Creates a StringTreeTable with the given parameters as the divider and wildcard.
Parameters:
divider - The divider string.
wildcard - The wildcard string.
Method Detail

get

public Set get(String nm)
Gets the set of matching objects in the tree structure. This will give you all the values for the tree's keys, leading from the root to the given key. This will never return null; if there are no matches, this will return a Set with no objects in it.

This works through a depth-first search, looking for either the current string token or the wildcard character.

Parameters:
nm - The value to search for.
Returns:
a Set including all matches.

add

public void add(String nm,
                Object o)
Adds a new key,object pair into the tree. If the key already exists, the object is added to the table anyway and both it and the pre-existing objects will be returned when requested.
Parameters:
nm - The key value to be inserted into the table.
o - The object value for the given key.

remove

public boolean remove(String nm,
                      Object o)
Removes a given key,value pair. The pair is only removed if the key is in the tree table and the object is a match for that key.
Parameters:
nm - The key to be removed, if present.
o - The object to be removed, if present.
Returns:
true if the object and key were in the table.

nuke

public int nuke(Object o)
Removes an object from all keys in the tree.
Parameters:
o - The object to be removed, if present.
Returns:
The number of keys for which the object was present.

nodes

public Iterator nodes()
Returns all the keys in the tree. The sequence in which keys are returned is not defined.
Returns:
An iterator over the tree's keys in some sequence.

getChildren

public Set getChildren(String nm)
Returns:
list of all folks which are in nodes in the given node or its children.

toString

public String toString()
Overrides:
toString in class Object

main

public static void main(String[] args)