Swift 3 and Index of a custom linked list collection type

Question

In Swift 3 Collection indices have to conform to Comparable instead of Equatable.

Full story can be read here swift-evolution/0065.

Here's a relevant quote:

Usually an index can be represented with one or two Ints that efficiently encode the path to the element from the root of a data structure. Since one is free to choose the encoding of the “path”, we think it is possible to choose it in such a way that indices are cheaply comparable. That has been the case for all of the indices required to implement the standard library, and a few others we investigated while researching this change.

In my implementation of a custom linked list collection a node (pointing to a successor) is the opaque index type. However, given two instances, it is not possible to tell if one precedes another without risking traversal of a significant part of the chain.

I'm curious, how would you implement Comparable for a linked list index with O(1) complexity?

The only idea that I currently have is to somehow count steps while advancing the index, storing it within the index type as a property and then comparing those values.

Serious downside of this solution is that indices must be invalidated when mutating the collection. And while that seems reasonable for arrays, I do not want to break that huge benefit linked lists have - they do not invalidate indices of unchanged nodes.

EDIT: It can be done at the cost of two additional integers as collection properties assuming that single linked list implements front insert, front remove and back append. Any meddling around in the middle would anyway break O(1) complexity requirement.

Answer 1

Here's my take on it.

a) I introduced one private integer type property to my custom Index type: depth.

b) I introduced two private integer type properties to the collection: startDepth and endDepth, which both default to zero for an empty list.

1. Each front insert decrements the startDepth.
2. Each front remove increments the startDepth.
3. Each back append increments the endDepth.

Thus all indices startIndex..<endIndex have a reflecting integer range startDepth..<endDepth.

c) Whenever collection vends an index either by startIndex or endIndex it will inherit its corresponding depth value from the collection. When collection is asked to advance the index by invoking index(_ after:) I will simply initialize a new Index instance with incremented depth value (depth += 1).

Conforming to Comparable boils down to comparing left-hand side depth value to the right-hand side one.

Note that because I expand the integer range from both sides as well, all the depth values for the middle indices remain unchanged (thus are not invalidated).

Conclusion:

Traded benefit of O(1) index comparisons at the cost of minor increase in memory footprint and few integer increments and decrements. I expect index lifetime to be short and number of collections relatively small.

If anyone has a better solution I'd gladly take a look at it!

Answer 2

I may have another solution. If you use floats instead of integers, you can gain kind of O(1) insertion-in-the-middle performance if you set the sortIndex of the inserted node to a value between the predecessor and the successor's sortIndex. This would require to store (and update) the predecessor's sortIndex on your nodes (I imagine this should not be to hard since it is only changed on insertion or removal and it can always be propagated 'up').

In your index(after:) method you need to query the successor node, but since you use your node as index, that is be straightforward.

One caveat is the finite precision of floating points, so if on insertion you the distance between the two sort indices are two small, you need to reindex at least part of the list. Since you said you only expect small scale, I would just go through the hole list and use the position for that.

This approach has all the benefits of your own, with the added benefit of good performance on insertion in the middle.