sortedlistasarray.cs

来自「Data Structures and Algorithms with Obj」· CS 代码 · 共 134 行

namespace Opus6
{
    using System;
    using System.Collections;

    [Copyright("Copyright (c) 2001 by Bruno R. Preiss, P.Eng."), Version("$Id: SortedListAsArray.cs,v 1.5 2001/10/28 19:50:09 brpreiss Exp $")]
    public class SortedListAsArray : OrderedListAsArray, Opus6.SortedList, SearchableContainer, Container, IComparable, IEnumerable
    {
        public SortedListAsArray(int size) : base(size)
        {
        }

        public override ComparableObject Find(ComparableObject obj)
        {
            int num1 = this.FindOffset(obj);
            if (num1 >= 0)
            {
                return base.array[num1];
            }
            return null;
        }

        protected int FindOffset(ComparableObject obj)
        {
            int num1 = 0;
            int num2 = base.count - 1;
            while (num1 <= num2)
            {
                int num3 = (num1 + num2) / 2;
                if (obj > base.array[num3])
                {
                    num1 = num3 + 1;
                }
                else
                {
                    if (obj < base.array[num3])
                    {
                        num2 = num3 - 1;
                        continue;
                    }
                    return num3;
                }
            }
            return -1;
        }

        public override Cursor FindPosition(ComparableObject obj)
        {
            return new Opus6.SortedListAsArray.MyCursor(this, this.FindOffset(obj));
        }

        public override void Insert(ComparableObject obj)
        {
            if (base.count == base.array.Length)
            {
                throw new ContainerFullException();
            }
            int num1 = base.count;
            while ((num1 > 0) && (base.array[num1 - 1] > obj))
            {
                base.array[num1] = base.array[num1 - 1];
                num1--;
            }
            base.array[num1] = obj;
            base.count++;
        }

        public static void Main()
        {
            Opus6.Console.WriteLine("SortedListAsArray Test");
            Opus6.SortedList list1 = new SortedListAsArray(10);
            SortedListAsArray.TestSortedList(list1);
        }

        internal static void TestSortedList(Opus6.SortedList list)
        {
            list.Insert((ComparableObject) 4);
            list.Insert((ComparableObject) 3);
            list.Insert((ComparableObject) 2);
            list.Insert((ComparableObject) 1);
            Opus6.Console.WriteLine(list);
            ComparableObject obj1 = list.Find((ComparableObject) 2);
            list.Withdraw(obj1);
            Opus6.Console.WriteLine(list);
            foreach (ComparableObject obj2 in list)
            {
                Opus6.Console.WriteLine(obj2);
            }
        }

        public override void Withdraw(ComparableObject obj)
        {
            if (base.count == 0)
            {
                throw new ContainerEmptyException();
            }
            int num1 = this.FindOffset(obj);
            if (num1 < 0)
            {
                throw new ArgumentException("object not found");
            }
            int num2 = num1;
            while (num2 < (base.count - 1))
            {
                base.array[num2] = base.array[num2 + 1];
                num2++;
            }
            base.array[num2] = null;
            base.count--;
        }



        private class MyCursor : OrderedListAsArray.MyCursor
        {
            internal MyCursor(SortedListAsArray list, int index) : base(list, index)
            {
            }

            public override void InsertAfter(ComparableObject obj)
            {
                throw new InvalidOperationException();
            }

            public override void InsertBefore(ComparableObject obj)
            {
                throw new InvalidOperationException();
            }

        }
    }
}