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 - 2017 Apple Inc. and the Swift project authors
 // Licensed under Apache License v2.0 with Runtime Library Exception
 //
 // See https://swift.org/LICENSE.txt for license information
 // See https://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.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.Element) -> Bool
 }

 /// The `Index` used for subscripting a `LazyFilterCollection`.
 @available(swift, deprecated: 3.1, obsoleted: 4.0, message: "Use Base.Index")
 public typealias LazyFilterIndex<Base : Collection> = Base.Index

 // FIXME(ABI)#27 (Conditional Conformance): `LazyFilter*Collection` types should be
 // collapsed into one `LazyFilterCollection` using conditional conformances.
 // Maybe even combined with `LazyFilterSequence`.
 // rdar://problem/17144340

 % 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 an index 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 = Base.Index

   public typealias IndexDistance = Base.IndexDistance

   /// Creates an instance containing the elements of `base` that
   /// satisfy `isIncluded`.
   public // @testable
   init(
     _base: Base,
     _ isIncluded: @escaping (Base.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 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 _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
     _precondition(index != _base.endIndex, "Can't advance past endIndex")
     repeat {
       _base.formIndex(after: &index)
     } while index != _base.endIndex && !_predicate(_base[index])
     i = 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
     _precondition(index != _base.startIndex, "Can't retreat before startIndex")
     repeat {
       _base.formIndex(before: &index)
     } while !_predicate(_base[index])
     i = index
   }
 %   end

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

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

   // Any estimate of the number of elements that pass `_predicate` requires
   // iterating the collection and evaluating each element, which can be costly,
   // is unexpected, and usually doesn't pay for itself in saving time through
   // preventing intermediate reallocations. (SR-4164)
   public var underestimatedCount: Int { return 0 }

   public func _copyToContiguousArray()
     -> ContiguousArray<Base.Iterator.Element> {

     // The default implementation of `_copyToContiguousArray` queries the
     // `count` property, which evaluates `_predicate` for every element --
     // see the note above `underestimatedCount`. Here we treat `self` as a
     // sequence and only rely on underestimated count.
     return _copySequenceToContiguousArray(self)
   }

   // FIXME(ABI)#28 (Associated Types with where clauses): 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.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.Element) -> Bool
   ) -> LazyFilterSequence<Self.Elements> {
     return LazyFilterSequence(
       _base: self.elements, isIncluded)
   }
 }

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

 extension LazyCollectionProtocol
 %   if Traversal != 'Forward':
   where
   Self : ${collectionForTraversal(Traversal)},
   Elements : ${collectionForTraversal(Traversal)}
 %   end
 {
   /// 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.Element) -> Bool
   ) -> LazyFilter${collectionForTraversal(Traversal)}<Self.Elements> {
     return LazyFilter${collectionForTraversal(Traversal)}(
       _base: self.elements, isIncluded)
   }
 }

 % end

 // ${'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 - 2017 Apple Inc. and the Swift project authors
	// Licensed under Apache License v2.0 with Runtime Library Exception
	//
	// See https://swift.org/LICENSE.txt for license information
	// See https://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.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.Element) -> Bool
	}

	/// The `Index` used for subscripting a `LazyFilterCollection`.
	@available(swift, deprecated: 3.1, obsoleted: 4.0, message: "Use Base.Index")
	public typealias LazyFilterIndex<Base : Collection> = Base.Index

	// FIXME(ABI)#27 (Conditional Conformance): `LazyFilter*Collection` types should be
	// collapsed into one `LazyFilterCollection` using conditional conformances.
	// Maybe even combined with `LazyFilterSequence`.
	// rdar://problem/17144340

	% 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 an index 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 = Base.Index

	public typealias IndexDistance = Base.IndexDistance

	/// Creates an instance containing the elements of `base` that
	/// satisfy `isIncluded`.
	public // @testable
	init(
	_base: Base,
	_ isIncluded: @escaping (Base.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 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 _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
	_precondition(index != _base.endIndex, "Can't advance past endIndex")
	repeat {
	_base.formIndex(after: &index)
	} while index != _base.endIndex && !_predicate(_base[index])
	i = 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
	_precondition(index != _base.startIndex, "Can't retreat before startIndex")
	repeat {
	_base.formIndex(before: &index)
	} while !_predicate(_base[index])
	i = index
	}
	% end

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

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

	// Any estimate of the number of elements that pass `_predicate` requires
	// iterating the collection and evaluating each element, which can be costly,
	// is unexpected, and usually doesn't pay for itself in saving time through
	// preventing intermediate reallocations. (SR-4164)
	public var underestimatedCount: Int { return 0 }

	public func _copyToContiguousArray()
	-> ContiguousArray<Base.Iterator.Element> {

	// The default implementation of `_copyToContiguousArray` queries the
	// `count` property, which evaluates `_predicate` for every element --
	// see the note above `underestimatedCount`. Here we treat `self` as a
	// sequence and only rely on underestimated count.
	return _copySequenceToContiguousArray(self)
	}

	// FIXME(ABI)#28 (Associated Types with where clauses): 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.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.Element) -> Bool
	) -> LazyFilterSequence<Self.Elements> {
	return LazyFilterSequence(
	_base: self.elements, isIncluded)
	}
	}

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

	extension LazyCollectionProtocol
	% if Traversal != 'Forward':
	where
	Self : ${collectionForTraversal(Traversal)},
	Elements : ${collectionForTraversal(Traversal)}
	% end
	{
	/// 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.Element) -> Bool
	) -> LazyFilter${collectionForTraversal(Traversal)}<Self.Elements> {
	return LazyFilter${collectionForTraversal(Traversal)}(
	_base: self.elements, isIncluded)
	}
	}

	% end

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