[swift-evolution] Collection index complexity and data structures

[Dave Abrahams]

on Fri Jun 24 2016, David Waite <swift-evolution at 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. 

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.

> 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 at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>

-- 
Dave