151 lines
4.3 KiB
C#
151 lines
4.3 KiB
C#
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();
|
|
}
|
|
}
|