# README
Generic Data Structures
This package implements some generic data structures.
avl: an AVL tree.btree: a B-tree.cache: a wrapper aroundmap[K]Vthat 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.multimap: an associative container that permits multiple entries with the same key.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.heap: a binary heap.
See each subpackage for documentation and examples. The top-level generic
package provides some useful types and constraints. See DOC.md for
documentation.
Contributing
If you would like to contribute a new feature, please let me know first what you would like to add (via email or issue tracker). Here are some ideas:
- New data structures (bloom filters, graph structures, concurrent data structures, adaptive radix tree, or other kinds of search trees).
- Benchmarks, and optimization of the existing data structures based on those benchmarks. The hashmap is an especially good target.
- Design and implement a nice iterator API.
- Improving tests (perhaps we can use Go's new fuzzing capabilities).
# Packages
Package avl provides an implementation of an AVL tree.
Package bimap provides an implementation of a bi-directional map.
Package btree provides an implementation of a B-tree.
Package cache provides an implementation of a key-value store with a maximum size.
Package hashmap provides an implementation of a hashmap.
Package hashset provides an implementation of a hashset.
Package heap provides an implementation of a binary heap.
Package interval provides an implementation of an interval tree built using an augmented AVL tree.
Package list provides an implementation of a doubly-linked list with a front and back.
Package mapset provides an implementation of a set using the built-in map.
Package multimap provides an associative container that permits multiple entries with the same key.
Package queue provides an implementation of a First In First Out (FIFO) queue.
Package rope provides an implementation of a rope data structure.
No description provided by the author
Package stack provides an implementation of a LIFO stack built using a resizing array.
Package trie provides an implementation of a ternary search trie.
# Functions
Clamp returns x constrained within [lo:hi] range.
ClampFunc returns x constrained within [lo:hi] range using the less func.
Compare uses a less function to determine the ordering of 'a' and 'b'.
Equals wraps the '==' operator for comparable types.
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
No description provided by the author
Less wraps the '<' operator for ordered types.
Max returns the max of a and b.
MaxFunc returns the max of a and b using the less func.
Min returns the min of a and b.
MinFunc returns the min of a and b using the less func.