namespace Opus6
{
    using System;
    using System.Collections;

    [Copyright("Copyright (c) 2001 by Bruno R. Preiss, P.Eng."), Version("$Id: BinarySearchTree.cs,v 1.4 2001/10/28 19:50:09 brpreiss Exp $")]
    public class BinarySearchTree : BinaryTree, SearchTree, Tree, SearchableContainer, Container, IComparable, IEnumerable
    {
        public override void AttachKey(object obj)
        {
            if (!this.IsEmpty)
            {
                throw new InvalidOperationException();
            }
            base.key = obj;
            base.left = new BinarySearchTree();
            base.right = new BinarySearchTree();
        }

        protected virtual void Balance()
        {
        }

        public virtual ComparableObject Find(ComparableObject obj)
        {
            if (this.IsEmpty)
            {
                return null;
            }
            int num1 = obj.CompareTo(this.Key);
            if (num1 == 0)
            {
                return this.Key;
            }
            if (num1 < 0)
            {
                return this.Left.Find(obj);
            }
            return this.Right.Find(obj);
        }

        public virtual void Insert(ComparableObject obj)
        {
            if (this.IsEmpty)
            {
                this.AttachKey(obj);
            }
            else
            {
                int num1 = obj.CompareTo(this.Key);
                if (num1 == 0)
                {
                    throw new ArgumentException("duplicate key");
                }
                if (num1 < 0)
                {
                    this.Left.Insert(obj);
                }
                else
                {
                    this.Right.Insert(obj);
                }
            }
            this.Balance();
        }

        public virtual bool IsMember(ComparableObject obj)
        {
            if (!this.IsEmpty)
            {
                if (obj == this.Key)
                {
                    return true;
                }
                if (obj < this.Key)
                {
                    return this.Left.IsMember(obj);
                }
                if (obj > this.Key)
                {
                    return this.Right.IsMember(obj);
                }
            }
            return false;
        }

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

        public static void TestSearchTree(SearchTree tree)
        {
            for (int num1 = 1; num1 <= 7; num1++)
            {
                tree.Insert((ComparableObject) num1);
            }
            AbstractTree.PrintingVisitor visitor1 = new 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);
            }
            Opus6.Console.WriteLine("Withdrawing 4");
            ComparableObject obj2 = tree.Find((ComparableObject) 4);
            try
            {
                tree.Withdraw(obj2);
                Opus6.Console.WriteLine(tree);
            }
            catch (MethodNotImplementedException exception1)
            {
                Opus6.Console.WriteLine(exception1);
                return;
            }
        }

        public virtual void Withdraw(ComparableObject obj)
        {
            if (this.IsEmpty)
            {
                throw new ArgumentException("object not found");
            }
            int num1 = obj.CompareTo(this.Key);
            if (num1 == 0)
            {
                if (!this.Left.IsEmpty)
                {
                    ComparableObject obj1 = this.Left.Max;
                    base.key = obj1;
                    this.Left.Withdraw(obj1);
                }
                else if (!this.Right.IsEmpty)
                {
                    ComparableObject obj2 = this.Right.Min;
                    base.key = obj2;
                    this.Right.Withdraw(obj2);
                }
                else
                {
                    this.DetachKey();
                }
            }
            else if (num1 < 0)
            {
                this.Left.Withdraw(obj);
            }
            else
            {
                this.Right.Withdraw(obj);
            }
            this.Balance();
        }


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

        public virtual BinarySearchTree Left
        {
            get
            {
                return (BinarySearchTree) base.Left;
            }
        }

        public virtual ComparableObject Max
        {
            get
            {
                if (this.IsEmpty)
                {
                    return null;
                }
                if (this.Right.IsEmpty)
                {
                    return this.Key;
                }
                return this.Right.Max;
            }
        }

        public virtual ComparableObject Min
        {
            get
            {
                if (this.IsEmpty)
                {
                    return null;
                }
                if (this.Left.IsEmpty)
                {
                    return this.Key;
                }
                return this.Left.Min;
            }
        }

        public BinarySearchTree Right
        {
            get
            {
                return (BinarySearchTree) base.Right;
            }
        }

    }
}