FrameGrabber/Frame Grabber/Packages/SampleTimeIndexer/Tests/SampleTimeIndexerTests/BinarySearchTests.swift at develop · arthurhammer/FrameGrabber · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
import XCTest
@testable import SampleTimeIndexer

final class BinarySearchTests: XCTestCase {

    // MARK: - sortedFirstIndex(of:)

    func test_indexOf_empty_shouldBeNil() {
        let array = [Int]().sorted()

        let input = 4
        let actual = array.sortedFirstIndex(of: input)
        let expected = array.firstIndex(of: input)

        XCTAssertEqual(actual, expected)
    }

    func test_indexOf_noMatch_shouldBeNil() {
        let array = [2, 4, 60, 80, 140, 150, 300, 900].sorted()

        let input = 90
        let actual = array.sortedFirstIndex(of: input)
        let expected = array.firstIndex(of: input)

        XCTAssertEqual(actual, expected)
    }

    func test_indexOf_match_shouldBeLeftmostMatch() {
        let array = [2, 4, 60, 80, 140, 140, 140, 150, 300, 900].sorted()

        let input = 140
        let actual = array.sortedFirstIndex(of: input)
        let expected = array.firstIndex(of: input)

        XCTAssertEqual(actual, expected)
    }

    func test_indexOf_randomMatches() {
        let array = randomArray(withCount: .random(in: 0...1000)).sorted()

        print("Testing random array of size \(array.count)")

        array.forEach {
            let actual = array.sortedFirstIndex(of: $0)
            let expected = array.firstIndex(of: $0)

            XCTAssertEqual(actual, expected)
        }
    }

    // MARK: - sortedLastIndex(ofElementLessThanOrEqualTo:)

    func test_indexLessOrEqualOf_empty_shouldBeNil() {
        let array = [Int]().sorted()

        let actual = array.sortedLastIndex(ofElementLessThanOrEqualTo: 4)

        XCTAssertNil(actual)
    }

    func test_indexLessOrEqualOf_beforeFirst_shouldBeNil() {
        let array = [2, 4, 60, 80, 140, 150, 300, 900].sorted()

        let actual = array.sortedLastIndex(ofElementLessThanOrEqualTo: -1)

        XCTAssertNil(actual)
    }

    func test_indexLessOrEqualOf_afterLast_shouldBeLast() {
        let array = [2, 4, 60, 80, 140, 150, 300, 900].sorted()

        let actual = array.sortedLastIndex(ofElementLessThanOrEqualTo: 1000)

        XCTAssertEqual(actual, 7)
    }

    func test_indexLessOrEqualOf_match_shouldBeRightmostMatch() {
        let array = [2, 4, 60, 80, 80, 80, 140, 140, 140, 150, 300, 900].sorted()

        let actual = array.sortedLastIndex(ofElementLessThanOrEqualTo: 80)

        XCTAssertEqual(actual, 5)
    }

    func test_indexLessOrEqualOf_inBetween_shouldBeSmallerNeighbour() {
        let array = [2, 4, 60, 80, 80, 80, 140, 140, 140, 150, 300, 900].sorted()

        let actual = array.sortedLastIndex(ofElementLessThanOrEqualTo: 100)

        XCTAssertEqual(actual, 5)
    }

    // MARK: - sortedLeftInsertionIndex(for:by:) / sortedRightInsertionIndex(for:by:)

    func test_insertionIndex_empty_shouldBe0() {
        let array = [Int]().sorted()

        let input = 4
        let actualLeft = array.sortedLeftInsertionIndex(for: input, by: <)
        let actualRight = array.sortedRightInsertionIndex(for: input, by: <)

        XCTAssertEqual(actualLeft, 0)
        XCTAssertEqual(actualRight, 0)
    }

    func test_insertionIndex_beforeFirst_shouldBe0() {
        let array = [2, 2, 4, 60, 80, 140, 150, 300, 900, 900].sorted()

        let input = -1
        let actualLeft = array.sortedLeftInsertionIndex(for: input, by: <)
        let actualRight = array.sortedRightInsertionIndex(for: input, by: <)

        XCTAssertEqual(actualLeft, 0)
        XCTAssertEqual(actualRight, 0)
    }

    func test_insertionIndex_afterLast_shouldBeLast() {
        let array = [2, 2, 4, 60, 80, 140, 150, 300, 900, 900].sorted()

        let input = 1000
        let actualLeft = array.sortedLeftInsertionIndex(for: input, by: <)
        let actualRight = array.sortedRightInsertionIndex(for: input, by: <)

        XCTAssertEqual(actualLeft, 10)
        XCTAssertEqual(actualRight, 10)
    }

    func test_insertionIndex_inBetween_shouldBeInBetween() {
        let array = [2, 4, 60, 80, 80, 80, 140, 140, 140, 150, 300, 900].sorted()

        let input = 100
        let actualLeft = array.sortedLeftInsertionIndex(for: input, by: <)
        let actualRight = array.sortedRightInsertionIndex(for: input, by: <)

        XCTAssertEqual(actualLeft, 6)
        XCTAssertEqual(actualRight, 6)
    }

    func test_insertionIndex_match_shouldBeLeftmostOrRightmost() {
        let array = [2, 4, 60, 80, 80, 80, 140, 140, 140, 150, 300, 900].sorted()

        let input = 80
        let actualLeft = array.sortedLeftInsertionIndex(for: input, by: <)
        let actualRight = array.sortedRightInsertionIndex(for: input, by: <)

        XCTAssertEqual(actualLeft, 3)
        XCTAssertEqual(actualRight, 6)
    }
}

// MARK: - Util

private extension BinarySearchTests {

    func randomArray(withCount count: Int) -> [Double] {
        let values = -9999999.0 ..< 9999999.0

        var array = [Double]()
        array.reserveCapacity(count)

        for _ in 0..<count {
            array.append(.random(in: values))
        }

        return array
    }
}