leftistheap.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: LeftistHeap.cs,v 1.3 2001/09/11 12:04:04 brpreiss Exp $")]
    public class LeftistHeap : BinaryTree, MergeablePriorityQueue, PriorityQueue, Container, IComparable, IEnumerable
    {
        public LeftistHeap()
        {
            this.nullPathLength = 0;
        }

        public LeftistHeap(ComparableObject key) : base(key, new LeftistHeap(), new LeftistHeap())
        {
            this.nullPathLength = 1;
        }

        public virtual ComparableObject DequeueMin()
        {
            if (this.IsEmpty)
            {
                throw new ContainerEmptyException();
            }
            ComparableObject obj1 = this.Key;
            LeftistHeap heap1 = this.Left;
            LeftistHeap heap2 = this.Right;
            this.Purge();
            this.SwapContentsWith(heap1);
            this.Merge(heap2);
            return obj1;
        }

        public void Enqueue(ComparableObject obj)
        {
            this.Merge(new LeftistHeap(obj));
        }

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

        public virtual void Merge(MergeablePriorityQueue queue)
        {
            LeftistHeap heap1 = (LeftistHeap) queue;
            if (this.IsEmpty)
            {
                this.SwapContentsWith(heap1);
            }
            else if (!heap1.IsEmpty)
            {
                if (this.Key > heap1.Key)
                {
                    this.SwapContentsWith(heap1);
                }
                this.Right.Merge(heap1);
                if (this.Left.nullPathLength < this.Right.nullPathLength)
                {
                    this.SwapSubtrees();
                }
                this.nullPathLength = 1 + Math.Min(this.Left.nullPathLength, this.Right.nullPathLength);
            }
        }

        private void SwapContentsWith(LeftistHeap heap)
        {
            object obj1 = base.key;
            base.key = heap.key;
            heap.key = obj1;
            LeftistHeap heap1 = (LeftistHeap) base.left;
            base.left = heap.left;
            heap.left = heap1;
            LeftistHeap heap2 = (LeftistHeap) base.right;
            base.right = heap.right;
            heap.right = heap2;
            int num1 = this.nullPathLength;
            this.nullPathLength = heap.nullPathLength;
            heap.nullPathLength = num1;
        }

        protected void SwapSubtrees()
        {
            LeftistHeap heap1 = this.Left;
            base.left = base.right;
            base.right = heap1;
        }


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

        public LeftistHeap Left
        {
            get
            {
                return (LeftistHeap) base.Left;
            }
        }

        public virtual ComparableObject Min
        {
            get
            {
                if (this.IsEmpty)
                {
                    throw new ContainerEmptyException();
                }
                return this.Key;
            }
        }

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


        protected int nullPathLength;
    }
}