> On 7 Jul 2016, at 02:41, Dave Abrahams via swift-evolution
> <[email protected]> wrote:
>
>
> on Wed Jul 06 2016, Haravikk <[email protected]> wrote:
>
>>> On 6 Jul 2016, at 03:39, Dave Abrahams via swift-evolution
>>> <[email protected]> wrote:
>>> For example, with
>>> Comparable indices, you can't build a linked list that supports
>>> restructuring (e.g. insert, delete, splice) in O(1) without invalidating
>>> indices... not even an unsafe linked list with reference semantics.
>>
>> I think the question is why you need to retain indices in these cases?
>>
>> When it comes to these operations I wonder if we might want to
>> investigate something like a mutating iterator; you might still use an
>> index to jump to an initial position, but then use .insert(),
>> .remove() etc. methods of the iterator to perform modification without
>> the need to track indices at all.
>
> There is no way, AFAIK, to implement important algorithms like rotate
> binarySearch and several others, without having some representation of
> position within a collection.
>
>> This is essentially how you want to edit trees anyway, as indexing
>> them isn't especially pretty, as it avoids the need to track the
>> indices at all for these operations, and many common cases should work
>> well when done as part of an iterator in this way.
>
> I don't know what you mean by “track,” here. We don't track the
> indices of an array.
By track I just mean store in a variable.
As an example, consider removing multiple values using a closure:
let delete:(Int) -> Bool = { ($0 % 2) == 1 } // Delete all odd numbers
let filtered = myArray.filter { !delete($0) } // Produces new copy of
array with elements filtered
// In-place removal
var index = myArray.startIndex, indices:[Array<Int>.Index] = []
for eachElement in myArray {
if delete(eachElement) { indices.append(index) }
myArray.formIndex(after: &index)
}
for eachIndex in indices { myArray.remove(at: eachIndex }
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:
var iterator = myArray.makeMutatingIterator()
while let eachElement = iterator.next() {
if delete(eachElement) { iterator.remove() }
}
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?
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 should 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):
struct LinkedListIndex<Element> : Comparable {
let mutationCount:Int
var position:Int, node:LinkedListNode<Element>
}
func == <E>(lhs:LinkedListIndex<E>, rhs:LinkedListIndex<E>) { return
lhs.position == rhs.position }
func < <E>(lhs:LinkedListIndex<E>, rhs:LinkedListIndex<E>) { return
lhs.position < rhs.position }
class LinkedListNode<Element> {
var element:Element, next:LinkedListNode<Element>?
init(_ element:Element) { self.element = element }
}
struct LinkedList<Element> : Indexable {
var mutationCount:Int = 0, head:LinkedListNode<Element>?,
tail:LinkedListNode<Element>?
typealias Index = LinkedListIndex
var startIndex:Index { return LinkedListIndex(mutationCount:
self.mutationCount, position: 0) }
func formIndex(after i:inout Index) {
precondition(i.mutationCount == self.mutationCount,
"Invalid index")
i.position += 1
i.node = i.node?.next
}
func index(after i:Index) -> Index { var i = i;
self.formIndex(after: &i); return i }
subscript(i:Index) -> Element {
precondition(i.mutationCount == self.mutationCount,
"Invalid index")
return i.node!.element
}
mutating func append(_ element:Element) {
let node = LinkedListNode(element)
if self.tail == nil { self.head = node; self.tail =
node }
else { self.tail.next = node; self.tail = node }
self.mutationCount = self.mutationCount &+ 1
}
}
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._______________________________________________
swift-evolution mailing list
[email protected]
https://lists.swift.org/mailman/listinfo/swift-evolution
