stdlib/public/core/Filter.swift.gyb - third_party/swift - Git at Google

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

 %{
 from gyb_stdlib_support import (
     collectionForTraversal,
     sliceTypeName
 )
 }%

 /// An iterator over the elements traversed by some base iterator that also
 /// satisfy a given predicate.
 ///
 /// - Note: This is the associated `Iterator` of `LazyFilterSequence`
 /// and `LazyFilterCollection`.
 public struct LazyFilterIterator<
   Base : IteratorProtocol
 > : IteratorProtocol, Sequence {
   /// 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`.
   ///
   /// - Precondition: `next()` has not been applied to a copy of `self`
   ///   since the copy was made.
   public mutating func next() -> Base.Element? {
     while let n = _base.next() {
       if _predicate(n) {
         return n
       }
     }
     return nil
   }

   /// Creates an instance that produces the elements `x` of `base`
   /// for which `isIncluded(x) == true`.
   internal init(
     _base: Base,
     _ isIncluded: @escaping (Base.Element) -> Bool
   ) {
     self._base = _base
     self._predicate = isIncluded
   }

   /// The underlying iterator whose elements are being filtered.
   public var base: Base { return _base }

   internal var _base: Base

   /// The predicate used to determine which elements produced by
   /// `base` are also produced by `self`.
   internal let _predicate: (Base.Element) -> Bool
 }

 /// A sequence whose elements consist of the elements of some base
 /// sequence that also satisfy a given predicate.
 ///
 /// - Note: `s.lazy.filter { ... }`, for an arbitrary sequence `s`,
 ///   is a `LazyFilterSequence`.
 public struct LazyFilterSequence<Base : Sequence>
   : LazySequenceProtocol {

   /// Returns an iterator over the elements of this sequence.
   ///
   /// - Complexity: O(1).
   public func makeIterator() -> LazyFilterIterator<Base.Iterator> {
     return LazyFilterIterator(
       _base: base.makeIterator(), _include)
   }

   /// Creates an instance consisting of the elements `x` of `base` for
   /// which `isIncluded(x) == true`.
   public // @testable
   init(
     _base base: Base,
     _ isIncluded: @escaping (Base.Iterator.Element) -> Bool
   ) {
     self.base = base
     self._include = isIncluded
   }

   /// The underlying sequence whose elements are being filtered
   public let base: Base

   /// The predicate used to determine which elements of `base` are
   /// also elements of `self`.
   internal let _include: (Base.Iterator.Element) -> Bool
 }

 /// The `Index` used for subscripting a `LazyFilterCollection`.
 ///
 /// The positions of a `LazyFilterIndex` correspond to those positions
 /// `p` in its underlying collection `c` such that `c[p]`
 /// satisfies the predicate with which the `LazyFilterIndex` was
 /// initialized.
 ///
 /// - Note: The performance of advancing a `LazyFilterIndex`
 ///   depends on how sparsely the filtering predicate is satisfied,
 ///   and may not offer the usual performance given by models of
 ///   `Collection`.
 public struct LazyFilterIndex<Base : Collection> {

   /// The position corresponding to `self` in the underlying collection.
   public let base: Base.Index
 }

 extension LazyFilterIndex : Comparable {
   public static func == (
     lhs: LazyFilterIndex<Base>,
     rhs: LazyFilterIndex<Base>
   ) -> Bool {
     return lhs.base == rhs.base
   }

   public static func != (
     lhs: LazyFilterIndex<Base>,
     rhs: LazyFilterIndex<Base>
   ) -> Bool {
     return lhs.base != rhs.base
   }

   public static func < (
     lhs: LazyFilterIndex<Base>,
     rhs: LazyFilterIndex<Base>
   ) -> Bool {
     return lhs.base < rhs.base
   }

   public static func <= (
     lhs: LazyFilterIndex<Base>,
     rhs: LazyFilterIndex<Base>
   ) -> Bool {
     return lhs.base <= rhs.base
   }

   public static func >= (
     lhs: LazyFilterIndex<Base>,
     rhs: LazyFilterIndex<Base>
   ) -> Bool {
     return lhs.base >= rhs.base
   }

   public static func > (
     lhs: LazyFilterIndex<Base>,
     rhs: LazyFilterIndex<Base>
   ) -> Bool {
     return lhs.base > rhs.base
   }
 }

 // FIXME(ABI)(compiler limitation): `LazyFilter*Collection` types should be
 // collapsed into one `LazyFilterCollection` using conditional conformances.
 // Maybe even combined with `LazyFilterSequence`.

 % for Traversal in ['Forward', 'Bidirectional']:
 %   Self = "LazyFilter" + collectionForTraversal(Traversal)
 %   Slice = sliceTypeName(traversal=Traversal, mutable=False, rangeReplaceable=False)

 /// A lazy `Collection` wrapper that includes the elements of an
 /// underlying collection that satisfy a predicate.
 ///
 /// - Note: The performance of accessing `startIndex`, `first`, any methods
 ///   that depend on `startIndex`, or of advancing a `LazyFilterIndex` depends
 ///   on how sparsely the filtering predicate is satisfied, and may not offer
 ///   the usual performance given by `Collection`. Be aware, therefore, that
 ///   general operations on `LazyFilterCollection` instances may not have the
 ///   documented complexity.
 public struct ${Self}<
   Base : ${collectionForTraversal(Traversal)}
 > : LazyCollectionProtocol, ${collectionForTraversal(Traversal)} {

   /// A type that represents a valid position in the collection.
   ///
   /// Valid indices consist of the position of every element and a
   /// "past the end" position that's not valid for use as a subscript.
   public typealias Index = LazyFilterIndex<Base>

   public typealias IndexDistance = Base.IndexDistance

   /// Creates an instance containing the elements of `base` that
   /// satisfy `isIncluded`.
   public // @testable
   init(
     _base: Base,
     _ isIncluded: @escaping (Base.Iterator.Element) -> Bool
   ) {
     self._base = _base
     self._predicate = isIncluded
   }

   /// The position of the first element in a non-empty collection.
   ///
   /// In an empty collection, `startIndex == endIndex`.
   ///
   /// - Complexity: O(N), where N is the ratio between unfiltered and
   ///   filtered collection counts.
   public var startIndex: Index {
     var index = _base.startIndex
     while index != _base.endIndex && !_predicate(_base[index]) {
       _base.formIndex(after: &index)
     }
     return LazyFilterIndex(base: index)
   }

   /// The collection's "past the end" position---that is, the position one
   /// greater than the last valid subscript argument.
   ///
   /// `endIndex` is always reachable from `startIndex` by zero or more
   /// applications of `index(after:)`.
   public var endIndex: Index {
     return LazyFilterIndex(base: _base.endIndex)
   }

   // TODO: swift-3-indexing-model - add docs
   public func index(after i: Index) -> Index {
     var i = i
     formIndex(after: &i)
     return i
   }

   public func formIndex(after i: inout Index) {
     // TODO: swift-3-indexing-model: _failEarlyRangeCheck i?
     var index = i.base
     _precondition(index != _base.endIndex, "can't advance past endIndex")
     repeat {
       _base.formIndex(after: &index)
     } while index != _base.endIndex && !_predicate(_base[index])
     i = LazyFilterIndex(base: index)
   }

 %   if Traversal == 'Bidirectional':
   public func index(before i: Index) -> Index {
     var i = i
     formIndex(before: &i)
     return i
   }

   public func formIndex(before i: inout Index) {
     // TODO: swift-3-indexing-model: _failEarlyRangeCheck i?
     var index = i.base
     _precondition(index != _base.startIndex, "can't retreat before startIndex")
     repeat {
       _base.formIndex(before: &index)
     } while !_predicate(_base[index])
     i = LazyFilterIndex(base: index)
   }
 %   end

   /// Accesses the element at `position`.
   ///
   /// - Precondition: `position` is a valid position in `self` and
   /// `position != endIndex`.
   public subscript(position: Index) -> Base.Iterator.Element {
     return _base[position.base]
   }

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

   // FIXME(ABI)(compiler limitation): we actually want to add:
   //
   //   typealias SubSequence = ${Self}<Base.SubSequence>
   //
   // so that all slicing optimizations of the base collection can kick in.
   //
   // We can't do that right now though, because that would force a lot of
   // constraints on `Base.SubSequence`, limiting the possible contexts where
   // the `.lazy.filter` API can be used.

   /// Returns an iterator over the elements of this sequence.
   ///
   /// - Complexity: O(1).
   public func makeIterator() -> LazyFilterIterator<Base.Iterator> {
     return LazyFilterIterator(
       _base: _base.makeIterator(), _predicate)
   }

   var _base: Base
   let _predicate: (Base.Iterator.Element) -> Bool
 }

 % end

 extension LazySequenceProtocol {
   /// Returns the elements of `self` that satisfy `isIncluded`.
   ///
   /// - Note: The elements of the result are computed on-demand, as
   ///   the result is used. No buffering storage is allocated and each
   ///   traversal step invokes `predicate` on one or more underlying
   ///   elements.
   public func filter(
     _ isIncluded: @escaping (Elements.Iterator.Element) -> Bool
   ) -> LazyFilterSequence<Self.Elements> {
     return LazyFilterSequence(
       _base: self.elements, isIncluded)
   }
 }

 % for Traversal in ['Forward', 'Bidirectional']:

 extension LazyCollectionProtocol
   where
   Self : ${collectionForTraversal(Traversal)},
   Elements : ${collectionForTraversal(Traversal)}
 {
   /// Returns the elements of `self` that satisfy `predicate`.
   ///
   /// - Note: The elements of the result are computed on-demand, as
   ///   the result is used. No buffering storage is allocated and each
   ///   traversal step invokes `predicate` on one or more underlying
   ///   elements.
   public func filter(
     _ isIncluded: @escaping (Elements.Iterator.Element) -> Bool
   ) -> LazyFilter${collectionForTraversal(Traversal)}<Self.Elements> {
     return LazyFilter${collectionForTraversal(Traversal)}(
       _base: self.elements, isIncluded)
   }
 }

 % end

 @available(*, unavailable, renamed: "LazyFilterIterator")
 public struct LazyFilterGenerator<Base : IteratorProtocol> {}

 extension LazyFilterIterator {
   @available(*, unavailable, message: "use '.lazy.filter' on the sequence")
   public init(
     _ base: Base,
     whereElementsSatisfy predicate: (Base.Element) -> Bool
   ) {
     Builtin.unreachable()
   }
 }

 extension LazyFilterSequence {
   @available(*, unavailable, message: "use '.lazy.filter' on the sequence")
   public init(
     _ base: Base,
     whereElementsSatisfy predicate: (Base.Iterator.Element) -> Bool
   ) {
     Builtin.unreachable()
   }

   @available(*, unavailable, renamed: "makeIterator()")
   public func generate() -> LazyFilterIterator<Base.Iterator> {
     Builtin.unreachable()
   }
 }

 extension LazyFilterCollection {
   @available(*, unavailable, message: "use '.lazy.filter' on the collection")
   public init(
     _ base: Base,
     whereElementsSatisfy predicate: (Base.Iterator.Element) -> Bool
   ) {
     Builtin.unreachable()
   }

   @available(*, unavailable, renamed: "makeIterator()")
   public func generate() -> LazyFilterIterator<Base.Iterator> {
     Builtin.unreachable()
   }
 }

 // ${'Local Variables'}:
 // eval: (read-only-mode 1)
 // End:
	//===--- Filter.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
	//
	//===----------------------------------------------------------------------===//

	%{
	from gyb_stdlib_support import (
	collectionForTraversal,
	sliceTypeName
	)
	}%

	/// An iterator over the elements traversed by some base iterator that also
	/// satisfy a given predicate.
	///
	/// - Note: This is the associated `Iterator` of `LazyFilterSequence`
	/// and `LazyFilterCollection`.
	public struct LazyFilterIterator<
	Base : IteratorProtocol
	> : IteratorProtocol, Sequence {
	/// 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`.
	///
	/// - Precondition: `next()` has not been applied to a copy of `self`
	/// since the copy was made.
	public mutating func next() -> Base.Element? {
	while let n = _base.next() {
	if _predicate(n) {
	return n
	}
	}
	return nil
	}

	/// Creates an instance that produces the elements `x` of `base`
	/// for which `isIncluded(x) == true`.
	internal init(
	_base: Base,
	_ isIncluded: @escaping (Base.Element) -> Bool
	) {
	self._base = _base
	self._predicate = isIncluded
	}

	/// The underlying iterator whose elements are being filtered.
	public var base: Base { return _base }

	internal var _base: Base

	/// The predicate used to determine which elements produced by
	/// `base` are also produced by `self`.
	internal let _predicate: (Base.Element) -> Bool
	}

	/// A sequence whose elements consist of the elements of some base
	/// sequence that also satisfy a given predicate.
	///
	/// - Note: `s.lazy.filter { ... }`, for an arbitrary sequence `s`,
	/// is a `LazyFilterSequence`.
	public struct LazyFilterSequence<Base : Sequence>
	: LazySequenceProtocol {

	/// Returns an iterator over the elements of this sequence.
	///
	/// - Complexity: O(1).
	public func makeIterator() -> LazyFilterIterator<Base.Iterator> {
	return LazyFilterIterator(
	_base: base.makeIterator(), _include)
	}

	/// Creates an instance consisting of the elements `x` of `base` for
	/// which `isIncluded(x) == true`.
	public // @testable
	init(
	_base base: Base,
	_ isIncluded: @escaping (Base.Iterator.Element) -> Bool
	) {
	self.base = base
	self._include = isIncluded
	}

	/// The underlying sequence whose elements are being filtered
	public let base: Base

	/// The predicate used to determine which elements of `base` are
	/// also elements of `self`.
	internal let _include: (Base.Iterator.Element) -> Bool
	}

	/// The `Index` used for subscripting a `LazyFilterCollection`.
	///
	/// The positions of a `LazyFilterIndex` correspond to those positions
	/// `p` in its underlying collection `c` such that `c[p]`
	/// satisfies the predicate with which the `LazyFilterIndex` was
	/// initialized.
	///
	/// - Note: The performance of advancing a `LazyFilterIndex`
	/// depends on how sparsely the filtering predicate is satisfied,
	/// and may not offer the usual performance given by models of
	/// `Collection`.
	public struct LazyFilterIndex<Base : Collection> {

	/// The position corresponding to `self` in the underlying collection.
	public let base: Base.Index
	}

	extension LazyFilterIndex : Comparable {
	public static func == (
	lhs: LazyFilterIndex<Base>,
	rhs: LazyFilterIndex<Base>
	) -> Bool {
	return lhs.base == rhs.base
	}

	public static func != (
	lhs: LazyFilterIndex<Base>,
	rhs: LazyFilterIndex<Base>
	) -> Bool {
	return lhs.base != rhs.base
	}

	public static func < (
	lhs: LazyFilterIndex<Base>,
	rhs: LazyFilterIndex<Base>
	) -> Bool {
	return lhs.base < rhs.base
	}

	public static func <= (
	lhs: LazyFilterIndex<Base>,
	rhs: LazyFilterIndex<Base>
	) -> Bool {
	return lhs.base <= rhs.base
	}

	public static func >= (
	lhs: LazyFilterIndex<Base>,
	rhs: LazyFilterIndex<Base>
	) -> Bool {
	return lhs.base >= rhs.base
	}

	public static func > (
	lhs: LazyFilterIndex<Base>,
	rhs: LazyFilterIndex<Base>
	) -> Bool {
	return lhs.base > rhs.base
	}
	}

	// FIXME(ABI)(compiler limitation): `LazyFilter*Collection` types should be
	// collapsed into one `LazyFilterCollection` using conditional conformances.
	// Maybe even combined with `LazyFilterSequence`.

	% for Traversal in ['Forward', 'Bidirectional']:
	% Self = "LazyFilter" + collectionForTraversal(Traversal)
	% Slice = sliceTypeName(traversal=Traversal, mutable=False, rangeReplaceable=False)

	/// A lazy `Collection` wrapper that includes the elements of an
	/// underlying collection that satisfy a predicate.
	///
	/// - Note: The performance of accessing `startIndex`, `first`, any methods
	/// that depend on `startIndex`, or of advancing a `LazyFilterIndex` depends
	/// on how sparsely the filtering predicate is satisfied, and may not offer
	/// the usual performance given by `Collection`. Be aware, therefore, that
	/// general operations on `LazyFilterCollection` instances may not have the
	/// documented complexity.
	public struct ${Self}<
	Base : ${collectionForTraversal(Traversal)}
	> : LazyCollectionProtocol, ${collectionForTraversal(Traversal)} {

	/// A type that represents a valid position in the collection.
	///
	/// Valid indices consist of the position of every element and a
	/// "past the end" position that's not valid for use as a subscript.
	public typealias Index = LazyFilterIndex<Base>

	public typealias IndexDistance = Base.IndexDistance

	/// Creates an instance containing the elements of `base` that
	/// satisfy `isIncluded`.
	public // @testable
	init(
	_base: Base,
	_ isIncluded: @escaping (Base.Iterator.Element) -> Bool
	) {
	self._base = _base
	self._predicate = isIncluded
	}

	/// The position of the first element in a non-empty collection.
	///
	/// In an empty collection, `startIndex == endIndex`.
	///
	/// - Complexity: O(N), where N is the ratio between unfiltered and
	/// filtered collection counts.
	public var startIndex: Index {
	var index = _base.startIndex
	while index != _base.endIndex && !_predicate(_base[index]) {
	_base.formIndex(after: &index)
	}
	return LazyFilterIndex(base: index)
	}

	/// The collection's "past the end" position---that is, the position one
	/// greater than the last valid subscript argument.
	///
	/// `endIndex` is always reachable from `startIndex` by zero or more
	/// applications of `index(after:)`.
	public var endIndex: Index {
	return LazyFilterIndex(base: _base.endIndex)
	}

	// TODO: swift-3-indexing-model - add docs
	public func index(after i: Index) -> Index {
	var i = i
	formIndex(after: &i)
	return i
	}

	public func formIndex(after i: inout Index) {
	// TODO: swift-3-indexing-model: _failEarlyRangeCheck i?
	var index = i.base
	_precondition(index != _base.endIndex, "can't advance past endIndex")
	repeat {
	_base.formIndex(after: &index)
	} while index != _base.endIndex && !_predicate(_base[index])
	i = LazyFilterIndex(base: index)
	}

	% if Traversal == 'Bidirectional':
	public func index(before i: Index) -> Index {
	var i = i
	formIndex(before: &i)
	return i
	}

	public func formIndex(before i: inout Index) {
	// TODO: swift-3-indexing-model: _failEarlyRangeCheck i?
	var index = i.base
	_precondition(index != _base.startIndex, "can't retreat before startIndex")
	repeat {
	_base.formIndex(before: &index)
	} while !_predicate(_base[index])
	i = LazyFilterIndex(base: index)
	}
	% end

	/// Accesses the element at `position`.
	///
	/// - Precondition: `position` is a valid position in `self` and
	/// `position != endIndex`.
	public subscript(position: Index) -> Base.Iterator.Element {
	return _base[position.base]
	}

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

	// FIXME(ABI)(compiler limitation): we actually want to add:
	//
	// typealias SubSequence = ${Self}<Base.SubSequence>
	//
	// so that all slicing optimizations of the base collection can kick in.
	//
	// We can't do that right now though, because that would force a lot of
	// constraints on `Base.SubSequence`, limiting the possible contexts where
	// the `.lazy.filter` API can be used.

	/// Returns an iterator over the elements of this sequence.
	///
	/// - Complexity: O(1).
	public func makeIterator() -> LazyFilterIterator<Base.Iterator> {
	return LazyFilterIterator(
	_base: _base.makeIterator(), _predicate)
	}

	var _base: Base
	let _predicate: (Base.Iterator.Element) -> Bool
	}

	% end

	extension LazySequenceProtocol {
	/// Returns the elements of `self` that satisfy `isIncluded`.
	///
	/// - Note: The elements of the result are computed on-demand, as
	/// the result is used. No buffering storage is allocated and each
	/// traversal step invokes `predicate` on one or more underlying
	/// elements.
	public func filter(
	_ isIncluded: @escaping (Elements.Iterator.Element) -> Bool
	) -> LazyFilterSequence<Self.Elements> {
	return LazyFilterSequence(
	_base: self.elements, isIncluded)
	}
	}

	% for Traversal in ['Forward', 'Bidirectional']:

	extension LazyCollectionProtocol
	where
	Self : ${collectionForTraversal(Traversal)},
	Elements : ${collectionForTraversal(Traversal)}
	{
	/// Returns the elements of `self` that satisfy `predicate`.
	///
	/// - Note: The elements of the result are computed on-demand, as
	/// the result is used. No buffering storage is allocated and each
	/// traversal step invokes `predicate` on one or more underlying
	/// elements.
	public func filter(
	_ isIncluded: @escaping (Elements.Iterator.Element) -> Bool
	) -> LazyFilter${collectionForTraversal(Traversal)}<Self.Elements> {
	return LazyFilter${collectionForTraversal(Traversal)}(
	_base: self.elements, isIncluded)
	}
	}

	% end

	@available(*, unavailable, renamed: "LazyFilterIterator")
	public struct LazyFilterGenerator<Base : IteratorProtocol> {}

	extension LazyFilterIterator {
	@available(*, unavailable, message: "use '.lazy.filter' on the sequence")
	public init(
	_ base: Base,
	whereElementsSatisfy predicate: (Base.Element) -> Bool
	) {
	Builtin.unreachable()
	}
	}

	extension LazyFilterSequence {
	@available(*, unavailable, message: "use '.lazy.filter' on the sequence")
	public init(
	_ base: Base,
	whereElementsSatisfy predicate: (Base.Iterator.Element) -> Bool
	) {
	Builtin.unreachable()
	}

	@available(*, unavailable, renamed: "makeIterator()")
	public func generate() -> LazyFilterIterator<Base.Iterator> {
	Builtin.unreachable()
	}
	}

	extension LazyFilterCollection {
	@available(*, unavailable, message: "use '.lazy.filter' on the collection")
	public init(
	_ base: Base,
	whereElementsSatisfy predicate: (Base.Iterator.Element) -> Bool
	) {
	Builtin.unreachable()
	}

	@available(*, unavailable, renamed: "makeIterator()")
	public func generate() -> LazyFilterIterator<Base.Iterator> {
	Builtin.unreachable()
	}
	}

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