dotgnu-pnet-commits
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Dotgnu-pnet-commits] CVS: pnetlib/Generics ArrayQueue.cs,NONE,1.1 IQue


From: Rhys Weatherley <address@hidden>
Subject: [Dotgnu-pnet-commits] CVS: pnetlib/Generics ArrayQueue.cs,NONE,1.1 IQueue.cs,NONE,1.1 Queue.cs,1.1,NONE
Date: Sat, 22 Feb 2003 00:15:34 -0500

Update of /cvsroot/dotgnu-pnet/pnetlib/Generics
In directory subversions:/tmp/cvs-serv29565/Generics

Added Files:
        ArrayQueue.cs IQueue.cs 
Removed Files:
        Queue.cs 
Log Message:


Rename Queue<T> to ArrayQueue<T> and add the IQueue<T> interface.


--- NEW FILE ---
/*
 * ArrayQueue.cs - Generic queue class, implemented as an array.
 *
 * Copyright (c) 2003  Southern Storm Software, Pty Ltd
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
 */

namespace Generics
{

using System;

public class ArrayQueue<T> : IQueue<T>
{
        // Internal state.
        private T[]   items;
        private int   add, remove, size;
        private float growFactor;
        private int   generation;

        // The default capacity for queues.
        private const int DefaultCapacity = 32;

        // Constructors.
        public ArrayQueue()
                        {
                                items = new Object [DefaultCapacity];
                                add = 0;
                                remove = 0;
                                size = 0;
                                growFactor = 2.0f;
                                generation = 0;
                        }
        public ArrayQueue(int capacity)
                        {
                                if(capacity < 0)
                                {
                                        throw new ArgumentOutOfRangeException
                                                ("capacity", 
S._("ArgRange_NonNegative"));
                                }
                                items = new T [capacity];
                                add = 0;
                                remove = 0;
                                size = 0;
                                growFactor = 2.0f;
                                generation = 0;
                        }
        public ArrayQueue(int capacity, float growFactor)
                        {
                                if(capacity < 0)
                                {
                                        throw new ArgumentOutOfRangeException
                                                ("capacity", 
S._("ArgRange_NonNegative"));
                                }
                                if(growFactor < 1.0f || growFactor > 10.0f)
                                {
                                        throw new ArgumentOutOfRangeException
                                                ("growFactor", 
S._("ArgRange_QueueGrowFactor"));
                                }
                                items = new T [capacity];
                                add = 0;
                                remove = 0;
                                size = 0;
                                this.growFactor = growFactor;
                                generation = 0;
                        }
        public ArrayQueue(ICollection<T> col)
                        {
                                if(col == null)
                                {
                                        throw new ArgumentNullException("col");
                                }
                                items = new T [col.Count];
                                col.CopyTo(items, 0);
                                add = 0;
                                remove = 0;
                                size = items.Length;
                                growFactor = 2.0f;
                                generation = 0;
                        }

        // Implement the ICollection<T> interface.
        public virtual void CopyTo(T[] array, int index)
                        {
                                if(array == null)
                                {
                                        throw new 
ArgumentNullException("array");
                                }
                                else if(index < 0)
                                {
                                        throw new ArgumentOutOfRangeException
                                                ("index", 
S._("ArgRange_Array"));
                                }
                                else if((array.Length - index) < size)
                                {
                                        throw new 
ArgumentException(S._("Arg_InvalidArrayRange"));
                                }
                                else if(size > 0)
                                {
                                        if((remove + size) <= items.Length)
                                        {
                                                Array.Copy(items, remove, 
array, index, size);
                                        }
                                        else
                                        {
                                                Array.Copy(items, remove, 
array, index,
                                                                   items.Length 
- remove);
                                                Array.Copy(items, 0, array,
                                                                   index + 
items.Length - remove, add);
                                        }
                                }
                        }
        public virtual int Count
                        {
                                get
                                {
                                        return size;
                                }
                        }
        public virtual bool IsSynchronized
                        {
                                get
                                {
                                        return false;
                                }
                        }
        public virtual Object SyncRoot
                        {
                                get
                                {
                                        return this;
                                }
                        }

        // Implement the ICloneable<T> interface.
        public virtual Object Clone()
                        {
                                ArrayQueue<T> queue = 
(ArrayQueue<T>)MemberwiseClone();
                                queue.items = (T[])items.Clone();
                                return queue;
                        }

        // Implement the IEnumerable<T> interface.
        public virtual IEnumerator<T> GetEnumerator()
                        {
                                return new QueueEnumerator<T>(this);
                        }

        // Implement the IIterable<T> interface.
        public virtual IIterable<T> GetIterator()
                        {
                                return new QueueIterator<T>(this);
                        }

        // Determine if this queue is read-only.
        public virtual bool IsReadOnly
                        {
                                get
                                {
                                        return false;
                                }
                        }

        // Clear the contents of this queue.
        public virtual void Clear()
                        {
                                add = 0;
                                remove = 0;
                                size = 0;
                                ++generation;
                        }

        // Determine if this queue contains a specific object.
        public virtual bool Contains(T obj)
                        {
                                int index = remove;
                                int capacity = items.Length;
                                int count = size;
                                if(typeof(T).IsValueType)
                                {
                                        while(count > 0)
                                        {
                                                if(obj.Equals(items[index]))
                                                {
                                                        return true;
                                                }
                                                index = (index + 1) % capacity;
                                                --count;
                                        }
                                }
                                else
                                {
                                        while(count > 0)
                                        {
                                                if(items[index] != null && obj 
!= null)
                                                {
                                                        
if(obj.Equals(items[index]))
                                                        {
                                                                return true;
                                                        }
                                                }
                                                else if(items[index] == null && 
obj == null)
                                                {
                                                        return true;
                                                }
                                                index = (index + 1) % capacity;
                                                --count;
                                        }
                                }
                                return false;
                        }

        // Implement the IQueue<T> interface.
        public virtual void Enqueue(T value)
                        {
                                if(size < items.Length)
                                {
                                        // The queue is big enough to hold the 
new item.
                                        items[add] = value;
                                        add = (add + 1) % items.Length;
                                        ++size;
                                }
                                else
                                {
                                        // We need to increase the size of the 
queue.
                                        int newCapacity = (int)(items.Length * 
growFactor);
                                        if(newCapacity <= items.Length)
                                        {
                                                newCapacity = items.Length + 1;
                                        }
                                        T[] newItems = new T [newCapacity];
                                        if(remove < size)
                                        {
                                                Array.Copy(items, remove, 
newItems, 0, size - remove);
                                        }
                                        if(remove > 0)
                                        {
                                                Array.Copy(items, 0, newItems, 
size - remove, remove);
                                        }
                                        items = newItems;
                                        add = size;
                                        remove = 0;
                                        items[add] = value;
                                        add = (add + 1) % items.Length;
                                        ++size;
                                }
                                ++generation;
                        }
        public virtual T Dequeue()
                        {
                                if(size > 0)
                                {
                                        T value = items[remove];
                                        remove = (remove + 1) % items.Length;
                                        --size;
                                        ++generation;
                                        return value;
                                }
                                else
                                {
                                        throw new InvalidOperationException
                                                (S._("Invalid_EmptyQueue"));
                                }
                        }
        public virtual T Peek()
                        {
                                if(size > 0)
                                {
                                        return items[remove];
                                }
                                else
                                {
                                        throw new InvalidOperationException
                                                (S._("Invalid_EmptyQueue"));
                                }
                        }
        public virtual T[] ToArray()
                        {
                                T[] array = new T [size];
                                if(size > 0)
                                {
                                        if((remove + size) <= items.Length)
                                        {
                                                Array.Copy(items, remove, 
array, 0, size);
                                        }
                                        else
                                        {
                                                Array.Copy(items, remove, 
array, 0,
                                                                   items.Length 
- remove);
                                                Array.Copy(items, 0, array,
                                                                   items.Length 
- remove, add);
                                        }
                                }
                                return array;
                        }

        // Convert this queue into a synchronized queue.
        public static ArrayQueue<T> Synchronized(ArrayQueue<T> queue)
                        {
                                if(queue == null)
                                {
                                        throw new 
ArgumentNullException("queue");
                                }
                                else if(queue.IsSynchronized)
                                {
                                        return queue;
                                }
                                else
                                {
                                        return new SynchronizedQueue<T>(queue);
                                }
                        }

        // Private class that implements synchronized queues.
        private class SynchronizedQueue : Queue
        {
                // Internal state.
                private ArrayQueue<T> queue;

                // Constructor.
                public SynchronizedQueue(ArrayQueue<T> queue)
                                {
                                        this.queue = queue;
                                }

                // Implement the ICollection<T> interface.
                public override void CopyTo(T[] array, int index)
                                {
                                        lock(SyncRoot)
                                        {
                                                queue.CopyTo(array, index);
                                        }
                                }
                public override int Count
                                {
                                        get
                                        {
                                                lock(SyncRoot)
                                                {
                                                        return queue.Count;
                                                }
                                        }
                                }
                public override bool IsSynchronized
                                {
                                        get
                                        {
                                                return true;
                                        }
                                }
                public override Object SyncRoot
                                {
                                        get
                                        {
                                                return queue.SyncRoot;
                                        }
                                }

                // Implement the ICloneable interface.
                public override Object Clone()
                                {
                                        return new SynchronizedQueue<T>
                                                
((ArrayQueue<T>)(queue.Clone()));
                                }

                // Implement the IEnumerable<T> interface.
                public override IEnumerator<T> GetEnumerator()
                                {
                                        lock(SyncRoot)
                                        {
                                                return new 
SynchronizedEnumerator<T>
                                                        (SyncRoot, 
queue.GetEnumerator());
                                        }
                                }

                // Clear the contents of this queue.
                public override void Clear()
                                {
                                        lock(SyncRoot)
                                        {
                                                queue.Clear();
                                        }
                                }

                // Determine if this queue contains a specific object.
                public override bool Contains(T obj)
                                {
                                        lock(SyncRoot)
                                        {
                                                return queue.Contains(obj);
                                        }
                                }

                // Dequeue an item.
                public override T Dequeue()
                                {
                                        lock(SyncRoot)
                                        {
                                                return queue.Dequeue();
                                        }
                                }

                // Enqueue an item.
                public override void Enqueue(T obj)
                                {
                                        lock(SyncRoot)
                                        {
                                                queue.Enqueue(obj);
                                        }
                                }

                // Peek at the first item without dequeuing it.
                public override T Peek()
                                {
                                        lock(SyncRoot)
                                        {
                                                return queue.Peek();
                                        }
                                }

                // Convert the contents of this queue into an array.
                public override T[] ToArray()
                                {
                                        lock(SyncRoot)
                                        {
                                                return queue.ToArray();
                                        }
                                }

        }; // class SynchronizedQueue

        // Private class for implementing queue enumeration.
        private class QueueEnumerator<T> : IEnumerator<T>
        {
                // Internal state.
                private ArrayQueue<T> queue;
                private int generation;
                private int position;

                // Constructor.
                public QueueEnumerator(ArrayQueue<T> queue)
                                {
                                        this.queue = queue;
                                        generation = queue.generation;
                                        position   = -1;
                                }

                // Implement the IEnumerator<T> interface.
                public bool MoveNext()
                                {
                                        if(generation != queue.generation)
                                        {
                                                throw new 
InvalidOperationException
                                                        
(S._("Invalid_CollectionModified"));
                                        }
                                        ++position;
                                        if(position < queue.size)
                                        {
                                                return true;
                                        }
                                        position = queue.size;
                                        return false;
                                }
                public void Reset()
                                {
                                        if(generation != queue.generation)
                                        {
                                                throw new 
InvalidOperationException
                                                        
(S._("Invalid_CollectionModified"));
                                        }
                                        position = -1;
                                }
                public T Current
                                {
                                        get
                                        {
                                                if(generation != 
queue.generation)
                                                {
                                                        throw new 
InvalidOperationException
                                                                
(S._("Invalid_CollectionModified"));
                                                }
                                                if(position < 0 || position >= 
queue.size)
                                                {
                                                        throw new 
InvalidOperationException
                                                                
(S._("Invalid_BadEnumeratorPosition"));
                                                }
                                                return queue.items
                                                        [(queue.remove + 
position) % queue.size];
                                        }
                                }

        }; // class QueueEnumerator<T>

        // Private class for implementing queue iteration.
        private class QueueIterator<T> : IIterator<T>
        {
                // Internal state.
                private ArrayQueue<T> queue;
                private int position;
                private bool reset;

                // Constructor.
                public QueueIterator(ArrayQueue<T> queue)
                                {
                                        this.queue = queue;
                                        position = -1;
                                        reset = true;
                                }

                // Implement the IEnumerator<T> interface.
                public bool MoveNext()
                                {
                                        if(reset)
                                        {
                                                position = 0;
                                                reset = false;
                                        }
                                        else
                                        {
                                                ++position;
                                        }
                                        return (position < queue.size);
                                }
                public void Reset()
                                {
                                        position = -1;
                                        reset = true;
                                }
                T IEnumerator<T>.Current
                                {
                                        get
                                        {
                                                if(position < 0 || position >= 
queue.size)
                                                {
                                                        throw new 
InvalidOperationException
                                                                
(S._("Invalid_BadIteratorPosition"));
                                                }
                                                return queue.items
                                                        [(queue.remove + 
position) % queue.size];
                                        }
                                }

                // Implement the IIterator<T> interface.
                public bool MovePrev()
                                {
                                        if(reset)
                                        {
                                                position = queue.size - 1;
                                                reset = false;
                                        }
                                        else
                                        {
                                                --position;
                                        }
                                        return (position >= 0);
                                }
                public T Current
                                {
                                        get
                                        {
                                                if(position < 0 || position >= 
queue.size)
                                                {
                                                        throw new 
InvalidIteratorPosition
                                                                
(S._("Invalid_BadEnumeratorPosition"));
                                                }
                                                return queue.items
                                                        [(queue.remove + 
position) % queue.size];
                                        }
                                        set
                                        {
                                                if(position < 0 || position >= 
queue.size)
                                                {
                                                        throw new 
InvalidOperationException
                                                                
(S._("Invalid_BadIteratorPosition"));
                                                }
                                                queue.items[(queue.remove + 
position) % queue.size]
                                                        = value;
                                        }
                                }

        }; // class QueueIterator<T>

}; // class ArrayQueue<T>

}; // namespace Generics

--- NEW FILE ---
/*
 * IQueue.cs - Interface to queue-like structures.
 *
 * Copyright (c) 2003  Southern Storm Software, Pty Ltd
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
 */

namespace Generics
{

using System;

public interface IQueue<T> : ICollection<T>, IEnumerable<T>, IIterable<T>
{
        void Enqueue(T value);
        T Dequeue();
        T Peek();
        T[] ToArray();

}; // interface IQueue<T>

}; // namespace Generics

--- Queue.cs DELETED ---





reply via email to

[Prev in Thread] Current Thread [Next in Thread]