HX_MapEditor/Assets/Scripts/PathFinding/PriorityQueueB.cs

using System;
using System.Collections.Generic;

namespace HxGame.PathFinding
{
	public interface IPriorityQueue<T>
	{
		int Push(T item);

		T Pop();

		T Peek();

		void Update(int i);
	}

	public class PriorityQueueB<T> : IPriorityQueue<T>
	{
		protected T[] InnerList;
		protected IComparer<T> mComparer;
		protected int InnerListCount;

		public PriorityQueueB()
		{
			mComparer = Comparer<T>.Default;
			InnerList = new T[4096];
			InnerListCount = 0;
		}

		public PriorityQueueB(IComparer<T> comparer)
		{
			mComparer = comparer;
			InnerList = new T[4096];
			InnerListCount = 0;
		}

		public IComparer<T> comparer { get { return mComparer; } }


		protected void SwapElements(int i, int j)
		{
			T h = InnerList[i];
			InnerList[i] = InnerList[j];
			InnerList[j] = h;
		}

		protected virtual int OnCompare(int i, int j)
		{
			return mComparer.Compare(InnerList[i], InnerList[j]);
		}


		// <returns><3E>б<EFBFBD><D0B1>ж<EFBFBD><D0B6><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD><DAB5><EFBFBD><EFBFBD><EFBFBD></returns>
		public int Push(T item)
		{
			int p = InnerListCount, p2;
			if (InnerListCount >= InnerList.Length)
			{
				ResizeInnerList();
			}
			InnerList[InnerListCount++] = item;
			do
			{
				if (p == 0)
					break;
				p2 = (p - 1) / 2;
				T InnerListp = InnerList[p];
				T InnerListp2 = InnerList[p2];
				if (mComparer.Compare(InnerListp, InnerListp2) < 0)
				{
					// Swap
					InnerList[p] = InnerListp2;
					InnerList[p2] = InnerListp;
					p = p2;
				}
				else
					break;
			} while (true);
			return p;
		}

		void ResizeInnerList()
		{
			T[] newInnerList = new T[InnerListCount * 2];
			Array.Copy(InnerList, newInnerList, InnerListCount);
			InnerList = newInnerList;
		}

		/// <summary>
		/// <20><>ȡ<EFBFBD><C8A1>С<EFBFBD>Ķ<EFBFBD><C4B6><EFBFBD>
		/// </summary>
		/// <returns></returns>
		public T Pop()
		{
			T result = InnerList[0];
			int p = 0, p1, p2, pn;
			int count = InnerListCount - 1;
			InnerList[0] = InnerList[count]; // InnerList.Count - 1
			InnerListCount--;
			do
			{
				pn = p;
				p1 = 2 * p + 1;
				p2 = p1 + 1; //2 * p + 2;

				if (count > p1)
				{
					if (mComparer.Compare(InnerList[p], InnerList[p1]) > 0)
					{
						p = p1;
					}
				}
				if (count > p2)
				{
					if (mComparer.Compare(InnerList[p], InnerList[p2]) > 0)
					{
						p = p2;
					}
				}

				if (p == pn)
					break;

				// Swap
				T h = InnerList[p];
				InnerList[p] = InnerList[pn];
				InnerList[pn] = h;

			} while (true);

			return result;
		}

		/// <summary>
		/// ֪ͨ<CDA8><D6AA><EFBFBD><EFBFBD>λ<EFBFBD><CEBB>i<EFBFBD><69><EFBFBD>Ķ<EFBFBD><C4B6><EFBFBD><EFBFBD>Ѹ<EFBFBD><D1B8><EFBFBD>
		/// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ҫ<EFBFBD>ָ<EFBFBD><D6B8><EFBFBD><EFBFBD><EFBFBD>
		/// <20><>Ϊ<EFBFBD><CEAA><EFBFBD><EFBFBD>Ȩ<EFBFBD><C8A8><EFBFBD><EFBFBD><EFBFBD>κ<EFBFBD><CEBA><EFBFBD><EFBFBD><EFBFBD>(<28><><EFBFBD><EFBFBD>ʹ<EFBFBD><CAB9><EFBFBD><EFBFBD>ʽIList.this)
		/// <20><><EFBFBD><EFBFBD>Ӧ<EFBFBD><D3A6><EFBFBD>ڲ<EFBFBD>ȷ<EFBFBD><C8B7>֪<EFBFBD><D6AA><EFBFBD>Լ<EFBFBD><D4BC><EFBFBD><EFBFBD><EFBFBD>ʲô<CAB2><C3B4><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>µ<EFBFBD><C2B5>ô˺<C3B4><CBBA><EFBFBD><EFBFBD><EFBFBD>
		/// </summary>
		/// <param name="i"><3E><><EFBFBD>Ķ<EFBFBD><C4B6><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD></param>
		public void Update(int i)
		{
			int p = i, pn;
			int p1, p2;
			do
			{   // aufsteigen
				if (p == 0)
					break;
				p2 = (p - 1) / 2;
				if (OnCompare(p, p2) < 0)
				{
					SwapElements(p, p2);
					p = p2;
				}
				else
					break;
			} while (true);
			if (p < i)
				return;
			do
			{      // absteigen
				pn = p;
				p1 = 2 * p + 1;
				p2 = 2 * p + 2;
				if (InnerListCount > p1 && OnCompare(p, p1) > 0) // links kleiner
					p = p1;
				if (InnerListCount > p2 && OnCompare(p, p2) > 0) // rechts noch kleiner
					p = p2;

				if (p == pn)
					break;
				SwapElements(p, pn);
			} while (true);
		}

		/// <summary>
		/// <20>ڲ<EFBFBD><DAB2>Ƴ<EFBFBD><C6B3><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>»<EFBFBD>ȡ<EFBFBD><C8A1>С<EFBFBD>Ķ<EFBFBD><C4B6><EFBFBD>
		/// </summary>
		/// <returns><3E><>С<EFBFBD>Ķ<EFBFBD><C4B6><EFBFBD></returns>
		public T Peek()
		{
			if (InnerListCount > 0)
				return InnerList[0];
			return default(T);
		}

		public void Clear()
		{
			InnerListCount = 0; //.Clear ();
		}

		public int Count
		{
			get { return InnerListCount; }
		}

		public void RemoveLocation(T item)
		{
			int index = -1;
			for (int i = 0; i < InnerListCount; i++)
			{
				if (mComparer.Compare(InnerList[i], item) == 0)
				{
					index = i;
					break;
				}
			}

			if (index != -1)
			{
				//InnerList.RemoveAt (index);
				for (int i = index; i < InnerListCount - 1; i++)
				{
					InnerList[i] = InnerList[i + 1];
				}
				InnerListCount--;
			}
		}

		public T this[int index]
		{
			get { return InnerList[index]; }
			set
			{
				InnerList[index] = value;
				Update(index);
			}
		}
	}
}