stdlib/public/core/LazySequence.swift - third_party/swift - Git at Google

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

 /// A sequence on which normally-eager operations such as `map` and
 /// `filter` are implemented lazily.
 ///
 /// Lazy sequences can be used to avoid needless storage allocation
 /// and computation, because they use an underlying sequence for
 /// storage and compute their elements on demand.  For example,
 ///
 ///     [1, 2, 3].lazy.map { $0 * 2 }
 ///
 /// is a sequence containing { `2`, `4`, `6` }.  Each time an element
 /// of the lazy sequence is accessed, an element of the underlying
 /// array is accessed and transformed by the closure.
 ///
 /// Sequence operations taking closure arguments, such as `map` and
 /// `filter`, are normally eager: they use the closure immediately and
 /// return a new array.  Using the `lazy` property gives the standard
 /// library explicit permission to store the closure and the sequence
 /// in the result, and defer computation until it is needed.
 ///
 /// To add new lazy sequence operations, extend this protocol with
 /// methods that return lazy wrappers that are themselves
 /// `LazySequenceProtocol`s.  For example, given an eager `scan`
 /// method defined as follows
 ///
 ///     extension Sequence {
 ///       /// Returns an array containing the results of
 ///       ///
 ///       ///   p.reduce(initial, nextPartialResult)
 ///       ///
 ///       /// for each prefix `p` of `self`, in order from shortest to
 ///       /// longest.  For example:
 ///       ///
 ///       ///     (1..<6).scan(0, +) // [0, 1, 3, 6, 10, 15]
 ///       ///
 ///       /// - Complexity: O(n)
 ///       func scan<ResultElement>(
 ///         _ initial: ResultElement,
 ///         _ nextPartialResult: (ResultElement, Element) -> ResultElement
 ///       ) -> [ResultElement] {
 ///         var result = [initial]
 ///         for x in self {
 ///           result.append(nextPartialResult(result.last!, x))
 ///         }
 ///         return result
 ///       }
 ///     }
 ///
 /// we can build a sequence that lazily computes the elements in the
 /// result of `scan`:
 ///
 ///     struct LazyScanIterator<Base : IteratorProtocol, ResultElement>
 ///       : IteratorProtocol {
 ///       mutating func next() -> ResultElement? {
 ///         return nextElement.map { result in
 ///           nextElement = base.next().map { nextPartialResult(result, $0) }
 ///           return result
 ///         }
 ///       }
 ///       private var nextElement: ResultElement? // The next result of next().
 ///       private var base: Base                  // The underlying iterator.
 ///       private let nextPartialResult: (ResultElement, Base.Element) -> ResultElement
 ///     }
 ///
 ///     struct LazyScanSequence<Base: Sequence, ResultElement>
 ///       : LazySequenceProtocol // Chained operations on self are lazy, too
 ///     {
 ///       func makeIterator() -> LazyScanIterator<Base.Iterator, ResultElement> {
 ///         return LazyScanIterator(
 ///           nextElement: initial, base: base.makeIterator(), nextPartialResult)
 ///       }
 ///       private let initial: ResultElement
 ///       private let base: Base
 ///       private let nextPartialResult:
 ///         (ResultElement, Base.Element) -> ResultElement
 ///     }
 ///
 /// and finally, we can give all lazy sequences a lazy `scan` method:
 ///
 ///     extension LazySequenceProtocol {
 ///       /// Returns a sequence containing the results of
 ///       ///
 ///       ///   p.reduce(initial, nextPartialResult)
 ///       ///
 ///       /// for each prefix `p` of `self`, in order from shortest to
 ///       /// longest.  For example:
 ///       ///
 ///       ///     Array((1..<6).lazy.scan(0, +)) // [0, 1, 3, 6, 10, 15]
 ///       ///
 ///       /// - Complexity: O(1)
 ///       func scan<ResultElement>(
 ///         _ initial: ResultElement,
 ///         _ nextPartialResult: (ResultElement, Element) -> ResultElement
 ///       ) -> LazyScanSequence<Self, ResultElement> {
 ///         return LazyScanSequence(
 ///           initial: initial, base: self, nextPartialResult)
 ///       }
 ///     }
 ///
 /// - See also: `LazySequence`
 ///
 /// - Note: The explicit permission to implement further operations
 ///   lazily applies only in contexts where the sequence is statically
 ///   known to conform to `LazySequenceProtocol`.  Thus, side-effects such
 ///   as the accumulation of `result` below are never unexpectedly
 ///   dropped or deferred:
 ///
 ///       extension Sequence where Element == Int {
 ///         func sum() -> Int {
 ///           var result = 0
 ///           _ = self.map { result += $0 }
 ///           return result
 ///         }
 ///       }
 ///
 ///   [We don't recommend that you use `map` this way, because it
 ///   creates and discards an array. `sum` would be better implemented
 ///   using `reduce`].
 public protocol LazySequenceProtocol : Sequence {
   /// A `Sequence` that can contain the same elements as this one,
   /// possibly with a simpler type.
   ///
   /// - See also: `elements`
   associatedtype Elements: Sequence = Self where Elements.Element == Element

   /// A sequence containing the same elements as this one, possibly with
   /// a simpler type.
   ///
   /// When implementing lazy operations, wrapping `elements` instead
   /// of `self` can prevent result types from growing an extra
   /// `LazySequence` layer.  For example,
   ///
   /// _prext_ example needed
   ///
   /// Note: this property need not be implemented by conforming types,
   /// it has a default implementation in a protocol extension that
   /// just returns `self`.
   var elements: Elements { get }
 }

 /// When there's no special associated `Elements` type, the `elements`
 /// property is provided.
 extension LazySequenceProtocol where Elements == Self {
   /// Identical to `self`.
   @inlinable // protocol-only
   public var elements: Self { return self }
 }

 extension LazySequenceProtocol {
   @inlinable // protocol-only
   public var lazy: LazySequence<Elements> {
     return elements.lazy
   }
 }

 extension LazySequenceProtocol where Elements: LazySequenceProtocol {
   @inlinable // protocol-only
   public var lazy: Elements {
     return elements
   }
 }

 /// A sequence containing the same elements as a `Base` sequence, but
 /// on which some operations such as `map` and `filter` are
 /// implemented lazily.
 ///
 /// - See also: `LazySequenceProtocol`
 @_fixed_layout // lazy-performance
 public struct LazySequence<Base : Sequence> {
   @usableFromInline
   internal var _base: Base

   /// Creates a sequence that has the same elements as `base`, but on
   /// which some operations such as `map` and `filter` are implemented
   /// lazily.
   @inlinable // lazy-performance
   internal init(_base: Base) {
     self._base = _base
   }
 }

 extension LazySequence: Sequence {
   public typealias Element = Base.Element
   public typealias Iterator = Base.Iterator

   @inlinable
   public __consuming func makeIterator() -> Iterator {
     return _base.makeIterator()
   }

   @inlinable // lazy-performance
   public var underestimatedCount: Int {
     return _base.underestimatedCount
   }

   @inlinable // lazy-performance
   @discardableResult
   public __consuming func _copyContents(
     initializing buf: UnsafeMutableBufferPointer<Element>
   ) -> (Iterator, UnsafeMutableBufferPointer<Element>.Index) {
     return _base._copyContents(initializing: buf)
   }

   @inlinable // lazy-performance
   public func _customContainsEquatableElement(_ element: Element) -> Bool? {
     return _base._customContainsEquatableElement(element)
   }

   @inlinable // generic-performance
   public __consuming func _copyToContiguousArray() -> ContiguousArray<Element> {
     return _base._copyToContiguousArray()
   }
 }

 extension LazySequence: LazySequenceProtocol {
   public typealias Elements = Base

   /// The `Base` (presumably non-lazy) sequence from which `self` was created.
   @inlinable // lazy-performance
   public var elements: Elements { return _base }
 }

 extension Sequence {
   /// A sequence containing the same elements as this sequence,
   /// but on which some operations, such as `map` and `filter`, are
   /// implemented lazily.
   @inlinable // protocol-only
   public var lazy: LazySequence<Self> {
     return LazySequence(_base: self)
   }
 }
	//===--- LazySequence.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
	//
	//===----------------------------------------------------------------------===//

	/// A sequence on which normally-eager operations such as `map` and
	/// `filter` are implemented lazily.
	///
	/// Lazy sequences can be used to avoid needless storage allocation
	/// and computation, because they use an underlying sequence for
	/// storage and compute their elements on demand. For example,
	///
	/// [1, 2, 3].lazy.map { $0 * 2 }
	///
	/// is a sequence containing { `2`, `4`, `6` }. Each time an element
	/// of the lazy sequence is accessed, an element of the underlying
	/// array is accessed and transformed by the closure.
	///
	/// Sequence operations taking closure arguments, such as `map` and
	/// `filter`, are normally eager: they use the closure immediately and
	/// return a new array. Using the `lazy` property gives the standard
	/// library explicit permission to store the closure and the sequence
	/// in the result, and defer computation until it is needed.
	///
	/// To add new lazy sequence operations, extend this protocol with
	/// methods that return lazy wrappers that are themselves
	/// `LazySequenceProtocol`s. For example, given an eager `scan`
	/// method defined as follows
	///
	/// extension Sequence {
	/// /// Returns an array containing the results of
	/// ///
	/// /// p.reduce(initial, nextPartialResult)
	/// ///
	/// /// for each prefix `p` of `self`, in order from shortest to
	/// /// longest. For example:
	/// ///
	/// /// (1..<6).scan(0, +) // [0, 1, 3, 6, 10, 15]
	/// ///
	/// /// - Complexity: O(n)
	/// func scan<ResultElement>(
	/// _ initial: ResultElement,
	/// _ nextPartialResult: (ResultElement, Element) -> ResultElement
	/// ) -> [ResultElement] {
	/// var result = [initial]
	/// for x in self {
	/// result.append(nextPartialResult(result.last!, x))
	/// }
	/// return result
	/// }
	/// }
	///
	/// we can build a sequence that lazily computes the elements in the
	/// result of `scan`:
	///
	/// struct LazyScanIterator<Base : IteratorProtocol, ResultElement>
	/// : IteratorProtocol {
	/// mutating func next() -> ResultElement? {
	/// return nextElement.map { result in
	/// nextElement = base.next().map { nextPartialResult(result, $0) }
	/// return result
	/// }
	/// }
	/// private var nextElement: ResultElement? // The next result of next().
	/// private var base: Base // The underlying iterator.
	/// private let nextPartialResult: (ResultElement, Base.Element) -> ResultElement
	/// }
	///
	/// struct LazyScanSequence<Base: Sequence, ResultElement>
	/// : LazySequenceProtocol // Chained operations on self are lazy, too
	/// {
	/// func makeIterator() -> LazyScanIterator<Base.Iterator, ResultElement> {
	/// return LazyScanIterator(
	/// nextElement: initial, base: base.makeIterator(), nextPartialResult)
	/// }
	/// private let initial: ResultElement
	/// private let base: Base
	/// private let nextPartialResult:
	/// (ResultElement, Base.Element) -> ResultElement
	/// }
	///
	/// and finally, we can give all lazy sequences a lazy `scan` method:
	///
	/// extension LazySequenceProtocol {
	/// /// Returns a sequence containing the results of
	/// ///
	/// /// p.reduce(initial, nextPartialResult)
	/// ///
	/// /// for each prefix `p` of `self`, in order from shortest to
	/// /// longest. For example:
	/// ///
	/// /// Array((1..<6).lazy.scan(0, +)) // [0, 1, 3, 6, 10, 15]
	/// ///
	/// /// - Complexity: O(1)
	/// func scan<ResultElement>(
	/// _ initial: ResultElement,
	/// _ nextPartialResult: (ResultElement, Element) -> ResultElement
	/// ) -> LazyScanSequence<Self, ResultElement> {
	/// return LazyScanSequence(
	/// initial: initial, base: self, nextPartialResult)
	/// }
	/// }
	///
	/// - See also: `LazySequence`
	///
	/// - Note: The explicit permission to implement further operations
	/// lazily applies only in contexts where the sequence is statically
	/// known to conform to `LazySequenceProtocol`. Thus, side-effects such
	/// as the accumulation of `result` below are never unexpectedly
	/// dropped or deferred:
	///
	/// extension Sequence where Element == Int {
	/// func sum() -> Int {
	/// var result = 0
	/// _ = self.map { result += $0 }
	/// return result
	/// }
	/// }
	///
	/// [We don't recommend that you use `map` this way, because it
	/// creates and discards an array. `sum` would be better implemented
	/// using `reduce`].
	public protocol LazySequenceProtocol : Sequence {
	/// A `Sequence` that can contain the same elements as this one,
	/// possibly with a simpler type.
	///
	/// - See also: `elements`
	associatedtype Elements: Sequence = Self where Elements.Element == Element

	/// A sequence containing the same elements as this one, possibly with
	/// a simpler type.
	///
	/// When implementing lazy operations, wrapping `elements` instead
	/// of `self` can prevent result types from growing an extra
	/// `LazySequence` layer. For example,
	///
	/// _prext_ example needed
	///
	/// Note: this property need not be implemented by conforming types,
	/// it has a default implementation in a protocol extension that
	/// just returns `self`.
	var elements: Elements { get }
	}

	/// When there's no special associated `Elements` type, the `elements`
	/// property is provided.
	extension LazySequenceProtocol where Elements == Self {
	/// Identical to `self`.
	@inlinable // protocol-only
	public var elements: Self { return self }
	}

	extension LazySequenceProtocol {
	@inlinable // protocol-only
	public var lazy: LazySequence<Elements> {
	return elements.lazy
	}
	}

	extension LazySequenceProtocol where Elements: LazySequenceProtocol {
	@inlinable // protocol-only
	public var lazy: Elements {
	return elements
	}
	}

	/// A sequence containing the same elements as a `Base` sequence, but
	/// on which some operations such as `map` and `filter` are
	/// implemented lazily.
	///
	/// - See also: `LazySequenceProtocol`
	@_fixed_layout // lazy-performance
	public struct LazySequence<Base : Sequence> {
	@usableFromInline
	internal var _base: Base

	/// Creates a sequence that has the same elements as `base`, but on
	/// which some operations such as `map` and `filter` are implemented
	/// lazily.
	@inlinable // lazy-performance
	internal init(_base: Base) {
	self._base = _base
	}
	}

	extension LazySequence: Sequence {
	public typealias Element = Base.Element
	public typealias Iterator = Base.Iterator

	@inlinable
	public __consuming func makeIterator() -> Iterator {
	return _base.makeIterator()
	}

	@inlinable // lazy-performance
	public var underestimatedCount: Int {
	return _base.underestimatedCount
	}

	@inlinable // lazy-performance
	@discardableResult
	public __consuming func _copyContents(
	initializing buf: UnsafeMutableBufferPointer<Element>
	) -> (Iterator, UnsafeMutableBufferPointer<Element>.Index) {
	return _base._copyContents(initializing: buf)
	}

	@inlinable // lazy-performance
	public func _customContainsEquatableElement(_ element: Element) -> Bool? {
	return _base._customContainsEquatableElement(element)
	}

	@inlinable // generic-performance
	public __consuming func _copyToContiguousArray() -> ContiguousArray<Element> {
	return _base._copyToContiguousArray()
	}
	}

	extension LazySequence: LazySequenceProtocol {
	public typealias Elements = Base

	/// The `Base` (presumably non-lazy) sequence from which `self` was created.
	@inlinable // lazy-performance
	public var elements: Elements { return _base }
	}

	extension Sequence {
	/// A sequence containing the same elements as this sequence,
	/// but on which some operations, such as `map` and `filter`, are
	/// implemented lazily.
	@inlinable // protocol-only
	public var lazy: LazySequence<Self> {
	return LazySequence(_base: self)
	}
	}