<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On 7 Jul 2016, at 02:41, Dave Abrahams via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class=""><br class="">on Wed Jul 06 2016, Haravikk <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:<br class=""><br class=""><blockquote type="cite" class=""><blockquote type="cite" class="">On 6 Jul 2016, at 03:39, Dave Abrahams via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:<br class="">For example, with<br class="">Comparable indices, you can't build a linked list that supports<br class="">restructuring (e.g. insert, delete, splice) in O(1) without invalidating<br class="">indices... not even an unsafe linked list with reference semantics.<br class=""></blockquote><br class="">I think the question is why you need to retain indices in these cases?<br class=""><br class="">When it comes to these operations I wonder if we might want to<br class="">investigate something like a mutating iterator; you might still use an<br class="">index to jump to an initial position, but then use .insert(),<br class="">.remove() etc. methods of the iterator to perform modification without<br class="">the need to track indices at all. <br class=""></blockquote><br class="">There is no way, AFAIK, to implement important algorithms like rotate<br class="">binarySearch and several others, without having some representation of<br class="">position within a collection.<br class=""><br class=""><blockquote type="cite" class="">This is essentially how you want to edit trees anyway, as indexing<br class="">them isn't especially pretty, as it avoids the need to track the<br class="">indices at all for these operations, and many common cases should work<br class="">well when done as part of an iterator in this way.<br class=""></blockquote><br class="">I don't know what you mean by “track,” here. We don't track the<br class="">indices of an array.</div></div></blockquote><br class=""></div><div>By track I just mean store in a variable.</div><div><br class=""></div><div>As an example, consider removing multiple values using a closure:</div><div><br class=""></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>let delete:(Int) -> Bool = { ($0 % 2) == 1 } // Delete all odd numbers</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>let filtered = myArray.filter { !delete($0) } // Produces new copy of array with elements filtered</font></div><div><font face="Monaco" class=""><br class=""></font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>// In-place removal</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>var index = myArray.startIndex, indices:[Array<Int>.Index] = []</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>for eachElement in myArray {</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>if delete(eachElement) { indices.append(index) }</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>myArray.formIndex(after: &index)</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>}</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>for eachIndex in indices { myArray.remove(at: eachIndex }</font></div><div><br class=""></div><div>The latter case only works with types where you know that there's a safe way to use the indices (removing in reverse order doesn't invalidate earlier indices of Array) so it's not suitable for generic collections. Since it requires iterating myArray anyway, then if the removals could be performed at the same time it would eliminate the need to store and then use indices at all, and would be a much better way to work with linked-lists, trees and so-on. So with a mutable iterator for example the in-place removal would look like:</div><div><br class=""></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>var iterator = myArray.makeMutatingIterator()</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>while let eachElement = iterator.next() {</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>if delete(eachElement) { iterator.remove() }</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>}</font></div><div><br class=""></div><div>Maybe this isn't directly applicable to this topic, but this for example seems like a better solution to the linked list problems raised than removing Comparable as a requirement which was my intended point, that perhaps this isn't necessary?</div><div><br class=""></div><div>Otherwise I think the main issue with types that don't seem like they can implement Comparable is that they need a means of detecting that they've been invalidated; arguably a singly-linked list's indices <i class="">should</i> become unusable if it has been changed, which could be done for example by giving the list a mutationCount value that is incremented each time it is mutated; indices would take a copy of this value and if they don't match, they produce a runtime error. Like so (heavily abridged):</div><div><br class=""></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>struct LinkedListIndex<Element> : Comparable {</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>let mutationCount:Int</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>var position:Int, node:LinkedListNode<Element></font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>}</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>func == <E>(lhs:LinkedListIndex<E>, rhs:LinkedListIndex<E>) { return lhs.position == rhs.position }</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>func < <E>(lhs:LinkedListIndex<E>, rhs:LinkedListIndex<E>) { return lhs.position < rhs.position }</font></div><div><font face="Monaco" class=""><br class=""></font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>class LinkedListNode<Element> {</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>var element:Element, next:LinkedListNode<Element>?</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>init(_ element:Element) { self.element = element }</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>}</font></div><div><font face="Monaco" class=""><br class=""></font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>struct LinkedList<Element> : Indexable {</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>var mutationCount:Int = 0, head:LinkedListNode<Element>?, tail:LinkedListNode<Element>?</font></div><div><font face="Monaco" class=""><br class=""></font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>typealias Index = LinkedListIndex</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>var startIndex:Index { return LinkedListIndex(mutationCount: self.mutationCount, position: 0) }</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space: pre;"> </span>func formIndex(after i:inout Index) {</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space: pre;"> </span>precondition(i.mutationCount == self.mutationCount, "Invalid index")</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>i.position += 1</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>i.node = i.node?.next</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space: pre;"> </span>}</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>func index(after i:Index) -> Index { var i = i; self.formIndex(after: &i); return i }</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>subscript(i:Index) -> Element {</font></div><span class="Apple-tab-span" style="font-family: Monaco; white-space: pre;"> </span><span style="font-family: Monaco;" class="">precondition(i.mutationCount == self.mutationCount, "Invalid index")</span><div class=""><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>return i.node!.element<br class=""></font><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>}</font></div><div><font face="Monaco" class=""><br class=""></font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>mutating func append(_ element:Element) {</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>let node = LinkedListNode(element)</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>if self.tail == nil { self.head = node; self.tail = node }</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>else { self.tail.next = node; self.tail = node }</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>self.mutationCount = self.mutationCount &+ 1</font></div><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>}</font></div></div><div class=""><div><font face="Monaco" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>}</font></div></div><div><font face="Monaco" class=""><br class=""></font></div>Please forgive typos/omissions, tried to keep it as short as possible. But yeah, this is essentially how I'd try to implement a linked list, while retaining the Comparable constraint.</body></html>