generic

generic is a small, focused Go module that fills a gap left by the standard library: a set of common data structures implemented with real type parameters instead of interface{} and type assertions. It packages an AVL tree, B-tree, bimap, LRU cache, copy-on-write hashmap and hashset, binary heap, interval tree, doubly-linked list, multimap, rope and persistent rope, stack, ternary search trie, and unrolled linked list as independent subpackages, each importable on its own.

Because every structure is generic over comparable or any type parameters, callers get compile-time type safety and avoid the runtime overhead of boxing values into interface{}. The root generic package also exposes small shared building blocks — EqualsFn, LessFn, HashFn, Compare, Max/Min/Clamp, and FNV-1a-based hash helpers — that the subpackages (and callers’ own code) build on, so there’s no need to hand-roll comparator or hashing plumbing for custom key types.

What You Get

• A copy-on-write hashmap and hashset using linear probing, cheap to clone via lazy copy-on-write semantics
• Tree structures: an AVL tree, a B-tree, and an augmented interval tree built on the AVL tree
• A bimap for bidirectional key/value lookups and a multimap for one-to-many associations
• A size-bounded cache that evicts entries with LRU once it reaches capacity
• Sequence structures: doubly-linked list, FIFO queue, LIFO stack, unrolled linked list (ulist), and a 2D array2d
• A rope and a persistent prope (versioned rope) for efficient insertion/deletion anywhere in a large generic sequence
• A ternary search trie and a plain mapset built on Go’s built-in map
• Shared root-level helpers — EqualsFn/LessFn/HashFn types, Compare, Max/Min/Clamp, and integer/string hash functions

Common Use Cases

• Swapping out ad-hoc map[K]interface{} code for a type-safe generic hashmap or hashset without writing per-type wrappers
• Using the LRU cache package to bound memory for an in-process cache of computed or fetched values
• Using the interval tree to answer overlap/containment queries over ranges (scheduling, genomic intervals, viewport culling)
• Building a text editor or collaborative-document backend on the rope/prope types for efficient mid-sequence edits
• Using the bimap or multimap where a plain map’s one-directional, one-value-per-key model doesn’t fit

Under The Hood

Architecture generic is organized as a root package (generic.go) supplying a handful of shared function types (EqualsFn, LessFn, HashFn) and small generic helpers (Compare, Max/Min/Clamp, integer/string hashing via FNV-1a), with every data structure implemented as its own independent subpackage (hashmap, btree, avl, interval, rope, trie, and so on). There is no central registry or shared base type — each subpackage depends only on the root package for its comparator/hash function types, so consumers import exactly the structures they need. The interval tree is a clear example of composition within the library: it is implemented as an augmented AVL tree rather than a separate self-balancing structure, reusing the AVL package’s balancing logic. Because each subpackage is self-contained with its own tests and README, removing or changing one structure has effectively no blast radius on the others — the coupling that exists is one-directional, from subpackages down to the shared root helpers.

Tech Stack The module targets Go 1.18, the first generics-enabled Go release, and its go.mod declares exactly two external dependencies: github.com/segmentio/fasthash for FNV-1a hashing and golang.org/x/exp/constraints for the Ordered type-constraint used by comparison helpers before cmp.Ordered existed in the standard library. There is no build system beyond a small Makefile (used for running gomarkdoc to regenerate DOC.md) and the standard go test/go build toolchain — no code generation, no external service integrations, and no runtime dependencies beyond the two listed.

Code Quality Each subpackage carries its own _test.go file (23 test files across the module), following Go’s standard testing package conventions with table-style test cases rather than a third-party assertion library. Reading the hashmap and btree implementations shows consistent naming (exported Map/Node/Tree types, lowercase unexported helpers), doc comments on every exported function and type, and explicit error-free APIs — operations like Get return a (value, bool) pair instead of panicking or swallowing a missing-key case. There is no linter configuration or CI-enforced static analysis visible beyond a GitHub Actions test workflow (referenced by the README’s badge), and no fuzzing despite the README explicitly inviting contributions to add it — so coverage depth beyond the existing table tests is unverified.

API Design The public surface favors small, composable constructors (New, NewFrom) that take explicit EqualsFn/LessFn/HashFn arguments for custom key types, avoiding hidden reflection-based comparisons. This is consistent across every subpackage, so once a caller learns the pattern in one structure (say hashmap.New), it transfers directly to avl, btree, and the others. The tradeoff is some boilerplate at call sites for non-comparable/non-constraints.Ordered key types, which must supply their own comparator functions rather than relying on operator overloading. Documentation is thorough at the function level (DOC.md is fully generated via gomarkdoc and mirrors every exported symbol) but there are few end-to-end usage examples beyond each subpackage’s own short README, so getting started requires reading the generated docs rather than a guided walkthrough.