Group Group Group Group Group Group Group Group Group

Removing a node after a particular node fails after COW fix

In the linked list section, I think I’ve found bug for the “remove(after:)” func after we implement the “copyNodes()” function.

Before we add copyNodes(), the function works adequately, and we have “After removing at index 1: 1 -> 3” printed out as expected. But, after adding copyNodes() at the beginning of the remove(after:) function, the printout is “After removing at index 1: 1 -> 2 -> 3”

Then, in “example(of: “removing a node after a particular node”)”, with the copyNodes() at the beginning of the remove(after:) function, I assign list to a new list2 var prior to performing the remove operation. list2 prints out the desired outcome after the operation and list prints out as if nothing was removed!?

@kelvin_lau Can you please help with this when you get a chance? Thank you - much appreciated! :]

Hey Paul, thank you for bringing this up. This is indeed a bug.

The root of the problem is this line here:

let node = list.node(at: index - 1)!

node is a reference to a node of list.

However, once you call a mutating method, copyNodes creates a brand new set of nodes for list. The node value is now referencing an old node that is no longer part of list.

I’ll have to think about how I can fix this. But thank you for flagging this!

Hi Kevin!

Good, can’t wait to see the fix.

Edit: Added isKnownUniquelyReferenced check (hadn’t gotten that far yet).
Edit2: Fixed tail comparison check on insert after

I have a fix that I’ve tested out and seems to resolve the issue. This applies anywhere that a selected node is passed in. So, same issue on insert as well. I am handling it by optionally passing in the selected node and making a comparison to determine if a node in the copied list should also be selected.

Here is my modified copyNodes method:

@discardableResult
private mutating func copyNodes(selected node: Node<Value>? = nil) -> Node<Value>? {
    guard !isKnownUniquelyReferenced(&head) else {
        return node
    }
    
    guard var oldNode = head else {
        return nil
    }
    
    var newSelectedNode: Node<Value>? = nil
    
    head = Node(value: oldNode.value)
    var newNode = head
    
    while let nextOldNode = oldNode.next {
        newNode!.next = Node(value: nextOldNode.value)
        
        if node != nil && node === oldNode {
            newSelectedNode = newNode
        }
        
        newNode = newNode!.next
        
        oldNode = nextOldNode
    }
    
    tail = newNode
    
    return newSelectedNode
}

Here are the changes to the insert(after) and remove(after):

@discardableResult
public mutating func insert(_ value: Value, after node: Node<Value>) -> Node<Value> {
    let selectedNode = copyNodes(selected: node)
    
    // 2
    guard tail !== selectedNode! else {
        append(value)
        return tail!
    }
    
    // 3
    selectedNode!.next = Node(value: value, next: selectedNode!.next)
    return selectedNode!.next!
}

@discardableResult
public mutating func remove(after node: Node<Value>) -> Value? {
    let selectedNode = copyNodes(selected: node)
    
    defer {
        if selectedNode!.next === tail {
            tail = selectedNode
        }
        selectedNode!.next = selectedNode!.next?.next
    }
    return selectedNode!.next?.value
}

Am I reading that correctly: You are grabbing hold of a reference to the original non-copied node that is passed into insert(:after:) and remove(after:) and within the copyNodes function “transform” that reference to instead point to the corresponding copied node?

Yep. That’s exactly what I’m doing.