generic

package module
v1.2.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 12, 2023 License: MIT Imports: 2 Imported by: 20

README

Generic Data Structures

Go Reference MIT License

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

Documentation

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func Clamp added in v1.0.0 

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/zyedidia/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 added in v1.0.0 

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/zyedidia/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 HashInt16 

func HashInt16(i int16) uint64

func HashInt32 

func HashInt32(i int32) uint64

func HashInt64 

func HashInt64(i int64) uint64

func HashInt8 

func HashInt8(i int8) uint64

func HashString 

func HashString(s string) uint64

func HashUint 

func HashUint(i uint) uint64

func HashUint16 

func HashUint16(u uint16) uint64

func HashUint32 

func HashUint32(u uint32) uint64

func HashUint64 

func HashUint64(u uint64) uint64

func HashUint8 

func HashUint8(u uint8) 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/zyedidia/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/zyedidia/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/zyedidia/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/zyedidia/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'.

Source Files

View all Source files

Directories

Path Synopsis
Package avl provides an implementation of an AVL tree.
 Package avl provides an implementation of an AVL tree.
Package bimap provides an implementation of a bi-directional map.
 Package bimap provides an implementation of a bi-directional map.
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 heap provides an implementation of a binary heap.
 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 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 multimap provides an associative container that permits multiple entries with the same key.
 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 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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.