mergesort

Documentation

Overview

Package heap provides heap operations for any type that implements heap.Interface. A heap is a tree with the property that each node is the minimum-valued node in its subtree.

The minimum element in the tree is the root, at index 0.

A heap is a common way to implement a priority queue. To build a priority queue, implement the Heap interface with the (negative) priority as the ordering for the Less method, so Push adds items while Pop removes the highest-priority item from the queue. The Examples include such an implementation; the file example_pq_test.go has the complete source.

Package sort provides primitives for sorting slices and user-defined collections.

Index

• func Merge[T any](col []containers.Vector, src *[]uint32, lessFunc LessFunc[T], ...) (ret []containers.Vector, mapping []uint32)
• func MergeSortedColumn(column []containers.Vector, sortedIdx *[]uint32, fromLayout, toLayout []uint32, ...) (ret []containers.Vector, mapping []uint32)
• func Multiplex(col []containers.Vector, src []uint32, fromLayout, toLayout []uint32, ...) (ret []containers.Vector)
• func Reshape(column []containers.Vector, fromLayout, toLayout []uint32, ...) (ret []containers.Vector)
• func Shuffle(col containers.Vector, idx []int32, pool *containers.VectorPool) containers.Vector
• func ShuffleColumn(column []containers.Vector, sortedIdx []uint32, fromLayout, toLayout []uint32, ...) (ret []containers.Vector)
• func Sort[T any](col containers.Vector, lessFunc LessFunc[T], idx []int32) (ret containers.Vector)
• func SortBlockColumns(cols []containers.Vector, pk int, pool *containers.VectorPool) ([]int32, error)
• type HeapElem
• type HeapSlice
  • func NewHeapSlice[T any](n int, lessFunc LessFunc[T]) HeapSlice[T]
  • func (x *HeapSlice[T]) Append(elem HeapElem[T])
  • func (x *HeapSlice[T]) AsSlice() []HeapElem[T]
  • func (x *HeapSlice[T]) Less(i, j int) bool
  • func (x *HeapSlice[T]) Swap(i, j int)
• type LessFunc
• type Lter
• type SortElem
• type SortSlice
  • func NewSortSlice[T any](n int, lessFunc LessFunc[T]) SortSlice[T]
  • func (x *SortSlice[T]) Append(elem SortElem[T])
  • func (x *SortSlice[T]) AsSlice() []SortElem[T]
  • func (x *SortSlice[T]) Less(i, j int) bool
  • func (x *SortSlice[T]) Swap(i, j int)

Functions

func Merge

func Merge[T any](
	col []containers.Vector,
	src *[]uint32,
	lessFunc LessFunc[T],
	fromLayout,
	toLayout []uint32,
	pool *containers.VectorPool,
) (ret []containers.Vector, mapping []uint32)

func MergeSortedColumn

func MergeSortedColumn(
	column []containers.Vector, sortedIdx *[]uint32, fromLayout, toLayout []uint32, pool *containers.VectorPool,
) (ret []containers.Vector, mapping []uint32)

func Multiplex

func Multiplex(
	col []containers.Vector, src []uint32, fromLayout, toLayout []uint32, pool *containers.VectorPool,
) (ret []containers.Vector)

func Reshape

func Reshape(
	column []containers.Vector, fromLayout, toLayout []uint32, pool *containers.VectorPool,
) (ret []containers.Vector)

func Shuffle

func Shuffle(
	col containers.Vector, idx []int32, pool *containers.VectorPool,
) containers.Vector

func ShuffleColumn

func ShuffleColumn(
	column []containers.Vector, sortedIdx []uint32, fromLayout, toLayout []uint32, pool *containers.VectorPool,
) (ret []containers.Vector)

func Sort

func Sort[T any](col containers.Vector, lessFunc LessFunc[T], idx []int32) (ret containers.Vector)

func SortBlockColumns

func SortBlockColumns(
	cols []containers.Vector, pk int, pool *containers.VectorPool,
) ([]int32, error)

Types

type HeapElem

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

type HeapSlice

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

func NewHeapSlice

func NewHeapSlice[T any](n int, lessFunc LessFunc[T]) HeapSlice[T]

func (*HeapSlice[T]) Append

func (x *HeapSlice[T]) Append(elem HeapElem[T])

func (*HeapSlice[T]) AsSlice

func (x *HeapSlice[T]) AsSlice() []HeapElem[T]

func (*HeapSlice[T]) Less

func (x *HeapSlice[T]) Less(i, j int) bool

func (*HeapSlice[T]) Swap

func (x *HeapSlice[T]) Swap(i, j int)

type LessFunc

type LessFunc[T any] func(a, b T) bool

type Lter

type Lter[T any] interface {
	Lt(b T) bool
}

uuid && decimal

type SortElem

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

type SortSlice

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

func NewSortSlice

func NewSortSlice[T any](n int, lessFunc LessFunc[T]) SortSlice[T]

func (*SortSlice[T]) Append

func (x *SortSlice[T]) Append(elem SortElem[T])

func (*SortSlice[T]) AsSlice

func (x *SortSlice[T]) AsSlice() []SortElem[T]

func (*SortSlice[T]) Less

func (x *SortSlice[T]) Less(i, j int) bool

func (*SortSlice[T]) Swap

func (x *SortSlice[T]) Swap(i, j int)