btree.cs

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

namespace Opus6
{
    using System;

    [Copyright("Copyright (c) 2001 by Bruno R. Preiss, P.Eng."), Version("$Id: BTree.cs,v 1.4 2001/10/28 19:50:09 brpreiss Exp $")]
    public class BTree : MWayTree
    {
        public BTree(int m) : base(m)
        {
        }

        protected void AttachLeftHalfOf(BTree btree)
        {
            base.count = ((this.M + 1) / 2) - 1;
            this.AttachSubtree(0, btree.subtree[0]);
            for (int num1 = 1; num1 <= base.count; num1++)
            {
                base.key[num1] = btree.key[num1];
                this.AttachSubtree(num1, btree.subtree[num1]);
            }
        }

        protected void AttachRightHalfOf(BTree btree)
        {
            base.count = (this.M - ((this.M + 1) / 2)) - 1;
            int num1 = (this.M + 1) / 2;
            this.AttachSubtree(0, btree.subtree[num1++]);
            int num2 = 1;
            while (num2 <= base.count)
            {
                base.key[num2] = btree.key[num1];
                this.AttachSubtree(num2, btree.subtree[num1]);
                num2++;
                num1++;
            }
        }

        public virtual void AttachSubtree(int i, MWayTree arg)
        {
            BTree tree1 = (BTree) arg;
            base.subtree[i] = tree1;
            tree1.parent = this;
        }

        public override void Insert(ComparableObject obj)
        {
            if (this.IsEmpty)
            {
                if (this.parent == null)
                {
                    this.AttachSubtree(0, new BTree(this.M));
                    base.key[1] = obj;
                    this.AttachSubtree(1, new BTree(this.M));
                    base.count = 1;
                }
                else
                {
                    this.parent.InsertPair(obj, new BTree(this.M));
                }
            }
            else
            {
                int num1 = base.FindIndex(obj);
                if ((num1 != 0) && (obj == base.key[num1]))
                {
                    throw new ArgumentException("duplicate key");
                }
                base.subtree[num1].Insert(obj);
            }
        }

        protected virtual ComparableObject InsertKey(int index, ComparableObject obj)
        {
            if (index == this.M)
            {
                return obj;
            }
            ComparableObject obj1 = base.key[this.M - 1];
            for (int num1 = this.M - 1; num1 > index; num1--)
            {
                base.key[num1] = base.key[num1 - 1];
            }
            base.key[index] = obj;
            return obj1;
        }

        protected virtual void InsertPair(ComparableObject obj, BTree child)
        {
            int num1 = base.FindIndex(obj);
            if (!this.IsFull)
            {
                this.InsertKey(num1 + 1, obj);
                this.InsertSubtree(num1 + 1, child);
                base.count++;
            }
            else
            {
                ComparableObject obj1 = this.InsertKey(num1 + 1, obj);
                BTree tree1 = this.InsertSubtree(num1 + 1, child);
                if (this.parent == null)
                {
                    BTree tree2 = new BTree(this.M);
                    BTree tree3 = new BTree(this.M);
                    tree2.AttachLeftHalfOf(this);
                    tree3.AttachRightHalfOf(this);
                    tree3.InsertPair(obj1, tree1);
                    this.AttachSubtree(0, tree2);
                    base.key[1] = base.key[(this.M + 1) / 2];
                    this.AttachSubtree(1, tree3);
                    base.count = 1;
                }
                else
                {
                    base.count = ((this.M + 1) / 2) - 1;
                    BTree tree4 = new BTree(this.M);
                    tree4.AttachRightHalfOf(this);
                    tree4.InsertPair(obj1, tree1);
                    this.parent.InsertPair(base.key[(this.M + 1) / 2], tree4);
                }
            }
        }

        protected BTree InsertSubtree(int index, BTree child)
        {
            if (index == this.M)
            {
                return child;
            }
            BTree tree1 = (BTree) base.subtree[this.M - 1];
            for (int num1 = this.M - 1; num1 > index; num1--)
            {
                base.subtree[num1] = base.subtree[num1 - 1];
            }
            base.subtree[index] = child;
            child.parent = this;
            return tree1;
        }

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

        public override void Withdraw(ComparableObject obj)
        {
            throw new MethodNotImplementedException();
        }


        protected BTree parent;
    }
}