Class TreapRecordStore

Namespace

BelNytheraSeiche.TrieDictionary

Assembly

BelNytheraSeiche.TrieDictionary.dll

A concrete implementation of BinaryTreeRecordStore that uses a Treap.

public class TreapRecordStore : BinaryTreeRecordStore, ICloneable

Inheritance

object

BasicRecordStore

BinaryTreeRecordStore

TreapRecordStore

Implements

ICloneable

Inherited Members

BinaryTreeRecordStore.Clear()

BinaryTreeRecordStore.Contains(int)

BinaryTreeRecordStore.GetRecordAccess(int, out bool)

BinaryTreeRecordStore.TryGetRecordAccess(int, out BasicRecordStore.RecordAccess)

BinaryTreeRecordStore.Enumerate()

BinaryTreeRecordStore.PrintTree(TextWriter)

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

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

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

BasicRecordStore.Deserialize<T>(byte[])

BasicRecordStore.Deserialize<T>(string)

BasicRecordStore.Deserialize<T>(Stream)

BasicRecordStore.Add(int)

BasicRecordStore.GetRecordAccess(int)

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Remarks

A Treap is a randomized binary search tree. It maintains the binary search tree property for its keys (identifiers) and the max-heap property for randomly assigned priorities. This combination maintains balance with high probability, providing good average-case performance for insertions, deletions, and lookups.

Serialization Limits: The binary serialization format for this class imposes certain constraints on the data. Exceeding these limits will result in an InvalidDataException during serialization.

• Max Records per List: A single identifier can have a maximum of 16,777,215 records in its linked list.
• Max Record Content Size: The Content byte array of any single record cannot exceed 65,535 bytes.

Methods

Clone()

Creates a deep copy of the TreapRecordStore.

public virtual object Clone()

Returns

object

A new TreapRecordStore instance with the same record data as the original.

Remarks

The method creates a new tree and copies all records. The new tree will have newly randomized priorities for its nodes, so its internal structure may differ from the original, but it will be functionally equivalent.

Deserialize(Stream)

Deserializes a TreapRecordStore from a stream.

public static TreapRecordStore Deserialize(Stream stream)

Parameters

stream Stream

The stream to read the serialized data from.

Returns

TreapRecordStore

A new instance of TreapRecordStore reconstructed from the stream.

Exceptions

ArgumentNullException

stream is null.

InvalidDataException

The stream data is corrupted, in an unsupported format, or contains invalid values.

IsBalanced()

Overrides the base method to check if the tree is a valid tree.

public override bool IsBalanced()

Returns

bool

true if the tree satisfies both the binary search tree property (for identifiers) and the max-heap property (for priorities); otherwise, false.

Remove(int)

Removes the node with the specified identifier from the tree, performing rotations to maintain the heap property before removal.

public override void Remove(int identifier)

Parameters

identifier int

The identifier of the node to remove.

Exceptions

ArgumentOutOfRangeException

identifier is MinValue.

Serialize(TreapRecordStore, Stream, SerializationOptions?)

Serializes the entire state of the tree, including node priorities, into a stream.

public static void Serialize(TreapRecordStore store, Stream stream, BasicRecordStore.SerializationOptions? options = null)

Parameters

store TreapRecordStore

The TreapRecordStore instance to serialize.

stream Stream

The stream to write the serialized data to.

options BasicRecordStore.SerializationOptions

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

Remarks

The serialization format is specific to this tree implementation, using Brotli compression and an XxHash32 checksum for data integrity.

Exceptions

ArgumentNullException

store or stream is null.