← Back to branch summary

~ubuntu-branches/debian/sid/scala/sid

« back to all changes in this revision

Viewing changes to src/library/scala/collection/immutable/Stream.scala

  • Committer: Package Import Robot
  • Author(s): Emmanuel Bourg, Mehdi Dogguy, Lucas Satabin, Frank S. Thomas, Emmanuel Bourg
  • Date: 2015-06-05 23:52:59 UTC
  • mfrom: (1.2.11)
  • Revision ID: package-import@ubuntu.com-20150605235259-wk00vgk83dh8o19g
Tags: 2.10.5-1
http://bugs.debian.org/744278
http://bugs.debian.org/754935
http://bugs.debian.org/724704
* Team upload.

[ Mehdi Dogguy ]
* New upstream release (Closes: #744278).

[ Lucas Satabin ]
* Update patches
* Update the clean target
* Update paths of elements to install
* Update watch file

[ Frank S. Thomas ]
* Remove myself from Uploaders.

[ Emmanuel Bourg ]
* The package has been adopted by the Java Team (Closes: #754935)
* Patched the build to avoid downloading libraries from the Internet
* Replaced the minified JavaScript files with unobfuscated ones
* No longer build scala-partest.jar until diffutils is packaged or replaced
* debian/watch: Fixed the versions matched (x.y.z instead of x.y.z..z)
* debian/rules:
  - Added the missing get-orig-source target (Closes: #724704)
  - Improved the clean target
* debian/control:
  - Build depend on scala (>= 2.10) and bnd
  - Use canonical URLs for the Vcs-* fields
  - Standards-Version updated to 3.9.6 (no changes)
* Switch to debhelper level 9

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/library/scala/collection/immutable/Stream.scala
1
1
/*                     __                                               *\
2
2
**     ________ ___   / /  ___     Scala API                            **
3
 
**    / __/ __// _ | / /  / _ |    (c) 2003-2011, LAMP/EPFL             **
 
3
**    / __/ __// _ | / /  / _ |    (c) 2003-2013, LAMP/EPFL             **
4
4
**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
5
5
** /____/\___/_/ |_/____/_/ | |                                         **
6
6
**                          |/                                          **
7
7
\*                                                                      */
8
8
 
9
 
 
10
 
 
11
9
package scala.collection
12
10
package immutable
13
11
 
15
13
import mutable.{Builder, StringBuilder, LazyBuilder, ListBuffer}
16
14
import scala.annotation.tailrec
17
15
import Stream.cons
 
16
import scala.language.implicitConversions
18
17
 
19
18
/** The class `Stream` implements lazy lists where elements
20
19
 *  are only evaluated when they are needed. Here is an example:
138
137
 *  val it3 = new Iterator[Int] {
139
138
 *    var i = -1
140
139
 *    def hasNext = true
141
 
 *    def next: Int = { i += 1; i }
 
140
 *    def next(): Int = { i += 1; i }
142
141
 *  }
143
142
 *  loop("Iterator3: ", it3.next, it3)
144
143
 *  }}}
178
177
 *  section on `Streams` for more information.
179
178
 
180
179
 *  @define naturalsEx def naturalsFrom(i: Int): Stream[Int] = i #:: naturalsFrom(i + 1)
181
 
 *  @define Coll Stream
 
180
 *  @define Coll `Stream`
182
181
 *  @define coll stream
183
182
 *  @define orderDependent
184
183
 *  @define orderDependentFold
185
184
 */
186
 
abstract class Stream[+A] extends LinearSeq[A]
 
185
abstract class Stream[+A] extends AbstractSeq[A]
 
186
                             with LinearSeq[A]
187
187
                             with GenericTraversableTemplate[A, Stream]
188
188
                             with LinearSeqOptimized[A, Stream[A]] {
189
189
self =>
422
422
   * // produces: 10, 10, 11, 10, 11, 11, 10, 11, 11, 12, 10, 11, 11, 12, 13
423
423
   * }}}
424
424
   *
 
425
   * ''Note:''  Currently `flatMap` will evaluate as much of the Stream as needed
 
426
   * until it finds a non-empty element for the head, which is non-lazy.
 
427
   *
425
428
   * @tparam B The element type of the returned collection '''That'''.
426
429
   * @param f  the function to apply on each element.
427
430
   * @return  `f(a,,0,,) ::: ... ::: f(a,,n,,)` if
479
482
  final class StreamWithFilter(p: A => Boolean) extends WithFilter(p) {
480
483
 
481
484
    override def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Stream[A], B, That]): That = {
482
 
      def tailMap = asStream[B](tail withFilter p map f)
483
 
      if (isStreamBuilder(bf)) asThat(
484
 
        if (isEmpty) Stream.Empty
485
 
        else if (p(head)) cons(f(head), tailMap)
486
 
        else tailMap
487
 
      )
 
485
      def tailMap(coll: Stream[A]): Stream[B] = {
 
486
        var head: A = null.asInstanceOf[A]
 
487
        var tail: Stream[A] = coll
 
488
        while (true) {
 
489
          if (tail.isEmpty)
 
490
            return Stream.Empty
 
491
          head = tail.head
 
492
          tail = tail.tail
 
493
          if (p(head))
 
494
            return cons(f(head), tailMap(tail))
 
495
        }
 
496
        throw new RuntimeException()
 
497
      }
 
498
 
 
499
      if (isStreamBuilder(bf)) asThat(tailMap(Stream.this))
488
500
      else super.map(f)(bf)
489
501
    }
490
502
 
491
503
    override def flatMap[B, That](f: A => GenTraversableOnce[B])(implicit bf: CanBuildFrom[Stream[A], B, That]): That = {
492
 
      def tailFlatMap = asStream[B](tail withFilter p flatMap f)
493
 
      if (isStreamBuilder(bf)) asThat(
494
 
        if (isEmpty) Stream.Empty
495
 
        else if (p(head)) f(head).toStream append tailFlatMap
496
 
        else tailFlatMap
497
 
      )
 
504
      def tailFlatMap(coll: Stream[A]): Stream[B] = {
 
505
        var head: A = null.asInstanceOf[A]
 
506
        var tail: Stream[A] = coll
 
507
        while (true) {
 
508
          if (tail.isEmpty)
 
509
            return Stream.Empty
 
510
          head = tail.head
 
511
          tail = tail.tail
 
512
          if (p(head))
 
513
            return f(head).toStream append tailFlatMap(tail)
 
514
        }
 
515
        throw new RuntimeException()
 
516
      }
 
517
 
 
518
      if (isStreamBuilder(bf)) asThat(tailFlatMap(Stream.this))
498
519
      else super.flatMap(f)(bf)
499
520
    }
500
521
 
604
625
   *
605
626
   * @example {{{
606
627
   * $naturalsEx
607
 
   * naturalsFrom(1) zip naturalsFrom(2) zip take 5 foreach println
 
628
   * naturalsFrom(1) zip naturalsFrom(2) take 5 foreach println
608
629
   * // prints
609
630
   * // (1,2)
610
631
   * // (2,3)
613
634
   * // (5,6)
614
635
   * }}}
615
636
   */
616
 
  override final def zip[A1 >: A, B, That](that: collection.GenIterable[B])(implicit bf: CanBuildFrom[Stream[A], (A1, B), That]): That =
 
637
  override final def zip[A1 >: A, B, That](that: scala.collection.GenIterable[B])(implicit bf: CanBuildFrom[Stream[A], (A1, B), That]): That =
617
638
    // we assume there is no other builder factory on streams and therefore know that That = Stream[(A1, B)]
618
639
    if (isStreamBuilder(bf)) asThat(
619
640
      if (this.isEmpty || that.isEmpty) Stream.Empty
716
737
  /** A substream starting at index `from` and extending up to (but not including)
717
738
   *  index `until`.  This returns a `Stream` that is lazily evaluated.
718
739
   *
719
 
   * @param start   The index of the first element of the returned subsequence
720
 
   * @param end     The index of the element following the returned subsequence
 
740
   * @param from    The index of the first element of the returned subsequence
 
741
   * @param until   The index of the element following the returned subsequence
721
742
   * @return A new string containing the elements requested from `start` until
722
743
   * `end`.
723
744
   *
774
795
   * `p`.
775
796
   *
776
797
   * @example {{{
777
 
   * naturalsFrom(0) takeWhile { _ < 5 } mkString ", "
 
798
   + naturalsFrom(0) takeWhile { _ < 5 } mkString ", "
778
799
   * produces: "0, 1, 2, 3, 4"
779
800
   * }}}
780
801
   */
805
826
    these
806
827
  }
807
828
 
808
 
  /** Builds a new stream from this stream in which any duplicates (wrt to ==)
809
 
   * have been removed.  Among duplicate elements, only the first one is
810
 
   * retained in the resulting `Stream`.
 
829
  /** Builds a new stream from this stream in which any duplicates (as
 
830
   * determined by `==`) have been removed. Among duplicate elements, only the
 
831
   * first one is retained in the resulting `Stream`.
811
832
   *
812
833
   * @return A new `Stream` representing the result of applying distinctness to
813
834
   * the original `Stream`.
820
841
   * // produces: "1, 2, 3, 4, 5, 6"
821
842
   * }}}
822
843
   */
823
 
  override def distinct: Stream[A] =
824
 
    if (isEmpty) this
825
 
    else cons(head, tail.filter(head !=).distinct)
 
844
  override def distinct: Stream[A] = {
 
845
    // This should use max memory proportional to N, whereas
 
846
    // recursively calling distinct on the tail is N^2.
 
847
    def loop(seen: Set[A], rest: Stream[A]): Stream[A] = {
 
848
      if (rest.isEmpty) rest
 
849
      else if (seen(rest.head)) loop(seen, rest.tail)
 
850
      else cons(rest.head, loop(seen + rest.head, rest.tail))
 
851
    }
 
852
    loop(Set(), this)
 
853
  }
826
854
 
827
855
  /** Returns a new sequence of given length containing the elements of this
828
856
   * sequence followed by zero or more occurrences of given elements.
903
931
   * // produces: "0, 0, 0, 0, 0, 0, 0, 0, 0, 0"
904
932
   * }}}
905
933
   */
906
 
  override def flatten[B](implicit asTraversable: A => /*<:<!!!*/ TraversableOnce[B]): Stream[B] = {
 
934
  override def flatten[B](implicit asTraversable: A => /*<:<!!!*/ GenTraversableOnce[B]): Stream[B] = {
907
935
    def flatten1(t: Traversable[B]): Stream[B] =
908
936
      if (!t.isEmpty)
909
937
        cons(t.head, flatten1(t.tail))
911
939
        tail.flatten
912
940
 
913
941
    if (isEmpty) Stream.empty
914
 
    else flatten1(asTraversable(head).toTraversable)
 
942
    else flatten1(asTraversable(head).seq.toTraversable)
915
943
  }
916
944
 
917
945
  override def view = new StreamView[A, Stream[A]] {
930
958
/** A specialized, extra-lazy implementation of a stream iterator, so it can
931
959
 *  iterate as lazily as it traverses the tail.
932
960
 */
933
 
final class StreamIterator[+A] private() extends Iterator[A] {
 
961
final class StreamIterator[+A] private() extends AbstractIterator[A] with Iterator[A] {
934
962
  def this(self: Stream[A]) {
935
963
    this()
936
964
    these = new LazyCell(self)
944
972
  private var these: LazyCell = _
945
973
 
946
974
  def hasNext: Boolean = these.v.nonEmpty
947
 
  def next: A =
 
975
  def next(): A =
948
976
    if (isEmpty) Iterator.empty.next
949
977
    else {
950
978
      val cur    = these.v
995
1023
    def result: Stream[A] = parts.toStream flatMap (_.toStream)
996
1024
  }
997
1025
 
998
 
  object Empty extends Stream[Nothing] {
 
1026
  object Empty extends Stream[Nothing] with Serializable {
999
1027
    override def isEmpty = true
1000
1028
    override def head = throw new NoSuchElementException("head of empty stream")
1001
1029
    override def tail = throw new UnsupportedOperationException("tail of empty stream")
1030
1058
      else Some((xs.head, xs.tail))
1031
1059
  }
1032
1060
 
1033
 
  @deprecated("use #:: instead", "2.8.0")
1034
 
  lazy val lazy_:: = #::
1035
 
 
1036
1061
  /** An alternative way of building and matching Streams using Stream.cons(hd, tl).
1037
1062
   */
1038
1063
  object cons {
1127
1152
  private[immutable] def collectedTail[A, B, That](stream: Stream[A], pf: PartialFunction[A, B], bf: CanBuildFrom[Stream[A], B, That]) = {
1128
1153
    cons(pf(stream.head), stream.tail.collect(pf)(bf).asInstanceOf[Stream[B]])
1129
1154
  }
1130
 
 
1131
 
  /** A stream containing all elements of a given iterator, in the order they are produced.
1132
 
   *  @param it   The iterator producing the stream's elements
1133
 
   */
1134
 
  @deprecated("use it.toStream instead", "2.8.0")
1135
 
  def fromIterator[A](it: Iterator[A]): Stream[A] = it.toStream
1136
 
 
1137
 
  /** The concatenation of a sequence of streams
1138
 
   */
1139
 
  @deprecated("use xs.flatten instead", "2.8.0")
1140
 
  def concat[A](xs: Iterable[Stream[A]]): Stream[A] = concat(xs.iterator)
1141
 
 
1142
 
  /** The concatenation of all streams returned by an iterator
1143
 
   */
1144
 
  @deprecated("use xs.toStream.flatten instead", "2.8.0")
1145
 
  def concat[A](xs: Iterator[Stream[A]]): Stream[A] = xs.toStream.flatten //(conforms[Stream[A], scala.collection.Traversable[A]])
1146
 
 
1147
 
  /**
1148
 
   * Create a stream with element values
1149
 
   * <code>v<sub>n+1</sub> = step(v<sub>n</sub>)</code>
1150
 
   * where <code>v<sub>0</sub> = start</code>
1151
 
   * and elements are in the range between <code>start</code> (inclusive)
1152
 
   * and <code>end</code> (exclusive)
1153
 
   * @param start the start value of the stream
1154
 
   * @param end the end value of the stream
1155
 
   * @param step the increment function of the stream, must be monotonically increasing or decreasing
1156
 
   * @return the stream starting at value <code>start</code>.
1157
 
   */
1158
 
  @deprecated("use `iterate' instead.", "2.8.0")
1159
 
  def range(start: Int, end: Int, step: Int => Int): Stream[Int] =
1160
 
    iterate(start, end - start)(step)
1161
 
 
1162
 
  /**
1163
 
   * Create an infinite stream containing the given element.
1164
 
   *
1165
 
   * @param elem the element composing the resulting stream
1166
 
   * @return the stream containing an infinite number of elem
1167
 
   */
1168
 
  @deprecated("use `continually' instead", "2.8.0")
1169
 
  def const[A](elem: A): Stream[A] = cons(elem, const(elem))
1170
 
 
1171
 
  /** Create a stream containing several copies of an element.
1172
 
   *
1173
 
   *  @param n    the length of the resulting stream
1174
 
   *  @param elem the element composing the resulting stream
1175
 
   *  @return     the stream composed of n elements all equal to elem
1176
 
   */
1177
 
  @deprecated("use fill(n, elem) instead", "2.8.0")
1178
 
  def make[A](n: Int, elem: A): Stream[A] = fill(n)(elem)
1179
1155
}
1180
1156
 
1181
1157