OffsetBound

offset_bound_gist.swift

// The below will be a customization point on Collection. For the purposes of
// this gist, we'll fake/approximate it with static overloads

extension Collection {
  /// Returns an index `distance` positions prior to `i` if it exists.
  ///
  /// Other methods such as `index(_:offetBy:)` must not be passed a negative
  /// offset if the collection is bidirectional. This method will perform a
  /// negative offset even if the collection is not bidirectional, by using a
  /// less efficient means. `BidirectionalCollection` customizes this with a
  /// more efficient implementation.
  ///
  /// - Parameters
  ///   - i: a valid index of the collection.
  ///   - distance: The distance to offset `i` backwards. `distance` must be
  ///     positive or zero.
  /// - Returns: The index `distance` positions prior to `i` if in bounds, else
  ///   `nil`.
  ///
  /// - Complexity:
  ///   - O(1) if the collection conforms to `RandomAccessCollection`.
  ///   - O(*k*), where *k* is equal to `distance` if the collection conforms
  ///     to `BidirectionalCollection`.
  ///   - Otherwise, O(*n*), where *n* is the length of the collection.
  func _reverseOffsetIndex(_ i: Index, by distance: Int) -> Index? {
    if distance == 0 { return i }

    precondition(distance > 0, "Negative distance")
    let amount = self.distance(from: startIndex, to: i) - distance
    guard amount >= 0 else { return nil }

    return index(startIndex, offsetBy: amount)
  }
}
extension BidirectionalCollection {
  func _reverseOffsetIndex(_ i: Index, by distance: Int) -> Index? {
    precondition(distance >= 0, "Negative distance")
    return index(i, offsetBy: -distance, limitedBy: startIndex)
  }
}

/// A position in a collection specified as an offset from either the first
/// or last element of the collection (i.e. the collection's bounds).
///
/// You can use an `OffsetBound` to access an index or element of a collection
/// as well as extract a slice. For example:
///
///       let str = "abcdefghijklmnopqrstuvwxyz"
///       print(str[.last]) // Optional("z")
///       print(str[.last - 2]) // Optional("x")
///       print(str[.first + 26]) // nil
///       print(str[.first + 3 ..< .first + 6]) // "def"
///       print(str[.first + 3 ..< .last - 2]) // "defghijklmnopqrstuvw"
///
/// `OffsetBound`s also provide a convenient way of working with slice types
/// over collections whose index type is `Int`. Slice types share indices with
/// their base collection, so `0` doesn't always mean the first element. For
/// example:
///
///     let array = [1,2,3,4,5,6]
///     print(array[2...][3) // 4
///     print(array[2...][.first + 3]!) // 6
///
public struct OffsetBound {
  internal enum Anchor {
    case fromStart
    case fromEnd
  }
  internal var anchor: Anchor
  internal var offset: Int
}

extension OffsetBound {
  internal init(fromStart: Int) {
    self.init(anchor: .fromStart, offset: fromStart)
  }

  internal init(fromEnd: Int) {
    self.init(anchor: .fromEnd, offset: fromEnd)
  }

  internal func advanced(by: Int) -> OffsetBound {
    return OffsetBound(anchor: self.anchor, offset: self.offset + by)
  }
}

extension OffsetBound {
  /// The position of the first element of a nonempty collection, corresponding
  /// to `startIndex`.
  public static var first: OffsetBound { return OffsetBound(fromStart: 0) }

  /// The position of the last element of a nonempty collection, corresponding
  /// to `index(before: endIndex)`.
  public static var last: OffsetBound { return OffsetBound(fromEnd: -1) }

  /// Returns a bound that offsets the given bound by the specified distance.
  ///
  /// For example:
  ///
  ///     .first + 2  // The position of the 3rd element
  ///     .last + 1   // One past the last element, corresponding to `endIndex`
  ///
  public static func +(_ lhs: OffsetBound, _ rhs: Int) -> OffsetBound {
    return lhs.advanced(by: rhs)
  }

  /// Returns a bound that offsets the given bound by the specified distance
  /// backwards.
  ///
  /// For example:
  ///
  ///     .last - 2 // Two positions before the last element's position
  ///
  public static func -(_ lhs: OffsetBound, _ rhs: Int) -> OffsetBound {
    return lhs.advanced(by: -rhs)
  }
}

extension OffsetBound: Comparable {

  /// Compare the positions represented by two `OffsetBound`s.
  ///
  /// Offsets relative to `.first` are always less than those relative to
  /// `.last`, as there are arbitrarily many offsets between the two
  /// extremities. Offsets from the same bound are ordered by their
  /// corresponding positions. For example:
  ///
  ///     .first + n < .last - m    // true for all values of n and m
  ///     .first + n < .first + m  // equivalent to n < m
  ///     .last - n < .last - m      // equivalent to n > m
  ///
  public static func < (_ lhs: OffsetBound, _ rhs: OffsetBound) -> Bool {
    if lhs.anchor == rhs.anchor { return lhs.offset < rhs.offset }

    return lhs.anchor == .fromStart
  }

  /// Compare two `OffsetBound`s to see if they represent equivalent positions.
  ///
  /// This is only true if both offset the same bound by the same amount. For
  /// example:
  ///
  ///     .first + n == .last - m    // false for all values of n and m
  ///     .first + n == .first + m  // equivalent to n == m
  ///
  public static func == (_ lhs: OffsetBound, _ rhs: OffsetBound) -> Bool {
    return lhs.anchor == rhs.anchor && lhs.offset == rhs.offset
  }
}

extension Collection {
  /// Returns the corresponding index for the provided offset, if it exists,
  /// else returns nil.
  ///
  /// - Complexity:
  ///   - O(1) if the collection conforms to `RandomAccessCollection`.
  ///   - O(*k*) where *k* is equal to the offset if the collection conforms to
  ///     `BidirectionalCollection`.
  ///   - O(*k*) if `position` is `.first + n` for any n, or `.last + 1`.
  ///   - Otherwise, O(*n*) where *n* is the length of the collection.
  public func index(at position: OffsetBound) -> Index? {
    switch position.anchor {
      case .fromStart:
        guard position.offset >= 0 else { return nil }

        return self.index(
          self.startIndex, offsetBy: position.offset, limitedBy: self.endIndex)

      case .fromEnd:
        guard position.offset <= 0 else { return nil }

        return self._reverseOffsetIndex(self.endIndex, by: -position.offset)
    }
  }

  // Returns an index for this collection, clamping to startIndex and endIndex
  // if out of bounds in the respective direction.
  internal func _clampedIndex(at bound: OffsetBound) -> Index {
    switch bound.anchor {
      case .fromStart:
        guard bound.offset >= 0 else { return self.startIndex }

        return self.index(
          self.startIndex, offsetBy: bound.offset, limitedBy: self.endIndex
        ) ?? self.endIndex

      case .fromEnd:
        guard bound.offset <= 0 else { return endIndex }

        return self._reverseOffsetIndex(
          self.endIndex, by: -bound.offset
        ) ?? self.startIndex
    }
  }
}

// To get a Range<OffsetBound> from a RangeExpression<OffsetBound>
private struct OffsetBoundConverter: Collection {
  fileprivate var startIndex: OffsetBound { return .first }
  fileprivate var endIndex: OffsetBound { return .last + 1 }

  fileprivate func index(after bound: OffsetBound) -> OffsetBound {
    return bound.advanced(by: 1)
  }

  fileprivate subscript(bound: OffsetBound) -> OffsetBound { return bound }
  fileprivate subscript(bounds: Range<OffsetBound>) -> Range<OffsetBound> {
    return bounds
  }

  fileprivate init() { }
}

extension RangeExpression where Bound == OffsetBound {
  internal func _relative<C: Collection>(to c: C) -> Range<C.Index> {
    let range = self.relative(to: OffsetBoundConverter())
    let lower = c._clampedIndex(at: range.lowerBound)
    let upper = c._clampedIndex(at: range.upperBound)
    return lower ..< max(lower, upper)
  }
}

extension Collection {
  internal func _subscriptGet(_ bound: OffsetBound) -> Element? {
    guard let idx = self.index(at: bound), idx != endIndex else { return nil }
    return self[idx]
  }

  internal func _subscriptGet<ORE: RangeExpression>(
    _ range: ORE
  ) -> SubSequence where ORE.Bound == OffsetBound {
    return self[range._relative(to: self)]
  }

  /// Returns the corresponding element for the provided offset, if it exists,
  /// else returns nil.
  ///
  /// Example:
  ///
  ///       let abcs = "abcdefg"
  ///       print(abcs[.last]) // Optional("g")
  ///       print(abcs[.last - 2]) // Optional("e")
  ///       print(abcs[.first + 8]) // nil
  ///
  /// - Complexity:
  ///   - O(1) if the collection conforms to `RandomAccessCollection`.
  ///   - O(*k*) where *k* is equal to the offset if the collection conforms to
  ///     `BidirectionalCollection`.
  ///   - O(*k*) if `position` is `.first + n` for any n, or `.last + 1`.
  ///   - Otherwise, O(*n*) where *n* is the length of the collection.
  public subscript(position: OffsetBound) -> Element? {
    return _subscriptGet(position)
  }

  /// Returns the contiguous subrange of elements corresponding to the provided
  /// offsets.
  ///
  /// Example:
  ///
  ///       let abcs = "abcdefg"
  ///       print(abcs[.first + 1 ..< .first + 6]) // "bcdef"
  ///       print(abcs[.first + 1 ..< .last - 1]) // "bcde"
  ///
  /// - Complexity:
  ///   - O(1) if the collection conforms to `RandomAccessCollection`.
  ///   - O(*k*) where *k* is equal to the larger offset if the collection
  ///     conforms to `BidirectionalCollection`.
  ///   - O(*k*) if the offsets are `.first + n` for any n or `.last + 1`.
  ///   - Otherwise, O(*n*) where *n* is the length of the collection.
  public subscript<ORE: RangeExpression>(
    range: ORE
  ) -> SubSequence where ORE.Bound == OffsetBound {
    return _subscriptGet(range)
  }
}

extension RangeReplaceableCollection {
  /// Replaces the specified subrange of elements with the given collection.
  ///
  /// This method has the effect of removing the specified range of elements
  /// from the collection and inserting the new elements at the same location.
  /// The number of new elements need not match the number of elements being
  /// removed.
  ///
  /// In this example, two characters in the middle of a string are
  /// replaced by the three elements of a `Repeated<Character>` instance.
  ///
  ///      var animals = "🐕🐈🐱🐩"
  ///      let dogFaces = repeatElement("🐶" as Character, count: 3)
  ///      animals.replaceSubrange(.first + 1 ... .last - 1, with: dogFaces)
  ///      print(animals)
  ///      // Prints "🐕🐶🐶🐶🐩"
  ///
  /// If you pass a zero-length range as the `subrange` parameter, this method
  /// inserts the elements of `newElements` at `subrange.startIndex`. Calling
  /// the `insert(contentsOf:at:)` method instead is preferred.
  ///
  /// Likewise, if you pass a zero-length collection as the `newElements`
  /// parameter, this method removes the elements in the given subrange
  /// without replacement. Calling the `removeSubrange(_:)` method instead is
  /// preferred.
  ///
  /// Calling this method may invalidate any existing indices for use with this
  /// collection.
  ///
  /// - Parameters:
  ///   - subrange: The subrange of the collection to replace, specified as
  ///   offsets from the collection's bounds.
  ///   - newElements: The new elements to add to the collection.
  ///
  /// - Complexity: O(*n* + *m*), where *n* is length of this collection and
  ///   *m* is the length of `newElements`. If the call to this method simply
  ///   appends the contents of `newElements` to the collection, the complexity
  ///   is O(*m*).
  public mutating func replaceSubrange<C: Collection, R: RangeExpression>(
    _ subrange: R, with newElements: __owned C
  ) where C.Element == Element, R.Bound == OffsetBound {
    self.replaceSubrange(subrange._relative(to: self), with: newElements)
  }

  /// Inserts a new element into the collection at the specified position.
  ///
  /// The new element is inserted before the element currently at the specified
  /// offset. If you pass `.last + 1` as the `position` parameter, corresponding
  /// to the collection's `endIndex`, the new element is appended to the
  /// collection.
  ///
  ///     var numbers = "12345"
  ///     numbers.insert("Ⅸ", at: .first + 1)
  ///     numbers.insert("𐄕", at: .last + 1)
  ///
  ///     print(numbers)
  ///     // Prints "1Ⅸ2345𐄕"
  ///
  /// Calling this method may invalidate any existing indices for use with this
  /// collection.
  ///
  /// - Parameter newElement: The new element to insert into the collection.
  /// - Parameter `position`: The position at which to insert the new element,
  ///   specified as offsets from the collection's bounds
  ///
  /// - Complexity: O(*n*), where *n* is the length of the collection. If
  ///   `position == .last + 1`, this method is equivalent to `append(_:)`.
  public mutating func insert(
    _ newElement: __owned Element, at position: OffsetBound
  ) {
    self.insert(newElement, at: self._clampedIndex(at: position))
  }

  /// Inserts the elements of a sequence into the collection at the specified
  /// position.
  ///
  /// The new elements are inserted before the element currently at the
  /// specified offset. If you pass `.last + 1` as the `position` parameter,
  /// corresponding to the collection's `endIndex`, the new elements are
  /// appended to the collection.
  ///
  /// Here's an example of inserting vulgar fractions in a string of numbers.
  ///
  ///     var numbers = "12345"
  ///     numbers.insert(contentsOf: "↉⅖⅑", at: .first + 2)
  ///     print(numbers)
  ///     // Prints "12↉⅖⅑345"
  ///
  /// Calling this method may invalidate any existing indices for use with this
  /// collection.
  ///
  /// - Parameter newElements: The new elements to insert into the collection.
  /// - Parameter `position`: The position at which to insert the new elements,
  ///   specified as offsets from the collection's bounds
  ///
  /// - Complexity: O(*n* + *m*), where *n* is length of this collection and
  ///   *m* is the length of `newElements`. If `position == .last + 1`, this
  ///   method is equivalent to `append(contentsOf:)`.
  public mutating func insert<S: Collection>(
    contentsOf newElements: __owned S, at position: OffsetBound
  ) where S.Element == Element {
    self.insert(contentsOf: newElements, at: self._clampedIndex(at: position))
  }

  /// Removes and returns the element at the specified position, if it exists,
  /// else returns nil.
  ///
  /// All the elements following the specified position are moved to close the
  /// gap.
  ///
  /// Example:
  ///     var measurements = [1.2, 1.5, 2.9, 1.2, 1.6]
  ///     let removed = measurements.remove(at: .last - 2)
  ///     print(measurements)
  ///     // Prints "[1.2, 1.5, 1.2, 1.6]"
  ///     print(measurements.remove(at: .first + 4))
  ///     // Prints nil
  ///
  /// Calling this method may invalidate any existing indices for use with this
  /// collection.
  ///
  /// - Parameter position: The position of the element to remove, specified as
  ///   an offset from the collection's bounds.
  /// - Returns: The removed element if it exists, else nil
  ///
  /// - Complexity: O(*n*), where *n* is the length of the collection.
  mutating func remove(at position: OffsetBound) -> Element? {
    guard let idx = self.index(at: position), idx != endIndex else { return nil }
    return self.remove(at: idx)
  }

  /// Removes the elements in the specified subrange from the collection.
  ///
  /// All the elements following the specified position are moved to close the
  /// gap. This example removes two elements from the middle of a string of
  /// rulers.
  ///
  ///     var rulers = "📏🤴👑📐"
  ///     rulers.removeSubrange(.first + 1 ... .last - 1)
  ///     print(rulers)
  ///     // Prints "📏📐"
  ///
  /// Calling this method may invalidate any existing indices for use with this
  /// collection.
  ///
  /// - Parameter range: The range of the collection to be removed, specified
  ///   as offsets from the collection's bounds.
  ///
  /// - Complexity: O(*n*), where *n* is the length of the collection.
  public mutating func removeSubrange<R: RangeExpression>(
    _ range: R
  ) where R.Bound == OffsetBound {
    self.removeSubrange(range._relative(to: self))
  }

  /// Accesses the element corresponding to the provided offset. If no element
  /// exists, `nil` is returned from the getter. Similarly, setting an element
  /// to `nil` will remove the element at that offset.
  ///
  /// Example:
  ///
  ///       let abcs = "abcdefg"
  ///       print(abcs[.last]) // Optional("g")
  ///       print(abcs[.last - 2]) // Optional("e")
  ///       print(abcs[.first + 8]) // nil
  ///       abcs[.first + 2] = "©"
  ///       print(abcs) // "ab©defg"
  ///       abcs[.last - 1] = nil
  ///       print(abcs) // "ab©deg"
  ///
  /// - Complexity (get):
  ///   - O(1) if the collection conforms to `RandomAccessCollection`.
  ///   - O(*k*) where *k* is equal to the offset if the collection conforms to
  ///     `BidirectionalCollection`.
  ///   - O(*k*) if `position` is `.first + n` for any n, or `.last + 1`.
  ///   - Otherwise, O(*n*) where *n* is the length of the collection.
  ///
  /// - Complexity (set):
  ///   - O(*n*) where *n* is the length of the collection.
  public subscript(position: OffsetBound) -> Element? {
    get { return _subscriptGet(position) }
    set {
      guard let elt = newValue else {
        _ = self.remove(at: position)
        return
      }
      self.replaceSubrange(position ..< position + 1, with: CollectionOfOne(elt))
    }
  }

  /// Accesses the contiguous subrange of elements corresponding to the provided
  /// offsets.
  ///
  /// Example:
  ///
  ///       var abcs = "abcdefg"
  ///       print(abcs[.first + 1 ..< .first + 6]) // "bcdef"
  ///       print(abcs[.first + 1 ..< .last - 1]) // "bcde"
  ///       abcs[.first ... .first + 3] = "🔡"
  ///       print(abcs) // "🔡efg"
  ///
  /// - Complexity (get):
  ///   - O(1) if the collection conforms to `RandomAccessCollection`.
  ///   - O(*k*) where *k* is equal to the larger offset if the collection
  ///     conforms to `BidirectionalCollection`.
  ///   - O(*k*) if the offsets are `.first + n` for any n or `.last + 1`.
  ///   - Otherwise, O(*n*) where *n* is the length of the collection.
  ///
  /// - Complexity (set):
  ///   - O(*n*) where *n* is the length of the collection.
  public subscript<ORE: RangeExpression>(
    range: ORE
  ) -> SubSequence where ORE.Bound == OffsetBound {
    get { return _subscriptGet(range) }
    set { self.replaceSubrange(range, with: newValue) }
  }
}

///
/// Test Harness
///

var testsPassed = true
defer {
  if testsPassed {
    print("[OK] Tests Passed")
  } else {
    print("[FAIL] Tests Failed")
  }
}

func checkExpect(
  _ condition: @autoclosure () -> Bool,
  expected: @autoclosure () -> String, saw: @autoclosure () -> String,
  file: StaticString = #file, line: UInt = #line
) {
  if !condition() {
    print("""
      [FAIL] \(file):\(line)
        expected: \(expected())
        saw:      \(saw())
      """)
    testsPassed = false
  }
}
func expectEqual<C: Equatable>(
  _ lhs: C, _ rhs: C, file: StaticString = #file, line: UInt = #line
) {
  checkExpect(
    lhs == rhs, expected: "\(lhs)", saw: "\(rhs)", file: file, line: line)
}
func expectNotEqual<C: Equatable>(
  _ lhs: C, _ rhs: C, file: StaticString = #file, line: UInt = #line
) {
  checkExpect(
    lhs != rhs, expected: "not \(lhs)", saw: "\(rhs)", file: file, line: line)
}
func expectNil<T>(
  _ t: T?, file: StaticString = #file, line: UInt = #line
) {
  checkExpect(t == nil, expected: "nil", saw: "\(t!)", file: file, line: line)
}
func expectTrue(
  _ t: Bool, file: StaticString = #file, line: UInt = #line
) {
  checkExpect(t, expected: "true", saw: "\(t)", file: file, line: line)
}

func expectEqualSequence<S1: Sequence, S2: Sequence>(
  _ lhs: S1, _ rhs: S2, file: StaticString = #file, line: UInt = #line
) where S1.Element == S2.Element, S1.Element: Equatable {
  checkExpect(lhs.elementsEqual(rhs), expected: "\(lhs)", saw: "\(rhs)",
    file: file, line: line)
}

var allTests: [(name: String, run: () -> ())] = []
struct TestSuite {
  let name: String
  init(_ s: String) {
    self.name = s
  }

  func test(_ name: String, _ f: @escaping () -> ()) {
    allTests.append((name, f))
  }
}
func runAllTests() {
  for (test, run) in allTests {
    print("Running test \(test)")
    run()
  }
}
defer { runAllTests() }

///
/// Tests
///

var OffsetBoundTests = TestSuite("OffsetBoundTests")

OffsetBoundTests.test("Concrete Sanity Checks") {
  // Just some ad-hoc example sanity checks. More exhaustive things below
  var array = [1,2,3,4,5,6,7,8,9,10]
  let sliceStart = 5

  let slice = array[sliceStart...]

  expectEqual(slice.first, slice[.first])
  expectEqual(slice[sliceStart], slice[.first])
  expectEqual(slice.last, slice[.last])
  expectEqual(slice[9], slice[.last])

  // Example from "Proposed Solution"
  let str = "abcdefghijklmnopqrstuvwxyz"
  expectEqual("def", str[.first + 3 ..< .first + 6])
  expectEqual("defghijklmnopqrstuvw", str[.first + 3 ..< .last - 2])
  expectEqual("", str[.first + 3 ..< .last - 22])
  expectEqual("z", str[.last])
  expectNil(str[.first + 26])
  expectEqual("wxyz", str[(.last - 3)...])

  expectEqual("y", str[str.index(at: .last - 1)!])
  expectEqual("a", str[str.index(at: .last - 25)!])
  expectEqual(nil, str.index(at: .last - 27))

  expectEqual(str.first, str[.first])
  expectEqual(str.last, str[.last])

  // Range<Int> indices are the ints themselves
  expectEqual(5..<10, (3..<10)[5...])
  expectEqual(8..<10, (3..<10)[(.first + 5)...])

  // Example from `OffsetBound` documentation
  expectEqual("z", str[.last])
  expectEqual("x", str[.last - 2])
  expectNil(str[.first + 26])
  expectEqual("def", str[.first + 3 ..< .first + 6])
  expectEqual("defghijklmnopqrstuvw", str[.first + 3 ..< .last - 2])
  array = [1,2,3,4,5,6]
  expectEqual(4, array[2...][3])
  expectEqual(6, array[2...][.first + 3]!)

  // Example from subscript documentation
  var abcs = "abcdefg"
  expectEqual("g", abcs[.last])
  expectEqual("e", abcs[.last - 2])
  expectNil(abcs[.first + 8])
  abcs[.first + 2] = "©"
  expectEqual("ab©defg", abcs)
  abcs[.last - 1] = nil
  expectEqual("ab©deg", abcs)

  abcs = "abcdefg"
  expectEqual("bcdef", abcs[.first + 1 ..< .first + 6])
  expectEqual("bcde", abcs[.first + 1 ..< .last - 1])
  abcs[.first ... .first + 3] = "🔡"
  expectEqual("🔡efg", abcs)

  // Example from replaceSubrange documentation
  var animals = "🐕🐈🐱🐩"
  let dogFaces = repeatElement("🐶" as Character, count: 3)
  animals.replaceSubrange(.first + 1 ... .last - 1, with: dogFaces)
  expectEqual("🐕🐶🐶🐶🐩", animals)

  // Example from insert documentation
  var numbers = "12345"
  numbers.insert("Ⅸ", at: .first + 1)
  numbers.insert("𐄕", at: .last + 1)
  expectEqual("1Ⅸ2345𐄕", numbers)

  numbers = "12345"
  numbers.insert(contentsOf: "↉⅖⅑", at: .first + 2)
  expectEqual("12↉⅖⅑345", numbers)

  // Example from remove documentation
  var measurements = [1.2, 1.5, 2.9, 1.2, 1.6]
  let removed = measurements.remove(at: .last - 2)
  expectEqual(2.9, removed)
  expectEqual([1.2, 1.5, 1.2, 1.6], measurements)
  expectNil(measurements.remove(at: .first + 4))

  // Example from removeSubrange documentation
  var rulers = "📏🤴👑📐"
  rulers.removeSubrange(.first + 1 ... .last - 1)
  expectEqual("📏📐", rulers)

}

OffsetBoundTests.test("Quick Nil Out of Bounds") {
  let count = 5
  let numberArray = [1,2,3,4,5]
  let numberSet = [1,2,3,4,5] as Set<Int>
  expectEqual(numberArray.startIndex, numberArray.index(at: .last + 1 - count))
  expectEqual(numberArray.endIndex, numberArray.index(at: .first + count))
  expectEqual(numberSet.startIndex, numberSet.index(at: .last + 1 - count))
  expectEqual(numberSet.endIndex, numberSet.index(at: .first + count))

  expectNil(numberArray[.first - 1])
  expectNil(numberArray[.last + 2])
  expectNil(numberArray[.last + 1])
  expectNil(numberArray[.last - count])
  expectNil(numberArray[.first + (count)])

  expectNil(numberSet[.first - 1])
  expectNil(numberSet[.last + 2])
  expectNil(numberSet[.last + 1])
  expectNil(numberSet[.last - count])
  expectNil(numberSet[.first + count])
}

// More extensive programmatic tests

OffsetBoundTests.test("Comparison") {

  // Sanity check ordering
  for i in 0..<10 {
    expectTrue(.first + i < .last + 1 - i)
    expectTrue(.last - i > .first + i)

    for j in 0..<10 {
      if i == j {
        expectEqual(.first + i, .first + j)
        expectEqual(.last - i, .last - j)
      } else {
        expectNotEqual(.first + i, .first + j)
        expectNotEqual(.last - i, .last - j)

        if i < j {
          expectTrue(.first + i < .first + j)
          expectTrue(.last - i > .last - j)
        } else {
          expectTrue(.first + i > .first + j)
          expectTrue(.last - i < .last - j)
        }
      }
    }
  }
}

// Use subclassing to work around lack of universal qualifier
protocol TestHost {
  func checkCollection<C: Collection>(_: C) where C.Element: Equatable
}

// Apply a host's methods to various collection types
func runChecks(_ host: TestHost) {
  let numArray = [1,2,3,4,5]
  let string = "a🤓b🧟‍♀️cde\u{301}fg👻😃😎"
  let intMaxArray = [Int.max]
  let emptyOptArray = [] as Array<Optional<Bool>>
  let emptyString = ""
  let smallString = "abcdef"
  let scalars = "a🤓b🧟‍♀️cde\u{301}fg👻😃😎".unicodeScalars
  let set1 = [1.0, 2.25, 3.0, 3.5, 100.0] as Set<Double>
  let set2: Set<Double> = {
    var set2 = set1
    set2.insert(9.0)
    set2.reserveCapacity(set2.capacity * 16) // Force different salt
    return set2
  }()

  host.checkCollection(numArray)
  host.checkCollection(intMaxArray)
  host.checkCollection(emptyOptArray)
  host.checkCollection(emptyString)
  host.checkCollection(smallString)
  host.checkCollection(string)
  host.checkCollection(scalars)
  host.checkCollection(set1)
  host.checkCollection(set2)
}


OffsetBoundTests.test("Index and element fetch") {
  struct IndexHost: TestHost {
    func checkCollection<C: Collection>(
      _ c: C
    ) where C.Element: Equatable {
      let count = c.count

      expectEqualSequence(c.indices,
        (0..<count).map { c.index(at: .first + $0)! })
      expectEqualSequence(c,
        (0..<count).map { c[.first + $0]! })
      expectEqualSequence(c.indices.reversed(),
        (0..<count).map { c.index(at: .last - $0)! })
      expectEqualSequence(c.reversed(),
        (0..<count).map { c[.last - $0]! })

      expectEqual(c.startIndex, c.index(at: .last + 1 - count))
      expectEqual(c.startIndex, c.index(at: (.last - count) + 1))

      expectEqual(c.endIndex, c.index(at: .last + 1))
      expectEqual(c.endIndex, c.index(at: .first + count))
      expectEqual(c.startIndex, c.index(at: .first))

      expectEqual(c.first, c[.first])

      expectNil(c.index(at: .first + count + 1))
      expectNil(c.index(at: .last + 2))
      expectNil(c.index(at: .last + 2))
      expectNil(c[.first + count + 1])
      expectNil(c[.last + 2])

      expectNil(c.index(at: .first - 1))
      expectNil(c.index(at: .last - count))
      expectNil(c[.first - 1])
      expectNil(c[.last - count])
    }
  }

  runChecks(IndexHost())
}

extension Collection {
  var indexRange: Range<Index> { return startIndex..<endIndex }
}

OffsetBoundTests.test("Slicing") {
  struct SlicingHost: TestHost {
    func checkCollection<C: Collection>(
      _ c: C
    ) where C.Element: Equatable {
      let count = c.count
      for (i, idx) in c.indices.enumerated() {
        expectEqualSequence(c[idx...], c[(.first + i)...])
        expectEqual(c[idx..<idx].indexRange,
          c[.first + i ..< .last + 1 - count].indexRange)
        expectEqual(c[idx..<idx].indexRange,
          c[.first + i ..< .last - count - 1].indexRange)
      }
      for (i, idx) in c.indices.reversed().enumerated() {
        expectEqualSequence(c[idx...], c[(.last - i)...])
      }

      expectEqualSequence(c, c[.first ..< .last + 1])
      expectEqualSequence(
        c[c.endIndex..<c.endIndex], c[.first + count ..< .last + 1])
      expectEqualSequence(
        c[c.endIndex..<c.endIndex], c[.first + count + 2 ..< .last + 2])
      expectEqualSequence(c, c[.last + 1 - count ..< .last + 1])
      expectEqualSequence(c, c[.last - count - 1 ..< .last + 3])

      expectEqualSequence(c, c[.first - 1 ..< .last + 2])
    }
  }

  runChecks(SlicingHost())
}

OffsetBoundTests.test("Int indexing") {
  // Sanity checks that offset indexing does what we want
  func fifth<C: Collection>(_ c: C) -> C.Element? where C.Index == Int {
    return c.count >= 5 ? c[4] : nil
  }
  func fifthOffset<C: Collection>(_ c: C) -> C.Element? where C.Index == Int {
    return c[.first + 4]
  }

  func fifthThroughSixth<C: Collection>(
    _ c: C
  ) -> C.SubSequence where C.Index == Int {
    return c[4..<6]
  }
  func fifthThroughSixthOffset<C: Collection>(
    _ c: C
  ) -> C.SubSequence where C.Index == Int {
    return c[.first + 4 ..< .first + 6]
  }

  expectNil(fifth([1,2,3,4]))
  expectNil(fifthOffset([1,2,3,4]))

  let array = [1,2,3,4,5,6,7,8,9]
  expectEqual(5, fifth(array)!)
  expectEqual(5, fifth(array[2...])!)

  expectEqual(5, fifthOffset(array)!)
  expectEqual(7, fifthOffset(array[2...])!)

  expectEqualSequence([5, 6], fifthThroughSixth(array))
  expectEqualSequence([5, 6], fifthThroughSixth(array[2...]))

  expectEqualSequence([5, 6], fifthThroughSixthOffset(array))
  expectEqualSequence([7, 8], fifthThroughSixthOffset(array[2...]))
}

OffsetBoundTests.test("RangeReplaceableCollection") {
  var array = [0]

  func checkArray(_ expect: [Int], _ operation: @autoclosure () -> (),
    file: StaticString = #file, line: UInt = #line
  ) {
    operation()
    expectEqual(expect, array, file: file, line: line)
  }

  checkArray([1, 0], array.insert(1, at: .last))
  checkArray([1, 0, 2], array.insert(2, at: .first + 100))
  checkArray([3, 1, 0, 2], array.insert(3, at: .last - 100))

  checkArray([4, 4, 3, 1, 0, 2], array.insert(contentsOf: [4, 4], at: .last - 100))

  expectNil(array.remove(at: .first + 100))
  do {
    let elt = array.remove(at: .first + 2)
    expectEqual(elt, 3)
  }

  checkArray([4, 4, 1, 0, 2], ())

  // Empty range is no-op
  checkArray([4, 4, 1, 0, 2], array.removeSubrange(.first + 2 ..< .last - 2))

  checkArray([4, 0, 2], array.removeSubrange(.first + 1 ..< .last - 1))
  checkArray([4, 0], array.removeSubrange(.first + 2 ..< .first + 100))

  checkArray([4, 8], array[.last] = 8)
  checkArray([4, 8, 9], array[.last + 1] = 9)
  checkArray([4, 8], array[.last] = nil)
  checkArray([4, 8], array[.last + 2] = nil)
  checkArray([4, 8, 9], array[.last + 2] = 9)

  checkArray([0, 1, 2, 8, 9], array[...(.first)] = [0, 1, 2])
  checkArray([0, 1, 2, 8, 9, 0, 1, 2], array[.last + 2 ..< .last + 3] = [0, 1, 2])
  checkArray([0, 1, 4, 2], array.replaceSubrange(.first + 2 ... .last - 1, with: [4]))


}

#if canImport(Foundation)
import Foundation
OffsetBoundTests.test("Data indexing") {
  // Data indexing sanity checks
  func fifth(_ data: Data) -> UInt8? {
    return data.count >= 5 ? data[4] : nil
  }
  func fifthOffset(_ data: Data) -> UInt8? {
    return data[.first + 4]
  }

  func fifthThroughSixth(_ data: Data) -> Data {
    return data[4..<6]
  }
  func fifthThroughSixthOffset(_ data: Data) -> Data {
    return data[.first + 4 ..< .first + 6]
  }

  expectNil(fifth(Data([1,2,3,4])))
  expectNil(fifthOffset(Data([1,2,3,4])))

  var data = Data([1, 2, 3, 4, 5, 6, 7, 8, 9])
  expectEqual(5, fifth(data)!)
  expectEqual(5, fifthOffset(data)!)

  expectEqualSequence([5, 6], fifthThroughSixth(data))
  expectEqualSequence([5, 6], fifthThroughSixthOffset(data))

  data = data.dropFirst()
  expectEqual(5, fifth(data)!)
  expectEqual(6, fifthOffset(data)!)

  expectEqualSequence([5, 6], fifthThroughSixth(data))
  expectEqualSequence([6, 7], fifthThroughSixthOffset(data))
}
#endif //  canImport(Foundation)

///
/// Examples
///

func print<T>(_ t: T?) { print(t as Any) } // Squash optional warning

func printRangeExample() {
  print("Range examples: (3..<10)")
  print((3..<10)[(.first + 5)...]) // 8..<10
  print()
}

func printCollectionExample() {
  print("Collection examples: fifth")
  func fifth<C: Collection>(_ c: C) -> C.Element? { return c[.first + 4] }

  let array = [1,2,3,4,5,6,7,8,9]
  print(fifth(array)!) // 5
  print(fifth(array[2...])!) // 7

  var data = Data([1, 2, 3, 4, 5, 6, 7, 8, 9])
  print(fifth(data)!) // 5
  data = data.dropFirst(2)
  print(fifth(data)!) // 7

  struct EveryOther<C: RandomAccessCollection>: RandomAccessCollection {
    internal var storage: C

    var startIndex: C.Index { return storage.startIndex }
    var endIndex: C.Index {
      if storage.count % 2 == 0 { return storage.endIndex }
      return storage.index(before: storage.endIndex)
    }

    subscript(position: C.Index) -> C.Element { return storage[position] }

    func index(before i: C.Index) -> C.Index {
      return storage.index(i, offsetBy: -2)
    }
    func index(after i: C.Index) -> C.Index {
      return storage.index(i, offsetBy: 2)
    }
    // ... and override `distance`, `index(_:offsetBy:)` for performance ...
  }
  let everyOther = EveryOther(storage: [1,2,3,4,5,6,7,8])
  print(everyOther[.first + 1]) // Optional(3)
  print()
}

func printStringExample() {
  print("String examples: abcdefghijklmnopqrstuvwxyz")
  let str = "abcdefghijklmnopqrstuvwxyz"
  print(str[.first + 3 ..< .first + 6]) // "def"
  print(str[.first + 3 ..< .last - 2]) // "defghijklmnopqrstuvw"
  print(str[.first + 3 ..< .last - 22]) // "",
  print(str[.last]) // Optional("z")
  print(str[.last - 1]) // Optional("y")
  print(str[.first + 26]) // nil

  print(str.index(at: .last - 1)) // Optional(... index of "y")
  print(str.index(at: .last - 25)) // Optional(... startIndex)
  print(str.index(at: .last - 26)) // nil

  print()
}

printRangeExample()
printCollectionExample()
printStringExample()

do {
func parseRequirements(_ s: String) -> [(finish: Character, before: Character)] {
  return s.split(separator: "\n").map { line in
    let finishIdx = line.index(line.startIndex, offsetBy: 5)
    let beforeIdx = line.index(line.endIndex, offsetBy: -12)
    return (line[finishIdx], line[beforeIdx])
  }
}
print(parseRequirements(
  """
  Step C must be finished before step A can begin.
  Step C must be finished before step F can begin.
  Step A must be finished before step B can begin.
  Step A must be finished before step D can begin.
  Step B must be finished before step E can begin.
  Step D must be finished before step E can begin.
  Step F must be finished before step E can begin.
  """))
}

do {
func parseRequirements(_ s: String) -> [(finish: Character, before: Character)] {
  return s.split(separator: "\n").map { line in
    (line.dropFirst(5).first!, line.dropLast(11).last!)
  }
}
print(parseRequirements(
  """
  Step C must be finished before step A can begin.
  Step C must be finished before step F can begin.
  Step A must be finished before step B can begin.
  Step A must be finished before step D can begin.
  Step B must be finished before step E can begin.
  Step D must be finished before step E can begin.
  Step F must be finished before step E can begin.
  """))
}

do {
func parseRequirements(_ s: String) -> [(finish: Character, before: Character)] {
  return s.split(separator: "\n").map { line in
    let finishIdx = line.index(line.startIndex, offsetBy: 5)
    let beforeIdx = line.index(line.endIndex, offsetBy: -12)
    return (line[finishIdx], line[beforeIdx])
  }
}
print(parseRequirements(
  """
  Step C must be finished before step A can begin.
  Step C must be finished before step F can begin.
  Step A must be finished before step B can begin.
  Step A must be finished before step D can begin.
  Step B must be finished before step E can begin.
  Step D must be finished before step E can begin.
  Step F must be finished before step E can begin.
  """))
}

do {

func parseRequirements(_ s: String) -> [(finish: Character, before: Character)] {
  return s.split(separator: "\n").map { line in
    (line[.first + 5]!, line[.last - 11]!)
  }
}
print(parseRequirements(
  """
  Step C must be finished before step A can begin.
  Step C must be finished before step F can begin.
  Step A must be finished before step B can begin.
  Step A must be finished before step D can begin.
  Step B must be finished before step E can begin.
  Step D must be finished before step E can begin.
  Step F must be finished before step E can begin.
  """))
}

func parseRequirements<C: Collection>(
  _ c: C, lineSeparator: C.Element
) -> [(finish: C.Element, before: C.Element)] where C.Element: Comparable {
  return c.split(separator: lineSeparator).map { line in
    (line[.first + 5]!, line[.last - 11]!)
  }
}

print(parseRequirements(
  """
  Step C must be finished before step A can begin.
  Step C must be finished before step F can begin.
  Step A must be finished before step B can begin.
  Step A must be finished before step D can begin.
  Step B must be finished before step E can begin.
  Step D must be finished before step E can begin.
  Step F must be finished before step E can begin.
  """, lineSeparator: "\n"))