dast

Documentation

Overview

Package dast contains custom data structure and algorithm implementations.

Index

• type Compare
• type FIFO
  • func NewFIFO[T any](capacity int) *FIFO[T]
  • func (f *FIFO[T]) First() typact.Option[T]
  • func (f *FIFO[T]) Len() int
  • func (f *FIFO[T]) Push(value T)
  • func (f *FIFO[T]) Slice() []T
• type Heap
  • func NewHeap[T Compare[T]](elems ...T) Heap[T]
  • func NewHeapWithCap[T Compare[T]](capacity int) Heap[T]
  • func (h Heap[T]) CompareAt(a, b int) iterop.Ordering
  • func (h *Heap[T]) Fix(idx int)
  • func (h *Heap[T]) Pop() T
  • func (h *Heap[T]) Push(elem T)
  • func (h *Heap[T]) Remove(idx int) T

Types

type Compare

type Compare[T any] interface {
	// Compare compares the current element with the given one
	// and returns the [iterop.Ordering].
	Compare(T) iterop.Ordering
}

Compare describes the required method for a comparator.

type FIFO

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

FIFO is a FIFO list.

func NewFIFO

func NewFIFO[T any](capacity int) *FIFO[T]

NewFIFO returns an initialized FIFO list.

func (*FIFO[T]) First

func (f *FIFO[T]) First() typact.Option[T]

First returns the first element in the list.

func (*FIFO[T]) Len

func (f *FIFO[T]) Len() int

Len returns the length of the list.

func (*FIFO[T]) Push

func (f *FIFO[T]) Push(value T)

Push pushes the given value to the front of the list.

func (*FIFO[T]) Slice

func (f *FIFO[T]) Slice() []T

Slice returns the slice representation of f.

WARN: Do NOT modify the slice!

type Heap

type Heap[T Compare[T]] []T

Heap implements a binary heap data structure.

WARN: Please call NewHeap otherwise the heap will not be correctly initialized!

func NewHeap

func NewHeap[T Compare[T]](elems ...T) Heap[T]

NewHeap returns a new and initialized [Heap[T]] from the given elements.

The time complexity is O(n) where n = len(elems).

func NewHeapWithCap

func NewHeapWithCap[T Compare[T]](capacity int) Heap[T]

NewHeapWithCap returns an empty Heap with the given capacity.

func (Heap[T]) CompareAt

func (h Heap[T]) CompareAt(a, b int) iterop.Ordering

CompareAt compares h[a] with h[b] and returns the result. If a or b are out of bounds of h, the method will panic.

func (*Heap[T]) Fix

func (h *Heap[T]) Fix(idx int)

Fix fixes the heap order for h after the element has changed at idx.

func (*Heap[T]) Pop

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

Pop removes and returns the min. element from h. The method panics if no more elements are available in h.

Time complexity: O(log n).

func (*Heap[T]) Push

func (h *Heap[T]) Push(elem T)

Push pushes the given elem onto the heap.

Time complexity: O(log n).

func (*Heap[T]) Remove

func (h *Heap[T]) Remove(idx int) T

Remove removes the element located at idx from h and returns the removed element. The method panics if idx is out of bounds.

Time complexity: O(log n).