Table of Contents

Class LevelOrderBitsDictionary

Namespace
BelNytheraSeiche.TrieDictionary
Assembly
BelNytheraSeiche.TrieDictionary.dll

An abstract base class for read-only, trie-based dictionaries that are constructed in level-order.

public abstract class LevelOrderBitsDictionary : KeyRecordDictionary, KeyRecordDictionary.IKeyAccess
Inheritance
LevelOrderBitsDictionary
Implements
Derived
Inherited Members

Remarks

This class provides the common infrastructure for trie implementations that are "flattened" into arrays based on a breadth-first (level-order) traversal. The core data is stored in arrays for labels, parent pointers, and terminal node flags.

Concrete implementations must provide a strategy for navigating the tree structure, primarily by implementing the FindRange1(int) method.

Important Usage Notes: This class and its derivatives are read-only after creation. Key addition and removal operations are not supported.

Methods

Add(ReadOnlySpan<byte>)

This operation is not supported. The dictionary is read-only after creation.

public int Add(ReadOnlySpan<byte> key)

Parameters

key ReadOnlySpan<byte>

Returns

int

Exceptions

NotSupportedException

Always thrown.

AsStringSpecialized(Encoding?)

Returns a string-specialized wrapper for the dictionary's key access interface.

public KeyRecordDictionary.StringSpecialized AsStringSpecialized(Encoding? encoding = null)

Parameters

encoding Encoding

The encoding to use for string conversions. Defaults to UTF-8.

Returns

KeyRecordDictionary.StringSpecialized

A new KeyRecordDictionary.StringSpecialized instance providing string-based access to the dictionary.

Contains(ReadOnlySpan<byte>)

Determines whether the specified key exists in the graph.

public virtual bool Contains(ReadOnlySpan<byte> key)

Parameters

key ReadOnlySpan<byte>

The key to locate.

Returns

bool

true if the key is found; otherwise, false.

EnumerateAll(bool)

Enumerates all keys in the dictionary in lexicographical order.

public virtual IEnumerable<(int, byte[])> EnumerateAll(bool reverse = false)

Parameters

reverse bool

If true, returns keys in reverse lexicographical order.

Returns

IEnumerable<(int, byte[])>

An enumerable collection of all (identifier, key) tuples.

FindFirst(out int, out byte[])

Finds the first key in the dictionary in lexicographical order.

public virtual bool FindFirst(out int identifier, out byte[] key)

Parameters

identifier int

When this method returns, the identifier of the first key.

key byte[]

When this method returns, the first key.

Returns

bool

true if the dictionary is not empty; otherwise, false.

FindLast(out int, out byte[])

Finds the last key in the dictionary in lexicographical order.

public virtual bool FindLast(out int identifier, out byte[] key)

Parameters

identifier int

When this method returns, the identifier of the last key.

key byte[]

When this method returns, the last key.

Returns

bool

true if the dictionary is not empty; otherwise, false.

FindNext(int, out int, out byte[])

Finds the next key in lexicographical order after the specified identifier.

public virtual bool FindNext(int currentIdentifier, out int foundIdentifier, out byte[] foundKey)

Parameters

currentIdentifier int

The identifier to start the search from.

foundIdentifier int

When this method returns, the identifier of the next key.

foundKey byte[]

When this method returns, the next key.

Returns

bool

true if a next key was found; otherwise, false.

FindNext(ReadOnlySpan<byte>, out int, out byte[])

Finds the next key in lexicographical order after the specified key.

public virtual bool FindNext(ReadOnlySpan<byte> currentKey, out int foundIdentifier, out byte[] foundKey)

Parameters

currentKey ReadOnlySpan<byte>

The key to start the search from.

foundIdentifier int

When this method returns, the identifier of the next key.

foundKey byte[]

When this method returns, the next key.

Returns

bool

true if a next key was found; otherwise, false.

FindPrevious(int, out int, out byte[])

Finds the previous key in lexicographical order before the specified identifier.

public virtual bool FindPrevious(int currentIdentifier, out int foundIdentifier, out byte[] foundKey)

Parameters

currentIdentifier int

The identifier to start the search from.

foundIdentifier int

When this method returns, the identifier of the previous key.

foundKey byte[]

When this method returns, the previous key.

Returns

bool

true if a previous key was found; otherwise, false.

FindPrevious(ReadOnlySpan<byte>, out int, out byte[])

Finds the previous key in lexicographical order before the specified key.

public virtual bool FindPrevious(ReadOnlySpan<byte> currentKey, out int foundIdentifier, out byte[] foundKey)

Parameters

currentKey ReadOnlySpan<byte>

The key to start the search from.

foundIdentifier int

When this method returns, the identifier of the previous key.

foundKey byte[]

When this method returns, the previous key.

Returns

bool

true if a previous key was found; otherwise, false.

GetKey(int)

Gets the key associated with the specified identifier.

public virtual byte[] GetKey(int identifier)

Parameters

identifier int

The identifier of the key to get.

Returns

byte[]

The key as a byte array.

Exceptions

ArgumentOutOfRangeException

The specified identifier does not exist.

GetRecordAccess(int, bool)

Gets an accessor for the list of records associated with a given key identifier.

public KeyRecordDictionary.IRecordAccess GetRecordAccess(int identifier, bool isTransient = false)

Parameters

identifier int

The identifier of the key whose records are to be accessed. This must be a valid key identifier obtained from a search or add operation.

isTransient bool

If true, accesses the transient (in-memory) record store; otherwise, accesses the persistent record store.

Returns

KeyRecordDictionary.IRecordAccess

An KeyRecordDictionary.IRecordAccess handle for the specified record list.

Remarks

Note that while new records can be added to a key's record list, new keys cannot be added to the dictionary itself after creation.

Exceptions

ArgumentOutOfRangeException

identifier is negative.

ArgumentException

The specified identifier is invalid or does not exist.

Remove(int)

This operation is not supported. The dictionary is read-only after creation.

public bool Remove(int identifier)

Parameters

identifier int

Returns

bool

Exceptions

NotSupportedException

Always thrown.

Remove(ReadOnlySpan<byte>)

This operation is not supported. The dictionary is read-only after creation.

public bool Remove(ReadOnlySpan<byte> key)

Parameters

key ReadOnlySpan<byte>

Returns

bool

Exceptions

NotSupportedException

Always thrown.

SearchByPrefix(ReadOnlySpan<byte>, bool)

Finds all keys that start with the given prefix.

public virtual IEnumerable<(int, byte[])> SearchByPrefix(ReadOnlySpan<byte> sequence, bool reverse = false)

Parameters

sequence ReadOnlySpan<byte>

The prefix to search for.

reverse bool

If true, returns results in reverse lexicographical order.

Returns

IEnumerable<(int, byte[])>

An enumerable collection of (identifier, key) tuples for all keys starting with the prefix.

Remarks

This is the implementation of interface method. For detailed behavior and examples, see SearchByPrefix(ReadOnlySpan<byte>, bool).

SearchCommonPrefix(ReadOnlySpan<byte>)

Finds all keys in the dictionary that are prefixes of the given sequence.

public virtual IEnumerable<(int, byte[])> SearchCommonPrefix(ReadOnlySpan<byte> sequence)

Parameters

sequence ReadOnlySpan<byte>

The sequence to search within.

Returns

IEnumerable<(int, byte[])>

An enumerable collection of (identifier, key) tuples for all matching prefixes.

Remarks

This is the implementation of interface method. For detailed behavior and examples, see SearchCommonPrefix(ReadOnlySpan<byte>).

SearchExactly(ReadOnlySpan<byte>)

Searches for an exact match of the given sequence and returns its identifier.

public virtual int SearchExactly(ReadOnlySpan<byte> sequence)

Parameters

sequence ReadOnlySpan<byte>

The key to search for.

Returns

int

The positive identifier for the key if found; otherwise, a non-positive value.

SearchLongestPrefix(ReadOnlySpan<byte>)

Finds the longest key in the dictionary that is a prefix of the given sequence.

public virtual (int, byte[]) SearchLongestPrefix(ReadOnlySpan<byte> sequence)

Parameters

sequence ReadOnlySpan<byte>

The sequence to search within.

Returns

(int, byte[])

A tuple containing the identifier and key of the longest matching prefix, or (-1, []) if no match is found.

Remarks

This is the implementation of interface method. For detailed behavior and examples, see SearchLongestPrefix(ReadOnlySpan<byte>).

SearchWildcard(ReadOnlySpan<byte>, ReadOnlySpan<char>, bool)

Performs a wildcard search for keys matching a pattern.

public virtual IEnumerable<(int, byte[])> SearchWildcard(ReadOnlySpan<byte> sequence, ReadOnlySpan<char> cards, bool reverse = false)

Parameters

sequence ReadOnlySpan<byte>

The byte sequence of the pattern.

cards ReadOnlySpan<char>

A sequence of characters ('?' for single, '*' for multiple wildcards) corresponding to the pattern.

reverse bool

If true, returns results in reverse order.

Returns

IEnumerable<(int, byte[])>

An enumerable collection of matching (identifier, key) tuples.

Remarks

This is the implementation of interface method. For detailed behavior and examples, see SearchWildcard(ReadOnlySpan<byte>, ReadOnlySpan<char>, bool).

TryAdd(ReadOnlySpan<byte>, out int)

This operation is not supported. The dictionary is read-only after creation.

public bool TryAdd(ReadOnlySpan<byte> key, out int identifier)

Parameters

key ReadOnlySpan<byte>
identifier int

Returns

bool

Exceptions

NotSupportedException

Always thrown.

TryGetKey(int, out byte[])

Tries to get the key associated with the specified identifier.

public virtual bool TryGetKey(int identifier, out byte[] key)

Parameters

identifier int

The identifier of the key to get.

key byte[]

When this method returns, contains the key if found; otherwise, an empty array.

Returns

bool

true if the key was found; otherwise, false.