// FIXME: Workaround until SignedNumber is updated.
/// This protocol is used only to compute offsets without accumulating error
/// while striding over floating point intervals.
public protocol _FloatingPointStrideable : FloatingPoint {
  func * (lhs: Self, rhs: Self) -> Self
}
extension Float : _FloatingPointStrideable { }
extension Double : _FloatingPointStrideable { }

/// An iterator for the result of `stride(to:...)` that advances without
/// accumulating error for floating point types.
///
/// - Note: The total number of steps required to stride over the interval
///   cannot exceed Int.max.
public struct FloatingPointStrideToIterator<
  Element : Strideable where Element.Stride : _FloatingPointStrideable
> : IteratorProtocol {
  internal var _step: Int = 0
  internal let _start: Element
  internal let _end: Element
  internal let _stride: Element.Stride

  /// Advance to the next element and return it, or `nil` if no next
  /// element exists.
  public mutating func next() -> Element? {
    let current = _start + Element.Stride(_step) * _stride
    if _stride > 0 ? current >= _end : current <= _end {
      return nil
    }
    _step += 1
    return current
  }

  internal init(_start: Element, end: Element, stride: Element.Stride) {
    // Attempting to compute the exact number of steps from start to end
    // by stride is inadvisable because that result may exceed the maximum
    // exactly representable integer; instead, determine if Int.max steps
    // would advance past the end
    let limit = _start + Element.Stride(Int.max) * stride
    _precondition(
      stride > 0 ? limit >= end : limit <= end,
      "can't construct FloatingPointStrideToIterator: total number of steps exceeds Int.max")
    self._start = _start
    self._end = end
    self._stride = stride
  }
}

/// A `Sequence` of values formed by striding over a floating point half-open
/// interval without accumulating error.
public struct FloatingPointStrideTo<
  Element : Strideable where Element.Stride : _FloatingPointStrideable
> : Sequence, CustomReflectable {
  // FIXME: should really be a CollectionType, as it is multipass

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

  internal init(_start: Element, end: Element, stride: Element.Stride) {
    // The endpoint is constrained by a step counter of type Int within
    // FloatingPointStrideToIterator, but it does not otherwise need to be
    // finite.
    _precondition(
      stride.isNormal,
      "stride size must be normal (not zero, subnormal, infinity, or NaN)")
    self._start = _start
    self._end = end
    self._stride = stride
  }

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

  public var customMirror: Mirror {
    return Mirror(self, children: ["from": _start, "to": _end, "by": _stride])
  }
}

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

/// An iterator for the result of `stride(through:...)` that advances without
/// accumulating error for floating point types.
///
/// - Note: The total number of steps required to stride over the interval
///   cannot exceed Int.max.
public struct FloatingPointStrideThroughIterator<
  Element : Strideable where Element.Stride : _FloatingPointStrideable
> : IteratorProtocol {
  internal var _step: Int = 0
  internal let _start: Element
  internal let _end: Element
  internal let _stride: Element.Stride
  internal var _done: Bool = false

  /// Advance to the next element and return it, or `nil` if no next
  /// element exists.
  public mutating func next() -> Element? {
    if _done {
      return nil
    }
    let current = _start + Element.Stride(_step) * _stride
    if _stride > 0 ? current >= _end : current <= _end {
      if current == _end {
        _done = true
        return current
      }
      return nil
    }
    _step += 1
    return current
  }

  internal init(_start: Element, end: Element, stride: Element.Stride) {
    let limit = _start + Element.Stride(Int.max) * stride
    _precondition(
      stride > 0 ? limit >= end : limit <= end,
      "can't construct FloatingPointStrideThroughIterator: total number of steps exceeds Int.max")
    self._start = _start
    self._end = end
    self._stride = stride
  }
}

/// A `Sequence` of values formed by striding over a floating point closed
/// interval without accumulating error.
public struct FloatingPointStrideThrough<
  Element : Strideable where Element.Stride : _FloatingPointStrideable
> : Sequence, CustomReflectable {
  // FIXME: should really be a CollectionType, as it is multipass

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

  internal init(_start: Element, end: Element, stride: Element.Stride) {
    _precondition(
      stride.isNormal,
      "stride size must be normal (not zero, subnormal, infinity, or NaN)")
    self._start = _start
    self._end = end
    self._stride = stride
  }

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

  public var customMirror: Mirror {
    return Mirror(self, children: ["from": _start, "to": _end, "by": _stride])
  }
}

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