# README
Lane
The Lane package provides implementations of generic Queue, PriorityQueue, Stack, and Deque data structures. It was designed with simplicity, performance, and concurrent usage in mind.
Installation
Using this package requires a working Go environment. See the install instructions for Go.
Go Modules are required when using this package. 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" // imports as package "cli"
)
...
Using v1 releases
go get github.com/oleiade/lane
...
import (
"github.com/oleiade/lane"
)
...
Usage/Examples
Priority Queue
PriorityQueue is a heap priority queue data structure implementation. It can be either maximum (descending) or minimum (ascending) oriented (ordered). Every operation on a PriorityQueue are synchronized and goroutine-safe. It performs Push and Pop operations in O(log N) time.
Example
// Let's create a new max ordered priority queue
priorityQueue := NewMaxPriorityQueue[string]()
// 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)
// Now let's take a look at the min element in
// the priority queue
headValue, headPriority, ok := priorityQueue.Head()
if okay {
fmt.Println(headValue) // "abc"
fmt.Println(headPriority) // 1
}
// okay, the song order seems to be preserved; let's
// roll
var jacksonFive []string = make([]string, priorityQueue.Size())
for i := 0; i < len(jacksonFive); i++ {
value, _, _ := priorityQueue.Pop()
jacksonFive[i] = value
}
fmt.Println(strings.Join(jacksonFive, " "))
Deque
Deque is a head-tail linked list data structure implementation. It is built upon a doubly-linked list container, and every operation on a Deque are performed in O(1) time complexity. Every operation on a Deque is synchronized and goroutine-safe.
Deques can optionally be instantiated with a limited capacity using the dedicated NewBoundDeque constructor, whereby the return value of the Append and Prepend return false if the Deque was full and the item was not added.
Deque Example
// Let's 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")
// Now let's take a look at what are the first and
// last element stored in the Deque
firstValue, ok := deque.First()
if okay {
fmt.Println(firstValue) // "abc"
}
lastValue, ok := deque.Last()
if ok {
fmt.Println(lastValue) // 1
}
//okay, now let's play with the Pop and Shift
// methods to bring the song words together
var jacksonFive []string = make([]string, deque.Size())
for i := 0; i < len(jacksonFive); i++ {
value, ok := deque.Shift()
if okay {
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. It is built upon a Deque container and focuses its API on core functionalities: Enqueue, Dequeue, Head. Every operation's time complexity is O(1). Every operation on a Queue is synchronized and goroutine-safe.
Queue Example
import (
"fmt"
"github.com/oleiade/lane/v2"
"sync"
)
func worker(item interface{}, wg *sync.WaitGroup) {
fmt.Println(item)
wg.Done()
}
func main() {
// Create a new queue and pretend we're handling starbucks
// clients
queue := NewQueue[string]()
// Let's add the incoming clients to the queue
queue.Enqueue("grumpyClient")
queue.Enqueue("happyClient")
queue.Enqueue("ecstaticClient")
fmt.Println(queue.Head()) // grumpyClient
// Let's handle the clients asynchronously
for client, okay:= queue.Dequeue(); ok; {
go fmt.Println(client)
}
// Wait until everything is printed
wg.Wait()
}
Stack
Stack is a LIFO ( Last in first out ) data structure implementation. It is built upon a Deque container and focuses its API on core functionalities: Push, Pop, Head. Every operation time complexity is O(1). Every operation on a Stack is synchronized and goroutine-safe.
Stack Example
// Create a new stack and put some plates over it
stack := NewStack[string]()
// Let's put some plates on the stack
stack.Push("redPlate")
stack.Push("bluePlate")
stack.Push("greenPlate")
fmt.Println(stack.Head()) // greenPlate
// What's on top of the stack?
value, okay:= stack.Pop()
if okay {
fmt.Println(value) // greenPlate
}
stack.Push("yellowPlate")
value, ok = stack.Pop()
if okay {
fmt.Println(value) // yellowPlate
}
// What's on top of the stack?
value, ok = stack.Pop()
if okay {
fmt.Println(value) // bluePlate
}
// What's on top of the stack?
value, ok = stack.Pop()
if okay {
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