1 Star 0 Fork 0

h79/goutils

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
克隆/下载
squeue.go 2.62 KB
一键复制 编辑 原始数据 按行查看 历史
huqiuyun 提交于 2023-02-20 13:14 . task
package queue
import "container/heap"
var _ Queue = (*SQueue)(nil)
type Node []IPriority
// SQueue 固定长度的队列
type SQueue struct {
node Node
head, tail, count int
}
func NewSQueue(capacity int) *SQueue {
if capacity <= 0 {
capacity = minCapacity
}
if capacity > maxCapacity {
capacity = maxCapacity
}
return &SQueue{
node: make(Node, minCapacity),
}
}
func (sq *SQueue) Len() int {
return sq.count
}
// Less 权重越少,越在前面
func (sq *SQueue) Less(i, j int) bool {
in := sq.node[i]
jn := sq.node[j]
if in == nil || jn == nil {
return false
}
return in.PValue() < jn.PValue()
}
// Swap swaps the elements with indexes i and j.
func (sq *SQueue) Swap(i, j int) {
temp := sq.node[i]
sq.node[i] = sq.node[j]
sq.node[j] = temp
}
// Push implements the heap.Interface.Push.
// Adds x as element Len().
func (sq *SQueue) Push(elem interface{}) {
if sq.count == len(sq.node) {
sq.resize()
}
sq.node[sq.tail] = NewPriorityItem(elem)
sq.tail = (sq.tail + 1) & (len(sq.node) - 1)
sq.count++
}
func (sq *SQueue) Add(elem interface{}) error {
heap.Push(sq, NewPriorityItem(elem))
return nil
}
func (sq *SQueue) Peek() interface{} {
if sq.Empty() {
return nil
}
return sq.node[sq.head].GValue()
}
// Get index -1 refers to the last.
func (sq *SQueue) Get(index int) interface{} {
if index < 0 {
index += sq.count
}
if index < 0 || index >= sq.count {
return nil
}
return sq.node[(sq.head+index)&(len(sq.node)-1)].GValue()
}
// Find return index -1 not found.
func (sq *SQueue) Find(fn IndexFunc) (interface{}, int) {
var (
cursor = sq.head
)
for i := 0; i < sq.count; i++ {
if fn(sq.node[cursor], i) {
return sq.node[cursor], cursor
}
cursor = (cursor + 1) & (len(sq.node) - 1)
}
return nil, -1
}
func (sq *SQueue) Pop() interface{} {
if sq.Empty() {
return nil
}
ret := sq.node[sq.head]
sq.node[sq.head] = nil
// bitwise modulus
sq.head = (sq.head + 1) & (len(sq.node) - 1)
sq.count--
return ret.GValue()
}
func (sq *SQueue) Empty() bool {
return sq.count <= 0
}
func (sq *SQueue) ToList() []interface{} {
var (
buf = make([]interface{}, sq.count)
cursor = sq.head
)
for i := 0; i < sq.count; i++ {
buf[i] = sq.Get(cursor)
cursor = (cursor + 1) & (len(sq.node) - 1)
}
return buf
}
func (sq *SQueue) resize() {
if sq.count >= maxCapacity {
return
}
size := sq.count << 1
if size > maxCapacity {
size = maxCapacity
}
newBuf := make(Node, size)
if sq.tail > sq.head {
copy(newBuf, sq.node[sq.head:sq.tail])
} else {
n := copy(newBuf, sq.node[sq.head:])
copy(newBuf[n:], sq.node[:sq.tail])
}
sq.tail = sq.count
sq.node = newBuf
}
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
Go
1
https://gitee.com/h79/goutils.git
git@gitee.com:h79/goutils.git
h79
goutils
goutils
v1.8.95

搜索帮助