mirror of
https://github.com/luxfi/math.git
synced 2026-09-24 00:25:16 +00:00
zeekay
7aa527e883
- Add Zero[T any]() generic function for zero values - Add IsSortedBytes for byte slice sorting checks - Add heap/queue.go with priority Queue[T] implementation - Add heap/map.go with indexed Map[K,V] for heap operations - Add linked/list.go with doubly-linked List[T] - Add linked/hashmap.go with ordered HashMap[K,V] - Update sampleable_set.go to use local luxmath.Zero[T]() - Update averager_heap.go to use github.com/luxfi/math/heap - Update safe_math.go to use luxmath.Zero[T]() - Remove github.com/luxfi/utils dependency entirely
95 lines
1.7 KiB
Go
95 lines
1.7 KiB
Go
// Copyright (C) 2019-2025, Lux Industries, Inc. All rights reserved.
|
|
// See the file LICENSE for licensing terms.
|
|
|
|
package heap
|
|
|
|
import (
|
|
"container/heap"
|
|
|
|
luxmath "github.com/luxfi/math"
|
|
)
|
|
|
|
var _ heap.Interface = (*queue[int])(nil)
|
|
|
|
// NewQueue returns an empty heap. See QueueOf for more.
|
|
func NewQueue[T any](less func(a, b T) bool) Queue[T] {
|
|
return QueueOf(less)
|
|
}
|
|
|
|
// QueueOf returns a heap containing entries ordered by less.
|
|
func QueueOf[T any](less func(a, b T) bool, entries ...T) Queue[T] {
|
|
q := Queue[T]{
|
|
queue: &queue[T]{
|
|
entries: make([]T, len(entries)),
|
|
less: less,
|
|
},
|
|
}
|
|
|
|
copy(q.queue.entries, entries)
|
|
heap.Init(q.queue)
|
|
return q
|
|
}
|
|
|
|
type Queue[T any] struct {
|
|
queue *queue[T]
|
|
}
|
|
|
|
func (q *Queue[T]) Len() int {
|
|
return len(q.queue.entries)
|
|
}
|
|
|
|
func (q *Queue[T]) Push(t T) {
|
|
heap.Push(q.queue, t)
|
|
}
|
|
|
|
func (q *Queue[T]) Pop() (T, bool) {
|
|
if q.Len() == 0 {
|
|
return luxmath.Zero[T](), false
|
|
}
|
|
|
|
return heap.Pop(q.queue).(T), true
|
|
}
|
|
|
|
func (q *Queue[T]) Peek() (T, bool) {
|
|
if q.Len() == 0 {
|
|
return luxmath.Zero[T](), false
|
|
}
|
|
|
|
return q.queue.entries[0], true
|
|
}
|
|
|
|
func (q *Queue[T]) Fix(i int) {
|
|
heap.Fix(q.queue, i)
|
|
}
|
|
|
|
type queue[T any] struct {
|
|
entries []T
|
|
less func(a, b T) bool
|
|
}
|
|
|
|
func (q *queue[T]) Len() int {
|
|
return len(q.entries)
|
|
}
|
|
|
|
func (q *queue[T]) Less(i, j int) bool {
|
|
return q.less(q.entries[i], q.entries[j])
|
|
}
|
|
|
|
func (q *queue[T]) Swap(i, j int) {
|
|
q.entries[i], q.entries[j] = q.entries[j], q.entries[i]
|
|
}
|
|
|
|
func (q *queue[T]) Push(e any) {
|
|
q.entries = append(q.entries, e.(T))
|
|
}
|
|
|
|
func (q *queue[T]) Pop() any {
|
|
end := len(q.entries) - 1
|
|
|
|
popped := q.entries[end]
|
|
q.entries[end] = luxmath.Zero[T]()
|
|
q.entries = q.entries[:end]
|
|
|
|
return popped
|
|
}
|