Sorting a Swift array by ordering from another array
Here's a generic Swift 5.2 solution.
First we need to define a protocol that holds a property that is used to reorder our elements:
protocol Reorderable {
associatedtype OrderElement: Equatable
var orderElement: OrderElement { get }
}
Then we need to extend Array with elements conforming to Reorderable and implement our reordering function:
extension Array where Element: Reorderable {
func reorder(by preferredOrder: [Element.OrderElement]) -> [Element] {
sorted {
guard let first = preferredOrder.firstIndex(of: $0.orderElement) else {
return false
}
guard let second = preferredOrder.firstIndex(of: $1.orderElement) else {
return true
}
return first < second
}
}
}
Example
Let's assume you have defined:
struct Player {
let position: String
}
let currentPositions = ["RB", "AA", "BB", "CC", "WR", "TE"]
let players = currentPositions.map { Player(position: $0) }
Now, all you need to do is conform Player to Reorderable:
extension Player: Reorderable {
typealias OrderElement = String
var orderElement: OrderElement { position }
}
You can now use:
let sortedPlayers = players.reorder(by: ["QB", "WR", "RB", "TE"])
print(sortedPlayers.map { $0.position })
// ["WR", "RB", "TE", "AA", "BB", "CC"]
Original Solution
This is a generic Swift 5.2 solution based on OuSS' code and requires array elements to be Equatable.
extension Array where Element: Equatable {
func reorder(by preferredOrder: [Element]) -> [Element] {
return self.sorted { (a, b) -> Bool in
guard let first = preferredOrder.firstIndex(of: a) else {
return false
}
guard let second = preferredOrder.firstIndex(of: b) else {
return true
}
return first < second
}
}
}
let currentPositions = ["RB", "AA", "BB", "CC", "WR", "TE"]
let preferredOrder = ["QB", "WR", "RB", "TE"]
let sorted = currentPositions.reorder(by: preferredOrder)
print(sorted) // ["WR", "RB", "TE", "AA", "BB", "CC"]
Edit: My original approach was shit. This post got a lot of traction, so it's time to give it some more attention and improve it.
Fundamentally, the problem is easy. We have two elements, and we have an array (or any ordered Collection) whose relative ordering determines their sort order. For every element, we find its position in the ordered collection, and compare the two indices to determine which is "greater".
However, if we naively do linear searches (e.g. Array.firstIndex(of:)), we'll get really bad performance (O(array.count)), particularly if the fixed ordering is very large. To remedy this, we can construct a Dictionary, that maps elements to their indices. The dictionary provides fast O(1) look-ups, which is perfect for the job.
This is exactly what HardCodedOrdering does. It pre-computes a dictionary of elements to their orderings, and provides an interface to compare 2 elements. Even better, it can be configured to respond differently to encountering elements with an unknown ordering. It could put them first before everything else, last after everything else, or crash entirely (the default behaviour).
HardCodedOrdering
public struct HardCodedOrdering<Element> where Element: Hashable {
public enum UnspecifiedItemSortingPolicy {
case first
case last
case assertAllItemsHaveDefinedSorting
}
private let ordering: [Element: Int]
private let sortingPolicy: UnspecifiedItemSortingPolicy
public init(
ordering: Element...,
sortUnspecifiedItems sortingPolicy: UnspecifiedItemSortingPolicy = .assertAllItemsHaveDefinedSorting
) {
self.init(ordering: ordering, sortUnspecifiedItems: sortingPolicy)
}
public init<S: Sequence>(
ordering: S,
sortUnspecifiedItems sortingPolicy: UnspecifiedItemSortingPolicy = .assertAllItemsHaveDefinedSorting
) where S.Element == Element {
self.ordering = Dictionary(uniqueKeysWithValues: zip(ordering, 1...))
self.sortingPolicy = sortingPolicy
}
private func sortKey(for element: Element) -> Int {
if let definedSortKey = self.ordering[element] { return definedSortKey }
switch sortingPolicy {
case .first: return Int.min
case .last: return Int.max
case .assertAllItemsHaveDefinedSorting:
fatalError("Found an element that does not have a defined ordering: \(element)")
}
}
public func contains(_ element: Element) -> Bool {
return self.ordering.keys.contains(element)
}
// For use in sorting a collection of `T`s by the value's yielded by `keyDeriver`.
// A throwing varient could be introduced, if necessary.
public func areInIncreasingOrder<T>(by keyDeriver: @escaping (T) -> Element) -> (T, T) -> Bool {
return { lhs, rhs in
self.sortKey(for: keyDeriver(lhs)) < self.sortKey(for: keyDeriver(rhs))
}
}
// For use in sorting a collection of `Element`s
public func areInIncreasingOrder(_ lhs: Element, rhs: Element) -> Bool {
return sortKey(for: lhs) < sortKey(for: rhs)
}
}
Example usage:
let rankOrdering = HardCodedOrdering(ordering: "Private", "Lieutenant", "Captain", "Admiral") // ideally, construct this once, cache it and share it
let someRanks = [
"Admiral", // Should be last (greatest)
"Gallactic Overlord", // fake, should be removed
"Private", // Should be first (least)
]
let realRanks = someRanks.lazy.filter(rankOrdering.contains)
let sortedRealRanks = realRanks.sorted(by: rankOrdering.areInIncreasingOrder) // works with mutating varient, `sort(by:)`, too.
print(sortedRealRanks) // => ["Private", "Admiral"]
SwifterSwift has this implementation
/// SwifterSwift: Sort an array like another array based on a key path. If the other array doesn't contain a certain value, it will be sorted last.
///
/// [MyStruct(x: 3), MyStruct(x: 1), MyStruct(x: 2)].sorted(like: [1, 2, 3], keyPath: \.x)
/// -> [MyStruct(x: 1), MyStruct(x: 2), MyStruct(x: 3)]
///
/// - Parameters:
/// - otherArray: array containing elements in the desired order.
/// - keyPath: keyPath indiciating the property that the array should be sorted by
/// - Returns: sorted array.
func sorted<T: Hashable>(like otherArray: [T], keyPath: KeyPath<Element, T>) -> [Element] {
let dict = otherArray.enumerated().reduce(into: [:]) { $0[$1.element] = $1.offset }
return sorted {
guard let thisIndex = dict[$0[keyPath: keyPath]] else { return false }
guard let otherIndex = dict[$1[keyPath: keyPath]] else { return true }
return thisIndex < otherIndex
}
}
Based on Alexander's answer, I've implemented an extension to do this.
extension Array where Element == String {
func reordered() -> [String] {
let defaultOrder = ["orange", "pear", "watermelon", "grapefruit", "apple", "lemon", "tomatoes"]
return self.sorted { (a, b) -> Bool in
if let first = defaultOrder.index(of: a), let second = defaultOrder.index(of: b) {
return first < second
}
return false
}
}
let arrayToSort = ["lemon", "watermelon", "tomatoes"]
let sortedArray = arrayToSort.reordered()
print(sortedArray) // ["watermelon", "lemon", "tomatoes"]