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:

/Core/Loyc.Utilities/Collections/CPTrie/CPIntTrie.cs

Inheritance diagram for Loyc.Collections.Impl.CPIntTrie< 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

TValue Type 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 >
V	this[K key] `[get]`
	Gets the value associated with the specified key. More...

Properties inherited from Loyc.Collections.IIndexed< int, TValue >
V	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

key	Key to remove.
oldValue	If 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

value On 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

value A 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.

Remarks

Nested classes

Properties

Public Member Functions

Protected Member Functions

Additional Inherited Members

Member Function Documentation

◆ Add()

◆ ContainsKey()

◆ Remove() [1/2]

◆ Remove() [2/2]

◆ TryAdd() [1/2]

◆ TryAdd() [2/2]

◆ TryGetValue()

Property Documentation

◆ this[int key, TValue defaultValue]