heap

Documentation

Index

• func BuildExcludeFilter[T any](start, end int, filterPredicate func(T) bool) func(sl *[]T)
• func MakeHeap[T any](less func(i, j T) bool, methods HeapMethods[T]) (*HeapWrapper[T], *SliceInterface[T])
• func MakeMaxHeap[T constraints.Ordered]() (*HeapWrapper[T], *SliceInterface[T])
• func MakeMinHeap[T constraints.Ordered]() (*HeapWrapper[T], *SliceInterface[T])
• type FilterableHeap
  • func NewFilterableHeap[T any]() *FilterableHeap[T]
  • func NewFilterableHeapHooks[T any](less func(i, j T) bool, hooks HeapMethods[T]) *FilterableHeap[T]
  • func (h *FilterableHeap[T]) Clone() *FilterableHeap[T]
  • func (h *FilterableHeap[T]) Filter(filterFuncs ...func(innerSlice *[]T))
  • func (h *FilterableHeap[T]) Len() int
  • func (h *FilterableHeap[T]) Peek() (p T)
• type HeapMethods
• type HeapWrapper
  • func NewHeapWrapper[T any](inter heapparam.Interface[T]) *HeapWrapper[T]
  • func (hw *HeapWrapper[T]) Fix(i int)
  • func (hw *HeapWrapper[T]) Init()
  • func (hw *HeapWrapper[T]) Pop() T
  • func (hw *HeapWrapper[T]) Push(x T)
  • func (hw *HeapWrapper[T]) Remove(i int) T
• type Lesser
• type Popper
• type Pusher
• type SliceInterface
  • func NewSliceInterface[T any](init []T, less func(i, j T) bool, methods HeapMethods[T]) *SliceInterface[T]
  • func (sl *SliceInterface[T]) Len() int
  • func (sl *SliceInterface[T]) Less(i, j int) bool
  • func (sl *SliceInterface[T]) Pop() T
  • func (sl *SliceInterface[T]) Push(x T)
  • func (sl *SliceInterface[T]) Swap(i, j int)
• type Swapper

Functions

func BuildExcludeFilter

func BuildExcludeFilter[T any](start, end int, filterPredicate func(T) bool) func(sl *[]T)

func MakeHeap

func MakeHeap[T any](less func(i, j T) bool, methods HeapMethods[T]) (*HeapWrapper[T], *SliceInterface[T])

MakeHeap makes a heap for the type T using a less[T] function.

To add your own heap methods, embed *HeapWrapper[T] to your own struct type to expose basic heap methods, and manipulate SliceInterface[T].Inner slice in its own way. Mutating inner slice may need succeeding Init() or Fix() call.

func MakeMaxHeap

func MakeMaxHeap[T constraints.Ordered]() (*HeapWrapper[T], *SliceInterface[T])

MakeMaxHeap makes a MaxHeap for the type T. This is same as MakeMinHeap but uses more[T] instead.

func MakeMinHeap

func MakeMinHeap[T constraints.Ordered]() (*HeapWrapper[T], *SliceInterface[T])

MakeMinHeap makes a MinHeap for the type T.

MakeMinHeap does what MakeHeap does but with predeclared less function. T is constrained to predeclared primitive types which are compatible with less and greater comparison operations.

Types

type FilterableHeap

type FilterableHeap[T any] struct {
	*HeapWrapper[T]
	// contains filtered or unexported fields
}

func NewFilterableHeap

func NewFilterableHeap[T any]() *FilterableHeap[T]

NewFilterableHeap returns newly created FilterableHeap. T must implement Lesser[T], otherwise it panics. T can optionally implement Swapper, Pusher, Popper. If T implements those interface, methods will be used in corresponding heap functions instead of default implementations.

func NewFilterableHeapHooks

func NewFilterableHeapHooks[T any](less func(i, j T) bool, hooks HeapMethods[T]) *FilterableHeap[T]

func (*FilterableHeap[T]) Clone

func (h *FilterableHeap[T]) Clone() *FilterableHeap[T]

Clone clones internal slice and creates new FilterableHeap with it. This is done by simple slice copy, without succeeding Init call, which means it also clones broken invariants if any.

If type T or one of its internal value is pointer type, mutation of T propagates cloned to original, and vice versa.

func (*FilterableHeap[T]) Filter

func (h *FilterableHeap[T]) Filter(filterFuncs ...func(innerSlice *[]T))

Filter calls filterFuncs one by one, in given order, with following heap.Init(). Each filterFunc receives innerSlice so that it can be mutated in that func.

Filter calls heap.Init() at the end of the method. So the complexity is at least O(n) where n is h.Len().

func (*FilterableHeap[T]) Len

func (h *FilterableHeap[T]) Len() int

func (*FilterableHeap[T]) Peek

func (h *FilterableHeap[T]) Peek() (p T)

Peek returns most prioritized value in heap without removing it. If this heap contains 0 element, returned p is zero value for type T.

The complexity is O(1).

type HeapMethods

type HeapMethods[T any] struct {
	Swap func(slice *slice.Stack[T], i, j int)
	Push func(slice *slice.Stack[T], v T)
	Pop  func(slice *slice.Stack[T]) T
}

HeapMethods is replacement methods for heap. Non nil fields will be used in heap functions of corresponding name.

type HeapWrapper

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

func NewHeapWrapper

func NewHeapWrapper[T any](inter heapparam.Interface[T]) *HeapWrapper[T]

func (*HeapWrapper[T]) Fix

func (hw *HeapWrapper[T]) Fix(i int)

func (*HeapWrapper[T]) Init

func (hw *HeapWrapper[T]) Init()

func (*HeapWrapper[T]) Pop

func (hw *HeapWrapper[T]) Pop() T

func (*HeapWrapper[T]) Push

func (hw *HeapWrapper[T]) Push(x T)

func (*HeapWrapper[T]) Remove

func (hw *HeapWrapper[T]) Remove(i int) T

type Lesser

type Lesser[T any] interface {
	Less(i, j T) bool
}

type Popper

type Popper[T any] interface {
	Pop(slice *slice.Stack[T]) T
}

type Pusher

type Pusher[T any] interface {
	Push(slice *slice.Stack[T], v T)
}

type SliceInterface

type SliceInterface[T any] struct {
	Inner slice.Stack[T]
	// contains filtered or unexported fields
}

func NewSliceInterface

func NewSliceInterface[T any](
	init []T,
	less func(i, j T) bool,
	methods HeapMethods[T],
) *SliceInterface[T]

NewSliceInterface returns a newly created SliceInterface. less is mandatory. Each fields of HeapMethods can be nil.

func (*SliceInterface[T]) Len

func (sl *SliceInterface[T]) Len() int

func (*SliceInterface[T]) Less

func (sl *SliceInterface[T]) Less(i, j int) bool

func (*SliceInterface[T]) Pop

func (sl *SliceInterface[T]) Pop() T

func (*SliceInterface[T]) Push

func (sl *SliceInterface[T]) Push(x T)

func (*SliceInterface[T]) Swap

func (sl *SliceInterface[T]) Swap(i, j int)

type Swapper

type Swapper[T any] interface {
	Swap(slice *slice.Stack[T], i, j int)
}