using System;
using System.Collections;
using System.IO;
using System.Runtime.Serialization.Formatters.Binary;
using NUnit.Framework;
using Spring.Util;

namespace Spring.Collections
{
	[TestFixture]
	public class PriorityQueueTests
	{
		protected static Int32 zero = Int32.Parse("0");
		protected static Int32 one = Int32.Parse("1");
		protected static Int32 two = Int32.Parse("2");
		protected static Int32 three = Int32.Parse("3");
		protected static Int32 four = Int32.Parse("4");
		protected static Int32 five = Int32.Parse("5");
		protected static Int32 six = Int32.Parse("6");
		protected static Int32 seven = Int32.Parse("7");
		protected static Int32 eight = Int32.Parse("8");
		protected static Int32 nine = Int32.Parse("9");
		protected static Int32 m1 = Int32.Parse("-1");
		protected static Int32 m2 = Int32.Parse("-2");
		protected static Int32 m3 = Int32.Parse("-3");
		protected static Int32 m4 = Int32.Parse("-4");
		protected static Int32 m5 = Int32.Parse("-5");
		protected static Int32 m10 = Int32.Parse("-10");
		private int SIZE = 20;

		internal class MyReverseComparator : IComparer
		{
			public virtual int Compare(Object x, Object y)
			{
				int i = (int)x;
				int j = (int)y;
				if (i < j)
					return 1;
				if (i > j)
					return - 1;
				return 0;
			}
		}

		private PriorityQueue populatedQueue(int n)
		{
			PriorityQueue q = new PriorityQueue(n);
			Assert.IsTrue((q.Count == 0));
			for (int i = n - 1; i >= 0; i -= 2)
				Assert.IsTrue(q.Offer(i));
			for (int i = (n & 1); i < n; i += 2)
				Assert.IsTrue(q.Offer(i));
			Assert.IsFalse((q.Count == 0));
			Assert.AreEqual(n, q.Count);
			return q;
		}

		[Test]
		public void CreateUnboundedQueue()
		{
			Assert.AreEqual(0, new PriorityQueue(SIZE).Count);
		}

		[Test]
		[ExpectedException(typeof (ArgumentException))]
		public void ThrowsArgumentExceptionForZeroCapacity()
		{
			new PriorityQueue(0);
		}

		[Test]
		[ExpectedException(typeof (ArgumentNullException))]
		public void ThrowsArgumentNullExceptionForNullCollection()
		{
			PriorityQueue q = new PriorityQueue((ICollection) null);
		}

		[Test]
			[ExpectedException(typeof(ArgumentNullException))]
		public void ThrowsArgumentNullExceptionForNullCollectionElements()
		{
			object[] ints = new object[SIZE];
			PriorityQueue q = new PriorityQueue(new ArrayList(ints));
		}

		[Test]
		[ExpectedException(typeof (ArgumentNullException))]
		public void ThrowsArgumentNullExceptionForSomeNullCollectionElements()
		{
			object[] ints = new object[SIZE];
			for (int i = 0; i < SIZE - 1; ++i)
				ints[i] = i;
			PriorityQueue q = new PriorityQueue(new ArrayList(ints));
		}

		[Test]
		public void ConstructorFromExistingCollection()
		{
			Int32[] ints = new Int32[SIZE];
			for (int i = 0; i < SIZE; ++i)
				ints[i] = i;
			PriorityQueue q = new PriorityQueue(new ArrayList(ints));
			for (int i = 0; i < SIZE; ++i)
				Assert.AreEqual(ints[i], q.Poll());
			Assert.IsTrue( q.IsEmpty );
		}

		[Test]
		public void ConstructorUsingComparator()
		{
			MyReverseComparator cmp = new MyReverseComparator();
			PriorityQueue q = new PriorityQueue(SIZE, cmp);
			Assert.AreEqual(cmp, q.Comparator());
			Int32[] ints = new Int32[SIZE];
			for (int i = 0; i < SIZE; ++i)
				ints[i] = i;
			q.AddAll(new ArrayList(ints));
			for (int i = SIZE - 1; i >= 0; --i)
				Assert.AreEqual(ints[i], q.Poll());
			Assert.IsTrue( q.IsEmpty );
		}

		[Test]
		public void IsEmpty()
		{
			PriorityQueue q = new PriorityQueue(2);
			Assert.IsTrue( q.IsEmpty );
			q.Add(1);
			Assert.IsFalse( q.IsEmpty );
			q.Add(2);
			q.Remove();
			q.Remove();
			Assert.IsTrue( q.IsEmpty );
		}

		[Test]
		public void Size()
		{
			PriorityQueue q = populatedQueue(SIZE);
			for (int i = 0; i < SIZE; ++i)
			{
				Assert.AreEqual(SIZE - i, q.Count);
				q.Remove();
			}
			for (int i = 0; i < SIZE; ++i)
			{
				Assert.AreEqual(i, q.Count);
				q.Add(i);
			}
		}

		[Test]
		[ExpectedException(typeof (ArgumentNullException))]
		public void OfferWithNullObject()
		{
			PriorityQueue q = new PriorityQueue(1);
			q.Offer(null);
		}

		[Test]
		[ExpectedException(typeof (ArgumentNullException))]
		public void AddWithNullObject()
		{
			PriorityQueue q = new PriorityQueue(1);
			q.Add(null);
		}

		[Test]
		public void OfferWithComparableElements()
		{
			PriorityQueue q = new PriorityQueue(1);
			Assert.IsTrue(q.Offer(zero));
			Assert.IsTrue(q.Offer(one));
		}

		[Test]
		[ExpectedException(typeof (InvalidCastException))]
		public void OfferNonComparable()
		{
			PriorityQueue q = new PriorityQueue(1);
			q.Offer(new Object());
			q.Offer(new Object());
			q.Offer(new Object());
		}

		[Test]
		public void AddWithComparableElements()
		{
			PriorityQueue q = new PriorityQueue(SIZE);
			for (int i = 0; i < SIZE; ++i)
			{
				Assert.AreEqual(i, q.Count);
				Assert.IsTrue(q.Add(i));
			}
		}

		[Test]
		[ExpectedException(typeof (ArgumentNullException))]
		public void AddAllWithNullElements()
		{
			PriorityQueue q = new PriorityQueue(1);
			q.AddAll(null);
		}

		[Test]
		[ExpectedException(typeof (ArgumentNullException))]
		public void AddAllWithCollectionWithNullElements()
		{
			PriorityQueue q = new PriorityQueue(SIZE);
			object[] ints = new object[SIZE];
			q.AddAll(new ArrayList(ints));
		}

		[Test]
		[ExpectedException(typeof (ArgumentNullException))]
		public void AddAllWithCollectionWithSomeNullElements()
		{
			PriorityQueue q = new PriorityQueue(SIZE);
			object[] ints = new object[SIZE];
			for (int i = 0; i < SIZE - 1; ++i)
				ints[i] = i;
			q.AddAll(new ArrayList(ints));
		}

		[Test]
		public void AddAllWithCollection()
		{
			Int32[] empty = new Int32[0];
			Int32[] ints = new Int32[SIZE];
			for (int i = 0; i < SIZE; ++i)
				ints[i] = (SIZE - 1 - i);
			PriorityQueue q = new PriorityQueue(SIZE);
			Assert.IsFalse(q.AddAll(new ArrayList(empty)));
			Assert.IsTrue(q.AddAll(new ArrayList(ints)));
			for (int i = 0; i < SIZE; ++i)
				Assert.AreEqual(i, q.Poll());
		}

		[Test]
		public void Poll()
		{
			PriorityQueue q = populatedQueue(SIZE);
			for (int i = 0; i < SIZE; ++i)
			{
				Assert.AreEqual(i, (q.Poll()));
			}
			Assert.IsNull(q.Poll());
		}

		[Test]
		public void Peek()
		{
			PriorityQueue q = populatedQueue(SIZE);
			for (int i = 0; i < SIZE; ++i)
			{
				Assert.AreEqual(i, (q.Peek()));
				q.Poll();
				Assert.IsTrue(q.Peek() == null || i != (int)(q.Peek()));
			}
			Assert.IsNull(q.Peek());
		}

		[Test]
		[ExpectedException(typeof (NoElementsException))]
		public void Element()
		{
			PriorityQueue q = populatedQueue(SIZE);
			for (int i = 0; i < SIZE; ++i)
			{
				Assert.AreEqual(i, (q.Element()));
				q.Poll();
			}
			q.Element();
		}

		[Test]
		[ExpectedException(typeof (NoElementsException))]
		public void Remove()
		{
			PriorityQueue q = populatedQueue(SIZE);
			for (int i = 0; i < SIZE; ++i)
			{
				Assert.AreEqual(i, (q.Remove()));
			}
			q.Remove();
		}

		[Test]
		public void RemoveElement()
		{
			PriorityQueue q = populatedQueue(SIZE);
			for (int i = 1; i < SIZE; i += 2)
			{
				Assert.IsTrue(q.Remove(i));
			}
			for (int i = 0; i < SIZE; i += 2)
			{
				Assert.IsTrue(q.Remove(i));
				Assert.IsFalse(q.Remove((i + 1)));
			}
			Assert.IsTrue((q.Count == 0));
		}

		[Test]
		public void Contains()
		{
			PriorityQueue q = populatedQueue(SIZE);
			for (int i = 0; i < SIZE; ++i)
			{
				Assert.IsTrue(CollectionUtils.Contains(q, i));
				q.Poll();
				Assert.IsFalse(CollectionUtils.Contains(q, i));
			}
		}

		[Test]
		public void Clear()
		{
			PriorityQueue q = populatedQueue(SIZE);
			q.Clear();
			Assert.IsTrue((q.Count == 0));
			Assert.AreEqual(0, q.Count);
			q.Add(1);
			Assert.IsFalse((q.Count == 0));
			q.Clear();
			Assert.IsTrue((q.Count == 0));
		}

		[Test]
		public void ContainsAll()
		{
			PriorityQueue q = populatedQueue(SIZE);
			PriorityQueue p = new PriorityQueue(SIZE);
			for (int i = 0; i < SIZE; ++i)
			{
				Assert.IsTrue(CollectionUtils.ContainsAll(q, p));
				Assert.IsFalse(CollectionUtils.ContainsAll(p, q));
				p.Add(i);
			}
			Assert.IsTrue(CollectionUtils.ContainsAll(p, q));
		}

		[Test]
		public void RemoveAll()
		{
			for (int i = 1; i < SIZE; ++i)
			{
				PriorityQueue q = populatedQueue(SIZE);
				PriorityQueue p = populatedQueue(i);
				CollectionUtils.RemoveAll(q, p);
				Assert.AreEqual(SIZE - i, q.Count);
				for (int j = 0; j < i; ++j)
				{
					Int32 I = (int) p.Remove();
					Assert.IsFalse(CollectionUtils.Contains(q, I));
				}
			}
		}

		[Test]
		public void ToArrayObject()
		{
			PriorityQueue q = populatedQueue(SIZE);
			Object[] o = (Object[]) CollectionUtils.ToArrayList(q).ToArray(typeof (object));
			Array.Sort(o);
			for (int i = 0; i < o.Length; i++)
				Assert.AreEqual(o[i], q.Poll());
		}

		[Test]
		public void ToArrayNonObject()
		{
			PriorityQueue q = populatedQueue(SIZE);
			Int32[] ints = (Int32[]) CollectionUtils.ToArrayList(q).ToArray(typeof (int));
			Array.Sort(ints);
			for (int i = 0; i < ints.Length; i++)
				Assert.AreEqual(ints[i], q.Poll());
		}

		[Test]
		public void Iterator()
		{
			PriorityQueue q = populatedQueue(SIZE);
			int i = 0;
			IEnumerator it = q.GetEnumerator();
			while (it.MoveNext())
			{
				Assert.IsTrue(CollectionUtils.Contains(q, it.Current));
				++i;
			}
			Assert.AreEqual(i, SIZE);
		}

		[Test]
		public void Serialization()
		{
			PriorityQueue q = populatedQueue(SIZE);
			MemoryStream bout = new MemoryStream(10000);

			BinaryFormatter formatter = new BinaryFormatter();
			formatter.Serialize(bout, q);

			MemoryStream bin = new MemoryStream(bout.ToArray());
			BinaryFormatter formatter2 = new BinaryFormatter();

			PriorityQueue r = (PriorityQueue) formatter2.Deserialize(bin);

			Assert.AreEqual(q.Count, r.Count);
			while (!(q.Count == 0))
				Assert.AreEqual(q.Remove(), r.Remove());
		}
		[Test]
			[ExpectedException(typeof(ArgumentException))]
			public void QueueCopyToArrayWithSmallerDestinationArray()
		{
			PriorityQueue source = populatedQueue(SIZE);
			object[] dest = new object[SIZE/2];
			source.CopyTo(dest);
		}
		[Test]
		[ExpectedException(typeof(ArgumentException))]
		public void QueueCopyToArrayWithIndexOutOfDestinationArrayRange()
		{
			PriorityQueue source = populatedQueue(SIZE);
			object[] dest = new object[SIZE/2];
			source.CopyTo(dest, 11);
		}
		[Test]
		[ExpectedException(typeof(IndexOutOfRangeException))]
			public void QueueCopyToArrayWithValidSizeButInvalidStartingIndex()
		{
			PriorityQueue source = populatedQueue(SIZE);
			object[] dest = new object[SIZE];
			source.CopyTo(dest, 10);
		}
		[Test]
			public void CompleteQueueCopyToArrayWithValidSize()
		{
			PriorityQueue source = populatedQueue(SIZE);
			object[] dest = new object[SIZE];
			source.CopyTo(dest);
			for ( int i = 0; i < SIZE; i++ )
			{
				Assert.AreEqual(source.Poll(), dest[i]);
			}
		}
		[Test]
			public void PartialQueueCopyToArrayWithValidSize()
		{
			PriorityQueue source = populatedQueue(SIZE);
			object[] dest = new object[SIZE*2];
			source.CopyTo(dest, SIZE / 2);
			for ( int i = 0; i < SIZE; i++ )
			{
				Assert.IsNull(dest[i]);
			}
			for ( int i = SIZE; i < SIZE / 2; i++ )
			{
				Assert.AreEqual(dest[i], i - SIZE / 2 );
			}
		}
	}
}