Documentation
¶
Overview ¶
Package algorithm contains some useful algorithms
Index ¶
- func BinarySearch[T any](s []T, cmp func(index int, element T) int) int
- func GetLargestNItems[T common.Sortable](inputChan <-chan T, topN int) ([]T, error)
- func GetSmallestNItems[T common.Sortable](inputChan <-chan T, topN int) ([]T, error)
- func GetTopKItems[T common.Sortable](inputChan <-chan T, topN int, sortOrder common.SortOrder) (result []T, err error)
- type Deque
- type DequeOptFunc
- type DiffArray
- type FIFO
- type PriorityItem
- type PriorityItemItf
- type PriorityQ
- type SkipList
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BinarySearch ¶
BinarySearch searches for target in a sorted slice s.
cmp must implement the same ordering as the slice, i.e. it must return a negative value if the target is less than the element at index, a positive value if the target is greater than the element at index, and zero if the target is equal to the element at index.
Returns the index of target in s, or -1 if target is not present.
I thinks this function is better than built-in slices.BinarySearchFunc, since of the cmp function is more flexible, you can get the index and element at each iteration, that can enpower you to do more things rather than just comparing. BTW, I think there is no need for the target as the parameter, since you can wrap the target in the cmp function.
func GetLargestNItems ¶
GetLargestNItems get N highest priority items
func GetSmallestNItems ¶
GetSmallestNItems get N smallest priority items
Types ¶
type Deque ¶
type Deque[T any] interface { PushBack(T) PushFront(T) PopFront() T PopBack() T Len() int Front() T Back() T }
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 DiffArray ¶ added in v6.1.0
type DiffArray struct {
// contains filtered or unexported fields
}
DiffArray represents a difference array for efficient range updates.
func NewDiffArray ¶ added in v6.1.0
NewDiffArray initializes a DiffArray based on the input array.
func (*DiffArray) IncrementRange ¶ added in v6.1.0
IncrementRange increments all elements in the range [l, r] by val.
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("empty")
}
fmt.Println(v.(int))
Output: 1
type PriorityItem ¶
type PriorityItem[T common.Sortable] struct { Val T // Value used for ordering Name any // Optional identifier }
PriorityItem is a concrete implementation of PriorityItemItf.
func (PriorityItem[T]) GetVal ¶
func (t PriorityItem[T]) GetVal() T
GetVal returns the value of the priority item.
type PriorityItemItf ¶ added in v6.1.0
PriorityItemItf defines the interface for items stored in the priority queue.
type PriorityQ ¶
PriorityQ is a generic priority queue. Do not use this structure directly, use `NewPriorityQ` instead.
func NewPriorityQ ¶
NewPriorityQ creates a new PriorityQ.
Args:
- order: common.SortOrderAsc or common.SortOrderDesc. Use common.SortOrderDesc for top-N items, Use common.SortOrderAsc for bottom-N items.
func (*PriorityQ[T]) Peek ¶
func (pq *PriorityQ[T]) Peek() PriorityItemItf[T]
Peek returns the highest-priority item without removing it.
func (*PriorityQ[T]) Pop ¶
func (pq *PriorityQ[T]) Pop() PriorityItemItf[T]
Pop removes and returns the highest-priority item.
func (*PriorityQ[T]) Push ¶
func (pq *PriorityQ[T]) Push(v PriorityItemItf[T])
Push inserts an item into the priority queue.
Source Files