using System;
using System.Collections.Generic;

namespace System.Reactive
{
	internal sealed class PriorityQueue<T> where T : IComparable<T>
	{
		public PriorityQueue()
			: this(16)
		{
		}

		public PriorityQueue(int capacity)
		{
			this._items = new PriorityQueue<T>.IndexedItem[capacity];
			this._size = 0;
		}

		private bool IsHigherPriority(int left, int right)
		{
			return this._items[left].CompareTo(this._items[right]) < 0;
		}

		private int Percolate(int index)
		{
			if (index < this._size && index >= 0)
			{
				int num = (index - 1) / 2;
				while (num >= 0 && num != index && this.IsHigherPriority(index, num))
				{
					PriorityQueue<T>.IndexedItem indexedItem = this._items[index];
					this._items[index] = this._items[num];
					this._items[num] = indexedItem;
					index = num;
					num = (index - 1) / 2;
				}
				return index;
			}
			return index;
		}

		private void Heapify(int index)
		{
			if (index < this._size)
			{
				if (index >= 0)
				{
					for (;;)
					{
						int num = 2 * index + 1;
						int num2 = 2 * index + 2;
						int num3 = index;
						if (num < this._size && this.IsHigherPriority(num, num3))
						{
							num3 = num;
						}
						if (num2 < this._size && this.IsHigherPriority(num2, num3))
						{
							num3 = num2;
						}
						if (num3 == index)
						{
							break;
						}
						PriorityQueue<T>.IndexedItem indexedItem = this._items[index];
						this._items[index] = this._items[num3];
						this._items[num3] = indexedItem;
						index = num3;
					}
					return;
				}
			}
		}

		public int Count
		{
			get
			{
				return this._size;
			}
		}

		public T Peek()
		{
			if (this._size == 0)
			{
				throw new InvalidOperationException(Strings_Core.HEAP_EMPTY);
			}
			return this._items[0].Value;
		}

		private void RemoveAt(int index)
		{
			PriorityQueue<T>.IndexedItem[] items = this._items;
			PriorityQueue<T>.IndexedItem[] items2 = this._items;
			int num = this._size - 1;
			this._size = num;
			items[index] = items2[num];
			this._items[this._size] = default(PriorityQueue<T>.IndexedItem);
			if (this.Percolate(index) == index)
			{
				this.Heapify(index);
			}
			if (this._size < this._items.Length / 4)
			{
				Array items3 = this._items;
				this._items = new PriorityQueue<T>.IndexedItem[this._items.Length / 2];
				Array.Copy(items3, 0, this._items, 0, this._size);
			}
		}

		public T Dequeue()
		{
			T t = this.Peek();
			this.RemoveAt(0);
			return t;
		}

		public void Enqueue(T item)
		{
			if (this._size >= this._items.Length)
			{
				PriorityQueue<T>.IndexedItem[] items = this._items;
				this._items = new PriorityQueue<T>.IndexedItem[this._items.Length * 2];
				Array.Copy(items, this._items, items.Length);
			}
			int size = this._size;
			this._size = size + 1;
			int num = size;
			PriorityQueue<T>.IndexedItem[] items2 = this._items;
			int num2 = num;
			PriorityQueue<T>.IndexedItem indexedItem = default(PriorityQueue<T>.IndexedItem);
			indexedItem.Value = item;
			long num3 = this._count + 1L;
			this._count = num3;
			indexedItem.Id = num3;
			items2[num2] = indexedItem;
			this.Percolate(num);
		}

		public bool Remove(T item)
		{
			for (int i = 0; i < this._size; i++)
			{
				if (EqualityComparer<T>.Default.Equals(this._items[i].Value, item))
				{
					this.RemoveAt(i);
					return true;
				}
			}
			return false;
		}

		private long _count = long.MinValue;

		private PriorityQueue<T>.IndexedItem[] _items;

		private int _size;

		private struct IndexedItem : IComparable<PriorityQueue<T>.IndexedItem>
		{
			public int CompareTo(PriorityQueue<T>.IndexedItem other)
			{
				int num = this.Value.CompareTo(other.Value);
				if (num == 0)
				{
					num = this.Id.CompareTo(other.Id);
				}
				return num;
			}

			public T Value;

			public long Id;
		}
	}
}
