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.

Looks like Tim’s solution works well. (Thank you Tim).
However, only ‘remove’ part has been revised on the book.
‘insert’ part needs to be revised on new edition.

You’re right. insert also has the same problem. Tagged for updates on the next version - thanks @tim_miller @stephen_moon

Tim has a point and looks like this issue is clarified now.

Happy to help! :smiley: