generic

README

Generic Data Structures

This package implements some generic data structures.

• array2d: a 2-dimensional array.
• avl: an AVL tree.
• bimap: a bi-directional map; a map that allows lookups on both keys and values.
• 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.
• heap: a binary heap.
• interval: an interval tree, implemented as an augmented AVL tree.
• list: a doubly-linked list.
• 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.
• queue: a First In First Out (FIFO) queue.
• 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.

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).

Documentation

Index

• func Clamp[T constraints.Ordered](x, lo, hi T) T
• func ClampFunc[T any](x, lo, hi T, less LessFn[T]) T
• 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 HashString(s string) uint64
• func HashUint64(u uint64) 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

Examples

• Clamp
• ClampFunc
• Max
• MaxFunc
• Min
• MinFunc

Functions

func Clamp

func Clamp[T constraints.Ordered](x, lo, hi T) T

Clamp returns x constrained within [lo:hi] range. If x compares less than lo, returns lo; otherwise if hi compares less than x, returns hi; otherwise returns v.

Example

package main

import (
	"fmt"
	"time"

	"github.com/fufuok/utils/generic"
)

func main() {
	fmt.Println(generic.Clamp(500, 400, 600))
	fmt.Println(generic.Clamp(200, 400, 600))
	fmt.Println(generic.Clamp(800, 400, 600))

	fmt.Println(generic.Clamp(5*time.Second, 4*time.Second, 6*time.Second).Milliseconds())
	fmt.Println(generic.Clamp(2*time.Second, 4*time.Second, 6*time.Second).Milliseconds())
	fmt.Println(generic.Clamp(8*time.Second, 4*time.Second, 6*time.Second).Milliseconds())

	fmt.Println(generic.Clamp(1.5, 1.4, 1.8))
	fmt.Println(generic.Clamp(1.5, 1.8, 1.8))
	fmt.Println(generic.Clamp(1.5, 2.1, 1.9))

}

Output:

500
400
600
5000
4000
6000
1.5
1.8
2.1

func ClampFunc

func ClampFunc[T any](x, lo, hi T, less LessFn[T]) T

ClampFunc returns x constrained within [lo:hi] range using the less func. If x compares less than lo, returns lo; otherwise if hi compares less than x, returns hi; otherwise returns v.

Example

package main

import (
	"fmt"
	"math"

	"github.com/fufuok/utils/generic"
)

func lessMagnitude(a, b float64) bool {
	return math.Abs(a) < math.Abs(b)
}

func main() {
	fmt.Println(generic.ClampFunc(1.5, 1.4, 1.8, lessMagnitude))
	fmt.Println(generic.ClampFunc(1.5, 1.8, 1.8, lessMagnitude))
	fmt.Println(generic.ClampFunc(1.5, 2.1, 1.9, lessMagnitude))
	fmt.Println(generic.ClampFunc(-1.5, -1.4, -1.8, lessMagnitude))
	fmt.Println(generic.ClampFunc(-1.5, -1.8, -1.8, lessMagnitude))
	fmt.Println(generic.ClampFunc(-1.5, -2.1, -1.9, lessMagnitude))
	fmt.Println(generic.ClampFunc(1.5, -1.5, -1.5, lessMagnitude))

}

Output:

1.5
1.8
2.1
-1.5
-1.8
-2.1
1.5

func Compare

func Compare[T any](a, b T, less LessFn[T]) int

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 HashBytes

func HashBytes(b []byte) uint64

func HashInt

func HashInt(i int) uint64

func HashString

func HashString(s string) uint64

func HashUint64

func HashUint64(u uint64) uint64

func Less

func Less[T constraints.Ordered](a, b T) bool

Less wraps the '<' operator for ordered types.

func Max

func Max[T constraints.Ordered](a, b T) T

Max returns the max of a and b.

Example

package main

import (
	"fmt"
	"time"

	"github.com/fufuok/utils/generic"
)

func main() {
	fmt.Println(generic.Max(7, 3))
	fmt.Println(generic.Max(2*time.Second, 3*time.Second).Milliseconds())
}

Output:

7
3000

func MaxFunc

func MaxFunc[T any](a, b T, less LessFn[T]) T

MaxFunc returns the max of a and b using the less func.

Example

package main

import (
	"fmt"
	"math"

	"github.com/fufuok/utils/generic"
)

func lessMagnitude(a, b float64) bool {
	return math.Abs(a) < math.Abs(b)
}

func main() {
	fmt.Println(generic.MaxFunc(2.5, -3.1, lessMagnitude))
}

Output:

-3.1

func Min

func Min[T constraints.Ordered](a, b T) T

Min returns the min of a and b.

Example

package main

import (
	"fmt"
	"time"

	"github.com/fufuok/utils/generic"
)

func main() {
	fmt.Println(generic.Min(7, 3))
	fmt.Println(generic.Min(2*time.Second, 3*time.Second).Milliseconds())
}

Output:

3
2000

func MinFunc

func MinFunc[T any](a, b T, less LessFn[T]) T

MinFunc returns the min of a and b using the less func.

Example

package main

import (
	"fmt"
	"math"

	"github.com/fufuok/utils/generic"
)

func lessMagnitude(a, b float64) bool {
	return math.Abs(a) < math.Abs(b)
}

func main() {
	fmt.Println(generic.MinFunc(2.5, -3.1, lessMagnitude))
}

Output:

2.5

Types

type EqualsFn

type EqualsFn[T any] func(a, b T) bool

EqualsFn is a function that returns whether 'a' and 'b' are equal.

type HashFn

type HashFn[T any] func(t T) uint64

HashFn is a function that returns the hash of 't'.

type LessFn

type LessFn[T any] func(a, b T) bool

LessFn is a function that returns whether 'a' is less than 'b'.