ordereddictionarytests.cs

C#写的类似于STL的集合类,首先是C#编写,可以用于.net变程.

//******************************
// Written by Peter Golde
// Copyright (c) 2004-2005, Wintellect
//
// Use and restribution of this code is subject to the license agreement 
// contained in the file "License.txt" accompanying this file.
//******************************

using System;
using System.Collections;
using System.Collections.Generic;
using NUnit.Framework;

namespace Wintellect.PowerCollections.Tests
{
	/// <summary>
	/// Tests for testing the OrderedDictionary class.
	/// </summary>
	[TestFixture]
	public class OrderedDictionaryTests
	{
		const int LENGTH = 1200;			// length of each random array of values.
		const int ITERATIONS = 80;		// number of iterations
		private OrderedDictionary<int,string> dict;

		/// <summary>
		/// Create a string from an integer
		/// </summary>
		/// <param name="i">The int.</param>
		/// <returns>The string made from the int.</returns>
		private string StringFromInt(int i)
		{
			return string.Format("e{0}", i);
		}

		/// <summary>
		/// Create a random array of values.
		/// </summary>
		/// <param name="seed">Seed for random number generators</param>
		/// <param name="length">Length of array</param>
		/// <param name="max">Maximum value of number. Should be much 
		/// greater than length.</param>
		/// <param name="allowDups">Whether to allow duplicate elements.</param>
		/// <returns></returns>
		private int[] CreateRandomArray(int seed, int length, int max, bool allowDups)
		{
			Random rand = new Random(seed);
			int[] a = new int[length];

			for (int i = 0; i < a.Length; ++i)
				a[i] = -1;

			for (int el = 0; el < a.Length; ++el)
			{
				int value;

				do
				{
					value = rand.Next(max);
				} while (!allowDups && Array.IndexOf(a, value) >= 0);

				a[el] = value;
			}

			return a;
		}
		/// <summary>
		/// Insert all the elements of an integer array into the dictionary. The
		/// values in the dictionary are the indexes of the array.
		/// </summary>
		/// <param name="a">Array of values to insert.</param>
		private void InsertArray(int[] a)
		{
			for (int i = 0; i < a.Length; ++i)
			{
				string s = StringFromInt(i);

				dict.Add(a[i], s);
			}
		}

		/// <summary>
		/// Iterate the dictionary, making sure that everything is in order, the values
		/// match, and that all the keys in the array are found.
		/// </summary>
		/// <param name="a"></param>
		private void CheckArray(int[] a)
		{
			int count = 0;
			int lastKey = -1;

			foreach (KeyValuePair<int,string> pair in dict)
			{
				Assert.IsTrue(lastKey < pair.Key, "Keys are not in order");

				int index = Array.IndexOf(a, pair.Key);

				Assert.IsTrue(index >= 0, "key wasn't found in the array");
				Assert.AreEqual(StringFromInt(index), pair.Value);
				a[index] = -1;

				++count;
                lastKey = pair.Key;
			}

			Assert.AreEqual(count, dict.Count, "Number of keys found is not correct");

			// All the items should have been knocked out.
			foreach (int x in a)
			{
				Assert.AreEqual(-1, x);
			}
		}

		/// <summary>
		/// Insert a bunch of entries into the tree, make sure that the count is correct, 
		/// and that they iterate correct in order.
		/// </summary>
		[Test]
		public void RandomAdd()
		{
			for (int iter = 0; iter < ITERATIONS; ++iter)
			{
				// Insert the array into the dictionary.
				dict = new OrderedDictionary<int,string>();

				int[] a = CreateRandomArray(iter + 1, LENGTH, LENGTH * 10, false);

				InsertArray(a);

				// Make sure the count is correct.
				Assert.AreEqual(LENGTH, dict.Count);
				CheckArray(a);
			}
		}

        private void CheckArgumentException(Exception e)
        {
            Assert.IsTrue(e is ArgumentException);
            Assert.IsTrue(((ArgumentException)e).ParamName == "key");
        }

        /// <summary>
        /// Test adding keys/values to the collection. Make sure the return value is right, and that
        /// the keys are present in the collection afterward.
        /// </summary>
        [Test]
        public void Add()
        {
            OrderedDictionary<double, int> dict1 = new OrderedDictionary<double, int>();

            dict1.Add(4.67, 12);
            dict1.Add(double.NaN, -17);
            dict1.Add(double.PositiveInfinity, 0);
            try {
                dict1.Add(4.67, 187); Assert.Fail("Exception should be thrown");
            }
            catch (Exception e) {
                CheckArgumentException(e);
            }
            dict1.Add(double.NegativeInfinity, 188921);
            try {
                dict1.Add(double.NegativeInfinity, 421); Assert.Fail("Exception should be thrown");
            }
            catch (Exception e) {
                CheckArgumentException(e);
            }
            try {
                dict1.Add(4.67, 222); Assert.Fail("Exception should be thrown");
            }
            catch (Exception e) {
                CheckArgumentException(e);
            }

            dict1.Add(double.MaxValue, 444);

            Assert.AreEqual(5, dict1.Count);

            Assert.AreEqual(12, dict1[4.67]);
            Assert.AreEqual(188921, dict1[double.NegativeInfinity]);
            Assert.AreEqual(0, dict1[double.PositiveInfinity]);
            Assert.AreEqual(-17, dict1[double.NaN]);
            Assert.AreEqual(444, dict1[double.MaxValue]);

            InterfaceTests.TestReadonlyCollectionGeneric(dict1.Keys, new double[] { double.NaN, double.NegativeInfinity, 4.67, double.MaxValue, double.PositiveInfinity }, true, "KeysCollection");
            InterfaceTests.TestReadonlyCollectionGeneric(dict1.Values, new int[] { -17, 188921, 12, 444, 0 }, true, "ValuesCollection");
        }

#if false
        /// <summary>
		/// Test adding keys/values to the collection. Make sure the return value is right, and that
		/// the keys are present in the collection afterward.
		/// </summary>
		[Test]
		public void AddOrUpdate()
		{
			OrderedDictionary<double,int> dict1 = new OrderedDictionary<double,int>();
			bool b;

			b = dict1.AddOrUpdate(4.67, 12);
			Assert.IsFalse(b);
			b = dict1.AddOrUpdate(double.NaN, -17);
			Assert.IsFalse(b);
			b = dict1.AddOrUpdate(double.PositiveInfinity, 0);
			Assert.IsFalse(b);
			b = dict1.AddOrUpdate(4.67, 187);
			Assert.IsTrue(b);
			b = dict1.AddOrUpdate(double.NegativeInfinity, 188921);
			Assert.IsFalse(b);
			b = dict1.AddOrUpdate(double.NegativeInfinity, 421);
			Assert.IsTrue(b);
			b = dict1.AddOrUpdate(4.67, 222);
			Assert.IsTrue(b);
			b = dict1.AddOrUpdate(double.MaxValue, 444);
			Assert.IsFalse(b);

			Assert.AreEqual(5, dict1.Count);

			Assert.AreEqual(222, dict1[4.67]);
			Assert.AreEqual(421, dict1[double.NegativeInfinity]);
			Assert.AreEqual(0, dict1[double.PositiveInfinity]);
			Assert.AreEqual(-17, dict1[double.NaN]);
			Assert.AreEqual(444, dict1[double.MaxValue]);

			TestUtil.TestReadonlyCollectionGeneric(dict1.Keys, new double[] { double.NaN, double.NegativeInfinity, 4.67, double.MaxValue, double.PositiveInfinity }, true, "KeysCollection");
			TestUtil.TestReadonlyCollectionGeneric(dict1.Values, new int[] { -17, 421, 222, 444, 0 }, true, "ValuesCollection");
		}
#endif

        /// <summary>
        /// Test updating. 
        /// </summary>
        [Test]
        public void Update()
        {
            OrderedDictionary<double, int> dict1 = new OrderedDictionary<double, int>();

            dict1.Add(4.67, 12);
            dict1.Add(double.NaN, -17);
            dict1.Add(double.PositiveInfinity, 0);
            dict1.Add(double.MaxValue, 441);
            dict1.Replace(4.67, -89);
            try {
                dict1.Replace(double.NegativeInfinity, 187); Assert.Fail("Exception should be thrown");
            }
            catch (Exception e) {
                Assert.IsTrue(e is KeyNotFoundException);
            }
            dict1.Add(double.NegativeInfinity, 188921);
            dict1.Replace(double.MaxValue, -1);
            dict1.Replace(double.NaN, 188);
            try {
                dict1.Replace(12, 3); Assert.Fail("Exception should be thrown");
            }
            catch (Exception e) {
                Assert.IsTrue(e is KeyNotFoundException);
            }

            dict1.Replace(double.MaxValue, 33);

            Assert.AreEqual(5, dict1.Count);

            Assert.AreEqual(-89, dict1[4.67]);
            Assert.AreEqual(188921, dict1[double.NegativeInfinity]);
            Assert.AreEqual(0, dict1[double.PositiveInfinity]);
            Assert.AreEqual(188, dict1[double.NaN]);
            Assert.AreEqual(33, dict1[double.MaxValue]);
            Assert.IsFalse(dict1.ContainsKey(12));

            InterfaceTests.TestReadonlyCollectionGeneric(dict1.Keys, new double[] { double.NaN, double.NegativeInfinity, 4.67, double.MaxValue, double.PositiveInfinity }, true, "KeysCollection");
            InterfaceTests.TestReadonlyCollectionGeneric(dict1.Values, new int[] { 188, 188921, -89, 33, 0 }, true, "ValuesCollection");
        }

        /// <summary>
        /// Test adding keys/values to the collection. Like the Add() test, but uses the indexer dict operation.
		/// Make sure the return value is right, and that
		/// the keys are present in the collection afterward.
		/// </summary>
		[Test]
		public void IndexerSet()
		{
			OrderedDictionary<double,int> dict1 = new OrderedDictionary<double,int>();

			dict1[4.67] = 12;
			dict1[double.NaN] = -17;
			dict1[double.PositiveInfinity] = 0;
			dict1[4.67] = 187;
			dict1[double.NegativeInfinity] = 188921;
			dict1[double.NegativeInfinity] = 421;
			dict1[4.67] = 222;
			dict1[double.MaxValue] = 444;

			Assert.AreEqual(5, dict1.Count);
			Assert.AreEqual(222, dict1[4.67]);
			Assert.AreEqual(421, dict1[double.NegativeInfinity]);
			Assert.AreEqual(0, dict1[double.PositiveInfinity]);
			Assert.AreEqual(-17, dict1[double.NaN]);
			Assert.AreEqual(444, dict1[double.MaxValue]);
			InterfaceTests.TestReadonlyCollectionGeneric(dict1.Keys, new double[] { double.NaN, double.NegativeInfinity, 4.67, double.MaxValue, double.PositiveInfinity }, true, "KeysCollection");
			InterfaceTests.TestReadonlyCollectionGeneric(dict1.Values, new int[] { -17, 421, 222, 444, 0 }, true, "ValuesCollection");
		}

        [Test]
        public void IndexerGet()
        {
            OrderedDictionary<string,int> dict1 = new OrderedDictionary<string,int>(StringComparer.InvariantCultureIgnoreCase);

            dict1["foo"] = 12;
            dict1[null] = 18;
            dict1["BAR"] = 11;

            Assert.AreEqual(12, dict1["Foo"]);
            Assert.AreEqual(18, dict1[null]);
            Assert.AreEqual(11, dict1["bar"]);

            try {
                int i = dict1["foobar"];
                Assert.Fail("should throw");
            }
            catch (Exception e) {
                Assert.IsTrue(e is KeyNotFoundException);
            }
        }

		/// <summary>
		/// Test removing items from the tree.
		///</summary>
		[Test]
		public void Remove()
		{
			OrderedDictionary<double,int> dict1 = new OrderedDictionary<double,int>();
			bool b;

			dict1[4.67] =  12;
			dict1[double.NaN] =  -17;
			dict1[double.PositiveInfinity] =  0;
			dict1[4.67] =  187;
			dict1[double.NegativeInfinity] =  188921;
			dict1[double.NegativeInfinity] =  421;