Get rid of Collection conformance or implement it differently

[vale-cocoa]

Added test showing that Collection conformance doesn't match the Sequ…ence conformance: when iterating elements via iterator the PriorityQueue uses the pop() method, effectively returning the elements in order. On the other hand if one iterates via indexes subscription, the elements are returned in the same order as they are stored in the underlaying storage, which doesn't necessarily matches the order in which elements are popped via the pop() method.

Fix: get rid of Collection conformance, otherwise implement a different Index type which takes into account how the effective order elements are popped out from the storage (most likely subscripting or creation of indexes won't be an O(1) operation).

[davecom]

Thanks. Yeah I should probably of never added Collection conformance. It doesn’t really make sense in retrospect. The issue is, what if someone is relying on it now? This project is 6 years old and has found its way into quite a few codebases and this could be considered a pretty major breaking change.

[vale-cocoa]

A solution could be in trading speed for accuracy, hence having the Collection subscript retrieve elements via the enumerated() method. This will make the subscript O(log n) operation rather than O(1); moreover iterating via the indexes, would be an O(n log n) operation.

[davecom]

I could be wrong, but wouldn't this mean that when you do a subscript, you are popping all of the elements before the index of the element you subscripted to? Because our implementation of next() is a pop():

mutating public func next() -> Element? { return pop() }

This could lead to some unintended consequences when calling the other Collection APIs.

[vale-cocoa]

I could be wrong, but wouldn't this mean that when you do a subscript, you are popping all of the elements before the index of the element you subscripted to? Because our implementation of next() is a pop():

mutating public func next() -> Element? { return pop() }

This could lead to some unintended consequences when calling the other Collection APIs.

Please check the unit test I've just added: testIteratingViaIndexesValueSemantics() It won't because of value semantics (the heap is a Swift Array). Otherwise you'd had this same problem by simply doing a fast iteration, and that would happen on your original version either. But again, this workaround is not really a desirable solution as we both agreed on due to the O(n) complexity of this subscript.