container

Documentation

Index

• type FIFO
  • func MakeFIFO[E any](size int) FIFO[E]
  • func (q *FIFO[E]) Len() int
  • func (q *FIFO[E]) Peek() (e E)
  • func (q *FIFO[E]) Pop() (e E)
  • func (q *FIFO[E]) Push(e E)
• type Heap
  • func (h *Heap[E]) Fix(i int)
  • func (h *Heap[E]) Init()
  • func (h *Heap[E]) Len() int
  • func (h *Heap[E]) Pop() E
  • func (h *Heap[E]) Push(e E)
  • func (h *Heap[E]) Remove(i int) E
• type HeapFunc
  • func (h *HeapFunc[E]) Fix(i int)
  • func (h *HeapFunc[E]) Init()
  • func (h *HeapFunc[E]) Len() int
  • func (h *HeapFunc[E]) Pop() E
  • func (h *HeapFunc[E]) Push(e E)
  • func (h *HeapFunc[E]) Remove(i int) E
• type LIFO
  • func (q *LIFO[E]) Len() int
  • func (q *LIFO[E]) Peek() (e E)
  • func (q *LIFO[E]) Pop() (e E)
  • func (q *LIFO[E]) Push(e E)
• type RadixMap
  • func (r *RadixMap[E]) All() iter.Seq2[string, E]
  • func (r *RadixMap[E]) Delete(key string) (old E, ok bool)
  • func (r *RadixMap[E]) Get(key string) (value E, ok bool)
  • func (r *RadixMap[E]) Len() int
  • func (r *RadixMap[E]) PrefixesOf(s string) iter.Seq2[string, E]
  • func (r *RadixMap[E]) Set(key string, value E) (old E, ok bool)
  • func (r *RadixMap[E]) WithPrefix(p string) iter.Seq2[string, E]
• type RadixSet
  • func (s *RadixSet) Add(str string) (added bool)
  • func (s *RadixSet) All() iter.Seq[string]
  • func (s *RadixSet) Contains(str string) bool
  • func (s *RadixSet) Delete(key string) (deleted bool)
  • func (s *RadixSet) Len() int
  • func (s *RadixSet) PrefixesOf(str string) iter.Seq[string]
  • func (s *RadixSet) WithPrefix(p string) iter.Seq[string]

Types

type FIFO

type FIFO[E any] struct {
	// contains filtered or unexported fields
}

FIFO is a First-In-First-Out queue. A zero FIFO is an empty queue ready to use.

func MakeFIFO

func MakeFIFO[E any](size int) FIFO[E]

MakeFIFO returns a FIFO that can hold up to size elements without allocating.

func (*FIFO[E]) Len

func (q *FIFO[E]) Len() int

Len returns the length of the queue.

func (*FIFO[E]) Peek

func (q *FIFO[E]) Peek() (e E)

Peek at the next element in the queue.

func (*FIFO[E]) Pop

func (q *FIFO[E]) Pop() (e E)

Pop an element from the queue.

func (*FIFO[E]) Push

func (q *FIFO[E]) Push(e E)

Push an element unto the queue.

type Heap

type Heap[E constraints.Ordered] []E

Heap implements a min-heap.

func (*Heap[E]) Fix

func (h *Heap[E]) Fix(i int)

Fix 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 Remove(h, i) followed by a Push of the new value.

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

func (*Heap[E]) Init

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

Init establishes the heap invariants required by the other routines in this package. 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[E]) Len

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

Len returns the numuüber of elements in h.

func (*Heap[E]) Pop

func (h *Heap[E]) Pop() E

Pop removes and returns the minimum element (according to Less) from the heap. Pop is equivalent to Remove(h, 0).

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

func (*Heap[E]) Push

func (h *Heap[E]) Push(e E)

Push pushes the element e onto the heap.

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

func (*Heap[E]) Remove

func (h *Heap[E]) Remove(i int) E

Remove removes and returns the element at index i from the heap.

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

type HeapFunc

type HeapFunc[E any] struct {
	Elements []E
	Less     func(E, E) bool
}

HeapFunc implements a min-heap with custom comparison.

func (*HeapFunc[E]) Fix

func (h *HeapFunc[E]) Fix(i int)

Fix 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 Remove(h, i) followed by a Push of the new value.

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

func (*HeapFunc[E]) Init

func (h *HeapFunc[E]) Init()

Init establishes the heap invariants required by the other routines in this package. 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 (*HeapFunc[E]) Len

func (h *HeapFunc[E]) Len() int

Len returns the numuüber of elements in h.

func (*HeapFunc[E]) Pop

func (h *HeapFunc[E]) Pop() E

Pop removes and returns the minimum element (according to Less) from the heap. Pop is equivalent to Remove(h, 0).

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

func (*HeapFunc[E]) Push

func (h *HeapFunc[E]) Push(e E)

Push pushes the element e onto the heap.

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

func (*HeapFunc[E]) Remove

func (h *HeapFunc[E]) Remove(i int) E

Remove removes and returns the element at index i from the heap.

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

type LIFO

type LIFO[E any] []E

LIFO is a Last-In-First-Out queue (also known as a stack).

func (*LIFO[E]) Len

func (q *LIFO[E]) Len() int

Len returns the length of the queue.

func (*LIFO[E]) Peek

func (q *LIFO[E]) Peek() (e E)

func (*LIFO[E]) Pop

func (q *LIFO[E]) Pop() (e E)

Pop an element from the queue.

func (*LIFO[E]) Push

func (q *LIFO[E]) Push(e E)

Push an element unto the queue.

type RadixMap

type RadixMap[E any] struct {
	// contains filtered or unexported fields
}

func (*RadixMap[E]) All

func (r *RadixMap[E]) All() iter.Seq2[string, E]

All returns an iterator over all key/value pairs in the map. The key must not be retained by the caller and is only valid until the next iteration.

func (*RadixMap[E]) Delete

func (r *RadixMap[E]) Delete(key string) (old E, ok bool)

Delete the value stored under key. Returns the previous value stored under key, if any.

func (*RadixMap[E]) Get

func (r *RadixMap[E]) Get(key string) (value E, ok bool)

Get the value stored under key.

func (*RadixMap[E]) Len

func (r *RadixMap[E]) Len() int

Len returns the number of elements in r.

func (*RadixMap[E]) PrefixesOf

func (r *RadixMap[E]) PrefixesOf(s string) iter.Seq2[string, E]

PrefixesOf returns an iterator over all key/value pairs in the map which are a prefix of s. The key must not be retained by the caller and is only valid until the next iteration.

func (*RadixMap[E]) Set

func (r *RadixMap[E]) Set(key string, value E) (old E, ok bool)

Set key to value. Returns the previous value stored under key, if any.

func (*RadixMap[E]) WithPrefix

func (r *RadixMap[E]) WithPrefix(p string) iter.Seq2[string, E]

WithPrefix returns an iterator over all key/value pairs in the map which have p as a prefix. The key must not be retained by the caller and is only valid until the next iteration.

type RadixSet

type RadixSet RadixMap[struct{}]

RadixSet is a set of strings, stored as a radix tree.

func (*RadixSet) Add

func (s *RadixSet) Add(str string) (added bool)

Add str to the set. Returns false, if str was already in the set.

func (*RadixSet) All

func (s *RadixSet) All() iter.Seq[string]

All returns an iterator over all the elements in the set. The value must not be retained by the caller and is only valid until the next iteration.

func (*RadixSet) Contains

func (s *RadixSet) Contains(str string) bool

Contains returns whether str is in the set.

func (*RadixSet) Delete

func (s *RadixSet) Delete(key string) (deleted bool)

Delete str from the set. Returns true, if str was in the set.

func (*RadixSet) Len

func (s *RadixSet) Len() int

Len returns the number of elements in s.

func (*RadixSet) PrefixesOf

func (s *RadixSet) PrefixesOf(str string) iter.Seq[string]

PrefixesOf returns an iterator over all elements in the set which are a prefix of s. The value must not be retained by the caller and is only valid until the next iteration.

func (*RadixSet) WithPrefix

func (s *RadixSet) WithPrefix(p string) iter.Seq[string]

WithPrefix returns an iterator over all elements in the set which have p as a prefix. The value must not be retained by the caller and is only valid until the next iteration.