Swift sorting on arbitrary types

Question

I have a Set of instances of type Thingie, and I want to provide arrays of Thingies sorted on any property of Thingie. Some of the properties are Int, for instance, while others are String, and there could be others. So I wanted to create a sort routine that accepts a string as the name of the property and compares the two properties of two thingies to determine the order.

It seemed like a job for generics, and I'm getting close, but there's a hole.

Here's where I'm at right now:

func compare<T:Comparable>(lft: T, _ rgt: T) -> Bool {
    return lft < rgt
}

func orderBy(sortField: String) -> [Thingie] {
    let allArray = (self.thingies as NSSet).allObjects as! [Thingie]

    //typealias T = the type of allArray[0][sortField]
    // or maybe create an alias that conforms to a protocol:
    //typealias T:Comparable = ?

    return allArray.sort({(a, b) -> Bool in
        return self.compare(a[sortField] as! T, b[sortField] as! T)
    })
}

I created a compare function using generics, and invoke it in my sort routine. The catch is that AnyObject! will not work for my generic, so I need to cast the values returned from a[sortField] and b[sortField] to be of the same type. It doesn't even really matter what type as long as the compiler is happy that both values are of the same type and that it implements the Comparable protocol.

I figured a typealias would do the trick, but maybe there's a better way?

Side question: surely there's a better way to create the initial, unsorted array from the set without resorting to NSSet. A little hint would be welcome. [Solved that bit! Thanks, Oliver Atkinson!]

Here's a big 'ol chunk of code you can paste into a playground. It has three attempts at the orderBy implementation, each with a problem.

//: Playground - noun: a place where people can play

import Foundation

class Thingie: Hashable {
    var data: [String: AnyObject]
    var hashValue: Int

    init(data: [String: AnyObject]) {
        self.data = data
        self.hashValue = (data["id"])!.hashValue
    }

    subscript(propName: String) -> AnyObject! {
        return self.data[propName]
    }

}

func ==(lhs: Thingie, rhs: Thingie) -> Bool {
    return lhs.hashValue == rhs.hashValue
}


var thingies: Set = Set<Thingie>()
thingies.insert(Thingie(data: ["id": 2, "description": "two"]));
thingies.insert(Thingie(data: ["id": 11, "description": "eleven"]));


// attempt 1
// won't compile because '<' won't work when type is ambiguous e.g., AnyObject
func orderByField1(sortField: String) -> [Thingie] {
    return thingies.sort { $0[sortField] < $1[sortField] }
}




// compare function that promises the compiler that the operands for < will be of the same type:
func compare<T:Comparable>(lft: T, _ rgt: T) -> Bool {
    return lft < rgt
}


// attempt 2
// This compiles but will bomb at runtime if Thingie[sortField] is not a string
func orderByField2(sortField: String) -> [Thingie] {
    return thingies.sort { compare($0[sortField] as! String, $1[sortField] as! String) }
}


// attempt 3
// Something like this would be ideal, but protocol Comparable can't be used like this.
// I suspect the underlying reason that Comparable can't be used as a type is the same thing preventing me from making this work.
func orderByField3(sortField: String) -> [Thingie] {
    return thingies.sort { compare($0[sortField] as! Comparable, $1[sortField] as! Comparable) }
}



// tests - can't run until a compiling candidate is written, of course

// should return array with thingie id=2 first:
var thingieList: Array = orderByField2("id");
print(thingieList[0]["id"])

// should return array with thingie id=11 first:
var thingieList2: Array = orderByField2("description");
print(thingieList2[0]["id"])

Answer 1

My previous answer, though it works, does not make the most of the Swift's excellent type checker. It also switches between the types that can be used in one centralised place which limits extensibility to the framework owner.

The following approach solves these issues. (Please forgive me for not having the heart to delete my previous answer; let us say that it's limitations are instructive...)

As before, we'll start with the target API:

struct Thing : ThingType {

    let properties: [String:Sortable]

    subscript(key: String) -> Sortable? {
        return properties[key]
    }
}

let data: [[String:Sortable]] = [
    ["id": 1, "description": "one"],
    ["id": 2, "description": "two"],
    ["id": 3, "description": "three"],
    ["id": 4, "description": "four"],
    ["id": 4, "description": "four"]
]

var things = data.map(Thing.init)

things.sortInPlaceBy("id")

things
    .map{ $0["id"]! } // [1, 2, 3, 4]

things.sortInPlaceBy("description")

things
    .map{ $0["description"]! } // ["four", "one", "three", "two"]

To make this possible we must have this ThingType protocol and an extension to mutable collections (which will work for sets as well as arrays):

protocol ThingType {
    subscript(_: String) -> Sortable? { get }
}

extension MutableCollectionType
where Index : RandomAccessIndexType, Generator.Element : ThingType
{
    mutating func sortInPlaceBy(key: String, ascending: Bool = true) {
        sortInPlace {
            guard let lhs = $0[key], let rhs = $1[key] else {
                return false // TODO: nil handling
            }
            guard let b = (try? lhs.isOrderedBefore(rhs, ascending: ascending)) else {
                return false // TODO: handle SortableError
            }
            return b
        }
    }
}

Evidently, the whole idea revolves around this Sortable protocol:

protocol Sortable {
    func isOrderedBefore(_: Sortable, ascending: Bool) throws -> Bool
}

... which can be conformed to independently by any type we want to work with:

import Foundation

extension NSNumber : Sortable {
    func isOrderedBefore(other: Sortable, ascending: Bool) throws -> Bool {
        try throwIfTypeNotEqualTo(other)
        let f: (Double, Double) -> Bool = ascending ? (<) : (>)
        return f(doubleValue, (other as! NSNumber).doubleValue)
    }
}

extension NSString : Sortable {
    func isOrderedBefore(other: Sortable, ascending: Bool) throws -> Bool {
        try throwIfTypeNotEqualTo(other)
        let f: (String, String) -> Bool = ascending ? (<) : (>)
        return f(self as String, other as! String)
    }
}

// TODO: make more types Sortable (including those that do not conform to NSObject or even AnyObject)!

This throwIfTypeNotEqualTo method is just a convenience extension of Sortable:

enum SortableError : ErrorType {
    case TypesNotEqual
}

extension Sortable {
    func throwIfTypeNotEqualTo(other: Sortable) throws {
        guard other.dynamicType == self.dynamicType else {
            throw SortableError.TypesNotEqual
        }
    }
}

And that's it. Now we can conform new types to Sortable even outside of the framework and the type checker is validating our [[String:Sortable]] source data at compile time. Also, if Thing is extended to conform to Hashable then Set<Thing> will also be sortable by key...

Note that, although Sortable is itself unconstrained (which is awesome), source data and Thing's properties can be constrained to dictionaries with NSObject or AnyObject values if required by making use of a protocol like:

protocol SortableNSObjectType : Sortable, NSObjectProtocol { }

... or more directly by declaring data and Thing's properties as:

let _: [String : protocol<Sortable, NSObjectProtocol>]