Flexible Queue Klasse

Beschreibung:

Diese Klasse dient dazu mit O(n) Geschwindigkeit Elemente in die Queue an einem beliebigen Index einzufügen. Ansonsten ähnelt die Funktion der normalen Standard-Queue.

Der Code besteht aus zwei Klassen und einem Interface.

    /// <summary>
    /// Defines the signature of a FlexibleQueue object.
    /// </summary>
    public interface IFlexibleQueue<T> : ICollection<T>, IEnumerable<T>
    {
        T Peek();

        T Dequeue();

        void Enqueue(T item);

        void PushIn(T item);

        void Insert(T item, int index);
    }

   /// <summary>
    /// A basic flexible Queue class. This class enables the insertion of items
    /// in any order in O(n) speed. It provides the knowen queue methods from 
    /// the default Queue class.
    /// </summary>
    public class FlexibleQueue<T> : IFlexibleQueue<T>
    {
        /// <summary>
        /// Nested class for the linked list structure.
        /// </summary>
        /// <typeparam name="S">The type of the ParameterQueue</typeparam>
        internal class QueueItem<S>
        {
            /// <summary>
            /// Gets or sets the value of this item.
            /// </summary>
            internal S Item { get; set; }

            /// <summary>
            /// Gets or sets the pointer to the next QueueItem object.
            /// </summary>
            internal QueueItem<S> Next { get; set; }
        }

        /// <summary>
        /// Gets the size of the queue object.
        /// </summary>
        public int Count { get; private set; }
        
        /// <summary>
        /// The pointer to the first QueueItem in the list.
        /// </summary>
        internal QueueItem<T> First { get; set; }

        /// <summary>
        /// The pointer to the last QueueItem in the list.
        /// </summary>
        internal QueueItem<T> Last { get; set; }

        public FlexibleQueue()
        {
            First = Last = null;
            Count = 0;
        }

        /// <summary>
        /// Gets the value of the first element in the queue.
        /// </summary>
        public T Peek()
        {
            if (First == null)
                throw new IndexOutOfRangeException("Queue is empty!");

            return First.Item;
        }

        /// <summary>
        /// Dequeues the first element in the list and returns it.
        /// </summary>
        public T Dequeue()
        {
            if (Count <= 0)
                throw new IndexOutOfRangeException("Queue is empty!");
            else
            {
                T item = First.Item;
                First = First.Next;
                Count--;
                return item;
            }
        }

        /// <summary>
        /// Enqueues the element at the end of the list.
        /// </summary>
        public void Enqueue(T item)
        {
            InsertLastElement(item);
            Count++;
        }

        /// <summary>
        /// Enqueues the given flexible queue at the end of this queue object.
        /// </summary>
        public void Enqueue(FlexibleQueue<T> queue)
        {
            if (queue == null)
                throw new ArgumentNullException("Queue for enqueuing must not be null!");

            if (queue.Count > 0)
            {
                if (Last != null)
                {
                    Last.Next = queue.First;
                    Last = queue.Last;
                }
                else
                {
                    First = queue.First;
                    Last = queue.Last;
                }

                Count += queue.Count;
            }
        }

        /// <summary>
        /// Pushes in the item at Index 0.
        /// </summary>
        public void PushIn(T item)
        {
            InsertFirstElement(item);
            Count++;
        }

        /// <summary>
        /// Inserts the given queue at the beginning of the collection.
        /// </summary>
        public void PushIn(FlexibleQueue<T> queue)
        {
            if (queue == null)
                throw new ArgumentNullException("Given queue must not be null!");

            if (queue.Count > 0)
            {
                if (First != null)
                {
                    queue.Last.Next = First;
                    First = queue.First;
                }
                else
                {
                    First = queue.First;
                    Last = queue.Last;
                }

                Count += queue.Count;
            }
        }

        /// <summary>
        /// Inserts the object at the specified Index.
        /// </summary>
        public void Insert(T item, int index)
        {
            if (index >= Count)
                throw new IndexOutOfRangeException("Index is not within the bounds of the collection!");

            if (IsStartIndex(index)) { InsertFirstElement(item); }
            else if (IsEndIndex(index)) { InsertLastElement(item); }
            else
            {
                QueueItem<T> current = First;
                QueueItem<T> prev = null;
                QueueItem<T> insertion = new QueueItem<T>() { Item = item };

                for (int i = 0; i < index; i++)
                {
                    prev = current;
                    current = current.Next;
                }

                prev.Next = insertion;
                insertion.Next = current;
            }
    
            Count++;
        }

        /// <summary>
        /// Checks if the given Index is the start Index.
        /// </summary>
        private bool IsStartIndex(int index)
        {
            return (index == 0);
        }

        /// <summary>
        /// Checks if the given Index is the Index of the last item.s
        /// </summary>
        private bool IsEndIndex(int i)
        {
            return (i == (Count - 1));
        }

        /// <summary>
        /// Inserts the item at the end of the list.
        /// </summary>
        private void InsertLastElement(T item)
        {
            if (Count == 0)
            {
                Last = First = new QueueItem<T>() { Item = item };
            }
            else
            {
                Last.Next = new QueueItem<T>() { Item = item };
                Last = Last.Next;
            }
        }

        /// <summary>
        /// Inserts the item at the start of the list.
        /// </summary>
        private void InsertFirstElement(T item)
        {
            if (Count == 0)
            {
                First = Last = new QueueItem<T> { Item = item };
            }
            else
            {
                QueueItem<T> it = new QueueItem<T>() { Item = item };
                it.Next = First;
                First = it;
            }
        }

        /// <summary>
        /// Adds the item at the end of the list.
        /// </summary>
        public void Add(T item)
        {
            Enqueue(item);
        }

        /// <summary>
        /// Clears the queue.
        /// </summary>
        public void Clear()
        {
            Count = 0;
            First = Last = null;
        }

        /// <summary>
        /// Checks if the queue contains the given item.
        /// </summary>
        public bool Contains(T item)
        {
            QueueItem<T> current = First;

            for (int i = 0; i < Count; i++)
            {
                if (current.Item.GetHashCode() == item.GetHashCode())
                    return true;

                current = current.Next;
            }

            return false;
        }

        /// <summary>
        /// Copies the items from the beginning Index to the array.
        /// </summary>
        public void CopyTo(T[] array, int arrayIndex)
        {
            if (arrayIndex >= Count)
                throw new IndexOutOfRangeException("Index is not within the bounds of the list!");

            if (array.Length < (Count - arrayIndex))
                throw new ArgumentOutOfRangeException("Array has insufficent length for coping process!");

            QueueItem<T> current = First;

            for (int i = 0; i < arrayIndex; i++)
                current = current.Next;

            for (int i = 0; (arrayIndex + i) < Count; i++)
            {
                array[i] = current.Item;
                current = current.Next;
            }
        }

        /// <summary>
        /// Gets allways the value false. This is a read and write collection.
        /// </summary>
        public bool IsReadOnly
        {
            get { return false; }
        }

        /// <summary>
        /// If the queue contains the item it gets removed.
        /// </summary>
        public bool Remove(T item)
        {
            QueueItem<T> prev = null;
            QueueItem<T> current = First;

            for (int i = 0; i < Count; i++)
            {
                if (current.Item.GetHashCode() == item.GetHashCode())
                {
                    if (prev == null)
                        First = current.Next;
                    else
                        prev.Next = current.Next;

                    current.Next = null;
                    return true;
                }

                prev = current;
                current = current.Next;
            }

            return false;
        }

        /// <summary>
        /// Removes the item at the given Index.
        /// </summary>
        public void RemoveAt(int index)
        {
            if (index >= Count)
                throw new IndexOutOfRangeException("Index is not within the bounds of the queue!");

            if (IsStartIndex(index)) { RemoveFirstItem(); }
            else if (IsEndIndex(index)) { RemoveLastItem(); }
            else
            {
                QueueItem<T> prev = null;
                QueueItem<T> current = First;

                for (int i = 0; i < index; i++)
                {
                    prev = current;
                    current = current.Next;
                }

                prev.Next = current.Next;
                current.Next = null;
            }

            Count--;
        }

        /// <summary>
        /// Removes the first item.
        /// </summary>
        private void RemoveFirstItem()
        {
            if (Count > 1)
                First = First.Next;
            else
                First = Last = null;
        }

        /// <summary>
        /// Removes the last item.
        /// </summary>
        private void RemoveLastItem()
        {
            QueueItem<T> current = First;

            for (int i = 0; i < (Count - 1); i++)
                current = current.Next;

            Last = current;
            current.Next = null;
        }
        
        /// <summary>
        /// Returns an enumerator for this collection.
        /// </summary>
        public IEnumerator<T> GetEnumerator()
        {
            return new FlexibleQueueEnumerator<T>(this);
        }

        /// <summary>
        /// Returns an enumerator for this collection.
        /// </summary>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }
    /// <summary>
    /// Enumerator class for the ParameterQueue collection class.
    /// </summary>
    public class FlexibleQueueEnumerator<T> : IEnumerator<T>
    {
        private int Index;

        private int ItemCount;

        private FlexibleQueue<T>.QueueItem<T> FirstItem;

        private FlexibleQueue<T>.QueueItem<T> CurrentItem;

        public FlexibleQueueEnumerator(FlexibleQueue<T> flexibleQueue)
        {
            FirstItem = flexibleQueue.First;
            CurrentItem = FirstItem;
            ItemCount = flexibleQueue.Count;
            Index = -1;
        }

        /// <summary>
        /// Gets the current item.
        /// </summary>
        public T Current
        {
            get { return CurrentItem.Item; }
        }

        /// <summary>
        /// Disposes this object.
        /// </summary>
        public void Dispose()
        {
            GC.SuppressFinalize(this);
        }
       
        /// <summary>
        /// Gets the current item.
        /// </summary>
        object System.Collections.IEnumerator.Current
        {
            get { return Current; }
        }

        /// <summary>
        /// Moves the item pointer to the next element. If the end was allready reached
        /// it returns false otherwise true.
        /// </summary>
        public bool MoveNext()
        {
            if (Index < (ItemCount - 1))
            {
                if(Index != -1)
                    CurrentItem = CurrentItem.Next;

                Index++;
                return true;
            }

            return false;
        }

        /// <summary>
        /// Resets the pointer to the start of the collection.
        /// </summary>
        public void Reset()
        {
            Index = 0;
            CurrentItem = FirstItem;
        }
    }

Schlagwörter: Queue Collection

Edit:
v1.1 herbivores Vorschläge umgesetzt
v1.2 Enqueue/PushIn Methoden in FlexibleQueue für FlexibleQueue Objekte hinzugefügt.

Hallo der-schlingel,

man kann sich natürlich streiten, ob eine Queue, bei der man auch an beliebigen Positionen einfügen und Elemente unabhängig von ihrer Position entfernen kann, überhaupt noch eine Queue ist. 😃

Wenn ich mich darauf einlasse 😃 fällt mir folgendes auf:
*IFlexibleQueue<T> wird in deinem Code verwendet, aber nicht definiert. *"Erbt" IFlexibleQueue<T> von IEnumerable<T>, ICollection, IEnumerable? Das wäre gut. *Wenn es InsertAt (das nach den üblichen Konventionen einfach Insert heißen sollte) und Remove gibt, dann sollte es auch RemoveAt geben. *Darüber, ob man Clone anbieten sollte, kann man sicher streiten. Wenn man es anbietet, sollte es aber auch immer funktionieren. Bei dir ist das nur der Fall, wenn die Elemente in der Queue serialisierbar sind. Ich würde Close eher als Shallow-Copy implementieren. Dann entgehst du auch der Abhängigkeit vom Elementtyp. *T[] array = null; CopyTo(array, 0); in GetEnumerator wird schiefgehen. Ich finde es ohnehin besser, GetEnumerator nur einmal zu implementieren und aus dem anderen GetEnumerator die erste GetEnumerator-Methode aufzurufen. Man sieht ja, dass es sonst zu Abweichungen kommen kann. Auch Current würde ich nur einmal kopieren und dann aus dem anderen Current heraus aufrufen. *Für den Enumerator alle Elemente erst in ein Array zu kopieren, finde ich ungünstig. Schöner wäre, wenn der Enumerator als innere Klasse direkt durch die verkette Liste laufen würde. Das macht das Abrufen des Enumerators zu einer O(1)-Operation. Momentan ist es - unnötigerweise - eine O(n)-Operation. *Eigentlich müsste Peek, wenn die Queue leer ist, die gleiche Exception werfen wie Dequeue. Das Element, auf das man mit Peek zugreifen will, ist dann genauso wenig vorhanden, wie bei Dequeue.

Das alles soll aber nicht darüber hinwegtäuschen, dass deine Queue durchaus praktisch ist. Vielleicht schreibst du ja auch noch eine PriorityQueue, bei der man beim Dequeue zuerst die Elemente mit der höchsten Priorität bekommt. Die Priorität muss man beim Enqueue dann natürlich angeben. Das wird in vielen Fällen noch flexibler und vor allem einfacher sein, als wenn man als Aufrufer Elemente an beliebiger Position hinzufügen kann.

herbivore