I'd like to have a script that lets me spin up a few Docker containers (one per supported Swift version) and run the tests on Linux with a single command. We can use the existing travis-build-script.sh for inspiration.

Because we're still supporting Swift 4.0, these should be gated with #if swift(>=4.1).

Apple has a new automatic check when validating the binary that was built using Xcode 9 / iOS 11 SDK. If the binary contains some code coverage instrumentation, it will be rejected. The full message is:

Invalid Bundle - Disallowed LLVM instrumentation. Do not submit apps with
LLVM profiling instrumentation or coverage collection enabled. Turn off
LLVM profiling or code coverage, rebuild your app and resubmit the app.

Can we have this available on cocoa pods as well please?

    public func last(where predicate: (Element) throws -> Bool) rethrows -> Element? {
        guard let index = try firstIndex(where: predicate) else { return nil }
        return self[index]
    }

presumably should be lastIndex(where:...)

I was surprised to find that the sort position of an element is also being used to determine element equality. This is can be seen with the following test case:

    func testEqualityVsSortPosition() {
        struct Item: Equatable {
            let id: String
            let name: String
        }

        let item1 = Item(id: "1", name: "Bumble")
        let item2 = Item(id: "2", name: "Bumble") // two items with same name, but not Equality
        let item3 = Item(id: "3", name: "Fumble")
        let item4 = Item(id: "4", name: "Grumble")

        // array is missing item 2
        var array = SortedArray(unsorted: [item1, item3, item4], areInIncreasingOrder: { $0.name < $1.name })

        // correctly find item 1
        XCTAssertTrue(array.contains(item1))       // passes
        // incorrectly find item 2
        XCTAssertFalse(array.contains(item2))      // fails

        XCTAssertNil(array.index(of: item2))       // fails
        XCTAssertNil(array.anyIndex(of: item2))    // fails
        XCTAssertNil(array.firstIndex(of: item2))  // fails
        XCTAssertNil(array.lastIndex(of: item2))   // fails

        let countBefore = array.count
        array.remove(item2)
        let countAfter = array.count
        XCTAssertEqual(countBefore, countAfter) // fails
    }

I would expect methods like remove(_ element: Element) to only remove if the elements are actually equal, not just if they're sorted into the same place. This method has the same signature as the one on Set, but behaves very differently.

A workaround is to define the sort function to take equality into account. I don't believe it's intuitive to consider objects sorted to the same index as also being Equal. At a minimum this should be better documented. I'd suggest to either update the functionality to take Equatable conformance into account, or change the method names to make it clear its acting on sort order not equality.

The comment suggests that insertion in Swift arrays is sometimes cheaper than a full copy.

The standard doc is not helpful; they only report the "Big-Oh".

Apparently, at least back in 2016, appending elements is cheap if contiguous memory can be allocated after the current buffer; if not, there'd be a full copy.

It seems reasonable to assume that insertion could be similarly sped up, for a total cost of

• T_search(n) + T_extend + (n-i)*T_swap in the good case, and
• T_search + T_copy(n) in the bad case (no matter at which index we insert).

Hello,
I think the algorithm :

fileprivate func search(for newElement: Element) -> Match<Index> {
    guard !isEmpty else { return .notFound(insertAt: endIndex) }
    var left = startIndex
    var right = index(before: endIndex)
    while left <= right {
        let dist = distance(from: left, to: right)
        let mid = index(left, offsetBy: dist/2)
        let candidate = self[mid]

        if areInIncreasingOrder(candidate, newElement) {
            left = index(after: mid)
        } else if areInIncreasingOrder(newElement, candidate) {
            right = index(before: mid)
        } else {
            // If neither element comes before the other, they _must_ be
            // equal, per the strict ordering requirement of `areInIncreasingOrder`.
            return .found(at: mid)
        }
    }
    // Not found. left is the index where this element should be placed if it were inserted.
    return .notFound(insertAt: left)
}

Doesn't take into account the case where duplicate keys are present. In particular, in calculating the mid point, it'll give the index value of the first occurence of newElement == candidate, not the smallest index.

As a result, enumerating all keys verifying k == 0 (for example), will fail. One has to find the lowest value for which areInIncreasingOrder(candidate, newElement) == true and areInIncreasingOrder(newElement, candidate + 1) == false.

If I find a quick solution, I'll let you know.