//===--- Stride.swift.gyb - Components for stride(...) iteration ----------===//
//
// 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
//
//===----------------------------------------------------------------------===//

/// Conforming types are notionally continuous, one-dimensional
/// values that can be offset and measured.
///
/// - Important: The `Strideable` protocol provides default implementations for
///   the equal-to (`==`) and less-than (`<`) operators that depend on the
///   `Stride` type's implementations. If a type conforming to `Strideable`
///   is its own `Stride` type, it must provide concrete implementations of
///   the two operators to avoid infinite recursion.
public protocol Strideable : Comparable {
  /// A type that represents the distance between two values of `Self`.
  associatedtype Stride : SignedNumeric, Comparable

  /// Returns a stride `x` such that `self.advanced(by: x)` approximates
  /// `other`.
  ///
  /// If `Stride` conforms to `Integer`, then `self.advanced(by: x) == other`.
  ///
  /// - Complexity: O(1).
  func distance(to other: Self) -> Stride

  /// Returns a `Self` `x` such that `self.distance(to: x)` approximates `n`.
  ///
  /// If `Stride` conforms to `Integer`, then `self.distance(to: x) == n`.
  ///
  /// - Complexity: O(1).
  func advanced(by n: Stride) -> Self

  /// `_step` is an implementation detail of Strideable; do not use it directly.
  static func _step(
    after current: (index: Int?, value: Self),
    from start: Self, by distance: Self.Stride
  ) -> (index: Int?, value: Self)

  associatedtype _DisabledRangeIndex = _DisabledRangeIndex_
}

extension Strideable {
  @_inlineable
  public static func < (x: Self, y: Self) -> Bool {
    return x.distance(to: y) > 0
  }

  @_inlineable
  public static func == (x: Self, y: Self) -> Bool {
    return x.distance(to: y) == 0
  }
}

//===----------------------------------------------------------------------===//

%{
  # Strideable used to provide + and - unconditionally. With the updated
  # collection indexing model of Swift 3 this became unnecessary for integer
  # types, and was deprecated, as it was a way to write mixed-type arithmetic
  # expressions, that are otherwise are not allowed.
}%
% for Base, VersionInfo in [
%   ('Strideable where Self : _Pointer', None),
%   ('Strideable', 'deprecated: 3, obsoleted: 4'),
%   ]:
%   Availability = '@available(swift, %s, message: "Please use explicit type conversions or Strideable methods for mixed-type arithmetics.")' % (VersionInfo) if VersionInfo else ''

extension ${Base} {
  @_inlineable // FIXME(sil-serialize-all)
  @_transparent
  ${Availability}
  public static func + (lhs: Self, rhs: Self.Stride) -> Self {
    return lhs.advanced(by: rhs)
  }

  @_inlineable // FIXME(sil-serialize-all)
  @_transparent
  ${Availability}
  public static func + (lhs: Self.Stride, rhs: Self) -> Self {
    return rhs.advanced(by: lhs)
  }

  @_inlineable // FIXME(sil-serialize-all)
  @_transparent
  ${Availability}
  public static func - (lhs: Self, rhs: Self.Stride) -> Self {
    return lhs.advanced(by: -rhs)
  }

  @_inlineable // FIXME(sil-serialize-all)
  @_transparent
  ${Availability}
  public static func - (lhs: Self, rhs: Self) -> Self.Stride {
    return rhs.distance(to: lhs)
  }

  @_inlineable // FIXME(sil-serialize-all)
  @_transparent
  ${Availability}
  public static func += (lhs: inout Self, rhs: Self.Stride) {
    lhs = lhs.advanced(by: rhs)
  }

  @_inlineable // FIXME(sil-serialize-all)
  @_transparent
  ${Availability}
  public static func -= (lhs: inout Self, rhs: Self.Stride) {
    lhs = lhs.advanced(by: -rhs)
  }
}

% end

//===----------------------------------------------------------------------===//

extension Strideable {
  @_inlineable
  public static func _step(
    after current: (index: Int?, value: Self),
    from start: Self, by distance: Self.Stride
  ) -> (index: Int?, value: Self) {
    return (nil, current.value.advanced(by: distance))
  }
}

extension Strideable where Stride : FloatingPoint {
  @_inlineable
  public static func _step(
    after current: (index: Int?, value: Self),
    from start: Self, by distance: Self.Stride
  ) -> (index: Int?, value: Self) {
    if let i = current.index {
      return (i + 1, start.advanced(by: Stride(i + 1) * distance))
    }
    // If current.index == nil, either we're just starting out (in which case
    // the next index is 1), or we should proceed without an index just as
    // though this floating point specialization doesn't exist.
    return (current.value == start ? 1 : nil,
            current.value.advanced(by: distance))
  }
}

/// An iterator for `StrideTo<Element>`.
@_fixed_layout
public struct StrideToIterator<Element : Strideable> : IteratorProtocol {
  @_versioned
  internal let _start: Element

  @_versioned
  internal let _end: Element

  @_versioned
  internal let _stride: Element.Stride

  @_versioned
  internal var _current: (index: Int?, value: Element)

  @_inlineable
  @_versioned
  internal init(_start: Element, end: Element, stride: Element.Stride) {
    self._start = _start
    _end = end
    _stride = stride
    _current = (nil, _start)
  }

  /// Advances to the next element and returns it, or `nil` if no next element
  /// exists.
  ///
  /// Once `nil` has been returned, all subsequent calls return `nil`.

  @_inlineable
  public mutating func next() -> Element? {
    let result = _current.value
    if _stride > 0 ? result >= _end : result <= _end {
      return nil
    }
    _current = Element._step(after: _current, from: _start, by: _stride)
    return result
  }
}

/// A `Sequence` of values formed by striding over a half-open interval.
@_fixed_layout
public struct StrideTo<Element : Strideable> : Sequence, CustomReflectable {
  // FIXME: should really be a Collection, as it is multipass

  /// Returns an iterator over the elements of this sequence.
  ///
  /// - Complexity: O(1).
  @_inlineable
  public func makeIterator() -> StrideToIterator<Element> {
    return StrideToIterator(_start: _start, end: _end, stride: _stride)
  }

  @_inlineable
  public func _preprocessingPass<R>(
    _ preprocess: () throws -> R
  ) rethrows -> R? {
    return try preprocess()
  }

  @_inlineable
  public func _customContainsEquatableElement(
    _ element: Element
  ) -> Bool? {
    if element < _start || _end <= element {
      return false
    }
    return nil
  }

  @_inlineable
  @_versioned
  internal init(_start: Element, end: Element, stride: Element.Stride) {
    _precondition(stride != 0, "Stride size must not be zero")
    // At start, striding away from end is allowed; it just makes for an
    // already-empty Sequence.
    self._start = _start
    self._end = end
    self._stride = stride
  }

  @_versioned
  internal let _start: Element

  @_versioned
  internal let _end: Element

  @_versioned
  internal let _stride: Element.Stride

  @_inlineable // FIXME(sil-serialize-all)
  public var customMirror: Mirror {
    return Mirror(self, children: ["from": _start, "to": _end, "by": _stride])
  }

  // FIXME(conditional-conformances): this is O(N) instead of O(1), leaving it
  // here until a proper Collection conformance is possible
  @_inlineable
  public var underestimatedCount: Int {
    var it = self.makeIterator()
    var count = 0
    while it.next() != nil {
      count += 1
    }
    return count
  }
}

// FIXME(conditional-conformances): these extra types can easily be turned into
// conditional extensions to StrideTo type
% for Self, ElementConstraint, Where in [
%   ('IntegerStrideToCollection', 'BinaryInteger', 'Element.Stride : BinaryInteger'),
%   ('FloatingPointStrideToCollection', 'BinaryFloatingPoint', 'Element.Stride == Element'),
% ]:
%   ElementIsInteger = ElementConstraint == 'BinaryInteger'

internal struct ${Self}<
  Element : ${ElementConstraint}
> : RandomAccessCollection, CustomReflectable
where ${Where} {

//===----------------------------------------------------------------------===//
// This block is copied from StrideTo struct definition                       //
//===----------------------------------------------------------------------===//
  @_inlineable
  public func makeIterator() -> StrideToIterator<Element> {
    return StrideToIterator(_start: _start, end: _end, stride: _stride)
  }

  @_inlineable
  public func _customContainsEquatableElement(
    _ element: Element
  ) -> Bool? {
    if element < _start || _end <= element {
      return false
    }
    return nil
  }

  @_inlineable
  @_versioned
  internal init(_start: Element, end: Element, stride: Element.Stride) {
    _precondition(stride != 0, "Stride size must not be zero")
    // At start, striding away from end is allowed; it just makes for an
    // already-empty Sequence.
    self._start = _start
    self._end = end
    self._stride = stride
  }

  @_versioned
  internal let _start: Element

  @_versioned
  internal let _end: Element

  @_versioned
  internal let _stride: Element.Stride

  @_inlineable // FIXME(sil-serialize-all)
  public var customMirror: Mirror {
    return Mirror(self, children: ["from": _start, "to": _end, "by": _stride])
  }
//===----------------------------------------------------------------------===//
// The end of the copied block
//===----------------------------------------------------------------------===//

  // RandomAccessCollection conformance
  public typealias Index = Int
  public typealias SubSequence = RandomAccessSlice<${Self}>
  public typealias Indices = CountableRange<Int>

  public var startIndex: Index { return 0 }
  public var endIndex: Index { return count }

  public var count: Int {
    let (start, end, stride) =
      (_stride > 0) ? (_start, _end, _stride) : (_end, _start, -_stride)
%   if ElementIsInteger:
    return Int((start.distance(to: end) - 1) / stride) + 1
%   else:
    let nonExactCount = (start.distance(to: end)) / stride
    return Int(nonExactCount.rounded(.toNearestOrAwayFromZero))
%   end
  }

  public subscript(position: Index) -> Element {
    _failEarlyRangeCheck(position, bounds: startIndex ..< endIndex)
    return _indexToElement(position)
  }

  public subscript(bounds: Range<Index>) -> RandomAccessSlice<${Self}> {
    _failEarlyRangeCheck(bounds, bounds: startIndex ..< endIndex)
    return RandomAccessSlice(base: self, bounds: bounds)
  }

  public func index(after i: Index) -> Index {
    _failEarlyRangeCheck(i, bounds: startIndex-1 ..< endIndex)
    return i+1
  }

  public func index(before i: Index) -> Index {
    _failEarlyRangeCheck(i, bounds: startIndex+1 ... endIndex)
    return i-1
  }

  @inline(__always)
  internal func _indexToElement(_ i: Index) -> Element {
    return _start.advanced(by: Element.Stride(i) * _stride)
  }
}

% end

/// Returns the sequence of values (`self`, `self + stride`, `self +
/// 2 * stride`, ... *last*) where *last* is the last value in the
/// progression that is less than `end`.
@_inlineable
public func stride<T>(
  from start: T, to end: T, by stride: T.Stride
) -> StrideTo<T> {
  return StrideTo(_start: start, end: end, stride: stride)
}

/// An iterator for `StrideThrough<Element>`.
@_fixed_layout
public struct StrideThroughIterator<Element : Strideable> : IteratorProtocol {
  @_versioned
  internal let _start: Element

  @_versioned
  internal let _end: Element

  @_versioned
  internal let _stride: Element.Stride

  @_versioned
  internal var _current: (index: Int?, value: Element)

  @_versioned
  internal var _didReturnEnd: Bool = false

  @_inlineable
  @_versioned
  internal init(_start: Element, end: Element, stride: Element.Stride) {
    self._start = _start
    _end = end
    _stride = stride
    _current = (nil, _start)
  }

  /// Advances to the next element and returns it, or `nil` if no next element
  /// exists.
  ///
  /// Once `nil` has been returned, all subsequent calls return `nil`.
  @_inlineable
  public mutating func next() -> Element? {
    let result = _current.value
    if _stride > 0 ? result >= _end : result <= _end {
      // This check is needed because if we just changed the above operators
      // to > and <, respectively, we might advance current past the end
      // and throw it out of bounds (e.g. above Int.max) unnecessarily.
      if result == _end && !_didReturnEnd {
        _didReturnEnd = true
        return result
      }
      return nil
    }
    _current = Element._step(after: _current, from: _start, by: _stride)
    return result
  }
}

/// A `Sequence` of values formed by striding over a closed interval.
@_fixed_layout
public struct StrideThrough<
  Element : Strideable
> : Sequence, CustomReflectable {
  // FIXME: should really be a CollectionType, as it is multipass

  /// Returns an iterator over the elements of this sequence.
  ///
  /// - Complexity: O(1).
  @_inlineable
  public func makeIterator() -> StrideThroughIterator<Element> {
    return StrideThroughIterator(_start: _start, end: _end, stride: _stride)
  }

  @_inlineable
  public func _preprocessingPass<R>(
    _ preprocess: () throws -> R
  ) rethrows -> R? {
    return try preprocess()
  }

  @_inlineable
  public func _customContainsEquatableElement(
    _ element: Element
  ) -> Bool? {
    if element < _start || _end < element {
      return false
    }
    return nil
  }

  @_inlineable
  @_versioned
  internal init(_start: Element, end: Element, stride: Element.Stride) {
    _precondition(stride != 0, "Stride size must not be zero")
    self._start = _start
    self._end = end
    self._stride = stride
  }

  @_versioned
  internal let _start: Element
  @_versioned
  internal let _end: Element
  @_versioned
  internal let _stride: Element.Stride

  @_inlineable // FIXME(sil-serialize-all)
  public var customMirror: Mirror {
    return Mirror(self,
      children: ["from": _start, "through": _end, "by": _stride])
  }

  // FIXME(conditional-conformances): this is O(N) instead of O(1), leaving it
  // here until a proper Collection conformance is possible
  @_inlineable
  public var underestimatedCount: Int {
    var it = self.makeIterator()
    var count = 0
    while it.next() != nil {
      count += 1
    }
    return count
  }
}

// FIXME(conditional-conformances): these extra types can easily be turned into
// conditional extensions to StrideThrough type
% for Self, ElementConstraint, Where in [
%   ('IntegerStrideThroughCollection', 'BinaryInteger', 'Element.Stride : BinaryInteger'),
%   ('FloatingPointStrideThroughCollection', 'BinaryFloatingPoint', 'Element.Stride == Element'),
% ]:
%   ElementIsInteger = ElementConstraint == 'BinaryInteger'

internal struct ${Self}<
  Element : ${ElementConstraint}
> : RandomAccessCollection, CustomReflectable
where ${Where} {

//===----------------------------------------------------------------------===//
// This block is copied from StrideThrough struct definition                  //
//===----------------------------------------------------------------------===//
  /// Returns an iterator over the elements of this sequence.
  ///
  /// - Complexity: O(1).
  @_inlineable
  public func makeIterator() -> StrideThroughIterator<Element> {
    return StrideThroughIterator(_start: _start, end: _end, stride: _stride)
  }

  @_inlineable
  public func _customContainsEquatableElement(
    _ element: Element
  ) -> Bool? {
    if element < _start || _end < element {
      return false
    }
    return nil
  }

  @_inlineable
  @_versioned
  internal init(_start: Element, end: Element, stride: Element.Stride) {
    _precondition(stride != 0, "Stride size must not be zero")
    self._start = _start
    self._end = end
    self._stride = stride
  }

  @_versioned
  internal let _start: Element
  @_versioned
  internal let _end: Element
  @_versioned
  internal let _stride: Element.Stride

  @_inlineable // FIXME(sil-serialize-all)
  public var customMirror: Mirror {
    return Mirror(self,
      children: ["from": _start, "through": _end, "by": _stride])
  }
//===----------------------------------------------------------------------===//
// The end of the copied block
//===----------------------------------------------------------------------===//

  // RandomAccessCollection conformance
  public typealias Index = ClosedRangeIndex<Int>
  public typealias IndexDistance = Int
  public typealias SubSequence = RandomAccessSlice<${Self}>

  @_inlineable
  public var startIndex: Index { return ClosedRangeIndex(0) }
  @_inlineable
  public var endIndex: Index { return ClosedRangeIndex() }

  @_inlineable
  public var count: Int {
    let (start, end, stride) =
      (_stride > 0) ? (_start, _end, _stride) : (_end, _start, -_stride)
%   if ElementIsInteger:
    return Int(start.distance(to: end) / stride) + 1
%   else:
    let nonExactCount = start.distance(to: end) / stride
    return Int(nonExactCount.rounded(.toNearestOrAwayFromZero)) + 1
%   end
  }

  public subscript(position: Index) -> Element {
    let offset = Element.Stride(position._dereferenced) * _stride
    return _start.advanced(by: offset)
  }

  public subscript(bounds: Range<Index>) -> RandomAccessSlice<${Self}> {
    return RandomAccessSlice(base: self, bounds: bounds)
  }

  @_inlineable
  public func index(before i: Index) -> Index {
    switch i._value {
    case .inRange(let n):
      _precondition(n > 0, "Incrementing past start index")
      return ClosedRangeIndex(n - 1)
    case .pastEnd:
      _precondition(_end >= _start, "Incrementing past start index")
      return ClosedRangeIndex(count - 1)
    }
  }

  @_inlineable
  public func index(after i: Index) -> Index {
    switch i._value {
    case .inRange(let n):
      return n == (count - 1)
        ? ClosedRangeIndex()
        : ClosedRangeIndex(n + 1)
    case .pastEnd:
      _preconditionFailure("Incrementing past end index")
    }
  }
}

% end

/// Returns the sequence of values (`self`, `self + stride`, `self +
/// 2 * stride`, ... *last*) where *last* is the last value in the
/// progression less than or equal to `end`.
///
/// - Note: There is no guarantee that `end` is an element of the sequence.
@_inlineable
public func stride<T>(
  from start: T, through end: T, by stride: T.Stride
) -> StrideThrough<T> {
  return StrideThrough(_start: start, end: end, stride: stride)
}