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 #if GENERICS
  12 using System;
  13 using System.Runtime.InteropServices;
  14
  15 namespace System.Collections.Generic
  16 {
  17         [CLSCompliant(false)]
  18         [ComVisible(false)]
  19         public class Queue<T> : ICollection<T>, IEnumerable<T>,
  20                 ICollection, IEnumerable
  21         {
  22                 int count;
  23                 protected int modified;
  24                 protected Node head;
  25                 Node tail;
  26
  27                 public void Clear ()
  28                 {
  29                         head = tail = null;
  30                         count = 0;
  31                         modified++;
  32                 }
  33
  34                 public void Enqueue (T item)
  35                 {
  36                         tail = new Node (tail, item);
  37                         if (head == null)
  38                                 head = tail;
  39                         count++;
  40                         modified++;
  41                 }
  42
  43                 public T Peek ()
  44                 {
  45                         if (head == null)
  46                                 throw new ArgumentException ();
  47
  48                         return head.Item;
  49                 }
  50
  51                 public T Dequeue ()
  52                 {
  53                         if (head == null)
  54                                 throw new ArgumentException ();
  55
  56                         T retval = head.Item;
  57                         head = head.Next;
  58                         if (head == null)
  59                                 tail = null;
  60                         count--;
  61                         modified++;
  62                         return retval;
  63                 }
  64
  65                 public bool Contains (T item)
  66                 {
  67                         for (Node node = head; node != null; node = node.Next)
  68                                 if (node.Item == item)
  69                                         return true;
  70
  71                         return false;
  72                 }
  73
  74                 public virtual void CopyTo (T[] array, int start)
  75                 {
  76                         if (start + count >= array.Length)
  77                                 throw new ArgumentException ();
  78
  79                         for (Node node = head; node != null; node = node.Next)
  80                                 array [start++] = node.Item;
  81                 }
  82
  83                 void ICollection.CopyTo (Array array, int start)
  84                 {
  85                         if (start + count >= array.Length)
  86                                 throw new ArgumentException ();
  87
  88                         for (Node node = head; node != null; node = node.Next)
  89                                 array.SetValue (node.Item, start++);
  90                 }
  91
  92                 public T[] ToArray ()
  93                 {
  94                         int pos = 0;
  95                         T[] retval = new T [count];
  96                         for (Node node = head; node != null; node = node.Next)
  97                                 retval [pos++] = node.Item;
  98
  99                         return retval;
 100                 }
 101
 102                 public void TrimToSize ()
 103                 { }
 104
 105                 public int Count {
 106                         get { return count; }
 107                 }
 108
 109                 public bool IsSynchronized {
 110                         get { return false; }
 111                 }
 112
 113                 public object SyncRoot {
 114                         get { return this; }
 115                 }
 116
 117                 public IEnumerator<T> GetEnumerator ()
 118                 {
 119                         return new Enumerator (this);
 120                 }
 121
 122                 IEnumerator IEnumerable.GetEnumerator ()
 123                 {
 124                         return new Enumerator (this);
 125                 }
 126
 127                 protected sealed class Node
 128                 {
 129                         public readonly T Item;
 130                         public readonly Node Next;
 131
 132                         public Node (Node next, T item)
 133                         {
 134                                 this.Next = next;
 135                                 this.Item = item;
 136                         }
 137                 }
 138
 139                 protected class Enumerator : IEnumerator<T>, IEnumerator
 140                 {
 141                         Queue<T> queue;
 142                         int modified;
 143                         Node current;
 144
 145                         public Enumerator (Queue<T> queue)
 146                         {
 147                                 this.queue = queue;
 148                                 this.modified = queue.modified;
 149                                 this.current = queue.head;
 150                         }
 151
 152                         public T Current {
 153                                 get {
 154                                         if (queue.modified != modified)
 155                                                 throw new InvalidOperationException ();
 156                                         if (current == null)
 157                                                 throw new ArgumentException ();
 158                                         return current.Item;
 159                                 }
 160                         }
 161
 162                         object IEnumerator.Current {
 163                                 get {
 164                                         return Current;
 165                                 }
 166                         }
 167
 168                         public bool MoveNext ()
 169                         {
 170                                 if (queue.modified != modified)
 171                                         throw new InvalidOperationException ();
 172                                 if (current == null)
 173                                         throw new ArgumentException ();
 174
 175                                 current = current.Next;
 176                                 return current != null;
 177                         }
 178
 179                         public void Reset () {
 180                                 if (queue.modified != modified)
 181                                         throw new InvalidOperationException();
 182
 183                                 current = queue.head;
 184                         }
 185
 186                         public void Dispose ()
 187                         {
 188                                 modified = -1;
 189                         }
 190                 }
 191         }
 192 }
 193 #endif