ColaStore<T>

Namespace: SnowBank.Collections.CacheOblivious · class

Implements: IDisposable

Store elements in a list of ordered levels

Constructors

ColaStore<T>

ColaStore<T>(ColaStore<T> source)

Constructs a ColaStore with a copy of the contents of another store

• source — Store to use as the source

Adding or removing elements to this new instance will not impact the source, and vice versa.

ColaStore<T>(int capacity, IComparer<T> comparer, ArrayPool<T> pool = null)

Allocates a new store

• capacity — Initial capacity, or 0 for the default capacity
• comparer — Comparer used to order the elements
• pool — Pool used to allocate levels

Properties

Capacity

int Capacity { get; }

Gets the current capacity of the store.

Comparer

IComparer<T> Comparer { get; }

Gets the comparer used to sort the elements in the store

Count

int Count { get; }

Gets the number of elements in the store.

Depth

int Depth { get; }

Gets the current number of levels

Note that the last level may not be currently used!

Item

T Item { get; }

MaxLevel

int MaxLevel { get; }

Gets the index of the last currently allocated level

MinLevel

int MinLevel { get; }

Gets the index of the first currently allocated level

Methods

Clear

void Clear()

Clears the array

Copy

ColaStore<T> Copy()

Returns a copy of this store

Returns: New store with a copy of the contents of this instance

Adding or removing elements to this new instance will not impact the source, and vice versa.

CopyTo

void CopyTo(Span<T> destination)

Copies the contents of this store into destination span.

• destination — The span to copy items into.

Debug_Dump

void Debug_Dump(TextWriter output, Func<T, string> dump = null)

Writes the contents of this store into a log, for debugging purpose [DEBUG ONLY]

Dispose

void Dispose()

EnsureCapacity

void EnsureCapacity(int minimumRequired)

Pre-allocate memory in the store so that it can store a specified amount of items

• minimumRequired — Number of items that will be inserted in the store

Find

T Find(T value, out int level, out int offset)

Finds the location of an element in the array

• value — Value of the element to search for.
• level — Receives the level that contains the element if found; otherwise, -1.
• offset — Receives the offset of the element inside the level if found; otherwise, 0.

Returns: Reference to the entry, or null if not found.

FindBetween

IEnumerable<T> FindBetween(T beginInclusive, T endExclusive, int limit, IComparer<T> comparer = null)

Enumerates all the items in the store that are between two bounds

• beginInclusive — Inclusive lower bound
• endExclusive — Exclusive upper bound
• limit — Maximum number of items to return
• comparer — Optional comparer (if null use the comparer used by the store)

Returns: Sequence that will return all elements in this store that are greater than or equal to beginInclusive and strictly less than endExclusive, up to a maximum of limit results.

IEnumerable<T> FindBetween(T begin, bool beginOrEqual, T end, bool endOrEqual, int limit, IComparer<T> comparer = null)

Enumerates all the items in the store that are between two bounds

• begin — Lower bound
• beginOrEqual — Specifies if the lower bound is included (true) or not (false)
• end — Upper bound
• endOrEqual — Specifies if the upper bound is included (true) or not (false)
• limit — Maximum number of items to return
• comparer — Optional comparer (if null use the comparer used by the store)

Returns: Sequence that will return all elements in this store that are greater than (or equal to) begin and less than (or equal to) end, up to a maximum of limit results.

FindNext

int FindNext(T value, bool orEqual, out int offset, out T result)

Searches for the smallest element that is larger than a reference element

• value — Reference element
• orEqual — If true, return the position of the value itself if it is found. If false, return the position of the closest value that is smaller.
• offset — Receive the offset within the level of the next element, or 0 if not found
• result — Receive the value of the next element, or default(T) if not found

Returns: Level of the next element, or -1 if result was already the largest

int FindNext(T value, bool orEqual, IComparer<T> comparer, out int offset, out T result)

Searches for the smallest element that is larger than a reference element

• value — Reference element
• orEqual — If true, return the position of the value itself if it is found. If false, return the position of the closest value that is smaller.
• offset — Receive the offset within the level of the next element, or 0 if not found
• result — Receive the value of the next element, or default(T) if not found

Returns: Level of the next element, or -1 if result was already the largest

FindPrevious

int FindPrevious(T value, bool orEqual, out int offset, out T result)

Searches for the largest element that is smaller than a reference element

• value — Reference element
• orEqual — If true, return the position of the value itself if it is found. If false, return the position of the closest value that is smaller.
• offset — Receive the offset within the level of the previous element, or 0 if not found
• result — Receive the value of the previous element, or default(T) if not found

Returns: Level of the previous element, or -1 if result was already the smallest

int FindPrevious(T value, bool orEqual, IComparer<T> comparer, out int offset, out T result)

Searches for the largest element that is smaller than a reference element

• value — Reference element
• orEqual — If true, return the position of the value itself if it is found. If false, return the position of the closest value that is smaller.
• offset — Receive the offset within the level of the previous element, or 0 if not found
• result — Receive the value of the previous element, or default(T) if not found

Returns: Level of the previous element, or -1 if result was already the smallest

GetIterator

Iterator GetIterator()

Returns a new iterator that can access the contents of this store

GetReference

T GetReference(int arrayIndex)

Returns the value stored at a specific location in the array

• arrayIndex — Absolute index in the vector-array

Returns: Value stored at this location, or default(T) if the level is not allocated

T GetReference(int level, int offset)

Returns the value at a specific location in the array

• level — Index of the level (0-based)
• offset — Offset in the level (0-based)

Returns: Returns a reference to the value at this location, or null if not found

Insert

void Insert(T value)

Inserts a new element in the set, and returns its index.

• value — Value to insert. Warning: if the value already exists, the store will be corrupted !

The index is the absolute index, as if all the levels where a single, contiguous, array (0 = root, 7 = first element of level 3)

InsertItems

void InsertItems(T first, T second)

Inserts two elements in the set.

void InsertItems(List<T> values, bool ordered = false)

Inserts one or more new elements in the set.

• values — Array of elements to insert. Warning: if a value already exist, the store will be corrupted !
• ordered — If true, the entries in values are guaranteed to already be sorted (using the store default comparer).

The best performances are achieved when inserting a number of items that is a power of 2. The worst performances are when doubling the size of a store that is full. Warning: if is true but is not sorted, or is sorted using a different comparer, then the store will become corrupted !

IsFree

bool IsFree(int level)

Checks if a level is currently not allocated

• level — Index of the level (0-based)

Returns: true is the level is unallocated and does not store any elements; otherwise, false.

Max

T Max()

Find the largest element in the store

Returns: Largest element found, or default(T) if the store is empty

Min

T Min()

Find the smallest element in the store

Returns: Smallest element found, or default(T) if the store is empty

RemoveAt

T RemoveAt(int arrayIndex)

Removes the value at the specified location

• arrayIndex — Absolute index in the vector-array

Returns: Value that was removed

T RemoveAt(int level, int offset)

Removes the value at the specified location

• level — Index of the level (0-based)
• offset — Offset in the level (0-based)

Returns: Value that was removed

RemoveItem

bool RemoveItem(T item)

Removes the specified item

RemoveItems

int RemoveItems(ReadOnlySpan<T> items)

Removes one or more items

int RemoveItems(IEnumerable<T> items)

Removes one or more items

SetOrAdd

bool SetOrAdd(T value, bool overwriteExistingValue = false)

Adds a value to the array

• value — Value to add to the array
• overwriteExistingValue — If value already exists in the array and overwriteExistingValue is true, it will be overwritten with value.

Returns: trueif the value was added to the array, or false if it was already there.

Setting overwriteExistingValue to true only makes sense for ValueTypes where the caller wants to update the existing entry with an update value, that has the same logical key value!

TryCopyTo

bool TryCopyTo(Span<T> destination)

Copies the contents of this store into destination span.

• destination — The span to copy items into.

Returns: true if the buffer was large enough; otherwise, false.

TryGetBounds

bool TryGetBounds(out T min, out T max)

Returns the smallest and largest element in the store

• min — Receives the value of the smallest element (or default(T) is the store is Empty)
• max — Receives the value of the largest element (or default(T) is the store is Empty)

If the store contains only one element, then min and max will be equal