algorithm

Documentation

Overview

Package algorithm contains some useful algorithms

Index

• func NewSkiplist() *skiplist.SkipList
• type Deque
  • func NewDeque[T any](optfs ...DequeOptFunc) (Deque[T], error)
• type DequeOptFunc
  • func WithDequeCurrentCapacity(size int) DequeOptFunc
  • func WithDequeMinimalCapacity(size int) DequeOptFunc
• type FIFO
  • func NewFIFO() *FIFO
  • func (f *FIFO) Get() any
  • func (f *FIFO) Len() int
  • func (f *FIFO) Put(d any)
• type HeapItemItf
  • func GetLargestNItems[T gutils.Sortable](inputChan <-chan HeapItemItf[T], topN int) ([]HeapItemItf[T], error)
  • func GetSmallestNItems[T gutils.Sortable](inputChan <-chan HeapItemItf[T], topN int) ([]HeapItemItf[T], error)
  • func GetTopKItems[T gutils.Sortable](inputChan <-chan HeapItemItf[T], topN int, isHighest bool) ([]HeapItemItf[T], error)
• type HeapSlice
• type LimitSizeHeap
  • func NewLimitSizeHeap[T gutils.Sortable](size int, isHighest bool) (LimitSizeHeap[T], error)

Examples

• FIFO
• GetLargestNItems
• GetSmallestNItems

Functions

func NewSkiplist

func NewSkiplist() *skiplist.SkipList

NewSkiplist new skiplist

https://github.com/sean-public/fast-skiplist

Types

type Deque

type Deque[T any] interface {
	PushBack(T)
	PushFront(T)
	PopFront() T
	PopBack() T
	Len() int
	Front() T
	Back() T
}

Deque

https://pkg.go.dev/github.com/gammazero/deque#Deque

func NewDeque

func NewDeque[T any](optfs ...DequeOptFunc) (Deque[T], error)

NewDeque new deque

type DequeOptFunc

type DequeOptFunc func(*dequeOpt) error

DequeOptFunc optional arguments for deque

func WithDequeCurrentCapacity

func WithDequeCurrentCapacity(size int) DequeOptFunc

WithDequeCurrentCapacity preallocate memory for deque

func WithDequeMinimalCapacity

func WithDequeMinimalCapacity(size int) DequeOptFunc

WithDequeMinimalCapacity set deque minimal capacity

type FIFO

type FIFO struct {
	// contains filtered or unexported fields
}

FIFO is a lock-free First-In-First-Out queue

paper: https://1drv.ms/b/s!Au45o0W1gVVLuNxYkPzfBo4fOssFPQ?e=TYxHKl

Example

f := NewFIFO()
f.Put(1)
v := f.Get()
if v == nil {
	panic(v)
}

fmt.Println(v.(int))

Output:

1

func NewFIFO

func NewFIFO() *FIFO

NewFIFO create a new FIFO queue

func (*FIFO) Get

func (f *FIFO) Get() any

Get pop data from the head of queue

func (*FIFO) Len

func (f *FIFO) Len() int

Len return the length of queue

func (*FIFO) Put

func (f *FIFO) Put(d any)

Put put an data into queue's tail

type HeapItemItf

type HeapItemItf[T gutils.Sortable] interface {
	GetKey() any
	GetPriority() T
}

HeapItemItf items need to sort

T is the type of priority

func GetLargestNItems

func GetLargestNItems[T gutils.Sortable](inputChan <-chan HeapItemItf[T], topN int) ([]HeapItemItf[T], error)

GetLargestNItems get N highest priority items

Example

var (
	itemsWaitToSort = HeapSlice[int]{
		&heapItem{p: 1},
		&heapItem{p: 3},
		&heapItem{p: 55},
		&heapItem{p: 2},
		&heapItem{p: 4441},
		&heapItem{p: 15555},
		&heapItem{p: 122},
	}
	itemChan = make(chan HeapItemItf[int])
)

go func() {
	for _, item := range itemsWaitToSort {
		itemChan <- item
	}

	close(itemChan)
}()

items, err := GetLargestNItems(itemChan, 3)
if err != nil {
	panic(err)
}

for _, item := range items {
	// 15555
	// 4441
	// 112
	fmt.Println(item.GetPriority())
}

func GetSmallestNItems

func GetSmallestNItems[T gutils.Sortable](inputChan <-chan HeapItemItf[T], topN int) ([]HeapItemItf[T], error)

GetSmallestNItems get N smallest priority items

Example

var (
	itemsWaitToSort = HeapSlice[int]{
		&heapItem{p: 1},
		&heapItem{p: 3},
		&heapItem{p: 55},
		&heapItem{p: 2},
		&heapItem{p: 4441},
		&heapItem{p: 15555},
		&heapItem{p: 122},
	}
	itemChan = make(chan HeapItemItf[int])
)

go func() {
	for _, item := range itemsWaitToSort {
		itemChan <- item
	}

	close(itemChan)
}()

items, err := GetSmallestNItems(itemChan, 3)
if err != nil {
	panic(err)
}

for _, item := range items {
	// 1
	// 2
	// 3
	fmt.Println(item.GetPriority())
}

func GetTopKItems

func GetTopKItems[T gutils.Sortable](
	inputChan <-chan HeapItemItf[T],
	topN int,
	isHighest bool,
) ([]HeapItemItf[T], error)

GetTopKItems calculate topN by heap

Arg isHighest:

• use min-heap to calculates topN Highest items.
• use max-heap to calculates topN Lowest items.

type HeapSlice

type HeapSlice[T gutils.Sortable] []HeapItemItf[T]

HeapSlice slice that could be used by heap

type LimitSizeHeap

type LimitSizeHeap[T gutils.Sortable] interface {
	Push(item HeapItemItf[T]) HeapItemItf[T]
	Pop() HeapItemItf[T]
}

LimitSizeHeap heap that with limited size

func NewLimitSizeHeap

func NewLimitSizeHeap[T gutils.Sortable](size int, isHighest bool) (LimitSizeHeap[T], error)

NewLimitSizeHeap create new LimitSizeHeap