| //===--- Algorithms.swift.gyb ---------------------------------*- swift -*-===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2017 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 |
| // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| // |
| //===----------------------------------------------------------------------===// |
| // RUN: rm -rf %t && mkdir -p %t && %gyb -DWORD_BITS=%target-ptrsize %s -o %t/out.swift |
| // RUN: %line-directive %t/out.swift -- %target-build-swift -parse-stdlib %t/out.swift -o %t/a.out -Onone |
| // RUN: %line-directive %t/out.swift -- %target-run %t/a.out |
| |
| // REQUIRES: executable_test |
| |
| import Swift |
| import StdlibUnittest |
| |
| %{ |
| |
| from gyb_stdlib_support import ( |
| TRAVERSALS, |
| collectionForTraversal, |
| defaultIndicesForTraversal, |
| sliceTypeName |
| ) |
| |
| }% |
| |
| //===--- Rotate -----------------------------------------------------------===// |
| //===----------------------------------------------------------------------===// |
| |
| // In the stdlib, this would simply be MutableCollection |
| public protocol MutableCollectionAlgorithms : MutableCollection { |
| /// Rotates the elements of the collection so that the element |
| /// at `middle` ends up first. |
| /// |
| /// - Returns: The new index of the element that was first |
| /// pre-rotation. |
| /// - Complexity: O(*n*) |
| @discardableResult |
| mutating func rotate(shiftingToStart middle: Index) -> Index |
| |
| /// Rotates the elements in `bounds` so that the element |
| /// at `middle` ends up first in `bounds`. |
| /// |
| /// - Returns: The new index of the element that was first |
| /// pre-rotation. |
| /// - Complexity: O(*n*) |
| @discardableResult |
| mutating func rotateSubrange( |
| _ bounds: Range<Index>, shiftingToStart middle: Index |
| ) -> Index |
| } |
| |
| // In the stdlib, this conformance wouldn't be needed |
| extension Array : MutableCollectionAlgorithms { } |
| |
| /// In the stdlib, this would simply be MutableCollection |
| extension MutableCollectionAlgorithms { |
| @inline(__always) |
| internal mutating func _swapNonemptySubrangePrefixes( |
| _ lhs: Range<Index>, _ rhs: Range<Index> |
| ) -> (Index, Index) { |
| _sanityCheck(!lhs.isEmpty) |
| _sanityCheck(!rhs.isEmpty) |
| |
| var p = lhs.lowerBound |
| var q = rhs.lowerBound |
| repeat { |
| swap(&self[p], &self[q]) |
| formIndex(after: &p) |
| formIndex(after: &q) |
| } |
| while p != lhs.upperBound && q != rhs.upperBound |
| return (p, q) |
| } |
| |
| @inline(__always) |
| internal mutating func _swapSubrangePrefixes( |
| _ lhs: Range<Index>, with rhs: Range<Index> |
| ) -> (Index, Index) { |
| return lhs.isEmpty || rhs.isEmpty |
| ? (lhs.lowerBound, rhs.lowerBound) |
| : _swapNonemptySubrangePrefixes(lhs, rhs) |
| } |
| |
| /// Rotates the elements of the collection so that the element |
| /// at `middle` ends up first. |
| /// |
| /// - Returns: The new index of the element that was first |
| /// pre-rotation. |
| /// - Complexity: O(*n*) |
| @discardableResult |
| public mutating func rotate(shiftingToStart middle: Index) -> Index { |
| return rotateSubrange(startIndex..<endIndex, shiftingToStart: middle) |
| } |
| |
| /// Rotates the elements in `bounds` so that the element |
| /// at `middle` ends up first. |
| /// |
| /// - Returns: The new index of the element that was first |
| /// pre-rotation. |
| /// - Complexity: O(*n*) |
| @discardableResult |
| public mutating func rotateSubrange( |
| _ bounds: Range<Index>, shiftingToStart middle: Index |
| ) -> Index { |
| return _rotateSubrangeForward(bounds, shiftingToStart: middle) |
| } |
| |
| // Broken out of the method above for testability purposes |
| @discardableResult |
| internal mutating func _rotateSubrangeForward( |
| _ bounds: Range<Index>, shiftingToStart middle: Index |
| ) -> Index { |
| var m = middle, s = bounds.lowerBound |
| let e = bounds.upperBound |
| |
| // Handle the trivial cases |
| if s == m { return e } |
| if m == e { return s } |
| |
| // We have two regions of possibly-unequal length that need to be |
| // exchanged. The return value of this method is going to be the |
| // position following that of the element that is currently last |
| // (element j). |
| // |
| // [a b c d e f g|h i j] or [a b c|d e f g h i j] |
| // ^ ^ ^ ^ ^ ^ |
| // s m e s m e |
| // |
| var ret = e // start with a known incorrect result. |
| while true { |
| // Exchange the leading elements of each region (up to the |
| // length of the shorter region). |
| // |
| // [a b c d e f g|h i j] or [a b c|d e f g h i j] |
| // ^^^^^ ^^^^^ ^^^^^ ^^^^^ |
| // [h i j d e f g|a b c] or [d e f|a b c g h i j] |
| // ^ ^ ^ ^ ^ ^ ^ ^ |
| // s s1 m m1/e s s1/m m1 e |
| // |
| let (s1, m1) = _swapNonemptySubrangePrefixes(s..<m, m..<e) |
| |
| if m1 == e { |
| // Left-hand case: we have moved element j into position. if |
| // we haven't already, we can capture the return value which |
| // is in s1. |
| // |
| // Note: the STL breaks the loop into two just to avoid this |
| // comparison once the return value is known. I'm not sure |
| // it's a worthwhile optimization, though. |
| if ret == e { ret = s1 } |
| |
| // If both regions were the same size, we're done. |
| if s1 == m { break } |
| } |
| |
| // Now we have a smaller problem that is also a rotation, so we |
| // can adjust our bounds and repeat. |
| // |
| // h i j[d e f g|a b c] or d e f[a b c|g h i j] |
| // ^ ^ ^ ^ ^ ^ |
| // s m e s m e |
| s = s1 |
| if s == m { m = m1 } |
| } |
| |
| return ret |
| } |
| } |
| |
| extension MutableCollection where Self: BidirectionalCollection { |
| |
| // This could be internal, but until we have pinned accessors for |
| // slices, every mutating algorithm needs a version that takes |
| // indices in order to get performance. |
| |
| /// Reverses the elements in the given subrange in place. |
| /// |
| /// var characters: [Character] = ["^", "C", "a", "f", "é", "$""] |
| /// let r = characters.index(after: characters.startIndex) |
| /// ..< characters.index(before: characters.endIndex) |
| /// characters.reverseSubrange(r) |
| /// print(cafe.characters) |
| /// // Prints "["^", "é", "f", "a", "C", "$"] |
| /// |
| /// - Complexity: O(*n*), where *n* is the number of elements in the |
| /// subrange. |
| public mutating func reverseSubrange(_ bounds: Range<Index>) { |
| if bounds.isEmpty { return } |
| var f = bounds.lowerBound |
| var l = index(before: bounds.upperBound) |
| while f < l { |
| swap(&self[f], &self[l]) |
| formIndex(after: &f) |
| formIndex(before: &l) |
| } |
| } |
| |
| @inline(__always) |
| @discardableResult |
| internal mutating func _reverseUntil(_ limit: Index) -> (Index, Index) { |
| var f = startIndex |
| var l = endIndex |
| while f != limit && l != limit { |
| formIndex(before: &l) |
| swap(&self[f], &self[l]) |
| formIndex(after: &f) |
| } |
| return (f, l) |
| } |
| |
| /// Rotates the elements of the collection so that the element |
| /// at `middle` ends up first. |
| /// |
| /// - Returns: The new index of the element that was first |
| /// pre-rotation. |
| /// - Complexity: O(*n*) |
| @discardableResult |
| public mutating func rotate(shiftingToStart middle: Index) -> Index { |
| // FIXME: this algorithm should be benchmarked on arrays against |
| // the forward Collection algorithm above to prove that it's |
| // actually faster. The other one sometimes does more swaps, but |
| // has better locality properties. Similarly, we've omitted a |
| // specialization of rotate for RandomAccessCollection that uses |
| // cycles per section 11.4 in "From Mathematics to Generic |
| // Programming" by A. Stepanov because it has *much* worse |
| // locality properties than either of the other implementations. |
| // Benchmarks should be performed for that algorithm too, just to |
| // be sure. |
| reverseSubrange(startIndex..<middle) |
| reverseSubrange(middle..<endIndex) |
| let (p, q) = _reverseUntil(middle) |
| reverseSubrange(p..<q) |
| return middle == p ? q : p |
| } |
| } |
| |
| /// Returns the greatest common denominator for `m` and `n`. |
| internal func _gcd(_ m: Int, _ n: Int) -> Int { |
| var (m, n) = (m, n) |
| while n != 0 { |
| let t = m % n |
| m = n |
| n = t |
| } |
| return m |
| } |
| |
| extension MutableCollection where Self: RandomAccessCollection, |
| SubSequence: MutableCollection, SubSequence: RandomAccessCollection { |
| |
| /// Rotates elements through a cycle, using `sourceForIndex` to generate |
| /// the source index for each movement. |
| @inline(__always) |
| internal mutating func _rotateCycle(start: Index, |
| transform sourceForIndex: (Index) -> Index) |
| { |
| let tmp = self[start] |
| var (i, j) = (start, sourceForIndex(start)) |
| while j != start { |
| self[i] = self[j] |
| i = j |
| j = sourceForIndex(j) |
| } |
| self[i] = tmp |
| } |
| |
| /// Rotates the elements of the collection so that the element |
| /// at `middle` ends up first. |
| /// |
| /// - Returns: The new index of the element that was first |
| /// pre-rotation. |
| /// - Complexity: O(*n*) |
| @discardableResult |
| public mutating func rotateRandomAccess( |
| shiftingToStart middle: Index) -> Index |
| { |
| if middle == startIndex { return endIndex } |
| if middle == endIndex { return startIndex } |
| |
| // The distance to move an element that is moving -> |
| let plus = distance(from: startIndex, to: middle) |
| // The distance to move an element that is moving <- |
| let minus = distance(from: endIndex, to: middle) |
| // The new pivot point, aka the destination for the first element |
| let pivot = index(startIndex, offsetBy: -minus) |
| |
| // If the difference moving forward and backward are relative primes, |
| // the entire rotation will be completed in one cycle. Otherwise, repeat |
| // cycle, moving the start point forward with each cycle. |
| let cycles = _gcd(numericCast(plus), -numericCast(minus)) |
| |
| for cycle in 1...cycles { |
| _rotateCycle(start: index(startIndex, offsetBy: numericCast(cycle))) { |
| index($0, offsetBy: $0 < pivot ? plus : minus) |
| } |
| } |
| return pivot |
| } |
| } |
| |
| //===--- ConcatenatedCollection -------------------------------------------===// |
| //===----------------------------------------------------------------------===// |
| |
| // ConcatenatedCollection improves on a flattened array or other collection by |
| // allowing random-access traversal if the underlying collections are |
| // random-access. |
| // |
| // Q: Add a ConcatenatedSequence for consistency? Would be nice to be able to |
| // call `let seqAB = concatenate(seqA, seqB)`. |
| |
| /// Represents a position in either the first or second collection of a |
| /// `ConcatenatedCollection`. |
| internal enum _ConcatenatedCollectionIndexRepresentation< |
| I1 : Comparable, I2 : Comparable |
| > { |
| case first(I1) |
| case second(I2) |
| } |
| |
| /// A position in a `ConcatenatedCollection` collection. |
| public struct ConcatenatedCollectionIndex< |
| C1 : Collection, C2 : Collection |
| > : Comparable { |
| /// Creates a new index into the first underlying collection. |
| internal init(first i: C1.Index) { |
| _position = .first(i) |
| } |
| |
| /// Creates a new index into the second underlying collection. |
| internal init(second i: C2.Index) { |
| _position = .second(i) |
| } |
| |
| internal let _position: |
| _ConcatenatedCollectionIndexRepresentation<C1.Index, C2.Index> |
| } |
| |
| public func < <C1: Collection, C2: Collection>( |
| lhs: ConcatenatedCollectionIndex<C1, C2>, |
| rhs: ConcatenatedCollectionIndex<C1, C2> |
| ) -> Bool { |
| switch (lhs._position, rhs._position) { |
| case (.first, .second): |
| return true |
| case (.second, .first): |
| return false |
| case let (.first(l), .first(r)): |
| return l < r |
| case let (.second(l), .second(r)): |
| return l < r |
| } |
| } |
| |
| public func == <C1: Collection, C2: Collection>( |
| lhs: ConcatenatedCollectionIndex<C1, C2>, |
| rhs: ConcatenatedCollectionIndex<C1, C2> |
| ) -> Bool { |
| switch (lhs._position, rhs._position) { |
| case let (.first(l), .first(r)): |
| return l == r |
| case let (.second(l), .second(r)): |
| return l == r |
| default: |
| return false |
| } |
| } |
| |
| % for Traversal in TRAVERSALS: |
| % Collection = collectionForTraversal(Traversal) |
| % Self = "Concatenated" + Collection |
| |
| /// A concatenation of two collections with the same element type. |
| public struct ${Self}<C1 : ${Collection}, C2: ${Collection}>: ${Collection} |
| where C1.Iterator.Element == C2.Iterator.Element { |
| |
| init(_base1: C1, base2: C2) { |
| self._base1 = _base1 |
| self._base2 = base2 |
| } |
| |
| public typealias Index = ConcatenatedCollectionIndex<C1, C2> |
| |
| public var startIndex: Index { |
| // If `_base1` is empty, then `_base2.startIndex` is either a valid position |
| // of an element or equal to `_base2.endIndex`. |
| return _base1.isEmpty |
| ? ConcatenatedCollectionIndex(second: _base2.startIndex) |
| : ConcatenatedCollectionIndex(first: _base1.startIndex) |
| } |
| |
| public var endIndex: Index { |
| return ConcatenatedCollectionIndex(second: _base2.endIndex) |
| } |
| |
| public subscript(i: Index) -> C1.Iterator.Element { |
| switch i._position { |
| case let .first(i): |
| return _base1[i] |
| case let .second(i): |
| return _base2[i] |
| } |
| } |
| |
| public func index(after i: Index) -> Index { |
| switch i._position { |
| case let .first(i): |
| _sanityCheck(i != _base1.endIndex) |
| let next = _base1.index(after: i) |
| return next == _base1.endIndex |
| ? ConcatenatedCollectionIndex(second: _base2.startIndex) |
| : ConcatenatedCollectionIndex(first: next) |
| case let .second(i): |
| return ConcatenatedCollectionIndex(second: _base2.index(after: i)) |
| } |
| } |
| |
| % if Traversal in ['Bidirectional', 'RandomAccess']: |
| public func index(before i: Index) -> Index { |
| assert(i != startIndex, "Can't advance before startIndex") |
| switch i._position { |
| case let .first(i): |
| return ConcatenatedCollectionIndex(first: _base1.index(before: i)) |
| case let .second(i): |
| return i == _base2.startIndex |
| ? ConcatenatedCollectionIndex( |
| first: _base1.index(before: _base1.endIndex)) |
| : ConcatenatedCollectionIndex(second: _base2.index(before: i)) |
| } |
| } |
| % end |
| |
| % if Traversal is 'RandomAccess': |
| public func index(_ i: Index, offsetBy n: ${Self}.IndexDistance) -> Index { |
| if n == 0 { return i } |
| return n > 0 ? _offsetForward(i, by: n) : _offsetBackward(i, by: -n) |
| } |
| |
| internal func _offsetForward( |
| _ i: Index, by n: ${Self}.IndexDistance |
| ) -> Index { |
| switch i._position { |
| case let .first(i): |
| let d: ${Self}.IndexDistance = numericCast( |
| _base1.distance(from: i, to: _base1.endIndex)) |
| if n < d { |
| return ConcatenatedCollectionIndex( |
| first: _base1.index(i, offsetBy: numericCast(n))) |
| } else { |
| return ConcatenatedCollectionIndex( |
| second: _base2.index(_base2.startIndex, offsetBy: numericCast(n - d))) |
| } |
| case let .second(i): |
| return ConcatenatedCollectionIndex( |
| second: _base2.index(i, offsetBy: numericCast(n))) |
| } |
| } |
| |
| internal func _offsetBackward( |
| _ i: Index, by n: ${Self}.IndexDistance |
| ) -> Index { |
| switch i._position { |
| case let .first(i): |
| return ConcatenatedCollectionIndex( |
| first: _base1.index(i, offsetBy: -numericCast(n))) |
| case let .second(i): |
| let d: ${Self}.IndexDistance = numericCast( |
| _base2.distance(from: _base2.startIndex, to: i)) |
| if n <= d { |
| return ConcatenatedCollectionIndex( |
| second: _base2.index(i, offsetBy: -numericCast(n))) |
| } else { |
| return ConcatenatedCollectionIndex( |
| first: _base1.index(_base1.endIndex, offsetBy: -numericCast(n - d))) |
| } |
| } |
| } |
| % end |
| |
| let _base1: C1 |
| let _base2: C2 |
| } |
| |
| /// Returns a new collection that presents a view onto the elements of the |
| /// first collection and then the elements of the second collection. |
| func concatenate< |
| C1 : ${Collection}, C2 : ${Collection} |
| >(_ first: C1, _ second: C2) -> ${Self}<C1, C2> |
| where C1.Iterator.Element == C2.Iterator.Element { |
| return ${Self}(_base1: first, base2: second) |
| } |
| |
| % end |
| |
| //===--- RotatedCollection ------------------------------------------------===// |
| //===----------------------------------------------------------------------===// |
| |
| /// A position in a rotated collection. |
| public struct RotatedCollectionIndex<Base : Collection> : Comparable |
| where Base.SubSequence: Collection { |
| internal let _index: |
| ConcatenatedCollectionIndex<Base.SubSequence, Base.SubSequence> |
| } |
| |
| public func < <Base: Collection>( |
| lhs: RotatedCollectionIndex<Base>, rhs: RotatedCollectionIndex<Base> |
| ) -> Bool |
| where Base.SubSequence: Collection { |
| return lhs._index < rhs._index |
| } |
| |
| public func == <Base: Collection>( |
| lhs: RotatedCollectionIndex<Base>, rhs: RotatedCollectionIndex<Base> |
| ) -> Bool |
| where Base.SubSequence: Collection { |
| return lhs._index == rhs._index |
| } |
| |
| % for Traversal in TRAVERSALS: |
| % Collection = collectionForTraversal(Traversal) |
| % Self = "Rotated" + Collection |
| |
| /// A rotated view onto a `${Collection}`. |
| public struct ${Self}< |
| Base : ${Collection} |
| > : ${Collection} |
| where Base.SubSequence: ${Collection} { |
| let _concatenation: Concatenated${Collection}< |
| Base.SubSequence, Base.SubSequence> |
| |
| init(_base: Base, shiftingToStart i: Base.Index) { |
| _concatenation = concatenate(_base.suffix(from: i), _base.prefix(upTo: i)) |
| } |
| |
| public typealias Index = RotatedCollectionIndex<Base> |
| |
| public var startIndex: Index { |
| return RotatedCollectionIndex(_index: _concatenation.startIndex) |
| } |
| |
| public var endIndex: Index { |
| return RotatedCollectionIndex(_index: _concatenation.endIndex) |
| } |
| |
| public subscript(i: Index) -> Base.SubSequence.Iterator.Element { |
| return _concatenation[i._index] |
| } |
| |
| public func index(after i: Index) -> Index { |
| return RotatedCollectionIndex(_index: _concatenation.index(after: i._index)) |
| } |
| |
| % if Traversal in ['Bidirectional', 'RandomAccess']: |
| public func index(before i: Index) -> Index { |
| return RotatedCollectionIndex( |
| _index: _concatenation.index(before: i._index)) |
| } |
| % end |
| |
| public func index(_ i: Index, offsetBy n: ${Self}.IndexDistance) -> Index { |
| return RotatedCollectionIndex( |
| _index: _concatenation.index(i._index, offsetBy: n)) |
| } |
| |
| /// The shifted position of the base collection's `startIndex`. |
| public var shiftedStartIndex: Index { |
| return RotatedCollectionIndex( |
| _index: ConcatenatedCollectionIndex( |
| second: _concatenation._base2.startIndex) |
| ) |
| } |
| } |
| |
| extension ${Collection} where SubSequence: ${Collection} { |
| /// Returns a view of this collection with the elements reordered such the |
| /// element at the given position ends up first. |
| /// |
| /// The subsequence of the collection up to `i` is shifted to after the |
| /// subsequence starting at `i`. The order of the elements within each |
| /// partition is otherwise unchanged. |
| /// |
| /// let a = [10, 20, 30, 40, 50, 60, 70] |
| /// let r = a.rotated(shiftingToStart: 3) |
| /// // r.elementsEqual([40, 50, 60, 70, 10, 20, 30]) |
| /// |
| /// - Parameter i: The position in the collection that should be first in the |
| /// result. `i` must be a valid index of the collection. |
| /// - Returns: A rotated view on the elements of this collection, such that |
| /// the element at `i` is first. |
| func rotated(shiftingToStart i: Index) -> ${Self}<Self> { |
| return ${Self}(_base: self, shiftingToStart: i) |
| } |
| } |
| |
| % end |
| |
| //===--- Stable Partition -------------------------------------------------===// |
| //===----------------------------------------------------------------------===// |
| |
| extension BidirectionalCollection |
| where Self : MutableCollectionAlgorithms, |
| SubSequence : BidirectionalCollection, |
| SubSequence.Index == Self.Index { |
| |
| @discardableResult |
| mutating func stablePartition( |
| choosingStartGroupBy p: (Iterator.Element) -> Bool |
| ) -> Index { |
| return stablyPartitionSubrange( |
| startIndex..<endIndex, |
| choosingStartGroupBy: p |
| ) |
| } |
| |
| mutating func stablyPartitionSubrange( |
| _ bounds: Range<Index>, |
| choosingStartGroupBy p: (Iterator.Element) -> Bool |
| ) -> Index { |
| return _stablyPartitionSubrange( |
| bounds, |
| distance: distance(from: bounds.lowerBound, to: bounds.upperBound), |
| choosingStartGroupBy: p |
| ) |
| } |
| |
| mutating func _stablyPartitionSubrange( |
| _ bounds: Range<Index>, |
| distance n: IndexDistance, |
| choosingStartGroupBy p: (Iterator.Element) -> Bool |
| ) -> Index { |
| assert(n >= 0) |
| let (start, end) = (bounds.lowerBound, bounds.upperBound) |
| assert(n == distance(from: start, to: end)) |
| if n == 0 { return start } |
| if n == 1 { |
| return p(self[start]) ? index(after: start) : start |
| } |
| |
| |
| // divide and conquer. |
| let d = n / numericCast(2) |
| let m = index(start, offsetBy: d) |
| |
| // TTTTTTTTT s FFFFFFF m ????????????? |
| let s = _stablyPartitionSubrange( |
| start..<m, distance: d, choosingStartGroupBy: p) |
| |
| // TTTTTTTTT s FFFFFFF m TTTTTTT e FFFFFFFF |
| let e = _stablyPartitionSubrange( |
| m..<end, distance: n - d, choosingStartGroupBy: p) |
| |
| // TTTTTTTTT s TTTTTTT m FFFFFFF e FFFFFFFF |
| return self.rotateSubrange(s..<e, shiftingToStart: m) |
| } |
| } |
| |
| extension Collection { |
| func stablyPartitioned( |
| choosingStartGroupBy p: (Iterator.Element) -> Bool |
| ) -> [Iterator.Element] { |
| var a = Array(self) |
| a.stablePartition(choosingStartGroupBy: p) |
| return a |
| } |
| } |
| |
| extension LazyCollectionProtocol |
| where Iterator.Element == Elements.Iterator.Element { |
| func stablyPartitioned( |
| choosingStartGroupBy p: (Iterator.Element) -> Bool |
| ) -> LazyCollection<[Iterator.Element]> { |
| return elements.stablyPartitioned(choosingStartGroupBy: p).lazy |
| } |
| } |
| |
| extension Collection { |
| /// Returns the index of the first element in the collection |
| /// that matches the predicate. |
| /// |
| /// The collection must already be partitioned according to the |
| /// predicate, as if `self.partition(by: predicate)` had already |
| /// been called. |
| func partitionPoint( |
| where predicate: (Iterator.Element) throws -> Bool |
| ) rethrows -> Index { |
| var n = distance(from: startIndex, to: endIndex) |
| var r = startIndex..<endIndex |
| |
| while n > 0 { |
| let half = n / 2 |
| let mid = index(r.lowerBound, offsetBy: half) |
| if try predicate(self[mid]) { |
| r = r.lowerBound..<mid |
| n = half |
| } |
| else { |
| r = index(after: mid)..<r.upperBound |
| n -= half + 1 |
| } |
| } |
| return r.lowerBound |
| } |
| } |
| |
| //===--- Tests ------------------------------------------------------------===// |
| //===----------------------------------------------------------------------===// |
| |
| var suite = TestSuite("Algorithms") |
| |
| suite.test("reverseSubrange") { |
| for l in 0..<10 { |
| let a = Array(0..<l) |
| |
| for p in a.startIndex...a.endIndex { |
| let prefix = a.prefix(upTo: p) |
| for q in p...l { |
| let suffix = a.suffix(from: q) |
| var b = a |
| b.reverseSubrange(p..<q) |
| expectEqual( |
| b, |
| Array([prefix, ArraySlice(a[p..<q].reversed()), suffix].joined())) |
| } |
| } |
| } |
| } |
| |
| suite.test("rotate") { |
| for l in 0..<11 { |
| let a = Array(0..<l) |
| |
| for p in a.startIndex...a.endIndex { |
| let prefix = a.prefix(upTo: p) |
| for q in p...l { |
| let suffix = a.suffix(from: q) |
| |
| for m in p...q { |
| var b = a |
| let r0 = b._rotateSubrangeForward(p..<q, shiftingToStart: m) |
| let rotated = Array([prefix, a[m..<q], a[p..<m], suffix].joined()) |
| expectEqual(b, rotated) |
| expectEqual(r0, a.index(p, offsetBy: a[m..<q].count)) |
| |
| b = a |
| let r1 = b.rotateSubrange(p..<q, shiftingToStart: m) |
| expectEqual(b, rotated) |
| expectEqual(r1, r0) |
| } |
| } |
| var b = a |
| b.rotate(shiftingToStart: p) |
| expectEqual(b, Array(a.rotated(shiftingToStart: p))) |
| } |
| } |
| } |
| |
| suite.test("rotateRandomAccess") { |
| for l in 0..<11 { |
| let a = Array(0..<l) |
| |
| for p in a.startIndex...a.endIndex { |
| let prefix = a.prefix(upTo: p) |
| for q in p...l { |
| let suffix = a.suffix(from: q) |
| |
| for m in p...q { |
| var b = a |
| let r0 = b[p..<q].rotateRandomAccess(shiftingToStart: m) |
| let rotated = Array([prefix, a[m..<q], a[p..<m], suffix].joined()) |
| expectEqual(b, rotated) |
| expectEqual(r0, a.index(p, offsetBy: a[m..<q].count)) |
| |
| b = a |
| let r1 = b[p..<q].rotateRandomAccess(shiftingToStart: m) |
| expectEqual(b, rotated) |
| expectEqual(r1, r0) |
| } |
| } |
| var b = a |
| b.rotateRandomAccess(shiftingToStart: p) |
| expectEqual(b, Array(a.rotated(shiftingToStart: p))) |
| } |
| } |
| } |
| |
| suite.test("concatenate") { |
| for x in 0...6 { |
| for y in 0...x { |
| let r1 = 0..<y |
| let r2 = y..<x |
| expectEqual(Array(0..<x), Array(concatenate(r1, r2))) |
| } |
| } |
| |
| let c1 = concatenate([1, 2, 3, 4, 5], 6...10) |
| let c2 = concatenate(1...5, [6, 7, 8, 9, 10]) |
| expectEqual(Array(1...10), Array(c1)) |
| expectEqual(Array(1...10), Array(c2)) |
| |
| let h = "Hello, " |
| let w = "world!" |
| let hw = concatenate(h.characters, w.characters) |
| expectEqual("Hello, world!", String(hw)) |
| } |
| |
| suite.test("stablePartition") { |
| for l in 0..<13 { |
| let a = Array(0..<l) |
| |
| for p in a.startIndex...a.endIndex { |
| let prefix = a.prefix(upTo: p) |
| for q in p...l { |
| let suffix = a.suffix(from: q) |
| |
| let subrange = a[p..<q] |
| |
| for modulus in 1...5 { |
| let f = { $0 % modulus == 0 } |
| let notf = { !f($0) } |
| |
| var b = a |
| var r = b.stablyPartitionSubrange(p..<q, choosingStartGroupBy: f) |
| expectEqual(b.prefix(upTo:p), prefix) |
| expectEqual(b.suffix(from:q), suffix) |
| expectEqual(b[p..<r], ArraySlice(subrange.filter(f))) |
| expectEqual(b[r..<q], ArraySlice(subrange.filter(notf))) |
| |
| b = a |
| r = b.stablyPartitionSubrange(p..<q, choosingStartGroupBy: notf) |
| expectEqual(b.prefix(upTo:p), prefix) |
| expectEqual(b.suffix(from:q), suffix) |
| expectEqual(b[p..<r], ArraySlice(subrange.filter(notf))) |
| expectEqual(b[r..<q], ArraySlice(subrange.filter(f))) |
| } |
| } |
| |
| for modulus in 1...5 { |
| let f = { $0 % modulus == 0 } |
| let notf = { !f($0) } |
| var b = a |
| var r = b.stablePartition(choosingStartGroupBy: f) |
| expectEqual(b.prefix(upTo: r), ArraySlice(a.filter(f))) |
| expectEqual(b.suffix(from: r), ArraySlice(a.filter(notf))) |
| |
| b = a |
| r = b.stablePartition(choosingStartGroupBy: notf) |
| expectEqual(b.prefix(upTo: r), ArraySlice(a.filter(notf))) |
| expectEqual(b.suffix(from: r), ArraySlice(a.filter(f))) |
| } |
| } |
| } |
| } |
| |
| suite.test("partitionPoint") { |
| for i in 0..<7 { |
| for j in i..<11 { |
| for k in i...j { |
| let p = (i..<j).partitionPoint { $0 >= k } |
| expectGE(p, i) |
| expectLE(p, j) |
| expectEqual(p, k) |
| } |
| } |
| } |
| } |
| |
| runAllTests() |
| |