Table of Contents

Bodu.Collections.Generic Namespace

Packages
Bodu.Core 1.3.0

Bodu.Collections.Generic

Purpose

Bodu.Collections.Generic is the headline namespace of the Bodu.Collections package (which depends on Bodu.Core): bounded, ordered, navigable, and range-keyed collections that behave predictably under memory pressure, with companions for pooled buffers, calendar value sets, encoding helpers, and argument validation in the adjacent Bodu.Core namespaces.

Reach for this library when you need a fixed-capacity FIFO queue, a deque with O(1) ends, a size-limited key/value cache with a real eviction policy (not just an ad-hoc Dictionary plus a bolted-on timer), a range-keyed lookup, or helpers that keep ceremony out of hot paths.

Static documentation

Key types

Ring-backed collections

  • CircularBuffer<T> - a fixed-capacity FIFO collection. With allowOverwrite: true it silently drops the oldest element when full; with allowOverwrite: false it throws on overflow.
  • ConcurrentCircularBuffer<T> - a lock-free multi-producer / multi-consumer circular buffer using the Vyukov MPMC algorithm, with the same overwrite semantics (ships in the companion Bodu.Collections.Concurrent package).
  • Deque<T> - double-ended queue with O(1) AddFirst / AddLast / RemoveFirst / RemoveLast; growable or fixed-capacity, with DequeOverflowPolicy (Reject / EvictOpposite) selecting what a full fixed-capacity deque does on overflow.
  • RingBackedCollection<T> - abstract base shared by CircularBuffer<T> and Deque<T> (extension point for new ring-backed collections).
  • SegmentedBuffer<T> - segmented backing buffer for streaming scenarios where the total length is not known up front.

Capacity-bounded dictionaries

Ordered dictionaries

  • SequencedDictionary<TKey, TValue> - an unbounded dictionary that preserves a stable encounter order (Java LinkedHashMap shape), with O(1) access to and removal of the first and last entries (First / Last / TryRemoveFirst / TryRemoveLast). Defaults to insertion order; an opt-in access-order mode moves an entry to the tail on read, the building block for a hand-rolled LRU.
  • NavigableDictionary<TKey, TValue> - key-sorted dictionary over an order-statistic red-black tree: O(log n) floor / ceiling / higher / lower entry queries, rank / select, CountInRange, and live Ascending / Descending / Range views. See the navigable dictionary guide.

Shaped dictionaries

Sets, multisets, range-keyed collections

Sibling namespace in the same package

  • Bodu.Collections.Specialized - the specialized structures that are not part of the general container catalogue: BitSet (packed bit set). It ships in Bodu.Collections alongside this namespace and needs only a second using.

Related namespaces (these ship in the Bodu.Core package, which Bodu.Collections depends on)

  • Bodu - DayOfWeekSet and the other calendar value sets, IRandomGenerator / XorShiftRandom, and ThrowHelper centralized argument validation.
  • Bodu.Buffers - PooledBufferBuilder<T> for ArrayPool<T>-backed zero-allocation building.
  • Bodu.Extensions - date / numeric / span / array extensions and the calendar-shape enums.
  • Bodu.Collections.Extensions, Bodu.Collections.Generic.Extensions - sequence-shaping helpers (recursive selection, sliding windows, batched enumeration, pluggable random shuffles).
  • Bodu.Sequences - SequenceGenerator lazy sequence factories (Range, NextWhile, Factory) and named mathematical series (Fibonacci, Farey, Leibniz, look-and-say, Thue-Morse).
  • Bodu.Text - EncodingDetection, EncodingExtensions, and StringEncodingExtensions: BOM detection and span / UTF-8 / pooled-buffer helpers over System.Text.Encoding.

Example

using Bodu.Collections.Generic;

// Bounded FIFO with overwrite: the four most recent samples win.
var recent = new CircularBuffer<double>(capacity: 4, allowOverwrite: true);
foreach (double sample in stream) recent.Enqueue(sample);

// LRU cache for expensive lookups.
var cache = new EvictingDictionary<string, User>(
    capacity: 1024,
    policy: EvictingDictionaryPolicy.LeastRecentlyUsed);

if (!cache.TryGetValue(id, out User user))
{
    user = Load(id);
    cache[id] = user; // oldest unused entry is evicted automatically when full.
}

Notes

  • Thread safety. CircularBuffer<T>, Deque<T>, and EvictingDictionary<TKey, TValue> are not thread-safe; external synchronization is required if accessed concurrently. For a concurrent FIFO, use ConcurrentCircularBuffer<T> from the companion Bodu.Collections.Concurrent package, which is designed for multi-producer / multi-consumer scenarios under the Vyukov algorithm.
  • Capacity is fixed. Both CircularBuffer<T> and EvictingDictionary<TKey, TValue> reject a non-positive capacity at construction time. CircularBuffer<T> allocates its backing array once, up front, and never grows it - a deliberate choice for predictable memory behavior in long-running services. EvictingDictionary<TKey, TValue> bounds its entry count but allocates per entry as it fills.
  • Eviction policies differ in cost. FirstInFirstOut is O(1); RandomReplacement keeps no per-access metadata, but each eviction walks the keys to a random position, O(n) in the entry count; LeastRecentlyUsed and MostRecentlyUsed maintain a linked recency list and are O(1) per access; LeastFrequentlyUsed and SecondChance carry a small bookkeeping overhead on access. Pick the policy that matches your workload rather than defaulting to LRU.
  • Enumeration is fail-fast for non-concurrent types - iterating while mutating throws, per the usual .NET contract.
  • See also: the circular buffer guide, the evicting dictionary guide, and the Bodu.Collections introduction for the full scenario table.

Namespaces

Bodu.Collections.Generic.Concurrent
Bodu.Collections.Generic.Extensions
Bodu.Collections.Generic.Graphs
Bodu.Collections.Generic.Trees

Classes

BiDictionary<TKey, TValue>

Represents a bidirectional one-to-one dictionary in which every key maps to exactly one value and every value maps back to exactly one key, providing O(1) lookup in both directions.

CircularBuffer<T>

Represents a fixed-size, first-in first-out (FIFO) circular buffer with optional overwrite-on-full semantics. Elements are inserted at the tail and removed from the head; once the buffer reaches Capacity, the AllowOverwrite property determines whether further inserts evict the oldest element or are rejected.

DefaultingDictionary<TKey, TValue>

Represents a dictionary whose indexer getter materializes missing entries on demand: reading an absent key invokes a value factory, stores the produced value, and returns it.

Deque<T>

Represents a double-ended queue (deque) backed by a contiguous circular array. Elements may be added or removed from either end in amortized O(1) time. The AllowGrow property selects between growable and fixed-capacity behavior at runtime.

EvictingDictionaryExpiration

Represents the immutable time-based expiration configuration for an EvictingDictionary<TKey, TValue>.

EvictingDictionary<TKey, TValue>

Represents a fixed-capacity dictionary that automatically removes entries based on a chosen eviction policy, such as First-In-First-Out (FirstInFirstOut), Least Recently Used (LeastRecentlyUsed), or Least Frequently Used (LeastFrequentlyUsed).

EvictingDictionary<TKey, TValue>.KeyCollection

Represents a live, order-preserving view of the keys contained in an EvictingDictionary<TKey, TValue>.

EvictingDictionary<TKey, TValue>.ValueCollection

Represents a live, order-preserving view of the values contained in an EvictingDictionary<TKey, TValue>.

IndexedPriorityQueue<TElement, TPriority>

Represents a binary min-heap priority queue keyed by element identity, supporting O(log n) re-prioritization (decrease- or increase-key) and removal of any element by value.

IndexedSet<T>

Represents an index-addressable unique list - an insertion-ordered collection of unique elements that exposes the full IList<T> contract.

IntervalTree<T>

Represents a collection of closed intervals [low, high] that may freely overlap, answering stabbing queries (QueryPoint(T) - all intervals containing a point) and overlap-window queries (QueryOverlaps(T, T) - all intervals intersecting a window) in O(log n + k).

IntervalTree<TKey, TValue>

Represents a collection of closed intervals [low, high] that may freely overlap, each carrying an associated value, answering stabbing queries (QueryPoint(TKey)) and overlap-window queries (QueryOverlaps(TKey, TKey)) in O(log n + k).

LayeredDictionary<TKey, TValue>

Represents a live, read-through view over an ordered list of underlying dictionaries in which the first layer containing a key supplies its value, and all writes are applied to the first layer only.

MultiValueDictionary<TKey, TValue>

Represents a mutable dictionary that maps each key to zero or more values.

Multiset<T>

Represents an unordered collection that tracks the multiplicity (occurrence count) of each element. Unlike HashSet<T>, duplicate elements are permitted; unlike List<T>, element counts are tracked as integers rather than stored as repeated entries.

NavigableDictionary<TKey, TValue>

Represents a key-sorted dictionary augmented with order statistics - an IDictionary<TKey, TValue> that keeps its entries in key comparer order and answers nearest-neighbor ( TryGetFloorEntry(TKey, out KeyValuePair<TKey, TValue>) / TryGetCeilingEntry(TKey, out KeyValuePair<TKey, TValue>) / TryGetHigherEntry(TKey, out KeyValuePair<TKey, TValue>) / TryGetLowerEntry(TKey, out KeyValuePair<TKey, TValue>)), rank/select ( IndexOfKey(TKey) / GetAt(int)), and range-counting queries in O(log n).

NavigableDictionary<TKey, TValue>.KeyCollection

Represents a live, ascending-key-ordered view of the keys contained in a NavigableDictionary<TKey, TValue>.

NavigableDictionary<TKey, TValue>.ValueCollection

Represents a live view of the values contained in a NavigableDictionary<TKey, TValue>, ordered by ascending key.

NavigableSet<T>

Represents a sorted set augmented with order statistics - an ISet<T> that keeps its elements in comparer order and answers nearest-neighbor (TryGetFloor(T, out T) / TryGetCeiling(T, out T) / TryGetHigher(T, out T) / TryGetLower(T, out T)), rank/select (IndexOf(T) / GetAt(int)), and range-counting queries in O(log n).

OrderedSet<T>

Represents an insertion-ordered set - a ISet<T> that preserves the order in which elements were first added and exposes that order through IReadOnlyList<T>.

RangeDictionary<TKey, TValue>

Represents a sorted dictionary that maps non-overlapping half-open ranges to values.

RangeSet<T>

Represents a sorted set of non-overlapping half-open ranges.

RingBackedCollection<T>

Provides the shared low-level mechanics for ring-buffer-backed collections - a contiguous backing array, head/tail indices with modulo wrap, a live element count, and a structural-version counter - as a reusable base type for CircularBuffer<T> and Deque<T>.

SegmentedBuffer<T>

Represents an append-only segmented buffer that grows efficiently by allocating fixed-size chunks (segments) of memory.

SequencedDictionary<TKey, TValue>

Represents a dictionary that preserves the order in which entries are added and provides O(1) access to and removal of the first and last entries, optionally re-ordering entries on access.

SequencedDictionary<TKey, TValue>.KeyCollection

Represents a live, order-preserving view of the keys contained in a SequencedDictionary<TKey, TValue>.

SequencedDictionary<TKey, TValue>.ValueCollection

Represents a live, order-preserving view of the values contained in a SequencedDictionary<TKey, TValue>.

ShuffleHelpers

Provides in-place and yield-based Fisher-Yates randomization over arrays, spans, memory regions, and arbitrary IEnumerable<T> sources.

Table<TRow, TColumn, TValue>

Represents a two-dimensional map that associates an ordered row/column key pair with a single value, exposing live row and column projections over a row-major backing store.

Structs

EvictingDictionary<TKey, TValue>.DictionaryEnumerator

Enumerates the elements of an EvictingDictionary<TKey, TValue>.

EvictingDictionary<TKey, TValue>.Enumerator

Enumerates the live entries of an EvictingDictionary<TKey, TValue> in policy order without allocating.

IndexedPriorityQueue<TElement, TPriority>.Enumerator

Enumerates the element-priority pairs of an IndexedPriorityQueue<TElement, TPriority> in heap-storage order.

IndexedSet<T>.Enumerator

Enumerates the elements of an IndexedSet<T> in insertion order without allocating.

IntervalTree<T>.Enumerator

Enumerates the intervals of an IntervalTree<T> in ascending (low, high) order without allocating, repeating duplicate intervals once per stored occurrence.

IntervalTree<TKey, TValue>.Enumerator

Enumerates the entries of an IntervalTree<TKey, TValue> in ascending (low, high) order without allocating, yielding an interval's values in insertion order.

MultiValueDictionary<TKey, TValue>.Enumerator

Enumerates the key-value-list pairs in a MultiValueDictionary<TKey, TValue>.

Multiset<T>.Enumerator

Enumerates the elements of a Multiset<T>, yielding each element as many times as its occurrence count in an unspecified order.

NavigableDictionary<TKey, TValue>.Enumerator

Enumerates the entries of a NavigableDictionary<TKey, TValue> in ascending key order without allocating.

NavigableSet<T>.Enumerator

Enumerates the elements of a NavigableSet<T> in ascending comparer order without allocating.

OrderedSet<T>.Enumerator

Enumerates the elements of an OrderedSet<T> in insertion order without allocating.

RangeDictionary<TKey, TValue>.Enumerator

Enumerates the entries of a RangeDictionary<TKey, TValue> in ascending start order without allocating.

RangeSet<T>.Enumerator

Enumerates the ranges of a RangeSet<T> in ascending start order without allocating.

Range<T>

Represents a half-open range, where StartInclusive is included and EndExclusive is excluded.

RingBackedCollection<T>.Enumerator

Enumerates the elements of a RingBackedCollection<T> in head-to-tail logical order.

SequencedDictionary<TKey, TValue>.DictionaryEnumerator

Enumerates the elements of a SequencedDictionary<TKey, TValue> as DictionaryEntry values.

SequencedDictionary<TKey, TValue>.Enumerator

Enumerates the entries of a SequencedDictionary<TKey, TValue> in iteration order without allocating.

ValueRange<TKey, TValue>

Represents a half-open range mapped to a value - the entry projection produced when enumerating a RangeDictionary<TKey, TValue>.

Enums

BiDictionaryDuplicateValuePolicy

Specifies how a BiDictionary<TKey, TValue> responds when an add or assignment operation supplies a value that is already bound to a different key.

DequeOverflowPolicy

Specifies how a fixed-capacity Deque<T> responds when an add operation is attempted while the deque is already full.

EvictingDictionaryExpirationKind

Specifies how an EvictingDictionary<TKey, TValue> measures an entry's time-to-live when expiration is configured through EvictingDictionaryExpiration.

EvictingDictionaryPolicy

Specifies the eviction strategy used by an EvictingDictionary<TKey, TValue> when its capacity is exceeded.

MultiValueBacking

Specifies how a MultiValueDictionary<TKey, TValue> stores the values associated with each key.