mirror of
https://github.com/apple/swift-algorithms
synced 2026-11-22 04:10:39 +00:00
* Incorporate swift-format formatting fixes * Resolve linting issues * Doc edits, mostly to fix linter-identified issues * Early exit improvements * Indentation fixes * Line lengths to 80 maximum * Implement case binding rule, plus argument line break improvements * Implement NoForceUnwrap rule * Format the tests, as well * Stop masquerading as XCTest
841 lines
31 KiB
Swift
841 lines
31 KiB
Swift
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift Algorithms open source project
|
|
//
|
|
// Copyright (c) 2021 Apple Inc. and the Swift project authors
|
|
// Licensed under Apache License v2.0 with Runtime Library Exception
|
|
//
|
|
// See https://swift.org/LICENSE.txt for license information
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
import Algorithms
|
|
import XCTest
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// Tests for `SplitSequence` and `SplitCollection`
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
final class SplitTests: XCTestCase {
|
|
func testEmpty() {
|
|
Validator(
|
|
subject: [],
|
|
separator: .element(0),
|
|
maxSplits: 1
|
|
).validate()
|
|
}
|
|
|
|
// The following test names indicate the sequence being split, using the
|
|
// notation
|
|
// S: Separator
|
|
// E: Element
|
|
//
|
|
// Values of `maxSplit` are interesting when they're less than the number of
|
|
// splits that would occur with the default. That varies depending on whether
|
|
// empty subsequences are omitted or included. `Validator` tests both the
|
|
// default and the value provided, but there are cases below where the
|
|
// provided `maxSplit` isn't less than the number of splits when empty
|
|
// subsequences are omitted.
|
|
|
|
//===--------------------------------------------------------------------===//
|
|
// Length 1
|
|
//===--------------------------------------------------------------------===//
|
|
|
|
func testE() {
|
|
Validator(subject: [1], separator: .element(0), maxSplits: 0).validate()
|
|
}
|
|
|
|
func testS() {
|
|
Validator(subject: [0], separator: .element(0), maxSplits: 0).validate()
|
|
}
|
|
|
|
//===--------------------------------------------------------------------===//
|
|
// Length 2
|
|
//===--------------------------------------------------------------------===//
|
|
|
|
func testEE() {
|
|
Validator(subject: [1, 1], separator: .element(0), maxSplits: 0).validate()
|
|
}
|
|
|
|
func testSS() {
|
|
Validator(subject: [0, 0], separator: .element(0), maxSplits: 1).validate()
|
|
}
|
|
|
|
func testES() {
|
|
Validator(subject: [1, 0], separator: .element(0), maxSplits: 0).validate()
|
|
}
|
|
|
|
func testSE() {
|
|
Validator(subject: [0, 1], separator: .element(0), maxSplits: 0).validate()
|
|
}
|
|
|
|
//===--------------------------------------------------------------------===//
|
|
// Length 3
|
|
//===--------------------------------------------------------------------===//
|
|
|
|
func testEEE() {
|
|
Validator(subject: [1, 1, 1], separator: .element(0), maxSplits: 0)
|
|
.validate()
|
|
}
|
|
|
|
func testSSS() {
|
|
Validator(subject: [0, 0, 0], separator: .element(0), maxSplits: 1)
|
|
.validate()
|
|
}
|
|
|
|
func testAllEES() {
|
|
let permutations = [[1, 1, 0], [1, 0, 1], [0, 1, 1]]
|
|
|
|
for permutation in permutations {
|
|
Validator(subject: permutation, separator: .element(0), maxSplits: 0)
|
|
.validate()
|
|
}
|
|
}
|
|
|
|
func testAllESS() {
|
|
let permutations = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
|
|
|
|
for permutation in permutations {
|
|
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
|
|
.validate()
|
|
}
|
|
}
|
|
|
|
//===--------------------------------------------------------------------===//
|
|
// Length 4 with less than two separators.
|
|
//===--------------------------------------------------------------------===//
|
|
|
|
func testEEEE() {
|
|
Validator(subject: [1, 1, 1, 1], separator: .element(0), maxSplits: 0)
|
|
.validate()
|
|
}
|
|
|
|
func testAllEEES() {
|
|
let permutations = [
|
|
[1, 1, 1, 0], [1, 1, 0, 1], [1, 0, 1, 1], [0, 1, 1, 1],
|
|
]
|
|
|
|
for permutation in permutations {
|
|
Validator(subject: permutation, separator: .element(0), maxSplits: 0)
|
|
.validate()
|
|
}
|
|
}
|
|
|
|
//===--------------------------------------------------------------------===//
|
|
// Unique permutations of sequences with at least two separators, so there can
|
|
// be multiple adjacent separators at the beginning, middle, or end.
|
|
//===--------------------------------------------------------------------===//
|
|
|
|
// All separators.
|
|
func testSSSS() {
|
|
Validator(subject: [0, 0, 0, 0], separator: .element(0), maxSplits: 1)
|
|
.validate()
|
|
}
|
|
|
|
// Equal numbers of elements and separators.
|
|
func testAllEESS() {
|
|
let permutations = [
|
|
[1, 1, 0, 0], [1, 0, 1, 0], [1, 0, 0, 1],
|
|
[0, 1, 1, 0], [0, 1, 0, 1], [0, 0, 1, 1],
|
|
]
|
|
|
|
for permutation in permutations {
|
|
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
|
|
.validate()
|
|
}
|
|
}
|
|
|
|
// More separators than elements.
|
|
func testAllEESSS() {
|
|
let permutations = [
|
|
[1, 1, 0, 0, 0], [1, 0, 1, 0, 0], [1, 0, 0, 1, 0], [1, 0, 0, 0, 1],
|
|
[0, 1, 1, 0, 0], [0, 1, 0, 1, 0], [0, 1, 0, 0, 1], [0, 0, 1, 1, 0],
|
|
[0, 0, 1, 0, 1], [0, 0, 0, 1, 1],
|
|
]
|
|
|
|
for permutation in permutations {
|
|
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
|
|
.validate()
|
|
}
|
|
}
|
|
|
|
// More elements than separators.
|
|
func testAllEEESS() {
|
|
let permutations = [
|
|
[1, 1, 1, 0, 0], [1, 1, 0, 1, 0], [1, 1, 0, 0, 1], [1, 0, 1, 1, 0],
|
|
[1, 0, 1, 0, 1], [1, 0, 0, 1, 1], [0, 1, 1, 1, 0], [0, 1, 1, 0, 1],
|
|
[0, 1, 0, 1, 1], [0, 0, 1, 1, 1],
|
|
]
|
|
|
|
for permutation in permutations {
|
|
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
|
|
.validate()
|
|
}
|
|
}
|
|
|
|
//===--------------------------------------------------------------------===//
|
|
// Unique permutations of sequences with at least three separators.
|
|
//===--------------------------------------------------------------------===//
|
|
|
|
func testAllESSS() {
|
|
let permutations = [
|
|
[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1],
|
|
]
|
|
|
|
for permutation in permutations {
|
|
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
|
|
.validate()
|
|
}
|
|
}
|
|
|
|
func testAllEEEESSS() {
|
|
let permutations = [
|
|
[1, 1, 1, 1, 0, 0, 0], [1, 1, 1, 0, 1, 0, 0], [1, 1, 1, 0, 0, 1, 0],
|
|
[1, 1, 1, 0, 0, 0, 1], [1, 1, 0, 1, 1, 0, 0], [1, 1, 0, 1, 0, 1, 0],
|
|
[1, 1, 0, 1, 0, 0, 1], [1, 1, 0, 0, 1, 1, 0], [1, 1, 0, 0, 1, 0, 1],
|
|
[1, 1, 0, 0, 0, 1, 1], [1, 0, 1, 1, 1, 0, 0], [1, 0, 1, 1, 0, 1, 0],
|
|
[1, 0, 1, 1, 0, 0, 1], [1, 0, 1, 0, 1, 1, 0], [1, 0, 1, 0, 1, 0, 1],
|
|
[1, 0, 1, 0, 0, 1, 1], [1, 0, 0, 1, 1, 1, 0], [1, 0, 0, 1, 1, 0, 1],
|
|
[1, 0, 0, 1, 0, 1, 1], [1, 0, 0, 0, 1, 1, 1], [0, 1, 1, 1, 1, 0, 0],
|
|
[0, 1, 1, 1, 0, 1, 0], [0, 1, 1, 1, 0, 0, 1], [0, 1, 1, 0, 1, 1, 0],
|
|
[0, 1, 1, 0, 1, 0, 1], [0, 1, 1, 0, 0, 1, 1], [0, 1, 0, 1, 1, 1, 0],
|
|
[0, 1, 0, 1, 1, 0, 1], [0, 1, 0, 1, 0, 1, 1], [0, 1, 0, 0, 1, 1, 1],
|
|
[0, 0, 1, 1, 1, 1, 0], [0, 0, 1, 1, 1, 0, 1], [0, 0, 1, 1, 0, 1, 1],
|
|
[0, 0, 1, 0, 1, 1, 1], [0, 0, 0, 1, 1, 1, 1],
|
|
]
|
|
|
|
for permutation in permutations {
|
|
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
|
|
.validate()
|
|
}
|
|
}
|
|
|
|
//===--------------------------------------------------------------------===//
|
|
// Unique permutations of sequences with at least four separators, so there
|
|
// can be two runs of multiple adjacent separators: beginning and end,
|
|
// beginning and middle, or end and middle.
|
|
//===--------------------------------------------------------------------===//
|
|
|
|
// Equal numbers of separators and elements.
|
|
func testAllEEEESSSS() {
|
|
let permutations = [
|
|
[1, 1, 1, 1, 0, 0, 0, 0], [1, 1, 1, 0, 1, 0, 0, 0],
|
|
[1, 1, 1, 0, 0, 1, 0, 0], [1, 1, 1, 0, 0, 0, 1, 0],
|
|
[1, 1, 1, 0, 0, 0, 0, 1], [1, 1, 0, 1, 1, 0, 0, 0],
|
|
[1, 1, 0, 1, 0, 1, 0, 0], [1, 1, 0, 1, 0, 0, 1, 0],
|
|
[1, 1, 0, 1, 0, 0, 0, 1], [1, 1, 0, 0, 1, 1, 0, 0],
|
|
[1, 1, 0, 0, 1, 0, 1, 0], [1, 1, 0, 0, 1, 0, 0, 1],
|
|
[1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 0, 0, 0, 1, 0, 1],
|
|
[1, 1, 0, 0, 0, 0, 1, 1], [1, 0, 1, 1, 1, 0, 0, 0],
|
|
[1, 0, 1, 1, 0, 1, 0, 0], [1, 0, 1, 1, 0, 0, 1, 0],
|
|
[1, 0, 1, 1, 0, 0, 0, 1], [1, 0, 1, 0, 1, 1, 0, 0],
|
|
[1, 0, 1, 0, 1, 0, 1, 0], [1, 0, 1, 0, 1, 0, 0, 1],
|
|
[1, 0, 1, 0, 0, 1, 1, 0], [1, 0, 1, 0, 0, 1, 0, 1],
|
|
[1, 0, 1, 0, 0, 0, 1, 1], [1, 0, 0, 1, 1, 1, 0, 0],
|
|
[1, 0, 0, 1, 1, 0, 1, 0], [1, 0, 0, 1, 1, 0, 0, 1],
|
|
[1, 0, 0, 1, 0, 1, 1, 0], [1, 0, 0, 1, 0, 1, 0, 1],
|
|
[1, 0, 0, 1, 0, 0, 1, 1], [1, 0, 0, 0, 1, 1, 1, 0],
|
|
[1, 0, 0, 0, 1, 1, 0, 1], [1, 0, 0, 0, 1, 0, 1, 1],
|
|
[1, 0, 0, 0, 0, 1, 1, 1], [0, 1, 1, 1, 1, 0, 0, 0],
|
|
[0, 1, 1, 1, 0, 1, 0, 0], [0, 1, 1, 1, 0, 0, 1, 0],
|
|
[0, 1, 1, 1, 0, 0, 0, 1], [0, 1, 1, 0, 1, 1, 0, 0],
|
|
[0, 1, 1, 0, 1, 0, 1, 0], [0, 1, 1, 0, 1, 0, 0, 1],
|
|
[0, 1, 1, 0, 0, 1, 1, 0], [0, 1, 1, 0, 0, 1, 0, 1],
|
|
[0, 1, 1, 0, 0, 0, 1, 1], [0, 1, 0, 1, 1, 1, 0, 0],
|
|
[0, 1, 0, 1, 1, 0, 1, 0], [0, 1, 0, 1, 1, 0, 0, 1],
|
|
[0, 1, 0, 1, 0, 1, 1, 0], [0, 1, 0, 1, 0, 1, 0, 1],
|
|
[0, 1, 0, 1, 0, 0, 1, 1], [0, 1, 0, 0, 1, 1, 1, 0],
|
|
[0, 1, 0, 0, 1, 1, 0, 1], [0, 1, 0, 0, 1, 0, 1, 1],
|
|
[0, 1, 0, 0, 0, 1, 1, 1], [0, 0, 1, 1, 1, 1, 0, 0],
|
|
[0, 0, 1, 1, 1, 0, 1, 0], [0, 0, 1, 1, 1, 0, 0, 1],
|
|
[0, 0, 1, 1, 0, 1, 1, 0], [0, 0, 1, 1, 0, 1, 0, 1],
|
|
[0, 0, 1, 1, 0, 0, 1, 1], [0, 0, 1, 0, 1, 1, 1, 0],
|
|
[0, 0, 1, 0, 1, 1, 0, 1], [0, 0, 1, 0, 1, 0, 1, 1],
|
|
[0, 0, 1, 0, 0, 1, 1, 1], [0, 0, 0, 1, 1, 1, 1, 0],
|
|
[0, 0, 0, 1, 1, 1, 0, 1], [0, 0, 0, 1, 1, 0, 1, 1],
|
|
[0, 0, 0, 1, 0, 1, 1, 1], [0, 0, 0, 0, 1, 1, 1, 1],
|
|
]
|
|
|
|
for permutation in permutations {
|
|
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
|
|
.validate()
|
|
}
|
|
}
|
|
|
|
// More separators than elements.
|
|
func testAllEEESSSS() {
|
|
let permutations = [
|
|
[1, 1, 1, 0, 0, 0, 0], [1, 1, 0, 1, 0, 0, 0], [1, 1, 0, 0, 1, 0, 0],
|
|
[1, 1, 0, 0, 0, 1, 0], [1, 1, 0, 0, 0, 0, 1], [1, 0, 1, 1, 0, 0, 0],
|
|
[1, 0, 1, 0, 1, 0, 0], [1, 0, 1, 0, 0, 1, 0], [1, 0, 1, 0, 0, 0, 1],
|
|
[1, 0, 0, 1, 1, 0, 0], [1, 0, 0, 1, 0, 1, 0], [1, 0, 0, 1, 0, 0, 1],
|
|
[1, 0, 0, 0, 1, 1, 0], [1, 0, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 1, 1],
|
|
[0, 1, 1, 1, 0, 0, 0], [0, 1, 1, 0, 1, 0, 0], [0, 1, 1, 0, 0, 1, 0],
|
|
[0, 1, 1, 0, 0, 0, 1], [0, 1, 0, 1, 1, 0, 0], [0, 1, 0, 1, 0, 1, 0],
|
|
[0, 1, 0, 1, 0, 0, 1], [0, 1, 0, 0, 1, 1, 0], [0, 1, 0, 0, 1, 0, 1],
|
|
[0, 1, 0, 0, 0, 1, 1], [0, 0, 1, 1, 1, 0, 0], [0, 0, 1, 1, 0, 1, 0],
|
|
[0, 0, 1, 1, 0, 0, 1], [0, 0, 1, 0, 1, 1, 0], [0, 0, 1, 0, 1, 0, 1],
|
|
[0, 0, 1, 0, 0, 1, 1], [0, 0, 0, 1, 1, 1, 0], [0, 0, 0, 1, 1, 0, 1],
|
|
[0, 0, 0, 1, 0, 1, 1], [0, 0, 0, 0, 1, 1, 1],
|
|
]
|
|
|
|
for permutation in permutations {
|
|
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
|
|
.validate()
|
|
}
|
|
}
|
|
|
|
// More elements than separators.
|
|
func testAllEEEEESSSS() {
|
|
let permutations = [
|
|
[1, 1, 1, 1, 1, 0, 0, 0, 0], [1, 1, 1, 1, 0, 1, 0, 0, 0],
|
|
[1, 1, 1, 1, 0, 0, 1, 0, 0], [1, 1, 1, 1, 0, 0, 0, 1, 0],
|
|
[1, 1, 1, 1, 0, 0, 0, 0, 1], [1, 1, 1, 0, 1, 1, 0, 0, 0],
|
|
[1, 1, 1, 0, 1, 0, 1, 0, 0], [1, 1, 1, 0, 1, 0, 0, 1, 0],
|
|
[1, 1, 1, 0, 1, 0, 0, 0, 1], [1, 1, 1, 0, 0, 1, 1, 0, 0],
|
|
[1, 1, 1, 0, 0, 1, 0, 1, 0], [1, 1, 1, 0, 0, 1, 0, 0, 1],
|
|
[1, 1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 0, 0, 0, 1, 0, 1],
|
|
[1, 1, 1, 0, 0, 0, 0, 1, 1], [1, 1, 0, 1, 1, 1, 0, 0, 0],
|
|
[1, 1, 0, 1, 1, 0, 1, 0, 0], [1, 1, 0, 1, 1, 0, 0, 1, 0],
|
|
[1, 1, 0, 1, 1, 0, 0, 0, 1], [1, 1, 0, 1, 0, 1, 1, 0, 0],
|
|
[1, 1, 0, 1, 0, 1, 0, 1, 0], [1, 1, 0, 1, 0, 1, 0, 0, 1],
|
|
[1, 1, 0, 1, 0, 0, 1, 1, 0], [1, 1, 0, 1, 0, 0, 1, 0, 1],
|
|
[1, 1, 0, 1, 0, 0, 0, 1, 1], [1, 1, 0, 0, 1, 1, 1, 0, 0],
|
|
[1, 1, 0, 0, 1, 1, 0, 1, 0], [1, 1, 0, 0, 1, 1, 0, 0, 1],
|
|
[1, 1, 0, 0, 1, 0, 1, 1, 0], [1, 1, 0, 0, 1, 0, 1, 0, 1],
|
|
[1, 1, 0, 0, 1, 0, 0, 1, 1], [1, 1, 0, 0, 0, 1, 1, 1, 0],
|
|
[1, 1, 0, 0, 0, 1, 1, 0, 1], [1, 1, 0, 0, 0, 1, 0, 1, 1],
|
|
[1, 1, 0, 0, 0, 0, 1, 1, 1], [1, 0, 1, 1, 1, 1, 0, 0, 0],
|
|
[1, 0, 1, 1, 1, 0, 1, 0, 0], [1, 0, 1, 1, 1, 0, 0, 1, 0],
|
|
[1, 0, 1, 1, 1, 0, 0, 0, 1], [1, 0, 1, 1, 0, 1, 1, 0, 0],
|
|
[1, 0, 1, 1, 0, 1, 0, 1, 0], [1, 0, 1, 1, 0, 1, 0, 0, 1],
|
|
[1, 0, 1, 1, 0, 0, 1, 1, 0], [1, 0, 1, 1, 0, 0, 1, 0, 1],
|
|
[1, 0, 1, 1, 0, 0, 0, 1, 1], [1, 0, 1, 0, 1, 1, 1, 0, 0],
|
|
[1, 0, 1, 0, 1, 1, 0, 1, 0], [1, 0, 1, 0, 1, 1, 0, 0, 1],
|
|
[1, 0, 1, 0, 1, 0, 1, 1, 0], [1, 0, 1, 0, 1, 0, 1, 0, 1],
|
|
[1, 0, 1, 0, 1, 0, 0, 1, 1], [1, 0, 1, 0, 0, 1, 1, 1, 0],
|
|
[1, 0, 1, 0, 0, 1, 1, 0, 1], [1, 0, 1, 0, 0, 1, 0, 1, 1],
|
|
[1, 0, 1, 0, 0, 0, 1, 1, 1], [1, 0, 0, 1, 1, 1, 1, 0, 0],
|
|
[1, 0, 0, 1, 1, 1, 0, 1, 0], [1, 0, 0, 1, 1, 1, 0, 0, 1],
|
|
[1, 0, 0, 1, 1, 0, 1, 1, 0], [1, 0, 0, 1, 1, 0, 1, 0, 1],
|
|
[1, 0, 0, 1, 1, 0, 0, 1, 1], [1, 0, 0, 1, 0, 1, 1, 1, 0],
|
|
[1, 0, 0, 1, 0, 1, 1, 0, 1], [1, 0, 0, 1, 0, 1, 0, 1, 1],
|
|
[1, 0, 0, 1, 0, 0, 1, 1, 1], [1, 0, 0, 0, 1, 1, 1, 1, 0],
|
|
[1, 0, 0, 0, 1, 1, 1, 0, 1], [1, 0, 0, 0, 1, 1, 0, 1, 1],
|
|
[1, 0, 0, 0, 1, 0, 1, 1, 1], [1, 0, 0, 0, 0, 1, 1, 1, 1],
|
|
[0, 1, 1, 1, 1, 1, 0, 0, 0], [0, 1, 1, 1, 1, 0, 1, 0, 0],
|
|
[0, 1, 1, 1, 1, 0, 0, 1, 0], [0, 1, 1, 1, 1, 0, 0, 0, 1],
|
|
[0, 1, 1, 1, 0, 1, 1, 0, 0], [0, 1, 1, 1, 0, 1, 0, 1, 0],
|
|
[0, 1, 1, 1, 0, 1, 0, 0, 1], [0, 1, 1, 1, 0, 0, 1, 1, 0],
|
|
[0, 1, 1, 1, 0, 0, 1, 0, 1], [0, 1, 1, 1, 0, 0, 0, 1, 1],
|
|
[0, 1, 1, 0, 1, 1, 1, 0, 0], [0, 1, 1, 0, 1, 1, 0, 1, 0],
|
|
[0, 1, 1, 0, 1, 1, 0, 0, 1], [0, 1, 1, 0, 1, 0, 1, 1, 0],
|
|
[0, 1, 1, 0, 1, 0, 1, 0, 1], [0, 1, 1, 0, 1, 0, 0, 1, 1],
|
|
[0, 1, 1, 0, 0, 1, 1, 1, 0], [0, 1, 1, 0, 0, 1, 1, 0, 1],
|
|
[0, 1, 1, 0, 0, 1, 0, 1, 1], [0, 1, 1, 0, 0, 0, 1, 1, 1],
|
|
[0, 1, 0, 1, 1, 1, 1, 0, 0], [0, 1, 0, 1, 1, 1, 0, 1, 0],
|
|
[0, 1, 0, 1, 1, 1, 0, 0, 1], [0, 1, 0, 1, 1, 0, 1, 1, 0],
|
|
[0, 1, 0, 1, 1, 0, 1, 0, 1], [0, 1, 0, 1, 1, 0, 0, 1, 1],
|
|
[0, 1, 0, 1, 0, 1, 1, 1, 0], [0, 1, 0, 1, 0, 1, 1, 0, 1],
|
|
[0, 1, 0, 1, 0, 1, 0, 1, 1], [0, 1, 0, 1, 0, 0, 1, 1, 1],
|
|
[0, 1, 0, 0, 1, 1, 1, 1, 0], [0, 1, 0, 0, 1, 1, 1, 0, 1],
|
|
[0, 1, 0, 0, 1, 1, 0, 1, 1], [0, 1, 0, 0, 1, 0, 1, 1, 1],
|
|
[0, 1, 0, 0, 0, 1, 1, 1, 1], [0, 0, 1, 1, 1, 1, 1, 0, 0],
|
|
[0, 0, 1, 1, 1, 1, 0, 1, 0], [0, 0, 1, 1, 1, 1, 0, 0, 1],
|
|
[0, 0, 1, 1, 1, 0, 1, 1, 0], [0, 0, 1, 1, 1, 0, 1, 0, 1],
|
|
[0, 0, 1, 1, 1, 0, 0, 1, 1], [0, 0, 1, 1, 0, 1, 1, 1, 0],
|
|
[0, 0, 1, 1, 0, 1, 1, 0, 1], [0, 0, 1, 1, 0, 1, 0, 1, 1],
|
|
[0, 0, 1, 1, 0, 0, 1, 1, 1], [0, 0, 1, 0, 1, 1, 1, 1, 0],
|
|
[0, 0, 1, 0, 1, 1, 1, 0, 1], [0, 0, 1, 0, 1, 1, 0, 1, 1],
|
|
[0, 0, 1, 0, 1, 0, 1, 1, 1], [0, 0, 1, 0, 0, 1, 1, 1, 1],
|
|
[0, 0, 0, 1, 1, 1, 1, 1, 0], [0, 0, 0, 1, 1, 1, 1, 0, 1],
|
|
[0, 0, 0, 1, 1, 1, 0, 1, 1], [0, 0, 0, 1, 1, 0, 1, 1, 1],
|
|
[0, 0, 0, 1, 0, 1, 1, 1, 1], [0, 0, 0, 0, 1, 1, 1, 1, 1],
|
|
]
|
|
|
|
for permutation in permutations {
|
|
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
|
|
.validate()
|
|
}
|
|
}
|
|
|
|
//===--------------------------------------------------------------------===//
|
|
// Permutations of a sequence with six separators, so there can be multiple
|
|
// adjacent separators at the beginning, middle, _and_ end.
|
|
//===--------------------------------------------------------------------===//
|
|
|
|
// More separators than elements.
|
|
func testAllEEESSSSSS() {
|
|
let permutations = [
|
|
[1, 1, 1, 0, 0, 0, 0, 0, 0], [1, 1, 0, 1, 0, 0, 0, 0, 0],
|
|
[1, 1, 0, 0, 1, 0, 0, 0, 0], [1, 1, 0, 0, 0, 1, 0, 0, 0],
|
|
[1, 1, 0, 0, 0, 0, 1, 0, 0], [1, 1, 0, 0, 0, 0, 0, 1, 0],
|
|
[1, 1, 0, 0, 0, 0, 0, 0, 1], [1, 0, 1, 1, 0, 0, 0, 0, 0],
|
|
[1, 0, 1, 0, 1, 0, 0, 0, 0], [1, 0, 1, 0, 0, 1, 0, 0, 0],
|
|
[1, 0, 1, 0, 0, 0, 1, 0, 0], [1, 0, 1, 0, 0, 0, 0, 1, 0],
|
|
[1, 0, 1, 0, 0, 0, 0, 0, 1], [1, 0, 0, 1, 1, 0, 0, 0, 0],
|
|
[1, 0, 0, 1, 0, 1, 0, 0, 0], [1, 0, 0, 1, 0, 0, 1, 0, 0],
|
|
[1, 0, 0, 1, 0, 0, 0, 1, 0], [1, 0, 0, 1, 0, 0, 0, 0, 1],
|
|
[1, 0, 0, 0, 1, 1, 0, 0, 0], [1, 0, 0, 0, 1, 0, 1, 0, 0],
|
|
[1, 0, 0, 0, 1, 0, 0, 1, 0], [1, 0, 0, 0, 1, 0, 0, 0, 1],
|
|
[1, 0, 0, 0, 0, 1, 1, 0, 0], [1, 0, 0, 0, 0, 1, 0, 1, 0],
|
|
[1, 0, 0, 0, 0, 1, 0, 0, 1], [1, 0, 0, 0, 0, 0, 1, 1, 0],
|
|
[1, 0, 0, 0, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 0, 0, 1, 1],
|
|
[0, 1, 1, 1, 0, 0, 0, 0, 0], [0, 1, 1, 0, 1, 0, 0, 0, 0],
|
|
[0, 1, 1, 0, 0, 1, 0, 0, 0], [0, 1, 1, 0, 0, 0, 1, 0, 0],
|
|
[0, 1, 1, 0, 0, 0, 0, 1, 0], [0, 1, 1, 0, 0, 0, 0, 0, 1],
|
|
[0, 1, 0, 1, 1, 0, 0, 0, 0], [0, 1, 0, 1, 0, 1, 0, 0, 0],
|
|
[0, 1, 0, 1, 0, 0, 1, 0, 0], [0, 1, 0, 1, 0, 0, 0, 1, 0],
|
|
[0, 1, 0, 1, 0, 0, 0, 0, 1], [0, 1, 0, 0, 1, 1, 0, 0, 0],
|
|
[0, 1, 0, 0, 1, 0, 1, 0, 0], [0, 1, 0, 0, 1, 0, 0, 1, 0],
|
|
[0, 1, 0, 0, 1, 0, 0, 0, 1], [0, 1, 0, 0, 0, 1, 1, 0, 0],
|
|
[0, 1, 0, 0, 0, 1, 0, 1, 0], [0, 1, 0, 0, 0, 1, 0, 0, 1],
|
|
[0, 1, 0, 0, 0, 0, 1, 1, 0], [0, 1, 0, 0, 0, 0, 1, 0, 1],
|
|
[0, 1, 0, 0, 0, 0, 0, 1, 1], [0, 0, 1, 1, 1, 0, 0, 0, 0],
|
|
[0, 0, 1, 1, 0, 1, 0, 0, 0], [0, 0, 1, 1, 0, 0, 1, 0, 0],
|
|
[0, 0, 1, 1, 0, 0, 0, 1, 0], [0, 0, 1, 1, 0, 0, 0, 0, 1],
|
|
[0, 0, 1, 0, 1, 1, 0, 0, 0], [0, 0, 1, 0, 1, 0, 1, 0, 0],
|
|
[0, 0, 1, 0, 1, 0, 0, 1, 0], [0, 0, 1, 0, 1, 0, 0, 0, 1],
|
|
[0, 0, 1, 0, 0, 1, 1, 0, 0], [0, 0, 1, 0, 0, 1, 0, 1, 0],
|
|
[0, 0, 1, 0, 0, 1, 0, 0, 1], [0, 0, 1, 0, 0, 0, 1, 1, 0],
|
|
[0, 0, 1, 0, 0, 0, 1, 0, 1], [0, 0, 1, 0, 0, 0, 0, 1, 1],
|
|
[0, 0, 0, 1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 0, 1, 0, 0],
|
|
[0, 0, 0, 1, 1, 0, 0, 1, 0], [0, 0, 0, 1, 1, 0, 0, 0, 1],
|
|
[0, 0, 0, 1, 0, 1, 1, 0, 0], [0, 0, 0, 1, 0, 1, 0, 1, 0],
|
|
[0, 0, 0, 1, 0, 1, 0, 0, 1], [0, 0, 0, 1, 0, 0, 1, 1, 0],
|
|
[0, 0, 0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 0, 0, 1, 1],
|
|
[0, 0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 1, 0],
|
|
[0, 0, 0, 0, 1, 1, 0, 0, 1], [0, 0, 0, 0, 1, 0, 1, 1, 0],
|
|
[0, 0, 0, 0, 1, 0, 1, 0, 1], [0, 0, 0, 0, 1, 0, 0, 1, 1],
|
|
[0, 0, 0, 0, 0, 1, 1, 1, 0], [0, 0, 0, 0, 0, 1, 1, 0, 1],
|
|
[0, 0, 0, 0, 0, 1, 0, 1, 1], [0, 0, 0, 0, 0, 0, 1, 1, 1],
|
|
]
|
|
|
|
for permutation in permutations {
|
|
Validator(subject: permutation, separator: .element(0), maxSplits: 1)
|
|
.validate()
|
|
}
|
|
}
|
|
|
|
//===--------------------------------------------------------------------===//
|
|
// Specific examples of interest.
|
|
//===--------------------------------------------------------------------===//
|
|
|
|
// The motivating example from
|
|
// https://github.com/apple/swift-algorithms/issues/59.
|
|
func testSplitFilenameComponents() {
|
|
Validator(
|
|
subject: "archive.tar.gz",
|
|
separator: .element("."),
|
|
maxSplits: 1
|
|
).validate()
|
|
}
|
|
|
|
// Examples from documentation.
|
|
func testSequenceDocExamples() {
|
|
// Closure version.
|
|
let numbers = stride(from: 1, through: 16, by: 1)
|
|
Validator(
|
|
subject: Array(numbers),
|
|
separator: .closure({ $0 % 3 == 0 || $0 % 5 == 0 }),
|
|
maxSplits: 1
|
|
).validate()
|
|
|
|
// Equatable element version.
|
|
let numbers2 = [1, 2, 0, 3, 4, 0, 0, 5]
|
|
Validator(subject: numbers2, separator: .element(0), maxSplits: 1)
|
|
.validate()
|
|
}
|
|
|
|
func testCollectionDocExample() {
|
|
let line = "BLANCHE: I don't want realism. I want magic!"
|
|
Validator(subject: line, separator: .element("."), maxSplits: 1).validate()
|
|
}
|
|
|
|
// Patterns tested in a previous version of this file which aren't tested
|
|
// above. Preserved to ensure we're not losing any test coverage.
|
|
func testVintagePatterns() {
|
|
let pattern1 = [1, 2, 42, 3, 4, 42, 5, 6, 42, 7]
|
|
Validator(subject: pattern1, separator: .element(42), maxSplits: 2)
|
|
.validate()
|
|
Validator(subject: pattern1, separator: .element(42), maxSplits: 0)
|
|
.validate()
|
|
|
|
let pattern2 = [42, 1, 2, 42, 3, 4, 42, 5, 6, 42, 7]
|
|
Validator(subject: pattern2, separator: .element(42), maxSplits: 2)
|
|
.validate()
|
|
|
|
let pattern3 = [1, 2, 42, 3, 4, 42, 42, 5, 6, 42, 7]
|
|
Validator(subject: pattern3, separator: .element(42), maxSplits: 2)
|
|
.validate()
|
|
|
|
let pattern4 = [1, 2, 42, 3, 4, 42, 42, 5, 6, 42, 7, 42, 42, 42]
|
|
Validator(subject: pattern4, separator: .element(42), maxSplits: 1)
|
|
.validate()
|
|
}
|
|
|
|
//===--------------------------------------------------------------------===//
|
|
// Protocol conformance.
|
|
//===--------------------------------------------------------------------===//
|
|
|
|
func testLaziness() {
|
|
let splitSequence = AnySequence([1, 2, 42, 3]).lazy.split(separator: 42)
|
|
requireLazySequence(splitSequence)
|
|
|
|
let splitCollection = "foo.bar".lazy.split(separator: ".")
|
|
requireLazySequence(splitCollection)
|
|
requireLazyCollection(splitCollection)
|
|
}
|
|
|
|
// TODO: Need a version of `validateIndexTraversals` that doesn't require
|
|
// `BidirectionalCollection` conformance.
|
|
|
|
//===--------------------------------------------------------------------===//
|
|
// Validator
|
|
//===--------------------------------------------------------------------===//
|
|
|
|
/// Splits a collection as both a lazy sequence and a lazy collection, using
|
|
/// the provided separator, and compares the results to those of the Standard
|
|
/// Library's eager splits, which are assumed to be correct.
|
|
///
|
|
/// Tests all combinations of default and provided `maxSplit` arguments and
|
|
/// default (true) and explicit false for `omittingEmptySubsequences`.
|
|
///
|
|
/// - Parameters:
|
|
/// - subject: The collection whose splits will be validated.
|
|
/// - separator: The element of the collection--or a predicate function to
|
|
/// determine the element--on which to split.
|
|
/// - maxSplits: The value to pass for `maxSplits` during validation. The
|
|
/// default value is also validated.
|
|
fileprivate struct Validator<C: Collection>
|
|
where C.Element: Equatable, C.SubSequence: Equatable {
|
|
enum Separator {
|
|
case element(C.Element)
|
|
case closure((C.Element) -> Bool)
|
|
}
|
|
|
|
let subject: C
|
|
let separator: Separator
|
|
let maxSplits: Int
|
|
|
|
func validate() {
|
|
_validateAsSequence(AnySequence(subject))
|
|
_validateAsCollection(subject)
|
|
}
|
|
|
|
private enum MaxSplits: CustomStringConvertible {
|
|
case provided(Int)
|
|
case defaultValue
|
|
|
|
var description: String {
|
|
switch self {
|
|
case .provided(let value):
|
|
return "maxSplits: \(value)"
|
|
case .defaultValue:
|
|
return "maxSplits: default"
|
|
}
|
|
}
|
|
}
|
|
|
|
private enum OmittingEmptySubsequences: CustomStringConvertible {
|
|
case provided(Bool)
|
|
case defaultValue
|
|
|
|
var description: String {
|
|
switch self {
|
|
case .provided(let value):
|
|
return "omittingEmptySubsequences: \(value)"
|
|
case .defaultValue:
|
|
return "omittingEmptySubsequences: default"
|
|
}
|
|
}
|
|
}
|
|
|
|
private func failureMessage<L: LazySequenceProtocol, S: Sequence>(
|
|
actual: L,
|
|
expected: S,
|
|
maxSplits: MaxSplits,
|
|
omittingEmptySubsequences: OmittingEmptySubsequences
|
|
) -> String {
|
|
"for \(Array(subject).debugDescription), \(maxSplits), \(omittingEmptySubsequences): \(Array(actual).debugDescription) != \(Array(expected).debugDescription)"
|
|
}
|
|
|
|
private func _validateAsSequence<T: Sequence>(_ s: T)
|
|
where T.Element == C.Element {
|
|
// Default max splits, omitting empty sequences
|
|
switch separator {
|
|
case .element(let element):
|
|
let expected = s.split(separator: element).map { Array($0) }
|
|
let actual = s.lazy.split(separator: element)
|
|
expectEqualSequences(
|
|
expected,
|
|
actual,
|
|
failureMessage(
|
|
actual: actual, expected: expected, maxSplits: .defaultValue,
|
|
omittingEmptySubsequences: .defaultValue)
|
|
)
|
|
case .closure(let closure):
|
|
let expected = s.split(whereSeparator: closure).map { Array($0) }
|
|
let actual = s.lazy.split(whereSeparator: closure)
|
|
expectEqualSequences(
|
|
expected,
|
|
actual,
|
|
failureMessage(
|
|
actual: actual, expected: expected, maxSplits: .defaultValue,
|
|
omittingEmptySubsequences: .defaultValue)
|
|
)
|
|
}
|
|
|
|
// Provided max splits, omitting empty sequences
|
|
switch separator {
|
|
case .element(let element):
|
|
let expected = s.split(
|
|
separator: element,
|
|
maxSplits: maxSplits
|
|
).map { Array($0) }
|
|
let actual = s.lazy.split(
|
|
separator: element,
|
|
maxSplits: maxSplits
|
|
)
|
|
expectEqualSequences(
|
|
expected,
|
|
actual,
|
|
failureMessage(
|
|
actual: actual, expected: expected, maxSplits: .provided(maxSplits),
|
|
omittingEmptySubsequences: .defaultValue)
|
|
)
|
|
case .closure(let closure):
|
|
let expected = s.split(
|
|
maxSplits: maxSplits,
|
|
whereSeparator: closure
|
|
).map { Array($0) }
|
|
let actual = s.lazy.split(
|
|
maxSplits: maxSplits,
|
|
whereSeparator: closure
|
|
)
|
|
expectEqualSequences(
|
|
expected,
|
|
actual,
|
|
failureMessage(
|
|
actual: actual, expected: expected, maxSplits: .provided(maxSplits),
|
|
omittingEmptySubsequences: .defaultValue)
|
|
)
|
|
}
|
|
|
|
// Default max splits, including empty sequences
|
|
switch separator {
|
|
case .element(let element):
|
|
let expected = s.split(
|
|
separator: element,
|
|
omittingEmptySubsequences: false
|
|
).map { Array($0) }
|
|
let actual = s.lazy.split(
|
|
separator: element,
|
|
omittingEmptySubsequences: false
|
|
)
|
|
expectEqualSequences(
|
|
expected,
|
|
actual,
|
|
failureMessage(
|
|
actual: actual, expected: expected, maxSplits: .defaultValue,
|
|
omittingEmptySubsequences: .provided(false))
|
|
)
|
|
case .closure(let closure):
|
|
let expected = s.split(
|
|
omittingEmptySubsequences: false,
|
|
whereSeparator: closure
|
|
).map { Array($0) }
|
|
let actual = s.lazy.split(
|
|
omittingEmptySubsequences: false,
|
|
whereSeparator: closure
|
|
)
|
|
expectEqualSequences(
|
|
expected,
|
|
actual,
|
|
failureMessage(
|
|
actual: actual, expected: expected, maxSplits: .defaultValue,
|
|
omittingEmptySubsequences: .provided(false))
|
|
)
|
|
}
|
|
|
|
// Provided max splits, including empty sequences
|
|
switch separator {
|
|
case .element(let element):
|
|
let expected = s.split(
|
|
separator: element,
|
|
maxSplits: maxSplits,
|
|
omittingEmptySubsequences: false
|
|
).map { Array($0) }
|
|
let actual = s.lazy.split(
|
|
separator: element,
|
|
maxSplits: maxSplits,
|
|
omittingEmptySubsequences: false
|
|
)
|
|
expectEqualSequences(
|
|
expected,
|
|
actual,
|
|
failureMessage(
|
|
actual: actual, expected: expected, maxSplits: .provided(maxSplits),
|
|
omittingEmptySubsequences: .provided(false))
|
|
)
|
|
case .closure(let closure):
|
|
let expected = s.split(
|
|
maxSplits: maxSplits,
|
|
omittingEmptySubsequences: false,
|
|
whereSeparator: closure
|
|
).map { Array($0) }
|
|
let actual = s.lazy.split(
|
|
maxSplits: maxSplits,
|
|
omittingEmptySubsequences: false,
|
|
whereSeparator: closure
|
|
)
|
|
expectEqualSequences(
|
|
expected,
|
|
actual,
|
|
failureMessage(
|
|
actual: actual, expected: expected, maxSplits: .provided(maxSplits),
|
|
omittingEmptySubsequences: .provided(false))
|
|
)
|
|
}
|
|
}
|
|
|
|
private func _validateAsCollection(_ c: C) {
|
|
// Default max splits, omitting empty sequences
|
|
switch separator {
|
|
case .element(let element):
|
|
let expected = c.split(separator: element)
|
|
let actual = c.lazy.split(separator: element)
|
|
expectEqualSequences(
|
|
expected,
|
|
actual,
|
|
failureMessage(
|
|
actual: actual, expected: expected, maxSplits: .defaultValue,
|
|
omittingEmptySubsequences: .defaultValue)
|
|
)
|
|
case .closure(let closure):
|
|
let expected = c.split(whereSeparator: closure)
|
|
let actual = c.lazy.split(whereSeparator: closure)
|
|
expectEqualSequences(
|
|
expected,
|
|
actual,
|
|
failureMessage(
|
|
actual: actual, expected: expected, maxSplits: .defaultValue,
|
|
omittingEmptySubsequences: .defaultValue)
|
|
)
|
|
}
|
|
|
|
// Provided max splits, omitting empty sequences
|
|
switch separator {
|
|
case .element(let element):
|
|
let expected = c.split(
|
|
separator: element,
|
|
maxSplits: maxSplits
|
|
)
|
|
let actual = c.lazy.split(
|
|
separator: element,
|
|
maxSplits: maxSplits
|
|
)
|
|
expectEqualSequences(
|
|
expected,
|
|
actual,
|
|
failureMessage(
|
|
actual: actual, expected: expected, maxSplits: .provided(maxSplits),
|
|
omittingEmptySubsequences: .defaultValue)
|
|
)
|
|
case .closure(let closure):
|
|
let expected = c.split(
|
|
maxSplits: maxSplits,
|
|
whereSeparator: closure
|
|
)
|
|
let actual = c.lazy.split(
|
|
maxSplits: maxSplits,
|
|
whereSeparator: closure
|
|
)
|
|
expectEqualSequences(
|
|
expected,
|
|
actual,
|
|
failureMessage(
|
|
actual: actual, expected: expected, maxSplits: .provided(maxSplits),
|
|
omittingEmptySubsequences: .defaultValue)
|
|
)
|
|
}
|
|
|
|
// Default max splits, including empty sequences
|
|
switch separator {
|
|
case .element(let element):
|
|
let expected = c.split(
|
|
separator: element,
|
|
omittingEmptySubsequences: false
|
|
)
|
|
let actual = c.lazy.split(
|
|
separator: element,
|
|
omittingEmptySubsequences: false
|
|
)
|
|
expectEqualSequences(
|
|
expected,
|
|
actual,
|
|
failureMessage(
|
|
actual: actual, expected: expected, maxSplits: .defaultValue,
|
|
omittingEmptySubsequences: .provided(false))
|
|
)
|
|
case .closure(let closure):
|
|
let expected = c.split(
|
|
omittingEmptySubsequences: false,
|
|
whereSeparator: closure
|
|
)
|
|
let actual = c.lazy.split(
|
|
omittingEmptySubsequences: false,
|
|
whereSeparator: closure
|
|
)
|
|
expectEqualSequences(
|
|
expected,
|
|
actual,
|
|
failureMessage(
|
|
actual: actual, expected: expected, maxSplits: .defaultValue,
|
|
omittingEmptySubsequences: .provided(false))
|
|
)
|
|
}
|
|
|
|
// Provided max splits, including empty sequences
|
|
switch separator {
|
|
case .element(let element):
|
|
let expected = c.split(
|
|
separator: element,
|
|
maxSplits: maxSplits,
|
|
omittingEmptySubsequences: false
|
|
)
|
|
let actual = c.lazy.split(
|
|
separator: element,
|
|
maxSplits: maxSplits,
|
|
omittingEmptySubsequences: false
|
|
)
|
|
expectEqualSequences(
|
|
expected,
|
|
actual,
|
|
failureMessage(
|
|
actual: actual, expected: expected, maxSplits: .provided(maxSplits),
|
|
omittingEmptySubsequences: .provided(false))
|
|
)
|
|
case .closure(let closure):
|
|
let expected = c.split(
|
|
maxSplits: maxSplits,
|
|
omittingEmptySubsequences: false,
|
|
whereSeparator: closure
|
|
)
|
|
let actual = c.lazy.split(
|
|
maxSplits: maxSplits,
|
|
omittingEmptySubsequences: false,
|
|
whereSeparator: closure
|
|
)
|
|
expectEqualSequences(
|
|
expected,
|
|
actual,
|
|
failureMessage(
|
|
actual: actual, expected: expected, maxSplits: .provided(maxSplits),
|
|
omittingEmptySubsequences: .provided(false))
|
|
)
|
|
}
|
|
}
|
|
}
|
|
}
|