Generic Data Structures

This package implements some generic data structures.

• avl: an AVL tree.
• btree: a B-tree.
• cache: a wrapper around map[K]V that uses a maximum size and evicts elements using LRU when full.
• hashmap: a hashmap with linear probing. The main feature is that the hashmap can be efficiently copied, using copy-on-write under the hood.
• hashset: a hashset that uses the hashmap as the underlying storage.
• mapset: a set that uses Go's built-in map as the underlying storage.
• interval: an interval tree, implemented as an augmented AVL tree.
• list: a doubly-linked list.
• rope: a generic rope, which is similar to an array but supports efficient insertion and deletion from anywhere in the array. Ropes are typically used for arrays of bytes, but this rope is generic.
• stack: a LIFO stack.
• trie: a ternary search trie.
• queue: a First In First Out (FIFO) queue.

See each subpackage for documentation and examples. The top-level generic package provides some useful types and constraints. See DOC.md for documentation.

Contributing

There are more data structures that may be useful to have, such as bloom filters, graph representations, and more kinds of search trees. If you would like to contribute a data structure please let me know.

It would also be useful to have comprehensive benchmarks for the data structures, comparing to standard library implementations when possible, or just on their own. Benchmarks will also allow us to profile and optimize the implementations.