• Stars
    star
    847
  • Rank 53,812 (Top 2 %)
  • Language
    Go
  • License
    MIT License
  • Created about 11 years ago
  • Updated over 1 year ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Generic PriorityQueues, Queues, Stacks, and Deque data structures for Go

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

More Repositories

1

trousseau

File based encrypted key-value store
Go
954
star
2

reflections

High level abstractions over the Go reflect library
Go
498
star
3

Elevator

Elevator is an open source, on-disk key-value store. Provides high-performance bulk read-write operations over very large datasets while exposing a simple and efficient API.
Python
71
star
4

motus

Dead simple password generator
Rust
60
star
5

durations

A Python durations parsing library
Python
25
star
6

etcaetera

Manage multiple configuration sources in a single place
Python
24
star
7

gomme

Parser combinator library for Go
Go
18
star
8

mymy

Gather information about your system quickly, intuitively, and easily.
Rust
13
star
9

py-elevator

py-elevator is a python client for Elevator, a Key-Value store written in Python and based on levelDB, allows high performance on-disk bulk read/write.
Python
13
star
10

elm-maestro

Elm music theory library
Elm
11
star
11

serrure

A encryption/decryption toolkit library for golang
Go
10
star
12

jackdauer

Use this Rust crate to easily parse various time formats to durations.
Rust
7
star
13

lhotse

Tiny HTTP server with controllable performance.
Go
6
star
14

k6-support

A full-fledged local k6 ecosystem a docker-compose up away
JavaScript
6
star
15

freebase4neo

Clojure util to setup a Freebase endpoint in Neo4j
Clojure
4
star
16

go-dynamic-array

Dynamic arrays Go lang implementation
Go
4
star
17

stamp

A simple license applier python script. Allows user to easily apply a specified license to some files.
Python
4
star
18

patron

A minimalist template system for Ableton Live
JavaScript
3
star
19

Happening

Go
3
star
20

Hurdles

A simple and yet powerful python benchmark framework. Write unit benchs just like you'd write unit tests.
Python
3
star
21

docker-localshop

Localshop pypi repository docker container builder
Python
3
star
22

Ash

Another Shell
C
2
star
23

Fridge

Ftp bridge over S3, controllable via RestFul api
Python
2
star
24

Butcher

Slice fat files into shinny slim ones in just a command
Go
2
star
25

xk6-exec

A k6 extension to execute shell commands from your k6 scripts
Go
2
star
26

Garbo

An automated plant monitoring and watering system for your garden
C++
1
star
27

Learn-unix-the-hacker-way-fr

Learn Unix, the hacker way
1
star
28

tempura

Temporary files creation and manipulation helpers for Go
Go
1
star
29

Paon

A simple Snake C++ game, including a two players "Tron mode".
1
star