Enhanced C#
Language of your choice: library documentation
Nested classes | Properties | Public Member Functions | Protected Member Functions | List of all members
Loyc.Collections.Impl.CPIntTrie< TValue > Class Template Reference

A trie that supports signed and unsigned keys with sizes up to 64 bits. Special encodings are used to preserve the sort order among integers of different sizes while using variable-length keys. More...


Source file:
Inheritance diagram for Loyc.Collections.Impl.CPIntTrie< TValue >:
Loyc.Collections.CPTrie< TValue > Loyc.Collections.IIndexed< long, TValue > Loyc.Collections.IIndexed< int, TValue >

Remarks

A trie that supports signed and unsigned keys with sizes up to 64 bits. Special encodings are used to preserve the sort order among integers of different sizes while using variable-length keys.

Template Parameters
TValueType of value associated with each key.

This trie allows you to insert integers of different sizes. Two integers of different sizes that have the same value are considered equivalent. You can insert a key as an Int16, then extract it as an Int32, for example.

This collection implements two versions of IDictionary: one using Int32 keys and another using Int64 keys. When calling a method on the class itself (i.e. not on an interface), Int64 is used in case of ambiguity (for example, GetEnumerator() doesn't know if you want to decode the keys into Int32 or Int64, so it uses Int64.) When not accessing CPIntTrie through an interface, most methods accept any of the following integer types: Int16, UInt16, Int32, UInt32, Int64, UInt64.

The trie does not choose the key length based on an integer's size (e.g. Int32 or Int64), rather it is chosen based on the key's magnitude. Keys ranging from -0x10000 to 0xFAFFFF are encoded most compactly (usually in one 4-byte cell); 40-bit keys as low as -0xFFFFFFFFFF and as high as 0xFFFFFFFFFF are usually encoded in 2 cells; and all larger keys require 3 cells.

I say "usually" because normally CPSNode can hold 3 bytes per cell, but keys whose low-order byte is 0xFD, 0xFE or 0xFF require one extra cell.

Negative 64-bit numbers can be held in the same trie as unsigned 64-bit numbers; therefore, there is no way to represent all keys using a single primitive data type. The LongEnumerator returns Int64s, and you will find that if a huge unsigned number like 0x8877665544332211 is in the trie, it will come out as a negative Int64. To find out whether the long number is signed or unsigned, call ContainsKey(Int64) - if it returns true, the number is signed, otherwise it is unsigned (so its signed representation was not found). If it is unsigned, convert the key returned by the enumerator to UInt64.

Nested classes

class  IntEnumerator
 
class  LongEnumerator
 

Properties

TValue this[int key, TValue defaultValue] [get]
 Finds the specified key and returns its associated value. If the key did not exist, returns defaultValue instead. More...
 
TValue this[uint key, TValue defaultValue] [get]
 
TValue this[short key, TValue defaultValue] [get]
 
TValue this[ushort key, TValue defaultValue] [get]
 
TValue this[long key, TValue defaultValue] [get]
 
TValue this[ulong key, TValue defaultValue] [get]
 
TValue this[int key] [get, set]
 
TValue this[uint key] [get, set]
 
TValue this[short key] [get, set]
 
TValue this[ushort key] [get, set]
 
TValue this[long key] [get, set]
 
TValue this[ulong key] [get, set]
 
ICollection< long > Keys [get]
 
ICollection< TValue > Values [get]
 
new int Count [get]
 
bool IsReadOnly [get]
 
bool IsEmpty [get]
 
- Properties inherited from Loyc.Collections.IIndexed< long, TValue >
this[K key] [get]
 Gets the value associated with the specified key. More...
 
- Properties inherited from Loyc.Collections.IIndexed< int, TValue >
this[K key] [get]
 Gets the value associated with the specified key. More...
 

Public Member Functions

 CPIntTrie (CPIntTrie< TValue > clone)
 
new int CountMemoryUsage (int sizeOfT)
 
bool TryAdd (int key, TValue value)
 Adds the specified key-value pair only if the specified key is not already present in the trie. More...
 
bool TryAdd (int key, ref TValue value)
 Adds the specified key-value pair only if the specified key is not already present in the trie. More...
 
bool TryAdd (uint key, TValue value)
 
bool TryAdd (uint key, ref TValue value)
 
bool TryAdd (short key, TValue value)
 
bool TryAdd (short key, ref TValue value)
 
bool TryAdd (ushort key, TValue value)
 
bool TryAdd (ushort key, ref TValue value)
 
bool TryAdd (long key, TValue value)
 
bool TryAdd (long key, ref TValue value)
 
bool TryAdd (ulong key, TValue value)
 
bool TryAdd (ulong key, ref TValue value)
 
void Add (int key, TValue value)
 Adds the specified key-value pair to the trie, throwing an exception if the key is already present. More...
 
void Add (uint key, TValue value)
 
void Add (short key, TValue value)
 
void Add (ushort key, TValue value)
 
void Add (long key, TValue value)
 
void Add (ulong key, TValue value)
 
bool ContainsKey (int key)
 Searches for the specified key, returning true if it is present in the trie. More...
 
bool ContainsKey (uint key)
 
bool ContainsKey (short key)
 
bool ContainsKey (ushort key)
 
bool ContainsKey (long key)
 
bool ContainsKey (ulong key)
 
bool Remove (int key)
 Removes the specified key and associated value, returning true if the entry was found and removed. More...
 
bool Remove (uint key)
 
bool Remove (short key)
 
bool Remove (ushort key)
 
bool Remove (long key)
 
bool Remove (ulong key)
 
bool Remove (int key, ref TValue oldValue)
 Removes the specified key and associated value, returning true if the entry was found and removed. More...
 
bool Remove (uint key, ref TValue oldValue)
 
bool Remove (short key, ref TValue oldValue)
 
bool Remove (ushort key, ref TValue oldValue)
 
bool Remove (long key, ref TValue oldValue)
 
bool Remove (ulong key, ref TValue oldValue)
 
bool TryGetValue (int key, out TValue value)
 Finds the specified key and gets its associated value, returning true if the key was found. More...
 
bool TryGetValue (uint key, out TValue value)
 
bool TryGetValue (short key, out TValue value)
 
bool TryGetValue (ushort key, out TValue value)
 
bool TryGetValue (long key, out TValue value)
 
bool TryGetValue (ulong key, out TValue value)
 
void Add (KeyValuePair< int, TValue > item)
 
void Add (KeyValuePair< long, TValue > item)
 
new void Clear ()
 
bool Contains (KeyValuePair< int, TValue > item)
 
bool Contains (KeyValuePair< long, TValue > item)
 
void CopyTo (KeyValuePair< int, TValue >[] array, int arrayIndex)
 
void CopyTo (KeyValuePair< long, TValue >[] array, int arrayIndex)
 
bool Remove (KeyValuePair< int, TValue > item)
 
bool Remove (KeyValuePair< long, TValue > item)
 
LongEnumerator GetEnumerator ()
 
IntEnumerator GetIntEnumerator ()
 
IntEnumerator FindAtLeast (int key)
 
LongEnumerator FindAtLeast (long key)
 
LongEnumerator FindAtLeast (ulong key)
 
IntEnumerator FindExact (int key)
 
LongEnumerator FindExact (long key)
 
LongEnumerator FindExact (ulong key)
 
bool Find (int key, out IntEnumerator e)
 
bool Find (long key, out LongEnumerator e)
 
bool Find (ulong key, out LongEnumerator e)
 
CPIntTrie< TValue > Clone ()
 
- Public Member Functions inherited from Loyc.Collections.CPTrie< TValue >
 CPTrie (CPTrie< T > copy)
 

Protected Member Functions

bool IsShortKey (int key)
 
bool IsShortKey (uint key)
 
bool IsLongKey (long key)
 
bool IsLongKey (ulong key)
 
KeyWalker EncodeShort (int key)
 
KeyWalker EncodeMed (int key)
 
KeyWalker EncodeMed (long key)
 
KeyWalker EncodeLong (long key)
 
KeyWalker EncodeLong (ulong key)
 
TValue GetValue (ref KeyWalker key, int keyI)
 
TValue GetValue (ref KeyWalker key, long keyI)
 
TValue GetValue (ref KeyWalker key, ulong keyI)
 
- Protected Member Functions inherited from Loyc.Collections.CPTrie< TValue >
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...
 

Additional Inherited Members

- Static Protected Member Functions inherited from Loyc.Collections.CPTrie< TValue >
static StringBuilder BytesToStringBuilder (byte[] key, int keyLength)
 
- Protected static fields inherited from Loyc.Collections.CPTrie< TValue >
static Comparer< T > DefaultComparer
 

Member Function Documentation

◆ Add()

void Loyc.Collections.Impl.CPIntTrie< TValue >.Add ( int  key,
TValue  value 
)
inline

Adds the specified key-value pair to the trie, throwing an exception if the key is already present.

References Loyc.Collections.Impl.CPIntTrie< TValue >.TryAdd().

◆ ContainsKey()

bool Loyc.Collections.Impl.CPIntTrie< TValue >.ContainsKey ( int  key)
inline

Searches for the specified key, returning true if it is present in the trie.

References Loyc.Collections.Impl.CPIntTrie< TValue >.TryGetValue().

◆ Remove() [1/2]

bool Loyc.Collections.Impl.CPIntTrie< TValue >.Remove ( int  key)
inline

Removes the specified key and associated value, returning true if the entry was found and removed.

◆ Remove() [2/2]

bool Loyc.Collections.Impl.CPIntTrie< TValue >.Remove ( int  key,
ref TValue  oldValue 
)
inline

Removes the specified key and associated value, returning true if the entry was found and removed.

Parameters
keyKey to remove.
oldValueIf the key is found, the associated value is assigned to this parameter. Otherwise, this parameter is not changed.

◆ TryAdd() [1/2]

bool Loyc.Collections.Impl.CPIntTrie< TValue >.TryAdd ( int  key,
ref TValue  value 
)
inline

Adds the specified key-value pair only if the specified key is not already present in the trie.

Parameters
valueOn entry, value specifies the value to associate with the specified key, but if the key already exists, value is changed to the value associated with the existing key.
Returns
Returns true if the key-value pair was added or false if the key already existed. In the false case, the trie is not modified.

◆ TryAdd() [2/2]

bool Loyc.Collections.Impl.CPIntTrie< TValue >.TryAdd ( int  key,
TValue  value 
)
inline

Adds the specified key-value pair only if the specified key is not already present in the trie.

Parameters
valueA value to associate with the specified key if the key does not already exist.
Returns
Returns true if the key-value pair was added or false if the key already existed. In the false case, the trie is not modified.

Referenced by Loyc.Collections.Impl.CPIntTrie< TValue >.Add().

◆ TryGetValue()

bool Loyc.Collections.Impl.CPIntTrie< TValue >.TryGetValue ( int  key,
out TValue  value 
)
inline

Finds the specified key and gets its associated value, returning true if the key was found.

Referenced by Loyc.Collections.Impl.CPIntTrie< TValue >.ContainsKey().

Property Documentation

◆ this[int key, TValue defaultValue]

TValue Loyc.Collections.Impl.CPIntTrie< TValue >.this[int key, TValue defaultValue]
get

Finds the specified key and returns its associated value. If the key did not exist, returns defaultValue instead.