mcs/class/corlib/System.Collections.Generic/Queue.cs

   1 // -*- Mode: csharp; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*-
   2 //
   3 // System.Collections.Generic.Queue
   4 //
   5 // Author:
   6 //    Martin Baulig (martin@ximian.com)
   7 //
   8 // (C) 2003 Novell, Inc.
   9 //
  10
  11 //
  12 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
  13 //
  14 // Permission is hereby granted, free of charge, to any person obtaining
  15 // a copy of this software and associated documentation files (the
  16 // "Software"), to deal in the Software without restriction, including
  17 // without limitation the rights to use, copy, modify, merge, publish,
  18 // distribute, sublicense, and/or sell copies of the Software, and to
  19 // permit persons to whom the Software is furnished to do so, subject to
  20 // the following conditions:
  21 //
  22 // The above copyright notice and this permission notice shall be
  23 // included in all copies or substantial portions of the Software.
  24 //
  25 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  26 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  27 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  28 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  29 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  30 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  31 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  32 //
  33
  34 #if NET_2_0
  35 using System;
  36 using System.Runtime.InteropServices;
  37
  38 namespace System.Collections.Generic
  39 {
  40         [CLSCompliant(false)]
  41         [ComVisible(false)]
  42         public class Queue<T> : ICollection<T>, IEnumerable<T>,
  43                 ICollection, IEnumerable
  44         {
  45                 int count;
  46                 protected int modified;
  47                 protected Node head;
  48                 Node tail;
  49
  50                 public void Clear ()
  51                 {
  52                         head = tail = null;
  53                         count = 0;
  54                         modified++;
  55                 }
  56
  57                 public void Enqueue (T item)
  58                 {
  59                         tail = new Node (tail, item);
  60                         if (head == null)
  61                                 head = tail;
  62                         count++;
  63                         modified++;
  64                 }
  65
  66                 public T Peek ()
  67                 {
  68                         if (head == null)
  69                                 throw new ArgumentException ();
  70
  71                         return head.Item;
  72                 }
  73
  74                 public T Dequeue ()
  75                 {
  76                         if (head == null)
  77                                 throw new ArgumentException ();
  78
  79                         T retval = head.Item;
  80                         head = head.Next;
  81                         if (head == null)
  82                                 tail = null;
  83                         count--;
  84                         modified++;
  85                         return retval;
  86                 }
  87
  88                 public bool Contains (T item)
  89                 {
  90                         for (Node node = head; node != null; node = node.Next)
  91                                 if (node.Item == item)
  92                                         return true;
  93
  94                         return false;
  95                 }
  96
  97                 public virtual void CopyTo (T[] array, int start)
  98                 {
  99                         // re-ordered to avoid possible integer overflow
 100                         if (start >= array.Length - count)
 101                                 throw new ArgumentException ();
 102
 103                         for (Node node = head; node != null; node = node.Next)
 104                                 array [start++] = node.Item;
 105                 }
 106
 107                 void ICollection.CopyTo (Array array, int start)
 108                 {
 109                         // re-ordered to avoid possible integer overflow
 110                         if (start >= array.Length - count)
 111                                 throw new ArgumentException ();
 112
 113                         for (Node node = head; node != null; node = node.Next)
 114                                 array.SetValue (node.Item, start++);
 115                 }
 116
 117                 public T[] ToArray ()
 118                 {
 119                         int pos = 0;
 120                         T[] retval = new T [count];
 121                         for (Node node = head; node != null; node = node.Next)
 122                                 retval [pos++] = node.Item;
 123
 124                         return retval;
 125                 }
 126
 127                 public void TrimToSize ()
 128                 { }
 129
 130                 public int Count {
 131                         get { return count; }
 132                 }
 133
 134                 public bool IsSynchronized {
 135                         get { return false; }
 136                 }
 137
 138                 public object SyncRoot {
 139                         get { return this; }
 140                 }
 141
 142                 public IEnumerator<T> GetEnumerator ()
 143                 {
 144                         return new Enumerator (this);
 145                 }
 146
 147                 IEnumerator IEnumerable.GetEnumerator ()
 148                 {
 149                         return new Enumerator (this);
 150                 }
 151
 152                 protected sealed class Node
 153                 {
 154                         public readonly T Item;
 155                         public readonly Node Next;
 156
 157                         public Node (Node next, T item)
 158                         {
 159                                 this.Next = next;
 160                                 this.Item = item;
 161                         }
 162                 }
 163
 164                 protected class Enumerator : IEnumerator<T>, IEnumerator
 165                 {
 166                         Queue<T> queue;
 167                         int modified;
 168                         Node current;
 169
 170                         public Enumerator (Queue<T> queue)
 171                         {
 172                                 this.queue = queue;
 173                                 this.modified = queue.modified;
 174                                 this.current = queue.head;
 175                         }
 176
 177                         public T Current {
 178                                 get {
 179                                         if (queue.modified != modified)
 180                                                 throw new InvalidOperationException ();
 181                                         if (current == null)
 182                                                 throw new ArgumentException ();
 183                                         return current.Item;
 184                                 }
 185                         }
 186
 187                         object IEnumerator.Current {
 188                                 get {
 189                                         return Current;
 190                                 }
 191                         }
 192
 193                         public bool MoveNext ()
 194                         {
 195                                 if (queue.modified != modified)
 196                                         throw new InvalidOperationException ();
 197                                 if (current == null)
 198                                         throw new ArgumentException ();
 199
 200                                 current = current.Next;
 201                                 return current != null;
 202                         }
 203
 204                         public void Reset () {
 205                                 if (queue.modified != modified)
 206                                         throw new InvalidOperationException();
 207
 208                                 current = queue.head;
 209                         }
 210
 211                         public void Dispose ()
 212                         {
 213                                 modified = -1;
 214                         }
 215                 }
 216         }
 217 }
 218 #endif