package queue

import "container/heap"

var _ Queue = (*SQueue)(nil)

type Node []IPriorityItem

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] = ConvertPriorityItem(elem)
	sq.tail = (sq.tail + 1) & (len(sq.node) - 1)
	sq.count++
}

func (sq *SQueue) Add(elem interface{}) error {
	heap.Push(sq, ConvertPriorityItem(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
}