typ

README

go-typ

Generic types and functions that are missing from Go, including sets, trees, linked lists, etc.

All code is implemented with 0 dependencies and in pure Go code (no CGo).

Background

Go v1.18 is about to be released now in February 2022, and with it comes some features that has been talked about for a really long time. One of which being generics! (Go 1.18 beta release notes)

They have moved generics from the Go v2.0 milestone over to Go v1.18, which means they have to stay backwards compatible and cannot alter any existing types. On top of this, they do not seem to plan on releasing any generic data types in the Go standard library until Go v1.19. All in all, to use generic data types with Go v1.18, you'll have to either write your own, or use a third-party package, like this one :)

This repository includes those generic functions and types that I find are missing from the release of Go v1.18-beta1, as well as a number of other data structures and utility functions I think should've been included in the standard library a long time ago. But now with generics, we can finally have sensible implementations of sets, trees, stacks, etc without excessive casting.

Compatibility

Requires Go v1.18rc1 or later as the code makes heavy use of generics.

Installation and usage

go get -u gopkg.in/typ.v4

import (
	"fmt"

	"gopkg.in/typ.v4/avl"
	"gopkg.in/typ.v4/maps"
)

func UsingSets() {
	set1 := make(maps.Set[string])
	set1.Add("A")
	set1.Add("B")
	set1.Add("C")
	fmt.Println("set1:", set1) // {A B C}

	set2 := make(maps.Set[string])
	set2.Add("B")
	set2.Add("C")
	set2.Add("D")
	fmt.Println("set2:", set2) // {B C D}

	fmt.Println("union:", set1.Union(set2))         // {A B C D}
	fmt.Println("intersect:", set1.Intersect(set2)) // {B C}
	fmt.Println("set diff:", set1.SetDiff(set2))    // {A}
	fmt.Println("sym diff:", set1.SymDiff(set2))    // {A D}
}

func UsingAVLTree() {
	tree := avl.NewOrdered[string]()

	// Unordered input
	tree.Add("E")
	tree.Add("B")
	tree.Add("D")
	tree.Add("C")
	tree.Add("A")

	// Sorted output
	fmt.Println(tree.Len(), tree) // 5 [A B C D E]
}

Features

• gopkg.in/typ.v4/arrays:

  • arrays.Array2D[T]: 2-dimensional array.

• gopkg.in/typ.v4/sync2:

  • sync2.AtomicValue[T]: Atomic value store, wrapper around sync/atomic.Value.
  • sync2.KeyedMutex[T]: Mutual exclusive lock on a per-key basis.
  • sync2.KeyedRWMutex[T]: Mutual exclusive reader/writer lock on a per-key basis.
  • sync2.Map[K,V]: Concurrent map, forked from sync.Map.
  • sync2.Set[V]: Concurrent set, based on sync2.Map.
  • sync2.Once1[R1]: Run action once, and tracks return values, wrapper around sync.Once.
  • sync2.Once2[R1,R2]: Run action once, and tracks return values, wrapper around sync.Once.
  • sync2.Once3[R1,R2,R3]: Run action once, and tracks return values, wrapper around sync.Once.
  • sync2.Pool[T]: Object pool, wrapper around sync.Pool.

• gopkg.in/typ.v4/lists:

  • lists.List[T]: Linked list, forked from container/list.
  • lists.Queue[T]: First-in-first-out collection.
  • lists.Ring[T]: Circular list, forked from container/ring.
  • lists.Stack[T]: First-in-last-out collection.

• gopkg.in/typ.v4/avl:

  • avl.Tree[T]: AVL-tree (auto-balancing binary search tree) implementation.

• gopkg.in/typ.v4/chans:

  • chans.PubSub[T]: Publish-subscribe pattern using channels.

• gopkg.in/typ.v4/maps:

  • maps.Bimap[K,V]: Bi-directional map.
  • maps.Set[V]: Set of distinct values, based on set theory.

• gopkg.in/typ.v4/sets:

  • sets.Set[T]: Generic set interface, implemented by sync2.Set and maps.Set

• gopkg.in/typ.v4/slices:

  • slices.Sorted[T]: Always-sorted slice. Requires custom less function.

Explanation:

• Forked type: Copied their code and modified it so it uses generic types down to the backing struct layer. This benefits the most from generics support.

• Wrapped type: Code depends on the underlying non-generic type, and adds abstraction to hide the type casting. Less performant than full generic support, but is done to reduce excessive complexity in this repository.

• Neither forked nor wrapped: Original code written by yours truly.

Development

Please read the CONTRIBUTING.md for information about development environment and guidelines.

Similar projects

All the below include multiple data structure implementations each, all with Go 1.18 generics support.

• https://github.com/zyedidia/generic: An experimental collection of generic data structures written in Go.

• https://github.com/marstr/collection: Generic Golang implementation of a few basic data structures.

• https://github.com/Kytabyte/go2-generic-containers: Some container data structures written in the next generation of Golang with generics.

• https://github.com/tomyl/collection: Generic data structures for Go.

• https://github.com/gabstv/container: Generic data structures now that Go 1.18+ supports generics.

• https://github.com/go-generics/collections: Go generic collections

• https://github.com/golang-design/go2generics: 🧪 A chunk of experiments and demos about Go 2 generics design (type parameter & type set)

Official Go packages:

• golang.org/x/exp/constraints: Constraints that are useful for generic code, such as constraints.Ordered.

• golang.org/x/exp/maps: A collection of generic functions that operate on slices of any element type.

• golang.org/x/exp/slices: A collection of generic functions that operate on maps of any key or element type.

License

This project is primarily licensed under the MIT license:

• My Go code in this project is licensed under the MIT license: LICENSES/MIT.txt

• Some Go code in this project is forked from Go's source code, which is licensed under the 3-Clause BSD license: LICENSES/BSD-3-Clause.txt

• Documentation is licensed under the Creative Commons Attribution 4.0 International (CC-BY-4.0) license: LICENSES

• Miscellanious files are licensed under the Creative Commons Zero Universal license (CC0-1.0): LICENSES

• GitHub Action for REUSE linting (and not any of go-typ's code) is licensed under GNU General Public License 3.0 or later (GPL-3.0-or-later): LICENSES/GPL-3.0-or-later.txt

Copyright © Kalle Fagerberg

Documentation

Overview

Package typ includes generic types that are missing from the Go standard library. This includes types for sets, sorted slices, trees, etc.

Index

• func Abs[T Real](v T) T
• func Clamp[T Ordered](v, min, max T) T
• func Clamp01[T Real](v T) T
• func Coal[T comparable](values ...T) T
• func Compare[T Ordered](a, b T) int
• func CompareFuncFromComparable[T comparable](less func(a, b T) bool) func(a, b T) int
• func CompareFuncFromKey[T any, K Ordered](key func(a T) K) func(a, b T) int
• func CompareFuncFromLess[T any](less func(a, b T) bool) func(a, b T) int
• func DerefZero[P ~*V, V any](ptr P) V
• func Digits10[T Integer](v T) int
• func DigitsSign10[T Integer](v T) int
• func Equal[T comparable](a, b T) bool
• func IsNil[T any](value T) bool
• func IsZero[T comparable](value T) bool
• func Less[T Ordered](a, b T) bool
• func Max[T Ordered](v ...T) T
• func Min[T Ordered](v ...T) T
• func Product[T Number](v ...T) T
• func Ref[T any](value T) *T
• func Sum[T Number](v ...T) T
• func Tern[T any](cond bool, ifTrue, ifFalse T) T
• func TernCast[T any](cond bool, value any, ifFalse T) T
• func Zero[T any]() T
• func ZeroOf[T any](T) T
• type Complex
• type Float
• type Integer
• type Number
• type Ordered
• type Real
• type Signed
• type Unsigned

Examples

• Coal
• Tern

Functions

func Abs

func Abs[T Real](v T) T

Abs returns the absolute value of a number, in other words removing the sign, in other words (again) changing negative numbers to positive and leaving positive numbers as-is.

Abs(0)   // => 0
Abs(15)  // => 15
Abs(-15) // => 15

func Clamp

func Clamp[T Ordered](v, min, max T) T

Clamp returns the value clamped between the minimum and maximum values.

func Clamp01

func Clamp01[T Real](v T) T

Clamp01 returns the value clamped between 0 (zero) and 1 (one).

func Coal

func Coal[T comparable](values ...T) T

Coal will return the first non-zero value. Equivalent to the "null coalescing" operator from other languages, or the SQL "COALESCE(...)" expression.

var result = null ?? myDefaultValue;       // C#, JavaScript, PHP, etc
var result = typ.Coal(nil, myDefaultValue) // Go

Example

bindAddressFromUser := ""
bindAddressDefault := "localhost:8080"

fmt.Println("Adress 1:", typ.Coal(bindAddressFromUser, bindAddressDefault))

bindAddressFromUser = "192.168.1.10:80"
fmt.Println("Adress 2:", typ.Coal(bindAddressFromUser, bindAddressDefault))

Output:

Adress 1: localhost:8080
Adress 2: 192.168.1.10:80

func Compare

func Compare[T Ordered](a, b T) int

Compare checks if either value is greater or equal to the other. The result will be 0 if a == b, -1 if a < b, and +1 if a > b.

func CompareFuncFromComparable

func CompareFuncFromComparable[T comparable](less func(a, b T) bool) func(a, b T) int

CompareFuncFromComparable returns a new function that can compare two objects by using the type's comparison operation.

func CompareFuncFromKey

func CompareFuncFromKey[T any, K Ordered](key func(a T) K) func(a, b T) int

CompareFuncFromKey returns a new function that can compare two objects by extracting some ordered key from the type.

func CompareFuncFromLess

func CompareFuncFromLess[T any](less func(a, b T) bool) func(a, b T) int

CompareFuncFromLess returns a new function that can compare two objects by flipping the less function.

func DerefZero

func DerefZero[P ~*V, V any](ptr P) V

DerefZero returns the dereferenced value, or zero if it was nil.

func Digits10

func Digits10[T Integer](v T) int

Digits10 returns the number of digits in the number as if it would be converted to a string in base 10. This is computed by comparing its value to all orders of 10, making it increadibly faster than calculating logaritms or by performing divisions.

func DigitsSign10

func DigitsSign10[T Integer](v T) int

DigitsSign10 returns the number of digits in the number as if it would be converted to a string in base 10, plus 1 if the number is negative to account for the negative sign. This is computed by comparing its value to all orders of 10, making it increadibly faster than calculating logaritms or by performing divisions.

func Equal

func Equal[T comparable](a, b T) bool

Equal returns true if the first argument is equal to the second.

func IsNil

func IsNil[T any](value T) bool

IsNil checks if the generic value is nil.

func IsZero

func IsZero[T comparable](value T) bool

IsZero returns true if the value is zero. If the type implements

IsZero() bool

then that method is also used.

func Less

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

Less returns true if the first argument is less than the second.

func Max

func Max[T Ordered](v ...T) T

Max returns the largest value.

func Min

func Min[T Ordered](v ...T) T

Min returns the smallest value.

func Product

func Product[T Number](v ...T) T

Product multiplies together all numbers from the arguments. Returns 1 if no arguments.

func Ref

func Ref[T any](value T) *T

Ref returns a pointer to the value. Useful when working with literals.

func Sum

func Sum[T Number](v ...T) T

Sum adds upp all numbers from the arguments. Returns 0 if no arguments.

func Tern

func Tern[T any](cond bool, ifTrue, ifFalse T) T

Tern returns different values depending on the given conditional boolean. Equivalent to the "ternary" operator from other languages.

var result = 1 > 2 ? "yes" : "no";        // C#, JavaScript, PHP, etc
var result = typ.Tern(1 > 2, "yes", "no") // Go

Example

age := 16
fmt.Println("To drink I want a glass of", typ.Tern(age >= 18, "wine", "milk"))

Output:

To drink I want a glass of milk

func TernCast

func TernCast[T any](cond bool, value any, ifFalse T) T

TernCast will cast the value if condition is true. Otherwise the last argument is returned.

func Zero

func Zero[T any]() T

Zero returns the zero value for a given type.

func ZeroOf

func ZeroOf[T any](T) T

ZeroOf returns the zero value for a given type. The first argument is unused, but using Go's type inference can be useful to create the zero value for an anonymous type without needing to declare the full type.

Types

type Complex

type Complex interface {
	~complex64 | ~complex128
}

Complex is a constraint that permits any complex numeric type. If future releases of Go add new predeclared complex numeric types, this constraint will be modified to include them.

type Float

type Float interface {
	~float32 | ~float64
}

Float is a constraint that permits any floating-point type. If future releases of Go add new predeclared floating-point types, this constraint will be modified to include them.

type Integer

type Integer interface {
	Signed | Unsigned
}

Integer is a constraint that permits any integer type. If future releases of Go add new predeclared integer types, this constraint will be modified to include them.

type Number

type Number interface {
	Integer | Float | Complex
}

Number is a type constraint for any Go numbers, including complex numbers.

type Ordered

type Ordered interface {
	Integer | Float | ~string
}

Ordered is a constraint that permits any ordered type: any type that supports the operators < <= >= >. If future releases of Go add new ordered types, this constraint will be modified to include them.

type Real

type Real interface {
	Integer | Float
}

Real is a type constraint for any real numbers. That being integers or floats.

type Signed

type Signed interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64
}

Signed is a constraint that permits any signed integer type. If future releases of Go add new predeclared signed integer types, this constraint will be modified to include them.

type Unsigned

type Unsigned interface {
	~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
}

Unsigned is a constraint that permits any unsigned integer type. If future releases of Go add new predeclared unsigned integer types, this constraint will be modified to include them.