//===--- SequenceAlgorithms.swift.gyb -------------------------*- swift -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

%{

# We know we will eventually get a Sequence.Element type.  Define
# a shorthand that we can use today.
GElement = "Iterator.Element"

}%

//===----------------------------------------------------------------------===//
// enumerated()
//===----------------------------------------------------------------------===//

extension Sequence {
  /// Returns a lazy `Sequence` containing pairs (*n*, *x*), where
  /// *n*s are consecutive `Int`s starting at zero, and *x*s are
  /// the elements of `self`:
  ///
  ///     > for (n, c) in "Swift".characters.enumerated() {
  ///         print("\(n): '\(c)'")
  ///       }
  ///     0: 'S'
  ///     1: 'w'
  ///     2: 'i'
  ///     3: 'f'
  ///     4: 't'
  public func enumerated() -> EnumeratedSequence<Self> {
    return EnumeratedSequence(_base: self)
  }
}

//===----------------------------------------------------------------------===//
// min(), max()
//===----------------------------------------------------------------------===//

% # Generate two versions: with explicit predicates and with
% # a Comparable requirement.
% for preds in [ True, False ]:

%{
if preds:
  orderingRequirement = """
  /// - Precondition: `isOrderedBefore` is a
  ///   [strict weak ordering](http://en.wikipedia.org/wiki/Strict_weak_order#Strict_weak_orderings)
  ///   over `self`."""
  rethrows_ = "rethrows "
else:
  orderingRequirement = ""
  rethrows_ = ""
}%

extension Sequence ${"" if preds else "where Iterator.Element : Comparable"} {

  /// Returns the minimum element in `self` or `nil` if the sequence is empty.
  ///
  /// - Complexity: O(`elements.count`).
  ///
  /// ${orderingRequirement}
  @warn_unused_result
  public func min(
%   if preds:
    @noescape isOrderedBefore isOrderedBefore:
      (${GElement}, ${GElement}) throws -> Bool
%   end
  ) ${rethrows_}-> ${GElement}? {
    var it = makeIterator()
    guard var result = it.next() else { return nil }
    for e in IteratorSequence(it) {
%   if preds:
      if try isOrderedBefore(e, result) { result = e }
%   else:
      if e < result { result = e }
%   end
    }
    return result
  }

  /// Returns the maximum element in `self` or `nil` if the sequence is empty.
  ///
  /// - Complexity: O(`elements.count`).
  ///   ${orderingRequirement}
  @warn_unused_result
  public func max(
%   if preds:
    @noescape isOrderedBefore isOrderedBefore:
      (${GElement}, ${GElement}) throws -> Bool
%   end
  ) ${rethrows_}-> ${GElement}? {
    var it = makeIterator()
    guard var result = it.next() else { return nil }
    for e in IteratorSequence(it) {
%   if preds:
      if try isOrderedBefore(result, e) { result = e }
%   else:
      if e > result { result = e }
%   end
    }
    return result
  }
}

% end

//===----------------------------------------------------------------------===//
// starts(with:)
//===----------------------------------------------------------------------===//

% # Generate two versions: with explicit predicates and with
% # an Equatable requirement.
% for preds in [ True, False ]:

extension Sequence ${"" if preds else "where Iterator.Element : Equatable"} {

%{
if preds:
  comment = """
  /// Returns `true` iff `self` begins with elements equivalent to those of
  /// `other`, using `isEquivalent` as the equivalence test.  Returns `true` if
  /// `other` is empty.
  ///
  /// - Precondition: `isEquivalent` is an
  ///   [equivalence relation](http://en.wikipedia.org/wiki/Equivalence_relation)."""

  rethrows_ = "rethrows "
else:
  comment = """
  /// Returns `true` iff the initial elements of `self` are equal to `prefix`.
  /// Returns `true` if `other` is empty."""
  rethrows_ = ""
}%
  ${comment}
  @warn_unused_result
  public func starts<
    PossiblePrefix : Sequence where PossiblePrefix.${GElement} == ${GElement}
  >(
    with possiblePrefix: PossiblePrefix${"," if preds else ""}
%   if preds:
    @noescape isEquivalent: (${GElement}, ${GElement}) throws -> Bool
%   end
  ) ${rethrows_}-> Bool {
    var possiblePrefixIterator = possiblePrefix.makeIterator()
    for e0 in self {
      if let e1 = possiblePrefixIterator.next() {
        if ${"try !isEquivalent(e0, e1)" if preds else "e0 != e1"} {
          return false
        }
      }
      else {
        return true
      }
    }
    return possiblePrefixIterator.next() == nil
  }
}

% end

//===----------------------------------------------------------------------===//
// elementsEqual()
//===----------------------------------------------------------------------===//

% # Generate two versions: with explicit predicates and with
% # an Equatable requirement.
% for preds in [ True, False ]:

extension Sequence ${"" if preds else "where Iterator.Element : Equatable"} {

%{
if preds:
  comment = """
  /// Returns `true` iff `self` and `other` contain equivalent elements, using
  /// `isEquivalent` as the equivalence test.
  ///
  /// - Precondition: `isEquivalent` is an
  ///   [equivalence relation](http://en.wikipedia.org/wiki/Equivalence_relation)."""
  rethrows_ = "rethrows "
else:
  comment = """
  /// Returns `true` iff `self` and `other` contain the same elements in the
  /// same order."""
  rethrows_ = ""
}%

  ${comment}
  @warn_unused_result
  public func elementsEqual<
    OtherSequence : Sequence where OtherSequence.${GElement} == ${GElement}
  >(
    other: OtherSequence${"," if preds else ""}
%   if preds:
    @noescape isEquivalent: (${GElement}, ${GElement}) throws -> Bool
%   end
  ) ${rethrows_}-> Bool {
    var iter1 = self.makeIterator()
    var iter2 = other.makeIterator()
    while true {
      switch (iter1.next(), iter2.next()) {
      case let (e1?, e2?):
        if ${'try !isEquivalent(e1, e2)' if preds else 'e1 != e2'} {
          return false
        }
      case (_?, nil),
           (nil, _?):
        return false
      case (nil, nil):
        return true
      }
    }
  }
}

% end

//===----------------------------------------------------------------------===//
// lexicographicallyPrecedes()
//===----------------------------------------------------------------------===//

% # Generate two versions: with explicit predicates and with
% # Comparable requirement.
% for preds in [ True, False ]:

extension Sequence ${"" if preds else "where Iterator.Element : Comparable"} {

%{
if preds:
  comment = """
  /// Returns `true` iff `self` precedes `other` in a lexicographical 
  /// ("dictionary") ordering, using `isOrderedBefore` as the comparison 
  /// between elements.
  ///
  /// - Note: This method implements the mathematical notion of lexicographical
  ///   ordering, which has no connection to Unicode.  If you are sorting strings
  ///   to present to the end-user, you should use `String` APIs that perform
  /// localized comparison.
  ///
  /// - Precondition: `isOrderedBefore` is a
  ///   [strict weak ordering](http://en.wikipedia.org/wiki/Strict_weak_order#Strict_weak_orderings)
  ///   over the elements of `self` and `other`."""
  rethrows_ = "rethrows "
else:
  comment = """
  /// Returns `true` iff `self` precedes `other` in a lexicographical
  /// ("dictionary") ordering, using "<" as the comparison between elements.
  ///
  /// - Note: This method implements the mathematical notion of lexicographical
  ///   ordering, which has no connection to Unicode.  If you are sorting strings
  ///   to present to the end-user, you should use `String` APIs that perform
  /// localized comparison."""
  rethrows_ = ""
}%

  ${comment}
  @warn_unused_result
  public func lexicographicallyPrecedes<
    OtherSequence : Sequence where OtherSequence.${GElement} == ${GElement}
  >(
    other: OtherSequence${"," if preds else ""}
%   if preds:
    @noescape isOrderedBefore: (${GElement}, ${GElement}) throws -> Bool
%   end
  ) ${rethrows_}-> Bool {
    var iter1 = self.makeIterator()
    var iter2 = other.makeIterator()
    while true {
      if let e1 = iter1.next() {
        if let e2 = iter2.next() {
          if ${"try isOrderedBefore(e1, e2)" if preds else "e1 < e2"} {
            return true
          }
          if ${"try isOrderedBefore(e2, e1)" if preds else "e2 < e1"} {
            return false
          }
          continue // Equivalent
        }
        return false
      }

      return iter2.next() != nil
    }
  }
}

% end

//===----------------------------------------------------------------------===//
// contains()
//===----------------------------------------------------------------------===//

extension Sequence where Iterator.Element : Equatable {
  /// Returns `true` iff `element` is in `self`.
  @warn_unused_result
  public func contains(element: ${GElement}) -> Bool {
    if let result = _customContainsEquatableElement(element) {
      return result
    }

    for e in self {
      if e == element {
        return true
      }
    }
    return false
  }
}

extension Sequence {
  /// Returns `true` iff an element in `self` satisfies `predicate`.
  @warn_unused_result
  public func contains(
    @noescape predicate: (${GElement}) throws -> Bool
  ) rethrows -> Bool {
    for e in self {
      if try predicate(e) {
        return true
      }
    }
    return false
  }
}

//===----------------------------------------------------------------------===//
// reduce()
//===----------------------------------------------------------------------===//

extension Sequence {
  /// Returns the result of repeatedly calling `combine` with an
  /// accumulated value initialized to `initial` and each element of
  /// `self`, in turn, i.e. return
  /// `combine(combine(...combine(combine(initial, self[0]),
  /// self[1]),...self[count-2]), self[count-1])`.
  @warn_unused_result
  public func reduce<T>(
    initial: T, @noescape combine: (T, ${GElement}) throws -> T
  ) rethrows -> T {
    var result = initial
    for element in self {
      result = try combine(result, element)
    }
    return result
  }
}

//===----------------------------------------------------------------------===//
// reversed()
//===----------------------------------------------------------------------===//

extension Sequence {
  /// Returns an `Array` containing the elements of `self` in reverse
  /// order.
  ///
  /// Complexity: O(N), where N is the length of `self`.
  @warn_unused_result
  public func reversed() -> [${GElement}] {
    // FIXME(performance): optimize to 1 pass?  But Array(self) can be
    // optimized to a memcpy() sometimes.  Those cases are usually collections,
    // though.
    var result = Array(self)
    let count = result.count
    for i in 0..<count/2 {
      swap(&result[i], &result[count - i - 1])
    }
    return result
  }
}

//===----------------------------------------------------------------------===//
// flatMap()
//===----------------------------------------------------------------------===//

extension Sequence {
  /// Returns an `Array` containing the concatenated results of mapping
  /// `transform` over `self`.
  ///
  ///     s.flatMap(transform)
  ///
  /// is equivalent to
  ///
  ///     Array(s.map(transform).flatten())
  ///
  /// - Complexity: O(*M* + *N*), where *M* is the length of `self`
  ///   and *N* is the length of the result.
  @warn_unused_result
  public func flatMap<S : Sequence>(
    @noescape transform: (${GElement}) throws -> S
  ) rethrows -> [S.${GElement}] {
    var result: [S.${GElement}] = []
    for element in self {
      result.append(contentsOf: try transform(element))
    }
    return result
  }
}

extension Sequence {
  /// Returns an `Array` containing the non-nil results of mapping
  /// `transform` over `self`.
  ///
  /// - Complexity: O(*M* + *N*), where *M* is the length of `self`
  ///   and *N* is the length of the result.
  @warn_unused_result
  public func flatMap<T>(
    @noescape transform: (${GElement}) throws -> T?
  ) rethrows -> [T] {
    var result: [T] = []
    for element in self {
      if let newElement = try transform(element) {
        result.append(newElement)
      }
    }
    return result
  }
}

extension Sequence {
  @available(*, unavailable, renamed="enumerated")
  public func enumerate() -> EnumeratedSequence<Self> {
    fatalError("unavailable function can't be called")
  }

  @available(*, unavailable, renamed="min")
  public func minElement(
    @noescape isOrderedBefore: (Iterator.Element, Iterator.Element) throws -> Bool
  ) rethrows -> Iterator.Element? {
    fatalError("unavailable function can't be called")
  }

  @available(*, unavailable, renamed="max")
  public func maxElement(
    @noescape isOrderedBefore: (Iterator.Element, Iterator.Element) throws -> Bool
  ) rethrows -> Iterator.Element? {
    fatalError("unavailable function can't be called")
  }

  @available(*, unavailable, renamed="reversed")
  public func reverse() -> [Iterator.Element] {
    fatalError("unavailable function can't be called")
  }

  @available(*, unavailable, renamed="starts")
  public func startsWith<
    PossiblePrefix : Sequence where PossiblePrefix.Iterator.Element == Iterator.Element
  >(
    with possiblePrefix: PossiblePrefix,
    @noescape isEquivalent: (Iterator.Element, Iterator.Element) throws -> Bool
  ) rethrows-> Bool {
    fatalError("unavailable function can't be called")
  }

  @available(*, unavailable, renamed="lexicographicallyPrecedes")
  public func lexicographicalCompare<
    OtherSequence : Sequence where OtherSequence.${GElement} == ${GElement}
  >(
    other: OtherSequence,
    @noescape isOrderedBefore: (${GElement}, ${GElement}) throws -> Bool
  ) rethrows -> Bool {
    fatalError("unavailable function can't be called")
  }
}

extension Sequence where Iterator.Element : Comparable {
  @available(*, unavailable, renamed="min")
  public func minElement() -> Iterator.Element? {
    fatalError("unavailable function can't be called")
  }

  @available(*, unavailable, renamed="max")
  public func maxElement() -> Iterator.Element? {
    fatalError("unavailable function can't be called")
  }

  @available(*, unavailable, renamed="starts")
  public func startsWith<
    PossiblePrefix : Sequence where PossiblePrefix.${GElement} == ${GElement}
  >(
    with possiblePrefix: PossiblePrefix
  ) -> Bool {
    fatalError("unavailable function can't be called")
  }

  @available(*, unavailable, renamed="lexicographicallyPrecedes")
  public func lexicographicalCompare<
    OtherSequence : Sequence where OtherSequence.${GElement} == ${GElement}
  >(
    other: OtherSequence
  ) -> Bool {
    fatalError("unavailable function can't be called")
  }
}