org.garret.perst
Interface PatriciaTrie

All Superinterfaces:

java.io.Externalizable, IPersistent, IResource, ITable, java.io.Serializable

public interface PatriciaTrie

extends IPersistent, IResource, ITable

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

IPersistent	add(PatriciaTrieKey key, IPersistent obj) Add new key to the trie
void	clear() Clear the trie: remove all elements from trie
java.util.ArrayList	elements() Get all objects in the trie.
IPersistent	findBestMatch(PatriciaTrieKey key) Find best match with specified key
IPersistent	findExactMatch(PatriciaTrieKey key) Find exact match with specified key
java.util.Iterator	iterator() Get iterator through all trie members.
IPersistent	remove(PatriciaTrieKey key) Removes key from the triesKFind exact match with specified key
IPersistent[]	toArray() Get array of all members of the trie
IPersistent[]	toArray(IPersistent[] arr) Get all objects in the trie.

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, size

Method Detail

add

public IPersistent add(PatriciaTrieKey key,
                       IPersistent 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

public void clear()

Clear the trie: remove all elements from trie

elements

public java.util.ArrayList elements()

Get all objects in the trie.

Returns:

array list of all objects in the trie

findBestMatch

public IPersistent 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

public IPersistent 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

iterator

public java.util.Iterator iterator()

Get iterator through all trie members. Iteration is performed on the copy of the trie, so it is not possible to remove trie elements using this iterator and any modification of trie has no influence on iterator.

Specified by:

iterator in interface ITable

Returns:

iterator through all trie member

remove

public IPersistent 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

toArray

public IPersistent[] toArray()

Get array of all members of the trie

Returns:

array of trie members

toArray

public IPersistent[] toArray(IPersistent[] arr)

Get all objects in the trie. The runtime type of the returned array is that of the specified array. If the index fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this index.

If this index fits in the specified array with room to spare (i.e., the array has more elements than this index), the element in the array immediately following the end of the index is set to null. This is useful in determining the length of this index only if the caller knows that this index does not contain any null elements.)

Parameters:

arr - specified array

Returns:

array of all objects in the index