using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;




namespace ServerCore;

//=============================================================================================
// 우선 순위 정책에 의해 순서를 정렬해주는 컨테이너 클래스 이다.
//
// author : kangms
// 
// From http://visualstudiomagazine.com/articles/2012/11/01/priority-queues-with-c.aspx
//=============================================================================================

public class PriorityQueue<T> : IEnumerable<T> where T : IComparable<T>
{
    protected List<T> m_datas;

    public PriorityQueue()
    {
        m_datas = new();
    }

    // 큐에 새 데이터 추가
    public void enqueue(T item)
    {
        m_datas.Add(item);
        var child_index = m_datas.Count - 1;

        // binary heaps algorithm을 이용한 정렬
        while (child_index > 0)
        {
            var parent_index = (child_index - 1) / 2;
            if (m_datas[child_index].CompareTo(m_datas[parent_index]) >= 0)
            {
                break;
            }
            T tmp = m_datas[child_index];
            m_datas[child_index] = m_datas[parent_index];
            m_datas[parent_index] = tmp;
            child_index = parent_index;
        }
    }

    // 최상단 pop
    public T dequeue()
    {
        var last_index = m_datas.Count - 1;

        T frontItem = m_datas[0];   // fetch the front
        m_datas[0] = m_datas[last_index];
        m_datas.RemoveAt(last_index);

        --last_index; // last index (after removal)
        var parent_index = 0; // parent index. start at front of pq
                              // binary heaps algorithm을 이용한 정렬
        while (true)
        {
            var client_index = parent_index * 2 + 1; // left child index of parent
            if (client_index > last_index)
            {
                break;  // no children so done
            }

            var rc = client_index + 1;     // right child
            if (rc <= last_index && m_datas[rc].CompareTo(m_datas[client_index]) < 0) // if there is a rc (ci + 1), and it is smaller than left child, use the rc instead
            {
                client_index = rc;
            }

            if (m_datas[parent_index].CompareTo(m_datas[client_index]) <= 0)
            {
                break; // parent is smaller than (or equal to) smallest child so done
            }

            T tmp = m_datas[parent_index];
            m_datas[parent_index] = m_datas[client_index];
            m_datas[client_index] = tmp; // swap parent and child
            parent_index = client_index;
        }

        return frontItem;
    }

    // 최상단 얻기
    public T peek()
    {
        T frontItem = m_datas[0];
        return frontItem;
    }

    public Int32 count()
    {
        return m_datas.Count;
    }

    public virtual string toBasicString()
    {
        string str = "";
        for (Int32 index = 0; index < m_datas.Count; ++index)
        {
            str += m_datas[index].ToString() + " ";
        }
        str += "count = " + m_datas.Count;
        return str;
    }

    // 
    public bool isConsistent()
    {
        // is the heap property true for all data?
        if (m_datas.Count == 0)
        {
            return true;
        }

        var li = m_datas.Count - 1; // last index
        for (var parent_index = 0; parent_index < m_datas.Count; ++parent_index)
        { // each parent index
            var left_child_index = 2 * parent_index + 1; // left child index
            var right_child_index = 2 * parent_index + 2; // right child index

            if (left_child_index <= li && m_datas[parent_index].CompareTo(m_datas[left_child_index]) > 0)
            {
                return false; // if lc exists and it's greater than parent then bad.
            }
            if (right_child_index <= li && m_datas[parent_index].CompareTo(m_datas[right_child_index]) > 0)
            {
                return false; // check the right child too.
            }
        }
        return true; // passed all checks
    }

    public IEnumerator<T> GetEnumerator()
    {
        return m_datas.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}