- Notifications
You must be signed in to change notification settings - Fork1.8k
GoDS (Go Data Structures) - Sets, Lists, Stacks, Maps, Trees, Queues, and much more
License
emirpasic/gods
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
Implementation of various data structures and algorithms in Go.
All data structures implement the container interface with the following methods:
typeContainerinterface {Empty()boolSize()intClear()Values() []interface{}String()string}
Containers are either ordered or unordered. All ordered containers providestateful iterators and some of them allowenumerable functions.
| Data | Structure | Ordered | Iterator | Enumerable | Referenced by |
|---|---|---|---|---|---|
| Lists | |||||
| ArrayList | yes | yes* | yes | index | |
| SinglyLinkedList | yes | yes | yes | index | |
| DoublyLinkedList | yes | yes* | yes | index | |
| Sets | |||||
| HashSet | no | no | no | index | |
| TreeSet | yes | yes* | yes | index | |
| LinkedHashSet | yes | yes* | yes | index | |
| Stacks | |||||
| LinkedListStack | yes | yes | no | index | |
| ArrayStack | yes | yes* | no | index | |
| Maps | |||||
| HashMap | no | no | no | key | |
| TreeMap | yes | yes* | yes | key | |
| LinkedHashMap | yes | yes* | yes | key | |
| HashBidiMap | no | no | no | key* | |
| TreeBidiMap | yes | yes* | yes | key* | |
| Trees | |||||
| RedBlackTree | yes | yes* | no | key | |
| AVLTree | yes | yes* | no | key | |
| BTree | yes | yes* | no | key | |
| BinaryHeap | yes | yes* | no | index | |
| Queues | |||||
| LinkedListQueue | yes | yes | no | index | |
| ArrayQueue | yes | yes* | no | index | |
| CircularBuffer | yes | yes* | no | index | |
| PriorityQueue | yes | yes* | no | index | |
| *reversible | *bidirectional |
A list is a data structure that stores values and may have repeated values.
ImplementsContainer interface.
typeListinterface {Get(indexint) (interface{},bool)Remove(indexint)Add(values...interface{})Contains(values...interface{})boolSort(comparator utils.Comparator)Swap(index1,index2int)Insert(indexint,values...interface{})Set(indexint,valueinterface{})containers.Container// Empty() bool// Size() int// Clear()// Values() []interface{}// String() string}
Alist backed by a dynamic array that grows and shrinks implicitly.
ImplementsList,ReverseIteratorWithIndex,EnumerableWithIndex,JSONSerializer andJSONDeserializer interfaces.
package mainimport ("github.com/emirpasic/gods/lists/arraylist""github.com/emirpasic/gods/utils")funcmain() {list:=arraylist.New()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")// falselist.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()// 0list.Add("a")// ["a"]list.Clear()// []list.Insert(0,"b")// ["b"]list.Insert(0,"a")// ["a","b"]}
Alist where each element points to the next element in the list.
ImplementsList,IteratorWithIndex,EnumerableWithIndex,JSONSerializer andJSONDeserializer interfaces.
package mainimport (sll"github.com/emirpasic/gods/lists/singlylinkedlist""github.com/emirpasic/gods/utils")funcmain() {list:=sll.New()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")// falselist.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()// 0list.Add("a")// ["a"]list.Clear()// []list.Insert(0,"b")// ["b"]list.Insert(0,"a")// ["a","b"]}
Alist where each element points to the next and previous elements in the list.
ImplementsList,ReverseIteratorWithIndex,EnumerableWithIndex,JSONSerializer andJSONDeserializer interfaces.
package mainimport (dll"github.com/emirpasic/gods/lists/doublylinkedlist""github.com/emirpasic/gods/utils")funcmain() {list:=dll.New()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")// falselist.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()// 0list.Add("a")// ["a"]list.Clear()// []list.Insert(0,"b")// ["b"]list.Insert(0,"a")// ["a","b"]}
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.
Set additionally allow set operations such asintersection,union,difference, etc.
ImplementsContainer interface.
typeSetinterface {Add(elements...interface{})Remove(elements...interface{})Contains(elements...interface{})bool// Intersection(another *Set) *Set// Union(another *Set) *Set// Difference(another *Set) *Setcontainers.Container// Empty() bool// Size() int// Clear()// Values() []interface{}// String() string}
Aset backed by a hash table (actually a Go's map). It makes no guarantees as to the iteration order of the set.
ImplementsSet,JSONSerializer andJSONDeserializer interfaces.
package mainimport"github.com/emirpasic/gods/sets/hashset"funcmain() {set:=hashset.New()// emptyset.Add(1)// 1set.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)// trueset.Contains(1,5)// trueset.Contains(1,6)// false_=set.Values()// []int{5,1} (random order)set.Clear()// emptyset.Empty()// trueset.Size()// 0}
Aset backed by ared-black tree to keep the elements ordered with respect to thecomparator.
ImplementsSet,ReverseIteratorWithIndex,EnumerableWithIndex,JSONSerializer andJSONDeserializer interfaces.
package mainimport"github.com/emirpasic/gods/sets/treeset"funcmain() {set:=treeset.NewWithIntComparator()// empty (keys are of type int)set.Add(1)// 1set.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)// trueset.Contains(1,5)// trueset.Contains(1,6)// false_=set.Values()// []int{1,5} (in order)set.Clear()// emptyset.Empty()// trueset.Size()// 0}
Aset that preserves insertion-order. Data structure is backed by a hash table to store values anddoubly-linked list to store insertion ordering.
ImplementsSet,ReverseIteratorWithIndex,EnumerableWithIndex,JSONSerializer andJSONDeserializer interfaces.
package mainimport"github.com/emirpasic/gods/sets/linkedhashset"funcmain() {set:=linkedhashset.New()// emptyset.Add(5)// 5set.Add(4,4,3,2,1)// 5, 4, 3, 2, 1 (in insertion-order, duplicates ignored)set.Add(4)// 5, 4, 3, 2, 1 (duplicates ignored, insertion-order unchanged)set.Remove(4)// 5, 3, 2, 1 (in insertion-order)set.Remove(2,3)// 5, 1 (in insertion-order)set.Contains(1)// trueset.Contains(1,5)// trueset.Contains(1,6)// false_=set.Values()// []int{5, 1} (in insertion-order)set.Clear()// emptyset.Empty()// trueset.Size()// 0}
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.
ImplementsContainer interface.
typeStackinterface {Push(valueinterface{})Pop() (valueinterface{},okbool)Peek() (valueinterface{},okbool)containers.Container// Empty() bool// Size() int// Clear()// Values() []interface{}// String() string}
Astack based on alinked list.
ImplementsStack,IteratorWithIndex,JSONSerializer andJSONDeserializer interfaces.
package mainimport lls"github.com/emirpasic/gods/stacks/linkedliststack"funcmain() {stack:=lls.New()// emptystack.Push(1)// 1stack.Push(2)// 1, 2stack.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)// 1stack.Clear()// emptystack.Empty()// truestack.Size()// 0}
Astack based on aarray list.
ImplementsStack,IteratorWithIndex,JSONSerializer andJSONDeserializer interfaces.
package mainimport"github.com/emirpasic/gods/stacks/arraystack"funcmain() {stack:=arraystack.New()// emptystack.Push(1)// 1stack.Push(2)// 1, 2stack.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)// 1stack.Clear()// emptystack.Empty()// truestack.Size()// 0}
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.
ImplementsContainer interface.
typeMapinterface {Put(keyinterface{},valueinterface{})Get(keyinterface{}) (valueinterface{},foundbool)Remove(keyinterface{})Keys() []interface{}containers.Container// Empty() bool// Size() int// Clear()// Values() []interface{}// String() string}
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.
typeBidiMapinterface {GetKey(valueinterface{}) (keyinterface{},foundbool)Map}
Amap based on hash tables. Keys are unordered.
ImplementsMap,JSONSerializer andJSONDeserializer interfaces.
package mainimport"github.com/emirpasic/gods/maps/hashmap"funcmain() {m:=hashmap.New()// emptym.Put(1,"x")// 1->xm.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->bm.Clear()// emptym.Empty()// truem.Size()// 0}
Amap based onred-black tree. Keys are ordered with respect to thecomparator.
ImplementsMap,ReverseIteratorWithIndex,EnumerableWithKey,JSONSerializer andJSONDeserializer interfaces.
package mainimport"github.com/emirpasic/gods/maps/treemap"funcmain() {m:=treemap.NewWithIntComparator()// empty (keys are of type int)m.Put(1,"x")// 1->xm.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->bm.Clear()// emptym.Empty()// truem.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.}
Amap that preserves insertion-order. It is backed by a hash table to store values anddoubly-linked list to store ordering.
ImplementsMap,ReverseIteratorWithIndex,EnumerableWithKey,JSONSerializer andJSONDeserializer interfaces.
package mainimport"github.com/emirpasic/gods/maps/linkedhashmap"funcmain() {m:=linkedhashmap.New()// empty (keys are of type int)m.Put(2,"b")// 2->bm.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->bm.Clear()// emptym.Empty()// truem.Size()// 0}
Amap based on two hashmaps. Keys are unordered.
ImplementsBidiMap,JSONSerializer andJSONDeserializer interfaces.
package mainimport"github.com/emirpasic/gods/maps/hashbidimap"funcmain() {m:=hashbidimap.New()// emptym.Put(1,"x")// 1->xm.Put(3,"b")// 1->x, 3->b (random order)m.Put(1,"a")// 1->a, 3->b (random order)m.Put(2,"b")// 1->a, 2->b (random order)_,_=m.GetKey("a")// 1, true_,_=m.Get(2)// b, true_,_=m.Get(3)// nil, false_=m.Values()// []interface {}{"a", "b"} (random order)_=m.Keys()// []interface {}{1, 2} (random order)m.Remove(1)// 2->bm.Clear()// emptym.Empty()// truem.Size()// 0}
Amap based on red-black tree. This map guarantees that the map will be in both ascending key and value order. Other than key and value ordering, the goal with this structure is to avoid duplication of elements (unlike inHashBidiMap), which can be significant if contained elements are large.
ImplementsBidiMap,ReverseIteratorWithIndex,EnumerableWithKey,JSONSerializer andJSONDeserializer interfaces.
package mainimport ("github.com/emirpasic/gods/maps/treebidimap""github.com/emirpasic/gods/utils")funcmain() {m:=treebidimap.NewWith(utils.IntComparator,utils.StringComparator)m.Put(1,"x")// 1->xm.Put(3,"b")// 1->x, 3->b (ordered)m.Put(1,"a")// 1->a, 3->b (ordered)m.Put(2,"b")// 1->a, 2->b (ordered)_,_=m.GetKey("a")// 1, true_,_=m.Get(2)// b, true_,_=m.Get(3)// nil, false_=m.Values()// []interface {}{"a", "b"} (ordered)_=m.Keys()// []interface {}{1, 2} (ordered)m.Remove(1)// 2->bm.Clear()// emptym.Empty()// truem.Size()// 0}
A tree is a widely used data data structure that simulates a hierarchical tree structure, with a root value and subtrees of children, represented as a set of linked nodes; thus no cyclic links.
ImplementsContainer interface.
typeTreeinterface {containers.Container// Empty() bool// Size() int// Clear()// Values() []interface{}// String() string}
A red–blacktree is a binary search tree with an extra bit of data per node, its color, which can be either red or black. The extra bit of storage ensures an approximately balanced tree by constraining how nodes are colored from any path from the root to the leaf. Thus, it is a data structure which is a type of self-balancing binary search tree.
The balancing of the tree is not perfect but it is good enough to allow it to guarantee searching in O(log n) time, where n is the total number of elements in the tree. The insertion and deletion operations, along with the tree rearrangement and recoloring, are also performed in O(log n) time.Wikipedia
ImplementsTree,ReverseIteratorWithKey,JSONSerializer andJSONDeserializer interfaces.
package mainimport ("fmt"rbt"github.com/emirpasic/gods/trees/redblacktree")funcmain() {tree:=rbt.NewWithIntComparator()// empty (keys are of type int)tree.Put(1,"x")// 1->xtree.Put(2,"b")// 1->x, 2->b (in order)tree.Put(1,"a")// 1->a, 2->b (in order, replacement)tree.Put(3,"c")// 1->a, 2->b, 3->c (in order)tree.Put(4,"d")// 1->a, 2->b, 3->c, 4->d (in order)tree.Put(5,"e")// 1->a, 2->b, 3->c, 4->d, 5->e (in order)tree.Put(6,"f")// 1->a, 2->b, 3->c, 4->d, 5->e, 6->f (in order)fmt.Println(tree)//// RedBlackTree// │ ┌── 6//│ ┌── 5//│ ┌── 4//│ │ └── 3//└── 2//└── 1_=tree.Values()// []interface {}{"a", "b", "c", "d", "e", "f"} (in order)_=tree.Keys()// []interface {}{1, 2, 3, 4, 5, 6} (in order)tree.Remove(2)// 1->a, 3->c, 4->d, 5->e, 6->f (in order)fmt.Println(tree)//// RedBlackTree// │ ┌── 6// │ ┌── 5// └── 4// │ ┌── 3// └── 1tree.Clear()// emptytree.Empty()// truetree.Size()// 0// Other:tree.Left()// gets the left-most (min) nodetree.Right()// get the right-most (max) nodetree.Floor(1)// get the floor nodetree.Ceiling(1)// get the ceiling node}
Extending the red-black tree's functionality has been demonstrated in the followingexample.
AVLtree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
AVL trees are often compared with red–black trees because both support the same set of operations and take O(log n) time for the basic operations. For lookup-intensive applications, AVL trees are faster than red–black trees because they are more strictly balanced.Wikipedia
ImplementsTree,ReverseIteratorWithKey,JSONSerializer andJSONDeserializer interfaces.
AVL tree with balance factors (green)
package mainimport ("fmt"avl"github.com/emirpasic/gods/trees/avltree")funcmain() {tree:=avl.NewWithIntComparator()// empty(keys are of type int)tree.Put(1,"x")// 1->xtree.Put(2,"b")// 1->x, 2->b (in order)tree.Put(1,"a")// 1->a, 2->b (in order, replacement)tree.Put(3,"c")// 1->a, 2->b, 3->c (in order)tree.Put(4,"d")// 1->a, 2->b, 3->c, 4->d (in order)tree.Put(5,"e")// 1->a, 2->b, 3->c, 4->d, 5->e (in order)tree.Put(6,"f")// 1->a, 2->b, 3->c, 4->d, 5->e, 6->f (in order)fmt.Println(tree)//// AVLTree// │ ┌── 6// │ ┌── 5// └── 4// │ ┌── 3// └── 2// └── 1_=tree.Values()// []interface {}{"a", "b", "c", "d", "e", "f"} (in order)_=tree.Keys()// []interface {}{1, 2, 3, 4, 5, 6} (in order)tree.Remove(2)// 1->a, 3->c, 4->d, 5->e, 6->f (in order)fmt.Println(tree)//// AVLTree// │ ┌── 6// │ ┌── 5// └── 4// └── 3// └── 1tree.Clear()// emptytree.Empty()// truetree.Size()// 0}
B-tree is a self-balancing tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children.
According to Knuth's definition, a B-tree of order m is a tree which satisfies the following properties:
- Every node has at most m children.
- Every non-leaf node (except root) has at least ⌈m/2⌉ children.
- The root has at least two children if it is not a leaf node.
- A non-leaf node with k children contains k−1 keys.
- All leaves appear in the same level
Each internal node’s keys act as separation values which divide its subtrees. For example, if an internal node has 3 child nodes (or subtrees) then it must have 2 keys: a1 and a2. All values in the leftmost subtree will be less than a1, all values in the middle subtree will be between a1 and a2, and all values in the rightmost subtree will be greater than a2.Wikipedia
ImplementsTree,ReverseIteratorWithKey,JSONSerializer andJSONDeserializer interfaces.
package mainimport ("fmt""github.com/emirpasic/gods/trees/btree")funcmain() {tree:=btree.NewWithIntComparator(3)// empty (keys are of type int)tree.Put(1,"x")// 1->xtree.Put(2,"b")// 1->x, 2->b (in order)tree.Put(1,"a")// 1->a, 2->b (in order, replacement)tree.Put(3,"c")// 1->a, 2->b, 3->c (in order)tree.Put(4,"d")// 1->a, 2->b, 3->c, 4->d (in order)tree.Put(5,"e")// 1->a, 2->b, 3->c, 4->d, 5->e (in order)tree.Put(6,"f")// 1->a, 2->b, 3->c, 4->d, 5->e, 6->f (in order)tree.Put(7,"g")// 1->a, 2->b, 3->c, 4->d, 5->e, 6->f, 7->g (in order)fmt.Println(tree)// BTree// 1// 2// 3// 4// 5// 6// 7_=tree.Values()// []interface {}{"a", "b", "c", "d", "e", "f", "g"} (in order)_=tree.Keys()// []interface {}{1, 2, 3, 4, 5, 6, 7} (in order)tree.Remove(2)// 1->a, 3->c, 4->d, 5->e, 6->f, 7->g (in order)fmt.Println(tree)// BTree// 1// 3// 4// 5// 6// 7tree.Clear()// emptytree.Empty()// truetree.Size()// 0// Other:tree.Height()// gets the height of the treetree.Left()// gets the left-most (min) nodetree.LeftKey()// get the left-most (min) node's keytree.LeftValue()// get the left-most (min) node's valuetree.Right()// get the right-most (max) nodetree.RightKey()// get the right-most (max) node's keytree.RightValue()// get the right-most (max) node's value}
A binary heap is atree created using a binary tree. It can be seen as a binary tree with two additional constraints:
Shape property:
A binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
Heap property:
All nodes are either greater than or equal to or less than or equal to each of its children, according to a comparison predicate defined for the heap.Wikipedia
ImplementsTree,ReverseIteratorWithIndex,JSONSerializer andJSONDeserializer interfaces.
package mainimport ("github.com/emirpasic/gods/trees/binaryheap""github.com/emirpasic/gods/utils")funcmain() {// Min-heapheap:=binaryheap.NewWithIntComparator()// empty (min-heap)heap.Push(2)// 2heap.Push(3)// 2, 3heap.Push(1)// 1, 3, 2heap.Values()// 1, 3, 2_,_=heap.Peek()// 1,true_,_=heap.Pop()// 1, true_,_=heap.Pop()// 2, true_,_=heap.Pop()// 3, true_,_=heap.Pop()// nil, false (nothing to pop)heap.Push(1)// 1heap.Clear()// emptyheap.Empty()// trueheap.Size()// 0// Max-heapinverseIntComparator:=func(a,binterface{})int {return-utils.IntComparator(a,b)}heap=binaryheap.NewWith(inverseIntComparator)// empty (min-heap)heap.Push(2,3,1)// 3, 2, 1 (bulk optimized)heap.Values()// 3, 2, 1}
A queue that represents a first-in-first-out (FIFO) data structure. The usual enqueue and dequeue operations are provided, as well as a method to peek at the first item in the queue.
ImplementsContainer interface.
typeQueueinterface {Enqueue(valueinterface{})Dequeue() (valueinterface{},okbool)Peek() (valueinterface{},okbool)containers.Container// Empty() bool// Size() int// Clear()// Values() []interface{}// String() string}
Aqueue based on alinked list.
ImplementsQueue,IteratorWithIndex,JSONSerializer andJSONDeserializer interfaces.
package mainimport llq"github.com/emirpasic/gods/queues/linkedlistqueue"// LinkedListQueueExample to demonstrate basic usage of LinkedListQueuefuncmain() {queue:=llq.New()// emptyqueue.Enqueue(1)// 1queue.Enqueue(2)// 1, 2_=queue.Values()// 1, 2 (FIFO order)_,_=queue.Peek()// 1,true_,_=queue.Dequeue()// 1, true_,_=queue.Dequeue()// 2, true_,_=queue.Dequeue()// nil, false (nothing to deque)queue.Enqueue(1)// 1queue.Clear()// emptyqueue.Empty()// true_=queue.Size()// 0}
Aqueue based on aarray list.
ImplementsQueue,ReverseIteratorWithIndex,JSONSerializer andJSONDeserializer interfaces.
package mainimport aq"github.com/emirpasic/gods/queues/arrayqueue"// ArrayQueueExample to demonstrate basic usage of ArrayQueuefuncmain() {queue:=aq.New()// emptyqueue.Enqueue(1)// 1queue.Enqueue(2)// 1, 2_=queue.Values()// 1, 2 (FIFO order)_,_=queue.Peek()// 1,true_,_=queue.Dequeue()// 1, true_,_=queue.Dequeue()// 2, true_,_=queue.Dequeue()// nil, false (nothing to deque)queue.Enqueue(1)// 1queue.Clear()// emptyqueue.Empty()// true_=queue.Size()// 0}
A circular buffer, circularqueue, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams.
ImplementsQueue,ReverseIteratorWithIndex,JSONSerializer andJSONDeserializer interfaces.
package mainimport cb"github.com/emirpasic/gods/queues/circularbuffer"// CircularBufferExample to demonstrate basic usage of CircularBufferfuncmain() {queue:=cb.New(3)// empty (max size is 3)queue.Enqueue(1)// 1queue.Enqueue(2)// 1, 2queue.Enqueue(3)// 1, 2, 3_=queue.Values()// 1, 2, 3queue.Enqueue(3)// 4, 2, 3_,_=queue.Peek()// 4,true_,_=queue.Dequeue()// 4, true_,_=queue.Dequeue()// 2, true_,_=queue.Dequeue()// 3, true_,_=queue.Dequeue()// nil, false (nothing to deque)queue.Enqueue(1)// 1queue.Clear()// emptyqueue.Empty()// true_=queue.Size()// 0}
A priority queue is a special type ofqueue in which each element is associated with a priority value. And, elements are served on the basis of their priority. That is, higher priority elements are served first. However, if elements with the same priority occur, they are served according to their order in the queue.
ImplementsQueue,ReverseIteratorWithIndex,JSONSerializer andJSONDeserializer interfaces.
package mainimport ( pq"github.com/emirpasic/gods/queues/priorityqueue""github.com/emirpasic/gods/utils")// Element is an entry in the priority queuetypeElementstruct {namestringpriorityint}// Comparator function (sort by element's priority value in descending order)funcbyPriority(a,binterface{})int {priorityA:=a.(Element).prioritypriorityB:=b.(Element).priorityreturn-utils.IntComparator(priorityA,priorityB)// "-" descending order}// PriorityQueueExample to demonstrate basic usage of BinaryHeapfuncmain() {a:=Element{name:"a",priority:1}b:=Element{name:"b",priority:2}c:=Element{name:"c",priority:3}queue:=pq.NewWith(byPriority)// emptyqueue.Enqueue(a)// {a 1}queue.Enqueue(c)// {c 3}, {a 1}queue.Enqueue(b)// {c 3}, {b 2}, {a 1}_=queue.Values()// [{c 3} {b 2} {a 1}]_,_=queue.Peek()// {c 3} true_,_=queue.Dequeue()// {c 3} true_,_=queue.Dequeue()// {b 2} true_,_=queue.Dequeue()// {a 1} true_,_=queue.Dequeue()// <nil> false (nothing to dequeue)queue.Clear()// empty_=queue.Empty()// true_=queue.Size()// 0}
Various helper functions used throughout the library.
Some data structures (e.g. TreeMap, TreeSet) require a comparator function to automatically keep their elements sorted upon insertion. This comparator is necessary during the initalization.
Comparator is defined as:
Return values (int):
negative ,ifa<bzero ,ifa==bpositive ,ifa>b
Comparator signature:
typeComparatorfunc(a,binterface{})int
All common comparators for builtin types are included in the library:
funcStringComparator(a,binterface{})intfuncIntComparator(a,binterface{})intfuncInt8Comparator(a,binterface{})intfuncInt16Comparator(a,binterface{})intfuncInt32Comparator(a,binterface{})intfuncInt64Comparator(a,binterface{})intfuncUIntComparator(a,binterface{})intfuncUInt8Comparator(a,binterface{})intfuncUInt16Comparator(a,binterface{})intfuncUInt32Comparator(a,binterface{})intfuncUInt64Comparator(a,binterface{})intfuncFloat32Comparator(a,binterface{})intfuncFloat64Comparator(a,binterface{})intfuncByteComparator(a,binterface{})intfuncRuneComparator(a,binterface{})intfuncTimeComparator(a,binterface{})int
Writing custom comparators is easy:
package mainimport ("fmt""github.com/emirpasic/gods/sets/treeset")typeUserstruct {idintnamestring}// Custom comparator (sort by IDs)funcbyID(a,binterface{})int {// Type assertion, program will panic if this is not respectedc1:=a.(User)c2:=b.(User)switch {casec1.id>c2.id:return1casec1.id<c2.id:return-1default:return0}}funcmain() {set:=treeset.NewWith(byID)set.Add(User{2,"Second"})set.Add(User{3,"Third"})set.Add(User{1,"First"})set.Add(User{4,"Fourth"})fmt.Println(set)// {1 First}, {2 Second}, {3 Third}, {4 Fourth}}
All ordered containers have stateful iterators. Typically an iterator is obtained byIterator() function of an ordered container. Once obtained, iterator'sNext() function moves the iterator to the next element and returns true if there was a next element. If there was an element, then element's can be obtained by iterator'sValue() function. Depending on the ordering type, it's position can be obtained by iterator'sIndex() orKey() functions. Some containers even provide reversible iterators, essentially the same, but provide another extraPrev() function that moves the iterator to the previous element and returns true if there was a previous element.
Note: it is unsafe to remove elements from container while iterating.
Aniterator whose elements are referenced by an index.
Typical usage:
it:=list.Iterator()forit.Next() {index,value:=it.Index(),it.Value()...}
Other usages:
ifit.First() {firstIndex,firstValue:=it.Index(),it.Value()...}
forit.Begin();it.Next(); {...}
Seeking to a specific element:
// Seek function, i.e. find element starting with "b"seek:=func(indexint,valueinterface{})bool {returnstrings.HasSuffix(value.(string),"b")}// Seek to the condition and continue traversal from that point (forward).// assumes it.Begin() was called.forfound:=it.NextTo(seek);found;found=it.Next() {index,value:=it.Index(),it.Value()...}
Aniterator whose elements are referenced by a key.
Typical usage:
it:=tree.Iterator()forit.Next() {key,value:=it.Key(),it.Value()...}
Other usages:
ifit.First() {firstKey,firstValue:=it.Key(),it.Value()...}
forit.Begin();it.Next(); {...}
Seeking to a specific element from the current iterator position:
// Seek function, i.e. find element starting with "b"seek:=func(keyinterface{},valueinterface{})bool {returnstrings.HasSuffix(value.(string),"b")}// Seek to the condition and continue traversal from that point (forward).// assumes it.Begin() was called.forfound:=it.NextTo(seek);found;found=it.Next() {key,value:=it.Key(),it.Value()...}
Aniterator whose elements are referenced by an index. Provides all functions asIteratorWithIndex, but can also be used for reverse iteration.
Typical usage of iteration in reverse:
it:=list.Iterator()forit.End();it.Prev(); {index,value:=it.Index(),it.Value()...}
Other usages:
ifit.Last() {lastIndex,lastValue:=it.Index(),it.Value()...}
Seeking to a specific element:
// Seek function, i.e. find element starting with "b"seek:=func(indexint,valueinterface{})bool {returnstrings.HasSuffix(value.(string),"b")}// Seek to the condition and continue traversal from that point (in reverse).// assumes it.End() was called.forfound:=it.PrevTo(seek);found;found=it.Prev() {index,value:=it.Index(),it.Value()...}
Aniterator whose elements are referenced by a key. Provides all functions asIteratorWithKey, but can also be used for reverse iteration.
Typical usage of iteration in reverse:
it:=tree.Iterator()forit.End();it.Prev(); {key,value:=it.Key(),it.Value()...}
Other usages:
ifit.Last() {lastKey,lastValue:=it.Key(),it.Value()...}
// Seek function, i.e. find element starting with "b"seek:=func(keyinterface{},valueinterface{})bool {returnstrings.HasSuffix(value.(string),"b")}// Seek to the condition and continue traversal from that point (in reverse).// assumes it.End() was called.forfound:=it.PrevTo(seek);found;found=it.Prev() {key,value:=it.Key(),it.Value()...}
Enumerable functions for ordered containers that implementEnumerableWithIndex orEnumerableWithKey interfaces.
Enumerable functions for ordered containers whose values can be fetched by an index.
Each
Calls the given function once for each element, passing that element's index and value.
Each(func(indexint,valueinterface{}))
Map
Invokes the given function once for each element and returns a container containing the values returned by the given function.
Map(func(indexint,valueinterface{})interface{})Container
Select
Returns a new container containing all elements for which the given function returns a true value.
Select(func(indexint,valueinterface{})bool)Container
Any
Passes each element of the container to the given function and returns true if the function ever returns true for any element.
Any(func(indexint,valueinterface{})bool)bool
All
Passes each element of the container to the given function and returns true if the function returns true for all elements.
All(func(indexint,valueinterface{})bool)bool
Find
Passes each element of the container to the given function and returns the first (index,value) for which the function is true or -1,nil otherwise if no element matches the criteria.
Find(func(indexint,valueinterface{})bool) (int,interface{})}
Example:
package mainimport ("fmt""github.com/emirpasic/gods/sets/treeset")funcprintSet(txtstring,set*treeset.Set) {fmt.Print(txt,"[ ")set.Each(func(indexint,valueinterface{}) {fmt.Print(value," ")})fmt.Println("]")}funcmain() {set:=treeset.NewWithIntComparator()set.Add(2,3,4,2,5,6,7,8)printSet("Initial",set)// [ 2 3 4 5 6 7 8 ]even:=set.Select(func(indexint,valueinterface{})bool {returnvalue.(int)%2==0})printSet("Even numbers",even)// [ 2 4 6 8 ]foundIndex,foundValue:=set.Find(func(indexint,valueinterface{})bool {returnvalue.(int)%2==0&&value.(int)%3==0})iffoundIndex!=-1 {fmt.Println("Number divisible by 2 and 3 found is",foundValue,"at index",foundIndex)// value: 6, index: 4}square:=set.Map(func(indexint,valueinterface{})interface{} {returnvalue.(int)*value.(int)})printSet("Numbers squared",square)// [ 4 9 16 25 36 49 64 ]bigger:=set.Any(func(indexint,valueinterface{})bool {returnvalue.(int)>5})fmt.Println("Set contains a number bigger than 5 is ",bigger)// truepositive:=set.All(func(indexint,valueinterface{})bool {returnvalue.(int)>0})fmt.Println("All numbers are positive is",positive)// trueevenNumbersSquared:=set.Select(func(indexint,valueinterface{})bool {returnvalue.(int)%2==0}).Map(func(indexint,valueinterface{})interface{} {returnvalue.(int)*value.(int)})printSet("Chaining",evenNumbersSquared)// [ 4 16 36 64 ]}
Enumerable functions for ordered containers whose values whose elements are key/value pairs.
Each
Calls the given function once for each element, passing that element's key and value.
Each(func(keyinterface{},valueinterface{}))
Map
Invokes the given function once for each element and returns a container containing the values returned by the given function as key/value pairs.
Map(func(keyinterface{},valueinterface{}) (interface{},interface{}))Container
Select
Returns a new container containing all elements for which the given function returns a true value.
Select(func(keyinterface{},valueinterface{})bool)Container
Any
Passes each element of the container to the given function and returns true if the function ever returns true for any element.
Any(func(keyinterface{},valueinterface{})bool)bool
All
Passes each element of the container to the given function and returns true if the function returns true for all elements.
All(func(keyinterface{},valueinterface{})bool)bool
Find
Passes each element of the container to the given function and returns the first (key,value) for which the function is true or nil,nil otherwise if no element matches the criteria.
Find(func(keyinterface{},valueinterface{})bool) (interface{},interface{})
Example:
package mainimport ("fmt""github.com/emirpasic/gods/maps/treemap")funcprintMap(txtstring,m*treemap.Map) {fmt.Print(txt," { ")m.Each(func(keyinterface{},valueinterface{}) {fmt.Print(key,":",value," ")})fmt.Println("}")}funcmain() {m:=treemap.NewWithStringComparator()m.Put("g",7)m.Put("f",6)m.Put("e",5)m.Put("d",4)m.Put("c",3)m.Put("b",2)m.Put("a",1)printMap("Initial",m)// { a:1 b:2 c:3 d:4 e:5 f:6 g:7 }even:=m.Select(func(keyinterface{},valueinterface{})bool {returnvalue.(int)%2==0})printMap("Elements with even values",even)// { b:2 d:4 f:6 }foundKey,foundValue:=m.Find(func(keyinterface{},valueinterface{})bool {returnvalue.(int)%2==0&&value.(int)%3==0})iffoundKey!=nil {fmt.Println("Element with value divisible by 2 and 3 found is",foundValue,"with key",foundKey)// value: 6, index: 4}square:=m.Map(func(keyinterface{},valueinterface{}) (interface{},interface{}) {returnkey.(string)+key.(string),value.(int)*value.(int)})printMap("Elements' values squared and letters duplicated",square)// { aa:1 bb:4 cc:9 dd:16 ee:25 ff:36 gg:49 }bigger:=m.Any(func(keyinterface{},valueinterface{})bool {returnvalue.(int)>5})fmt.Println("Map contains element whose value is bigger than 5 is",bigger)// truepositive:=m.All(func(keyinterface{},valueinterface{})bool {returnvalue.(int)>0})fmt.Println("All map's elements have positive values is",positive)// trueevenNumbersSquared:=m.Select(func(keyinterface{},valueinterface{})bool {returnvalue.(int)%2==0}).Map(func(keyinterface{},valueinterface{}) (interface{},interface{}) {returnkey,value.(int)*value.(int)})printMap("Chaining",evenNumbersSquared)// { b:4 d:16 f:36 }}
All data structures can be serialized (marshalled) and deserialized (unmarshalled). Currently, only JSON support is available.
Outputs the container into its JSON representation.
Typical usage for key-value structures:
package mainimport ("encoding/json""fmt""github.com/emirpasic/gods/maps/hashmap")funcmain() {m:=hashmap.New()m.Put("a","1")m.Put("b","2")m.Put("c","3")bytes,err:=json.Marshal(m)// Same as "m.ToJSON(m)"iferr!=nil {fmt.Println(err)}fmt.Println(string(bytes))// {"a":"1","b":"2","c":"3"}}
Typical usage for value-only structures:
package mainimport ("encoding/json""fmt""github.com/emirpasic/gods/lists/arraylist")funcmain() {list:=arraylist.New()list.Add("a","b","c")bytes,err:=json.Marshal(list)// Same as "list.ToJSON(list)"iferr!=nil {fmt.Println(err)}fmt.Println(string(bytes))// ["a","b","c"]}
Populates the container with elements from the input JSON representation.
Typical usage for key-value structures:
package mainimport ("encoding/json""fmt""github.com/emirpasic/gods/maps/hashmap")funcmain() {hm:=hashmap.New()bytes:= []byte(`{"a":"1","b":"2"}`)err:=json.Unmarshal(bytes,&hm)// Same as "hm.FromJSON(bytes)"iferr!=nil {fmt.Println(err)}fmt.Println(hm)// HashMap map[b:2 a:1]}
Typical usage for value-only structures:
package mainimport ("encoding/json""fmt""github.com/emirpasic/gods/lists/arraylist")funcmain() {list:=arraylist.New()bytes:= []byte(`["a","b"]`)err:=json.Unmarshal(bytes,&list)// Same as "list.FromJSON(bytes)"iferr!=nil {fmt.Println(err)}fmt.Println(list)// ArrayList ["a","b"]}
Sort is a general purpose sort function.
Lists have an in-placeSort() function and all containers can return their sorted elements viacontainers.GetSortedValues() function.
Internally these all use theutils.Sort() method:
package mainimport"github.com/emirpasic/gods/utils"funcmain() {strings:= []interface{}{}// []strings=append(strings,"d")// ["d"]strings=append(strings,"a")// ["d","a"]strings=append(strings,"b")// ["d","a",b"strings=append(strings,"c")// ["d","a",b","c"]utils.Sort(strings,utils.StringComparator)// ["a","b","c","d"]}
Container specific operations:
// Returns sorted container''s elements with respect to the passed comparator.// Does not affect the ordering of elements within the container.funcGetSortedValues(containerContainer,comparator utils.Comparator) []interface{}
Usage:
package mainimport ("github.com/emirpasic/gods/lists/arraylist""github.com/emirpasic/gods/utils")funcmain() {list:=arraylist.New()list.Add(2,1,3)values:=GetSortedValues(container,utils.StringComparator)// [1, 2, 3]}
Collections and data structures found in other languages: Java Collections, C++ Standard Template Library (STL) containers, Qt Containers, Ruby Enumerable etc.
Fast algorithms:
- Based on decades of knowledge and experiences of other libraries mentioned above.
Memory efficient algorithms:
- Avoiding to consume memory by using optimal algorithms and data structures for the given set of problems, e.g. red-black tree in case of TreeMap to avoid keeping redundant sorted array of keys in memory.
Easy to use library:
- Well-structured library with minimalistic set of atomic operations from which more complex operations can be crafted.
Stable library:
- Only additions are permitted keeping the library backward compatible.
Solid documentation and examples:
- Learning by example.
Production ready:
- Used in production.
No dependencies:
- No external imports.
There is often a tug of war between speed and memory when crafting algorithms. We choose to optimize for speed in most cases within reasonable limits on memory consumption.
Thread safety is not a concern of this project, this should be handled at a higher level.
This takes a while, so test within sub-packages:
go test -run=NO_TEST -bench . -benchmem -benchtime 1s ./...
Biggest contribution towards this library is to use it and give us feedback for further improvements and additions.
For direct contributions,pull request into master branch or ask to become a contributor.
Coding style:
# Install tooling and set path:go install gotest.tools/gotestsum@latestgo install golang.org/x/lint/golint@latestgo install github.com/kisielk/errcheck@latestexport PATH=$PATH:$GOPATH/bin# Fix errors and warnings:go fmt ./...&&gotest -v ./...&& golint -set_exit_status ./...&&! go fmt ./...2>&1|read&&go vet -v ./...&&gocyclo -avg -over 15 ../gods&&errcheck ./...
This library is distributed under the BSD-style license found in theLICENSE file.
BrowserStack is a cloud-based cross-browser testing tool that enables developers to test their websites across various browsers on different operating systems and mobile devices, without requiring users to install virtual machines, devices or emulators.
About
GoDS (Go Data Structures) - Sets, Lists, Stacks, Maps, Trees, Queues, and much more