org.garret.perst
Interface PatriciaTrie<T extends IPersistent>

All Superinterfaces:

java.util.Collection, java.io.Externalizable, IPersistent, IResource, ITable, java.lang.Iterable, java.io.Serializable

public interface PatriciaTrie<T extends IPersistent>

extends IPersistent, IResource, ITable<T>

PATRICIA trie (Practical Algorithm To Retrieve Information Coded In Alphanumeric). Tries are a kind of tree where each node holds a common part of one or more keys. PATRICIA trie is one of the many existing variants of the trie, which adds path compression by grouping common sequences of nodes together.
This structure provides a very efficient way of storing values while maintaining the lookup time for a key in O(N) in the worst case, where N is the length of the longest key. This structure has it's main use in IP routing software, but can provide an interesting alternative to other structures such as hashtables when memory space is of concern.

Method Summary

T	add(PatriciaTrieKey key, T obj) Add new key to the trie
void	clear() Clear the trie: remove all elements from trie
java.util.ArrayList<T>	elements() Get list of all elements in the Trie
T	findBestMatch(PatriciaTrieKey key) Find best match with specified key
T	findExactMatch(PatriciaTrieKey key) Find exact match with specified key
T	remove(PatriciaTrieKey key) Removes key from the triesKFind exact match with specified key

Methods inherited from interface org.garret.perst.IPersistent

assignOid, deallocate, getOid, getStorage, invalidate, isDeleted, isModified, isPersistent, isRaw, load, loadAndModify, makePersistent, modify, onLoad, onStore, recursiveLoading, store

Methods inherited from interface java.io.Externalizable

readExternal, writeExternal

Methods inherited from interface org.garret.perst.IResource

exclusiveLock, exclusiveLock, reset, sharedLock, sharedLock, unlock

Methods inherited from interface org.garret.perst.ITable

select

Methods inherited from interface java.util.Collection

add, addAll, contains, containsAll, equals, hashCode, isEmpty, iterator, remove, removeAll, retainAll, size, toArray, toArray

Method Detail

add

T add(PatriciaTrieKey key,
      T obj)

Add new key to the trie

Parameters:

key - bit vector

obj - persistent object associated with this key

Returns:

previous object associtated with this key or null if there was no such object

clear

void clear()

Clear the trie: remove all elements from trie

Specified by:

clear in interface java.util.Collection

elements

java.util.ArrayList<T> elements()

Get list of all elements in the Trie

Returns:

list of all elements

findBestMatch

T findBestMatch(PatriciaTrieKey key)

Find best match with specified key

Parameters:

key - bit vector

Returns:

object associated with this deepest possible match with specified key

findExactMatch

T findExactMatch(PatriciaTrieKey key)

Find exact match with specified key

Parameters:

key - bit vector

Returns:

object associated with this key or NULL if match is not found

remove

T remove(PatriciaTrieKey key)

Removes key from the triesKFind exact match with specified key

Parameters:

key - bit vector

Returns:

object associated with removed key or null if such key is not found