collections

package
v0.0.0-...-bc49051 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 27, 2024 License: MIT Imports: 1 Imported by: 0

README

collections

These are basic generic collection types that should probably be in the standard library and not in this random package.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func More 

func More[A cmp.Ordered](x, y A) bool

More is `cmp.Less` but the other direction.

Types

type BatchIterator 

type BatchIterator[T any] struct {
	Items     []T
	BatchSize int
	Cursor    int
}

BatchIterator allows you to iterate over a larger slice of items in chunsk with a given `BatchSize`.

It is useful if you need to, for example, process 100,000 items in 1000 item chunks, such as for batch inserts.

func (*BatchIterator[T]) HasNext 

func (bi *BatchIterator[T]) HasNext() bool

HasNext returns if we should process another batch.

func (*BatchIterator[T]) Next 

func (bi *BatchIterator[T]) Next() []T

Next yields the next batch of size `BatchSize` or smaller.

type BinarySearchTree 

type BinarySearchTree[K cmp.Ordered, V any] struct {
	// contains filtered or unexported fields
}

BinarySearchTree is a AVL balanced tree which holds the properties that nodes are ordered left to right.

The choice to use AVL to balance the tree means the use cases skew towards fast lookups at the expense of more costly mutations.

func (*BinarySearchTree[K, V]) Delete 

func (bst *BinarySearchTree[K, V]) Delete(k K)

Delete deletes a value from the tree, and returns if it existed.

func (*BinarySearchTree[K, V]) InOrder 

func (bst *BinarySearchTree[K, V]) InOrder(fn func(K, V))

InOrder traversal returns the sorted values in the tree.

func (*BinarySearchTree[K, V]) Insert 

func (bst *BinarySearchTree[K, V]) Insert(k K, v V)

Insert adds a new value to the binary search tree.

func (*BinarySearchTree[K, V]) KeysEqual 

func (bst *BinarySearchTree[K, V]) KeysEqual(other *BinarySearchTree[K, V]) bool

KeysEqual is a function that can be used to deeply compare two trees based on their keys.

Values are _not_ considered because values are not comparable by design.

func (*BinarySearchTree[K, V]) Max 

func (bst *BinarySearchTree[K, V]) Max() (k K, v V, ok bool)

Max returns the maximum key and value.

func (*BinarySearchTree[K, V]) Min 

func (bst *BinarySearchTree[K, V]) Min() (k K, v V, ok bool)

Min returns the minimum key and value.

func (*BinarySearchTree[K, V]) PostOrder 

func (bst *BinarySearchTree[K, V]) PostOrder(fn func(K, V))

PostOrder traversal returns the values in the tree in post-order.

func (*BinarySearchTree[K, V]) PreOrder 

func (bst *BinarySearchTree[K, V]) PreOrder(fn func(K, V))

PreOrder traversal returns the values in the tree in pre-order.

func (*BinarySearchTree[K, V]) Search 

func (bst *BinarySearchTree[K, V]) Search(k K) (v V, ok bool)

Search searches for a node with a given key, returning the value and a boolean indicating the key was found.

type BinarySearchTreeNode 

type BinarySearchTreeNode[K cmp.Ordered, V any] struct {
	Key    K
	Value  V
	Left   *BinarySearchTreeNode[K, V]
	Right  *BinarySearchTreeNode[K, V]
	Height int
}

BinarySearchTreeNode is a node in a BinarySearchTree.

type Heap 

type Heap[A any] struct {
	LessFn func(A, A) bool
	Values []A
}

Heap is a generic container that satisfies the heap property.

You should use the `NewHeap` constructor to create a Heap[A].

A heap is a structure that organizes an array into a binary tree such that each element's children are less than the elements value in respec to the `LessFn` result.

Most operations (Push, Pop etc.) are O(log n) where n = h.Len().

Peeking the min element is O(1).

func NewHeap 

func NewHeap[A any](lessfn func(A, A) bool, values ...A) *Heap[A]

NewHeap returns a new heap.

func (*Heap[A]) FixAt 

func (h *Heap[A]) FixAt(i int)

FixAt re-establishes the heap ordering after the element at index i has changed its value. Changing the value of the element at index i and then calling Fix is equivalent to, but less expensive than, calling `RemoveAt(i)` followed by a Push of the new value.

The complexity is O(log n) where n = h.Len().

func (*Heap[A]) Init 

func (h *Heap[A]) Init()

Init establishes the heap invariants.

Init is idempotent with respect to the heap invariants and may be called whenever the heap invariants may have been invalidated. The complexity is O(n) where n = h.Len().

func (*Heap[A]) Len 

func (h *Heap[A]) Len() int

Len returns the length, or number of items in the heap.

func (*Heap[A]) Peek 

func (h *Heap[A]) Peek() (output A, ok bool)

Peek returns the first (smallest according to LessFn) element in the heap.

func (*Heap[A]) Pop 

func (h *Heap[A]) Pop() (output A, ok bool)

Pop removes and returns the minimum element (according to `h.LessFn`) from the heap. The complexity is O(log n) where n = h.Len().

Pop is equivalent to `RemoveAt(0)`.

func (*Heap[A]) Push 

func (h *Heap[A]) Push(v A)

Push pushes values onto the heap.

func (*Heap[A]) PushPop 

func (h *Heap[A]) PushPop(v A) (output A, ok bool)

PushPop implements a combined push and pop action which will be faster in practice than calling Push and then Pop separately (or vice versa).

func (*Heap[A]) RemoveAt 

func (h *Heap[A]) RemoveAt(i int) (output A, ok bool)

RemoveAt removes and returns the element at index i from the heap. The complexity is O(log n) where n = h.Len().

Note that `RemoveAt` takes an index, you should first determine the index by scanning the heap values for the appropriate index.

Further note; we don't have a value based function for this because not all types implement `comparable` and we don't want to make assumptions about the heap type for a subset of the heap methods.

type LRU 

type LRU[K comparable, V any] struct {
	Capacity int
	OnEvict  func(K, V)
	// contains filtered or unexported fields
}

LRU is a structure that allows you to evict items based on which were used last.

It combines a light linked list structure with a map for fast lookups and fast evictions based on which item is at the "tail" of the linked list.

func (*LRU[K, V]) Each 

func (lru *LRU[K, V]) Each(fn func(K, V))

Each calls a given function for each element in the lru cache.

func (*LRU[K, V]) Get 

func (lru *LRU[K, V]) Get(k K) (v V, ok bool)

Get returns an item with a given key.

func (*LRU[K, V]) Head 

func (lru *LRU[K, V]) Head() (k K, v V, ok bool)

Head returns the head, or oldest, key and value.

func (*LRU[K, V]) Len 

func (lru *LRU[K, V]) Len() int

Len returns the number of items in the lru cache.

func (*LRU[K, V]) Remove 

func (lru *LRU[K, V]) Remove(k K) (ok bool)

Remove removes an element.

func (*LRU[K, V]) Set 

func (lru *LRU[K, V]) Set(k K, v V)

Get returns an item with a given key.

func (*LRU[K, V]) Tail 

func (lru *LRU[K, V]) Tail() (k K, v V, ok bool)

Tail returns the tail, or most recently used, key and value.

func (*LRU[K, V]) Touch 

func (lru *LRU[K, V]) Touch(k K) (ok bool)

Touch moves a given key to the end of the lru queue.

type LinkedList 

type LinkedList[T any] struct {
	// contains filtered or unexported fields
}

LinkedList is an implementation of a fifo buffer using nodes and poitners. Remarks; it is not threadsafe. It is constant(ish) time in all ops.

func (*LinkedList[T]) Clear 

func (l *LinkedList[T]) Clear()

Clear clears the linked list.

func (*LinkedList[T]) Each 

func (q *LinkedList[T]) Each(consumer func(value T))

Each calls the consumer for each element of the linked list.

func (*LinkedList[T]) Len 

func (l *LinkedList[T]) Len() int

Len returns the length of the list in constant time.

func (*LinkedList[T]) Peek 

func (q *LinkedList[T]) Peek() (out T, ok bool)

Peek returns the first element of the list but does not remove it.

func (*LinkedList[T]) PeekBack 

func (q *LinkedList[T]) PeekBack() (out T, ok bool)

PeekBack returns the last element of the list.

func (*LinkedList[T]) Pop 

func (l *LinkedList[T]) Pop() (out T, ok bool)

Pop removes the head element from the list.

func (*LinkedList[T]) PopAll 

func (l *LinkedList[T]) PopAll() (output []T)

PopAll removes all the elements, returning a slice.

func (*LinkedList[T]) PopBack 

func (l *LinkedList[T]) PopBack() (out T, ok bool)

PopBack removes the last, or tail, element of the list.

func (*LinkedList[T]) Push 

func (l *LinkedList[T]) Push(value T) *LinkedListNode[T]

Push appends a node to the end, or tail, of the list.

func (*LinkedList[T]) PushFront 

func (l *LinkedList[T]) PushFront(value T) *LinkedListNode[T]

PushBack adds a new value to the front of the list.

func (*LinkedList[T]) Remove 

func (l *LinkedList[T]) Remove(i *LinkedListNode[T])

type LinkedListNode 

type LinkedListNode[T any] struct {
	// Value holds the value of the node.
	Value T
	// Next points towards the tail.
	Next *LinkedListNode[T]
	// Previous points towards the head.
	Previous *LinkedListNode[T]
}

LinkedListNode is a linked list node.

type PriorityQueue 

type PriorityQueue[T any] struct {
	// contains filtered or unexported fields
}

PriorityQueue is a heap of items with priorities.

func NewPriorityQueue 

func NewPriorityQueue[T any]() *PriorityQueue[T]

NewPriorityQueue returns a new priority queue.

A priority queue is very similar to a heap but instead of bring intrinsically ordered, you can supply a separate priority.

func (*PriorityQueue[T]) Len 

func (pq *PriorityQueue[T]) Len() int

Len returns the length of the priority queue.

func (*PriorityQueue[T]) Peek 

func (pq *PriorityQueue[T]) Peek() (item T, priority int, ok bool)

Peek returns the minimum item and its priority but does not remove it.

func (*PriorityQueue[T]) Pop 

func (pq *PriorityQueue[T]) Pop() (item T, priority int, ok bool)

Pop pops an item off the priority queue.

func (*PriorityQueue[T]) Push 

func (pq *PriorityQueue[T]) Push(item T, priority int)

Push pushes an item into the priority queue.

func (*PriorityQueue[T]) PushPop 

func (pq *PriorityQueue[T]) PushPop(inputItem T, inputPriority int) (outputItem T, outputPriority int, ok bool)

Push pushes an item into the priority queue.

type PriorityQueueItem 

type PriorityQueueItem[T any] struct {
	Item     T
	Priority int
}

PriorityQueueItem is an item in the priority queue.

type Queue 

type Queue[A any] struct {
	// contains filtered or unexported fields
}

Queue is a fifo (first-in, first-out) buffer implementation.

It is is backed by a pre-allocated array, which saves GC churn because the memory used to hold elements is not released unless the queue is trimmed.

This stands in opposition to how queues are typically are implemented, which is as a linked list.

As a result, `Push` can be O(n) if the backing array needs to be embiggened, though this should be relatively rare in pracitce if you're keeping a fixed queue size.

Pop is generally O(1) because it just moves pointers around and nil's out elements.

func (*Queue[A]) Cap 

func (q *Queue[A]) Cap() int

Cap returns the total capacity of the queue, including empty elements.

func (*Queue[A]) Clear 

func (q *Queue[A]) Clear()

Clear removes all elements from the Queue.

It does _not_ reclaim any backing buffer length.

To resize the backing buffer, use `Trim(size)`.

func (*Queue[A]) Each 

func (q *Queue[A]) Each(fn func(A))

Each calls the fn for each element in the buffer.

func (*Queue[A]) EachUntil 

func (q *Queue[A]) EachUntil(fn func(A) bool)

Each calls the fn for each element in the buffer.

func (*Queue[A]) Len 

func (q *Queue[A]) Len() int

Len returns the number of elements in the queue.

Use `Cap()` to return the length of the backing array itself.

func (*Queue[A]) Peek 

func (q *Queue[A]) Peek() (output A, ok bool)

Peek returns but does not remove the first element.

func (*Queue[A]) PeekBack 

func (q *Queue[A]) PeekBack() (output A, ok bool)

PeekBack returns but does not remove the last element.

func (*Queue[A]) Pop 

func (q *Queue[A]) Pop() (output A, ok bool)

Pop removes the first (oldest) element from the Queue.

func (*Queue[A]) PopBack 

func (q *Queue[A]) PopBack() (output A, ok bool)

Pop removes the last (newest) element from the Queue.

func (*Queue[A]) Push 

func (q *Queue[A]) Push(v A)

Push adds an element to the "back" of the Queue.

func (*Queue[A]) ReverseEach 

func (q *Queue[A]) ReverseEach(fn func(A))

ReverseEach calls fn in reverse order (tail to head).

func (*Queue[A]) ReverseEachUntil 

func (q *Queue[A]) ReverseEachUntil(fn func(A) bool)

ReverseEachUntil calls fn in reverse order (tail to head) with the function able to abort iteration by returning `false`.

func (*Queue[A]) Trim 

func (q *Queue[A]) Trim(size int)

Trim trims a queue to a given size.

func (*Queue[A]) Values 

func (q *Queue[A]) Values() (output []A)

Values collects the storage array into a copy array which is returned.

type Set 

type Set[A comparable] map[A]struct{}

Set is a generic set.

func NewSet 

func NewSet[A comparable](values []A) Set[A]

NewSet creates a new set.

func (Set[A]) Add 

func (s Set[A]) Add(v A)

Add adds a given element.

func (Set[A]) Copy 

func (s Set[A]) Copy() (output Set[A])

Copy copies a set.

func (Set[A]) CopyAdd 

func (s Set[A]) CopyAdd(v A) (output Set[A])

CopyAdd copies a set and adds a given element.

func (Set[A]) CopyRemove 

func (s Set[A]) CopyRemove(v A) (output Set[A])

CopyRemove copies a set and removes a given element.

func (Set[A]) Delete 

func (s Set[A]) Delete(v A)

Delete removes a given element.

func (Set[A]) DiffAdded 

func (s Set[A]) DiffAdded(other Set[A]) Set[A]

DiffAdded returns the elements in the other set that are not found in this set.

func (Set[A]) DiffRemoved 

func (s Set[A]) DiffRemoved(other Set[A]) Set[A]

DiffRemoved returns the elements in this set that are not found in the other set.

func (Set[A]) Disjoint 

func (s Set[A]) Disjoint(other Set[A]) Set[A]

Disjoint returns the disjoint elements.

Disjoint elements are elements that are not present in this set, but present in the other set, or are not preset in the other set but present in this set.

func (Set[A]) Equals 

func (s Set[A]) Equals(other Set[A]) bool

Equals returns if a set is strictly equals to another set.

Equality in this case depends on the sets being the same length, and then that each key present in this set is present in the other set.

func (Set[A]) Has 

func (s Set[A]) Has(v A) bool

Has returns if a given element exists.

func (Set[A]) Intersect 

func (s Set[A]) Intersect(other Set[A]) Set[A]

Intersect returns a new set that is the shared elements of this set and another set.

func (Set[A]) PopRandom 

func (s Set[A]) PopRandom() (out A, ok bool)

PopRandom selects an element semi-randomly and deletes it from the set.

func (Set[A]) Union 

func (s Set[A]) Union(other Set[A]) Set[A]

Union returns a new combined set that is the keys of this set and the unique keys of the other set.

func (Set[A]) Values 

func (s Set[A]) Values() (output []A)

Values yields the values in the set as a slice.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.