Sorting Dictionaries containing more complex values in Swift

Question

The key-sorting according to values of a dictionary with simple Doubles or Ints works perfectly fine according to the example provided here....

But what about more complex dictionary-structures ?

I have a dictionary with dictionary-values that each consist of an array of Double-Tuples. (pretty complex, I know....). And I would like to sort the dictionary-values according to the sum of the Second-Tuple-Array. (i.e. all second-tuple elements form an array and this array is summed-up; then sort the array-sums according to the smallest value). But all that still without loosing information on the dictionary-key. The result of the asked method shall return an array of keys according to the sorted result of "second-tuple-summed-up-array-results).

Here my "poor" trial for this problem : I tried to sort the keys according to the values of the first-Tuple of the array-of-Tuples with the following Playground example (see below). But it does not perform yet....

This works for basic types:

extension Dictionary {
    func keysSortedByValue(isOrderedBefore:(Value, Value) -> Bool) -> [Key] {
        return sorted(self) {
            let (lk, lv) = $0
            let (rk, rv) = $1
            return isOrderedBefore(lv, rv)
        }.map { (k,v) in k }
    }
}

let dict = ["a":2, "c":1, "b":3]
dict.keysSortedByValue(<)  // result array of keys: ["c", "a", "b"]
dict.keysSortedByValue(>)  // result array of keys: ["b", "a", "c"]

But in my more complex case, it doesn't work:

var criteria_array1 = [(Double, Double)]()
var criteria_array2 = [Double]()
var criteria_dict1 = [String:[(Double, Double)]]()
var criteria_dict2 = [String:[Double]]()

// Random creation of two dictionaries with a complex value-structure...
// Dictionary1: keys = Strings, values = array of Double-Tuples
// Dictionary2: keys = Strings, values = array of Doubles
for n in 1...5 {
    let currentTopoString: String = "topo_\(n)"
    for t in 0...14 {
        let a: Double = Double(arc4random_uniform(1000))
        let b: Double = Double(Double(arc4random_uniform(1000))/1000)
        criteria_array1 += [(a, b)]
        criteria_array2 += [b]
    }
    criteria_dict1[currentTopoString] = criteria_array1
    criteria_dict2[currentTopoString] = criteria_array2
    criteria_array1.removeAll()
    criteria_array2.removeAll()
}

// the two following instruction generate compiler errors....
// why ???????????
// How could a complex dictionary-value-structure be applied to a sortingMethod ??
criteria_dict1.keysSortedByFirstTupleValue(>)
criteria_dict2.keysSortedByFirstTupleValue(>)

Answer 1

This is a question of implementing the isOrderedBefore function appropriately. Just passing in > is not going to cut it (even assuming there was an implementation of > for arrays of tuples, it almost certainly wouldn't do the comparison-of-summation you are looking for).

If I understand your goal correctly, you want to sort the keys based on the value of the sum of one of the tuple entries in an array of tuples?

So something like this:

criteria_dict1.keysSortedByValue { lhs, rhs in
    // if you actually want to sort by sum of first element in tuple,
    // change next.1 to next.0
    let left_sum = reduce(lhs, 0) { total, next in total + next.1 }
    let right_sum = reduce(rhs, 0) { total, next in total + next.1 }
    return left_sum > right_sum
}

This is quite inefficient, since you're summing the array for every comparison – in practice you may want to memoize it, or maybe rethink the problem in terms of a different data structure if you do this a lot.