package heap

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

/**
 * @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 获取数据流的中位数
 * 如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
 * 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
 * <p>
 * 例如，[2,3,4]的中位数是 3
 * [2,3]的中位数是 (2 + 3) / 2 = 2.5
 * <p>
 * 设计一个支持以下两种操作的数据结构：
 * void Offer(int num) - 从数据流中添加一个整数到数据结构中。
 * double FindMedian() - 返回目前所有元素的中位数。
 * 解析：
 * 维护两个堆，一个大顶堆，一个小顶堆，保持两个堆数量平衡，
 * 取数的时候，分别取大顶堆的尾和小顶堆的头，平均一下即可。
 * */

type GetMidNum struct {
	lowQueue  *PriorityQueue
	highQueue *PriorityQueue
}

func NewGetMidNum() *GetMidNum {
	return &GetMidNum{
		lowQueue:  NewPriorityQueue(),
		highQueue: NewPriorityQueue(C.WithQueueType(true)),
	}
}

func (m *GetMidNum) Offer(value int) {
	if m.lowQueue.size == m.highQueue.size {
		if m.lowQueue.size != 0 && value > m.highQueue.Peak().(int) {
			m.lowQueue.Offer(m.highQueue.Poll())
			m.highQueue.Offer(value)
		} else {
			m.lowQueue.Offer(value)
		}
	} else {
		if value < m.lowQueue.Peak().(int) {
			m.highQueue.Offer(m.lowQueue.Poll())
			m.lowQueue.Offer(value)
		} else {
			m.highQueue.Offer(value)
		}
	}
}

func (m *GetMidNum) FindMedian() float64 {
	if m.lowQueue.size == 0 && m.highQueue.size == 0 {
		return C.ErrorFloat
	}
	if m.lowQueue.size == m.highQueue.size {
		return ((float64)(m.lowQueue.Peak().(int)) + (float64)(m.highQueue.Peak().(int))) / 2
	}
	return (float64)(m.lowQueue.Peak().(int))
}

func (m *GetMidNum) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.Heap},
		Desc: &C.Desc{
			Name:   "GetMidNum",
			NameCn: "获取数据流的中位数",
		},
	}
}