package heap

import (
	C "gitee.com/ljfirst/algo-go-sdk/common/constant"
	sort "gitee.com/ljfirst/algo-go-sdk/src/data_structure/sort/inner_sort"
)

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/6/27 01:12
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 优先队列
 * */
type PriorityQueue struct {
	IsSmallHeap bool
	sortDown    *sort.HeapSort
	sortUp      *sort.HeapSort2
	queue       []interface{}
	size        int       // 实际容量
	maxSize     int       // 最大容量
	limitSize   int       // 限制容量
	Comp        C.Compare // 比较器
}

func NewPriorityQueue(options ...C.Options) *PriorityQueue {
	opt := C.NewOptions()
	for _, option := range options {
		option(opt)
	}
	return &PriorityQueue{
		IsSmallHeap: opt.IsSmallHeap,
		sortDown:    sort.NewHeapSort(options...),
		sortUp:      sort.NewHeapSort2(options...),
		queue:       make([]interface{}, 0, opt.MaxSize),
		size:        0,
		maxSize:     opt.MaxSize,
		limitSize:   opt.LimitSize,
		Comp:        opt.Compare,
	}
}

func (m *PriorityQueue) Offer(value interface{}) {
	if m.limitSize != 0 && m.size == m.limitSize {
		m.updatePeak(value)
		return
	}
	if m.size == m.maxSize {
		m.Resize()
	}
	m.queue = append(m.queue, value)
	m.sortUp.BuildHeapUp(m.queue, m.size)
	m.size++
}

func (m *PriorityQueue) Poll() interface{} {
	if len(m.queue) == 0 {
		return C.ErrorNum
	}
	value := m.queue[0]
	m.queue[0], m.queue[m.size-1] = m.queue[m.size-1], m.queue[0]
	m.queue = m.queue[:m.size-1]
	m.size--
	m.sortDown.BuildHeapDown(m.queue, 0, m.size-1)
	return value
}

func (m *PriorityQueue) Peak() interface{} {
	if len(m.queue) == 0 {
		return C.ErrorNum
	}
	return m.queue[0]
}

func (m *PriorityQueue) Update(value interface{}) () {
	if m.size == 0 {
		return
	}
	for i := (m.size - 1) / 2; i >= 0; i-- {
		//if !reflect.DeepEqual(m.queue[i], value) {
		if m.queue[i] != value {
			continue
		}
		// update operation
		m.sortDown.BuildHeapDown(m.queue, i, m.size-1)
		return
	}
	/*m.queue[0] = value
	m.sortDown.BuildHeapDown(m.queue, 0, m.size-1)*/
}

/* updatePeak
 * IsSmallHeap表示当前PriorityQueue是小顶堆，insert的元素value 如果小于堆顶，则直接过滤，如果大于堆顶，则替代堆顶，并重新排序
 * 大顶堆类似
 */
func (m *PriorityQueue) updatePeak(value interface{}) () {
	if (m.IsSmallHeap && !m.Comp(value, m.Peak())) || (!m.IsSmallHeap && !m.Comp(m.Peak(), value)) {
		return
	}
	m.queue[0] = value
	m.sortDown.BuildHeapDown(m.queue, 0, m.size-1)
}

func (m *PriorityQueue) Empty() bool {
	return m.size == 0
}

func (m *PriorityQueue) Size() int {
	return m.size
}
func (m *PriorityQueue) Resize() {
	m.maxSize *= 2
}

func (m *PriorityQueue) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.Heap, C.Queue},
		Desc: &C.Desc{
			Name:   "PriorityQueue",
			NameCn: "优先队列",
		},
	}
}