abstracttree.cs

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

namespace Opus6
{
    using System;
    using System.Collections;

    [Copyright("Copyright (c) 2001 by Bruno R. Preiss, P.Eng."), Version("$Id: AbstractTree.cs,v 1.6 2001/10/28 19:50:09 brpreiss Exp $")]
    public abstract class AbstractTree : AbstractContainer, Tree, Container, IComparable, IEnumerable
    {
        protected AbstractTree()
        {
        }

        public override void Accept(Visitor visitor)
        {
            this.DepthFirstTraversal(new PreOrder(visitor));
        }

        public virtual void BreadthFirstTraversal(Visitor visitor)
        {
            Opus6.Queue queue1 = new QueueAsLinkedList();
            if (!this.IsEmpty)
            {
                queue1.Enqueue(this);
            }
            while (!queue1.IsEmpty && !visitor.IsDone)
            {
                Tree tree1 = (Tree) queue1.Dequeue();
                visitor.Visit(tree1.Key);
                for (int num1 = 0; num1 < tree1.Degree; num1++)
                {
                    Tree tree2 = tree1.GetSubtree(num1);
                    if (!tree2.IsEmpty)
                    {
                        queue1.Enqueue(tree2);
                    }
                }
            }
        }

        public virtual void DepthFirstTraversal(PrePostVisitor visitor)
        {
            if (!visitor.IsDone && !this.IsEmpty)
            {
                visitor.PreVisit(this.Key);
                for (int num1 = 0; num1 < this.Degree; num1++)
                {
                    this.GetSubtree(num1).DepthFirstTraversal(visitor);
                }
                visitor.PostVisit(this.Key);
            }
        }

        public override IEnumerator GetEnumerator()
        {
            return new Opus6.AbstractTree.Enumerator(this);
        }

        public abstract Tree GetSubtree(int i);
        public static void TestTree(Tree tree)
        {
            Opus6.AbstractTree.PrintingVisitor visitor1 = new Opus6.AbstractTree.PrintingVisitor();
            Opus6.Console.WriteLine(tree);
            Opus6.Console.WriteLine("Breadth-First traversal");
            tree.BreadthFirstTraversal(visitor1);
            visitor1.Finish();
            Opus6.Console.WriteLine("Preorder traversal");
            tree.DepthFirstTraversal(new PreOrder(visitor1));
            visitor1.Finish();
            Opus6.Console.WriteLine("Inorder traversal");
            tree.DepthFirstTraversal(new InOrder(visitor1));
            visitor1.Finish();
            Opus6.Console.WriteLine("Postorder traversal");
            tree.DepthFirstTraversal(new PostOrder(visitor1));
            visitor1.Finish();
            Opus6.Console.WriteLine("Using Enumeration");
            foreach (object obj1 in tree)
            {
                Opus6.Console.WriteLine(obj1);
            }
        }


        public override int Count
        {
            get
            {
                if (this.IsEmpty)
                {
                    return 0;
                }
                int num1 = 1;
                for (int num2 = 0; num2 < this.Degree; num2++)
                {
                    num1 += this.GetSubtree(num2).Count;
                }
                return num1;
            }
        }

        public abstract int Degree { get; }

        public virtual int Height
        {
            get
            {
                if (this.IsEmpty)
                {
                    return -1;
                }
                int num1 = -1;
                for (int num2 = 0; num2 < this.Degree; num2++)
                {
                    num1 = Math.Max(num1, this.GetSubtree(num2).Height);
                }
                return (num1 + 1);
            }
        }

        public abstract bool IsLeaf { get; }

        public abstract object Key { get; }



        protected class Enumerator : IEnumerator
        {
            public Enumerator(Tree tree)
            {
                this.tree = tree;
                this.stack = new StackAsLinkedList();
            }

            public bool MoveNext()
            {
                if (this.stack.IsEmpty)
                {
                    if (!this.tree.IsEmpty)
                    {
                        this.stack.Push(this.tree);
                    }
                }
                else
                {
                    Tree tree1 = (Tree) this.stack.Pop();
                    for (int num1 = tree1.Degree - 1; num1 >= 0; num1--)
                    {
                        Tree tree2 = tree1.GetSubtree(num1);
                        if (!tree2.IsEmpty)
                        {
                            this.stack.Push(tree2);
                        }
                    }
                }
                return !this.stack.IsEmpty;
            }

            public void Reset()
            {
                this.stack.Purge();
            }


            public object Current
            {
                get
                {
                    if (this.stack.IsEmpty)
                    {
                        throw new InvalidOperationException();
                    }
                    return ((Tree) this.stack.Top).Key;
                }
            }


            private Opus6.Stack stack;
            private Tree tree;
        }

        protected class PrintingVisitor : AbstractVisitor
        {
            public PrintingVisitor()
            {
                this.comma = false;
            }

            public void Finish()
            {
                Opus6.Console.WriteLine();
                this.comma = false;
            }

            public override void Visit(object obj)
            {
                if (this.comma)
                {
                    Opus6.Console.Write(", ");
                }
                Opus6.Console.Write(obj);
                this.comma = true;
            }


            private bool comma;
        }
    }
}