Documentation ¶
Overview ¶
Package lane provides queue, priority queue, stack and deque data structures implementations. Its was designed with simplicity, performance, and concurrent usage in mind.
Index ¶
- func Maximum[T constraints.Ordered](lhs, rhs T) bool
- func Minimum[T constraints.Ordered](lhs, rhs T) bool
- type BoundDeque
- type Capaciter
- type Deque
- func (d *Deque[T]) Append(item T)
- func (d *Deque[T]) Empty() bool
- func (d *Deque[T]) First() (item T, ok bool)
- func (d *Deque[T]) Last() (item T, ok bool)
- func (d *Deque[T]) Pop() (item T, ok bool)
- func (d *Deque[T]) Prepend(item T)
- func (d *Deque[T]) Shift() (item T, ok bool)
- func (d *Deque[T]) Size() uint
- type Dequer
- type Element
- type List
- func (l *List[T]) Back() *Element[T]
- func (l *List[T]) Front() *Element[T]
- func (l *List[T]) Init() *List[T]
- func (l *List[T]) InsertAfter(v T, mark *Element[T]) *Element[T]
- func (l *List[T]) InsertBefore(v T, mark *Element[T]) *Element[T]
- func (l *List[T]) Len() uint
- func (l *List[T]) MoveAfter(e, mark *Element[T])
- func (l *List[T]) MoveBefore(e, mark *Element[T])
- func (l *List[T]) MoveToBack(e *Element[T])
- func (l *List[T]) MoveToFront(e *Element[T])
- func (l *List[T]) PushBack(v T) *Element[T]
- func (l *List[T]) PushBackList(other *List[T])
- func (l *List[T]) PushFront(v T) *Element[T]
- func (l *List[T]) PushFrontList(other *List[T])
- func (l *List[T]) Remove(e *Element[T]) T
- type PriorityQueue
- type Queue
- type Stack
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Maximum ¶
func Maximum[T constraints.Ordered](lhs, rhs T) bool
Maximum returns whether `rhs` is greater than `lhs`.
It can be used as a comparison heuristic during a PriorityQueue's instantiation.
func Minimum ¶
func Minimum[T constraints.Ordered](lhs, rhs T) bool
Minimum returns whether `rhs` is less than `lhs`.
It can be used as a comparison heuristic during a PriorityQueue's instantiation.
Types ¶
type BoundDeque ¶
BoundDeque is a head-tail linked list data structure implementation with a user-defined capacity: any operation leading to the size of the container to overflow its capacity will fail.
The BoundDeque's implementation is built upon a doubly linked list container, so that every operations' time complexity is O(1) (N.B: linked-list are not CPU-cache friendly). Every operation on a BoundDeque are goroutine-safe and ready for concurrent usage.
func NewBoundDeque ¶
func NewBoundDeque[T any](capacity uint, values ...T) *BoundDeque[T]
NewBoundDeque produces a new BoundDeque instance with the provided capacity.
func (*BoundDeque[T]) Append ¶
func (bd *BoundDeque[T]) Append(item T) bool
Append inserts item at the back of the BoundDeque in a O(1) time complexity. If the BoundDeque's capacity disallows the insertion, Append returns false.
func (*BoundDeque[T]) Capacity ¶
func (bd *BoundDeque[T]) Capacity() uint
Capacity returns the BoundDeque's capacity.
func (*BoundDeque[T]) Full ¶
func (bd *BoundDeque[T]) Full() bool
Full checks if the BoundDeque is full.
func (*BoundDeque[T]) Prepend ¶
func (bd *BoundDeque[T]) Prepend(item T) bool
Prepend inserts item at the BoundDeque's front in a O(1) time complexity. If the BoundDeque's capacity disallows the insertion, Prepend returns false.
type Capaciter ¶
type Capaciter interface { // Capacity returns the current capacity of the underlying type implementation. Capacity() int // IsFull returns whether the implementing type instance is full. IsFull() bool }
Capaciter is an interface type providing operations related to capacity management.
type Deque ¶
Deque is a head-tail linked list data structure implementation.
The Deque's implementation is built upon a doubly linked list container, so that every operations' time complexity is O(1) (N.B: linked-list are not CPU-cache friendly). Every operation on a Deque are goroutine-safe and ready for concurrent usage.
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 ok { 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 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, " "))
Output:
func (*Deque[T]) Append ¶
func (d *Deque[T]) Append(item T)
Append inserts item at the back of the Deque in a O(1) time complexity.
func (*Deque[T]) Pop ¶
Pop removes and returns the back element of the Deque in O(1) time complexity.
func (*Deque[T]) Prepend ¶
func (d *Deque[T]) Prepend(item T)
Prepend inserts item at the Deque's front in a O(1) time complexity.
type Dequer ¶
type Dequer[T any] interface { Deque[T] | BoundDeque[T] }
Dequer is the interface that wraps the basic Deque operations.
type Element ¶
type Element[T any] struct { Value T // contains filtered or unexported fields }
Element is a node of a linked list.
type List ¶
type List[T any] struct { // contains filtered or unexported fields }
List represents a doubly linked list.
func (*List[T]) InsertAfter ¶
InsertAfter inserts a new element e with value v immediately after mark and returns e.
func (*List[T]) InsertBefore ¶
InsertBefore inserts a new element e with value v immediately before mark and returns e.
func (*List[T]) MoveBefore ¶
MoveBefore moves element e to its new position before mark.
func (*List[T]) MoveToBack ¶
MoveToBack moves element e to the back of list l.
func (*List[T]) MoveToFront ¶
MoveToFront moves element e to the front of list l.
func (*List[T]) PushBack ¶
PushBack inserts a new element e with value v at the back of list l and returns e.
func (*List[T]) PushBackList ¶
PushBackList inserts a copy of an other list at the back of list l.
func (*List[T]) PushFront ¶
PushFront inserts a new element e with value v at the front of list l and returns e.
func (*List[T]) PushFrontList ¶
PushFrontList inserts a copy of an other list at the front of list l.
type PriorityQueue ¶
type PriorityQueue[T any, P constraints.Ordered] struct { sync.RWMutex // contains filtered or unexported fields }
PriorityQueue is a heap priority queue data structure implementation.
It can be either be minimum (ascending) or maximum (descending) oriented/ordered. Its type parameters `T` and `P` respectively specify the value underlying type, and the priority underlying type.
Every operations are synchronized and goroutine-safe.
Example ¶
// Let's 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) // Now let's 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 } // Okay the song order seems to be preserved, let's // roll jacksonFive := make([]string, priorityQueue.Size()) for i := 0; i < len(jacksonFive); i++ { value, _, _ := priorityQueue.Pop() jacksonFive[i] = value } fmt.Println(strings.Join(jacksonFive, " "))
Output:
func NewMaxPriorityQueue ¶
func NewMaxPriorityQueue[T any, P constraints.Ordered]() *PriorityQueue[T, P]
NewMaxPriorityQueue instantiates a new maximum oriented PriorityQueue.
func NewMinPriorityQueue ¶
func NewMinPriorityQueue[T any, P constraints.Ordered]() *PriorityQueue[T, P]
NewMinPriorityQueue instantiates a new minimum oriented PriorityQueue.
func NewPriorityQueue ¶
func NewPriorityQueue[T any, P constraints.Ordered](heuristic func(lhs, rhs P) bool) *PriorityQueue[T, P]
NewPriorityQueue instantiates a new PriorityQueue with the provided comparison heuristic. The package defines the `Max` and `Min` heuristic to define a maximum-oriented or minimum-oriented heuristic respectively.
func (*PriorityQueue[T, P]) Empty ¶
func (pq *PriorityQueue[T, P]) Empty() bool
Empty returns whether the PriorityQueue is empty.
func (*PriorityQueue[T, P]) Head ¶
func (pq *PriorityQueue[T, P]) Head() (value T, priority P, ok bool)
Head returns the highest or lowest priority item (depending on the comparison heuristic of your PriorityQueue) from the PriorityQueue in O(1) complexity.
func (*PriorityQueue[T, P]) Pop ¶
func (pq *PriorityQueue[T, P]) Pop() (value T, priority P, ok bool)
Pop and returns the highest or lowest priority item (depending on the comparison heuristic of your PriorityQueue) from the PriorityQueue in at most O(log n) complexity.
func (*PriorityQueue[T, P]) Push ¶
func (pq *PriorityQueue[T, P]) Push(value T, priority P)
Push inserts the value in the PriorityQueue with the provided priority in at most O(log n) time complexity.
func (*PriorityQueue[T, P]) Size ¶
func (pq *PriorityQueue[T, P]) Size() uint
Size returns the number of elements present in the PriorityQueue.
type Queue ¶
type Queue[T any] struct { // contains filtered or unexported fields }
Queue is a FIFO (First in first out) data structure implementation. It is based on a Deque container and focuses its API on core functionalities: Enqueue, Dequeue, Head, Size, Empty.
Every operation's time complexity is O(1).
As it is implemented using a Deque container, every operations over an instiated Queue are synchronized and goroutine-safe.
Example ¶
// 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, ok := queue.Dequeue(); ok; { go fmt.Println(client) }
Output:
func (*Queue[T]) Dequeue ¶
Dequeue removes and returns the Queue's front item in O(1) time complexity.
func (*Queue[T]) Enqueue ¶
func (q *Queue[T]) Enqueue(item T)
Enqueue adds an item at the back of the Queue in O(1) time complexity.
type Stack ¶
type Stack[T any] struct { // contains filtered or unexported fields }
Stack is a LIFO (Last in first out) data structure implementation. It is based on a Deque container and focuses its API on core functionalities: Push, Pop, Head, Size, Empty.
Every operation's time complexity is O(1).
As it is implemented using a Deque container, every operations over an instiated Stack are synchronized and goroutine-safe.
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, ok := stack.Pop() if ok { fmt.Println(value) // greenPlate } stack.Push("yellowPlate") value, ok = stack.Pop() if ok { fmt.Println(value) // yellowPlate } // What's on top of the stack? value, ok = stack.Pop() if ok { fmt.Println(value) // bluePlate } // What's on top of the stack? value, ok = stack.Pop() if ok { fmt.Println(value) // redPlate }
Output:
func NewStack ¶
NewStack produces a new Stack instance.
If any initialization variadic items are provided, they will be inserted as is: lower index being the head of stack.