Table of Contents

Class DirectedAcyclicGraphDictionary

Namespace
BelNytheraSeiche.TrieDictionary
Assembly
BelNytheraSeiche.TrieDictionary.dll

A concrete implementation of KeyRecordDictionary that uses a Directed Acyclic Word Graph (DAWG).

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

Remarks

This class stores keys in a DAWG, which is a data structure that compresses a standard Trie by merging common prefixes and suffixes to reduce redundancy.

Important Usage Notes:

  • Read-Only Structure: The dictionary is built once from a collection of keys and is effectively read-only afterward. The Add and Remove operations for keys are not supported and will throw a NotSupportedException.

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.

Create(IEnumerable<byte[]>, SearchDirectionType)

Creates a new DirectedAcyclicGraphDictionary from a collection of keys.

public static DirectedAcyclicGraphDictionary 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

DirectedAcyclicGraphDictionary

A new, optimized, and read-only DirectedAcyclicGraphDictionary instance.

Remarks

The input keys are sorted and used to build a minimal, compressed graph structure.

Exceptions

ArgumentNullException

keys is null.

Deserialize(Stream)

Deserializes a dictionary from a stream.

public static DirectedAcyclicGraphDictionary Deserialize(Stream stream)

Parameters

stream Stream

The stream to read the serialized data from.

Returns

DirectedAcyclicGraphDictionary

A new instance of DirectedAcyclicGraphDictionary.

Exceptions

InvalidDataException

The stream data is corrupted or in an unsupported format.

ArgumentNullException

stream is null.

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

ArgumentException

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[])

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 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(DirectedAcyclicGraphDictionary, Stream, SerializationOptions?)

Serializes the state of the dictionary into a stream.

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

Parameters

dictionary DirectedAcyclicGraphDictionary

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 graph implementation.

Exceptions

ArgumentNullException

dictionary or stream is null.

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.