How do I compare two elements for equality in a Swift generic without knowing if they structs or class objects?

Question

I have implemented a linked list in Swift. Code that uses this data structure can append, insert, etc., a new node into the list by providing an element of the generic type. In other words, the list holds nodes and each node holds a reference or instance of the type, and callers simply pass the T type element to insert into the list (not wasting lines of code creating a node they don't need to know about). Here are some pieces of the code defining the linked list (with tons of irrelevant stuff removed):

public class LinkedListNode<T> {
    init( value: T ) {
        self.value = value
    }
    public var next: LinkedListNode?
    public weak var previous: LinkedListNode?
    public var value: T
}

struct LinkedList<T>: Sequence {
     internal var head: LinkedListNode<T>?
     internal unowned var tail: LinkedListNode<T>?

    @discardableResult public mutating func insert( _ value: T, after: LinkedListNode<T> ) -> LinkedListNode<T> {
        if after === tail {
            return append( value )
        } else {
            let node = LinkedListNode<T>( value: value )
            insertBetween( node, after: after, before: after.previous )
            return node
        }
    }
...
}

This all works great. I only had a medium amount of trouble finding documentation that explained how to make the Sequence protocol work right.

Now I want to add a function to add or replace an element in the list. I want the caller to pass in something of type T and I want to check to see if it exists so it can be replaced. I want to add the new element if it doesn't already exist. The problem is that I want to compare two T types to see if they are the same instance of an object of the list has objects in it (within the nodes) but compare for content equality if the list has structs or just native types like Int, within it.

I can do this outside of the linked list code because I have a first() function. Maybe that's a better choice. But I would still like to know if it's possible to write code that let's me do an appropriate equality test depending on the type of thing that the list contains.

This is what I was working on when I got to this problem:

@discardableResult public mutating func replaceOrAppend( _ value: T ) -> LinkedListNode<T> {
    var node = first( where: { $0.value === value } )
    if node == nil {
        node = LinkedListNode<T>( value: value )
        insertBetween( node!, after: tail, before: tail?.next )
        tail = node
    }
    return node!
}

Notice that I used === for the comparison. Unless I define T as T:AnyObject, this will fail to compile. I want this to work to compare the content of structs and native types and the references for class objects.

score 2 · Accepted Answer · answered Jan 28 '23 at 01:33

Not all things can be compared for equality. Functions are a great example of this. If I have a LinkedList<() -> Void>, and I want to replaceOrAppend another () -> Void to it, how can you tell if the new function "already exists" in the linked list? Figuring that out would at least require solving the halting problem. :D

A better design would be to only have replaceOrAppend be available when T is Equatable:

extension LinkedList where T: Equatable {
    // I've rewritten this to eliminate the "!"
    @discardableResult public mutating func replaceOrAppend( _ value: T ) -> LinkedListNode<T> {
        // now you can use "==", because T is known to be Equatable
        if let node = first( where: { $0.value == value } ) {
            return node
        } else {
            let newNode = LinkedListNode<T>( value: value )
            insertBetween( newNode, after: tail, before: tail?.next )
            tail = newNode
            return newNode
        }
     }
}

I'm starting to think that this is the only option. Coming from C++, I would never have this problem since the list could only hold native numeric types or pointers and nothing else. Both can be compared numerically without having to pick between == and ===. Alas, this is Swift, and some things, maybe terrible things, are not possible. I ended up leaving T alone and I just moved my code into the caller where it can better decide how to handle duplicates since it knows the type of T. — David Rector, Jan 30 '23 at 21:42

score 1 · Answer 2 · answered Jan 28 '23 at 03:11

The problem is that I want to compare two T types to see if they are the same instance of an object of the list has objects in it (within the nodes) but compare for content equality if the list has structs or just native types like Int, within it.

I don't think you should have this distinction. I would suggest you just use ==.

It's pretty unusual to have objects only be considered equal when they're exactly equal. If you callers did want that, they would implement Equatable/== to achieve that, or stuff it in a wrapper like the IdentityWrapper in this example here.

How do I compare two elements for equality in a Swift generic without knowing if they structs or class objects?

2 Answers2