//===--- MinimalCollections.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
//
//===----------------------------------------------------------------------===//

%{
  TRACE = '''@autoclosure _ message: () -> String = "",
    showFrame: Bool = true,
    stackTrace: SourceLocStack = SourceLocStack(),
    file: String = #file, line: UInt = #line'''

  stackTrace = 'stackTrace.pushIf(showFrame, file: file, line: line)'
}%

import StdlibUnittest

/// State that is created every time a fresh generator is created with
/// `MinimalSequence.makeIterator()`.
internal class _MinimalIteratorPrivateState<T> {
  internal init() {}

  internal var returnedNilCounter: Int = 0
}

/// State shared by all generators of a MinimalSequence.
internal class _MinimalIteratorSharedState<T> {
  internal init(_ data: [T]) {
    self.data = data
  }

  internal let data: [T]
  internal var i: Int = 0
  internal var underestimatedCount: Int = 0
}

//===----------------------------------------------------------------------===//
// MinimalIterator
//===----------------------------------------------------------------------===//

/// An IteratorProtocol that implements the protocol contract in the most
/// narrow way possible.
///
/// This generator will return `nil` only once.
public struct MinimalIterator<T> : IteratorProtocol {
  public init<S : Sequence where S.Iterator.Element == T>(_ s: S) {
    self._sharedState = _MinimalIteratorSharedState(Array(s))
  }

  public init(_ data: [T]) {
    self._sharedState = _MinimalIteratorSharedState(data)
  }

  internal init(_ _sharedState: _MinimalIteratorSharedState<T>) {
    self._sharedState = _sharedState
  }

  public func next() -> T? {
    if _sharedState.i == _sharedState.data.count {
      if isConsumed {
        expectUnreachable("next() was called on a consumed generator")
      }
      _privateState.returnedNilCounter += 1
      return nil
    }
    defer { _sharedState.i += 1 }
    return _sharedState.data[_sharedState.i]
  }

  public var isConsumed: Bool {
    return returnedNilCounter >= 1
  }

  public var returnedNilCounter: Int {
    return _privateState.returnedNilCounter
  }

  internal let _privateState: _MinimalIteratorPrivateState<T> =
    _MinimalIteratorPrivateState()
  internal let _sharedState: _MinimalIteratorSharedState<T>
}

// A protocol to identify MinimalIterator.
public protocol _MinimalIterator {}
extension MinimalIterator : _MinimalIterator {}

//===----------------------------------------------------------------------===//
// MinimalSequence
//===----------------------------------------------------------------------===//

public enum UnderestimatedCountBehavior {
  /// Return the actual number of elements.
  case precise

  /// Return the actual number of elements divided by 2.
  case half

  /// Return an overestimated count.  Useful to test how algorithms reserve
  /// memory.
  case overestimate

  /// Return the provided value.
  case value(Int)
}

public protocol StrictSequence : Sequence {
  associatedtype Element
  init(base: MinimalSequence<Element>)
  var base: MinimalSequence<Element> { get }
}

extension StrictSequence {
  public init<S : Sequence where S.Iterator.Element == Element>(
    elements: S,
    underestimatedCount: UnderestimatedCountBehavior = .value(0)
  ) {
    self.init(base: MinimalSequence(
      elements: elements, underestimatedCount: underestimatedCount))
  }

  public var underestimatedCount: Int {
    return base.underestimatedCount
  }
}

extension StrictSequence where Iterator : _MinimalIterator {
  public func makeIterator() -> MinimalIterator<Element> {
    return base.makeIterator()
  }
}

/// A Sequence that implements the protocol contract in the most
/// narrow way possible.
///
/// This sequence is consumed when its generator is advanced.
public struct MinimalSequence<T> : Sequence, CustomDebugStringConvertible {
  public init<S : Sequence where S.Iterator.Element == T>(
    elements: S,
    underestimatedCount: UnderestimatedCountBehavior = .value(0)
  ) {
    let data = Array(elements)
    self._sharedState = _MinimalIteratorSharedState(data)

    switch underestimatedCount {
    case .precise:
      self._sharedState.underestimatedCount = data.count

    case .half:
      self._sharedState.underestimatedCount = data.count / 2

    case .overestimate:
      self._sharedState.underestimatedCount = data.count * 3 + 5

    case .value(let count):
      self._sharedState.underestimatedCount = count
    }
  }

  public func makeIterator() -> MinimalIterator<T> {
    return MinimalIterator(_sharedState)
  }

  public var underestimatedCount: Int {
    return Swift.max(0, self._sharedState.underestimatedCount - self._sharedState.i)
  }

  public var debugDescription: String {
    return "MinimalSequence(\(_sharedState.data[_sharedState.i..<_sharedState.data.count]))"
  }

  internal let _sharedState: _MinimalIteratorSharedState<T>
}

//===----------------------------------------------------------------------===//
// Index invalidation checking
//===----------------------------------------------------------------------===//

internal enum _CollectionOperation : Equatable {
  case reserveCapacity(capacity: Int)
  case append
  case appendContentsOf(count: Int)
  case replaceRange(subRange: Range<Int>, replacementCount: Int)
  case insert(atIndex: Int)
  case insertContentsOf(atIndex: Int, count: Int)
  case removeAtIndex(index: Int)
  case removeLast
  case removeRange(subRange: Range<Int>)
  case removeAll(keepCapacity: Bool)

  internal func _applyTo(
    elementsLastMutatedStateIds: [Int], nextStateId: Int) -> [Int] {
    var result = elementsLastMutatedStateIds
    switch self {
    case reserveCapacity:
      let invalidIndices = result.indices
      result.replaceSubrange(
        invalidIndices,
        with: repeatElement(nextStateId, count: invalidIndices.count))

    case append:
      result.append(nextStateId)

    case appendContentsOf(let count):
      result.append(contentsOf:
        repeatElement(nextStateId, count: count))

    case replaceRange(let subRange, let replacementCount):
      result.replaceSubrange(
        subRange,
        with: repeatElement(nextStateId, count: replacementCount))

      let invalidIndices = subRange.startIndex..<result.endIndex
      result.replaceSubrange(
        invalidIndices,
        with: repeatElement(nextStateId, count: invalidIndices.count))

    case insert(let atIndex):
      result.insert(nextStateId, at: atIndex)

      let invalidIndices = atIndex..<result.endIndex
      result.replaceSubrange(
        invalidIndices,
        with: repeatElement(nextStateId, count: invalidIndices.count))

    case insertContentsOf(let atIndex, let count):
      result.insert(
        contentsOf: repeatElement(nextStateId, count: count),
        at: atIndex)

      let invalidIndices = atIndex..<result.endIndex
      result.replaceSubrange(
        invalidIndices,
        with: repeatElement(nextStateId, count: invalidIndices.count))

    case removeAtIndex(let index):
      result.remove(at: index)

      let invalidIndices = index..<result.endIndex
      result.replaceSubrange(
        invalidIndices,
        with: repeatElement(nextStateId, count: invalidIndices.count))

    case removeLast:
      result.removeLast()

    case removeRange(let subRange):
      result.removeSubrange(subRange)

      let invalidIndices = subRange.startIndex..<result.endIndex
      result.replaceSubrange(
        invalidIndices,
        with: repeatElement(nextStateId, count: invalidIndices.count))

    case removeAll(let keepCapacity):
      result.removeAll(keepingCapacity: keepCapacity)
    }
    return result
  }
}

internal func == (
  lhs: _CollectionOperation,
  rhs: _CollectionOperation
) -> Bool {
  switch (lhs, rhs) {
  case (.reserveCapacity(let lhsCapacity), .reserveCapacity(let rhsCapacity)):
    return lhsCapacity == rhsCapacity

  case (.append, .append):
    return true

  case (.appendContentsOf(let lhsCount), .appendContentsOf(let rhsCount)):
    return lhsCount == rhsCount

  case (
    .replaceRange(let lhsSubRange, let lhsReplacementCount),
    .replaceRange(let rhsSubRange, let rhsReplacementCount)):

    return lhsSubRange == rhsSubRange &&
      lhsReplacementCount == rhsReplacementCount

  case (.insert(let lhsAtIndex), .insert(let rhsAtIndex)):
    return lhsAtIndex == rhsAtIndex

  case (
    .insertContentsOf(let lhsAtIndex, let lhsCount),
    .insertContentsOf(let rhsAtIndex, let rhsCount)):

    return lhsAtIndex == rhsAtIndex && lhsCount == rhsCount

  case (.removeAtIndex(let lhsIndex), .removeAtIndex(let rhsIndex)):
    return lhsIndex == rhsIndex

  case (.removeLast, .removeLast):
    return true

  case (.removeRange(let lhsSubRange), .removeRange(let rhsSubRange)):
    return lhsSubRange == rhsSubRange

  case (.removeAll(let lhsKeepCapacity), .removeAll(let rhsKeepCapacity)):
    return lhsKeepCapacity == rhsKeepCapacity

  default:
    return false
  }
}

public struct _CollectionState : Equatable, Hashable {
  internal static var _nextUnusedState: Int = 0
  internal static var _namedStates: [String : _CollectionState] = [:]

  internal let _id: Int
  internal let _elementsLastMutatedStateIds: [Int]

  internal init(id: Int, elementsLastMutatedStateIds: [Int]) {
    self._id = id
    self._elementsLastMutatedStateIds = elementsLastMutatedStateIds
  }

  internal init(newRootStateForElementCount count: Int) {
    self._id = _CollectionState._nextUnusedState
    _CollectionState._nextUnusedState += 1
    self._elementsLastMutatedStateIds =
      Array(repeatElement(self._id, count: count))
  }

  internal init(name: String, elementCount: Int) {
    if let result = _CollectionState._namedStates[name] {
      self = result
    } else {
      self = _CollectionState(newRootStateForElementCount: elementCount)
      _CollectionState._namedStates[name] = self
    }
  }

  public var hashValue: Int {
    return _id.hashValue
  }
}

public func == (lhs: _CollectionState, rhs: _CollectionState) -> Bool {
  return lhs._id == rhs._id
}

internal struct _CollectionStateTransition {
  internal let _previousState: _CollectionState
  internal let _operation: _CollectionOperation
  internal let _nextState: _CollectionState

  internal static var _allTransitions:
    [_CollectionState : Box<[_CollectionStateTransition]>] = [:]

  internal init(
    previousState: _CollectionState,
    operation: _CollectionOperation,
    nextState: _CollectionState
  ) {
    var transitions =
      _CollectionStateTransition._allTransitions[previousState]
    if transitions == nil {
      transitions = Box<[_CollectionStateTransition]>([])
      _CollectionStateTransition._allTransitions[previousState] = transitions
    }
    if let i = transitions!.value.index(where: { $0._operation == operation }) {
      self = transitions!.value[i]
      return
    }
    self._previousState = previousState
    self._operation = operation
    self._nextState = nextState
    transitions!.value.append(self)
  }

  internal init(
    previousState: _CollectionState,
    operation: _CollectionOperation
  ) {
    let nextStateId = _CollectionState._nextUnusedState
    _CollectionState._nextUnusedState += 1
    let newElementStates = operation._applyTo(
      previousState._elementsLastMutatedStateIds, nextStateId: nextStateId)
    let nextState = _CollectionState(
      id: nextStateId, elementsLastMutatedStateIds: newElementStates)
    self = _CollectionStateTransition(
      previousState: previousState,
      operation: operation,
      nextState: nextState)
  }
}

//===----------------------------------------------------------------------===//
// MinimalForwardIndex
//===----------------------------------------------------------------------===//

/// Asserts that the two indices are allowed to participate in a binary
/// operation.
internal func _expectCompatibleIndices<Index : _MinimalIndex>(
  first: Index,
  _ second: Index,
  ${TRACE}
) {
  if let firstStateId = first._collectionState?._id,
    let secondStateId = second._collectionState?._id
    where firstStateId == secondStateId {

    // The indices are derived from the same state.
    return
  }

  // The indices are derived from different states.  Check that they point
  // to elements that persisted from the same state.

  func getLastMutatedStateId(i: Index) -> Int? {
    guard let state = i._collectionState else { return nil }
    let offset = i._offset
    if offset == state._elementsLastMutatedStateIds.endIndex {
      return state._id
    }
    return state._elementsLastMutatedStateIds[offset]
  }

  let firstElementLastMutatedStateId = getLastMutatedStateId(first)
  let secondElementLastMutatedStateId = getLastMutatedStateId(second)

  expectEqual(
    firstElementLastMutatedStateId,
    secondElementLastMutatedStateId,
    "Indices are not compatible:\n" +
    "first: \(first)\n" +
    "second: \(second)\n" +
    "first element last mutated in state id: \(firstElementLastMutatedStateId)\n" +
    "second element last mutated in state id: \(secondElementLastMutatedStateId)\n",
    stackTrace: ${stackTrace})

  // To make writing assertions easier, perform a trap.
  if firstElementLastMutatedStateId != secondElementLastMutatedStateId {
    fatalError("Indices are not compatible")
  }
}

public protocol _MinimalIndex {
  /// Distance from start index.
  var _offset: Int { get }

  var _collectionState: _CollectionState? { get }
}

% for Distance in [ '', 'Int32' ]:
%   Index = 'MinimalForward%sIndex' % Distance

public struct ${Index} : ForwardIndex {
% if Distance != '':
  public typealias Distance = ${Distance}
% else:
  public typealias Distance = Int
% end

  public init(position: Int, startIndex: Int, endIndex: Int) {
    self = ${Index}(
      collectionState: nil,
      position: position,
      startIndex: startIndex,
      endIndex: endIndex)
  }

  internal init(
    collectionState: _CollectionState?,
    position: Int,
    startIndex: Int,
    endIndex: Int
  ) {
    expectLE(startIndex, position)
    expectGE(endIndex, position)
    self._collectionState = collectionState
    self.position = position
    self.startIndex = startIndex
    self.endIndex = endIndex
  }

  public func successor() -> ${Index} {
    expectNotEqual(endIndex, position)
    return ${Index}(
      collectionState: _collectionState,
      position: position + 1, startIndex: startIndex, endIndex: endIndex)
  }

  public static func _failEarlyRangeCheck(
    index: ${Index}, bounds: Range<${Index}>
  ) {
    expectLE(bounds.startIndex.position, index.position)
    expectGT(bounds.endIndex.position, index.position)

    if ${Index}.trapOnRangeCheckFailure.value {
      Int._failEarlyRangeCheck(
        index.position,
        bounds: bounds.startIndex.position..<bounds.endIndex.position)
    }
  }

  public static func _failEarlyRangeCheck2(
    rangeStart rangeStart: ${Index}, rangeEnd: ${Index},
    boundsStart: ${Index}, boundsEnd: ${Index}
  ) {
    let range = rangeStart..<rangeEnd
    let bounds = boundsStart..<boundsEnd
    expectLE(bounds.startIndex.position, range.startIndex.position)
    expectGE(bounds.endIndex.position, range.startIndex.position)
    expectLE(bounds.startIndex.position, range.endIndex.position)
    expectGE(bounds.endIndex.position, range.endIndex.position)

    if ${Index}.trapOnRangeCheckFailure.value {
      Int._failEarlyRangeCheck2(
        rangeStart: rangeStart.position,
        rangeEnd: rangeEnd.position,
        boundsStart: boundsStart.position,
        boundsEnd: boundsEnd.position)
    }
  }

  public let _collectionState: _CollectionState?

  public let position: Int
  public let startIndex: Int
  public let endIndex: Int

  public static var trapOnRangeCheckFailure = ResettableValue(true)
}

public func == (lhs: ${Index}, rhs: ${Index}) -> Bool {
  _expectCompatibleIndices(lhs, rhs)
  return lhs.position == rhs.position
}

extension ${Index} : _MinimalIndex {
  public var _offset: Int {
    return position - startIndex
  }
}

% end

//===----------------------------------------------------------------------===//
// MinimalBidirectionalIndex
//===----------------------------------------------------------------------===//

public struct MinimalBidirectionalIndex : BidirectionalIndex {
  public typealias Distance = Int

  public init(position: Int, startIndex: Int, endIndex: Int) {
    self = MinimalBidirectionalIndex(
      collectionState: nil,
      position: position,
      startIndex: startIndex,
      endIndex: endIndex)
  }

  internal init(
    collectionState: _CollectionState?,
    position: Int,
    startIndex: Int,
    endIndex: Int
  ) {
    expectLE(startIndex, position)
    expectGE(endIndex, position)
    self._collectionState = collectionState
    self.position = position
    self.startIndex = startIndex
    self.endIndex = endIndex
  }

  public func successor() -> MinimalBidirectionalIndex {
    expectNotEqual(endIndex, position)
    return MinimalBidirectionalIndex(
      collectionState: _collectionState,
      position: position + 1, startIndex: startIndex, endIndex: endIndex)
  }

  public func predecessor() -> MinimalBidirectionalIndex {
    expectNotEqual(startIndex, position)
    return MinimalBidirectionalIndex(
      collectionState: _collectionState,
      position: position - 1, startIndex: startIndex, endIndex: endIndex)
  }

  public static func _failEarlyRangeCheck(
    index: MinimalBidirectionalIndex,
    bounds: Range<MinimalBidirectionalIndex>
  ) {
    expectLE(bounds.startIndex.position, index.position)
    expectGT(bounds.endIndex.position, index.position)

    if MinimalBidirectionalIndex.trapOnRangeCheckFailure.value {
      Int._failEarlyRangeCheck(
        index.position,
        bounds: bounds.startIndex.position..<bounds.endIndex.position)
    }
  }

  public static func _failEarlyRangeCheck2(
    rangeStart rangeStart: MinimalBidirectionalIndex,
    rangeEnd: MinimalBidirectionalIndex,
    boundsStart: MinimalBidirectionalIndex,
    boundsEnd: MinimalBidirectionalIndex
  ) {
    let range = rangeStart..<rangeEnd
    let bounds = boundsStart..<boundsEnd
    expectLE(bounds.startIndex.position, range.startIndex.position)
    expectGE(bounds.endIndex.position, range.startIndex.position)
    expectLE(bounds.startIndex.position, range.endIndex.position)
    expectGE(bounds.endIndex.position, range.endIndex.position)

    if MinimalBidirectionalIndex.trapOnRangeCheckFailure.value {
      Int._failEarlyRangeCheck2(
        rangeStart: rangeStart.position,
        rangeEnd: rangeEnd.position,
        boundsStart: boundsStart.position,
        boundsEnd: boundsEnd.position)
    }
  }

  public let _collectionState: _CollectionState?

  public let position: Int
  public let startIndex: Int
  public let endIndex: Int

  public static var trapOnRangeCheckFailure = ResettableValue(true)
}

public func == (
  lhs: MinimalBidirectionalIndex,
  rhs: MinimalBidirectionalIndex
) -> Bool {
  _expectCompatibleIndices(lhs, rhs)
  return lhs.position == rhs.position
}

extension MinimalBidirectionalIndex : _MinimalIndex {
  public var _offset: Int {
    return position - startIndex
  }
}

//===----------------------------------------------------------------------===//
// Strict Index Types
//===----------------------------------------------------------------------===//

% for Traversal in ['Forward', 'Bidirectional', 'RandomAccess']:
%   StrictIndex = 'Strict{}Index'.format(Traversal)

public protocol ${StrictIndex} : ${Traversal}Index {
  associatedtype Base : ${Traversal}Index
  init(_ base: Base)
  var base: Base { get set }

  func logSuccessor()
  func logPredecessor()
}

extension ${StrictIndex} {
  public func successor() -> Self {
    logSuccessor()
    return Self(base.successor())
  }
%   if Traversal in ['Bidirectional', 'RandomAccess']:
  public func predecessor() -> Self {
    logPredecessor()
    return Self(base.predecessor())
  }
%   end
}

% end

//===----------------------------------------------------------------------===//
// Defaulted Index Types
//===----------------------------------------------------------------------===//
% for Traversal in ['Forward', 'Bidirectional', 'RandomAccess']:
%   StrictIndex = 'Strict{}Index'.format(Traversal)
%   DefaultedIndex = 'Defaulted{}Index'.format(Traversal)

public struct ${DefaultedIndex}: ${StrictIndex} {
  public typealias Distance = Int
  public typealias Base = Int
  public var base: Base
  public static var timesSuccessorCalled = ResettableValue(0)
  public static var timesPredecessorCalled = ResettableValue(0)

  public init(_ base: Base) {
    self.base = base
  }

  public init(position: Base, startIndex: Base, endIndex: Base) {
    expectLE(startIndex, position)
    expectGE(endIndex, position)
    self.init(position)
  }

  public func logSuccessor() {
    ${DefaultedIndex}.timesSuccessorCalled.value += 1
  }

  public func logPredecessor() {
    ${DefaultedIndex}.timesPredecessorCalled.value += 1
  }

% if Traversal == 'RandomAccess':
  public func distance(to n: ${DefaultedIndex}) -> Distance {
    return n.base - base
  }

  public func advanced(by n: Distance) -> ${DefaultedIndex} {
    return ${DefaultedIndex}(base + n)
  }
% end
}

public func == (lhs: ${DefaultedIndex}, rhs: ${DefaultedIndex}) -> Bool {
  return rhs.base == lhs.base
}

% end



//===----------------------------------------------------------------------===//
// MinimalRandomAccessIndex
//===----------------------------------------------------------------------===//

public struct MinimalRandomAccessIndex : RandomAccessIndex {
  public typealias Distance = Int
  public init(position: Int, startIndex: Int, endIndex: Int) {
    self = MinimalRandomAccessIndex(
      collectionState: nil,
      position: position,
      startIndex: startIndex,
      endIndex: endIndex)
  }

  internal init(
    collectionState: _CollectionState?,
    position: Int,
    startIndex: Int,
    endIndex: Int
  ) {
    expectLE(startIndex, position)
    expectGE(endIndex, position) /*{
      "position=\(self.position) startIndex=\(self.startIndex) endIndex=\(self.endIndex)"
    }*/

    self._collectionState = collectionState
    self.position = position
    self.startIndex = startIndex
    self.endIndex = endIndex
  }

  public func successor() -> MinimalRandomAccessIndex {
    expectNotEqual(endIndex, position)
    return MinimalRandomAccessIndex(
      collectionState: _collectionState,
      position: position + 1, startIndex: startIndex, endIndex: endIndex)
  }

  public func predecessor() -> MinimalRandomAccessIndex {
    expectNotEqual(startIndex, position)
    return MinimalRandomAccessIndex(
      collectionState: _collectionState,
      position: position - 1, startIndex: startIndex, endIndex: endIndex)
  }

  public func distance(to other: MinimalRandomAccessIndex) -> Int {
    _expectCompatibleIndices(self, other)
    return other.position - position
  }

  public func advanced(by n: Int) -> MinimalRandomAccessIndex {
    let newPosition = position + n
    expectLE(startIndex, newPosition)
    expectGE(
      endIndex, newPosition,
      "position=\(self.position) startIndex=\(self.startIndex)")
    return MinimalRandomAccessIndex(
      collectionState: _collectionState,
      position: newPosition, startIndex: startIndex, endIndex: endIndex)
  }

  public static func _failEarlyRangeCheck(
    index: MinimalRandomAccessIndex,
    bounds: Range<MinimalRandomAccessIndex>
  ) {
    expectLE(bounds.startIndex.position, index.position)
    expectGT(bounds.endIndex.position, index.position)

    if MinimalRandomAccessIndex.trapOnRangeCheckFailure.value {
      Int._failEarlyRangeCheck(
        index.position,
        bounds: bounds.startIndex.position..<bounds.endIndex.position)
    }
  }

  public static func _failEarlyRangeCheck2(
    rangeStart rangeStart: MinimalRandomAccessIndex,
    rangeEnd: MinimalRandomAccessIndex,
    boundsStart: MinimalRandomAccessIndex,
    boundsEnd: MinimalRandomAccessIndex
  ) {
    let range = rangeStart..<rangeEnd
    let bounds = boundsStart..<boundsEnd
    expectLE(bounds.startIndex.position, range.startIndex.position)
    expectGE(bounds.endIndex.position, range.startIndex.position)
    expectLE(bounds.startIndex.position, range.endIndex.position)
    expectGE(bounds.endIndex.position, range.endIndex.position)

    if MinimalRandomAccessIndex.trapOnRangeCheckFailure.value {
      Int._failEarlyRangeCheck2(
        rangeStart: rangeStart.position,
        rangeEnd: rangeEnd.position,
        boundsStart: boundsStart.position,
        boundsEnd: boundsEnd.position)
    }
  }

  public let _collectionState: _CollectionState?

  public let position: Int
  public let startIndex: Int
  public let endIndex: Int

  public static var trapOnRangeCheckFailure = ResettableValue(true)
}

public func == (
  lhs: MinimalRandomAccessIndex,
  rhs: MinimalRandomAccessIndex
) -> Bool {
  _expectCompatibleIndices(lhs, rhs)
  return lhs.position == rhs.position
}

extension MinimalRandomAccessIndex : _MinimalIndex {
  public var _offset: Int {
    return position - startIndex
  }
}

//===----------------------------------------------------------------------===//
// Minimal***[Mutable]?Collection
//===----------------------------------------------------------------------===//

% for traversal in [ 'Forward', 'Bidirectional', 'RandomAccess' ]:
%   for mutable in [ False, True ]:
// This comment is a workaround for <rdar://problem/18900352> gyb miscompiles nested loops
%     Protocol = 'Strict%s%sCollection' % (traversal, 'Mutable' if mutable else '')
%     Self = 'Minimal%s%sCollection' % (traversal, 'Mutable' if mutable else '')
%     Index = 'Minimal%sIndex' % traversal

public protocol ${Protocol} : ${'MutableCollection' if mutable else 'Collection'} {
  associatedtype Element
  init(base: ${Self}<Element>)
%     if mutable:
  var base: ${Self}<Element> { get set }
%     else:
  var base: ${Self}<Element> { get }
%     end
}

extension ${Protocol} {
  public init<S : Sequence where S.Iterator.Element == Element>(
    elements: S,
    underestimatedCount: UnderestimatedCountBehavior = .value(0)
  ) {
    self.init(base:
      ${Self}(elements: elements, underestimatedCount: underestimatedCount))
  }

  public var underestimatedCount: Int {
    return base.underestimatedCount
  }
}

extension ${Protocol} where Iterator : _MinimalIterator {
  public func makeIterator() -> MinimalIterator<Element> {
    return base.makeIterator()
  }
}

extension ${Protocol} where Index : _MinimalIndex {
  public var startIndex: ${Index} {
    return base.startIndex
  }

  public var endIndex: ${Index} {
    return base.endIndex
  }

  public subscript(i: ${Index}) -> Element {
    get {
      _expectCompatibleIndices(self.startIndex, i)
      return base[i]
    }
%     if mutable:
    set {
      _expectCompatibleIndices(self.startIndex, i)
      base[i] = newValue
    }
%     end
  }
}

/// A minimal implementation of `Collection` with extra checks.
public struct ${Self}<T> : ${'MutableCollection' if mutable else 'Collection'} {
  public init<S : Sequence where S.Iterator.Element == T>(
    elements: S,
    underestimatedCount: UnderestimatedCountBehavior = .value(0)
  ) {
    self._elements = Array(elements)

    self._collectionState = _CollectionState(
      newRootStateForElementCount: self._elements.count)

    switch underestimatedCount {
    case .precise:
      self.underestimatedCount = _elements.count

    case .half:
      self.underestimatedCount = _elements.count / 2

    case .overestimate:
      self.underestimatedCount = _elements.count * 3 + 5

    case .value(let count):
      self.underestimatedCount = count
    }
  }

  public func makeIterator() -> MinimalIterator<T> {
    return MinimalIterator(_elements)
  }

  public var startIndex: ${Index} {
    return ${Index}(
      collectionState: _collectionState,
      position: 0,
      startIndex: 0,
      endIndex: _elements.endIndex)
  }

  public var endIndex: ${Index} {
    return ${Index}(
      collectionState: _collectionState,
      position: _elements.endIndex,
      startIndex: 0,
      endIndex: _elements.endIndex)
  }

  public subscript(i: ${Index}) -> T {
    get {
      _expectCompatibleIndices(self.startIndex, i)
      return _elements[i.position]
    }
%     if mutable:
    set {
      _expectCompatibleIndices(self.startIndex, i)
      _elements[i.position] = newValue
    }
%     end
  }

  public var underestimatedCount: Int

  internal var _elements: [T]
  internal let _collectionState: _CollectionState
}

%   end
% end

//===----------------------------------------------------------------------===//
// Minimal***RangeReplaceableCollection
//===----------------------------------------------------------------------===//

% for traversal in [ 'Forward', 'Bidirectional', 'RandomAccess' ]:
%   Protocol = 'Strict%sRangeReplaceableCollection' % traversal
%   Self = 'Minimal%sRangeReplaceableCollection' % traversal
%   Index = 'Minimal%sIndex' % traversal

public protocol ${Protocol} : RangeReplaceableCollection {
  associatedtype Element
  init(base: ${Self}<Element>)
  var base: ${Self}<Element> { get set }
}

extension ${Protocol} {
  public mutating func replaceSubrange<
    C: Collection where C.Iterator.Element == Element
  >(subRange: Range<${Self}<Element>.Index>,
    with newElements: C) {
    base.replaceSubrange(subRange, with: newElements)
  }

  public mutating func removeLast() -> Element {
    return base.removeLast()
  }
}

extension ${Protocol} where Iterator : _MinimalIterator {
  public func makeIterator() -> MinimalIterator<Element> {
    return base.makeIterator()
  }
}

extension ${Protocol} where Index : _MinimalIndex {
  public var startIndex: ${Index} {
    return base.startIndex
  }

  public var endIndex: ${Index} {
    return base.endIndex
  }

  public subscript(i: ${Index}) -> Element {
    get {
      _expectCompatibleIndices(self.startIndex.advanced(by: i.position), i)
      return base[i]
    }
    set {
      _expectCompatibleIndices(self.startIndex.advanced(by: i.position), i)
      base[i] = newValue
    }
  }
}

/// A minimal implementation of `RangeReplaceableCollection` with extra
/// checks.
public struct ${Self}<T> : RangeReplaceableCollection {
  /// Creates a collection with given contents, but a unique modification
  /// history.  No other instance has the same modification history.
  public init<S : Sequence where S.Iterator.Element == T>(
    elements: S,
    underestimatedCount: UnderestimatedCountBehavior = .value(0)
  ) {
    self.elements = Array(elements)

    self._collectionState = _CollectionState(
      newRootStateForElementCount: self.elements.count)

    switch underestimatedCount {
    case .precise:
      self.underestimatedCount = self.elements.count

    case .half:
      self.underestimatedCount = self.elements.count / 2

    case .overestimate:
      self.underestimatedCount = self.elements.count * 3 + 5

    case .value(let count):
      self.underestimatedCount = count
    }
  }

  public init() {
    self.underestimatedCount = 0
    self.elements = []
    self._collectionState = _CollectionState(name: "\(self.dynamicType)", elementCount: 0)
  }

  public init<
    S : Sequence where S.Iterator.Element == T
  >(_ elements: S) {
    self.underestimatedCount = 0
    self.elements = Array(elements)
    self._collectionState =
      _CollectionState(newRootStateForElementCount: self.elements.count)
  }

  public func makeIterator() -> MinimalIterator<T> {
    return MinimalIterator(elements)
  }

  public var startIndex: ${Index} {
    return ${Index}(
      collectionState: _collectionState,
      position: 0,
      startIndex: 0,
      endIndex: elements.endIndex)
  }

  public var endIndex: ${Index} {
    return ${Index}(
      collectionState: _collectionState,
      position: elements.endIndex,
      startIndex: 0,
      endIndex: elements.endIndex)
  }

  public subscript(i: ${Index}) -> T {
    get {
      _expectCompatibleIndices(self.startIndex.advanced(by: i.position), i)
      return elements[i.position]
    }
    set {
      _expectCompatibleIndices(self.startIndex.advanced(by: i.position), i)
      elements[i.position] = newValue
    }
  }

  public mutating func reserveCapacity(n: Int) {
    _willMutate(.reserveCapacity(capacity: n))
    elements.reserveCapacity(n)
    reservedCapacity = Swift.max(reservedCapacity, n)
  }

  public mutating func append(x: T) {
    _willMutate(.append)
    elements.append(x)
  }

  public mutating func append<
    S : Sequence where S.Iterator.Element == T
  >(contentsOf newElements: S) {
    let oldCount = count
    elements.append(contentsOf: newElements)
    let newCount = count
    _willMutate(.appendContentsOf(count: newCount - oldCount))
  }

  public mutating func replaceSubrange<
    C : Collection where C.Iterator.Element == T
  >(
    subRange: Range<${Index}>, with newElements: C
  ) {
    let oldCount = count
    elements.replaceSubrange(
      subRange.startIndex.position..<subRange.endIndex.position,
      with: newElements)
    let newCount = count
    _willMutate(.replaceRange(
      subRange: subRange.startIndex._offset..<subRange.endIndex._offset,
      replacementCount: subRange.count + newCount - oldCount))
  }

  public mutating func insert(newElement: T, at i: ${Index}) {
    _willMutate(.insert(atIndex: i._offset))
    elements.insert(newElement, at: i.position)
  }

  public mutating func insert<
    S : Collection where S.Iterator.Element == T
  >(contentsOf newElements: S, at i: ${Index}) {
    let oldCount = count
    elements.insert(contentsOf: newElements, at: i.position)
    let newCount = count

    if newCount - oldCount != 0 {
      _willMutate(.insertContentsOf(
        atIndex: i._offset,
        count: newCount - oldCount))
    }
  }

  public mutating func remove(at i: ${Index}) -> T {
    _willMutate(.removeAtIndex(index: i._offset))
    return elements.remove(at: i.position)
  }

  public mutating func removeLast() -> T {
    _willMutate(.removeLast)
    return elements.removeLast()
  }

  public mutating func removeSubrange(subRange: Range<${Index}>) {
    if !subRange.isEmpty {
      _willMutate(.removeRange(
        subRange: subRange.startIndex._offset..<subRange.endIndex._offset))
    }
    elements.removeSubrange(
      subRange.startIndex.position..<subRange.endIndex.position
    )
  }

  public mutating func removeAll(keepingCapacity keepCapacity: Bool = false) {
    _willMutate(.removeAll(keepCapacity: keepCapacity))
    // Ignore the value of `keepCapacity`.
    elements.removeAll(keepingCapacity: false)
  }

  internal mutating func _willMutate(operation: _CollectionOperation) {
    _collectionState = _CollectionStateTransition(
      previousState: _collectionState,
      operation: operation)._nextState
  }

  public var underestimatedCount: Int
  public var reservedCapacity: Int = 0

  public var elements: [T]
  internal var _collectionState: _CollectionState
}

% end

/// A Sequence that uses as many default implementations as
/// `Sequence` can provide.
public struct DefaultedSequence<Element> : StrictSequence {
  public let base: MinimalSequence<Element>

  public init(base: MinimalSequence<Element>) {
    self.base = base
  }
}

% for traversal in [ 'Forward', 'Bidirectional', 'RandomAccess' ]:

/// A Collection that uses as many default implementations as
/// `Collection` can provide.
public struct Defaulted${traversal}Collection<Element>
  : Strict${traversal}Collection {

  public typealias Base = Minimal${traversal}Collection<Element>
  public typealias Iterator = MinimalIterator<Element>
  public typealias Index = Minimal${traversal}Index

  public let base: Base

  public init(base: Base) {
    self.base = base
  }

  public init(_ array: [Element]) {
    self.base = Base(elements: array)
  }

  public init(elements: [Element]) {
    self.base = Base(elements: elements)
  }
}

public struct Defaulted${traversal}MutableCollection<Element>
  : Strict${traversal}MutableCollection {

  public typealias Base = Minimal${traversal}MutableCollection<Element>
  public typealias Iterator = MinimalIterator<Element>
  public typealias Index = Minimal${traversal}Index

  public var base: Base

  public init(base: Base) {
    self.base = base
  }

  public init(_ array: [Element]) {
    self.base = Base(elements: array)
  }

  public init(elements: [Element]) {
    self.base = Base(elements: elements)
  }
}

public struct Defaulted${traversal}RangeReplaceableCollection<Element>
  : Strict${traversal}RangeReplaceableCollection {

  public typealias Base = Minimal${traversal}RangeReplaceableCollection<Element>
  public typealias Iterator = MinimalIterator<Element>
  public typealias Index = Minimal${traversal}Index

  public var base: Base

  public init() {
    base = Base()
  }

  public init(base: Base) {
    self.base = base
  }

  public init(_ array: [Element]) {
    self.base = Base(elements: array)
  }

  public init(elements: [Element]) {
    self.base = Base(elements: elements)
  }
}

public struct Defaulted${traversal}RangeReplaceableSlice<Element>
  : RangeReplaceableCollection {

  public typealias Self_ = Defaulted${traversal}RangeReplaceableSlice<Element>
  public typealias Base = Minimal${traversal}RangeReplaceableCollection<Element>
  public typealias Iterator = MinimalIterator<Element>
  public typealias Index = Minimal${traversal}Index

  public var base: Base
  public var startIndex: Index
  public var endIndex: Index

  public init() {
    expectSliceType(Self_.self)

    self.base = Base()
    self.startIndex = base.startIndex
    self.endIndex = base.endIndex
  }

  public init(base: Base) {
    self.base = base
    self.startIndex = base.startIndex
    self.endIndex = base.endIndex
  }

  public init(base: Base, bounds: Range<Index>) {
    self.base = base
    self.startIndex = bounds.startIndex
    self.endIndex = bounds.endIndex
  }

  public init(_ array: [Element]) {
    self = Defaulted${traversal}RangeReplaceableSlice(
      base: Base(elements: array))
  }

  public init(elements: [Element]) {
    self = Defaulted${traversal}RangeReplaceableSlice(
      base: Base(elements: elements))
  }

  public func makeIterator() -> MinimalIterator<Element> {
    return MinimalIterator(Array(self))
  }

  public subscript(index: Index) -> Element {
    Index._failEarlyRangeCheck(index, bounds: startIndex..<endIndex)
    return base[index]
  }

  public subscript(bounds: Range<Index>) -> Self_ {
    Index._failEarlyRangeCheck2(
      rangeStart: bounds.startIndex,
      rangeEnd: bounds.endIndex,
      boundsStart: startIndex,
      boundsEnd: endIndex)
    return Defaulted${traversal}RangeReplaceableSlice(
      base: base, bounds: bounds)
  }

  public mutating func replaceSubrange<
    C : Collection where C.Iterator.Element == Element
  >(
    subRange: Range<Index>,
    with newElements: C
  ) {
    let startOffset = startIndex.position
    let endOffset =
      endIndex.position
      - subRange.count
      + numericCast(newElements.count) as Int
    Index._failEarlyRangeCheck2(
      rangeStart: subRange.startIndex,
      rangeEnd: subRange.endIndex,
      boundsStart: startIndex,
      boundsEnd: endIndex)
    base.replaceSubrange(subRange, with: newElements)
    startIndex = base.startIndex.advanced(by: startOffset)
    endIndex = base.startIndex.advanced(by: endOffset)
  }
}

% end

// ${'Local Variables'}:
// eval: (read-only-mode 1)
// End: