using System.Diagnostics;
using System.Collections.Generic;
public Fruit(string name, uint count)
public static void Main()
Console.WriteLine("Priority Queue Exercise");
PriorityQueue<Fruit> foo = new PriorityQueue<Fruit>(new CompareFruitCount());
foo.Push(new Fruit("Apple", 8));
foo.Push(new Fruit("Orange", 1));
foo.Push(new Fruit("Grape", 23));
foo.Push(new Fruit("Lemon", 5));
Console.WriteLine("Pop: "+foo.Pop().Name);
foo.Push(new Fruit("Cherry", 2));
foo[1] = new Fruit("Watermelon", 31);
if (foo.Contains(new Fruit("Grape", 23), new EqualFruitName()))
Console.Write("Contains");
Console.Write ("Doesn't contain");
public static void printQueue(PriorityQueue<Fruit> q)
for (int i=0; i<q.Count; i++)
Console.WriteLine("#"+i+": "+q[i].Name+" x "+q[i].Count);
internal class CompareFruitCount : IComparer<Fruit>
public int Compare(Fruit x, Fruit y)
else if (x.Count < y.Count)
internal class EqualFruitName : IEqualityComparer<Fruit>
public bool Equals(Fruit x, Fruit y)
public int GetHashCode(Fruit x)
return x.Name.GetHashCode();
public class PriorityQueue<T>
protected List<T> MyList = new List<T>();
protected IComparer<T> Comparer;
protected IEqualityComparer<T> EqualityComparer;
get{return MyList.Count;}
Comparer = Comparer<T>.Default;
public PriorityQueue(IComparer<T> comparer)
protected void Swap(int i, int j)
Debug.WriteLine("index: "+i);
protected virtual int OnCompare(int i, int j)
return Comparer.Compare(MyList[i], MyList[j]);
if (OnCompare(p, pParent)<0)
int pLeftChild, pRightChild, pPrevious;
MyList[0] = MyList[MyList.Count-1];
MyList.RemoveAt(MyList.Count-1);
if (MyList.Count > pLeftChild && OnCompare(p, pLeftChild)>0)
if (MyList.Count > pRightChild && OnCompare(p, pRightChild)>0)
private void Update(int i)
int pParent, pLeftChild, pRightChild;
Debug.WriteLine(p+", "+pParent);
if(OnCompare(p, pParent)<0)
Debug.WriteLine("pPrevious="+pPrevious+", pLeftChild="+pLeftChild+", pRightChild="+pRightChild);
if (MyList.Count > pLeftChild && OnCompare(p, pLeftChild)>0)
if (MyList.Count > pRightChild && OnCompare(p, pRightChild)>0)
get {return MyList[index]; }
public bool Contains(T target, IEqualityComparer<T> comparer)
for (int i=0; i<MyList.Count; i++)
if (comparer.Equals(MyList[i], target))