package queue

// Priority 优先级
type Priority struct {
	l []IPriority
}

var _ Queue = (*Priority)(nil)

func NewPriority() *Priority {
	return &Priority{}
}

// Len returns the Priority length.
func (pq *Priority) Len() int { return len(pq.l) }

func (pq *Priority) Add(elem any) error {
	return pq.Push(elem)
}

func (pq *Priority) Push(x any) error {
	p := NewPriorityItem(x)
	index := pq.getInsertIndex(p.PValue(), 0, pq.Len()-1)
	pq.l = append(pq.l, nil)
	copy(pq.l[index+1:], pq.l[index:])

	pq.l[index] = p
	return nil
}

// Pop implements the heap.Interface.Pop.
// Removes and returns element Len() - 1.
func (pq *Priority) Pop() any {
	//old := pq.l
	//n := len(old)
	//if n == 0 {
	//	return nil
	//}
	//item := old[n-1]
	//pq.l = old[0 : n-1]
	old := pq.l
	item := old[0]
	pq.l = old[1:]
	return item.GValue()
}

// Head returns the first item of a Priority without removing it.
func (pq *Priority) Head() IPriority {
	if pq.Empty() {
		return nil
	}
	return pq.l[0]
}

func (pq *Priority) Peek() any {
	if pq.Empty() {
		return nil
	}
	return pq.l[0].GValue()
}

// Remove removes and returns the element at index i from the Priority.
func (pq *Priority) Remove(i int) any {
	if i < 0 && i >= pq.Len() {
		return nil
	}
	item := pq.l[i]
	pq.l = append(pq.l[:i], pq.l[i+1:]...)
	return item.GValue()
}

func (pq *Priority) Empty() bool {
	return pq.Len() == 0
}

// Find return index -1 not found.
func (pq *Priority) Find(fn IndexFunc) (any, int) {
	for i := range pq.l {
		if fn(pq.l[i], i) {
			return pq.l[i], i
		}
	}
	return nil, -1
}

func (pq *Priority) getInsertIndex(priority int64, leftIndex, rightIndex int) (index int) {
	if len(pq.l) == 0 {
		// 如果当前优先级切片没有元素，则插入的index就是0
		return 0
	}

	length := rightIndex - leftIndex
	if pq.l[leftIndex].PValue() >= priority {
		// 如果当前切片中最小的元素都超过了插入的优先级，则插入位置应该是最左边
		return leftIndex
	}

	if pq.l[rightIndex].PValue() <= priority {
		// 如果当前切片中最大的元素都没超过插入的优先级，则插入位置应该是最右边
		return rightIndex + 1
	}

	if length == 1 && pq.l[leftIndex].PValue() < priority && pq.l[rightIndex].PValue() >= priority {
		// 如果插入的优先级刚好在仅有的两个优先级之间，则中间的位置就是插入位置
		return leftIndex + 1
	}

	middleVal := pq.l[leftIndex+length/2].PValue()

	// 这里用二分法递归的方式，一直寻找正确的插入位置
	if priority <= middleVal {
		return pq.getInsertIndex(priority, leftIndex, leftIndex+length/2)
	}
	return pq.getInsertIndex(priority, leftIndex+length/2, rightIndex)
}