Class DoubleArrayDictionary

Namespace

BelNytheraSeiche.TrieDictionary

Assembly

BelNytheraSeiche.TrieDictionary.dll

A concrete implementation of KeyRecordDictionary that uses a mutable Double-Array trie structure.

public abstract class DoubleArrayDictionary : KeyRecordDictionary, KeyRecordDictionary.IKeyAccess

Inheritance

object

KeyRecordDictionary

DoubleArrayDictionary

Implements

KeyRecordDictionary.IKeyAccess

Inherited Members

KeyRecordDictionary.SearchDirection

KeyRecordDictionary.Additional1

KeyRecordDictionary.Additional2

KeyRecordDictionary.Create<T>(KeyRecordDictionary.SearchDirectionType)

KeyRecordDictionary.Create<T>(IEnumerable<byte[]>, KeyRecordDictionary.SearchDirectionType)

KeyRecordDictionary.Create<T>(IEnumerable<string>, Encoding, KeyRecordDictionary.SearchDirectionType)

KeyRecordDictionary.Serialize<T>(T, KeyRecordDictionary.SerializationOptions)

KeyRecordDictionary.Serialize<T>(T, string, KeyRecordDictionary.SerializationOptions)

KeyRecordDictionary.Serialize<T>(T, Stream, KeyRecordDictionary.SerializationOptions)

KeyRecordDictionary.Deserialize<T>(byte[])

KeyRecordDictionary.Deserialize<T>(string)

KeyRecordDictionary.Deserialize<T>(Stream)

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Remarks

This class provides very fast key lookups by representing a trie data structure in two compact arrays ('BASE' and 'CHECK').

Important Usage Notes:

• Mutable Structure: Unlike the DAWG or LOUDS implementations, this dictionary is mutable. Keys can be added and removed after the initial creation.
• Fragmentation: Repeated additions and removals can lead to fragmentation of the internal arrays, which may degrade performance and increase memory usage over time. To eliminate fragmentation and optimize the structure, it is recommended to periodically rebuild the dictionary using the static Compact(DoubleArrayDictionary) method.

Methods

Add(ReadOnlySpan<byte>)

Adds a key to the dictionary. If the key already exists, its existing identifier is returned.

public virtual int Add(ReadOnlySpan<byte> key)

Parameters

key ReadOnlySpan<byte>

The key to add.

Returns

int

The identifier for the added or existing key.

Exceptions

ArgumentException

key is empty.

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.

Clear()

Removes all keys and records from the dictionary and resets its internal state.

public void Clear()

Compact(DoubleArrayDictionary)

Rebuilds the dictionary to eliminate fragmentation and optimize its internal structure.

public static DoubleArrayDictionary Compact(DoubleArrayDictionary original)

Parameters

original DoubleArrayDictionary

The original, potentially fragmented dictionary to compact.

Returns

DoubleArrayDictionary

A new, compacted DoubleArrayDictionary instance containing the same keys and records.

Remarks

This method should be used when performance or memory usage degrades after a large number of additions and removals. It works by creating a new dictionary from the keys of the original, effectively rebuilding the internal arrays.

Important: The integer identifiers assigned to keys in the new, compacted dictionary will be different from those in the original. Any external references to the old identifiers will be invalid after compaction.

Exceptions

ArgumentNullException

original is null.

Contains(ReadOnlySpan<byte>)

Determines whether the specified key exists in the dictionary.

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.

Create(IEnumerable<byte[]>, SearchDirectionType)

Creates a new DoubleArrayDictionary from a collection of keys.

public static DoubleArrayDictionary Create(IEnumerable<byte[]> keys, KeyRecordDictionary.SearchDirectionType searchDirection = SearchDirectionType.LTR)

Parameters

keys IEnumerable<byte[]>

An enumerable collection of byte arrays to use as the initial keys. The collection does not need to be pre-sorted. Duplicate keys are permitted, but only the first occurrence will be added. The collection must not contain any elements that are null or empty byte array.

searchDirection KeyRecordDictionary.SearchDirectionType

The key search direction for the new dictionary.

Returns

DoubleArrayDictionary

A new, mutable DoubleArrayDictionary instance.

Exceptions

ArgumentNullException

keys is null.

Deserialize(Stream)

Deserializes a dictionary from a stream.

public static DoubleArrayDictionary Deserialize(Stream stream)

Parameters

stream Stream

The stream to read the serialized data from.

Returns

DoubleArrayDictionary

A new instance of DoubleArrayDictionary.

Exceptions

ArgumentNullException

stream is null.

InvalidDataException

The stream data is corrupted or in an unsupported format.

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 is out of the valid range.

ArgumentException

The specified identifier is invalid.

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

ArgumentException

The specified identifier is invalid or does not exist.

Remove(int)

Removes a key and its associated records from the dictionary using its identifier.

public virtual bool Remove(int identifier)

Parameters

identifier int

The identifier of the key to remove.

Returns

bool

true if the key was found and removed; otherwise, false.

Remove(ReadOnlySpan<byte>)

Removes a key and its associated records from the dictionary.

public virtual bool Remove(ReadOnlySpan<byte> key)

Parameters

key ReadOnlySpan<byte>

The key to remove.

Returns

bool

true if the key was found and removed; otherwise, false.

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).

Serialize(DoubleArrayDictionary, Stream, SerializationOptions?)

Serializes the state of the dictionary into a stream.

public static void Serialize(DoubleArrayDictionary dictionary, Stream stream, KeyRecordDictionary.SerializationOptions? options = null)

Parameters

dictionary DoubleArrayDictionary

The dictionary instance to serialize.

stream Stream

The stream to write the serialized data to.

options KeyRecordDictionary.SerializationOptions

Options to control the serialization process. If null, the settings from Default will be used.

Remarks

The serialization format is a custom binary format specific to this Double-Array trie implementation.

Exceptions

ArgumentNullException

dictionary or stream is null.

TryAdd(ReadOnlySpan<byte>, out int)

Tries to add a key to the dictionary.

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

Parameters

key ReadOnlySpan<byte>

The key to add.

identifier int

When this method returns, contains the identifier for the new key. If the key already existed, this will be the existing identifier.

Returns

bool

true if the key was newly added; false if the key already existed.

Exceptions

ArgumentException

key is empty.

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.