Quick sort by custom types

Question

I have a set of instances of type Thingie , and I want to provide Thingies arrays sorted by any Thingie property. Some of the properties are Int, for example, while others are String, and there may be others. So I wanted to create a sorting procedure that takes a string as the name of a property and compares two properties of two objects to determine the order.

It seemed like work for generics, and I'm getting closer, but there is a hole there.

Here where I am 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 generic comparison function and call it in my sort. The trick is that AnyObject! will not work for my generic type, so I need to specify the values ​​returned from a[sortField] and b[sortField] same type. It does not even matter which type as long as the compiler is happy that both values ​​are of the same type and that it implements the Comparable protocol.

I thought that typalism would do the trick, but maybe the best way?

Side question: There is probably a better way to create a source, unsorted array from a set without resorting to NSSet. A little hint. [Decided that a bit! Thanks, Oliver Atkinson!]

Here is a big piece of code that you can insert into the playing field. It has three attempts to implement orderBy, each of which has 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 eg, 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, although it works, does not do its best possible Swift validator. It also switches between types that can be used in one centralized location, which limits extensibility for the frame owner.

The following approach solves these problems. (Please forgive me for not having a heart to delete my previous answer, let's say that these limitations are instructive ...)

As before, we will 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 for mutable collections (which will work for both sets and 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 } } } 

Obviously, the whole idea revolves around this Sortable protocol:

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

... that can be matched independently by whatever 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 simply an extension of the Sortable convenience:

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

What is it. Now we can map new types to Sortable even outside the box, and type checking checks the source data [[String:Sortable]] at compile time. Also, if Thing expands to match Hashable , then Set<Thing> will also sort by key ...

Note that although Sortable itself has no limitations (which is surprising), the data and Thing properties source can be bound to dictionaries with NSObject or AnyObject , if required, using a protocol, for example:

 protocol SortableNSObjectType : Sortable, NSObjectProtocol { } 

... or more, declaring data and Thing properties as:

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

Answer 2

I do not know the implementation of Thingie , but perhaps you could provide more context.

You could go for something like this

 func orderBy(sortField: String) -> [Thingie] { return thingies.allObjects.map { $0 as! Thingie }.sort { $0[sortField] < $1[sortField] } } 

If you can provide an example of a playground, I can provide additional help.

Also why did you use NSSet and not speed dial? it will give you what you want

 let thingies: Set = Set<Thingie>() func orderBy(sortField: String) -> [Thingie] { return thingies.sort { $0[sortField] < $1[sortField] } } 

edit:

The security problem is of fast type - it requires you to know what types you are dealing with so that it can compile correctly - if you specify the actual type, when you want to order a field, you can make it work properly.

 func orderByField<T: Comparable>(sortField: String, type: T.Type) -> [Thingie] { return thingies.sort { ($0[sortField] as? T) < ($1[sortField] as? T) } } var thingieList: Array = orderByField("id", type: Int.self); print(thingieList[0]["id"]) var thingieList2: Array = orderByField("description", type: String.self); print(thingieList2[0]["id"]) 

Above will be printed 2, and then 11 - if you want to get around this, you can save your objects in a different structure, and then you can sort the array of "Things" in a variable.

eg.

 struct Thing { let id: Int let description: String } var data: [Thing] = [ Thing(id: 2, description: "two"), Thing(id: 11, description: "eleven") ] let first = data.sort { $0.id < $1.id }.first?.id let second = data.sort { $0.description < $1.description }.first?.id print(first) print(second) 

To achieve the same - 2 and 11

I would advise against using AnyObject where possible, as he is trying to trick the compiler by telling him that you don't need his help.

This is an interesting problem, although I hope this helps you in solving the problem.

Answer 3

I will start with the target API (ignoring the Hashable , since adding it will not change anything in the future). So let me say that we would like to write the following:

 var thingies = [ ["id": 1, "description": "one"], ["id": 2, "description": "two"], ["id": 3, "description": "three"], ["id": 4, "description": "four"] ].map(Thingie.init) thingies.sortInPlace{ $0["id"] < $1["id"] } 

... and even:

 thingies.sortInPlaceBy("id") thingies .map{ $0["id"]!.value } // [1, 2, 3, 4] thingies.sortInPlaceBy("description") thingies .map{ $0["description"]!.value } // ["four", "one", "three", "two"] 

Obviously, we will need the MutableCollectionType protocol extension MutableCollectionType by line:

 protocol ThingieDatumSubscriptable { subscript(_: String) -> ThingieDatum? { get } } extension Thingie : ThingieDatumSubscriptable {} extension MutableCollectionType where Index : RandomAccessIndexType, Generator.Element : ThingieDatumSubscriptable { mutating func sortInPlaceBy(datumName: String, ascending: Bool = true) { let f: (ThingieDatum?, ThingieDatum?) -> Bool = ascending ? (<) : (>) sortInPlace{ f($0[datumName], $1[datumName]) } } } 

This ThingieDatum will be something like:

 import Foundation struct ThingieDatum : Comparable { let type: AnyObject.Type let value: AnyObject let name: String init(keyValuePair: (String, AnyObject)) { name = keyValuePair.0 value = keyValuePair.1 type = keyValuePair.1.dynamicType } } 

... and its Comparable compliance Comparable implemented in some pedestrian way as follows (unless we introduce more protocols):

 func == (lhs: ThingieDatum, rhs: ThingieDatum) -> Bool { guard lhs.name == rhs.name && lhs.type == rhs.type else { return false } switch lhs.type { // TODO: implement for other types case is NSNumber.Type: return lhs.value as! NSNumber == rhs.value as! NSNumber case is NSString.Type: return (lhs.value as! String) == (rhs.value as! String) default: break } return false } func < (lhs: ThingieDatum, rhs: ThingieDatum) -> Bool { assert(lhs.name == rhs.name && lhs.type == rhs.type) switch lhs.type { // TODO: implement for other types case is NSNumber.Type: return (lhs.value as! NSNumber).doubleValue < (rhs.value as! NSNumber).doubleValue case is NSString.Type: return (lhs.value as! String) < (rhs.value as! String) default: break } return false } 

Armed with such a ThingieDatum , we can finally work out Thingie himself:

 struct Thingie { var data: [ThingieDatum] init(_ data: [String: AnyObject]) { self.data = data.map(ThingieDatum.init) } subscript(datumName: String) -> ThingieDatum? { for datum in data where datum.name == datumName { return datum } return nil } } 

And although this, of course, is all meant as a fun exercise, it really works (copy and paste into the playground, if you can work with our correct order of fragments) ... However, to accept this idea, we probably would like to limit ThingiDatum initialization ThingiDatum special protocol (not AnyObject ), which would guarantee compatibility. Then we would coordinate this protocol with each type that we want to work with, instead of switch through these types in one centralized place ...