CODEWITHSUNDEEP
arraysswiftsorting
Łukasz
Łukasz

Reputation: 805

Comparable extension works but gives bad results

I wrote Comparable extension for Array:

extension Array:Comparable where Element == Double {
     public static func < (lhs: Array<Element>, rhs: Array<Element>) -> Bool {
         let count = Swift.min(lhs.count, rhs.count)
         for i in 0..<count {
             if lhs[i] < rhs[i]  { return true }
        }
        return false
    }
}

and for class Tuple:

extension Tuple:Comparable where T == Double {
    static func < (lhs: Tuple<T>, rhs: Tuple<T>) -> Bool {
        print ("compare \(lhs) \( lhs.content < rhs.content ? "<" : ">=") \(rhs)")
        return lhs.content < rhs.content
    }
}

When i call 

return Array<This>(newVertices.sorted(by: { $0.position < $1.position}))

listing looks good, Tuple func < (lhs: Array<Element>, rhs: Array<Element>) is called and results strange:

wrong, 100 > 55:

compare Tuple<Double> 3-D: [100.0, 0.0, 55.0, ] < Tuple<Double> 3-D: [55.0, 55.0, 300.0, ]

wrong, 100 > 0:

compare Tuple<Double> 3-D: [100.0, 0.0, 55.0, ] < Tuple<Double> 3-D: [0.0, 55.0, 300.0, ]

hmm, OK... 100 > 55

compare Tuple<Double> 3-D: [100.0, 0.0, 55.0, ] >= Tuple<Double> 3-D: [55.0, 0.0, 55.0, ]

OK, -100 < 55

compare Tuple<Double> 3-D: [-100.0, 55.0, 300.0, ] < Tuple<Double> 3-D: [55.0, 55.0, 300.0, ]

OK, -100 < 0

compare Tuple<Double> 3-D: [-100.0, 55.0, 300.0, ] < Tuple<Double> 3-D: [0.0, 55.0, 300.0, ]

OK, -100 < 100

compare Tuple<Double> 3-D: [-100.0, 55.0, 300.0, ] < Tuple<Double> 3-D: [100.0, 0.0, 55.0, ]

Where could be a mistake?

Upvotes: 1

Views: 45

Answers (1)

Martin R
Martin R

Reputation: 539795

Your array comparison function is invalid, is does not provide a “strict weak ordering”:

let a = [2.0, 1.0, 3.0]
let b = [1.0, 2.0, 4.0]

print(a < b) // true
print(b < a) // true

For the lexicographic ordering you have to return false as soon as lhs[i] > rhs[i] for some index, instead of continuing the loop. Also the case of one array being a prefix of the other is not handled.

This would be a correct implementation:

extension Array: Comparable where Element == Double {
    public static func < (lhs: Array<Element>, rhs: Array<Element>) -> Bool {
        let count = Swift.min(lhs.count, rhs.count)
        for i in 0..<count {
            if lhs[i] < rhs[i]  { return true }
            if lhs[i] > rhs[i]  { return false }
        }
        return lhs.count < rhs.count
    }
}

which can be simplified and generalized to

extension Array: Comparable where Element: Comparable {
    public static func < (lhs: Array<Element>, rhs: Array<Element>) -> Bool {
        for (l, r) in zip(lhs, rhs) {
            if l < r { return true }
            if l > r { return false }
        }
        return lhs.count < rhs.count
    }
}

Examples:

print( [2.0, 1.0, 3.0] < [1.0, 2.0, 4.0]) // false
print( [1.0, 2.0, 4.0] < [2.0, 1.0, 3.0]) // true
print( [1.0] < [1.0, 2.0]) // true
print( [1.0, 2.0] < [1.0, 2.0]) // false
print( [1.0, 2.0] < [1.0]) // false

Upvotes: 2

Related Questions