mwaytree.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: MWayTree.cs,v 1.5 2001/10/28 19:50:09 brpreiss Exp $")]
    public class MWayTree : AbstractTree, SearchTree, Tree, SearchableContainer, Container, IComparable, IEnumerable
    {
        public MWayTree(int m)
        {
            if (m < 2)
            {
                throw new ArgumentException("invalid degree");
            }
            this.key = new ComparableObject[m];
            this.subtree = new MWayTree[m];
        }

        public override void BreadthFirstTraversal(Visitor visitor)
        {
            Opus6.Queue queue1 = new QueueAsLinkedList();
            if (!this.IsEmpty)
            {
                queue1.Enqueue(this);
            }
            while (!queue1.IsEmpty)
            {
                MWayTree tree1 = (MWayTree) queue1.Dequeue();
                for (int num1 = 1; num1 <= (tree1.Degree - 1); num1++)
                {
                    visitor.Visit(tree1.GetKey(num1));
                }
                for (int num2 = 0; num2 <= (tree1.Degree - 1); num2++)
                {
                    MWayTree tree2 = (MWayTree) tree1.GetSubtree(num2);
                    if (!tree2.IsEmpty)
                    {
                        queue1.Enqueue(tree2);
                    }
                }
            }
        }

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

        public override void DepthFirstTraversal(PrePostVisitor visitor)
        {
            if (!this.IsEmpty)
            {
                for (int num1 = 0; num1 <= (base.count + 1); num1++)
                {
                    if (num1 >= 2)
                    {
                        visitor.PostVisit(this.key[num1 - 1]);
                    }
                    if ((num1 >= 1) && (num1 <= base.count))
                    {
                        visitor.InVisit(this.key[num1]);
                    }
                    if (num1 <= (base.count - 1))
                    {
                        visitor.PreVisit(this.key[num1 + 1]);
                    }
                    if (num1 <= base.count)
                    {
                        this.subtree[num1].DepthFirstTraversal(visitor);
                    }
                }
            }
        }

        public virtual ComparableObject Find(ComparableObject obj)
        {
            if (this.IsEmpty)
            {
                return null;
            }
            int num1 = base.count;
            while (num1 > 0)
            {
                int num2 = obj.CompareTo(this.key[num1]);
                if (num2 == 0)
                {
                    return this.key[num1];
                }
                if (num2 > 0)
                {
                    break;
                }
                num1--;
            }
            return this.subtree[num1].Find(obj);
        }

        protected int FindIndex(ComparableObject obj)
        {
            if (this.IsEmpty || (obj < this.key[1]))
            {
                return 0;
            }
            int num1 = 1;
            int num2 = base.count;
            while (num1 < num2)
            {
                int num3 = ((num1 + num2) + 1) / 2;
                if (obj < this.key[num3])
                {
                    num2 = num3 - 1;
                }
                else
                {
                    num1 = num3;
                }
            }
            return num1;
        }

        public ComparableObject FindV2(ComparableObject obj)
        {
            if (this.IsEmpty)
            {
                return null;
            }
            int num1 = this.FindIndex(obj);
            if ((num1 != 0) && (obj == this.key[num1]))
            {
                return this.key[num1];
            }
            return this.subtree[num1].FindV2(obj);
        }

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

        public virtual object GetKey(int i)
        {
            if (this.IsEmpty)
            {
                throw new InvalidOperationException();
            }
            Bounds.Check(i, 1, base.count);
            return this.key[i];
        }

        public override Tree GetSubtree(int i)
        {
            if (this.IsEmpty)
            {
                throw new InvalidOperationException();
            }
            Bounds.Check(i, 0, base.count + 1);
            return this.subtree[i];
        }

        public virtual void Insert(ComparableObject obj)
        {
            if (this.IsEmpty)
            {
                this.subtree[0] = new MWayTree(this.M);
                this.key[1] = obj;
                this.subtree[1] = new MWayTree(this.M);
                base.count = 1;
            }
            else
            {
                int num1 = this.FindIndex(obj);
                if ((num1 != 0) && (obj == this.key[num1]))
                {
                    throw new ArgumentException("duplicate key");
                }
                if (!this.IsFull)
                {
                    for (int num2 = base.count; num2 > num1; num2--)
                    {
                        this.key[num2 + 1] = this.key[num2];
                        this.subtree[num2 + 1] = this.subtree[num2];
                    }
                    this.key[num1 + 1] = obj;
                    this.subtree[num1 + 1] = new MWayTree(this.M);
                    base.count++;
                }
                else
                {
                    this.subtree[num1].Insert(obj);
                }
            }
        }

        public virtual bool IsMember(ComparableObject obj)
        {
            if (this.IsEmpty)
            {
                return false;
            }
            int num1 = base.count;
            while (num1 > 0)
            {
                if (obj == this.key[num1])
                {
                    return true;
                }
                if (obj > this.key[num1])
                {
                    break;
                }
                num1--;
            }
            return this.subtree[num1].IsMember(obj);
        }

        public static void Main()
        {
            SearchTree tree1 = new MWayTree(3);
            BinarySearchTree.TestSearchTree(tree1);
        }

        public override void Purge()
        {
            for (int num1 = 1; num1 <= base.count; num1++)
            {
                this.key[num1] = null;
            }
            for (int num2 = 0; num2 <= base.count; num2++)
            {
                this.subtree[num2] = null;
            }
            base.count = 0;
        }

        public virtual void Withdraw(ComparableObject obj)
        {
            if (this.IsEmpty)
            {
                throw new ArgumentException("object not found");
            }
            int num1 = this.FindIndex(obj);
            if ((num1 != 0) && (obj == this.key[num1]))
            {
                if (!this.subtree[num1 - 1].IsEmpty)
                {
                    ComparableObject obj1 = this.subtree[num1 - 1].Max;
                    this.key[num1] = obj1;
                    this.subtree[num1 - 1].Withdraw(obj1);
                }
                else if (!this.subtree[num1].IsEmpty)
                {
                    ComparableObject obj2 = this.subtree[num1].Min;
                    this.key[num1] = obj2;
                    this.subtree[num1].Withdraw(obj2);
                }
                else
                {
                    base.count--;
                    int num2 = num1;
                    while (num2 <= base.count)
                    {
                        this.key[num2] = this.key[num2 + 1];
                        this.subtree[num2] = this.subtree[num2 + 1];
                        num2++;
                    }
                    this.key[num2] = null;
                    this.subtree[num2] = null;
                    if (base.count == 0)
                    {
                        this.subtree[0] = null;
                    }
                }
            }
            else
            {
                this.subtree[num1].Withdraw(obj);
            }
        }


        public override int Count
        {
            get
            {
                if (this.IsEmpty)
                {
                    return 0;
                }
                int num1 = base.count;
                for (int num2 = 0; num2 <= base.count; num2++)
                {
                    num1 += this.subtree[num2].Count;
                }
                return num1;
            }
        }

        public override int Degree
        {
            get
            {
                if (base.count == 0)
                {
                    return 0;
                }
                return (base.count + 1);
            }
        }

        public override bool IsEmpty
        {
            get
            {
                return (base.count == 0);
            }
        }

        public override bool IsFull
        {
            get
            {
                return (base.count == (this.M - 1));
            }
        }

        public override bool IsLeaf
        {
            get
            {
                if (this.IsEmpty)
                {
                    return false;
                }
                for (int num1 = 0; num1 <= base.count; num1++)
                {
                    if (!this.subtree[num1].IsEmpty)
                    {
                        return false;
                    }
                }
                return true;
            }
        }

        public override object Key
        {
            get
            {
                throw new InvalidOperationException();
            }
        }

        public virtual int M
        {
            get
            {
                return this.subtree.Length;
            }
        }

        public virtual ComparableObject Max
        {
            get
            {
                if (this.IsEmpty)
                {
                    return null;
                }
                if (this.subtree[base.count].IsEmpty)
                {
                    return this.key[base.count];
                }
                return this.subtree[base.count].Max;
            }
        }

        public virtual ComparableObject Min
        {
            get
            {
                if (this.IsEmpty)
                {
                    return null;
                }
                if (this.subtree[0].IsEmpty)
                {
                    return this.key[1];
                }
                return this.subtree[0].Min;
            }
        }


        protected ComparableObject[] key;
        protected MWayTree[] subtree;


        private class Enumerator : IEnumerator
        {
            internal Enumerator(MWayTree tree)
            {
                this.stack = new StackAsLinkedList();
                this.tree = tree;
            }

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

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


            public object Current
            {
                get
                {
                    if (this.stack.IsEmpty)
                    {
                        throw new InvalidOperationException();
                    }
                    return ((MWayTree) this.stack.Top).GetKey(this.position);
                }
            }


            protected int position;
            protected Opus6.Stack stack;
            private MWayTree tree;
        }
    }
}