Bodu.Collections.Generic Namespace

Packages: Bodu.Collections 1.0.0

Bodu.Core 1.0.1

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, day-of-week patterns, 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

Bodu.Collections introduction - namespaces, headline types, scenarios.
Bodu.Collections getting started - install and minimal samples for the headline types.
Core Foundations guides - recipe-style walk-throughs: choosing a collection, circular buffer, deque, evicting dictionary, sequenced dictionary, indexed priority queue, indexed and ordered sets, multiset, multi-value dictionary, bidirectional dictionary, layered and defaulting dictionaries, table, navigable set, navigable dictionary, bit set, range-keyed lookups, interval tree, segmented buffer, concurrent collections, WeekPattern.

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

EvictingDictionary<TKey, TValue> - a fixed-capacity dictionary that evicts entries automatically when it fills up, under a policy of your choice.
EvictingDictionaryPolicy - the policy enum: FirstInFirstOut, LeastRecentlyUsed, LeastFrequentlyUsed, MostRecentlyUsed, RandomReplacement, SecondChance.
EvictingDictionaryExpiration, EvictingDictionaryExpirationKind - optional time-to-live expiry layered on the capacity bound: Absolute (from insertion) or Sliding (reset on access).

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

BiDictionary<TKey, TValue> - bidirectional one-to-one map with O(1) lookup in both directions and a live Inverse view; BiDictionaryDuplicateValuePolicy (Throw / Replace) decides what a duplicate value does. See the bidirectional dictionary guide.
LayeredDictionary<TKey, TValue>, DefaultingDictionary<TKey, TValue> - a read-through view over an ordered list of dictionaries (Python ChainMap shape) and a dictionary whose indexer materializes a factory-supplied default for a missing key (Python defaultdict shape). See the layered and defaulting dictionaries guide.
Table<TRow, TColumn, TValue> - two-key row / column map (Guava Table shape) with live Row / Column projections over a row-major store. See the table guide.

Sets, multisets, range-keyed collections

IndexedSet<T>, OrderedSet<T>, IndexedPriorityQueue<TElement, TPriority> - index-aware set and priority-queue variants for lookup-by-position and key-based priority updates.
NavigableSet<T> - comparer-ordered set over the same order-statistic red-black tree: O(log n) TryGetFloor / TryGetCeiling / TryGetHigher / TryGetLower, rank / select, CountInRange, and live Ascending / Descending / Range views. See the navigable set guide.
MultiValueDictionary<TKey, TValue>, Multiset<T> - multi-map and multi-set semantics over IEqualityComparer<TKey>; MultiValueBacking (List / Set) chooses whether each key's values are an ordered list or a de-duplicated set.
Range<T>, RangeDictionary<TKey, TValue>, RangeSet<T>, ValueRange<TKey, TValue> - range-keyed lookups for ordered or interval-valued keys (non-overlapping ranges).
IntervalTree<T>, IntervalTree<TKey, TValue> - overlap-storing interval trees over a max-endpoint augmented red-black tree: O(log n + k) stabbing (QueryPoint) and window (QueryOverlaps) queries over closed intervals that may freely overlap. See the interval tree guide.

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 - WeekPattern (day-of-week bitmask), 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. Allocation happens once, up front, not incrementally - this is a deliberate choice for predictable memory behavior in long-running services.
Eviction policies differ in cost. FirstInFirstOut and RandomReplacement are O(1); 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 snapshot-stable 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-neighbour ( 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-neighbour (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.

Table of Contents