Code:
/ Dotnetfx_Win7_3.5.1 / Dotnetfx_Win7_3.5.1 / 3.5.1 / DEVDIV / depot / DevDiv / releases / whidbey / NetFXspW7 / ndp / fx / src / CompMod / System / Collections / Generic / Queue.cs / 1 / Queue.cs
// ==++== // // Copyright (c) Microsoft Corporation. All rights reserved. // // ==--== /*============================================================================== ** ** Class: Queue ** ** Purpose: A circular-array implementation of a generic queue. ** ** Date: January 28, 2003 ** =============================================================================*/ namespace System.Collections.Generic { using System; using System.Security.Permissions; using System.Diagnostics; // A simple Queue of generic objects. Internally it is implemented as a // circular buffer, so Enqueue can be O(n). Dequeue is O(1). [DebuggerTypeProxy(typeof(System_QueueDebugView<>))] [DebuggerDisplay("Count = {Count}")] [Serializable()] [System.Runtime.InteropServices.ComVisible(false)] public class Queue: IEnumerable , System.Collections.ICollection { private T[] _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 _version; [NonSerialized] private Object _syncRoot; private const int _MinimumGrow = 4; private const int _ShrinkThreshold = 32; private const int _GrowFactor = 200; // double each time private const int _DefaultCapacity = 4; static T[] _emptyArray = new T[0]; // Creates a queue with room for capacity objects. The default initial // capacity and grow factor are used. /// public Queue() { _array = _emptyArray; } // Creates a queue with room for capacity objects. The default grow factor // is used. // /// public Queue(int capacity) { if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNumRequired); _array = new T[capacity]; _head = 0; _tail = 0; _size = 0; } // Fills a Queue with the elements of an ICollection. Uses the enumerator // to get each of the elements. // /// public Queue(IEnumerable collection) { if (collection == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection); _array = new T[_DefaultCapacity]; _size = 0; _version = 0; using(IEnumerator en = collection.GetEnumerator()) { while(en.MoveNext()) { Enqueue(en.Current); } } } /// public int Count { get { return _size; } } /// bool System.Collections.ICollection.IsSynchronized { get { return false; } } Object System.Collections.ICollection.SyncRoot { get { if( _syncRoot == null) { System.Threading.Interlocked.CompareExchange(ref _syncRoot, new Object(), null); } return _syncRoot; } } // Removes all Objects from the queue. /// public 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 void CopyTo(T[] array, int arrayIndex) { if (array==null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); } if (arrayIndex < 0 || arrayIndex > array.Length) { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.arrayIndex, ExceptionResource.ArgumentOutOfRange_Index); } int arrayLen = array.Length; if (arrayLen - arrayIndex < _size) { ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen); } int numToCopy = (arrayLen - arrayIndex < _size) ? (arrayLen - arrayIndex) : _size; if (numToCopy == 0) return; int firstPart = (_array.Length - _head < numToCopy) ? _array.Length - _head : numToCopy; Array.Copy(_array, _head, array, arrayIndex, firstPart); numToCopy -= firstPart; if (numToCopy > 0) { Array.Copy(_array, 0, array, arrayIndex+_array.Length - _head, numToCopy); } } void System.Collections.ICollection.CopyTo(Array array, int index) { if (array == null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); } if (array.Rank != 1) { ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported); } if( array.GetLowerBound(0) != 0 ) { ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound); } int arrayLen = array.Length; if (index < 0 || index > arrayLen) { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index); } if (arrayLen - index < _size) { ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen); } int numToCopy = (arrayLen-index < _size) ? arrayLen-index : _size; if (numToCopy == 0) return; try { 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); } } catch(ArrayTypeMismatchException) { ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); } } // Adds item to the tail of the queue. // /// public void Enqueue(T item) { 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] = item; _tail = (_tail + 1) % _array.Length; _size++; _version++; } // GetEnumerator returns an IEnumerator over this Queue. This // Enumerator will support removing. // /// public Enumerator GetEnumerator() { return new Enumerator(this); } /// /// IEnumerator IEnumerable .GetEnumerator() { return new Enumerator(this); } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return new Enumerator(this); } // Removes the object at the head of the queue and returns it. If the queue // is empty, this method simply returns null. /// public T Dequeue() { if (_size == 0) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue); T removed = _array[_head]; _array[_head] = default(T); _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 T Peek() { if (_size == 0) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue); return _array[_head]; } // Returns true if the queue contains at least one object equal to item. // Equality is determined using item.Equals(). // // Exceptions: ArgumentNullException if item == null. /// public bool Contains(T item) { int index = _head; int count = _size; EqualityComparer c = EqualityComparer .Default; while (count-- > 0) { if (((Object) item) == null) { if (((Object) _array[index]) == null) return true; } else if (_array[index] != null && c.Equals(_array[index], item)) { return true; } index = (index + 1) % _array.Length; } return false; } internal T 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 T[] ToArray() { T[] arr = new T[_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) { T[] newarray = new T[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 void TrimExcess() { int threshold = (int)(((double)_array.Length) * 0.9); if( _size < threshold ) { SetCapacity(_size); } } // 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()] public struct Enumerator : IEnumerator , System.Collections.IEnumerator { private Queue _q; private int _index; // -1 = not started, -2 = ended/disposed private int _version; private T _currentElement; internal Enumerator(Queue q) { _q = q; _version = _q._version; _index = -1; _currentElement = default(T); } /// public void Dispose() { _index = -2; _currentElement = default(T); } /// public bool MoveNext() { if (_version != _q._version) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); if (_index == -2) return false; _index++; if (_index == _q._size) { _index = -2; _currentElement = default(T); return false; } _currentElement = _q.GetElement(_index); return true; } /// public T Current { get { if (_index < 0) { if (_index == -1) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted); else ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded); } return _currentElement; } } Object System.Collections.IEnumerator.Current { get { if (_index < 0) { if (_index == -1) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted); else ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded); } return _currentElement; } } void System.Collections.IEnumerator.Reset() { if (_version != _q._version) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); _index = -1; _currentElement = default(T); } } } } // 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 generic queue. ** ** Date: January 28, 2003 ** =============================================================================*/ namespace System.Collections.Generic { using System; using System.Security.Permissions; using System.Diagnostics; // A simple Queue of generic objects. Internally it is implemented as a // circular buffer, so Enqueue can be O(n). Dequeue is O(1). [DebuggerTypeProxy(typeof(System_QueueDebugView<>))] [DebuggerDisplay("Count = {Count}")] [Serializable()] [System.Runtime.InteropServices.ComVisible(false)] public class Queue : IEnumerable , System.Collections.ICollection { private T[] _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 _version; [NonSerialized] private Object _syncRoot; private const int _MinimumGrow = 4; private const int _ShrinkThreshold = 32; private const int _GrowFactor = 200; // double each time private const int _DefaultCapacity = 4; static T[] _emptyArray = new T[0]; // Creates a queue with room for capacity objects. The default initial // capacity and grow factor are used. /// public Queue() { _array = _emptyArray; } // Creates a queue with room for capacity objects. The default grow factor // is used. // /// public Queue(int capacity) { if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNumRequired); _array = new T[capacity]; _head = 0; _tail = 0; _size = 0; } // Fills a Queue with the elements of an ICollection. Uses the enumerator // to get each of the elements. // /// public Queue(IEnumerable collection) { if (collection == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection); _array = new T[_DefaultCapacity]; _size = 0; _version = 0; using(IEnumerator en = collection.GetEnumerator()) { while(en.MoveNext()) { Enqueue(en.Current); } } } /// public int Count { get { return _size; } } /// bool System.Collections.ICollection.IsSynchronized { get { return false; } } Object System.Collections.ICollection.SyncRoot { get { if( _syncRoot == null) { System.Threading.Interlocked.CompareExchange(ref _syncRoot, new Object(), null); } return _syncRoot; } } // Removes all Objects from the queue. /// public 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 void CopyTo(T[] array, int arrayIndex) { if (array==null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); } if (arrayIndex < 0 || arrayIndex > array.Length) { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.arrayIndex, ExceptionResource.ArgumentOutOfRange_Index); } int arrayLen = array.Length; if (arrayLen - arrayIndex < _size) { ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen); } int numToCopy = (arrayLen - arrayIndex < _size) ? (arrayLen - arrayIndex) : _size; if (numToCopy == 0) return; int firstPart = (_array.Length - _head < numToCopy) ? _array.Length - _head : numToCopy; Array.Copy(_array, _head, array, arrayIndex, firstPart); numToCopy -= firstPart; if (numToCopy > 0) { Array.Copy(_array, 0, array, arrayIndex+_array.Length - _head, numToCopy); } } void System.Collections.ICollection.CopyTo(Array array, int index) { if (array == null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); } if (array.Rank != 1) { ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported); } if( array.GetLowerBound(0) != 0 ) { ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound); } int arrayLen = array.Length; if (index < 0 || index > arrayLen) { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index); } if (arrayLen - index < _size) { ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen); } int numToCopy = (arrayLen-index < _size) ? arrayLen-index : _size; if (numToCopy == 0) return; try { 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); } } catch(ArrayTypeMismatchException) { ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); } } // Adds item to the tail of the queue. // /// public void Enqueue(T item) { 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] = item; _tail = (_tail + 1) % _array.Length; _size++; _version++; } // GetEnumerator returns an IEnumerator over this Queue. This // Enumerator will support removing. // /// public Enumerator GetEnumerator() { return new Enumerator(this); } /// /// IEnumerator IEnumerable .GetEnumerator() { return new Enumerator(this); } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return new Enumerator(this); } // Removes the object at the head of the queue and returns it. If the queue // is empty, this method simply returns null. /// public T Dequeue() { if (_size == 0) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue); T removed = _array[_head]; _array[_head] = default(T); _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 T Peek() { if (_size == 0) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue); return _array[_head]; } // Returns true if the queue contains at least one object equal to item. // Equality is determined using item.Equals(). // // Exceptions: ArgumentNullException if item == null. /// public bool Contains(T item) { int index = _head; int count = _size; EqualityComparer c = EqualityComparer .Default; while (count-- > 0) { if (((Object) item) == null) { if (((Object) _array[index]) == null) return true; } else if (_array[index] != null && c.Equals(_array[index], item)) { return true; } index = (index + 1) % _array.Length; } return false; } internal T 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 T[] ToArray() { T[] arr = new T[_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) { T[] newarray = new T[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 void TrimExcess() { int threshold = (int)(((double)_array.Length) * 0.9); if( _size < threshold ) { SetCapacity(_size); } } // 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()] public struct Enumerator : IEnumerator , System.Collections.IEnumerator { private Queue _q; private int _index; // -1 = not started, -2 = ended/disposed private int _version; private T _currentElement; internal Enumerator(Queue q) { _q = q; _version = _q._version; _index = -1; _currentElement = default(T); } /// public void Dispose() { _index = -2; _currentElement = default(T); } /// public bool MoveNext() { if (_version != _q._version) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); if (_index == -2) return false; _index++; if (_index == _q._size) { _index = -2; _currentElement = default(T); return false; } _currentElement = _q.GetElement(_index); return true; } /// public T Current { get { if (_index < 0) { if (_index == -1) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted); else ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded); } return _currentElement; } } Object System.Collections.IEnumerator.Current { get { if (_index < 0) { if (_index == -1) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted); else ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded); } return _currentElement; } } void System.Collections.IEnumerator.Reset() { if (_version != _q._version) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); _index = -1; _currentElement = default(T); } } } } // 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
- QueryOpeningEnumerator.cs
- WebFormsRootDesigner.cs
- CalendarData.cs
- XMLDiffLoader.cs
- XPathNodeInfoAtom.cs
- ReferencedAssemblyResolver.cs
- XmlSchemaSearchPattern.cs
- XmlILAnnotation.cs
- ADRoleFactoryConfiguration.cs
- DynamicScriptObject.cs
- SchemaImporter.cs
- GenerateTemporaryAssemblyTask.cs
- ComNativeDescriptor.cs
- BitStream.cs
- RuntimeConfigurationRecord.cs
- CapabilitiesAssignment.cs
- StateManagedCollection.cs
- XomlCompilerError.cs
- SoapTypeAttribute.cs
- ItemContainerProviderWrapper.cs
- OrderingExpression.cs
- DbConnectionPoolOptions.cs
- SubpageParagraph.cs
- Popup.cs
- FormClosingEvent.cs
- GenericWebPart.cs
- ListDesigner.cs
- WebException.cs
- AttributeSetAction.cs
- ToolboxItemFilterAttribute.cs
- DataContractSerializerSection.cs
- CaretElement.cs
- RightsManagementInformation.cs
- DynamicResourceExtensionConverter.cs
- TextRangeBase.cs
- TagMapCollection.cs
- ElementHostPropertyMap.cs
- FunctionParameter.cs
- XmlAttributeAttribute.cs
- RegistryDataKey.cs
- FullTextBreakpoint.cs
- DispatchWrapper.cs
- LinqExpressionNormalizer.cs
- GeneratedCodeAttribute.cs
- TraceAsyncResult.cs
- CodeRemoveEventStatement.cs
- MetadataArtifactLoaderCompositeFile.cs
- WebPartAddingEventArgs.cs
- ValueChangedEventManager.cs
- ObjectStateEntryDbDataRecord.cs
- EdmConstants.cs
- SoapMessage.cs
- SignedXml.cs
- BaseDataList.cs
- RequestCachePolicyConverter.cs
- XmlSubtreeReader.cs
- FormViewPageEventArgs.cs
- ILGenerator.cs
- WebAdminConfigurationHelper.cs
- RemoteWebConfigurationHostStream.cs
- X509Certificate.cs
- WorkerRequest.cs
- BindingBase.cs
- AlgoModule.cs
- Pair.cs
- DataGridTextBoxColumn.cs
- ExpressionList.cs
- ServiceOperationWrapper.cs
- DataGridViewCellStyleContentChangedEventArgs.cs
- DataGridViewImageColumn.cs
- DiscoveryEndpoint.cs
- HtmlShimManager.cs
- NullEntityWrapper.cs
- EdmProviderManifest.cs
- MaterializeFromAtom.cs
- ComponentCache.cs
- TextMarkerSource.cs
- __ConsoleStream.cs
- GlyphElement.cs
- ThreadStartException.cs
- RegexTree.cs
- ObjectContextServiceProvider.cs
- CTreeGenerator.cs
- LazyTextWriterCreator.cs
- EncryptedKey.cs
- VectorAnimationUsingKeyFrames.cs
- SchemaAttDef.cs
- PrimitiveDataContract.cs
- SerializationSectionGroup.cs
- WebPartConnectionsConfigureVerb.cs
- OracleParameterBinding.cs
- DSASignatureDeformatter.cs
- OptimalTextSource.cs
- FilterFactory.cs
- WindowsScroll.cs
- SqlEnums.cs
- XPathCompileException.cs
- BufferAllocator.cs
- DocumentViewer.cs
- X509Chain.cs