Collection index complexity and data structures


(David Waite) #1

I noticed that the new Collection index(_:offsetBy:) <http://swiftdoc.org/v3.0/protocol/Collection/#comment-func-index_offsetby_> does not define that negative offsets require a BidirectionalCollection. It also declares that negative offsets must complete in O( | offset | ) time. This differs from other methods such as distance(from:to:) <http://swiftdoc.org/v3.0/protocol/Collection/#comment-func-distance-from_to_>which indicates start <= end if not a BidirectionalCollection

This would preclude some data structures from strictly implementing the Collection protocol, such as singly-linked lists.

Would it be appropriate to indicate instead that BidirectionalCollection defines the negative offset behavior and negative offset performance constraint?

-DW


(David Waite) #2

And never mind me. Not sure how I missed that in the docs that many times.

-DW

···

On Jun 24, 2016, at 1:38 PM, David Waite via swift-evolution <swift-evolution@swift.org> wrote:

I noticed that the new Collection index(_:offsetBy:) <http://swiftdoc.org/v3.0/protocol/Collection/#comment-func-index_offsetby_> does not define that negative offsets require a BidirectionalCollection. It also declares that negative offsets must complete in O( | offset | ) time. This differs from other methods such as distance(from:to:) <http://swiftdoc.org/v3.0/protocol/Collection/#comment-func-distance-from_to_>which indicates start <= end if not a BidirectionalCollection

This would preclude some data structures from strictly implementing the Collection protocol, such as singly-linked lists.

Would it be appropriate to indicate instead that BidirectionalCollection defines the negative offset behavior and negative offset performance constraint?

-DW
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dave Abrahams) #3

I noticed that the new Collection index(_:offsetBy:)
<http://swiftdoc.org/v3.0/protocol/Collection/#comment-func-index_offsetby_>
does not define that negative offsets require a
BidirectionalCollection.

Looks like a doc bug; it should require n >= 0 as a precondition.
Please file a bug report.

It also declares that negative offsets must complete in O( | offset |
) time. This differs from other methods such as distance(from:to:)
<http://swiftdoc.org/v3.0/protocol/Collection/#comment-func-distance-from_to_>which
indicates start <= end if not a BidirectionalCollection

That's also wrong. Since indices are currently Comparable, we're able
to measure distance no matter which order you pass the indices in, as
long as one is reachable from the other. However, I am leaning strongly
toward dropping the Comparable requirement.

This would preclude some data structures from strictly implementing
the Collection protocol, such as singly-linked lists.

It can work, sort of, if you store an offset in each node, but that is
admittedly not a great answer. That's one reason we're thinking about
dropping the Comparable requirement.

···

on Fri Jun 24 2016, David Waite <swift-evolution@swift.org> wrote:

Would it be appropriate to indicate instead that
BidirectionalCollection defines the negative offset behavior and
negative offset performance constraint?

-DW
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
Dave


(Haravikk) #4

I started a discussion thread that may be of interest to you, basically discussing the possibility for directional methods to reduce confusion/clarify intent, should be accessible at the following URL:
http://thread.gmane.org/gmane.comp.lang.swift.evolution/19185/focus=19613

···

On 24 Jun 2016, at 22:05, David Waite via swift-evolution <swift-evolution@swift.org> wrote:

And never mind me. Not sure how I missed that in the docs that many times.

-DW

On Jun 24, 2016, at 1:38 PM, David Waite via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

I noticed that the new Collection index(_:offsetBy:) <http://swiftdoc.org/v3.0/protocol/Collection/#comment-func-index_offsetby_> does not define that negative offsets require a BidirectionalCollection. It also declares that negative offsets must complete in O( | offset | ) time. This differs from other methods such as distance(from:to:) <http://swiftdoc.org/v3.0/protocol/Collection/#comment-func-distance-from_to_>which indicates start <= end if not a BidirectionalCollection

This would preclude some data structures from strictly implementing the Collection protocol, such as singly-linked lists.

Would it be appropriate to indicate instead that BidirectionalCollection defines the negative offset behavior and negative offset performance constraint?

-DW
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution