deap.cs

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

namespace Opus6
{
    using System;
    using System.Collections;

    [Version("$Id: Deap.cs,v 1.5 2001/10/28 19:50:09 brpreiss Exp $"), Copyright("Copyright (c) 2001 by Bruno R. Preiss, P.Eng.")]
    public class Deap : AbstractContainer, DoubleEndedPriorityQueue, PriorityQueue, Container, IComparable, IEnumerable
    {
        public Deap(int length)
        {
            this.array = new ComparableObject[length + 2];
        }

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

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

        public ComparableObject DequeueMax()
        {
            if (base.count == 0)
            {
                throw new ContainerEmptyException();
            }
            if (base.count == 1)
            {
                base.count--;
                return this.array[2];
            }
            if (base.count == 2)
            {
                base.count--;
                return this.array[3];
            }
            ComparableObject obj1 = this.array[3];
            ComparableObject obj2 = this.array[base.count + 1];
            base.count--;
            int num1 = 3;
            while ((2 * num1) < (base.count + 2))
            {
                int num2 = 2 * num1;
                if (((num2 + 1) < (base.count + 2)) && (this.array[num2 + 1] > this.array[num2]))
                {
                    num2++;
                }
                this.array[num1] = this.array[num2];
                num1 = num2;
            }
            int num3 = this.Dual(num1);
            if (obj2 >= this.array[num3])
            {
                this.InsertMax(num1, obj2);
            }
            else
            {
                this.array[num1] = this.array[num3];
                this.InsertMin(num3, obj2);
            }
            return obj1;
        }

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

        protected virtual int Dual(int i)
        {
            int num1 = Deap.Mask(i);
            int num2 = i ^ num1;
            if ((num2 & num1) != 0)
            {
                if (num2 >= (base.count + 2))
                {
                    num2 /= 2;
                }
                return num2;
            }
            if ((2 * num2) < (base.count + 2))
            {
                num2 *= 2;
                if (((num2 + 1) < (base.count + 2)) && (this.array[num2 + 1] > this.array[num2]))
                {
                    num2++;
                }
            }
            return num2;
        }

        public virtual void Enqueue(ComparableObject obj)
        {
            if (base.count == (this.array.Length - 2))
            {
                throw new ContainerFullException();
            }
            if (++base.count == 1)
            {
                this.array[2] = obj;
            }
            else
            {
                int num1 = base.count + 1;
                int num2 = this.Dual(num1);
                if ((num1 & Deap.Mask(num1)) != 0)
                {
                    if (obj >= this.array[num2])
                    {
                        this.InsertMax(num1, obj);
                    }
                    else
                    {
                        this.array[num1] = this.array[num2];
                        this.InsertMin(num2, obj);
                    }
                }
                else if (obj < this.array[num2])
                {
                    this.InsertMin(num1, obj);
                }
                else
                {
                    this.array[num1] = this.array[num2];
                    this.InsertMax(num2, obj);
                }
            }
        }

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

        protected virtual void InsertMax(int pos, ComparableObject obj)
        {
            int num1 = pos;
            while ((num1 > 3) && (this.array[num1 / 2] < obj))
            {
                this.array[num1] = this.array[num1 / 2];
                num1 /= 2;
            }
            this.array[num1] = obj;
        }

        protected virtual void InsertMin(int pos, ComparableObject obj)
        {
            int num1 = pos;
            while ((num1 > 2) && (this.array[num1 / 2] > obj))
            {
                this.array[num1] = this.array[num1 / 2];
                num1 /= 2;
            }
            this.array[num1] = obj;
        }

        public static int Log2(int i)
        {
            int num1 = 0;
            while ((1 << (num1 & 0x1f)) <= i)
            {
                num1++;
            }
            return (num1 - 1);
        }

        public static void Main()
        {
            DoubleEndedPriorityQueue queue1 = new Deap(0x100);
            Deap.TestDoubleEndedPriorityQueue(queue1);
        }

        public static int Mask(int i)
        {
            return (1 << ((Deap.Log2(i) - 1) & 0x1f));
        }

        public override void Purge()
        {
            this.array = new ComparableObject[this.array.Length];
            base.count = 0;
        }

        public static void TestDoubleEndedPriorityQueue(DoubleEndedPriorityQueue pqueue)
        {
            BinaryHeap.TestPriorityQueue(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.DequeueMax();
                Opus6.Console.WriteLine(obj1);
            }
        }


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

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

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


        protected ComparableObject[] array;


        private class Enumerator : IEnumerator
        {
            internal Enumerator(Deap deap)
            {
                this.position = 1;
                this.deap = deap;
            }

            public bool MoveNext()
            {
                this.position++;
                if (this.position == (this.deap.Count - 2))
                {
                    this.position = 1;
                }
                return (this.position > 1);
            }

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


            public object Current
            {
                get
                {
                    if (this.position < 2)
                    {
                        throw new InvalidOperationException();
                    }
                    return this.deap.array[this.position];
                }
            }


            private Deap deap;
            protected int position;
        }
    }
}