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<T> head;
  25                 Node<T> 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<T> (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<T> 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<T> node = head; node != null; node = node.Next)
  80                                 array [start++] = node.Item;
  81                 }
  82
  83                 public T[] ToArray ()
  84                 {
  85                         int pos = 0;
  86                         T[] retval = new T [count];
  87                         for (Node<T> node = head; node != null; node = node.Next)
  88                                 retval [pos++] = node.Item;
  89
  90                         return retval;
  91                 }
  92
  93                 public void TrimToSize ()
  94                 { }
  95
  96                 public int Count {
  97                         get { return count; }
  98                 }
  99
 100                 public IEnumerator<T> GetEnumerator ()
 101                 {
 102                         return new Enumerator (this);
 103                 }
 104
 105                 protected sealed class Node<T>
 106                 {
 107                         public readonly T Item;
 108                         public readonly Node<T> Next;
 109
 110                         public Node (Node<T> next, T item)
 111                         {
 112                                 this.Next = next;
 113                                 this.Item = item;
 114                         }
 115                 }
 116
 117                 protected class Enumerator : IEnumerator<T>
 118                 {
 119                         Queue<T> queue;
 120                         int modified;
 121                         Node<T> current;
 122
 123                         public Enumerator (Queue<T> queue)
 124                         {
 125                                 this.queue = queue;
 126                                 this.modified = queue.modified;
 127                                 this.current = queue.head;
 128                         }
 129
 130                         public T Current {
 131                                 get {
 132                                         if (queue.modified != modified)
 133                                                 throw new InvalidOperationException ();
 134                                         if (current == null)
 135                                                 throw new ArgumentException ();
 136                                         return current.Item;
 137                                 }
 138                         }
 139
 140                         public bool MoveNext ()
 141                         {
 142                                 if (queue.modified != modified)
 143                                         throw new InvalidOperationException ();
 144                                 if (current == null)
 145                                         throw new ArgumentException ();
 146
 147                                 current = current.Next;
 148                                 return current != null;
 149                         }
 150
 151                         public void Dispose ()
 152                         {
 153                                 modified = -1;
 154                         }
 155                 }
 156         }
 157 }
 158 #endif