dequetests.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.Generic;
using System.Collections;
using NUnit.Framework;

namespace Wintellect.PowerCollections.Tests
{
    [TestFixture]
    public class DequeTests
    {
        private void CheckListAndDeque<T>(List<T> list, Deque<T> deque)
        {
            Assert.AreEqual(list.Count, deque.Count);

            for (int i = 0; i < list.Count; ++i) {
                Assert.AreEqual(list[i], deque[i]);
            }
        }

        [Test]
        public void RandomInsertDelete()
        {
            const int ITER = 2000, LOOP = 15;
            Random rand = new Random(13);

            for (int loop = 0; loop < LOOP; ++loop) {
                Deque<int> deque = new Deque<int>();
                List<int> list = new List<int>();
                for (int iter = 0; iter < ITER; ++iter) {
                    //Console.Write("Loop {0}, Iteration {1}: ", loop, iter);
                    if (rand.Next(100) < 45) {
                        // remove an item.
                        if (list.Count > 0) {
                            int index = rand.Next(list.Count);
                            //Console.WriteLine("RemoveAt({0})", index);
                            list.RemoveAt(index);
                            deque.RemoveAt(index);
                        }
                    }
                    else {
                        // Add an item.
                        int item = rand.Next(1, 1000);
                        int index = rand.Next(list.Count + 1);
                        //Console.WriteLine("Insert({0}, {1})", index, item);
                        list.Insert(index, item);
                        deque.Insert(index, item);
                    }

                    //deque.Print();
                    CheckListAndDeque(list, deque);
                }

                InterfaceTests.TestReadWriteList<int>(deque, list.ToArray());
            }
        }

        [Test]
        public void RandomInsertDeleteRange()
        {
            const int ITER = 2000, LOOP = 15;
            Random rand = new Random(13);

            for (int loop = 0; loop < LOOP; ++loop) {
                Deque<int> deque = new Deque<int>();
                List<int> list = new List<int>();
                for (int iter = 0; iter < ITER; ++iter) {
                   //Console.Write("Loop {0}, Iteration {1}: ", loop, iter);
                    if (rand.Next(100) < 45) {
                        // remove a range.
                        if (list.Count > 0) {
                            int index = rand.Next(list.Count);
                            int count = rand.Next(list.Count - index);
                            //Console.WriteLine("RemoveAt({0}, {1})", index, count);
                            list.RemoveRange(index, count);
                            deque.RemoveRange(index, count);
                        }
                    }
                    else {
                        // Add an range.
                        int index = rand.Next(list.Count + 1);
                        int count = rand.Next(10);
                        int[] items = new int[count];
                        for (int i = 0; i < count; ++i)
                            items[i] = rand.Next(1000);

                        /*Console.Write("Insert({0}, {{", index);
                        for (int i = 0; i < count; ++i) {
                            if (i > 0)
                                Console.Write(", ");
                            Console.Write(items[i]);
                        }
                        Console.WriteLine("})"); */

                        IEnumerable<int> e = (rand.Next(2) == 0) ? AlgorithmsTests.EnumerableFromArray(items) : items;
                        list.InsertRange(index, e);
                        deque.InsertRange(index, e);
                    }

                    //deque.Print();
                    CheckListAndDeque(list, deque);
                }

                InterfaceTests.TestReadWriteList<int>(deque, list.ToArray());
            }
        }

        [Test]
        public void RandomAddRemoveFrontBack()
        {
            const int ITER = 2000, LOOP = 15;
            Random rand = new Random(13);

            for (int loop = 0; loop < LOOP; ++loop) {
                Deque<int> deque = new Deque<int>();
                List<int> list = new List<int>();
                for (int iter = 0; iter < ITER; ++iter) {
                    //Console.Write("Loop {0}, Iteration {1}: ", loop, iter);
                    if (rand.Next(100) < 45 && list.Count > 0) {
                        int r = rand.Next(10);
                        if (r < 4) {
                            //Console.WriteLine("RemoveFront()");
                            int removedList = list[0];
                            list.RemoveAt(0);
                            int removedDeque = deque.RemoveFromFront();
                            Assert.AreEqual(removedList, removedDeque);
                        }
                        else if (r < 8) {
                            //Console.WriteLine("RemoveBack()");
                            int removedList = list[list.Count - 1];
                            list.RemoveAt(list.Count - 1);
                            int removedDeque = deque.RemoveFromBack();
                            Assert.AreEqual(removedList, removedDeque);
                        }
                        else {
                            int index = rand.Next(list.Count);
                            //Console.WriteLine("RemoveAt({0})", index);
                            list.RemoveAt(index);
                            deque.RemoveAt(index);
                        }
                    }
                    else {
                        int r = rand.Next(10);
                        int item = rand.Next(1, 1000);
                        if (r < 4) {
                            //Console.WriteLine("AddFront({0})", item);
                            list.Insert(0, item);
                            deque.AddToFront(item);
                        }
                        else if (r < 8) {
                            //Console.WriteLine("AddBack({0})", item);
                            list.Add(item);
                            deque.AddToBack(item);
                        }
                        else {
                            // Add an item.
                            int index = rand.Next(list.Count + 1);
                            //Console.WriteLine("Insert({0}, {1})", index, item);
                            list.Insert(index, item);
                            deque.Insert(index, item);
                        }
                    }

                    //deque.Print();
                    CheckListAndDeque(list, deque);
                }

                InterfaceTests.TestReadWriteList<int>(deque, list.ToArray());
            }
        }

        [Test]
        public void GenericIListInterface()
        {
            Deque<string> d = new Deque<string>();

            d.AddToFront("foo");
            d.AddToBack("world");
            d.AddToFront("hello");
            d.AddToBack("elvis");
            d.AddToFront("elvis");
            d.AddToBack(null);
            d.AddToFront("cool");

            InterfaceTests.TestReadWriteListGeneric<string>((IList<string>)d, new string[] { "cool", "elvis", "hello", "foo", "world", "elvis", null });
        }

        [Test]
        public void IListInterface()
        {
            Deque<string> d = new Deque<string>();

            d.AddToFront("foo");
            d.AddToBack("world");
            d.AddToFront("hello");
            d.AddToBack("elvis");
            d.AddToFront("elvis");
            d.AddToBack(null);
            d.AddToFront("cool");

            InterfaceTests.TestReadWriteList<string>((IList)d, new string[] { "cool", "elvis", "hello", "foo", "world", "elvis", null });
        }

        [Test]
        public void Insert()
        {
            Deque<string> d = new Deque<string>();

            d.Insert(0, "a");
            d.Insert(1, "b");
            d.Insert(0, "c");
            d.Insert(2, "d");
            d.Insert(1, "e");
            d.Insert(4, "f");
            d.Insert(3, "g");
            d.Insert(2, "h");
            d.Insert(0, "i");
            d.Insert(2, "j");
            d.Insert(4, "k");
            d.Insert(3, "l");
            d.Insert(4, "m");
            d.Insert(2, "n");
            InterfaceTests.TestEnumerableElements(d, new string[] { "i", "c", "n", "j", "l", "m", "e", "k", "h", "a", "g", "d", "f", "b" });
            d.RemoveFromBack();
            d.RemoveFromBack();
            d.RemoveFromBack();
            d.RemoveFromBack();
            d.RemoveFromBack();
            d.Insert(4, "o");
            d.Insert(10, "p");
            InterfaceTests.TestEnumerableElements(d, new string[] { "i", "c", "n", "j", "o", "l", "m", "e", "k", "h", "p" });
            InterfaceTests.TestReadWriteListGeneric(d, new string[] { "i", "c", "n", "j", "o", "l", "m", "e", "k", "h", "p" });
        }

        [Test]
        public void InsertExceptions()
        {
            Deque<string> d = new Deque<string>();

            d.AddToFront("foo");
            d.AddToBack("world");
            d.AddToFront("hello");
            d.AddToBack("elvis");
            d.AddToFront("elvis");
            d.AddToBack(null);
            d.AddToFront("cool");

            try {
                d.Insert(-1, "hi");
                Assert.Fail("should throw");
            }
            catch (Exception e) {
                Assert.IsTrue(e is ArgumentOutOfRangeException);
            }

            try {
                d.Insert(8, "hi");
                Assert.Fail("should throw");
            }
            catch (Exception e) {
                Assert.IsTrue(e is ArgumentOutOfRangeException);
            }

            try {
                d.Insert(int.MinValue, "hi");
                Assert.Fail("should throw");
            }
            catch (Exception e) {
                Assert.IsTrue(e is ArgumentOutOfRangeException);
            }

            try {
                d.Insert(int.MaxValue, "hi");
                Assert.Fail("should throw");
            }
            catch (Exception e) {
                Assert.IsTrue(e is ArgumentOutOfRangeException);
            }
        }

        [Test]
        public void RemoveAt()
        {
            Deque<string> d = new Deque<string>();

            d.Insert(0, "a");
            d.Insert(1, "b");
            d.Insert(0, "c");
            d.Insert(2, "d");
            d.Insert(1, "e");
            d.Insert(4, "f");
            d.Insert(3, "g");
            d.Insert(2, "h");
            d.Insert(0, "i");
            d.Insert(2, "j");
            d.Insert(4, "k");
            d.RemoveAt(4);
            d.RemoveAt(3);
            d.RemoveAt(2);
            d.RemoveAt(5);
            d.RemoveAt(2);
            InterfaceTests.TestReadWriteListGeneric(d, new string[] { "i", "c", "a", "g", "f", "b" });

            d.Clear();
            d.AddToBack("f");
            d.AddToBack("g");
            d.AddToFront("e");
            d.AddToFront("d");
            d.AddToFront("c");
            d.AddToFront("b");
            d.AddToFront("a");
            d.RemoveAt(3);
            d.RemoveAt(4);
            d.RemoveAt(4);
            InterfaceTests.TestReadWriteListGeneric(d, new string[] {"a", "b", "c", "e" });
        }

        [Test]
        public void RemoveAtExceptions()
        {
            Deque<string> d = new Deque<string>();

            d.AddToFront("foo");
            d.AddToBack("world");
            d.AddToFront("hello");
            d.AddToBack("elvis");
            d.AddToFront("elvis");
            d.AddToBack(null);
            d.AddToFront("cool");

            try {
                d.RemoveAt(-1);
                Assert.Fail("should throw");
            }
            catch (Exception e) {
                Assert.IsTrue(e is ArgumentOutOfRangeException);
            }

            try {
                d.RemoveAt(7);
                Assert.Fail("should throw");
            }
            catch (Exception e) {
                Assert.IsTrue(e is ArgumentOutOfRangeException);
            }

            try {
                d.RemoveAt(int.MinValue);
                Assert.Fail("should throw");
            }
            catch (Exception e) {
                Assert.IsTrue(e is ArgumentOutOfRangeException);
            }

            try {
                d.RemoveAt(int.MaxValue);
                Assert.Fail("should throw");
            }
            catch (Exception e) {
                Assert.IsTrue(e is ArgumentOutOfRangeException);
            }
        }

        [Test]
        public void Indexer()
        {
            Deque<string> d = new Deque<string>();

            d.AddToFront("c");
            d.AddToFront("b");
            d.AddToFront("a");
            d.AddToBack("d");
            d.AddToBack("e");
            d.AddToBack("f");
            Assert.AreEqual("b", d[1]);
            Assert.AreEqual("e", d[4]);
            d[1] = "q";
            d[4] = "r";
            Assert.AreEqual("q", d[1]);
            Assert.AreEqual("r", d[4]);
            InterfaceTests.TestReadWriteListGeneric(d, new string[] { "a", "q", "c", "d", "r", "f" });
            d.Clear();

            d.AddToBack("a");
            d.AddToBack("b");
            d.AddToBack("c");
            d.AddToBack("d");
            Assert.AreEqual("b", d[1]);
            Assert.AreEqual("d", d[3]);
            d[1] = "q";
            d[3] = "r";
            Assert.AreEqual("q", d[1]);
            Assert.AreEqual("r", d[3]);
            InterfaceTests.TestReadWriteListGeneric(d, new string[] { "a", "q", "c", "r" });
        }