{"action":"created","issue":{"url":"https://api.github.com/repos/dotnet/corefx/issues/574","labels_url":"https://api.github.com/repos/dotnet/corefx/issues/574/labels{/name}","comments_url":"https://api.github.com/repos/dotnet/corefx/issues/574/comments","events_url":"https://api.github.com/repos/dotnet/corefx/issues/574/events","html_url":"https://github.com/dotnet/corefx/issues/574","id":56088839,"number":574,"title":"The core generic collection types should include a priority queue","user":{"login":"ebickle","id":2086875,"avatar_url":"https://avatars.githubusercontent.com/u/2086875?v=3","gravatar_id":"","url":"https://api.github.com/users/ebickle","html_url":"https://github.com/ebickle","followers_url":"https://api.github.com/users/ebickle/followers","following_url":"https://api.github.com/users/ebickle/following{/other_user}","gists_url":"https://api.github.com/users/ebickle/gists{/gist_id}","starred_url":"https://api.github.com/users/ebickle/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ebickle/subscriptions","organizations_url":"https://api.github.com/users/ebickle/orgs","repos_url":"https://api.github.com/users/ebickle/repos","events_url":"https://api.github.com/users/ebickle/events{/privacy}","received_events_url":"https://api.github.com/users/ebickle/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/dotnet/corefx/labels/api%20addition","name":"api addition","color":"207de5"}],"state":"open","locked":false,"assignee":{"login":"terrajobst","id":5169960,"avatar_url":"https://avatars.githubusercontent.com/u/5169960?v=3","gravatar_id":"","url":"https://api.github.com/users/terrajobst","html_url":"https://github.com/terrajobst","followers_url":"https://api.github.com/users/terrajobst/followers","following_url":"https://api.github.com/users/terrajobst/following{/other_user}","gists_url":"https://api.github.com/users/terrajobst/gists{/gist_id}","starred_url":"https://api.github.com/users/terrajobst/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/terrajobst/subscriptions","organizations_url":"https://api.github.com/users/terrajobst/orgs","repos_url":"https://api.github.com/users/terrajobst/repos","events_url":"https://api.github.com/users/terrajobst/events{/privacy}","received_events_url":"https://api.github.com/users/terrajobst/received_events","type":"User","site_admin":false},"milestone":null,"comments":20,"created_at":"2015-01-30T21:46:20Z","updated_at":"2015-05-10T14:46:30Z","closed_at":null,"body":"Issue https://github.com/dotnet/corefx/issues/163 requested the addition of a priority queue to the core .NET collection data structures.\r\n\r\nThis post, while a duplicate, is intended to act the formal submission to the corefx API Review Process. The issue contents are the *speclet* for a new System.Collections.Generic.PriorityQueue<T> type.\r\n\r\nI will be contributing the PR, if approved.\r\n\r\n## Rationale and Usage\r\n\r\nThe .NET Base Class Libraries (BCL) currently lacks support for ordered producer-consumer collections. A common requirement of many software applications is the ability generate a list of items over time and process them in an order different from the order they were received in.\r\n\r\nThere are three generic data structures within the System.Collections hierarchy of namespaces that supported a sorted collection of items; System.Collections.Generic.SortedList, System.Collections.Generic.SortedSet, and System.Collections.Generic.SortedDictionary.\r\n\r\nOf these, SortedSet and SortedDictionary are not appropriate for producer-consumer patterns that generate duplicate values. The complexity of SortedList is Θ(n) worst case for both Add and Remove.\r\n\r\nA much more memory and time efficient data structure for ordered collections with producer-consumer usage patterns is a priority queue. Other than when capacity resizing is necessary, worse case insertion (enqueue) and remove top (dequeue) performance is Θ(log n) - far better than the existing options that exist in the BCL.\r\n\r\nPriority queues have a wide degree of applicability across different classes of applications. The Wikipedia page on Priority Queues offers a list of many different well understand use cases. While highly specialized implementations may still require custom priority queue implementations, a standard implementation would cover a broad range of usage scenarios. Priority queues are particularly useful in scheduling the output of multiple producers, which is an important pattern in highly parallelized software.\r\n\r\nIt's worth noting that both the C++ standard library and Java offer priority queue functionality as part of their basic APIs.\r\n\r\n## Proposed API\r\n\r\n~~~C#\r\nnamespace System.Collections.Generic\r\n{\r\n    /// <summary>\r\n    /// Represents a collection of objects that are removed in a sorted order.\r\n    /// </summary>\r\n    /// <typeparam name=\"T\">Specifies the type of elements in the queue.</typeparam>    \r\n    [DebuggerDisplay(\"Count = {count}\")]\r\n    [DebuggerTypeProxy(typeof(System_PriorityQueueDebugView<>))]\r\n    public class PriorityQueue<T> : IEnumerable<T>, ICollection, IEnumerable\r\n    {\r\n        /// <summary>\r\n        /// Initializes a new instance of the <see cref=\"PriorityQueue{T}\"/> class \r\n        /// that uses a default comparer.\r\n        /// </summary>\r\n        public PriorityQueue();\r\n\r\n        /// <summary>\r\n        /// Initializes a new instance of the <see cref=\"PriorityQueue{T}\"/> class \r\n        /// that has the specified initial capacity.\r\n        /// </summary>\r\n        /// <param name=\"capacity\">The initial number of elements that the <see cref=\"PriorityQueue{T}\"/> can contain.</param>\r\n        /// <exception cref=\"T:System.ArgumentOutOfRangeException\"><paramref name=\"capacity\"/> is less than zero.</exception>\r\n        public PriorityQueue(int capacity);\r\n\r\n        /// <summary>\r\n        /// Initializes a new instance of the <see cref=\"PriorityQueue{T}\"/> class \r\n        /// that uses a specified comparer.\r\n        /// </summary>\r\n        /// <param name=\"comparer\">The <see cref=\"T:System.Collections.Generic.IComparer{T}\"/> to use when comparing elements.</param>\r\n        /// <exception cref=\"T:System.ArgumentNullException\"><paramref name=\"comparer\"/> is null.</exception>\r\n        public PriorityQueue(IComparer<T> comparer);\r\n\r\n        /// <summary>\r\n        /// Initializes a new instance of the <see cref=\"PriorityQueue{T}\"/> class \r\n        /// that contains elements copied from the specified collection and uses a default comparer.\r\n        /// </summary>\r\n        /// <param name=\"collection\">The collection whose elements are copied to the new <see cref=\"PriorityQueue{T}\"/>.</param>\r\n        /// <exception cref=\"T:System.ArgumentNullException\"><paramref name=\"collection\"/> is null.</exception>\r\n        public PriorityQueue(IEnumerable<T> collection);\r\n\r\n        /// <summary>\r\n        /// Initializes a new instance of the <see cref=\"PriorityQueue{T}\"/> class \r\n        /// that contains elements copied from the specified collection and uses a specified comparer.\r\n        /// </summary>\r\n        /// <param name=\"collection\">The collection whose elements are copied to the new <see cref=\"PriorityQueue{T}\"/>.</param>\r\n        /// <param name=\"comparer\">The <see cref=\"T:System.Collections.Generic.IComparer{T}\"/> to use when comparing elements.</param>\r\n        /// <exception cref=\"T:System.ArgumentNullException\">\r\n        /// <paramref name=\"collection\"/> is null. -or-\r\n        /// <paramref name=\"comparer\"/> is null.\r\n        /// </exception>\r\n        public PriorityQueue(IEnumerable<T> collection, IComparer<T> comparer);\r\n\r\n        /// <summary>\r\n        /// Initializes a new instance of the <see cref=\"PriorityQueue{T}\"/> class that is empty,\r\n        /// has the specified initial capacity, and uses a specified comparer.\r\n        /// </summary>\r\n        /// <param name=\"capacity\">The initial number of elements that the <see cref=\"PriorityQueue{T}\"/> can contain.</param>\r\n        /// <param name=\"comparer\">The <see cref=\"T:System.Collections.Generic.IComparer{T}\"/> to use when comparing elements.</param>\r\n        /// <exception cref=\"T:System.ArgumentOutOfRangeException\"><paramref name=\"capacity\"/> is less than zero.</exception>\r\n        /// <exception cref=\"T:System.ArgumentNullException\"><paramref name=\"comparer\"/> is null.</exception>\r\n        public PriorityQueue(int capacity, IComparer<T> comparer);\r\n\r\n        /// <summary>\r\n        /// Gets the <see cref=\"IComparer{T}\"/> for the <see cref=\"PriorityQueue{T}\"/>. \r\n        /// </summary>\r\n        /// <value>\r\n        /// The <see cref=\"T:System.Collections.Generic.IComparer{T}\"/> that is used when\r\n        /// comparing elements in the <see cref=\"PriorityQueue{T}\"/>. \r\n        /// </value>\r\n        public IComparer<T> Comparer \r\n        { \r\n            get;\r\n        }\r\n\r\n        /// <summary>\r\n        /// Gets the number of elements contained in the <see cref=\"PriorityQueue{T}\"/>.\r\n        /// </summary>\r\n        /// <value>The number of elements contained in the <see cref=\"PriorityQueue{T}\"/>.</value>\r\n        public int Count \r\n        { \r\n            get;\r\n        }\r\n\r\n        /// <summary>\r\n        /// Adds an object to the end of the <see cref=\"PriorityQueue{T}\"/>.\r\n        /// </summary>\r\n        /// <param name=\"item\">\r\n        /// The object to add to the end of the <see cref=\"PriorityQueue{T}\"/>. \r\n        /// The value can be null for reference types.\r\n        /// </param>\r\n        public void Enqueue(T item);\r\n\r\n        /// <summary>\r\n        /// Removes and returns the object with the lowest priority in the <see cref=\"PriorityQueue{T}\"/>.\r\n        /// </summary>\r\n        /// <returns>The object with the lowest priority that is removed from the <see cref=\"PriorityQueue{T}\"/>.</returns>\r\n        /// <exception cref=\"InvalidOperationException\">The <see cref=\"PriorityQueue{T}\"/> is empty.</exception>\r\n        public T Dequeue();\r\n\r\n        /// <summary>\r\n        /// Returns the object with the lowest priority in the <see cref=\"PriorityQueue{T}\"/>.\r\n        /// </summary>\r\n        /// <exception cref=\"InvalidOperationException\">The <see cref=\"PriorityQueue{T}\"/> is empty.</exception>\r\n        public T Peek();\r\n\r\n        /// <summary>\r\n        /// Removes all elements from the <see cref=\"PriorityQueue{T}\"/>.\r\n        /// </summary>\r\n        public void Clear();\r\n\r\n        /// <summary>\r\n        /// Determines whether an element is in the <see cref=\"PriorityQueue{T}\"/>.\r\n        /// </summary>\r\n        /// <param name=\"item\">\r\n        /// The object to add to the end of the <see cref=\"PriorityQueue{T}\"/>. \r\n        /// The value can be null for reference types.\r\n        /// </param>\r\n        /// <returns>\r\n        /// true if item is found in the <see cref=\"PriorityQueue{T}\"/>;  otherwise, false.\r\n        /// </returns>\r\n        public bool Contains(T item);\r\n\r\n        /// <summary>\r\n        /// Copies the elements of the <see cref=\"PriorityQueue{T}\"/> to an  <see cref=\"T:System.Array\"/>, \r\n        /// starting at a particular <see cref=\"T:System.Array\"/> index.\r\n        /// </summary>\r\n        /// <param name=\"array\">\r\n        /// The one-dimensional <see cref=\"T:System.Array\">Array</see> that is the\r\n        /// destination of the elements copied from the <see cref=\"PriorityQueue{T}\"/>. \r\n        /// The <see cref=\"T:System.Array\">Array</see> must have zero-based indexing.\r\n        /// </param>\r\n        /// <param name=\"arrayIndex\">The zero-based index in <paramref name=\"array\"/> at which copying begins.</param>\r\n        /// <exception cref=\"T:System.ArgumentNullException\"><paramref name=\"array\"/> is null.</exception>\r\n        /// <exception cref=\"T:System.ArgumentOutOfRangeException\">\r\n        /// <paramref name=\"arrayIndex\"/> is less than zero. -or- \r\n        /// <paramref name=\"arrayIndex\"/> is equal to or greater than the length of the <paramref name=\"array\"/>\r\n        /// </exception>\r\n        /// <exception cref=\"ArgumentException\">\r\n        /// The number of elements in the source <see cref=\"T:System.Collections.ICollection\"/> is\r\n        /// greater than the available space from <paramref name=\"index\"/> to the end of the destination\r\n        /// <paramref name=\"array\"/>.\r\n        /// </exception>\r\n        public void CopyTo(T[] array, int arrayIndex);\r\n\r\n        /// <summary>\r\n        /// Copies the elements of the <see cref=\"T:System.Collections.ICollection\"/> to an \r\n        /// <see cref=\"T:System.Array\"/>, starting at a particular <see cref=\"T:System.Array\"/> index.\r\n        /// </summary>\r\n        /// <param name=\"array\">\r\n        /// The one-dimensional <see cref=\"T:System.Array\">Array</see> that is the\r\n        /// destination of the elements copied from the <see cref=\"PriorityQueue{T}\"/>. \r\n        /// The <see cref=\"T:System.Array\">Array</see> must have zero-based indexing.\r\n        /// </param>\r\n        /// <param name=\"index\">The zero-based index in <paramref name=\"array\"/> at which copying begins.</param>\r\n        /// <exception cref=\"T:System.ArgumentNullException\"><paramref name=\"array\"/> is null.</exception>\r\n        /// <exception cref=\"T:System.ArgumentOutOfRangeException\"><paramref name=\"index\"/> is less than zero.</exception>\r\n        /// <exception cref=\"ArgumentException\">\r\n        /// <paramref name=\"array\"/> is multidimensional. -or-\r\n        /// <paramref name=\"array\"/> does not have zero-based indexing. -or-\r\n        /// <paramref name=\"index\"/> is equal to or greater than the length of the <paramref name=\"array\"/> -or- \r\n        /// The number of elements in the source <see cref=\"T:System.Collections.ICollection\"/> is\r\n        /// greater than the available space from <paramref name=\"index\"/> to the end of the destination\r\n        /// <paramref name=\"array\"/>. -or- \r\n        /// The type of the source <see cref=\"T:System.Collections.ICollection\"/> cannot be cast automatically \r\n        /// to the type of the destination <paramref name=\"array\"/>.\r\n        /// </exception>\r\n        void ICollection.CopyTo(Array array, int index);\r\n\r\n        /// <summary>\r\n        /// Copies the elements stored in the <see cref=\"PriorityQueue{T}\"/> to a new array.\r\n        /// </summary>\r\n        /// <returns>\r\n        /// A new array containing a snapshot of elements copied from the <see cref=\"PriorityQueue{T}\"/>.\r\n        /// </returns>\r\n        public T[] ToArray();\r\n\r\n        /// <summary>\r\n        /// Returns an enumerator that iterates through the <see cref=\"PriorityQueue{T}\"/>\r\n        /// </summary>\r\n        /// <returns>An enumerator for the contents of the <see cref=\"PriorityQueue{T}\"/>.</returns>\r\n        public Enumerator GetEnumerator();\r\n\r\n        /// <summary>\r\n        /// Returns an enumerator that iterates through the <see cref=\"PriorityQueue{T}\"/>\r\n        /// </summary>\r\n        /// <returns>An enumerator for the contents of the <see cref=\"PriorityQueue{T}\"/>.</returns>\r\n        IEnumerator<T> IEnumerable<T>.GetEnumerator();\r\n\r\n        /// <summary>\r\n        /// Returns an enumerator that iterates through the <see cref=\"PriorityQueue{T}\"/>.\r\n        /// </summary>\r\n        /// <returns>An <see cref=\"T:System.Collections.IEnumerator\"/> that can be used to iterate through the collection.</returns>\r\n        IEnumerator IEnumerable.GetEnumerator();\r\n\r\n        /// <summary>\r\n        /// Sets the capacity to the actual number of elements in the <see cref=\"PriorityQueue{T}\"/>, \r\n        /// if that number is less than than a threshold value.\r\n        /// </summary>\r\n        public void TrimExcess();\r\n\r\n        /// <summary>\r\n        /// Gets a value that indicates whether access to the <see cref=\"ICollection\"/> is \r\n        /// synchronized with the SyncRoot.\r\n        /// </summary>\r\n        /// <value>true if access to the <see cref=\"T:System.Collections.ICollection\"/> is synchronized\r\n        /// with the SyncRoot; otherwise, false. For <see cref=\"PriorityQueue{T}\"/>, this property always\r\n        /// returns false.</value>\r\n        bool ICollection.IsSynchronized\r\n        {\r\n            get;\r\n        }\r\n\r\n        /// <summary>\r\n        /// Gets an object that can be used to synchronize access to the \r\n        /// <see cref=\"T:System.Collections.ICollection\"/>.\r\n        /// </summary>\r\n        /// <value>\r\n        /// An object that can be used to synchronize access to the \r\n        /// <see cref=\"T:System.Collections.ICollection\"/>.\r\n        /// </value>\r\n        object ICollection.SyncRoot\r\n        {\r\n            get;\r\n        }\r\n\r\n        public struct Enumerator : IEnumerator<T>\r\n        {\r\n            public T Current { get; }\r\n            object IEnumerator.Current { get; }\r\n            public bool MoveNext();\r\n            public void Reset();\r\n            public void Dispose();\r\n        }\r\n    }\r\n}\r\n~~~\r\n\r\n## Details\r\n* Implementation data structure will be a binary heap. Items with a greater comparison value will be returned first. (descending order)\r\n\r\n* Time complexities:\r\n\r\n| Operation | Complexity | Notes |\r\n| ------------- | ------------- | ------- |\r\n| Construct | Θ(1) | \r\n| Construct Using IEnumerable | Θ(n) |\r\n| Enqueue | Θ(log n) |\r\n| Dequeue | Θ(log n) |\r\n| Peek | Θ(1) |\r\n| Count | Θ(1) |\r\n| Clear | Θ(N) |\r\n| Contains | Θ(N) |\r\n| CopyTo | Θ(N) | Uses Array.Copy, actual complexity may be lower |\r\n| ToArray | Θ(N) | Uses Array.Copy, actual complexity may be lower |\r\n| GetEnumerator | Θ(1) |\r\n| Enumerator.MoveNext | Θ(1) |\r\n\r\n* Additional constructor overloads that take the System.Comparison<T> delegate were intentionally omitted in favor of a simplified API surface area. Callers can use Comparer<T>.Create to convert a function or Lambda expression to an IComparer<T> interface if necessary. This does require the caller to incur a one-time heap allocation.\r\n\r\n* Although System.Collections.Generic is not yet part of corefx, I propose that this class be added to corefxlab in the meantime. It can be moved to the primary corefx repository once System.Collections.Generic are added and there is consensus that its status should be elevated from experimental to an official API.\r\n\r\n* An IsEmpty property was not included, since there is no additional performance penalty calling Count. The majority of the collection data structures do not include IsEmpty.\r\n\r\n* The IsSynchronized and SyncRoot properties of ICollection were implemented explicitly as they are effectively obsolete. This also follows the pattern used for the other System.Collection.Generic data structures.\r\n\r\n* Dequeue and Peek throw an InvalidOperationException when the queue is empty to match the established behavior of System.Collections.Queue<T>.\r\n\r\n* IProducerConsumerCollection<T> was not implemented as its documentation states that it is only intended for thread-safe collections.\r\n\r\n## Open Questions\r\n* Is avoiding an additional heap allocation during calls to GetEnumerator when using foreach a strong enough rationale for including the nested public enumerator structure? \r\n\r\n* Should CopyTo, ToArray, and GetEnumerator return results in prioritized (sorted) order, or the internal order used by the data structure? My assumption is that the internal order should be returned, as it doesn't incur any additional performance penalties. However, this is a potential usability issue if a developer thinks of the class as a \"sorted queue\" rather a priority queue.\r\n\r\n* Does adding a type named PriorityQueue to System.Collections.Generic cause a potentially breaking change? The namespace is heavily used, and could cause a source compatibility problem for projects that include their own priority queue type.\r\n\r\n* Should items be dequeued in ascending or descending order, based on the output of IComparer<T>? (my assumption is ascending order, to match the normal sorting convention of IComparer<T>).\r\n\r\n* Should the collection be 'stable'? In other words, should two items with equal IComparison<T> results be dequeued in the exact same order they are enqueued in? (my assumption is this isn't needed)\r\n\r\n## Updates\r\n\r\n* Fixed complexity of 'Construct Using IEnumerable' to Θ(n). Thanks @svick.\r\n\r\n* Added another option question regarding whether the priority queue should be ordered in ascending or descending order compared to the IComparer<T>.\r\n\r\n* Removed NotSupportedException from explicit SyncRoot property to match behavior of other System.Collection.Generic types instead of using the newer pattern.\r\n\r\n* Made the public GetEnumerator method return a nested Enumerator struct instead of IEnumerable<T>, similar to the existing System.Collections.Generic types. This is an optimization to avoid a heap (GC) allocation when using a foreach loop.\r\n\r\n* Removed ComVisible attribute.\r\n\r\n* Changed complexity of Clear to Θ(n). Thanks @mbeidler.\r\n"},"comment":{"url":"https://api.github.com/repos/dotnet/corefx/issues/comments/100651678","html_url":"https://github.com/dotnet/corefx/issues/574#issuecomment-100651678","issue_url":"https://api.github.com/repos/dotnet/corefx/issues/574","id":100651678,"user":{"login":"ebickle","id":2086875,"avatar_url":"https://avatars.githubusercontent.com/u/2086875?v=3","gravatar_id":"","url":"https://api.github.com/users/ebickle","html_url":"https://github.com/ebickle","followers_url":"https://api.github.com/users/ebickle/followers","following_url":"https://api.github.com/users/ebickle/following{/other_user}","gists_url":"https://api.github.com/users/ebickle/gists{/gist_id}","starred_url":"https://api.github.com/users/ebickle/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ebickle/subscriptions","organizations_url":"https://api.github.com/users/ebickle/orgs","repos_url":"https://api.github.com/users/ebickle/repos","events_url":"https://api.github.com/users/ebickle/events{/privacy}","received_events_url":"https://api.github.com/users/ebickle/received_events","type":"User","site_admin":false},"created_at":"2015-05-10T14:46:30Z","updated_at":"2015-05-10T14:46:30Z","body":"@terrajobst How do you feel about the API proposal so far? Do you feel this a good fit for CoreFX?"}}