How could I prevent duplicate references to class objects in an array?

Question

I'm looking for a way to prevent an array from having duplicate references to the same object in it. I don't mean duplicate values - that would be fine.

For example, I know in Apple's SpriteKit framework, an SKNode object stores its children in an array (var children: [SKNode]), and adding a node to a parent twice causes the program to crash.

let parent = SKNode()
let child1 = SKNode()
let child2 = SKNode()
parent.addChild(child1)
parent.addChild(child2)    // Allowed, although child2 == child1.
parent.addChild(child1)    // Causes a crash.

This is the exact kind of behavior I am wanting to emulate. How would I manage this? Is it possible without having O(n) complexity from having to compare each reference?

Alexander · Accepted Answer · 2017-06-13 04:10:11Z

1

I'm not sure why exactly you would want to do this, but here is how you can go about doing it:

...

var childReferences = Set<ObjectIdentifier>

private func validateUniqueness(_ node: SKNode) {
    guard childReferences.insert(ObjectIdentifier(node)).inserted else {
        fatalError("An attempt was made to add a duplicate child")
    }
}

override func addChild(_ node: SKNode) {
    validateUniqueness(node)
    super.addChild(node)
}

override func insertChild(_ node: SKNode at index: Int) {
    validateUniqueness(node)
    super.insertChild(node, at: index)
}

override func removeChildren(in nodes: [SKNode]) {
    childReferences.subtract(nodes)
    super.removeChildren(in nodes: [SKNode])
}

override func removeAllChildren() {
    childReferences.removeAll(keepingCapacity: false)
    super.removeAllChildren()
}

answered Jun 13, 2017 at 4:10

Alexander

63.9k13 gold badges106 silver badges177 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

ebby94 Over a year ago

I think OP asked if it is possible to do it without O(n) complexity. But you're just using a set which just checks for duplicates before adding and so the worst case complexity is still O(n).

Alexander Over a year ago

@ebby94 Lookups in Sets are O(1).

ebby94 Over a year ago

Didn't know that. But how is a Set lookup O(1)? Accessing with a subscript has a O(1) complexity, but finding duplicates should take O(n) complexity right? Any links that explains this would be cool :)

Alexander Over a year ago

Accessing with a subscript has a O(1) complexity Subscripts can implement any arbitrary behaviour, so there's no guarantee they're O(1). For Array in particular, the index is multiplied by the element size, and added to the base pointer. This happens to be a constant time operation, but other types can implement subscripts that have higher time complexity. For example, a linked list could implement a subscript with O(N).

Alexander Over a year ago

@ebby94 github.com/apple/swift/blob/master/stdlib/public/core/…

|

Collectives™ on Stack Overflow

How could I prevent duplicate references to class objects in an array?

1 Answer 1

9 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related