Best way to move an item to the start of a collection

Question

If I have a collection

let initial = [ "a", "b", "c", "d", "e" ]

and I wanted to move an item from that collection to the start (but keep the ordering of the other items intact)

let final = initial.placeFirst { $0 == "b" }
assert(final == [ "b", "a", "c", "d", "e" ])

What would be the best way to implement placeFirst?

My example has the elements as Equatable - that's just to make the question readable, it's sadly not the case in real life, hence a predicate passed into placeFirst which will return true for the item I want at the start.

For my use case there should only be one item which matches the predicate - if more than one matches then putting any (or some, or all) of the matching elements at the start is fine.

I have a few ideas, but it seems like the kind of problem there would be a really neat solution which uses bits of Collection/Sequence I'm not aware of yet.

PS I do realize how much this sounds like a homework question - I promise it's not :)

Answer 1

A possible implementation as a mutating method on RangeReplaceableCollection (Swift 3):

extension RangeReplaceableCollection {
    mutating func placeFirst(where predicate: (Iterator.Element) -> Bool) {
        if let index = index(where: predicate) {
            insert(remove(at: index), at: startIndex)
        }
    }
}

Example:

var array = [ "a", "b", "c", "d", "e" ]
array.placeFirst(where: { $0 == "b" })
print(array) // ["b", "a", "c", "d", "e"]

Similar as in How do I shuffle an array in Swift? you can add a non-mutating method taking an arbitrary sequence and returning an array:

extension Sequence {
    func placingFirst(where predicate: (Iterator.Element) -> Bool) -> [Iterator.Element] {
        var result = Array(self)
        result.placeFirst(where: predicate)
        return result
    }
}

Example:

let initial = [ "a", "b", "c", "d", "e" ]
let final = initial.placingFirst { $0 == "b" }
print(final) // ["b", "a", "c", "d", "e"]

Answer 2

A possible implementation as a pair of mutating methods on MutableCollection (doesn't require the resizing of the collection):

extension MutableCollection {

    mutating func placeFirst(from index: Index) {

        var i = startIndex

        while i < index {
            swap(&self[i], &self[index]) // in Swift 4: swapAt(i, index)
            formIndex(after: &i)
        }
    }

    //                      in Swift 4, remove Iterator.
    mutating func placeFirst(where predicate: (Iterator.Element) throws -> Bool) rethrows {

        var i = startIndex

        while i < endIndex {
            if try predicate(self[i]) {
                placeFirst(from: i)
            }
            formIndex(after: &i)
        }
    }
}

var initial = ["a", "b", "c", "d", "e", "c", "q"]
initial.placeFirst(where: { $0 == "c" })
print(initial) // ["c", "c", "a", "b", "d", "e", "q"]

In placeFirst(from:), we just take a single index, and swap all the elements from the start index up to the desired index, effectively placing the element at the given index at the start, and "shifting" the remaining elements up.

Then in the predicate version, placeFirst(where:), we iterate through and check the predicate against all the indices of the collection, calling onto placeFirst(from:) if we find a match.

And as Martin says, a non-mutating variant for all sequences can be created easily by first constructing an Array:

extension Sequence {

    // in Swift 4, remove Iterator.
    func placingFirst(
        where predicate: (Iterator.Element) throws -> Bool
        ) rethrows -> [Iterator.Element] {

        var result = Array(self)
        try result.placeFirst(where: predicate)
        return result
    }
}

let initial = ["a", "b", "c", "d", "e", "c", "q"]
let final = initial.placingFirst(where: { $0 == "c" })
print(final) // ["c", "c", "a", "b", "d", "e", "q"]

---

In order to benchmark against Martin's implementation, I changed the implementation of my placeFirst(where:) to only consider the first element that the predicate matches, such that both implementations short-circuit:

extension MutableCollection {

    mutating func placeFirstSwap(from index: Index) {

        var i = startIndex

        while i < index {
            swapAt(i, index)
            formIndex(after: &i)
        }
    }

    mutating func placeFirstSwap(where predicate: (Iterator.Element) throws -> Bool) rethrows {

        if let index = try index(where: predicate) {
            placeFirstSwap(from: index)
        }
    }

}

extension RangeReplaceableCollection {
    mutating func placeFirstInsertRemove(where predicate: (Iterator.Element) throws -> Bool) rethrows {
        if let index = try index(where: predicate) {
            insert(remove(at: index), at: startIndex)
        }
    }
}

extension Sequence {
    func placingFirstInsertRemove(where predicate: (Iterator.Element) throws -> Bool) rethrows -> [Iterator.Element] {
        var result = Array(self)
        try result.placeFirstInsertRemove(where: predicate)
        return result
    }

    func placingFirstSwap(where predicate: (Iterator.Element) throws -> Bool) rethrows -> [Iterator.Element] {
        var result = Array(self)
        try result.placeFirstSwap(where: predicate)
        return result
    }
}

Then, with the following setup in a Swift 4 release build:

import Foundation

let a = Array(0 ... 50_000_000)

let i = 33_000_000

print("pivot \(100 * Double(i) / Double(a.count - 1))% through array")

do {
    let date = Date()
    let final = a.placingFirstInsertRemove(where: { $0 == i })
    print(final.count, "Martin's:", Date().timeIntervalSince(date))
}

do {
    let date = Date()
    let final = a.placingFirstSwap(where: { $0 == i })
    print(final.count, "Hamish's:", Date().timeIntervalSince(date))
}

print("---")

do {
    let date = Date()
    let final = a.placingFirstInsertRemove(where: { $0 == i })
    print(final.count, "Martin's:", Date().timeIntervalSince(date))
}

do {
    let date = Date()
    let final = a.placingFirstSwap(where: { $0 == i })
    print(final.count, "Hamish's:", Date().timeIntervalSince(date))
}

When i is around 33_000_000, both implementations appear to have similar performance:

pivot 66.0% through array
50000001 Martin's: 0.344986021518707
50000001 Hamish's: 0.358841001987457
---
50000001 Martin's: 0.310263991355896
50000001 Hamish's: 0.313731968402863

With Martin's performing slightly better for values of i over this, e.g with i = 45_000_000:

pivot 90.0% through array
50000001 Martin's: 0.35604602098465
50000001 Hamish's: 0.392504990100861
---
50000001 Martin's: 0.321934998035431
50000001 Hamish's: 0.342424035072327

and mine performing slightly better for values of i less than this, e.g with i = 5_000_000:

pivot 10.0% through array
50000001 Martin's: 0.368523001670837
50000001 Hamish's: 0.271382987499237
---
50000001 Martin's: 0.289749026298523
50000001 Hamish's: 0.261726975440979

In all of these results, the second pair is generally more reliable, as both should benefit from branch prediction done by the first run.