Code:
/ Dotnetfx_Win7_3.5.1 / Dotnetfx_Win7_3.5.1 / 3.5.1 / DEVDIV / depot / DevDiv / releases / whidbey / NetFXspW7 / ndp / clr / src / BCL / System / Collections / Queue.cs / 1 / Queue.cs
// ==++== // // Copyright (c) Microsoft Corporation. All rights reserved. // // ==--== /*============================================================================== ** ** Class: Queue ** ** Purpose: A circular-array implementation of a queue. ** ** =============================================================================*/ namespace System.Collections { using System; using System.Security.Permissions; using System.Diagnostics; // A simple Queue of objects. Internally it is implemented as a circular // buffer, so Enqueue can be O(n). Dequeue is O(1). [DebuggerTypeProxy(typeof(System.Collections.Queue.QueueDebugView))] [DebuggerDisplay("Count = {Count}")] [System.Runtime.InteropServices.ComVisible(true)] [Serializable()] public class Queue : ICollection, ICloneable { private Object[] _array; private int _head; // First valid element in the queue private int _tail; // Last valid element in the queue private int _size; // Number of elements. private int _growFactor; // 100 == 1.0, 130 == 1.3, 200 == 2.0 private int _version; [NonSerialized] private Object _syncRoot; private const int _MinimumGrow = 4; private const int _ShrinkThreshold = 32; // Creates a queue with room for capacity objects. The default initial // capacity and grow factor are used. public Queue() : this(32, (float)2.0) { } // Creates a queue with room for capacity objects. The default grow factor // is used. // public Queue(int capacity) : this(capacity, (float)2.0) { } // Creates a queue with room for capacity objects. When full, the new // capacity is set to the old capacity * growFactor. // public Queue(int capacity, float growFactor) { if (capacity < 0) throw new ArgumentOutOfRangeException("capacity", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); if (!(growFactor >= 1.0 && growFactor <= 10.0)) throw new ArgumentOutOfRangeException("growFactor", Environment.GetResourceString("ArgumentOutOfRange_QueueGrowFactor", 1, 10)); _array = new Object[capacity]; _head = 0; _tail = 0; _size = 0; _growFactor = (int)(growFactor * 100); } // Fills a Queue with the elements of an ICollection. Uses the enumerator // to get each of the elements. // public Queue(ICollection col) : this((col==null ? 32 : col.Count)) { if (col==null) throw new ArgumentNullException("col"); IEnumerator en = col.GetEnumerator(); while(en.MoveNext()) Enqueue(en.Current); } public virtual int Count { get { return _size; } } public virtual Object Clone() { Queue q = new Queue(_size); q._size = _size; int numToCopy = _size; int firstPart = (_array.Length - _head < numToCopy) ? _array.Length - _head : numToCopy; Array.Copy(_array, _head, q._array, 0, firstPart); numToCopy -= firstPart; if (numToCopy > 0) Array.Copy(_array, 0, q._array, _array.Length - _head, numToCopy); q._version = _version; return q; } public virtual bool IsSynchronized { get { return false; } } public virtual Object SyncRoot { get { if( _syncRoot == null) { System.Threading.Interlocked.CompareExchange(ref _syncRoot, new Object(), null); } return _syncRoot; } } // Removes all Objects from the queue. public virtual void Clear() { if (_head < _tail) Array.Clear(_array, _head, _size); else { Array.Clear(_array, _head, _array.Length - _head); Array.Clear(_array, 0, _tail); } _head = 0; _tail = 0; _size = 0; _version++; } // CopyTo copies a collection into an Array, starting at a particular // index into the array. // public virtual void CopyTo(Array array, int index) { if (array==null) throw new ArgumentNullException("array"); if (array.Rank != 1) throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported")); if (index < 0) throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index")); int arrayLen = array.Length; if (arrayLen - index < _size) throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); int numToCopy = _size; if (numToCopy == 0) return; int firstPart = (_array.Length - _head < numToCopy) ? _array.Length - _head : numToCopy; Array.Copy(_array, _head, array, index, firstPart); numToCopy -= firstPart; if (numToCopy > 0) Array.Copy(_array, 0, array, index+_array.Length - _head, numToCopy); } // Adds obj to the tail of the queue. // public virtual void Enqueue(Object obj) { if (_size == _array.Length) { int newcapacity = (int)((long)_array.Length * (long)_growFactor / 100); if (newcapacity < _array.Length + _MinimumGrow) { newcapacity = _array.Length + _MinimumGrow; } SetCapacity(newcapacity); } _array[_tail] = obj; _tail = (_tail + 1) % _array.Length; _size++; _version++; } // GetEnumerator returns an IEnumerator over this Queue. This // Enumerator will support removing. // public virtual IEnumerator GetEnumerator() { return new QueueEnumerator(this); } // Removes the object at the head of the queue and returns it. If the queue // is empty, this method simply returns null. public virtual Object Dequeue() { if (_size == 0) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyQueue")); Object removed = _array[_head]; _array[_head] = null; _head = (_head + 1) % _array.Length; _size--; _version++; return removed; } // Returns the object at the head of the queue. The object remains in the // queue. If the queue is empty, this method throws an // InvalidOperationException. public virtual Object Peek() { if (_size == 0) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyQueue")); return _array[_head]; } // Returns a synchronized Queue. Returns a synchronized wrapper // class around the queue - the caller must not use references to the // original queue. // [HostProtection(Synchronization=true)] public static Queue Synchronized(Queue queue) { if (queue==null) throw new ArgumentNullException("queue"); return new SynchronizedQueue(queue); } // Returns true if the queue contains at least one object equal to obj. // Equality is determined using obj.Equals(). // // Exceptions: ArgumentNullException if obj == null. public virtual bool Contains(Object obj) { int index = _head; int count = _size; while (count-- > 0) { if (obj == null) { if (_array[index] == null) return true; } else if (_array[index] != null && _array[index].Equals(obj)) { return true; } index = (index + 1) % _array.Length; } return false; } internal Object GetElement(int i) { return _array[(_head + i) % _array.Length]; } // Iterates over the objects in the queue, returning an array of the // objects in the Queue, or an empty array if the queue is empty. // The order of elements in the array is first in to last in, the same // order produced by successive calls to Dequeue. public virtual Object[] ToArray() { Object[] arr = new Object[_size]; if (_size==0) return arr; if (_head < _tail) { Array.Copy(_array, _head, arr, 0, _size); } else { Array.Copy(_array, _head, arr, 0, _array.Length - _head); Array.Copy(_array, 0, arr, _array.Length - _head, _tail); } return arr; } // PRIVATE Grows or shrinks the buffer to hold capacity objects. Capacity // must be >= _size. private void SetCapacity(int capacity) { Object[] newarray = new Object[capacity]; if (_size > 0) { if (_head < _tail) { Array.Copy(_array, _head, newarray, 0, _size); } else { Array.Copy(_array, _head, newarray, 0, _array.Length - _head); Array.Copy(_array, 0, newarray, _array.Length - _head, _tail); } } _array = newarray; _head = 0; _tail = (_size == capacity) ? 0 : _size; _version++; } public virtual void TrimToSize() { SetCapacity(_size); } // Implements a synchronization wrapper around a queue. [Serializable()] private class SynchronizedQueue : Queue { private Queue _q; private Object root; internal SynchronizedQueue(Queue q) { this._q = q; root = _q.SyncRoot; } public override bool IsSynchronized { get { return true; } } public override Object SyncRoot { get { return root; } } public override int Count { get { lock (root) { return _q.Count; } } } public override void Clear() { lock (root) { _q.Clear(); } } public override Object Clone() { lock (root) { return new SynchronizedQueue((Queue)_q.Clone()); } } public override bool Contains(Object obj) { lock (root) { return _q.Contains(obj); } } public override void CopyTo(Array array, int arrayIndex) { lock (root) { _q.CopyTo(array, arrayIndex); } } public override void Enqueue(Object value) { lock (root) { _q.Enqueue(value); } } public override Object Dequeue() { lock (root) { return _q.Dequeue(); } } public override IEnumerator GetEnumerator() { lock (root) { return _q.GetEnumerator(); } } public override Object Peek() { lock (root) { return _q.Peek(); } } public override Object[] ToArray() { lock (root) { return _q.ToArray(); } } public override void TrimToSize() { lock (root) { _q.TrimToSize(); } } } // Implements an enumerator for a Queue. The enumerator uses the // internal version number of the list to ensure that no modifications are // made to the list while an enumeration is in progress. [Serializable()] private class QueueEnumerator : IEnumerator, ICloneable { private Queue _q; private int _index; private int _version; private Object currentElement; internal QueueEnumerator(Queue q) { _q = q; _version = _q._version; _index = 0; currentElement = _q._array; if (_q._size == 0) _index = -1; } public Object Clone() { return MemberwiseClone(); } public virtual bool MoveNext() { if (_version != _q._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion)); if (_index < 0) { currentElement = _q._array; return false; } currentElement = _q.GetElement(_index); _index++; if (_index == _q._size) _index = -1; return true; } public virtual Object Current { get { if (currentElement == _q._array) { if (_index == 0) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumNotStarted)); else throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumEnded)); } return currentElement; } } public virtual void Reset() { if (_version != _q._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion)); if (_q._size == 0) _index = -1; else _index = 0; currentElement = _q._array; } } internal class QueueDebugView { private Queue queue; public QueueDebugView( Queue queue) { if( queue == null) throw new ArgumentNullException("queue"); this.queue = queue; } [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] public Object[] Items { get { return queue.ToArray(); } } } } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007. // ==++== // // Copyright (c) Microsoft Corporation. All rights reserved. // // ==--== /*============================================================================== ** ** Class: Queue ** ** Purpose: A circular-array implementation of a queue. ** ** =============================================================================*/ namespace System.Collections { using System; using System.Security.Permissions; using System.Diagnostics; // A simple Queue of objects. Internally it is implemented as a circular // buffer, so Enqueue can be O(n). Dequeue is O(1). [DebuggerTypeProxy(typeof(System.Collections.Queue.QueueDebugView))] [DebuggerDisplay("Count = {Count}")] [System.Runtime.InteropServices.ComVisible(true)] [Serializable()] public class Queue : ICollection, ICloneable { private Object[] _array; private int _head; // First valid element in the queue private int _tail; // Last valid element in the queue private int _size; // Number of elements. private int _growFactor; // 100 == 1.0, 130 == 1.3, 200 == 2.0 private int _version; [NonSerialized] private Object _syncRoot; private const int _MinimumGrow = 4; private const int _ShrinkThreshold = 32; // Creates a queue with room for capacity objects. The default initial // capacity and grow factor are used. public Queue() : this(32, (float)2.0) { } // Creates a queue with room for capacity objects. The default grow factor // is used. // public Queue(int capacity) : this(capacity, (float)2.0) { } // Creates a queue with room for capacity objects. When full, the new // capacity is set to the old capacity * growFactor. // public Queue(int capacity, float growFactor) { if (capacity < 0) throw new ArgumentOutOfRangeException("capacity", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum")); if (!(growFactor >= 1.0 && growFactor <= 10.0)) throw new ArgumentOutOfRangeException("growFactor", Environment.GetResourceString("ArgumentOutOfRange_QueueGrowFactor", 1, 10)); _array = new Object[capacity]; _head = 0; _tail = 0; _size = 0; _growFactor = (int)(growFactor * 100); } // Fills a Queue with the elements of an ICollection. Uses the enumerator // to get each of the elements. // public Queue(ICollection col) : this((col==null ? 32 : col.Count)) { if (col==null) throw new ArgumentNullException("col"); IEnumerator en = col.GetEnumerator(); while(en.MoveNext()) Enqueue(en.Current); } public virtual int Count { get { return _size; } } public virtual Object Clone() { Queue q = new Queue(_size); q._size = _size; int numToCopy = _size; int firstPart = (_array.Length - _head < numToCopy) ? _array.Length - _head : numToCopy; Array.Copy(_array, _head, q._array, 0, firstPart); numToCopy -= firstPart; if (numToCopy > 0) Array.Copy(_array, 0, q._array, _array.Length - _head, numToCopy); q._version = _version; return q; } public virtual bool IsSynchronized { get { return false; } } public virtual Object SyncRoot { get { if( _syncRoot == null) { System.Threading.Interlocked.CompareExchange(ref _syncRoot, new Object(), null); } return _syncRoot; } } // Removes all Objects from the queue. public virtual void Clear() { if (_head < _tail) Array.Clear(_array, _head, _size); else { Array.Clear(_array, _head, _array.Length - _head); Array.Clear(_array, 0, _tail); } _head = 0; _tail = 0; _size = 0; _version++; } // CopyTo copies a collection into an Array, starting at a particular // index into the array. // public virtual void CopyTo(Array array, int index) { if (array==null) throw new ArgumentNullException("array"); if (array.Rank != 1) throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported")); if (index < 0) throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_Index")); int arrayLen = array.Length; if (arrayLen - index < _size) throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); int numToCopy = _size; if (numToCopy == 0) return; int firstPart = (_array.Length - _head < numToCopy) ? _array.Length - _head : numToCopy; Array.Copy(_array, _head, array, index, firstPart); numToCopy -= firstPart; if (numToCopy > 0) Array.Copy(_array, 0, array, index+_array.Length - _head, numToCopy); } // Adds obj to the tail of the queue. // public virtual void Enqueue(Object obj) { if (_size == _array.Length) { int newcapacity = (int)((long)_array.Length * (long)_growFactor / 100); if (newcapacity < _array.Length + _MinimumGrow) { newcapacity = _array.Length + _MinimumGrow; } SetCapacity(newcapacity); } _array[_tail] = obj; _tail = (_tail + 1) % _array.Length; _size++; _version++; } // GetEnumerator returns an IEnumerator over this Queue. This // Enumerator will support removing. // public virtual IEnumerator GetEnumerator() { return new QueueEnumerator(this); } // Removes the object at the head of the queue and returns it. If the queue // is empty, this method simply returns null. public virtual Object Dequeue() { if (_size == 0) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyQueue")); Object removed = _array[_head]; _array[_head] = null; _head = (_head + 1) % _array.Length; _size--; _version++; return removed; } // Returns the object at the head of the queue. The object remains in the // queue. If the queue is empty, this method throws an // InvalidOperationException. public virtual Object Peek() { if (_size == 0) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyQueue")); return _array[_head]; } // Returns a synchronized Queue. Returns a synchronized wrapper // class around the queue - the caller must not use references to the // original queue. // [HostProtection(Synchronization=true)] public static Queue Synchronized(Queue queue) { if (queue==null) throw new ArgumentNullException("queue"); return new SynchronizedQueue(queue); } // Returns true if the queue contains at least one object equal to obj. // Equality is determined using obj.Equals(). // // Exceptions: ArgumentNullException if obj == null. public virtual bool Contains(Object obj) { int index = _head; int count = _size; while (count-- > 0) { if (obj == null) { if (_array[index] == null) return true; } else if (_array[index] != null && _array[index].Equals(obj)) { return true; } index = (index + 1) % _array.Length; } return false; } internal Object GetElement(int i) { return _array[(_head + i) % _array.Length]; } // Iterates over the objects in the queue, returning an array of the // objects in the Queue, or an empty array if the queue is empty. // The order of elements in the array is first in to last in, the same // order produced by successive calls to Dequeue. public virtual Object[] ToArray() { Object[] arr = new Object[_size]; if (_size==0) return arr; if (_head < _tail) { Array.Copy(_array, _head, arr, 0, _size); } else { Array.Copy(_array, _head, arr, 0, _array.Length - _head); Array.Copy(_array, 0, arr, _array.Length - _head, _tail); } return arr; } // PRIVATE Grows or shrinks the buffer to hold capacity objects. Capacity // must be >= _size. private void SetCapacity(int capacity) { Object[] newarray = new Object[capacity]; if (_size > 0) { if (_head < _tail) { Array.Copy(_array, _head, newarray, 0, _size); } else { Array.Copy(_array, _head, newarray, 0, _array.Length - _head); Array.Copy(_array, 0, newarray, _array.Length - _head, _tail); } } _array = newarray; _head = 0; _tail = (_size == capacity) ? 0 : _size; _version++; } public virtual void TrimToSize() { SetCapacity(_size); } // Implements a synchronization wrapper around a queue. [Serializable()] private class SynchronizedQueue : Queue { private Queue _q; private Object root; internal SynchronizedQueue(Queue q) { this._q = q; root = _q.SyncRoot; } public override bool IsSynchronized { get { return true; } } public override Object SyncRoot { get { return root; } } public override int Count { get { lock (root) { return _q.Count; } } } public override void Clear() { lock (root) { _q.Clear(); } } public override Object Clone() { lock (root) { return new SynchronizedQueue((Queue)_q.Clone()); } } public override bool Contains(Object obj) { lock (root) { return _q.Contains(obj); } } public override void CopyTo(Array array, int arrayIndex) { lock (root) { _q.CopyTo(array, arrayIndex); } } public override void Enqueue(Object value) { lock (root) { _q.Enqueue(value); } } public override Object Dequeue() { lock (root) { return _q.Dequeue(); } } public override IEnumerator GetEnumerator() { lock (root) { return _q.GetEnumerator(); } } public override Object Peek() { lock (root) { return _q.Peek(); } } public override Object[] ToArray() { lock (root) { return _q.ToArray(); } } public override void TrimToSize() { lock (root) { _q.TrimToSize(); } } } // Implements an enumerator for a Queue. The enumerator uses the // internal version number of the list to ensure that no modifications are // made to the list while an enumeration is in progress. [Serializable()] private class QueueEnumerator : IEnumerator, ICloneable { private Queue _q; private int _index; private int _version; private Object currentElement; internal QueueEnumerator(Queue q) { _q = q; _version = _q._version; _index = 0; currentElement = _q._array; if (_q._size == 0) _index = -1; } public Object Clone() { return MemberwiseClone(); } public virtual bool MoveNext() { if (_version != _q._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion)); if (_index < 0) { currentElement = _q._array; return false; } currentElement = _q.GetElement(_index); _index++; if (_index == _q._size) _index = -1; return true; } public virtual Object Current { get { if (currentElement == _q._array) { if (_index == 0) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumNotStarted)); else throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumEnded)); } return currentElement; } } public virtual void Reset() { if (_version != _q._version) throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumFailedVersion)); if (_q._size == 0) _index = -1; else _index = 0; currentElement = _q._array; } } internal class QueueDebugView { private Queue queue; public QueueDebugView( Queue queue) { if( queue == null) throw new ArgumentNullException("queue"); this.queue = queue; } [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] public Object[] Items { get { return queue.ToArray(); } } } } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- LockedActivityGlyph.cs
- WebControlsSection.cs
- WeakEventManager.cs
- ProcessStartInfo.cs
- TextEndOfLine.cs
- URLIdentityPermission.cs
- DetailsViewRow.cs
- ImageListStreamer.cs
- ServiceNameElementCollection.cs
- BooleanAnimationBase.cs
- Visual.cs
- ProtocolsConfigurationEntry.cs
- externdll.cs
- EntityException.cs
- UserPreferenceChangingEventArgs.cs
- XmlSubtreeReader.cs
- ContentDisposition.cs
- ProfileManager.cs
- XPathAncestorIterator.cs
- TrimSurroundingWhitespaceAttribute.cs
- DeclarativeCatalogPart.cs
- FrameworkElementFactory.cs
- ObfuscationAttribute.cs
- ToolboxComponentsCreatingEventArgs.cs
- FileDialogPermission.cs
- XamlSerializer.cs
- SystemResources.cs
- SymbolDocumentInfo.cs
- PropertyChangeTracker.cs
- StylusDownEventArgs.cs
- WindowsClaimSet.cs
- XmlTextAttribute.cs
- serverconfig.cs
- SrgsItemList.cs
- ModuleBuilderData.cs
- XmlAttribute.cs
- StatusBar.cs
- WorkflowPersistenceContext.cs
- JsonWriter.cs
- QueueProcessor.cs
- FieldBuilder.cs
- WmpBitmapDecoder.cs
- DataGridViewComponentPropertyGridSite.cs
- ControlBindingsCollection.cs
- ExceptionHandlersDesigner.cs
- MenuTracker.cs
- OdbcCommand.cs
- TypedReference.cs
- BitmapEffectDrawingContextWalker.cs
- ToolStripItem.cs
- TextBoxAutomationPeer.cs
- EnumerableValidator.cs
- InlineCollection.cs
- SaveRecipientRequest.cs
- XmlAutoDetectWriter.cs
- XamlStyleSerializer.cs
- MarshalDirectiveException.cs
- TrackBarRenderer.cs
- Script.cs
- Trace.cs
- DashStyle.cs
- DtrList.cs
- CodeDOMUtility.cs
- SingleObjectCollection.cs
- DefaultPrintController.cs
- AutomationPattern.cs
- SecurityHelper.cs
- RotateTransform.cs
- SatelliteContractVersionAttribute.cs
- SoapInteropTypes.cs
- ContentTextAutomationPeer.cs
- DiscoveryViaBehavior.cs
- PeerContact.cs
- BStrWrapper.cs
- TextTreeTextNode.cs
- OpenFileDialog.cs
- TimeSpanValidator.cs
- ConnectionManagementSection.cs
- NumberSubstitution.cs
- IFlowDocumentViewer.cs
- DataGridViewHitTestInfo.cs
- UserValidatedEventArgs.cs
- XmlSchemaSimpleContent.cs
- NumericUpDownAccelerationCollection.cs
- Event.cs
- Int64Converter.cs
- DataGridCell.cs
- ConnectivityStatus.cs
- ConsumerConnectionPointCollection.cs
- AppDomainManager.cs
- SpellerStatusTable.cs
- TranslateTransform3D.cs
- StructureChangedEventArgs.cs
- ServerReliableChannelBinder.cs
- ManifestResourceInfo.cs
- WindowHideOrCloseTracker.cs
- PathNode.cs
- IgnoreSectionHandler.cs
- RegexNode.cs
- FlowDocumentScrollViewer.cs