Bodu.Collections.Generic Namespace
- Packages
-
Bodu.Collections 1.3.0Bodu.Core 1.3.0
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
- 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,
DayOfWeekSet, calendar value sets.
Key types
Ring-backed collections
- CircularBuffer<T> - a fixed-capacity FIFO collection. With
allowOverwrite: trueit silently drops the oldest element when full; withallowOverwrite: falseit 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.Concurrentpackage). - 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>andDeque<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) orSliding(reset on access).
Ordered dictionaries
- SequencedDictionary<TKey, TValue> - an unbounded dictionary that preserves a stable encounter order (Java
LinkedHashMapshape), 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 liveAscending/Descending/Rangeviews. 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
Inverseview; 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
ChainMapshape) and a dictionary whose indexer materializes a factory-supplied default for a missing key (Pythondefaultdictshape). See the layered and defaulting dictionaries guide. - Table<TRow, TColumn, TValue> - two-key row / column map (Guava
Tableshape) with liveRow/Columnprojections 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 liveAscending/Descending/Rangeviews. 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 inBodu.Collectionsalongside this namespace and needs only a secondusing.
Related namespaces (these ship in the Bodu.Core package, which Bodu.Collections depends on)
- Bodu -
DayOfWeekSetand the other calendar value sets,IRandomGenerator/XorShiftRandom, andThrowHelpercentralized argument validation. - Bodu.Buffers -
PooledBufferBuilder<T>forArrayPool<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 -
SequenceGeneratorlazy sequence factories (Range,NextWhile,Factory) and named mathematical series (Fibonacci, Farey, Leibniz, look-and-say, Thue-Morse). - Bodu.Text -
EncodingDetection,EncodingExtensions, andStringEncodingExtensions: BOM detection and span / UTF-8 / pooled-buffer helpers overSystem.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>, andEvictingDictionary<TKey, TValue>are not thread-safe; external synchronization is required if accessed concurrently. For a concurrent FIFO, use ConcurrentCircularBuffer<T> from the companionBodu.Collections.Concurrentpackage, which is designed for multi-producer / multi-consumer scenarios under the Vyukov algorithm. - Capacity is fixed. Both
CircularBuffer<T>andEvictingDictionary<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.
FirstInFirstOutis O(1);RandomReplacementkeeps no per-access metadata, but each eviction walks the keys to a random position, O(n) in the entry count;LeastRecentlyUsedandMostRecentlyUsedmaintain a linked recency list and are O(1) per access;LeastFrequentlyUsedandSecondChancecarry 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
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.