SSF.OS.BGP4.Util
Class RadixTree

java.lang.Object
  |
  +--SSF.OS.BGP4.Util.RadixTree

Direct Known Subclasses:

RIBElement

public class RadixTree

extends java.lang.Object

This class is used as an efficient way to store information which is keyed by a binary string (IP addresses, for example).

Constructor Summary

RadixTree()
Constructs an empty radix tree.

Method Summary

java.lang.Object	add(BitString bs, java.lang.Object obj) Attempts to add data to the tree, keyed by the given binary string, but fails if data associated with that string already exists.
java.lang.Object	find(BitString bs) Returns the data associated with the given binary string, if any.
java.util.ArrayList	get_ancestors(BitString bs) Examines each node in the tree which is associated with a proper prefix of the given binary string, and finds all of the ones which have (non-null) data associated with them.
java.util.ArrayList	get_descendants(BitString bs) Examines each node in the tree whose binary string key has the given binary string as a proper prefix, and finds all of the ones which have (non-null) data associated with them.
boolean	has_descendants(BitString bs) Determines whether or not any descendants of a given node have (non-null) data.
java.lang.Object	oldest_ancestor(BitString bs) Examines each node in the tree which is associated with a proper prefix of the given binary string, and finds the shortest one which has (non-null) data associated with it.
void	print() Prints all strings in the tree.
void	prune(BitString bs) Prunes the subtree rooted at the node associated with the given binary string.
java.lang.Object	remove(BitString bs) Removes and returns the data (if any) associated with the given binary string.
java.lang.Object	replace(BitString bs, java.lang.Object obj) Adds data to the tree, keyed by the given binary string, replacing any pre-existing data with that key which may have already been there.
RadixTreeNode	root() Returns the root node of the tree.
java.lang.Object	youngest_ancestor(BitString bs) Examines each node in the tree which is associated with a proper prefix of the given binary string, and finds the longest one which has (non-null) data associated with it.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

RadixTree

public RadixTree()

Constructs an empty radix tree.

Method Detail

root

public RadixTreeNode root()

Returns the root node of the tree.

Returns:

the root node of the tree

replace

public java.lang.Object replace(BitString bs,
                                java.lang.Object obj)

Adds data to the tree, keyed by the given binary string, replacing any pre-existing data with that key which may have already been there.

Parameters:

bs - The binary string to use as the key for the data.

obj - The data to add to the tree.

Returns:

data which was replaced by the addition; null if none

add

public java.lang.Object add(BitString bs,
                            java.lang.Object obj)

Attempts to add data to the tree, keyed by the given binary string, but fails if data associated with that string already exists. Upon failure, the pre-existing data is returned. Upon success, null is returned.

Parameters:

bs - The binary string to use as the key for the addition

obj - The data to add to the tree.

Returns:

data which was replaced by the addition; null if none

find

public java.lang.Object find(BitString bs)

Returns the data associated with the given binary string, if any.

Parameters:

bs - The bit string being used to key the find.

Returns:

data associated with the given binary string, if any

get_ancestors

public java.util.ArrayList get_ancestors(BitString bs)

Examines each node in the tree which is associated with a proper prefix of the given binary string, and finds all of the ones which have (non-null) data associated with them. A list containing the data of each such node is returned. Note that only proper prefixes are considered, so an exact match does not count.

Parameters:

bs - The bit string being used to key the search.

Returns:

the data from each prefix of the given bit string which has non-null data

oldest_ancestor

public java.lang.Object oldest_ancestor(BitString bs)

Examines each node in the tree which is associated with a proper prefix of the given binary string, and finds the shortest one which has (non-null) data associated with it. If such a prefix is found, its data is returned; otherwise, null is returned. Note that only proper prefixes are considered, so an exact match does not count.

Parameters:

bs - The bit string being used to key the search.

Returns:

the data from the shortest prefix of the given bit string which has non-null data

youngest_ancestor

public java.lang.Object youngest_ancestor(BitString bs)

Examines each node in the tree which is associated with a proper prefix of the given binary string, and finds the longest one which has (non-null) data associated with it. If such a prefix is found, its data is returned; otherwise, null is returned. Note that only proper prefixes are considered, so an exact match does not count.

Parameters:

bs - The bit string being used to key the search.

Returns:

the data from the longest prefix of the given bit string which has non-null data

get_descendants

public java.util.ArrayList get_descendants(BitString bs)

Examines each node in the tree whose binary string key has the given binary string as a proper prefix, and finds all of the ones which have (non-null) data associated with them. A list containing the data of each such node is returned. Note that only proper prefixes are considered, so an exact match does not count.

Parameters:

bs - The bit string which indicates the node to look for descendants of.

Returns:

a list containing the data from all descendants that have (non-null) data

has_descendants

public boolean has_descendants(BitString bs)

Determines whether or not any descendants of a given node have (non-null) data.

Parameters:

bs - The bit string which indicates the node to look for descendants of.

Returns:

true only if at least one descendant has (non-null) data

remove

public java.lang.Object remove(BitString bs)

Removes and returns the data (if any) associated with the given binary string.

Parameters:

bs - The bit string being used to key the removal.

Returns:

the data being removed, if any

prune

public void prune(BitString bs)

Prunes the subtree rooted at the node associated with the given binary string.

Parameters:

bs - The bit string being used to key the pruning.

print

public void print()

Prints all strings in the tree. We define a string as being "in" the tree if its associated data is non-null.