GoDS (Go Data Structures). Containers (Sets, Lists, Stacks, Maps, Trees), Sets (HashSet, TreeSet, LinkedHashSet), Lists (ArrayList, SinglyLinkedList, DoublyLinkedList), Stacks (LinkedListStack, ArrayStack), Maps (HashMap, TreeMap, HashBidiMap, TreeBidiMap, LinkedHashMap), Trees (RedBlackTree, AVLTree, BTree, BinaryHeap), Comparators, Iterators, Enumerables, Sort, JSON

Overview

GoDoc Build Status Go Report Card PyPI

GoDS (Go Data Structures)

Implementation of various data structures and algorithms in Go.

Data Structures

Containers

All data structures implement the container interface with the following methods:

type Container interface {
	Empty() bool
	Size() int
	Clear()
	Values() []interface{}
}

Containers are either ordered or unordered. All ordered containers provide stateful iterators and some of them allow enumerable 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
*reversible *bidirectional

Lists

A list is a data structure that stores values and may have repeated values.

Implements Container interface.

type List interface {
	Get(index int) (interface{}, bool)
	Remove(index int)
	Add(values ...interface{})
	Contains(values ...interface{}) bool
	Sort(comparator utils.Comparator)
	Swap(index1, index2 int)
	Insert(index int, values ...interface{})
	Set(index int, value interface{})

	containers.Container
	// Empty() bool
	// Size() int
	// Clear()
	// Values() []interface{}
}

ArrayList

A list backed by a dynamic array that grows and shrinks implicitly.

Implements List, IteratorWithIndex, EnumerableWithIndex, JSONSerializer and JSONDeserializer interfaces.

package main

import (
	"github.com/emirpasic/gods/lists/arraylist"
	"github.com/emirpasic/gods/utils"
)

func main() {
	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") // 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()                          // []
	list.Insert(0, "b")                   // ["b"]
	list.Insert(0, "a")                   // ["a","b"]
}

SinglyLinkedList

A list where each element points to the next element in the list.

Implements List, IteratorWithIndex, EnumerableWithIndex, JSONSerializer and JSONDeserializer interfaces.

package main

import (
	sll "github.com/emirpasic/gods/lists/singlylinkedlist"
	"github.com/emirpasic/gods/utils"
)

func main() {
	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") // 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()                          // []
	list.Insert(0, "b")                   // ["b"]
	list.Insert(0, "a")                   // ["a","b"]
}

DoublyLinkedList

A list where each element points to the next and previous elements in the list.

Implements List, IteratorWithIndex, EnumerableWithIndex, JSONSerializer and JSONDeserializer interfaces.

package main

import (
	dll "github.com/emirpasic/gods/lists/doublylinkedlist"
	"github.com/emirpasic/gods/utils"
)

func main() {
	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") // 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()                          // []
	list.Insert(0, "b")                   // ["b"]
	list.Insert(0, "a")                   // ["a","b"]
}

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 interface.

type Set interface {
	Add(elements ...interface{})
	Remove(elements ...interface{})
	Contains(elements ...interface{}) bool

	containers.Container
	// Empty() bool
	// Size() int
	// Clear()
	// Values() []interface{}
}

HashSet

A set backed by a hash table (actually a Go's map). It makes no guarantees as to the iteration order of the set.

Implements Set, JSONSerializer and JSONDeserializer interfaces.

package main

import "github.com/emirpasic/gods/sets/hashset"

func main() {
	set := hashset.New()   // empty
	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 backed by a red-black tree to keep the elements ordered with respect to the comparator.

Implements Set, IteratorWithIndex, EnumerableWithIndex, JSONSerializer and JSONDeserializer interfaces.

package main

import "github.com/emirpasic/gods/sets/treeset"

func main() {
	set := treeset.NewWithIntComparator() // empty (keys are of type int)
	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 that preserves insertion-order. Data structure is backed by a hash table to store values and doubly-linked list to store insertion ordering.

Implements Set, IteratorWithIndex, EnumerableWithIndex, JSONSerializer and JSONDeserializer interfaces.

package main

import "github.com/emirpasic/gods/sets/linkedhashset"

func main() {
	set := linkedhashset.New() // empty
	set.Add(5)                 // 5
	set.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)            // 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 interface.

type Stack interface {
	Push(value interface{})
	Pop() (value interface{}, ok bool)
	Peek() (value interface{}, ok bool)

	containers.Container
	// Empty() bool
	// Size() int
	// Clear()
	// Values() []interface{}
}

LinkedListStack

A stack based on a linked list.

Implements Stack, IteratorWithIndex, JSONSerializer and JSONDeserializer interfaces.

package main

import lls "github.com/emirpasic/gods/stacks/linkedliststack"

func main() {
	stack := lls.New()  // 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 based on a array list.

Implements Stack, IteratorWithIndex, JSONSerializer and JSONDeserializer interfaces.

package main

import "github.com/emirpasic/gods/stacks/arraystack"

func main() {
	stack := arraystack.New() // 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 interface.

type Map interface {
	Put(key interface{}, value interface{})
	Get(key interface{}) (value interface{}, found bool)
	Remove(key interface{})
	Keys() []interface{}

	containers.Container
	// 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.

type BidiMap interface {
	GetKey(value interface{}) (key interface{}, found bool)

	Map
}

HashMap

A map based on hash tables. Keys are unordered.

Implements Map, JSONSerializer and JSONDeserializer interfaces.

package main

import "github.com/emirpasic/gods/maps/hashmap"

func main() {
	m := hashmap.New() // 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 based on red-black tree. Keys are ordered with respect to the comparator.

Implements Map, IteratorWithKey, EnumerableWithKey, JSONSerializer and JSONDeserializer interfaces.

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 that preserves insertion-order. It is backed by a hash table to store values and doubly-linked list to store ordering.

Implements Map, IteratorWithKey, EnumerableWithKey, JSONSerializer and JSONDeserializer interfaces.

package main

import "github.com/emirpasic/gods/maps/linkedhashmap"

func main() {
	m := linkedhashmap.New() // 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 based on two hashmaps. Keys are unordered.

Implements BidiMap, JSONSerializer and JSONDeserializer interfaces.

package main

import "github.com/emirpasic/gods/maps/hashbidimap"

func main() {
	m := hashbidimap.New() // empty
	m.Put(1, "x")          // 1->x
	m.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->b
	m.Clear()              // empty
	m.Empty()              // true
	m.Size()               // 0
}

TreeBidiMap

A map 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 in HashBidiMap), which can be significant if contained elements are large.

Implements BidiMap, IteratorWithKey, EnumerableWithKey, JSONSerializer and JSONDeserializer interfaces.

package main

import (
	"github.com/emirpasic/gods/maps/treebidimap"
	"github.com/emirpasic/gods/utils"
)

func main() {
	m := treebidimap.NewWith(utils.IntComparator, utils.StringComparator)
	m.Put(1, "x")        // 1->x
	m.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->b
	m.Clear()            // empty
	m.Empty()            // true
	m.Size()             // 0
}

Trees

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.

Implements Container interface.

type Tree interface {
	containers.Container
	// Empty() bool
	// Size() int
	// Clear()
	// Values() []interface{}
}

RedBlackTree

A red–black tree 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

Implements Tree, ReverseIteratorWithKey, JSONSerializer and JSONDeserializer interfaces.

package main

import (
	"fmt"
	rbt "github.com/emirpasic/gods/trees/redblacktree"
)

func main() {
	tree := rbt.NewWithIntComparator() // empty (keys are of type int)

	tree.Put(1, "x") // 1->x
	tree.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
	//      └── 1

	tree.Clear() // empty
	tree.Empty() // true
	tree.Size()  // 0

	// Other:
	tree.Left() // gets the left-most (min) node
	tree.Right() // get the right-most (max) node
	tree.Floor(1) // get the floor node
	tree.Ceiling(1) // get the ceiling node
}

Extending the red-black tree's functionality has been demonstrated in the following example.

AVLTree

AVL tree 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

Implements Tree, ReverseIteratorWithKey, JSONSerializer and JSONDeserializer interfaces.


AVL tree with balance factors (green)

package main

import (
	"fmt"
	avl "github.com/emirpasic/gods/trees/avltree"
)

func main() {
	tree := avl.NewWithIntComparator() // empty(keys are of type int)

	tree.Put(1, "x") // 1->x
	tree.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
	//          └── 1

	tree.Clear() // empty
	tree.Empty() // true
	tree.Size()  // 0
}

BTree

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

Implements Tree, ReverseIteratorWithKey, JSONSerializer and JSONDeserializer interfaces.

package main

import (
	"fmt"
	"github.com/emirpasic/gods/trees/btree"
)

func main() {
	tree := btree.NewWithIntComparator(3) // empty (keys are of type int)

	tree.Put(1, "x") // 1->x
	tree.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
	//     7

	tree.Clear() // empty
	tree.Empty() // true
	tree.Size()  // 0

	// Other:
	tree.Height() // gets the height of the tree
	tree.Left() // gets the left-most (min) node
	tree.LeftKey() // get the left-most (min) node's key
	tree.LeftValue() // get the left-most (min) node's value
	tree.Right() // get the right-most (max) node
	tree.RightKey() // get the right-most (max) node's key
	tree.RightValue() // get the right-most (max) node's value
}

BinaryHeap

A binary heap is a tree 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

Implements Tree, ReverseIteratorWithIndex, JSONSerializer and JSONDeserializer interfaces.

package main

import (
	"github.com/emirpasic/gods/trees/binaryheap"
	"github.com/emirpasic/gods/utils"
)

func main() {

	// Min-heap
	heap := binaryheap.NewWithIntComparator() // empty (min-heap)
	heap.Push(2)                              // 2
	heap.Push(3)                              // 2, 3
	heap.Push(1)                              // 1, 3, 2
	heap.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)                              // 1
	heap.Clear()                              // empty
	heap.Empty()                              // true
	heap.Size()                               // 0

	// Max-heap
	inverseIntComparator := func(a, b interface{}) 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
}

Functions

Various helper functions used throughout the library.

Comparator

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 , if a < b
zero     , if a == b
positive , if a > b

Comparator signature:

type Comparator func(a, b interface{}) int

All common comparators for builtin types are included in the library:

func StringComparator(a, b interface{}) int

func IntComparator(a, b interface{}) int

func Int8Comparator(a, b interface{}) int

func Int16Comparator(a, b interface{}) int

func Int32Comparator(a, b interface{}) int

func Int64Comparator(a, b interface{}) int

func UIntComparator(a, b interface{}) int

func UInt8Comparator(a, b interface{}) int

func UInt16Comparator(a, b interface{}) int

func UInt32Comparator(a, b interface{}) int

func UInt64Comparator(a, b interface{}) int

func Float32Comparator(a, b interface{}) int

func Float64Comparator(a, b interface{}) int

func ByteComparator(a, b interface{}) int

func RuneComparator(a, b interface{}) int

func TimeComparator(a, b interface{}) int

Writing custom comparators is easy:

package main

import (
	"fmt"
	"github.com/emirpasic/gods/sets/treeset"
)

type User struct {
	id   int
	name string
}

// Custom comparator (sort by IDs)
func byID(a, b interface{}) int {

	// Type assertion, program will panic if this is not respected
	c1 := a.(User)
	c2 := b.(User)

	switch {
	case c1.id > c2.id:
		return 1
	case c1.id < c2.id:
		return -1
	default:
		return 0
	}
}

func main() {
	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}
}

Iterator

All ordered containers have stateful iterators. Typically an iterator is obtained by Iterator() function of an ordered container. Once obtained, iterator's Next() 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's Value() function. Depending on the ordering type, it's position can be obtained by iterator's Index() or Key() functions. Some containers even provide reversible iterators, essentially the same, but provide another extra Prev() 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.

IteratorWithIndex

An iterator whose elements are referenced by an index.

Typical usage:

it := list.Iterator()
for it.Next() {
	index, value := it.Index(), it.Value()
	...
}

Other usages:

if it.First() {
	firstIndex, firstValue := it.Index(), it.Value()
	...
}
for it.Begin(); it.Next(); {
	...
}

IteratorWithKey

An iterator whose elements are referenced by a key.

Typical usage:

it := tree.Iterator()
for it.Next() {
	key, value := it.Key(), it.Value()
	...
}

Other usages:

if it.First() {
	firstKey, firstValue := it.Key(), it.Value()
	...
}
for it.Begin(); it.Next(); {
	...
}

ReverseIteratorWithIndex

An iterator whose elements are referenced by an index. Provides all functions as IteratorWithIndex, but can also be used for reverse iteration.

Typical usage of iteration in reverse:

it := list.Iterator()
for it.End(); it.Prev(); {
	index, value := it.Index(), it.Value()
	...
}

Other usages:

if it.Last() {
	lastIndex, lastValue := it.Index(), it.Value()
	...
}

ReverseIteratorWithKey

An iterator whose elements are referenced by a key. Provides all functions as IteratorWithKey, but can also be used for reverse iteration.

Typical usage of iteration in reverse:

it := tree.Iterator()
for it.End(); it.Prev(); {
	key, value := it.Key(), it.Value()
	...
}

Other usages:

if it.Last() {
	lastKey, lastValue := it.Key(), it.Value()
	...
}

Enumerable

Enumerable functions for ordered containers that implement EnumerableWithIndex or EnumerableWithKey interfaces.

EnumerableWithIndex

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(index int, value interface{}))

Map

Invokes the given function once for each element and returns a container containing the values returned by the given function.

Map(func(index int, value interface{}) interface{}) Container

Select

Returns a new container containing all elements for which the given function returns a true value.

Select(func(index int, value interface{}) 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(index int, value interface{}) 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(index int, value interface{}) 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(index int, value interface{}) bool) (int, interface{})}

Example:

package main

import (
	"fmt"
	"github.com/emirpasic/gods/sets/treeset"
)

func printSet(txt string, set *treeset.Set) {
	fmt.Print(txt, "[ ")
	set.Each(func(index int, value interface{}) {
		fmt.Print(value, " ")
	})
	fmt.Println("]")
}

func main() {
	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(index int, value interface{}) bool {
		return value.(int)%2 == 0
	})
	printSet("Even numbers", even) // [ 2 4 6 8 ]

	foundIndex, foundValue := set.Find(func(index int, value interface{}) bool {
		return value.(int)%2 == 0 && value.(int)%3 == 0
	})
	if foundIndex != -1 {
		fmt.Println("Number divisible by 2 and 3 found is", foundValue, "at index", foundIndex) // value: 6, index: 4
	}

	square := set.Map(func(index int, value interface{}) interface{} {
		return value.(int) * value.(int)
	})
	printSet("Numbers squared", square) // [ 4 9 16 25 36 49 64 ]

	bigger := set.Any(func(index int, value interface{}) bool {
		return value.(int) > 5
	})
	fmt.Println("Set contains a number bigger than 5 is ", bigger) // true

	positive := set.All(func(index int, value interface{}) bool {
		return value.(int) > 0
	})
	fmt.Println("All numbers are positive is", positive) // true

	evenNumbersSquared := set.Select(func(index int, value interface{}) bool {
		return value.(int)%2 == 0
	}).Map(func(index int, value interface{}) interface{} {
		return value.(int) * value.(int)
	})
	printSet("Chaining", evenNumbersSquared) // [ 4 16 36 64 ]
}

EnumerableWithKey

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(key interface{}, value interface{}))

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(key interface{}, value interface{}) (interface{}, interface{})) Container

Select

Returns a new container containing all elements for which the given function returns a true value.

Select(func(key interface{}, value interface{}) 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(key interface{}, value interface{}) 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(key interface{}, value interface{}) 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(key interface{}, value interface{}) bool) (interface{}, interface{})

Example:

package main

import (
	"fmt"
	"github.com/emirpasic/gods/maps/treemap"
)

func printMap(txt string, m *treemap.Map) {
	fmt.Print(txt, " { ")
	m.Each(func(key interface{}, value interface{}) {
		fmt.Print(key, ":", value, " ")
	})
	fmt.Println("}")
}

func main() {
	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(key interface{}, value interface{}) bool {
		return value.(int) % 2 == 0
	})
	printMap("Elements with even values", even) // { b:2 d:4 f:6 }

	foundKey, foundValue := m.Find(func(key interface{}, value interface{}) bool {
		return value.(int) % 2 == 0 && value.(int) % 3 == 0
	})
	if foundKey != 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(key interface{}, value interface{}) (interface{}, interface{}) {
		return key.(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(key interface{}, value interface{}) bool {
		return value.(int) > 5
	})
	fmt.Println("Map contains element whose value is bigger than 5 is", bigger) // true

	positive := m.All(func(key interface{}, value interface{}) bool {
		return value.(int) > 0
	})
	fmt.Println("All map's elements have positive values is", positive) // true

	evenNumbersSquared := m.Select(func(key interface{}, value interface{}) bool {
		return value.(int) % 2 == 0
	}).Map(func(key interface{}, value interface{}) (interface{}, interface{}) {
		return key, value.(int) * value.(int)
	})
	printMap("Chaining", evenNumbersSquared) // { b:4 d:16 f:36 }
}

Serialization

All data structures can be serialized (marshalled) and deserialized (unmarshalled). Currently only JSON support is available.

JSONSerializer

Outputs the container into its JSON representation.

Typical usage for key-value structures:

package main

import (
	"fmt"
	"github.com/emirpasic/gods/maps/hashmap"
)

func main() {
	m := hashmap.New()
	m.Put("a", "1")
	m.Put("b", "2")
	m.Put("c", "3")

	json, err := m.ToJSON()
	if err != nil {
		fmt.Println(err)
	}
	fmt.Println(string(json)) // {"a":"1","b":"2","c":"3"}

Typical usage for value-only structures:

package main

import (
	"fmt"
	"github.com/emirpasic/gods/lists/arraylist"
)

func main() {
	list := arraylist.New()
	list.Add("a", "b", "c")

	json, err := list.ToJSON()
	if err != nil {
		fmt.Println(err)
	}
	fmt.Println(string(json)) // ["a","b","c"]
}

JSONDeserializer

Populates the container with elements from the input JSON representation.

Typical usage for key-value structures:

package main

import (
	"fmt"
	"github.com/emirpasic/gods/maps/hashmap"
)

func main() {
	hm := hashmap.New()

	json := []byte(`{"a":"1","b":"2"}`)
	err := hm.FromJSON(json)
	if err != nil {
		fmt.Println(err)
	}
	fmt.Println(hm) // HashMap map[b:2 a:1]
}

Typical usage for value-only structures:

package main

import (
	"fmt"
	"github.com/emirpasic/gods/lists/arraylist"
)

func main() {
	list := arraylist.New()

	json := []byte(`["a","b"]`)
	err := list.FromJSON(json)
	if err != nil {
		fmt.Println(err)
	}
	fmt.Println(list) // ArrayList ["a","b"]
}

Sort

Sort is a general purpose sort function.

Lists have an in-place Sort() function and all containers can return their sorted elements via containers.GetSortedValues() function.

Internally these all use the utils.Sort() method:

package main

import "github.com/emirpasic/gods/utils"

func main() {
	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

Container specific operations:

// Returns sorted container''s elements with respect to the passed comparator.
// Does not effect the ordering of elements within the container.
func GetSortedValues(container Container, comparator utils.Comparator) []interface{}

Usage:

package main

import (
	"github.com/emirpasic/gods/lists/arraylist"
	"github.com/emirpasic/gods/utils"
)

func main() {
	list := arraylist.New()
	list.Add(2, 1, 3)
	values := GetSortedValues(container, utils.StringComparator) // [1, 2, 3]
}

Appendix

Motivation

Collections and data structures found in other languages: Java Collections, C++ Standard Template Library (STL) containers, Qt Containers, Ruby Enumerable etc.

Goals

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.

Testing and Benchmarking

This takes a while, so test within sub-packages:

go test -run=NO_TEST -bench . -benchmem -benchtime 1s ./...

Contributing

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 get github.com/golang/lint/golint
go get github.com/fzipp/gocyclo
go get github.com/kisielk/errcheck
export PATH=$PATH:$GOPATH/bin

# Fix errors and warnings:
go fmt ./... && gofmt -s -w . && go vet ./... && go get ./... && go test ./... && golint ./... && gocyclo -avg -over 15 . && errcheck ./...

License

This library is distributed under the BSD-style license found in the LICENSE file.

Sponsors

BrowserStack

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.

Issues
  • What do you think about Enumerator?

    What do you think about Enumerator?

    What do you think about Enumerator? In offical library, there is "container/list", it contains Element, that can take values one by one. I think it takes less complex then every time find it.

    new feature 
    opened by wildfire810 13
  • Access value in key comparator

    Access value in key comparator

    I want to implement a structure base on TreeMap where I have IP addresses as the key and a TreeSet as the value. I want to be able to sort the TreeMap using the size() of the TreeSet. This is currently impossible because the comparator can only access either the keys or values.

    For example:

    m := treemap.NewWith(myComparator)
    
    s1 := treeset.NewWithIntComparator()
    s1.Add(2, 2, 3, 4, 5) 
    
    s2 := treeset.NewWithIntComparator()
    s2.Add(7, 8, 9) 
    
    m.Put("server1", s1)
    m.Put("server2", s2)
    

    Unfortunately, the myComparator can only access the keys:

    func myComparator(a, b interface{}) int {
        // a and b are the keys
    }
    

    What do you think about adding access to the values for key comparators used by maps?

    question 
    opened by F21 11
  • Treeset iterator is broken

    Treeset iterator is broken

    How to reproduce:

    import "github.com/emirpasic/gods/sets/treeset"
    
    var tree  *treeset.Set
    tree = treeset.NewWith(someComparator)
    for _, v := range someItems {
        tree.Add(v)
    }
    items := tree.Iterator()
    for items.Next() {
        // infinite loop!
    }
    
    bug 
    opened by grglcs 10
  • Enumerable chaining

    Enumerable chaining

    I noticed you have Map and Select method commented out in EnumerableWithIndex and EnumerableWithKey interfaces since returning a container will require type assertion at every step, pretty ugly for chaining.

    I would suggest returning EnumerableWithIndex (or EnumerableWithKey) for those methods and add a ToContainer method at the end.

    This would allow API calls like:

    f1 := func(index int, value interface{}) interface{} { // some mapping }
    f2 := func(index int, value interface{}) interface{} { // some other mapping }
    f3 := func(index int, value interface{}) bool { // some filtering }
    
    list.Map(f1).Map(f2).Select(f3).toContainer()
    

    At the end, the user is free to do any type assertion as they want.

    discussion question 
    opened by imulab 10
  • Is there a map comparator that simply retains the order of insertion?

    Is there a map comparator that simply retains the order of insertion?

    I am using code that collects KV pairs in a map[string]interface{}. Because it's Go, when json.Unmarshal() iterates over the keys, they come out in a random order. This does not work for my purposes; I need the keys to iterate in the same order in which they were inserted.

    Your TreeMap maintains an ordered set of keys, based on a comparator. Does a comparator exist, or can one be built, that sorts the keys based on the order of their insertion? And if so, would the JSON interface then serialize these keys in the insertion order?

    Thank you.

    new feature 
    opened by MartinDelVecchio 8
  • Implement json.Marshaller interface

    Implement json.Marshaller interface

    Not sure if this is possible, but it would be nice if there were a way to implement a default json marshaling implementation so that the collection data can be exported as json.

    new feature 
    opened by saheljalal 8
  • Int pairs

    Int pairs

    Hi,

    I use pairs of ints which are id's for my data. These are 'maps' - relations between two data. What data structure do you suggest I use? Treemap.Map would seem slow for lookup because I can only Get by Key and I'd like to Get by Key or Value.

    If I use 2 lists or 2 sets the int pairs will not align.

    Should I just use a 2 dimensional int slice? [][]int{}

    Thanks.

    new feature 
    opened by 5k3105 7
  • Add Ceiling and Floor functions to redblacktree

    Add Ceiling and Floor functions to redblacktree

    Request: The redblacktree implementation now is :sparkles: great :sparkles: , and it would be nicer to have Ceiling and Floor functions.

    Reasons: Ceiling and Floor functions are frequently used, and are almost standard functions for tree data structure.

    My implementation: I implemented these two functions in an iterative way. It's time complexity is O(log(N)), and space complexity is O(1). I also implemented test cases for these two functions.

    opened by otnt 7
  • gods breaks the world (a.k.a. sort considered harmful)

    gods breaks the world (a.k.a. sort considered harmful)

    tl;dr for later readers who come here from google -- see the more concise dockerized example in https://github.com/emirpasic/gods/issues/123#issuecomment-539232054

    Can we rename the sort example to something like godsort?

    • The name sort conflicts with a basic system command.
    • Many/most go tutorials tell the user to put $GOPATH/bin at the front of their $PATH.
    • Other tutorials recommend appending ... to a project path to install all of the child packages.

    That combination of factors will break a UNIX or Linux machine. Here's a fun example:

    $ which sort
    /usr/bin/sort
    $ sort /etc/hosts | wc -l
    103
    $ go get github.com/emirpasic/gods
    can't load package: package github.com/emirpasic/gods: no Go files in /home/stevegt/go/1.12.7/src/github.com/emirpasic/gods
    $ go get github.com/emirpasic/gods/...  # ok, then maybe I'm supposed to do this...
    
    [... time passes, we forget we even installed gods that way ...]
    
    $ hash -r
    $ sort /etc/passwd | wc -l
    0
    

    Without the explicit hash -r, the failure mode is even more subtle, only showing up in new shells. I'm going to take the time to add some detail here, both as background and as google fodder for anyone else hitting this.

    In my case the first symptoms were that vim-go wasn't running guru correctly a day after I installed a bunch of go dev bits. I spent a while troubleshooting vim-go, finally tracked it down to goenv, and then noticed that both pyenv init - and goenv init - were throwing errors when opening new xterms. Here's one of the error messages:

    -bash: eval: line 188: syntax error near unexpected token `)'
    -bash: eval: line 188: `  )'
    

    That's it. The entirety of the message. That message was showing up when .bashrc ran eval "$(pyenv init -)". The message originated several shell scripts deep, in some code which was supposed to collect, sort, and uniq the content of $HOME/.pyenv/libexec and include it to the left of a ) in a case statement in a shell script that is generated on the fly and returned to the above eval. (Fun, right?)

    It happens that goenv and pyenv use the same algorithm and similar shell scripts.

    I found myself adding lots of echo statements to those various shell scripts trying to narrow it down -- never tried actually testing the output of sort itself until hours later, partly because it's buried in the middle of a pipeline. Even after I broke up the pipeline into little pieces and found the empty sort output, it still took me a few minutes to figure out what happened:

    $ echo foo | sort    # what, no output?
    $ sort    # not waiting on stdin either?
    $ sort -h   # what?
    $ sort --help  # um.
    $ which sort
    /home/stevegt/go/1.12.7/bin/sort
    $ strings /home/stevegt/go/1.12.7/bin/sort | tail
    github.com/emirpasic/gods/utils.StringComparator
    github.com/emirpasic/gods/utils.sortable.Len
    github.com/emirpasic/gods/utils.sortable.Swap
    github.com/emirpasic/gods/utils.sortable.Less
    github.com/emirpasic/gods/utils.init
    github.com/emirpasic/gods/utils.(*sortable).Len
    github.com/emirpasic/gods/utils.(*sortable).Less
    github.com/emirpasic/gods/utils.(*sortable).Swap
    main.main
    main.init
    
    bug discussion question 
    opened by stevegt 5
  • Iterator  support seek ?

    Iterator support seek ?

    Any follow up plan to add "seek" function for treemap ? like:

    	it := m.Iterator()
    	prefix :="1234"
            it.Seek(prefix)
    	for it.Next() {
    		...
    	}
    
    new feature 
    opened by zhengxiaochuan-3 5
  • better and more idiomatic support for JSON marshalling/unmarshalling

    better and more idiomatic support for JSON marshalling/unmarshalling

    I would love to see standard MarshalJSON / UnmarshalJSON (and their streaming Encode/Decode counterparts) support. This would allow us to persist complex structs using data structures without having to manually implement JSON reading/writing

    opened by genez 5
  • Speed up LinkedHashMap remove() function to O(1)

    Speed up LinkedHashMap remove() function to O(1)

    LinkedHashMap is currently implemented using a combination of map and Doubly Linked List but takes O(n) time to remove an element. The implementation should use a reference to the node in the doubly linked list where the element is stored and should be removed in O(1). Also, the remove method first tries to find the index in O (n) and then remove the element in O(n). It can be easily optimized to do it in O(n).

    opened by chaitanya0411 0
  • linkedhashmap maintaining order only on first level? Is there any data structure that holds order in nested maps also?

    linkedhashmap maintaining order only on first level? Is there any data structure that holds order in nested maps also?

    https://play.golang.org/p/AIAkjs_TELp If we see above example. linkedhashmap is maintaining the order only on firsl level of keys. It is not maintaining the same for nested keys or maps. Do we have any data structure that holds order in nested keys also?

    Input:

    {"pulse_in_sec":60,"pulse_count":1,"rate":1.0,"slabs":["1-50"],"billplan_hierarchy":{"direction":"outgoing","legType":"pstn","callType":"trans","endUserCircleMask":"intra"}}
    

    Expected:

    map[pulse_in_sec:60 pulse_count:1 rate:1 slabs:[1-50] billplan_hierarchy:map[direction:outgoing legType:pstn  callType:trans endUserCircleMask:intra]]
    

    Ouput:

    map[pulse_in_sec:60 pulse_count:1 rate:1 slabs:[1-50] billplan_hierarchy:map[callType:trans direction:outgoing endUserCircleMask:intra legType:pstn]]
    
    new feature discussion question 
    opened by punithck 1
Releases(v1.18.1)
  • v1.18.1(Apr 18, 2022)

  • v1.18.0(Apr 14, 2022)

  • v1.17.0(Apr 13, 2022)

  • v1.16.0(Apr 12, 2022)

  • v1.15.1(Apr 12, 2022)

    • [x] ToString() util function optimization
    • [x] String() interface function for Container interface to be implemented by all data structures
    Source code(tar.gz)
    Source code(zip)
  • v1.15.0(Apr 12, 2022)

  • v1.14.0(Apr 12, 2022)

    • [x] GetNode() to find node in AVLTree, BTree, and RedBlackTree by key
    • [x] Size() function for the tree node of AVLTree, BTree, and RedBlackTree to dynamically calculate the size of the subtree
    • [x] Node() function of the iterators for AVLTree, BTree, and RedblackTree to return the actual node at the current iterator position
    Source code(tar.gz)
    Source code(zip)
  • v1.13.0(Apr 11, 2022)

  • v1.12.1(Sep 22, 2018)

  • v1.11.0(Sep 21, 2018)

  • v1.10.0(Sep 20, 2018)

    • [x] List set method `list.Set(index, interface{}) https://github.com/emirpasic/gods/pull/87
    • [x] TreeBidiMap fix to panic on first invalid type according to comparator https://github.com/emirpasic/gods/commit/370f7ab252bf7f9f3e8832a0d67c06aee657d027
    • [x] Array list optimization https://github.com/emirpasic/gods/pull/76
    • [x] Documentation updates
    Source code(tar.gz)
    Source code(zip)
  • v1.9.0(Mar 6, 2017)

  • v1.8.1(Mar 5, 2017)

  • v1.8.0(Mar 5, 2017)

  • v1.7.0(Mar 3, 2017)

  • v1.6.0(Sep 17, 2016)

    • [x] Added comparators for most common builting types (string, int, int8, int16, int32, int64, uint, uint8, uint16, uint32, uint64, float32, float64, byte, rune)
    Source code(tar.gz)
    Source code(zip)
  • v1.5.2(Sep 7, 2016)

  • v1.5.1(Sep 7, 2016)

  • v1.5.0(Jul 16, 2016)

    • [x] B tree implementation #26
    • [x] Red-black tree returning all keys and values optimization to use its own iterator rather than stack #26
    • [x] Test for insertion, deletions and search #26
    Source code(tar.gz)
    Source code(zip)
  • v1.4.0(Jul 3, 2016)

  • v1.3.0(Jul 2, 2016)

  • v1.2.0(Jun 27, 2016)

    New features:

    • [x] Iterators extended:
      • [x] Begin() for iterators to reset iterator (one-before-first).
      • [x] End() for iterators to move iterator past the end (one-past-the-end).
      • [x] First() for iterators to jump to first element.
      • [x] Last() for reversible iterators to jump to last element.

    Fixes and Improvements:

    • [x] RebBlackTree iterator to be explicit about its state

    #20

    Source code(tar.gz)
    Source code(zip)
  • v1.1.0(Jun 25, 2016)

  • v1.0.0(Sep 22, 2018)

    This is is the first official production-ready release that matured for a year. There were no issues throughout the year, so we feel comfortable calling this v1.0.0.

    • [x] Containers
      • [x] Lists
        • [x] ArrayList
        • [x] SinglyLinkedList
        • [x] DoublyLinkedList
      • [x] Sets
        • [x] HashSet
        • [x] TreeSet
      • [x] Stacks
        • [x] LinkedListStack
        • [x] ArrayStack
      • [x] Maps
        • [x] HashMap
        • [x] TreeMap
      • [x] Trees
        • [x] RedBlackTree
        • [x] BinaryHeap
    • [x] Functions
      • [x] Comparator
      • [x] Iterator
        • [x] IteratorWithIndex
        • [x] IteratorWithKey
      • [x] Enumerable
        • [x] EnumerableWithIndex
        • [x] EnumerableWithKey
      • [x] Sort
      • [x] Container
    • [x] Appendix
    Source code(tar.gz)
    Source code(zip)
Owner
Emir Pasic
Emir Pasic
A simple Set data structure implementation in Go (Golang) using LinkedHashMap.

Set Set is a simple Set data structure implementation in Go (Golang) using LinkedHashMap. This library allow you to get a set of int64 or string witho

Studio Sol Comunicação Digital Ltda 21 Apr 6, 2022
BTree provides a simple, ordered, in-memory data structure for Go programs.

BTree implementation for Go This package provides an in-memory B-Tree implementation for Go, useful as an ordered, mutable data structure. The API is

Google 2.7k May 17, 2022
Distributed merge sort for large sets across nodes in a network

distMergeSort An implementation of mergesort distributed across nodes used to sort large sets. Introduction Merge sort partitions sets so that they ca

Elton SV 11 Nov 9, 2021
Tutorial code for my video Learn to Use Basic Data Structures - Slices, Structs and Maps in Golang

Learn to Use Basic Data Structures - Slices, Structs and Maps in Golang Read text from a file and split into words. Introduction to slices / lists. Co

null 0 Jan 26, 2022
Go implementation of C++ STL iterators and algorithms.

iter Go implementation of C++ STL iterators and algorithms. Less hand-written loops, more expressive code. README translations: 简体中文 Motivation Althou

disksing 156 May 2, 2022
A Golang lock-free thread-safe HashMap optimized for fastest read access.

hashmap Overview A Golang lock-free thread-safe HashMap optimized for fastest read access. Usage Set a value for a key in the map: m := &HashMap{} m.S

Cornel 1.1k May 7, 2022
A simple and efficient thread-safe sharded hashmap for Go

shardmap A simple and efficient thread-safe sharded hashmap for Go. This is an alternative to the standard Go map and sync.Map, and is optimized for w

Josh Baker 190 Apr 13, 2022
Package iter provides generic, lazy iterators, functions for producing them from primitive types, as well as functions and methods for transforming and consuming them.

iter Package iter provides generic, lazy iterators, functions for producing them from primitive types, as well as functions and methods for transformi

Matthew Toohey 21 May 6, 2022
Stalin sort in multiple languages!

stalin-sort Stalin sort in multiple languages, contributions are welcome! Motivation This repo is motivated by this tweet, this tweet contains a refer

CaKrome 0 Jan 14, 2022
Code in this repository solves the game Water Sort Puzzle for phones

Water Sort Puzzle Solver This code can solve a game called "Water Sort Puzzle" available on APPStore and PlayMarket. Start Guide Firstly, you have to

Pavel Kositsyn 6 Apr 5, 2022
Implementation of external merge sort with 2-way merge.

External merge sort An implementation of external merge sort algorithm (with 2-way merge) written in Go. This particular implementation sorts strings.

Igor Baliuk 0 Jan 16, 2022
Smartsort - A smart sorting algorithm for Go to sort filename containing digits that is not zero padded

smartsort A smart sorting algorithm for Go to sort filename containing digits th

Toby Chui 1 Mar 26, 2022
estruct traverses javascript projects and maps all the dependencies and relationships to a JSON. the output can be used to build network visualizations of the project and document the architecture.

EStruct traverses javascript projects and maps all the dependencies and relationships to a JSON. The output can be used to build network visualizations of the project and document the architecture.

Ray Luxembourg 11 Jan 27, 2022
A tree like tool help you to explore data structures in your redis server

Redis-view is a tree like tool help you explore data structures in your redis server

dreamersdw 19 Mar 17, 2022
Probabilistic data structures for processing continuous, unbounded streams.

Boom Filters Boom Filters are probabilistic data structures for processing continuous, unbounded streams. This includes Stable Bloom Filters, Scalable

Tyler Treat 1.4k May 19, 2022
Graph algorithms and data structures

Your basic graph Golang library of basic graph algorithms Topological ordering, image by David Eppstein, CC0 1.0. This library offers efficient and we

Algorithms to Go 545 May 12, 2022
Graph algorithms and data structures

Your basic graph Golang library of basic graph algorithms Topological ordering, image by David Eppstein, CC0 1.0. This library offers efficient and we

Algorithms to Go 9 Jan 25, 2021
This is the course materials for the Go Data Structures Crash Course!

Go Data Structures Course ?? Welcome Gophers! This is the official repository that contains all of the data structures we cover in the Go Data Structu

TutorialEdge 9 May 10, 2022
Basic Implementation of Data-structures in Go

Data structures in Go v1.15.6 This repo consists the implementation of the following: Stacks Queues Linked Lists (Singly) Binary Search Trees Heaps (M

Shehab Abdel-Salam 4 May 24, 2021