/// A sequence of weakly held elements.
///
/// Iterating over this sequence yields the elements that still exist at the
/// moment of iteration. Subsequent iterations may not yield the same elements,
/// as some elements may have been removed from memory.
public struct WeakSequence<Element: AnyObject> : Sequence {
  var _contents: [Box] = []

  /// A box for weakly holding a class instance.
  class Box {
    weak var value: Element?

    init(_ value: Element) {
      self.value = value
    }
  }

  /// An iterator over a sequence of weakly held instances.
  public struct Iterator : IteratorProtocol {
    var _contents: [Box]
    var _current: Int = 0

    init(_ _weakSequence: WeakSequence) {
      self._contents = _weakSequence._contents
    }

    public mutating func next() -> Element? {
      while _current != _contents.endIndex {
        defer { _current += 1 }
        if let result = _contents[_current].value {
          return result
        }
      }
      return nil
    }
  }

  public func makeIterator() -> Iterator {
    return Iterator(self)
  }

  /// The number of elements in the sequence that are still in memory.
  public var count: Int {
    return _contents.lazy.filter({ $0.value != nil }).count
  }

  /// The number of weakly-held instances that are referenced by this sequence.
  public var weakCount: Int {
    return _contents.count
  }

  /// Removes any already released references from the sequence.
  public mutating func compress() {
    _contents = _contents.filter { $0.value != nil }
  }

  public init() {}

  public init<S: Sequence>(_ elements: S) where S.Element == Element {
    _contents = elements.map(Box.init)
  }

  public mutating func append(_ element: Element) {
    _contents.append(Box(element))
  }

  public mutating func append<S: Sequence>(contentsOf elements: S)
    where S.Element == Element
  {
    _contents.append(contentsOf: elements.map(Box.init))
  }

  public mutating func prepend(_ element: Element) {
    _contents.insert(Box(element), at: 0)
  }

  public mutating func prepend<S: Sequence>(contentsOf elements: S)
    where S.Element == Element
  {
    _contents.replaceSubrange(0..<0, with: elements.map(Box.init))
  }

  public mutating func remove(_ element: Element) -> Element? {
    if let i = _contents.index(where: { $0.value === element }) {
      return _contents.remove(at: i).value
    }
    return nil
  }

  public mutating func removeAll() {
    _contents.removeAll()
  }
}