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.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.
Documentation
¶
Index ¶
- func Compare[T any](a, b T, less LessFn[T]) int
- func Equals[T comparable](a, b T) bool
- func HashBytes(b []byte) uint64
- func HashInt(i int) uint64
- func HashInt16(i int16) uint64
- func HashInt32(i int32) uint64
- func HashInt64(i int64) uint64
- func HashInt8(i int8) uint64
- func HashString(s string) uint64
- func HashUint(i uint) uint64
- func HashUint16(u uint16) uint64
- func HashUint32(u uint32) uint64
- func HashUint64(u uint64) uint64
- func HashUint8(u uint8) uint64
- func Less[T constraints.Ordered](a, b T) bool
- func Max[T constraints.Ordered](a, b T) T
- func MaxFunc[T any](a, b T, less LessFn[T]) T
- func Min[T constraints.Ordered](a, b T) T
- func MinFunc[T any](a, b T, less LessFn[T]) T
- type EqualsFn
- type HashFn
- type LessFn
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Compare ¶
Compare uses a less function to determine the ordering of 'a' and 'b'. It returns:
* -1 if a < b
* 1 if a > b
* 0 if a == b
func Equals ¶
func Equals[T comparable](a, b T) bool
Equals wraps the '==' operator for comparable types.
func HashString ¶
func HashUint16 ¶
func HashUint32 ¶
func HashUint64 ¶
func Less ¶
func Less[T constraints.Ordered](a, b T) bool
Less wraps the '<' operator for ordered types.
Types ¶
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
Package avl provides an implementation of an AVL tree.
|
Package avl provides an implementation of an AVL tree. |
|
Package btree provides an implementation of a B-tree.
|
Package btree provides an implementation of a B-tree. |
|
Package cache provides an implementation of a key-value store with a maximum size.
|
Package cache provides an implementation of a key-value store with a maximum size. |
|
Package hashmap provides an implementation of a hashmap.
|
Package hashmap provides an implementation of a hashmap. |
|
Package hashset provides an implementation of a hashset.
|
Package hashset provides an implementation of a hashset. |
|
Package interval provides an implementation of an interval tree built using an augmented AVL tree.
|
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 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 mapset provides an implementation of a set using the built-in map. |
|
Package queue provides an implementation of a First In First Out (FIFO) queue.
|
Package queue provides an implementation of a First In First Out (FIFO) queue. |
|
Package rope provides an implementation of a rope data structure.
|
Package rope provides an implementation of a rope data structure. |
|
Package stack provides an implementation of a LIFO stack built using a resizing array.
|
Package stack provides an implementation of a LIFO stack built using a resizing array. |
|
Package trie provides an implementation of a ternary search trie.
|
Package trie provides an implementation of a ternary search trie. |