Collections#

Collection of generic data structures in Go 📦

• Collections
  • Project Description
  • Installation
  • Quickstart
    • Set
    • Stack
    • Queue
    • List
    • Ordered Map
    • DAG
    • Counter
    • Chain
    • Priority Queue

Project Description#

Small, useful, zero dependency implementations of generic collection data structures in Go:

• Set: Offers fast membership checking as well as difference, intersection etc.
• Stack: Simple LIFO stack
• Queue: Simple FIFO queue
• List: A doubly-linked list
• OrderedMap: A map that remembers the order in which keys were inserted
• DAG: A generic directed acyclic graph
• Counter: A convenient construct for counting occurrences of things (similar to Python's collections.Counter)
• Chain: A chain of maps, lookups first look in one map, then the next, then the next, returning the first result found (similar to Python's collections.ChainMap)
• Priority Queue A queue where items are popped according to order of priority

Installation#

go get go.followtheprocess.codes/collections@latest

Quickstart#

Set#

A set is an unordered collection of unique items offering fast lookup and membership checking.

// Initialise a new set with a concrete type
s := set.New[string]()

// Pre-size if you know the expected population, or build from existing data
_ = set.WithCapacity[string](1024)
_ = set.From([]string{"built", "from", "a", "slice"})
_ = set.Collect(slices.Values([]string{"from", "an", "iterator"}))

// Insert items to the set
s.Insert("hello")
s.Insert("sets")
s.Insert("in")
s.Insert("go")

// All the methods you'd expect
s.Contains("hello") // true
s.Size() // 4

// Remove an item,
s.Remove("go")
s.Size() // 3

// Rich comparison with other sets
other := set.New[string]()
other.Insert("hello")
other.Insert("more")

// Union: combine both sets into one
set.Union(s, other) // ["hello", "in", "sets", "more"]

// Intersection: all items present in both sets
set.Intersection(s, other) // ["hello"]

// Difference: items in s but not in other
set.Difference(s, other) // ["sets", "in"]

// Symmetric difference: items in exactly one of the two sets
set.SymmetricDifference(s, other) // ["sets", "in", "more"]

// Set predicates
set.IsDisjoint(s, other) // false — they share "hello"
set.IsSubset(s, other)   // false
set.IsSuperset(s, other) // false

Stack#

A stack is a LIFO data structure useful in a variety of situations.

// Initialise a new stack with a concrete type
s := stack.New[string]()

// Push items onto the stack
s.Push("hello")
s.Push("stacks")
s.Push("in")
s.Push("go")

s.Size() // 4

// Pop items off the stack in LIFO order
item, _ := s.Pop()
fmt.Println(item) // "go"

item, _ = s.Pop()
fmt.Println(item) // "in"

item, _ = s.Pop()
fmt.Println(item) // "stacks"

item, _ = s.Pop()
fmt.Println(item) // "hello"

// Popping from an empty stack returns the zero value and ok = false
item, ok := s.Pop()
fmt.Println(item, ok) // "", false

Queue#

A queue is a FIFO data structure useful in a variety of situations.

// Initialise a new queue with a concrete type
q := queue.New[string]()

// Push items into the back of the queue
q.Push("hello")
q.Push("queues")
q.Push("in")
q.Push("go")

q.Size() // 4

// Pop items off the front of the queue
item, _ := q.Pop()
fmt.Println(item) // "hello"

item, _ = q.Pop()
fmt.Println(item) // "queues"

item, _ = q.Pop()
fmt.Println(item) // "in"

item, _ = q.Pop()
fmt.Println(item) // "go"

// Popping from an empty queue returns the zero value and ok = false
item, ok := q.Pop()
fmt.Println(item, ok) // "", false

List#

A doubly linked list is a data structure where nodes wrap the data and point to their next and previous nodes. It offers cheap insertion and removal.

// Initialise a new list holding a string as the data
l := list.New[string]()

// Bolt things on the end
l.Append("one")
l.Append("two")

// Push things at the start
l.Prepend("before")

// Last returns (*Node, bool) — ok is false when the list is empty.
last, ok := l.Last()
if !ok {
    // list is empty
}
fmt.Println(last.Item()) // <- Last is a Node, so you must call .Item() to get underlying data

Ordered Map#

An ordered map is like the Go standard map, except it remembers the order in which items were inserted.

m := orderedmap.New[int, string]()

// Insert key value pairs
m.Insert(1, "one")
m.Insert(2, "two")
m.Insert(3, "three")

one, ok := m.Get(1) // Fetch them back out, same API as go map
if !ok {
    fmt.Println("1 was missing!")
}

two, existed := m.Remove(2) // Removal returns what was in the map

oldestKey, oldestVal, ok := m.Oldest() // Get the first inserted thing (there's also a Newest())

DAG#

A DAG (Directed Acyclic Graph) is an ordered graph ideal for task orchestration and dependency management.

// Create a new DAG storing integers as the vertex data type, and a unique ID
// for each vertex of a string (this must uniquely identify a single vertex in the graph)
graph := dag.New[string, int]()

_ = graph.AddVertex("one", 1) // Add a vertex named "one" storing the integer 1
_ = graph.AddVertex("two", 2) // Add a vertex named "two" storing the integer 2

// Connect the two vertices, "two" depends on "one"
_ = graph.AddEdge("one", "two")

// Topologically sort the graph
order, err := graph.Sort()

Counter#

A convenient construct to count occurrences of comparable items.

counts := counter.New[string]()

// Count fruits
counts.Add("apple")
counts.Add("apple")
counts.Add("apple")
counts.Add("orange")
counts.Add("orange")
counts.Add("raspberry")

// How many apples?
counts.Get("apple") // 3

// How many fruits in total?
counts.Sum() // 6

// What's the most common fruit — MostCommon takes n and returns the top-n pairs
counts.MostCommon(1) // [{Item: "apple", Count: 3}]

// Iterate every (item, count) pair in descending count order
for item, count := range counts.Descending() {
    // "apple" 3, "orange" 2, "raspberry" 1
    _, _ = item, count
}

Chain#

A chain of maps who's values are looked up in order. If the value isn't in the first map, it falls through to the second etc. Fresh inserts always go to the first map, updates update the value in whichever map it's first found in.

maps := []map[int]string{
    {
        1: "one in first map",
        2: "two in first map",
    },
    {
        1: "one in second map",
        2: "two in second map",
        3: "three in second map",
    },
    {
        1: "one in third map",
        2: "two in third map",
        3: "three in third map",
        4: "four in third map",
    },
    }

    chain := chain.From(maps)

    // 1 is in the first map in the chain
    chain.Get(1) // -> "one in first map", true 

    // To get 4, we look through every map until it's found
    chain.Get(4) // -> "four in third map", true

    // 5 isn't in any map
    chain.Get(5) // -> "", false

Priority Queue#

q := priority.New[string]()

// Add strings and their priorities (note out of order)
// highest priority wins
q.Push("two", 2)
q.Push("one", 1)
q.Push("three", 3)
q.Push("four", 4)

item, ok := q.Pop() // -> "four", true
item, ok = q.Pop()  // -> "three", true
item, ok = q.Pop()  // -> "two", true
item, ok = q.Pop()  // -> "one", true

// Pop from empty queue returns the zero value and ok = false
item, ok := q.Pop() // -> "", false