emirpasic / gods

среда, 29 июня 2016 г. в 03:14:11

Go
Go Data Structures. Containers, Sets, Lists, Stacks, Maps, Trees, HashSet, TreeSet, ArrayList, SinglyLinkedList, DoublyLinkedList, LinkedListStack, ArrayStack, HashMap, TreeMap, RedBlackTree, BinaryHeap, Comparator, Iterator, Enumerable, Sort

GoDS (Go Data Structures)

Implementation of various data structures and algorithms in Go.

Data Structures

Containers
- Lists
- Sets
  - HashSet
  - TreeSet
- Stacks
  - LinkedListStack
  - ArrayStack
- Maps
  - HashMap
  - TreeMap
- Trees
  - RedBlackTree
  - BinaryHeap
Functions
Appendix

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.

Container	Ordered	Iterator	Enumerable	Ordered by
ArrayList	yes	yes*	yes	index
SinglyLinkedList	yes	yes	yes	index
DoublyLinkedList	yes	yes*	yes	index
HashSet	no	no	no	index
TreeSet	yes	yes*	yes	index
LinkedListStack	yes	yes	no	index
ArrayStack	yes	yes*	no	index
HashMap	no	no	no	key
TreeMap	yes	yes*	yes	key
RedBlackTree	yes	yes*	no	key
BinaryHeap	yes	yes*	no	index
		_^*reversible

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{})

    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 and EnumerableWithIndex 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 and EnumerableWithIndex 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 and EnumerableWithIndex 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 structed 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 interface.

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 and EnumerableWithIndex 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
}

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 and IteratorWithIndex 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 and IteratorWithIndex 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{}
}

HashMap

A map based on hash tables. Keys are unordered.

Implements Map interface.

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 ordered with respect to the comparator.

Implements Map, IteratorWithKey and EnumerableWithKey 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.
}

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 and IteratorWithKey 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(m)
    //
    //  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(m)
    //
    //  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.

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 and IteratorWithIndex 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)                                    // 2
    heap.Push(3)                                    // 3, 2
    heap.Push(1)                                    // 3, 2, 1
    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

Two common comparators are included in the library:

func IntComparator(a, b interface{}) int

func StringComparator(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.

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 }
}

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.

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

go test -v -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 or ask to become a contributor.

Coding style:

# Install tooling:
go build github.com/golang/lint/golint
go build github.com/fzipp/gocyclo

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

License

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