Swift 5 Dictionary sortedKeysByValue

Question

I need to get a sorted key list from a dictionary by their values.

I found an answer close to this question but not good enough:

extension Dictionary {
  func sortedKeysByValue(by compareMethod: (Value, Value) -> Bool) -> [Key] {
    return self
      .sorted {
        let (lk, lv) = $0
        let (rk, rv) = $1
        return compareMethod(lv, rv)
      }
      .map {
        let (key, _) = $0
        return key
      }
  }
}

let dict = ["a": 5, "b": 3, "c": 10, "d": 7, "e": 9, "f": 5]
let result = dict.keysSortedByValue(>)

// The result could be: 
// ["c", "e", "d", "a", "f", "b"] or 
// ["c", "e", "d", "f", "a", "b"]

The question is that: when the value is equal, it should compare the keys to always produce the same results. To do so, I need to make compareMethod not just accept Value type but also Key type. I try to make the method signature use Comparable protocol, but is gets a compilation error:

extension Dictionary where Key: Comparable, Value: Comparable {
                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ensure Key/Value types are Comparable
  func sortedKeysByValue(by compareMethod: (Comparable, Comparable) -> Bool) -> [Key] {
                                            ^^^^^^^^^^  ^^^^^^^^^^ got error (see below)
    return self
      .sorted {
        let (lk, lv) = $0
        let (rk, rv) = $1
        return compareMethod(lv, rv) || (lv == rv && compareMethod(lk, rk))
                                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ compare keys when values are equal 
      }
      .map {
        let (key, _) = $0
        return key
      }
  }
}

Compilation error: Protocol 'Comparable' can only be used as a generic constraint because it has Self or associated type requirements

The compareMethod should be able to handle both Value type and Key type. How do I fix it?

"I found an answer close to this question" Que!? What is your question? — El Tomato, Dec 18 '20 at 12:06

Sweeper · Accepted Answer · 2020-12-19T00:19:12.777

The compareMethod should be able to handle both Value type and Key type.

It is not possible to declare such a function. You need one function to compare the keys, and another to compare the values.

You can write it like this:

// doesn't have to be Comparable, just conforming to Equatable is fine, as you are only using "=="
extension Dictionary where Value: Equatable {
    func sortedKeysByValue(byComparingValues compareValues: (Value, Value) -> Bool, andComparingKeys compareKeys: (Key, Key) -> Bool) -> [Key] {
    return self
        .sorted {
            let (lk, lv) = $0
            let (rk, rv) = $1
            return compareValues(lv, rv) || (lv == rv && compareKeys(lk, rk))
        }.map(\.key)
    }
}

IMO, a better way to do this is to use (Value, Value) -> ComparisonResult functions, rather than (Value, Value) -> Bool. This not only allows the caller to specify their custom definition of equality, rather than always using "==", but also makes the method available on all types of dictionaries.

extension Dictionary {
    func sortedKeysByValue(byComparingValues compareValues: (Value, Value) -> ComparisonResult, andComparingKeys compareKeys: (Key, Key) -> Bool) -> [Key] {
        return self
            .sorted {
                let (lk, lv) = $0
                let (rk, rv) = $1
                switch compareValues(lv, rv) {
                case .orderedAscending:
                    return false
                case .orderedDescending:
                    return true
                default:
                    return compareKeys(lk, rk)
                }
            }.map(\.key)
    }

}

The downside is of course that you can't easily pass a comparison operator to this.

Thanks for your answer. `??` is typo; it should be `&&`. The one line code should be `compareMethod(lv, rv) || (lv == rv && compareMethod(lk, rk))`. I corrected the post. — Xaree Lee, Dec 18 '20 at 13:54
@李岡諭 Ah that makes sense. I was confused why you thought `??` could be used there, haha. — Sweeper, Dec 18 '20 at 13:56
Key already conforms to Hashable. There is no need to add a Equatable constrain. — Leo Dabus, Dec 18 '20 at 15:40
@LeoDabus oh gosh silly me! My brain doesn’t work well at night :) — Sweeper, Dec 19 '20 at 00:20

Swift 5 Dictionary sortedKeysByValue

1 Answers1