Given an array of objects, link the child objects to its parent

Using Swift
1

Hi, I have the same problem described here. What could be the efficient Swift solution for this?

Thanks in advance!

2

The JavaScript solution can be ported over pretty much as-is, but it's not great. It's doing repeated filtering operations over the array, instead of a single grouping into a dictionary. Might not matter for small input sizes, but it's bit meh.

Here's how I'd write this:

class Element {
    let name: String
    let id: Int
    let parentID: Int
    var children = [Element]()
    
    init(name: String, id: Int, parentID: Int, children: [Element] = []) {
        self.name = name
        self.id = id
        self.parentID = parentID
        self.children = children
    }
}

let elements = [
    Element(name: "el1", id: 1, parentID: 0),
    Element(name: "el2", id: 2, parentID: 1),
    Element(name: "el3", id: 3, parentID: 0),
    Element(name: "el4", id: 4, parentID: 3),
    Element(name: "el5", id: 5, parentID: 0),
    Element(name: "el6", id: 6, parentID: 2),
]

// Rather than running many `filter` operations over `elements`, just go over it once
// and build groupings of elements base on their parents.
let elementsByParentID = Dictionary(grouping: elements, by: \.parentID)

// I'm using classes and mutating in-place because I'm lazy, but you could just as well
// make immutable objects and produce new ones here instead.
for element in elements {
    element.children = elementsByParentID[element.parentID] ?? []
}

elements.forEach { dump($0) }
1 Like
3

Hi Alexander,

Thanks for the quick response. I was trying out your solution and replacing element.parentID with element.id in the for-in loop gives me the expected output. But the catch here is Dictionary does not maintain the order and for some reason, the order is what I can't ignore. Although I didn't see any change in the order as of now, I'm concerned when the data is a bit large.

4

There is an ordered version of Dictionary.

2 Likes
5

For a very good reason: hash maps just don't work that way. To maintain order, a hash map needs an auxiliary data structure (or an embedded linked list) between elements to record the order. This is adds a memory and performance cost that isn't justified if order is not needed, so dicts are non-ordered by default.

This actually won't be an issue here. The iteration order of (key, value) pairs of Dictionaries is not deterministic, but if you'll notice, nowhere in this code is that iteration order being used.

The final print iterates the elements input array, which remains in the same order as it started. The dictionary is merely a look-up table to draw child elements from, in order to set them correctly on each element.

If order matters, there's just one catch here: this code is assuming that the ordering of elements within each group (inside elementsByParentID) has the same ordering as it had in the input elements. This is correct today, and it's the most obvious way for Dictionary.init(grouping:by:) to be implemented, but it's not technically guaranteed by the documentation. I would consider it safe to assume.

2 Likes