Skip to content

oleiade/lane

Repository files navigation

Lane

MIT License Build Status Go Documentation Go Report Card Go Version

The Lane package provides textbook implementations of generic Queue, PriorityQueue, Stack, and Deque data structures. Its design focuses on simplicity, performance, and concurrent usage.

Installation

Using this package requires a working Go environment. See the install instructions for Go.

This package requires a modern version of Go supporting modules: see the go blog guide on using Go Modules.

Using v2 releases

go get github.com/oleiade/lane/v2
...
import (
 "github.com/oleiade/lane/v2"
)
...

Using v1 releases

go get github.com/oleiade/lane
...
import (
 "github.com/oleiade/lane"
)
...

Usage/Examples

Priority queue

PriorityQueue implements a heap priority queue data structure. It can be either max (descending) or min (ascending) ordered. Every operation on a PriorityQueue is goroutine-safe. It performs Push and Pop operations in O(log N) time.

Example

// Create a new max ordered priority queue
priorityQueue := NewMaxPriorityQueue[string, int]()

// And push some prioritized content into it
priorityQueue.Push("easy as", 3)
priorityQueue.Push("123", 2)
priorityQueue.Push("do re mi", 4)
priorityQueue.Push("abc", 1)

// Take a look at the min element in
// the priority queue
headValue, headPriority, ok := priorityQueue.Head()
if ok {
    fmt.Println(headValue)    // "abc"
    fmt.Println(headPriority) // 1
}

// The operations seem to preserve the song order
jacksonFive := make([]string, priorityQueue.Size())

for i := 0; i < len(jacksonFive); i++ {
    value, _, _ := priorityQueue.Pop()
    jacksonFive[i] = value
}

fmt.Println(strings.Join(jacksonFive, " "))

Deque

Deque implements a head-tail linked list data structure. Built upon a doubly linked list container, every operation performed on a Deque happen in O(1) time complexity. Every operation on a Deque are goroutine-safe.

Users have the option to instantiate Deques with a limited capacity using the dedicated NewBoundDeque constructor. When a bound Deque is full, the Append and Prepend operations fail.

Deque example

// Create a new Deque data structure
deque := NewDeque[string]()

// And push some content into it using the Append
// and Prepend methods
deque.Append("easy as")
deque.Prepend("123")
deque.Append("do re mi")
deque.Prepend("abc")

// Take a look at what the first and
// last element stored in the Deque are.
firstValue, ok := deque.First()
if ok {
    fmt.Println(firstValue) // "abc"
}

lastValue, ok := deque.Last()
if ok {
    fmt.Println(lastValue) // 1
}

// Use the `Pop` and `Shift`
// methods to bring the song words together
jacksonFive := make([]string, deque.Size())

for i := 0; i < len(jacksonFive); i++ {
    value, ok := deque.Shift()
    if ok {
        jacksonFive[i] = value
    }
}

// abc 123 easy as do re mi
fmt.Println(strings.Join(jacksonFive, " "))

Queue

Queue is a FIFO (First In First Out) data structure implementation. Built upon a Deque container, it focuses its API on the following core functionalities: Enqueue, Dequeue, Head. Every operation on a Queue has a time complexity of O(1). Every operation on a Queue is goroutine-safe.

Queue example

// Create a new queue and pretend to handle Starbucks clients
queue := NewQueue[string]()

// Add the incoming clients to the queue
queue.Enqueue("grumpyClient")
queue.Enqueue("happyClient")
queue.Enqueue("ecstaticClient")

fmt.Println(queue.Head()) // grumpyClient

// Handle the clients asynchronously
for {
    client, ok := queue.Dequeue()
    if !ok {
        break
    }

    fmt.Println(client)
}

Stack

Stack implements a Last In First Out data structure. Built upon a Deque container, its API focuses on the following core functionalities: Push, Pop, Head. Every operation on a Stack has a time complexity of O(1). Every operation on a Stack is goroutine-safe.

Stack example

// Create a new stack and put some plates over it
stack := NewStack[string]()

// Put some plates on the stack
stack.Push("redPlate")
stack.Push("bluePlate")
stack.Push("greenPlate")

fmt.Println(stack.Head()) // greenPlate

// Check the top of the stack
value, ok := stack.Pop()
if ok {
    fmt.Println(value) // greenPlate
}

stack.Push("yellowPlate")

value, ok = stack.Pop()
if ok {
    fmt.Println(value) // yellowPlate
}

// Check the top of the stack
value, ok = stack.Pop()
if ok {
    fmt.Println(value) // bluePlate
}

// Check the top of the stack
value, ok = stack.Pop()
if ok {
    fmt.Println(value) // redPlate
}

Performance

go test -bench=.
goos: darwin
goarch: arm64
pkg: github.com/oleiade/lane/v2
BenchmarkDequeAppend-8          22954384        54.44 ns/op      32 B/op       1 allocs/op
BenchmarkDequePrepend-8         25097098        44.59 ns/op      32 B/op       1 allocs/op
BenchmarkDequePop-8             63403720        18.99 ns/op       0 B/op       0 allocs/op
BenchmarkDequeShift-8           63390186        20.88 ns/op       0 B/op       0 allocs/op
BenchmarkDequeFirst-8           86662152        13.76 ns/op       0 B/op       0 allocs/op
BenchmarkDequeLast-8            85955014        13.76 ns/op       0 B/op       0 allocs/op
BenchmarkDequeSize-8            86614975        13.77 ns/op       0 B/op       0 allocs/op
BenchmarkDequeEmpty-8           86893297        14.22 ns/op       0 B/op       0 allocs/op
BenchmarkBoundDequeFull-8       590152324         2.039 ns/op       0 B/op       0 allocs/op
BenchmarkBoundDequeAppend-8     64457216        18.50 ns/op       0 B/op       0 allocs/op
BenchmarkBoundDeque-8           64631377        18.48 ns/op       0 B/op       0 allocs/op
BenchmarkPriorityQueuePush-8    19994029        65.67 ns/op      72 B/op       1 allocs/op
BenchmarkPriorityQueuePop-8     62751249        18.52 ns/op       0 B/op       0 allocs/op
BenchmarkPriorityQueueHead-8    86090420        13.77 ns/op       0 B/op       0 allocs/op
BenchmarkPriorityQueueSize-8    86768415        13.77 ns/op       0 B/op       0 allocs/op
BenchmarkPriorityQueueEmpty-8   87036146        13.76 ns/op       0 B/op       0 allocs/op
BenchmarkNewQueue-8             19570003        60.36 ns/op
BenchmarkQueueEnqueue-8         25482283        46.63 ns/op      32 B/op       1 allocs/op
BenchmarkQueueDequeue-8         63715965        18.50 ns/op       0 B/op       0 allocs/op
BenchmarkQueueHead-8            85664312        13.79 ns/op       0 B/op       0 allocs/op
BenchmarkNewStack-8             19925473        59.57 ns/op
BenchmarkStackPop-8             64704993        18.80 ns/op       0 B/op       0 allocs/op
BenchmarkStackHead-8            86119761        13.76 ns/op       0 B/op       0 allocs/op

Documentation

For a more detailed overview of lane, please refer to Documentation

License

MIT