Typesafe Go Data Structures

Your brand-new Golang collections implementation with generics. Go version >= 1.18. If facing compiler issue, please upgrade to 1.19.

go get github.com/cuzfrog/tgods@<version>

Interfaces

Implementation\Interface	Stack	List	Queue	Deque	Set	Map	MultiMap	Graph
`arrayStack`	✔️
`circularArray`	✔️	✔️	✔️	✔️
`linkedList`	✔️	✔️	✔️	✔️
`binaryHeap`			✔️
`rbTree`					✔️	✔️
`hashTable`					✔️	✔️
`linkedHashTable`					✔️	✔️
`enumMap`						✔️
`enumSet`					✔️
`multiMap`						✔️	✔️
`treeAdjacencyList`								✔️

Top interface Collection contains general methods, sub-interfaces like ArrayList, SortedSet, SortedMap provide more rich functionalities. All interface definitions can be found: here

Data Structures:

arrayStack - fixed length first-in-last-out array based stack. Backing up Stack
circularArray - variable length/cap array with fast add/remove at head or tail and random access with index. Backing up Stack, ArrayList, Queue, Deque
linkedList - doubly linked list with fast add/remove. Backing up Stack, LinkedList, Queue, Deque
binaryHeap - binary heap based min or max priority queue. Backing up Queue
rbTree - recursion-free red black tree implementation. Backing up SortedSet, SortedMap
hashTable - variable length/cap array based hash table, hash collision is handled by linked nodes. Backing up Set, Map
linkedHashTable hashTable preserving inserting or configurable access order. Can serve as an LRU cache. Backing up LinkedSet, LinkedMap
enumMap & enumSet fast array based map and set with Integer as the key. Implementing SortedMap, SortedSet respectively.
multiMap multimap implementation with arrayListMultiMap and hashSetMultiMap constructors.
treeAdjacencyList a treeMap based graph implementation with directional edge properties. It has typical O(log(n)) time complexity for adding, searching, and removing vertices. Backing up Graph

Usage:

Rich Constructors:

import "github.com/cuzfrog/tgods/collections"

list := collections.NewLinkedListOf(1, 2, 3) // List[int]
list := collections.NewArrayListOf(1, 2, 3) // List[int]
queue := collections.NewLinkedListQueue[int]() // Queue[int]
queue := collections.NewArrayListQueue[int]() // Queue[int]
hashMap := collections.NewHashMapOf[string, int](funcs.NewStrHash(), funcs.ValueEqual[string]) // Map[string, int]
hashMap := collections.NewHashMapOfStrKey[int](EntryOf("Earth", 3), EntryOf("Mars", 4)) // Map[string, int]
cache := collections.NewLRUCacheOfStrKey[int](40, collections.PutOrder + collections.GetOrder) // LRU cache[string, int] of size limit 40
// more...

Client implementation of constraint interfaces to simplify collection creation:

type myStruct struct {...}
func (s *myStruct) Hash() uint {...}
func (s *myStruct) Equal(other *myStruct) bool {...}
hashSet := collections.NewHashSetC[*myStruct]()

Functional Transformation

import "github.com/cuzfrog/tgods/transform"

c := collections.NewArrayListOf(1, 3, 4)
l := collections.NewLinkedListOf[string]()
transform.MapTo[int, string](c, l, func(elem int) string { return fmt.Sprint(elem) }) // l ["1", "2", "3"]

listOfList := ... // List[List[int]] [[1, 3], [2, 4]]
list := NewArrayListOf[int]()
transform.FlattenTo[types.List[int], int](listOfList, list) // list [1, 3, 2, 4]

c := collections.NewArrayListOf(1, 3, 4)
transform.Reduce[int, string](c, "", func(acc string, next int) string { return acc + strconv.Itoa(next) }) // "134"

c := []int{1, 3, 4}
transform.CountSlice[int](c, func(elem int) bool {return elem > 2}) // 2, yeah for slices, also has Count for Collection
// more...

Built-in Utils & Functions:

import "github.com/cuzfrog/tgods/utils"
list := collections.NewArrayListOf(1, 3, 2) // ArrayList 1, 3, 2
list.Sort(funcs.ValueLess[int]) // ArrayList 1, 2, 3
utils.StringFrom(list) // [1, 2, 3]
utils.SliceFrom(list)  // []int{1, 2, 3}
m := // Map [1->"a", 2->"b"]
utils.KeysFrom(m) // [1, 2]

// functions:
import "github.com/cuzfrog/tgods/funcs"
funcs.NewStrHash() // func(s string) uint, create a string hash function based on 64bit or 32bit platform
funcs.ValueEqual // (a, b comparable) bool

// HOFs:
funcs.CompToEq // func(comp Compare[T]) Equal[T]
funcs.InverseComp // func(comp Compare[T]) Compare[T]

// more...

Semantic Iteration:

Iteration behavior is based on which interface type is constructed.

list := collections.NewLinkedListOf[int]() // interface List[int], implementation linkedList[int]
list.Add(1)
list.Add(2)
list.Add(3)
list.Each(func (i, v int) {fmt.Print(v)}) // 123

stack := collections.NewLinkedListStack[int]() // interface Stack[int], implementation linkedList[int]
stack.Push(1)
stack.Push(2)
stack.Push(3)
stack.Each(func (i, v int) {fmt.Print(v)}) // 321

Development

Run test:

go test --tags=test ./...

Author

Cause Chung(cuzfrog@gmail.com)