go18ds
CategoryData Structures and Algorithms
SubcategoryMiscellaneous Data Structures and Algorithms
Stars48
Go Data Structures using Go 1.18 generics
About go18ds
This large README is shown as a plain-text preview. Read the full README at the source
<!-- omit in toc -->
# Go18DS (Go 1.18+ Data Structures)
[](https://pkg.go.dev/github.com/daichi-m/go18ds)
[](https://github.com/daichi-m/go18ds/actions/workflows/go.yml)
[](https://goreportcard.com/report/github.com/daichi-m/go18ds)
[](https://codecov.io/gh/daichi-m/go18ds)
[](https://github.com/daichi-m/go18ds/blob/main/LICENSE)
Implementation of various data structures and algorithms in Go.
This is based on the [GoDS](https://github.com/emirpasic/gods) library developed by Emir Pasic.
Since the target is for Go 1.18+, it is inherently generic-aware.
<!-- omit in toc -->
## Data Structures
- [Containers](#containers)
- [Lists](#lists)
- [ArrayList](#arraylist)
- [SinglyLinkedList](#singlylinkedlist)
- [DoublyLinkedList](#doublylinkedlist)
- [Sets](#sets)
- [HashSet](#hashset)
- [TreeSet](#treeset)
- [LinkedHashSet](#linkedhashset)
- [Stacks](#stacks)
- [LinkedListStack](#linkedliststack)
- [ArrayStack](#arraystack)
- [Maps](#maps)
- [HashMap](#hashmap)
- [TreeMap](#treemap)
- [LinkedHashMap](#linkedhashmap)
- [HashBidiMap](#hashbidimap)
- [TreeBidiMap](#treebidimap)
- [Trees](#trees)
- [RedBlackTree](#redblacktree)
- [AVLTree](#avltree)
- [BTree](#btree)
- [BinaryHeap](#binaryheap)
- [Functions](#functions)
- [Comparator](#comparator)
- [Iterator](#iterator)
- [IteratorWithIndex](#iteratorwithindex)
- [IteratorWithKey](#iteratorwithkey)
- [ReverseIteratorWithIndex](#reverseiteratorwithindex)
- [ReverseIteratorWithKey](#reverseiteratorwithkey)
- [Enumerable](#enumerable)
- [EnumerableWithIndex](#enumerablewithindex)
- [EnumerableWithKey](#enumerablewithkey)
- [Serialization](#serialization)
- [JSONSerializer](#jsonserializer)
- [JSONDeserializer](#jsondeserializer)
- [Sort](#sort)
- [Container](#container)
- [Appendix](#appendix)
- [Motivation](#motivation)
- [Goals](#goals)
- [Testing and Benchmarking](#testing-and-benchmarking)
- [Contributing](#contributing)
- [License](#license)
## Containers
All data structures implement the container interface with the following methods:
```go
type Container[T any] interface {
Empty() bool
Size() int
Clear()
Values() []T
}
```
Containers are either ordered or unordered. All ordered containers provide [stateful iterators](#iterator) and some of them allow [enumerable functions](#enumerable).
| **Data** | **Structure** | **Ordered** | **[Iterator](#iterator)** | **[Enumerable](#enumerable)** | **Referenced by** |
| :--- | :--- | :---: | :---: | :---: | :---: |
| [Lists](#lists) |
| | [ArrayList](#arraylist) | yes | yes* | yes | index |
| | [SinglyLinkedList](#singlylinkedlist) | yes | yes | yes | index |
| | [DoublyLinkedList](#doublylinkedlist) | yes | yes* | yes | index |
| [Sets](#sets) |
| | [HashSet](#hashset) | no | no | no | index |
| | [TreeSet](#treeset) | yes | yes* | yes | index |
| | [LinkedHashSet](#linkedhashset) | yes | yes* | yes | index |
| [Stacks](#stacks) |
| | [LinkedListStack](#linkedliststack) | yes | yes | no | index |
| | [ArrayStack](#arraystack) | yes | yes* | no | index |
| [Maps](#maps) |
| | [HashMap](#hashmap) | no | no | no | key |
| | [TreeMap](#treemap) | yes | yes* | yes | key |
| | [LinkedHashMap](#linkedhashmap) | yes | yes* | yes | key |
| | [HashBidiMap](#hashbidimap) | no | no | no | key* |
| | [TreeBidiMap](#treebidimap) | yes | yes* | yes | key* |
| [Trees](#trees) |
| | [RedBlackTree](#redblacktree) | yes | yes* | no | key |
| | [AVLTree](#avltree) | yes | yes* | no | key |
| | [BTree](#btree) | yes | yes* | no | key |
| | [BinaryHeap](#binaryheap) | yes | yes* | no | index |
| | | | <sub><sup>*reversible</sup></sub> | | <sub><sup>*bidirectional</sup></sub> |
### Lists
A list is a data structure that stores values and may have repeated values.
Implements [Container](#containers) interface.
```go
type List[T comparable] interface {
Get(index int) (T, bool)
Remove(index int)
Add(values ...T)
Contains(values ...T) bool
Sort(comparator utils.Comparator[T])
Swap(index1, index2 int)
Insert(index int, values ...T)
Set(index int, value T)
containers.Container[T]
// Empty() bool
// Size() int
// Clear()
// Values() []T
}
```
#### ArrayList
A [list](#lists) backed by a dynamic array that grows and shrinks implicitly.
Implements [List](#lists), [IteratorWithIndex](#iteratorwithindex), [EnumerableWithIndex](#enumerablewithindex), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
```go
package main
import (
"github.com/daichi-m/go18ds/lists/arraylist"
"github.com/daichi-m/go18ds/utils"
)
// ArrayListExample to demonstrate basic usage of ArrayList
func main() {
list := arraylist.New[string]()
list.Add("a") // ["a"]
list.Add("c", "b") // ["a","c","b"]
list.Sort(utils.StringComparator) // ["a","b","c"]
_, _ = list.Get(0) // "a",true
_, _ = list.Get(100) // nil,false
_ = list.Contains("a", "b", "c") // true
_ = list.Contains("a", "b", "c", "d") // false
list.Swap(0, 1) // ["b","a",c"]
list.Remove(2) // ["b","a"]
list.Remove(1) // ["b"]
list.Remove(0) // []
list.Remove(0) // [] (ignored)
_ = list.Empty() // true
_ = list.Size() // 0
list.Add("a") // ["a"]
list.Clear() // []
}
```
#### SinglyLinkedList
A [list](#lists) where each element points to the next element in the list.
Implements [List](#lists), [IteratorWithIndex](#iteratorwithindex), [EnumerableWithIndex](#enumerablewithindex), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
```go
package main
import (
sll "github.com/daichi-m/go18ds/lists/singlylinkedlist"
"github.com/daichi-m/go18ds/utils"
)
// SinglyLinkedListExample to demonstrate basic usage of SinglyLinkedList
func main() {
list := sll.New[string]()
list.Add("a") // ["a"]
list.Append("b") // ["a","b"] (same as Add())
list.Prepend("c") // ["c","a","b"]
list.Sort(utils.StringComparator) // ["a","b","c"]
_, _ = list.Get(0) // "a",true
_, _ = list.Get(100) // nil,false
_ = list.Contains("a", "b", "c") // true
_ = list.Contains("a", "b", "c", "d") // false
list.Remove(2) // ["a","b"]
list.Remove(1) // ["a"]
list.Remove(0) // []
list.Remove(0) // [] (ignored)
_ = list.Empty() // true
_ = list.Size() // 0
list.Add("a") // ["a"]
list.Clear() // []
}
```
#### DoublyLinkedList
A [list](#lists) where each element points to the next and previous elements in the list.
Implements [List](#lists), [IteratorWithIndex](#iteratorwithindex), [EnumerableWithIndex](#enumerablewithindex), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
```go
package main
import (
dll "github.com/daichi-m/go18ds/lists/doublylinkedlist"
"github.com/daichi-m/go18ds/utils"
)
// DoublyLinkedListExample to demonstrate basic usage of DoublyLinkedList
func main() {
list := dll.New[string]()
list.Add("a") // ["a"]
list.Append("b") // ["a","b"] (same as Add())
list.Prepend("c") // ["c","a","b"]
list.Sort(utils.StringComparator) // ["a","b","c"]
_, _ = list.Get(0) // "a",true
_, _ = list.Get(100) // nil,false
_ = list.Contains("a", "b", "c") // true
_ = list.Contains("a", "b", "c", "d") // false
list.Remove(2) // ["a","b"]
list.Remove(1) // ["a"]
list.Remove(0) // []
list.Remove(0) // [] (ignored)
_ = list.Empty() // true
_ = list.Size() // 0
list.Add("a") // ["a"]
list.Clear() // []
}
```
### Sets
A set is a data structure that can store elements and has no repeated values. It is a computer implementation of the mathematical concept of a finite set. Unlike most other collection types, rather than retrieving a specific element from a set, one typically tests an element for membership in a set. This structure is often used to ensure that no duplicates are present in a container.
Implements [Container](#containers) interface.
```go
type Set[T comparable] interface {
Add(elements ...T)
Remove(elements ...T)
Contains(elements ...T) bool
containers.Container[T]
// Empty() bool
// Size() int
// Clear()
// Values() []T
}
```
#### HashSet
A [set](#sets) backed by a hash table (actually a Go's map). It makes no guarantees as to the iteration order of the set.
Implements [Set](#sets), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
```go
import "github.com/daichi-m/go18ds/sets/hashset"
// HashSetExample to demonstrate basic usage of HashSet
func main() {
set := hashset.New[int]() // empty (keys are of type int)
set.Add(1) // 1
set.Add(2, 2, 3, 4, 5) // 3, 1, 2, 4, 5 (random order, duplicates ignored)
set.Remove(4) // 5, 3, 2, 1 (random order)
set.Remove(2, 3) // 1, 5 (random order)
set.Contains(1) // true
set.Contains(1, 5) // true
set.Contains(1, 6) // false
_ = set.Values() // []int{5,1} (random order)
set.Clear() // empty
set.Empty() // true
set.Size() // 0
}
```
#### TreeSet
A [set](#sets) backed by a [red-black tree](#redblacktree) to keep the elements ordered with respect to the [comparator](#comparator).
Implements [Set](#sets), [IteratorWithIndex](#iteratorwithindex), [EnumerableWithIndex](#enumerablewithindex), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
```go
package main
import "github.com/daichi-m/go18ds/sets/treeset"
// TreeSetExample to demonstrate basic usage of TreeSet
func main() {
set := treeset.NewWithIntComparator() // empty
set.Add(1) // 1
set.Add(2, 2, 3, 4, 5) // 1, 2, 3, 4, 5 (in order, duplicates ignored)
set.Remove(4) // 1, 2, 3, 5 (in order)
set.Remove(2, 3) // 1, 5 (in order)
set.Contains(1) // true
set.Contains(1, 5) // true
set.Contains(1, 6) // false
_ = set.Values() // []int{1,5} (in order)
set.Clear() // empty
set.Empty() // true
set.Size() // 0
}
```
#### LinkedHashSet
A [set](#sets) that preserves insertion-order. Data structure is backed by a hash table to store values and [doubly-linked list](#doublylinkedlist) to store insertion ordering.
Implements [Set](#sets), [IteratorWithIndex](#iteratorwithindex), [EnumerableWithIndex](#enumerablewithindex), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
```go
package main
import "github.com/daichi-m/go18ds/sets/linkedhashset"
// LinkedHashSetExample to demonstrate basic usage of LinkedHashSet
func main() {
set := linkedhashset.New[int]() // empty
set.Add(5) // 5
set.Add(4, 4, 3, 2, 1) // 5, 4, 3, 2, 1 (in insertion-order, duplicates ignored)
set.Remove(4) // 5, 3, 2, 1 (in insertion-order)
set.Remove(2, 3) // 5, 1 (in insertion-order)
set.Contains(1) // true
set.Contains(1, 5) // true
set.Contains(1, 6) // false
_ = set.Values() // []int{5, 1} (in insertion-order)
set.Clear() // empty
set.Empty() // true
set.Size() // 0
}
```
### Stacks
A stack that represents a last-in-first-out (LIFO) data structure. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack.
Implements [Container](#containers) interface.
```go
type Stack[T comparable] interface {
Push(value T)
Pop() (value T, ok bool)
Peek() (value T, ok bool)
containers.Container[T]
// Empty() bool
// Size() int
// Clear()
// Values() []interface{}
}
```
#### LinkedListStack
A [stack](#stacks) based on a [linked list](#singlylinkedlist).
Implements [Stack](#stacks), [IteratorWithIndex](#iteratorwithindex), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
```go
package main
import lls "github.com/daichi-m/go18ds/stacks/linkedliststack"
// LinkedListStackExample to demonstrate basic usage of LinkedListStack
func main() {
stack := lls.New[int]() // empty
stack.Push(1) // 1
stack.Push(2) // 1, 2
stack.Values() // 2, 1 (LIFO order)
_, _ = stack.Peek() // 2,true
_, _ = stack.Pop() // 2, true
_, _ = stack.Pop() // 1, true
_, _ = stack.Pop() // nil, false (nothing to pop)
stack.Push(1) // 1
stack.Clear() // empty
stack.Empty() // true
stack.Size() // 0
}
```
#### ArrayStack
A [stack](#stacks) based on a [array list](#arraylist).
Implements [Stack](#stacks), [IteratorWithIndex](#iteratorwithindex), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
```go
package main
import "github.com/daichi-m/go18ds/stacks/arraystack"
// ArrayStackExample to demonstrate basic usage of ArrayStack
func main() {
stack := arraystack.New[int]() // empty
stack.Push(1) // 1
stack.Push(2) // 1, 2
stack.Values() // 2, 1 (LIFO order)
_, _ = stack.Peek() // 2,true
_, _ = stack.Pop() // 2, true
_, _ = stack.Pop() // 1, true
_, _ = stack.Pop() // nil, false (nothing to pop)
stack.Push(1) // 1
stack.Clear() // empty
stack.Empty() // true
stack.Size() // 0
}
```
### Maps
A Map is a data structure that maps keys to values. A map cannot contain duplicate keys and each key can map to at most one value.
Implements [Container](#containers) interface.
```go
// Map interface that all maps implement
type Map[K comparable, V any] interface {
Put(key K, value V)
Get(key K) (value V, found bool)
Remove(key K)
Keys() []K
containers.Container[V]
// Empty() bool
// Size() int
// Clear()
// Values() []interface{}
}
```
A BidiMap is an extension to the Map. A bidirectional map (BidiMap), also called a hash bag, is an associative data structure in which the key-value pairs form a one-to-one relation. This relation works in both directions by allow the value to also act as a key to key, e.g. a pair (a,b) thus provides a coupling between 'a' and 'b' so that 'b' can be found when 'a' is used as a key and 'a' can be found when 'b' is used as a key.
```go
// BidiMap interface that all bidirectional maps implement (extends the Map interface)
type BidiMap[K comparable, V any] interface {
GetKey(value V) (key K, found bool)
Map[K, V]
}
```
#### HashMap
A [map](#maps) based on hash tables. Keys are unordered.
Implements [Map](#maps), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
```go
package main
import "github.com/daichi-m/go18ds/maps/hashmap"
// HashMapExample to demonstrate basic usage of HashMap
func main() {
m := hashmap.New[int, string]() // empty
m.Put(1, "x") // 1->x
m.Put(2, "b") // 2->b, 1->x (random order)
m.Put(1, "a") // 2->b, 1->a (random order)
_, _ = m.Get(2) // b, true
_, _ = m.Get(3) // nil, false
_ = m.Values() // []interface {}{"b", "a"} (random order)
_ = m.Keys() // []interface {}{1, 2} (random order)
m.Remove(1) // 2->b
m.Clear() // empty
m.Empty() // true
m.Size() // 0
}
```
#### TreeMap
A [map](#maps) based on [red-black tree](#redblacktree). Keys are ordered with respect to the [comparator](#comparator).
Implements [Map](#maps), [IteratorWithKey](#iteratorwithkey), [EnumerableWithKey](#enumerablewithkey), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
```go
package main
import "github.com/emirpasic/gods/maps/treemap"
func main() {
m := treemap.NewWithIntComparator() // empty (keys are of type int)
m.Put(1, "x") // 1->x
m.Put(2, "b") // 1->x, 2->b (in order)
m.Put(1, "a") // 1->a, 2->b (in order)
_, _ = m.Get(2) // b, true
_, _ = m.Get(3) // nil, false
_ = m.Values() // []interface {}{"a", "b"} (in order)
_ = m.Keys() // []interface {}{1, 2} (in order)
m.Remove(1) // 2->b
m.Clear() // empty
m.Empty() // true
m.Size() // 0
// Other:
m.Min() // Returns the minimum key and its value from map.
m.Max() // Returns the maximum key and its value from map.
}
```
#### LinkedHashMap
A [map](#maps) that preserves insertion-order. It is backed by a hash table to store values and [doubly-linked list](doublylinkedlist) to store ordering.
Implements [Map](#maps), [IteratorWithKey](#iteratorwithkey), [EnumerableWithKey](#enumerablewithkey), [JSONSerializer](#jsonserializer) and [JSONDeserializer](#jsondeserializer) interfaces.
```go
package main
import "github.com/daichi-m/go18ds/maps/linkedhashmap"
// LinkedHashMapExample to demonstrate basic usage of LinkedHashMapExample
func main() {
m := linkedhashmap.New[int, string]() // empty (keys are of type int)
m.Put(2, "b") // 2->b
m.Put(1, "x") // 2->b, 1->x (insertion-order)
m.Put(1, "a") // 2->b, 1->a (insertion-order)
_, _ = m.Get(2) // b, true
_, _ = m.Get(3) // nil, false
_ = m.Values() // []interface {}{"b", "a"} (insertion-order)
_ = m.Keys() // []interface {}{2, 1} (insertion-order)
m.Remove(1) // 2->b
m.Clear() // empty
m.Empty() // true
m.Size() // 0
}
```
#### HashBidiMap
A [map](#maps) based on two hashmaps. Keys are unordered.
Frequently Asked Questions
What is go18ds?
go18ds is a Data Structures and Algorithms library for the Go programming language. Go Data Structures using Go 1.18 generics
How do I install go18ds?
Install go18ds with the Go module system using `go get daichi-m/go18ds`. Check the repository for the current installation instructions.
What category does go18ds belong to?
go18ds is listed under Data Structures and Algorithms, specifically Miscellaneous Data Structures and Algorithms.