binaryheap.cs

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

namespace Opus6
{
    using System;
    using System.Collections;

    [Version("$Id: BinaryHeap.cs,v 1.4 2001/09/15 20:41:02 brpreiss Exp $"), Copyright("Copyright (c) 2001 by Bruno R. Preiss, P.Eng.")]
    public class BinaryHeap : AbstractContainer, PriorityQueue, Container, IComparable, IEnumerable
    {
        public BinaryHeap(int length)
        {
            this.array = new ComparableObject[length + 1];
        }

        public override void Accept(Visitor visitor)
        {
            for (int num1 = 1; num1 < (base.count + 1); num1++)
            {
                visitor.Visit(this.array[num1]);
                if (visitor.IsDone)
                {
                    return;
                }
            }
        }

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

        public virtual ComparableObject DequeueMin()
        {
            if (base.count == 0)
            {
                throw new ContainerEmptyException();
            }
            ComparableObject obj1 = this.array[1];
            ComparableObject obj2 = this.array[base.count];
            base.count--;
            int num1 = 1;
            while ((2 * num1) < (base.count + 1))
            {
                int num2 = 2 * num1;
                if (((num2 + 1) < (base.count + 1)) && (this.array[num2 + 1] < this.array[num2]))
                {
                    num2++;
                }
                if (obj2 <= this.array[num2])
                {
                    break;
                }
                this.array[num1] = this.array[num2];
                num1 = num2;
            }
            this.array[num1] = obj2;
            return obj1;
        }

        public virtual void Enqueue(ComparableObject obj)
        {
            if (base.count == (this.array.Length - 1))
            {
                throw new ContainerFullException();
            }
            base.count++;
            int num1 = base.count;
            while ((num1 > 1) && (this.array[num1 / 2] > obj))
            {
                this.array[num1] = this.array[num1 / 2];
                num1 /= 2;
            }
            this.array[num1] = obj;
        }

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

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

        public override void Purge()
        {
            while (base.count > 0)
            {
                this.array[base.count--] = null;
            }
        }

        public static void TestPriorityQueue(PriorityQueue pqueue)
        {
            Opus6.Console.WriteLine(pqueue);
            pqueue.Enqueue((ComparableObject) 3);
            pqueue.Enqueue((ComparableObject) 1);
            pqueue.Enqueue((ComparableObject) 4);
            pqueue.Enqueue((ComparableObject) 1);
            pqueue.Enqueue((ComparableObject) 5);
            pqueue.Enqueue((ComparableObject) 9);
            pqueue.Enqueue((ComparableObject) 2);
            pqueue.Enqueue((ComparableObject) 6);
            pqueue.Enqueue((ComparableObject) 5);
            pqueue.Enqueue((ComparableObject) 4);
            Opus6.Console.WriteLine(pqueue);
            while (!pqueue.IsEmpty)
            {
                ComparableObject obj1 = pqueue.DequeueMin();
                Opus6.Console.WriteLine(obj1);
            }
        }


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

        public virtual ComparableObject Min
        {
            get
            {
                if (base.count == 0)
                {
                    throw new ContainerEmptyException();
                }
                return this.array[1];
            }
        }


        protected ComparableObject[] array;


        private class Enumerator : IEnumerator
        {
            internal Enumerator(BinaryHeap heap)
            {
                this.position = 0;
                this.heap = heap;
            }

            public bool MoveNext()
            {
                this.position++;
                if (this.position > this.heap.count)
                {
                    this.position = 0;
                }
                return (this.position > 0);
            }

            public void Reset()
            {
                this.position = 0;
            }


            public object Current
            {
                get
                {
                    if (this.position == 0)
                    {
                        throw new InvalidOperationException();
                    }
                    return this.heap.array[this.position];
                }
            }


            private BinaryHeap heap;
            private int position;
        }
    }
}