Loyc.Collections.CPTrie< T > Class Template Reference

Compact patricia tree class that stores keys as byte arrays. This class is intended to be use as a base class; a derived class can give meaning to the byte arrays, e.g. CPStringTrie encodes strings into byte arrays so they can be placed in the trie. More...

---

Source file:

• /Core/Loyc.Collections/CPTrie/CPTrie.cs

Inheritance diagram for Loyc.Collections.CPTrie< T >:

Remarks

Compact patricia tree class that stores keys as byte arrays. This class is intended to be use as a base class; a derived class can give meaning to the byte arrays, e.g. CPStringTrie encodes strings into byte arrays so they can be placed in the trie.

An article is available online the CPTrie data types.

Template Parameters

T	Type of values to be associated with the keys. CPTrie can save memory if many or all values are null; therefore, if you wish to store a set rather than a dictionary, set T=object and associate null with every key.

Public Member Functions
	CPTrie (CPTrie< T > copy)

Protected Member Functions
bool	Find (ref KeyWalker key, CPEnumerator< T > e)
bool	Find (ref KeyWalker key, ref T value)
	Retrieves the value associated with the specified key; does nothing if the key does not exist. More...
bool	ContainsKey (ref KeyWalker key)
bool	Set (ref KeyWalker key, ref T value, CPMode mode)
	Associates the specified value with the specified key. More...
bool	Remove (ref KeyWalker key, ref T value)
	Removes the specified key and associated value. More...
bool	Remove (ref KeyWalker key)
void	Clear ()
int	CountMemoryUsage (int sizeOfT)
	Calculates the memory usage of this object, assuming a 32-bit architecture. More...

Static Protected Member Functions
static StringBuilder	BytesToStringBuilder (byte[] key, int keyLength)

Protected static fields
static Comparer< T >	DefaultComparer = Comparer<T>.Default

Member Function Documentation

int Loyc.Collections.CPTrie< T >.CountMemoryUsage ( int  sizeOfT )

inlineprotected

Calculates the memory usage of this object, assuming a 32-bit architecture.

Parameters

sizeOfT

Size of data type T. CountMemoryUsage doesn't use sizeof(T), as it would force the code to be marked "unsafe".

Returns

Estimated number of bytes used by this object

bool Loyc.Collections.CPTrie< T >.Find ( ref KeyWalker  key, ref T  value  )

inlineprotected

Retrieves the value associated with the specified key; does nothing if the key does not exist.

Returns

Returns true if the key was found.

bool Loyc.Collections.CPTrie< T >.Remove ( ref KeyWalker  key, ref T  value  )

inlineprotected

Removes the specified key and associated value.

Parameters

key	Key to find; if key.Offset > 0, bytes before that offset are ignored.
value	If the key was found, its associated value is stored in this parameter; otherwise, the parameter is left unchanged.

Returns

Returns true if the specified key was found and removed.

bool Loyc.Collections.CPTrie< T >.Set ( ref KeyWalker  key, ref T  value, CPMode  mode  )

inlineprotected

Associates the specified value with the specified key.

Parameters

key	A key to find or create; if key.Offset > 0, bytes before that offset are ignored.
value	Value to assign to the node, depending on the value of mode. On return, value is set to the previous value for the given key.
mode	Specifies whether to create an entry if the key is not present, and whether to change an existing entry. If mode is Find, Set() only retrieves an existing value; it does not change the trie.

Returns

Returns true if the specified key already existed and false if it did not.