binomialqueue.cs

Data Structures and Algorithms with Object-Oriented Design Patterns in C# 这本书的范例代码dll自己反编译的source

namespace Opus6
{
    using System;
    using System.Collections;
    using System.Text;

    [Copyright("Copyright (c) 2001 by Bruno R. Preiss, P.Eng."), Version("$Id: BinomialQueue.cs,v 1.6 2001/11/04 20:49:34 brpreiss Exp $")]
    public class BinomialQueue : AbstractContainer, MergeablePriorityQueue, PriorityQueue, Container, IComparable, IEnumerable
    {
        public BinomialQueue()
        {
            this.treeList = new LinkedList();
        }

        public override void Accept(Visitor visitor)
        {
            for (LinkedList.Element element1 = this.treeList.Head; element1 != null; element1 = element1.Next)
            {
                ((BinomialTree) element1.Datum).DepthFirstTraversal(new PreOrder(visitor));
            }
        }

        protected virtual void AddTree(BinomialTree tree)
        {
            this.treeList.Append(tree);
            base.count += tree.Count;
        }

        protected BinomialTree Carry(BinomialTree a, BinomialTree b, BinomialTree c)
        {
            if (((a != null) && (b != null)) && (c == null))
            {
                return a.Add(b);
            }
            if (((a != null) && (b == null)) && (c != null))
            {
                return a.Add(c);
            }
            if (((a == null) && (b != null)) && (c != null))
            {
                return b.Add(c);
            }
            if (((a != null) && (b != null)) && (c != null))
            {
                return a.Add(b);
            }
            return null;
        }

        public override int CompareTo(object arg)
        {
            throw new MethodNotImplementedException();
        }

        public virtual ComparableObject DequeueMin()
        {
            if (base.count == 0)
            {
                throw new ContainerEmptyException();
            }
            BinomialTree tree1 = this.MinTree;
            this.removeTree(tree1);
            BinomialQueue queue1 = new BinomialQueue();
            while (tree1.Degree > 0)
            {
                BinomialTree tree2 = (BinomialTree) tree1.GetSubtree(0);
                tree1.DetachSubtree(tree2);
                queue1.AddTree(tree2);
            }
            this.Merge(queue1);
            return tree1.Key;
        }

        public virtual void Enqueue(ComparableObject obj)
        {
            BinomialQueue queue1 = new BinomialQueue();
            queue1.AddTree(new BinomialTree(obj));
            this.Merge(queue1);
        }

        public override IEnumerator GetEnumerator()
        {
            throw new MethodNotImplementedException();
        }

        public static void Main()
        {
            PriorityQueue queue1 = new BinomialQueue();
            BinaryHeap.TestPriorityQueue(queue1);
        }

        public virtual void Merge(MergeablePriorityQueue queue)
        {
            BinomialQueue queue1 = (BinomialQueue) queue;
            LinkedList list1 = this.treeList;
            this.treeList = new LinkedList();
            base.count = 0;
            LinkedList.Element element1 = list1.Head;
            LinkedList.Element element2 = queue1.treeList.Head;
            BinomialTree tree1 = null;
            for (int num1 = 0; ((element1 != null) || (element2 != null)) || (tree1 != null); num1++)
            {
                BinomialTree tree2 = null;
                if (element1 != null)
                {
                    BinomialTree tree3 = (BinomialTree) element1.Datum;
                    if (tree3.Degree == num1)
                    {
                        tree2 = tree3;
                        element1 = element1.Next;
                    }
                }
                BinomialTree tree4 = null;
                if (element2 != null)
                {
                    BinomialTree tree5 = (BinomialTree) element2.Datum;
                    if (tree5.Degree == num1)
                    {
                        tree4 = tree5;
                        element2 = element2.Next;
                    }
                }
                BinomialTree tree6 = this.Sum(tree2, tree4, tree1);
                if (tree6 != null)
                {
                    this.AddTree(tree6);
                }
                tree1 = this.Carry(tree2, tree4, tree1);
            }
            queue1.Purge();
        }

        public override void Purge()
        {
            this.treeList = new LinkedList();
            base.count = 0;
        }

        protected virtual void removeTree(BinomialTree tree)
        {
            this.treeList.Extract(tree);
            base.count -= tree.Count;
        }

        protected virtual BinomialTree Sum(BinomialTree a, BinomialTree b, BinomialTree c)
        {
            if (((a != null) && (b == null)) && (c == null))
            {
                return a;
            }
            if (((a == null) && (b != null)) && (c == null))
            {
                return b;
            }
            if (((a == null) && (b == null)) && (c != null))
            {
                return c;
            }
            if (((a != null) && (b != null)) && (c != null))
            {
                return c;
            }
            return null;
        }

        public override string ToString()
        {
            StringBuilder builder1 = new StringBuilder();
            builder1.Append(base.GetType().FullName + "{\r\n");
            for (LinkedList.Element element1 = this.treeList.Head; element1 != null; element1 = element1.Next)
            {
                builder1.Append(element1.Datum + "\r\n");
            }
            builder1.Append("}");
            return builder1.ToString();
        }


        public virtual ComparableObject Min
        {
            get
            {
                if (base.count == 0)
                {
                    throw new ContainerEmptyException();
                }
                return this.MinTree.Key;
            }
        }

        protected virtual BinomialTree MinTree
        {
            get
            {
                BinomialTree tree1 = null;
                for (LinkedList.Element element1 = this.treeList.Head; element1 != null; element1 = element1.Next)
                {
                    BinomialTree tree2 = (BinomialTree) element1.Datum;
                    if ((tree1 == null) || (tree2.Key < tree1.Key))
                    {
                        tree1 = tree2;
                    }
                }
                return tree1;
            }
        }


        protected LinkedList treeList;


        protected class BinomialTree : GeneralTree
        {
            public BinomialTree(object key) : base(key)
            {
            }

            internal virtual BinomialQueue.BinomialTree Add(BinomialQueue.BinomialTree tree)
            {
                if (base.degree != tree.degree)
                {
                    throw new ArgumentException("incompatible degrees");
                }
                if (this.Key > tree.Key)
                {
                    this.SwapContentsWith(tree);
                }
                base.AttachSubtree(tree);
                return this;
            }

            internal virtual void SwapContentsWith(BinomialQueue.BinomialTree tree)
            {
                object obj1 = base.key;
                base.key = tree.key;
                tree.key = obj1;
                LinkedList list1 = base.list;
                base.list = tree.list;
                tree.list = list1;
                int num1 = base.degree;
                base.degree = tree.degree;
                tree.degree = num1;
            }


            public override int Count
            {
                get
                {
                    return (1 << (base.degree & 0x1f));
                }
            }

            public ComparableObject Key
            {
                get
                {
                    return (ComparableObject) base.Key;
                }
            }

        }
    }
}