IMO the port of the original Swift implementation made the name gratuitously worse. Aside from being precedented partitionPoint is shorter and more wieldy, not any easier to misinterpret, a natural name (it was chosen totally independently for the algorithm in C++) and doesn't make the type name Index more significant than it should be. The addition of ing in particular turns what can be read as a pure noun—a thing—into something that is definitely the noun form of a verb—an action—thus making this algorithm seem like it has something to do with partitioning when it does not.

Thanks for this amazing framework ✌️.

Well, my request relates to the framework Charts which is very popular with more than 20k stars.

With the latest version, this framework has been integrated via SPM. However, this framework does not support CocoPods here. As a result, this popular framework can no longer be installed via Cocoapods.

I would therefore wish that this framework could also be integrated via CocoaPods.

The function that was used is unknown on my side ?
I use Swift 5.3 and Xcode 12.3, macOS 11.1

I have a daily CI that cross-compiles this package for Android along with swift-numerics trunk: it broke because of this update today.

Swift Algorithms version: main branch, but only when forced to build against swift-numerics' latest commit.
Swift version: 5.4.2 and the latest 5.5 and trunk development snapshots

Checklist

• If possible, I've reproduced the issue using the main branch of this package
• I've searched for existing GitHub issues

Steps to Reproduce

Check out trunk of this package and swift-numerics and force this package to use that one by replacing the online checkout with .package(path: "../swift-numerics"),.

Expected behavior

Builds as normal.

Actual behavior

error: product 'RealModule' not found in package 'swift-numerics'. it is required by package 'swift-algorithms' target 'Algorithms'.

Also, the current swift-numerics checkout of 0.0.1 that's normally used is two years old, should also update that.

While benchmarking a different project, I noticed that the compilation / type checking of StrideCollection.offsetBackward is the bottleneck when building swift-algorithms. On a 2019 8 Core MacBook Pro using Xcode 12.4 a small refactor reduced compiling Stride.swift from 6.5s -> 1s, so that it is no longer the bottleneck in the build graph.

Swift Algorithms version: 0.2.1/ main
Swift version:

Apple Swift version 5.3.2 (swiftlang-1200.0.45 clang-1200.0.32.28)
Target: x86_64-apple-darwin19.6.0

Checklist

• If possible, I've reproduced the issue using the main branch of this package
• I've searched for existing GitHub issues

Steps to Reproduce

• Install and select the 5.3.2 toolchain
• Update package.swift to include debug flags below
• Compile in Xcode and navigate to Stride.swift -> StrideCollection.offsetBackward
• View issues in Xcode
• (Optional) Run xclogparser parse --project swift-algorithms --reporter html to generate the screenshots below
  • https://github.com/MobileNativeFoundation/XCLogParser

targets: [
    .target(
      name: "Algorithms",
      dependencies: [
        .product(name: "RealModule", package: "swift-numerics"),
      ],
      swiftSettings: [.unsafeFlags([
        "-driver-time-compilation",
        "-Xfrontend",
        "-debug-time-compilation",
        "-Xfrontend",
        "-debug-time-function-bodies",
        "-Xfrontend",
        "-debug-time-expression-type-checking",
        "-Xfrontend",
        "-warn-long-function-bodies=500",
        "-Xfrontend",
        "-warn-long-expression-type-checking=500",
      ])]),
    .testTarget(
      name: "SwiftAlgorithmsTests",
      dependencies: ["Algorithms"]),
  ]

Screenshots

Before	After

Proposed fix

-    let distance = i == endIndex
-      ? -((base.count - 1) % stride + 1) + (n - 1) * -stride
-      : n * -stride
+    // We typically use the ternary operator but that stresses out the compiler.
+    // To avoid slow build times for consumers, we use the longhand below.
+    let distance: Int
+    if i == endIndex {
+      distance = -((base.count - 1) % stride + 1) + (n - 1) * -stride
+    } else {
+      distance = n * -stride
+    }

Expected behavior

Users build time shouldn't be unnecessarily impacted by using swift-algorithms.

Actual behavior

Builds for consumers are slower than necessary. As swift-algorithms is likely to be early in a dependency graph, this is likely to affect users overall build times.

The documentation of chunked(by:) states that the predicate is evaluated on consecutive elements. Experience and a naive look at the source are suggesting it is evaluated using the first element of the chunk instead of the previous one.

Steps to Reproduce

Let a: [Int] = [1,2,3,4,6,7,8,9] ("5" is missing). We want to chunk a such as two consecutive elements are consecutive numbers (their difference is exactly 1).

Expected behavior

[1,2,3,4,6,7,8,9].chunked(by: { $1 - $0 == 1 }) == [[1, 2, 3, 4], [6, 7, 8, 9]]

Actual behavior

[1,2,3,4,6,7,8,9].chunked(by: { $1 - $0 == 1 }) == [[1, 2], [3, 4], [6, 7], [8, 9]]

Am I understanding the documentation incorrectly, or is there an inconsistency between the documentation and the expected behavior?

In c++ there has a stl function named as lower_bound which works as binary search. But in swift there has no such function. Could you please add it?

Our test suite contains the XCTAssertEqualSequences function which tests whether two sequences have equal elements, either based on Equatable conformance or using a custom predicate. It's currently implemented in terms of the elementsEqual method on Sequence which only returns whether or not the two sequences have equal elements.

For our purposes, when the two sequences are different, it would not only be useful to know that they are different, but also how they are different. Either the elements at the same position in the respective sequences aren't equal, or one of the sequences is shorter than the other one. XCTAssertEqualSequences should be changed to log this information to make debugging a bit easier.

Many iOS developer use cocoapods in their project. So i think it would be convenient if you add cocoapods feature.
Thanks

Xcode 14, target iOS is 14.1

When using a combinations in a playground, I get this error -

error: Test.playground:301:30: error: value of type '[Double]' has no member 'combinations' for combo in combos.combinations(ofCount: 1...4) {

Now where else to turn. It seems that the package is successfully added to the project. The playground is in the project with the dependancy added.

The import statement is there.
import Algorithms

Growl, not sure who else to ask?

In the (only) implementation of XCTAssertUnorderedEqualSequences (where elements are Equatable), it converts the sequence into an Array. Then it iterates through the second sequence, calling firstIndex(of:) on the first array (O(n)), which totals to O(n²). If a Set were used (when the elements are Hashable), then getting the index of an element is O(1), which would make the total algorithmic complexity O(n).

Expected behavior

XCTAssertUnorderedEqualSequences is O(n) when Element: Hashable

Actual behavior

XCTAssertUnorderedEqualSequences is O(n²) when Element: Hashable

Sorry if this is the wrong place to ask, but I didn’t know anywhere else to ask. 😂

I am a long time iOS Swift/ObjC developer and I have been looking to get involved contributing to this repo (I use it in a project currently) but looks like all the good-first-issue labelled issues have been taken.

I wasn’t sure if the starter issue labels get updated on a regular basis (or if there is a Jira board that I don’t know about) so wanted to ask just in case (I am very keen). Are there any new features or improvements I could try to take as a good first issue?

Thanks a lot for the great work, and in advance for the help. Can’t wait to use this in the standard library when this becomes live! 😊

In #4 the implementation of trimmed(where:) requires a raw loop because using lastIndex(where:) would require making an extra call to index(after:) to advanced the returned index.

The embracing algorithms talk exhibits the need for the dual—the index before firstIndex(where:)—to avoid a raw loop or an extra call to index(before:):

extension MutableCollection {
    mutating func bringForward(elementsSatisfying predicate: (Element) -> Bool) {
        if let predecessor = indexBeforeFirst(where: predicate) {
            self[predecessor...].stablePartition(isSuffixElement: { !predicate($0) })
        }
    }
}

extension Collection {
    func indexBeforeFirst(where predicate: (Element) -> Bool) -> Index? {
        return indices.first {
            let successor = index(after: $0)
            return successor != endIndex && predicate(self[successor])
        }
    } 
}

These use cases seem like sufficient justification to add these algorithms.

Though I wonder if indexBeforeFirst(where:)/indexAfterLast(where:) or firstIndex(before:)/lastIndex(after:) or some other naming scheme is best?

Several of the sequence/collection wrappers provide public access to the collection that they wrap, which can end up raising questions about substitutability and isn't strictly necessary. We should make all of these internal, instead.

Recently we've been exploring at FilePath APIs for Swift System, including extension:

let path: FilePath = "/tmp/archive.tar.gz"
print(path.stem!)
print(path.extension!)
// Prints "archive.tar"
// Prints "gz"

For more complicated cases, a lazy version of the existing split algorithm could be a handy and efficient (no heap allocations!) way to operate on a path with multiple extensions:

let path: FilePath = "/tmp/archive.tar.gz"
for component in path.basename!.string.lazy.split(separator: ".") {
    print(component)
}
// Prints "archive"
// Prints "tar"
// Prints "gz"

Using the mutating partitioning functions are useful even when the returned index isn’t used.

The Embracing Algorithms (WWDC 2018) session implements a bringForward(elementsSatisfying:) function on MutableCollection.¹ It uses stablePartition(by:) in its implementation, but doesn’t need its return value, resulting in a warning.

Actual behavior

extension MutableCollection {
	mutating func bringForward(elementsSatisfying predicate: (Element) -> Bool) {
		if let predecessor = indexBeforeFirst(where: predicate) {
			self[predecessor...].stablePartition(by: { !predicate($0) }) // ⚠️ Result of call to 'stablePartition(by:)' is unused
		}
	}
}

Expected behavior

extension MutableCollection {
	mutating func bringForward(elementsSatisfying predicate: (Element) -> Bool) {
		if let predecessor = indexBeforeFirst(where: predicate) {
			self[predecessor...].stablePartition(by: { !predicate($0) })
		}
	}
}

While it could be argued that bringForward(elementsSatisfying:) should return an Index as well, even that return value isn’t always needed to be used and should be marked as @discardableResult.

Checklist

• If possible, I've reproduced the issue using the main branch of this package
• I've searched for existing GitHub issues

1. This implementation function can be seen on page 218 of the presentation slides PDF.

cycled(times:) is currently implemented as follows:

extension Collection {
  public func cycled(times: Int) -> FlattenSequence<Repeated<Self>> {
    repeatElement(self, count: times).joined()
  }
}

This is suboptimal because FlattenSequence does not conform to RandomAccessCollection when the base collection does, even though the return value of cycled(times:) could! By implementing this method in terms of FlattenSequence, we are essentially throwing away the information that each inner collection is the same (and therefore has the same length).

Another way of repeating a collection a fixed number of times is by taking the product of it and an integer range:

let array = [10, 20, 30]
for (_, x) in product(0..<5, array) {
  print(x)  // 10, 20, 30, 10, 20, 30, 10, 20, 30, 10, 20, 30, 10, 20, 30
}

Unlike FlattenSequence, the Product2 collection does conditionally conform to RandomAccessCollection.

We should add a new FiniteCycle collection as the return type of product(times:) that wraps a Product2<Range<Int>, Base> value and conforms to RandomAccessCollection.

The issue here is x86_64 simulator is not supported as it hinders development using SwiftUI project. This issue is there in every release.

You can reproduce this by adding settings in build settings

This setting is required other spm to compile.

When adding this setting simulator must compile and run.

Just helps new starters to get started with how to contribute when opening a PR. I am happy to attempt this.

Screenshot of Contribution Guidelines hyperlink:

Checklist

• If possible, I've reproduced the issue using the main branch of this package
• I've searched for existing GitHub issues

Steps to Reproduce

The link should be (I think): https://github.com/apple/swift-algorithms/blob/main/CONTRIBUTING.md
Actual: https://github.com/apple/swift-algorithms/CONTRIBUTING.md <-- This is broken for #133

Expected behavior

Open Markdown file for Contribution Guidelines.

Actual behavior

We currently provide just one way to trim a collection:

extension BidirectionalCollection {
  public func trimming(
    while predicate: (Element) throws -> Bool
  ) rethrows -> SubSequence {
    let start = try endOfPrefix(while: predicate)
    let end = try self[start...].startOfSuffix(while: predicate)
    return self[start..<end]
  }
}

We should also provide ways to trim only the start of the collection (trimmingPrefix(while:), available to all collections), or only the end (trimmingSuffix(while:)).

Furthermore, collections for which Self == SubSequence should have mutating variants using trim as the base name. As an example, Collection's popFirst() from the standard library is implemented using the same constraint.

And finally, despite String not being its own SubSequence, String should also have access to these mutating variants for the sake of convenience.

Some of the algorithms in this package have a return value that might not be needed by the caller. It would be nice if these were marked as @ discardableResult so that callers don't have to use _ = to silence Xcode warnings.

For example, stablePartition returns the start of the resulting suffix, which might not be of interest to a caller who's only interested in the final result.

Here's a checklist of the remaining work to do for the next Algorithms release:

• Add guides for suffix(while:) and any other new methods: #82
• Rename sortedPrefix: #77
• Rename slidingWindows: #79
• Audit inlinability annotations throughout: #83
• Verify that all methods are called out in the README
• Update the CHANGELOG

Hi!

TL;DR - permutations(ofCount:) is slow in debug builds, taking tens of seconds vs explicit nested for loops taking a fraction of a second. Release builds are fine. Hopefully there's a way to mitigate this problem in debug builds so I can use the algorithm along with being able to use the debugger.

(also, in retrospect, I am confusing permutations and combinations, so I should have used combination here %-) It works fine in Debug-mode. But the issue still stands of the long time to do the permutation work in debug-land)

Using version 0.2.1

Checklist

• If possible, I've reproduced the issue using the main branch of this package. I have not, but notice that there aren't any changes since 0.2.1 was cut
• I've searched for existing GitHub issues

Steps to Reproduce

Attached is a project you can run. Look in ContentView.swift for aoc1_2 and use the #if there to choose between the permutations version and one that's nested for loops. Run and click the Permute button to run.

TL;DR:

From AdventOfCode 2020, day 1: https://adventofcode.com/2020/day/1 with a 200 element array. Find the triple of elements in the array that add to 2020, then return their product.

    for perm in stuff.permutations(ofCount: 3) {
        if perm[0] + perm[1] + perm[2] == 2020 {
            let solution = perm[0] * perm[1] * perm[2]
            print("FOUND IT \(solution)")
            break
        }

Expected behavior

The permutations runs in amount of time similar to a simple for-loop equivalent

Actual behavior

In Debug mode, it's two orders of magnitude slower, due of course to Swift's lack of optimizations to enhance debuggability. It'd be nice if it were possible to use this algorithm (maybe others? I haven't investigated any others yet) in a debuggable environment. Right now, waiting 25+ seconds for each edit/run/test/curse cycle is a long time.

In release mode, the times are short enough to where it doesn't impact workflow (outside of not being able to debug things outside of print statements)

Sample project:
Permutation.zip

Instruments profile of a Debug build.
Permutations-instruments.trace.zip . just a quick glance, a lot of time is spent in memory (nanov2) allocation

My timing results

// Xcode 12.2, MacBook Pro (16-inch, 2019), Catalina
// debug mode
//     permutations - 22.7 seconds
//     for loops - 0.25 seconds
// release mode
//     permutations - 0.25 seconds
//     for loops - 0.002 seconds
//
// Xcode 13-beta-1, M1 mini, Big Sur.
// debug mode
//     permutations - 9.2 seconds
//     for loops - 0.113 seconds
// release mode
//     permutations - 0.127 seconds
//     for loops - 0.001 seconds

The libray doesn't compile under Xcode 14 and iOS 16 beta 4

Swift Algorithms version: 1.0.0

Checklist

• [x ] If possible, I've reproduced the issue using the main branch of this package
• I've searched for existing GitHub issues

Recently we've been exploring at FilePath APIs for Swift System, including extension:

let path: FilePath = "/tmp/archive.tar.gz"
print(path.stem!)
print(path.extension!)
// Prints "archive.tar"
// Prints "gz"

For more complicated cases, a lazy version of the existing split algorithm could be a handy and efficient (no heap allocations!) way to operate on a path with multiple extensions:

let path: FilePath = "/tmp/archive.tar.gz"
for component in path.basename!.string.lazy.split(separator: ".") {
    print(component)
}
// Prints "archive"
// Prints "tar"
// Prints "gz"

I regularly find myself wanting to sum all the (numeric) elements in a Set, Array or other Collections. This made me think about whether adding a simple wrapper in the standard library for the sum and product operations, something along the lines of:

collection.reduce(0,+) for Sums
and
collection.reduce(0,*) for Products

(only for collections where Element: Numeric)

could be more clearer to write. In terms of implementation details, this is purely additive.

I don't know whether reduce would be the best way to implement this, but would be open to feedback on this. Might be a good starter issue?

When doing macOS or iOS programming, a common use-case I have for interspersed is to insert a separator or divider view in-between a bunch of other views.

Example, given an array of views, I'd like to insert a separator view in-between each one:

let views = [view1, view2, view3]

let allViews = views.interspersed(using: { SeparatorView() })

Expected:

[view1, separator1, view2, separator2, view3]

Because these are NSView, the inserted element needs to be a new instance each time, which the existing implementation does not appear to offer.

I found myself often having to find the first element in an array that passes an optional initialiser.
If I wanted to stick to a purely functional paradigm (which I do, I'm a zealot) I need to do some pretty not-ideal transforms to allow this behaviour without defining a new function.

let value = ["Hello", "10"].lazy.map(Int.init).first { $0 != nil }.flatMap { $0 }

This could be trivialised with the following (naive) implementation.

public extension Sequence {
    /// Returns the first element in `self` that `transform` maps to a `.some`.
    func first<Result>(of transform: (Element) throws -> Result?) rethrows -> Result? {
        for value in self {
            if let value = try transform(value) {
                return value
            }
        }
        return nil
    }
}

I was playing around with your package and decided to take a look at a Windows example. After setting a very simple playground and trying this example, I can not build it. Instead of building it, it throws the next error:

/path/to/playground/main.swift:5:32: error: value of type 'String' has no member 'windows'
let windowed: [String] = swift.windows(ofCount: 2)

First of all, I thought that there is something on my end, however, other examples work fine(I've tried this and this)

Swift Algorithms version: 0.0.2
Swift version: Apple Swift version 5.3.2 (swiftlang-1200.0.45 clang-1200.0.32.28) Target: x86_64-apple-darwin20.3.0

Checklist

• If possible, I've reproduced the issue using the main branch of this package
• I've searched for existing GitHub issues

Steps to Reproduce

Here is my Package.swift:

import PackageDescription

let package = Package(
    name: "playground",
    dependencies: [
        .package(url: "https://github.com/apple/swift-algorithms", from: "0.0.2"),
    ],
    targets: [
        .target(
            name: "playground",
            dependencies: [
                .product(name: "Algorithms", package: "swift-algorithms"),
            ],
            path: "Sources/playground"
            ),
    ]
)

and main.swift:

import Foundation
import Algorithms
let swift = "swift"

let windowed: [String] = swift.windows(ofCount: 2) 
print(windowed)

Expected behavior

I expected to see the next result: ["sw", "wi", "if", "ft"]

Actual behavior

I get the error after running swift build:

/path/to/playground/main.swift:5:32: error: value of type 'String' has no member 'windows'
let windowed: [String] = swift.windows(ofCount: 2)

I remember scan(_:combine:) not making the cut on the grounds of offering low utility. Is it possible for it to find a place here?

Now we have randomSample method for collections to get multiple random elements of a specific number with orders shuffled. This behavior should make it easy to make a shuffle method, which don't have to take any parameters (or a generator, if needed) to shuffle the collection. Inside the shuffle method, we just have to call randomSample(count: self.count) and it should work as expected:

let aCollection = [1, 2, 3, 4, 5]
let shuffled = aCollection.shuffled()
// ↑ which should be identical with `aCollection.randomSample(count: aCollection.count)`

In the documentation for partitioningIndex(where:), it only mentions what happens when the predicate returns true. But, if the predicate returns false in all cases, it is unclear what the return value is. The documentation should be written so that it is clear that the return value is endIndex if belongsInSecondPartition returns false for all elements.

I think this should at least be reflected in the “Returns” section of the inline documentation, but could probably be made more clear by rephrasing the first few sentences. The first sentence makes it sound like this is identical to firstIndex(where:), but the second and third sentences make the behavior more clear, indicating that this function is only to be used on collections that have already been partitioned.

GitHub has lots of really handy bots that integrate with pushed commits and PR actions, as well as GitHub Actions CI. I have used GitHub’s bots in my own projects and found them very secure, helpful and easy to integrate.

I have raised #133 re: [ImgBot] but I am open to your feedback on more general Bot integrations as well.

Thanks.

With dictionaries, we have a uniquingKeysWith parameter. It would be helpful to have similar for uniqued.

This came up in a Stack Overflow Q/A. The following works but relies on arrays—we should have something better in Algorithms.

import struct OrderedCollections.OrderedDictionary

public extension Sequence {
  @inlinable func uniqued<Subject: Hashable>(
    on projection: (Element) throws -> Subject,
    uniquingWith combine: (Element, Element) throws -> Element
  ) rethrows -> [Element] {
    try OrderedDictionary(keyed(by: projection), uniquingKeysWith: combine)
      .values
      .elements
  }
}

public extension Sequence {
  @inlinable func keyed<Key: Hashable>(
    by key: (Element) throws -> Key
  ) rethrows -> [KeyValuePairs<Key, Element>.Element] {
    try map { (try key($0), $0) }
  }
}

One of the most common uses of compactMap is to just flatten the nils out of a sequence without transforming its elements, i.e. x.lazy.compactMap { $0 }.

A compacted() convenience method for this use case would be useful because, similar to joined() in the Standard Library, it wouldn't have to capture an escaping closure and (by the current conventions) it would be able to be lazy by default, i.e. x.compacted() // => Compacted<[Int?], Int>

A new Compacted sequence should also be able to conditionally conform to Collection and BidirectionalCollection, and it should precompute on initialization in order to provide an O(1) startIndex.

Here's a sketch of the Sequence conformance:

struct Compacted<Base: Sequence, Element>: Sequence
  where Base.Element == Element?
{
  let base: Base

  struct Iterator: IteratorProtocol {
    var base: Base.Iterator

    mutating func next() -> Element? {
      while let wrapped = base.next() {
        if let some = wrapped {
          return some
        } else {
          // skip nil
        }
      }
      return nil
    }
  }

  func makeIterator() -> Iterator {
    return Iterator(base: base.makeIterator())
  }
}

extension Sequence {
  func compacted<Unwrapped>() -> Compacted<Self, Unwrapped> where Element == Unwrapped? {
    Compacted(base: self)
  }
}

var tests: [[Int?]] = [
  [],
  [0],
  [nil],
  [0, nil],
  [nil, 0],
  [0, nil, 1, nil, 2, nil],
  [0, 1, 2, nil, nil, nil],
  [nil, nil, nil, 0, 1, 2],
]

for test in tests {
  assert(test.compacted().elementsEqual(test.compactMap({ $0 })))
}

// let x: Array<Int> = [1, 2, 3]
// _ = x.compacted() // error: instance method 'compacted()' requires the types 'Int' and 'Unwrapped?' be equivalent

Thanks to @natecook1000 for coming up with how to make the types work out!

As I mentioned in #109, a benchmark suite is important for ensuring a stable level of performance.

Personally, I've been using https://github.com/google/swift-benchmark - it's a little rough around the edges, but it produces decent reports on all platforms and the dynamic iterations features works really well for getting stable readings out of small code snippets. I'd encourage Apple (or Swift.org) to adopt it, given S4TF's demise, the likelihood that the original authors will abandon it, and the need for good benchmarking utilities that work across platforms.

The implementation of the counts property on Combinations can be optimized to make use of the fact that the binomial is symmetrical around N/2 or (N - 1)/2.

More details available in this review comment on #51.

Replace this paragraph with a description of your proposed feature. Code samples that show what's missing, or what new capabilities will be possible, are very helpful! Provide links to existing issues or external references/discussions, if appropriate.

It seems there is a compile time issue found in Release configuration for the latest release version 0.1.0 when trying to compile with Xcode. Debug configuration appears to be fine.

Swift Algorithms version: 0.1.0
Swift version: Paste the output of swift --version here.

Apple Swift version 5.3.2 (swiftlang-1200.0.45 clang-1200.0.32.28)
Target: x86_64-apple-darwin19.6.0

Xcode Version: 12.4 (12D4e)

Checklist

• If possible, I've reproduced the issue using the main branch of this package
• I've searched for existing GitHub issues

Steps to Reproduce

Create a new iOS project in Xcode, add Swift Algorithms version 0.1.0 as a dependency. Attempt to archive the app -> see error.

Expected behavior

App compiles with Xcode. I have not tested this outside of Xcode yet, will report back when I can, figured I'd post now.

Actual behavior

There seems to be broad appetite for sorting on, say, surnames or ages for a collection of Person values. This has been made even more ergonomic now that key path literals can be used where a function takes a closure as an argument.

I'd propose, therefore, to add the following sorted(on:by:) and sort(on:by:) additions:

extension Sequence {
    @inlinable
    public func sorted<T>(
        on transform: (Self.Element) throws -> T,
        by areInIncreasingOrder: (T, T) throws -> Bool
    ) rethrows -> [Element] {
        try sorted {
            try areInIncreasingOrder(transform($0), transform($1))
        }
    }

    @inlinable
    public func sorted<T: Comparable>(
        on transform: (Self.Element) throws -> T
    ) rethrows -> [Element] {
        try sorted { try transform($0) < transform($1) }
    }
}

extension MutableCollection where Self: RandomAccessCollection {
    @inlinable
    public mutating func sort<T>(
        on transform: (Self.Element) throws -> T,
        by areInIncreasingOrder: (T, T) throws -> Bool
    ) rethrows {
        try sort {
            try areInIncreasingOrder(transform($0), transform($1))
        }
    }

    @inlinable
    public mutating func sort<T: Comparable>(
        on transform: (Self.Element) throws -> T
    ) rethrows {
        try sort { try transform($0) < transform($1) }
    }
}

The use site would look like the following:

struct Person {
    var name: String
    var age: Int
}

let persons = [
    Person(name: "Alice", age: 56),
    Person(name: "Bob", age: 34)
]

let x = persons.sorted(on: \.name, by: >)
let y = persons.sorted(on: \.age)

Any interest in such a change?

The Collection.partitioningIndex(where:) method is described in "Partition.md," the guide for its source file. However, the master list on the library home-page's read-me does not list this method. The read-me only lists the stable-partitioning methods in that same source file. The partitioningIndex method should be listed in the read-me file. It needs to be in a different category, though.

The standard library includes prefix and suffix methods that take a number of elements or an index, but only a prefix method that takes a predicate. We should add a suffix(while:) method to match prefix(while:) for bidirectional collections.

combinations(ofCount:) not working in a command line app for the documented examples.

Swift Algorithms version: 0.0.2
Swift version: 5 (selected from build settings).

Checklist

• If possible, I've reproduced the issue using the main branch of this package
• I've searched for existing GitHub issues

Steps to Reproduce

Created a new command-line app with v 0.0.2 of the Algorithms Swift Package, successfully compiled. I am trying to use combinations(ofCount: ) but it doesn't seem to work. I've tried with String and Int arrays, but the result of the combo only includes the original array. I've pretty much followed the documentation word-for-word, with the example.

func algorithmCombinations(_ digits: [Int]) -> [Int] {
  let combos = digits.combinations(ofCount:3)
  var results = [Int]()
  for combo in combos {
    results.append(contentsOf: combo)
    print(combo)
  }
  return results
}

let res = algorithmCombinations([3,6,2]) // prints [3,6,2]

Expected behavior

Describe what you expect to happen.

[2,3,6],[2,6,3],[3,2,6],[3,6,2],[6,2,3],[6,3,2] gets printed and returned.

Actual behavior

Describe or copy/paste the behavior you observe.
let res = algorithmCombinations([3,6,2]) // prints and returns [3,6,2]

I noticed there’s a method for counting the unique permutations of a collection - how come there is no equivalent for combinations? For example the unique combinations of length 2 of “aabc” are “aa”, “ab”, “ac”, “bc”. If others think this would be useful Id be interested in trying to implement it !

An equivalent would be more_itertools.distinct_combinations(collection, k) in Python

Replace this paragraph with a short description of the incorrect incorrect behavior. If this is a regression, please note the last version that the behavior was correct in addition to your current version.

Swift Algorithms version:
main branch

Swift version:

swift-driver version: 1.26.21 Apple Swift version 5.5.2 (swiftlang-1300.0.47.5 clang-1300.0.29.30)
Target: arm64-apple-macosx12.0

Checklist

• If possible, I've reproduced the issue using the main branch of this package
• I've searched for existing GitHub issues

Steps to Reproduce

The following code crashes:

import Algorithms
import Foundation

let input = "A|1|B|2"
let keyPairs = input
  .split(separator: "|", omittingEmptySubsequences: false)
  .chunks(ofCount: 2)

let aValue = keyPairs.first(where: {$0.first == "A"})
//  .flatMap { Array($0) }
  .flatMap { $0.count == 2 ? $0[1] : nil }

let bValue = keyPairs.first(where: {$0.first == "B"})
//  .flatMap { Array($0) }  // <--- uncomment this and it no longer crashes
  .flatMap { $0.count == 2 ? $0[1] : nil }   // <--- crash here with "Fatal error: Index out of bounds"

print("A: \(aValue ?? "n/a"); B: \(bValue ?? "n/a")")

Expected behavior

It shouldn't crash. Each chunk has a count of 2 so accessing a chunk with index 1 should not crash.

Actual behavior

It crashes. If I uncomment the conversion back to Array it works fine. Based on some testing, the crash appears to happen with every sub-chunk after the first one.

I would like to add a GitHub workflow to run the tests. I wanted to check-in first to see if this is wanted and if there are any requirements for it.

At a high level I would:

• on a push or pull request run the tests
• add a 'test' status badge to the README.md file

Are there any requirements for the machine and swift versions? Is it okay to run on 'macOS-latest' and use swift test --enable-test-discovery to run the tests?

Thank you.

This is a "subtract" operation, e.g.:

let animals = ["Cow", "Bulldog", "Labrador"]
return animals.without(["Bulldog", "Labrador"]) // ["Cow"]

We can see that this is an operation Swift developers are already trying to do from SO questions (1, 2), and it exists in other languages like Ruby.

This is a proposal to get consensus on it. And if people like it, I'd be happy to implement it.

randomSample may have crash in case of 0 was out from Double.random(in: 0..<1).
log(0) is invalid because the domain of log(x) is 0 < x.
It seems that Double.log(0.0) produces -inf.

(lldb) po Double.log(0.0)
-inf

-inf cannot cast to Int so the next crash happens.

Swift Algorithms version: 0.0.2
Swift version: Paste the output of swift --version here

Apple Swift version 5.3.2 (swiftlang-1200.0.45 clang-1200.0.32.28)
Target: x86_64-apple-darwin19.6.0

Checklist

• If possible, I've reproduced the issue using the main branch of this package
• I've searched for existing GitHub issues

Steps to Reproduce

I can reproduce this behavior from the code below.

var generator = SplitMix64(seed: 0x61c8864680b583eb) // this generator outs `0` first.
_ = c.randomSample(count: k, using: &generator) // crash!

Expected behavior

Does not crash.

Actual behavior

pasted screeenshot above.

Summary:
Add ability to optionally also include the pair of the last element and the first element at the end of AdjacentPairs.

Use Case:
For use with circular linked links. Today, I was working with the key view loop on macOS and needed to be able to tie the last element in the loop back to the first. AdjacentPairs almost made this really easy, but was missing the pair of (last, first) so I couldn’t connect them together to be a loop.

for (previousView, nextView) in keyViewLoop.adjacentPairs(wrapping: true) {
  previousView.nextKeyView = nextView
}

Possible API:

I’m not sure if this should be a separate API, or if this extends AdjacentPairs

extension Sequence {
  /// …
  /// The following example uses `adjacentPairs(wrapping: true)` to iterate over
  /// adjacent pairs of integers:
  ///
  ///     for pair in (1...).prefix(5).adjacentPairs(wrapping: true) {
  ///         print(pair)
  ///     }
  ///     // Prints "(1, 2)"
  ///     // Prints "(2, 3)"
  ///     // Prints "(3, 4)"
  ///     // Prints "(4, 5)"
  ///     // Prints "(5, 1)"
  @inlinable
  public func adjacentPairs(wrapping: Bool = false) -> AdjacentPairsSequence<Self> {
    AdjacentPairsSequence(base: self, wrapping: wrapping)
  }
}

extension Collection {
  /// …
  ///     for pair in (1...5).adjacentPairs(wrapping: true) {
  ///         print(pair)
  ///     }
  ///     // Prints "(1, 2)"
  ///     // Prints "(2, 3)"
  ///     // Prints "(3, 4)"
  ///     // Prints "(4, 5)"
  ///     // Prints "(5, 1)"
  @inlinable
  public func adjacentPairs(wrapping: Bool = false) -> AdjacentPairsCollection<Self> {
    AdjacentPairsCollection(base: self, wrapping: wrapping)
  }
}

This code should be fast, but isn't:

for x in (0..<10_000_000).striding(by: 1_000_000) {
  // ...
}

Stride's iterator wraps the base collection's iterator, and can't skip over multiple elements at a time. By forcing the iterator to be an IndexingIterator, the code is fast again:

for x in (0..<10_000_000).striding(by: 1_000_000)[...] {
  // ...
}

I don't think we can vary the Stride.Iterator associated type based on whether Base conforms to Collection, so the only way to fix this that I can think of is to split up Stride into two types (with two overloads), one for sequences and one for collections.