Bodu.Collections 1.3.0

Bodu.Collections

API stability - Stable. The public API surface is committed: breaking changes are reserved for a major-version bump per SemVer, except a deliberate break that is recorded in the release notes and in the package's CompatibilitySuppressions.xml. See versioning and support.

The specialized generic-collection catalogue for the Bodu solution and for general use on .NET 8 and .NET 10: bounded and ordered collections, bidirectional and layered dictionaries, navigable (order-statistic) sets and maps, interval and range-keyed lookups, graph and tree structures, and probabilistic sketches. The catalogue was split out of Bodu.Core with namespaces unchanged - code written against Bodu.Collections.Generic and its siblings keeps compiling; only the package reference changes. Most collections ship a struct enumerator for allocation-free iteration, and the collections implement the standard BCL interfaces (IEnumerable<T>, ICollection<T>, IReadOnlyCollection<T>, ISet<T>, IList<T>) so the types drop into existing code. The package references Bodu.Core for its shared ThrowHelper argument validation.

Installation

dotnet add package Bodu.Collections

Targets net8.0 and net10.0. Depends on Bodu.Core.

Collections

Graphs

The Bodu.Collections.Generic.Graphs namespace provides an adjacency-list Graph<T> (directed or undirected, optionally weighted), the static GraphAlgorithms catalogue (breadth-/depth-first traversal, Dijkstra shortest path, Kahn topological sort, connected components) over the read-only IReadOnlyGraph<T> / IReadOnlyWeightedGraph<TVertex> interfaces, and the element-keyed union-find structure DisjointSet<T>.

Trees and tries

The Bodu.Collections.Generic.Trees namespace provides Tree<T> (a mutable n-ary tree node with iterative, stack-safe traversals), the prefix trees Trie / Trie<TValue> (string set / string-keyed map with prefix queries), their path-compressed siblings RadixTrie / RadixTrie<TValue> (identical member-for-member surface over PATRICIA-style edges), and AhoCorasickAutomaton / AhoCorasickAutomaton<TValue> (immutable multi-pattern matchers that report every occurrence of every pattern in a single O(text + matches) pass).

Probabilistic collections

The Bodu.Collections.Probabilistic namespace ships three fixed-footprint approximate sketches, each with a one-sided, quantified error contract:

• BloomFilter<T> - approximate set membership with no false negatives; false positives approach the design rate as the fill approaches ExpectedItems.
• CountMinSketch<T> - approximate frequencies that never underestimate; overestimates by at most ε · TotalCount with probability ≥ 1 − δ.
• HyperLogLog<T> - approximate distinct counts with a relative standard error of about 1.04/√m for m = 2^precision one-byte registers.

All three hash through an IEqualityComparer<T>, merge with parameter-compatible instances, and round-trip their state through an opaque, version-checked export format. None is thread-safe.

The thread-safe variants (ConcurrentCircularBuffer<T>, ConcurrentHashSet<T>, ConcurrentEvictingDictionary<TKey,TValue>, and ConcurrentLruCache<TKey,TValue>) ship separately in the Bodu.Collections.Concurrent package.

Building and testing

To build this package from source and run its tests, see CONTRIBUTING.md.

License

MIT. © Bodu Pty. Ltd.