1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
|
/* __ *\
** ________ ___ / / ___ Scala API **
** / __/ __// _ | / / / _ | (c) 2003-2009, LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
// $Id: Stream.scala 16287 2008-10-18 13:41:36Z nielsen $
package scalax.collection.immutable
import mutable.ListBuffer
import generic.{SequenceTemplate, SequenceFactory, EmptyIterableFactory, Builder, LazyBuilder}
import annotation.unchecked.uncheckedVariance
/**
* The object <code>Stream</code> provides helper functions
* to manipulate streams.
*
* @author Martin Odersky, Matthias Zenger
* @version 1.1 08/08/03
*/
object Stream extends SequenceFactory[Stream] with EmptyIterableFactory[Stream] {
import collection.{Iterable, OrderedIterable, Sequence, Vector}
override val empty: Stream[Nothing] = Nil
override def apply[A](xs: A*) = xs.asInstanceOf[Iterable[A]].toList // !@!
override def newBuilder[B]: Builder[Stream, B] = new ListBuffer[B]
class ConsWrapper[A](tl: => Stream[A]) {
def #::(hd: A): Stream[A] = new Cons(hd, tl)
def #:::(prefix: Stream[A]): Stream[A] = prefix append tl
}
implicit def consWrapper[A](stream: => Stream[A]): ConsWrapper[A] =
new ConsWrapper[A](stream)
object #:: {
def unapply[A](xs: Stream[A]): Option[(A, Stream[A])] =
if (xs.isEmpty) None
else Some(xs.head, xs.tail)
}
/** @deprecated use #:: instead */
@deprecated lazy val lazy_:: = #::
/** An alternative way of building and matching Streams using Stream.cons(hd, tl).
*/
object cons {
/** A stream consisting of a given first element and remaining elements
* @param hd The first element of the result stream
* @param tl The remaining elements of the result stream
*/
def apply[A](hd: A, tl: => Stream[A]) = new Cons(hd, tl)
/** Maps a stream to its head and tail */
def unapply[A](xs: Stream[A]): Option[(A, Stream[A])] = #::.unapply(xs)
}
final class Cons[+A](hd: A, tl: => Stream[A]) extends Stream[A] {
override def isEmpty = false
override def head = hd
private[this] var tlVal: Stream[A] = _
private def tlDefined = tlVal ne null
override def tail: Stream[A] = {
if (!tlDefined) { tlVal = tl }
tlVal
}
override def hasDefiniteSize = tlDefined && tlVal.hasDefiniteSize
// Overridden methods from IterableTemplate or overloaded variants of such methods
/** Create a new stream which contains all elements of this stream
* followed by all elements of Iterable `that'
*/
override def ++[B >: A](that: Iterable[B]): Stream[B] = this append that
/** Create a new stream which contains all elements of this stream
* followed by all elements of Iterator `that'
*/
override def ++[B >: A](that: Iterator[B]): Stream[B] = this append that.toStream
/** Returns the stream resulting from applying the given function
* <code>f</code> to each element of this stream.
*
* @param f function to apply to each element.
* @return <code>f(a<sub>0</sub>), ..., f(a<sub>n</sub>)</code> if this
* sequence is <code>a<sub>0</sub>, ..., a<sub>n</sub></code>.
*/
override def map[B](f: A => B): Stream[B] =
new Cons(f(head), tail map f)
/** Applies the given function <code>f</code> to each element of
* this stream, then concatenates the results.
*
* @param f the function to apply on each element.
* @return <code>f(a<sub>0</sub>) ::: ... ::: f(a<sub>n</sub>)</code> if
* this stream is <code>[a<sub>0</sub>, ..., a<sub>n</sub>]</code>.
*/
override def flatMap[B](f: A => Iterable[B]): Stream[B] = {
// drops A's for which f yields an empty Iterable[B]
def loop(s: Stream[A]): Stream[B] =
if (s.isEmpty) Nil
else {
val i = f(s.head)
if (i.isEmpty) loop(s.tail)
else i.toStream append loop(s.tail)
}
loop(this)
}
/** Returns all the elements of this stream that satisfy the
* predicate <code>p</code>. The order of the elements is preserved.
*
* @param p the predicate used to filter the stream.
* @return the elements of this stream satisfying <code>p</code>.
*/
override def filter(p: A => Boolean): Stream[A] = {
// drops A's for which p yields false
def loop(s: Stream[A]): Stream[A] =
if (s.isEmpty) Nil
else {
val b = p(s.head)
if (!b) loop(s.tail)
else new Cons(s.head, tail filter p)
}
loop(this)
}
/** Returns all the elements of this stream that satisfy the
* predicate <code>p</code>. The order of the elements is preserved.
*
* @param p the predicate used to filter the stream.
* @return the elements of this stream satisfying <code>p</code>.
*/
override def partition(p: A => Boolean): (Stream[A], Stream[A]) = (filter(p(_)), remove(p(_)))
/** Returns a stream formed from this stream and the specified stream
* <code>that</code> by associating each element of the former with
* the element at the same position in the latter.
* If one of the two streams is longer than the other, its remaining elements are ignored.
*
* @return <code>Stream({a<sub>0</sub>,b<sub>0</sub>}, ...,
* {a<sub>min(m,n)</sub>,b<sub>min(m,n)</sub>)}</code> when
* <code>Stream(a<sub>0</sub>, ..., a<sub>m</sub>)
* zip Stream(b<sub>0</sub>, ..., b<sub>n</sub>)</code> is invoked.
*/
def zip[B](that: Stream[B]): Stream[(A, B)] =
if (that.isEmpty) empty
else new Cons((this.head, that.head), this.tail zip that.tail)
/** Returns a list formed from this list and the specified list
* <code>that</code> by associating each element of the former with
* the element at the same position in the latter.
*
* @param that list <code>that</code> may have a different length
* as the self list.
* @param thisElem element <code>thisElem</code> is used to fill up the
* resulting list if the self list is shorter than
* <code>that</code>
* @param thatElem element <code>thatElem</code> is used to fill up the
* resulting list if <code>that</code> is shorter than
* the self list
* @return <code>List((a<sub>0</sub>,b<sub>0</sub>), ...,
* (a<sub>n</sub>,b<sub>n</sub>), (elem,b<sub>n+1</sub>),
* ..., {elem,b<sub>m</sub>})</code>
* when <code>[a<sub>0</sub>, ..., a<sub>n</sub>] zip
* [b<sub>0</sub>, ..., b<sub>m</sub>]</code> is
* invoked where <code>m > n</code>.
*/
def zipAll[B, A1 >: A, B1 >: B](that: Stream[B], thisElem: A1, thatElem: B1): Stream[(A1, B1)] = {
if (that.isEmpty) new Cons((this.head, thatElem), this.tail.zipAll(that, thisElem, thatElem))
else new Cons((this.head, that.head), this.tail.zipAll(that.tail, thisElem, thatElem))
}
/** Zips this iterable with its indices. `s.zipWithIndex` is equivalent to
* `s zip s.indices`
*/
override def zipWithIndex = this zip (Iterator.from(0).toStream)
/** Write all defined elements of this iterable into given string builder.
* The written text begins with the string <code>start</code> and is finished by the string
* <code>end</code>. Inside, the string representations of defined elements (w.r.t.
* the method <code>toString()</code>) are separated by the string
* <code>sep</code>. The method will not force evaluation of undefined elements. A
* tail of such elements will be represented by a "?" instead.
*/
override def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = {
b append start append hd
if (tlDefined) tlVal.addString(b, sep, sep, end)
else b append ", ?" append end
}
/** Returns the <code>n</code> first elements of this stream, or else the whole
* stream, if it has less than <code>n</code> elements.
*
* @param n the number of elements to take.
* @return the <code>n</code> first elements of this stream.
*/
override def take(n: Int): Stream[A] =
if (n <= 0) Nil else new Cons(head, tail take (n-1))
/** Returns the stream without its <code>n</code> first elements.
* If the stream has less than <code>n</code> elements, the empty stream is returned.
*
* @param n the number of elements to drop.
* @return the stream without its <code>n</code> first elements.
*/
override def drop(n: Int): Stream[A] = {
var these: Stream[A] = this
var i = n
while (!these.isEmpty && i > 0) {
these = these.tail
i -= 1
}
these
}
/** A substream starting at index `from`
* and extending up to (but not including) index `until`.
*
* @This is equivalent to (but possibly more efficient than)
* c.drop(from).take(to - from)
*
* @param from The index of the first element of the returned subsequence
* @param until The index of the element following the returned subsequence
* @throws IndexOutOfBoundsException if <code>from < 0</code>
* or <code>length < from + len<code>
* @note Might return different results for different runs, unless this iterable is ordered
*/
override def slice(from: Int, to: Int): Stream[A] =
this.drop(from).take(to - from)
/** The stream without its last element.
* @throws Predef.UnsupportedOperationException if the stream is empty.
*/
override def init: Stream[A] =
if (tail.isEmpty) Nil
else new Cons(head, tail.init)
/** Returns the rightmost <code>n</code> elements from this iterable.
* @param n the number of elements to take
*/
override def takeRight(n: Int): Stream[A] = {
var these: Stream[A] = this
var lead = this drop n
while (!lead.isEmpty) {
these = these.tail
lead = lead.tail
}
these
}
/** Returns the longest prefix of this stream whose elements satisfy
* the predicate <code>p</code>.
*
* @param p the test predicate.
*/
override def takeWhile(p: A => Boolean): Stream[A] =
if (p(head)) new Cons(head, tail takeWhile p) else Nil
/** Returns the longest suffix of this iterable whose first element
* does not satisfy the predicate <code>p</code>.
*
* @param p the test predicate.
*/
override def dropWhile(p: A => Boolean): Stream[A] = {
var these: Stream[A] = this
while (!these.isEmpty && p(these.head)) these = these.tail
these
}
/** Returns a pair consisting of the longest prefix of the stream whose
* elements all satisfy the given predicate, and the rest of the stream.
*
* @param p the test predicate
*/
override def span(p: A => Boolean): (List[A], Stream[A]) = {
var these: Stream[A] = this
val l = new ListBuffer[A]
while (!these.isEmpty && p(these.head)) {
l += these.head
these = these.tail
}
(l.toList, these)
}
// Overridden methods from Sequence
/** Builds a new stream from this stream in which any duplicates (wrt to ==) removed.
* Among duplicate elements, only the first one is retained in the result stream
*/
override def removeDuplicates: Stream[A] =
new Cons(head, tail.filter(head !=).removeDuplicates)
/** Returns a new sequence of given length containing the elements of this sequence followed by zero
* or more occurrences of given elements.
*/
override def padTo[B >: A](len: Int, elem: B): Stream[B] =
new Cons(head, tail.padTo(len - 1, elem))
}
/**
* Create an infinite stream starting at <code>start</code>
* and incrementing by step <code>step</code>
*
* @param start the start value of the stream
* @param step the increment value of the stream
* @return the stream starting at value <code>start</code>.
*/
def from(start: Int, step: Int): Stream[Int] =
new Cons(start, from(start+step, step))
/**
* Create an infinite stream starting at <code>start</code>
* and incrementing by 1.
*
* @param start the start value of the stream
* @return the stream starting at value <code>start</code>.
*/
def from(start: Int): Stream[Int] = from(start, 1)
/**
* Create an infinite stream containing the given element expression (which is computed for each
* occurrence)
* @param elem the element composing the resulting stream
* @return the stream containing an inifinite number of elem
* @deprecated use fill instead
*/
@deprecated def fill[A](elem: => A): Stream[A] = new Cons(elem, fill(elem))
/** A stream containing all elements of a given iterator, in the order they are produced.
* @param it The iterator producing the stream's elements
* @deprecated use it.toStream instead
*/
@deprecated def fromIterator[A](it: Iterator[A]): Stream[A] =
if (it.hasNext) cons(it.next, fromIterator(it)) else empty
/** The concatenation of a sequence of streams
* @deprecated use xs.flatten instead
*/
@deprecated def concat[A](xs: Iterable[Stream[A]]): Stream[A] = concat(xs.elements)
/** The concatenation of all streams returned by an iterator
* @deprecated use xs.toStream.flatten instead
*/
@deprecated def concat[A](xs: Iterator[Stream[A]]): Stream[A] =
if (xs.hasNext) xs.next append concat(xs)
else empty
/**
* Create a stream with element values
* <code>v<sub>n+1</sub> = step(v<sub>n</sub>)</code>
* where <code>v<sub>0</sub> = start</code>
* and elements are in the range between <code>start</code> (inclusive)
* and <code>end</code> (exclusive)
* @deprecated use @see iterate instead.
* @param start the start value of the stream
* @param end the end value of the stream
* @param step the increment function of the stream, must be monotonically increasing or decreasing
* @return the stream starting at value <code>start</code>.
*/
@deprecated def range(start: Int, end: Int, step: Int => Int): Stream[Int] = {
val up = step(start) > start
val down = step(start) < start
def loop(lo: Int): Stream[Int] =
if ((!up || lo < end) && (!down || lo > end)) cons(lo, loop(step(lo)))
else empty
loop(start)
}
/**
* Create an infinite stream containing the given element.
*
* @param elem the element composing the resulting stream
* @return the stream containing an inifinite number of elem
* @deprecated use fill(elem) instead
*/
@deprecated def const[A](elem: A): Stream[A] = cons(elem, const(elem))
/** Create a stream containing several copies of an element.
*
* @param n the length of the resulting stream
* @param elem the element composing the resulting stream
* @return the stream composed of n elements all equal to elem
* @deprecated use fill(n, elem) instead
*/
@deprecated def make[A](n: Int, elem: A): Stream[A] =
const(elem) take n
}
import Stream._
/**
* <p>The class <code>Stream</code> implements lazy lists where elements
* are only evaluated when they are needed. Here is an example:</p>
* <pre>
* <b>object</b> Main <b>extends</b> Application {
*
* <b>def</b> from(n: Int): Stream[Int] =
* Stream.cons(n, from(n + 1))
*
* <b>def</b> sieve(s: Stream[Int]): Stream[Int] =
* Stream.cons(s.head, sieve(s.tail filter { _ % s.head != 0 }))
*
* <b>def</b> primes = sieve(from(2))
*
* primes take 10 print
* }
* </pre>
*
* @author Martin Odersky, Matthias Zenger
* @version 1.1 08/08/03
*/
abstract class Stream[+A] extends Sequence[A]
with SequenceTemplate[Stream, A @uncheckedVariance] {
self =>
import collection.{Iterable, OrderedIterable, Sequence, Vector}
/** is this stream empty? */
def isEmpty: Boolean
/** The first element of this stream
* @throws Predef.NoSuchElementException if the stream is empty.
*/
def head: A
/** A stream consisting of the remaining elements of this stream after the first one.
* @throws Predef.UnsupportedOperationException if the stream is empty.
*/
def tail: Stream[A]
// Implementation of abstract methods
/** Create a new @see LazyBuilder to build a stream */
def newBuilder[B]: Builder[Stream, B] = new LazyBuilder[Stream, B] {
def result: Stream[B] = elements.toStream
}
/** Returns the number of elements in the list.
*/
def length: Int = {
var these = self
var len = 0
while (!these.isEmpty) {
len += 1
these = these.tail
}
len
}
/** Returns the <code>n</code>-th element of this stream. The first element
* (head of the stream) is at position 0.
*
* @param n index of the element to return
* @return the element at position <code>n</code> in this stream.
* @throws Predef.NoSuchElementException if the stream is too short.
*/
override def apply(n: Int): A = drop(n).head
// New methods in Stream
/** The stream resulting from the concatenation of this stream with the argument stream.
* @param rest The stream that gets appended to this stream
*/
def append[B >: A](rest: => Iterable[B]): Stream[B] =
if (isEmpty) rest.toStream else new Cons(head, tail append rest)
/** Force evaluation of the whole stream and return it */
def force: Stream[A] = {
var these = this
while (!isEmpty) these = these.tail
this
}
/** Prints elements of this stream one by one, separated by commas */
def print() { print(", ") }
/** Prints elements of this stream one by one, separated by <code>sep</code>
* @param sep The separator string printed between consecutive elements.
*/
def print(sep: String) {
def loop(these: Stream[A], start: String) {
Console.print(start)
if (isEmpty) Console.print("empty")
else {
Console.print(these.head)
loop(these.tail, sep)
}
}
loop(this, "")
}
// Overridden methods from IterableTemplate or overloaded variants of such methods
/** Returns the elements in the sequence as an iterator
*/
override def elements: Iterator[A] = new Iterator[A] {
var these = self
def hasNext: Boolean = !these.isEmpty
def next: A =
if (hasNext) {
val result = these.head; these = these.tail; result
} else Iterator.empty.next
override def toList: List[A] = these.toList
}
/** Apply the given function <code>f</code> to each element of this stream
* (while respecting the order of the elements).
*
* @param f the treatment to apply to each element.
*/
override def foreach(f: A => Unit) {
var these = this
while (!these.isEmpty) {
f(these.head)
these = these.tail
}
}
/** Tests if the predicate <code>p</code> is satisfied by all elements
* in this list.
*
* !!! todo: perform speed with inherited version from Iterable, and drop
* if not significantly better
* @param p the test predicate.
* @return <code>true</code> iff all elements of this list satisfy the
* predicate <code>p</code>.
*/
override def forall(p: A => Boolean): Boolean = {
var these = this
while (!these.isEmpty) {
if (!p(these.head)) return false
these = these.tail
}
true
}
/** Tests the existence in this list of an element that satisfies the
* predicate <code>p</code>.
*
* !!! todo: perform speed with inherited version from Iterable, and drop
* if not significantly better
* @param p the test predicate.
* @return <code>true</code> iff there exists an element in this list that
* satisfies the predicate <code>p</code>.
*/
override def exists(p: A => Boolean): Boolean = {
var these = this
while (!these.isEmpty) {
if (p(these.head)) return true
these = these.tail
}
false
}
/** Count the number of elements in the iterable which satisfy a predicate.
*
* !!! todo: perform speed with inherited version from Iterable, and drop
* if not significantly better
* @param p the predicate for which to count
* @return the number of elements satisfying the predicate <code>p</code>.
*/
override def count(p: A => Boolean): Int = {
var these = this
var cnt = 0
while (!these.isEmpty) {
if (p(these.head)) cnt += 1
these = these.tail
}
cnt
}
/** Find and return the first element of the list satisfying a
* predicate, if any.
*
* !!! todo: perform speed with inherited version from Iterable, and drop
* if not significantly better
* @param p the predicate
* @return the first element in the list satisfying <code>p</code>,
* or <code>None</code> if none exists.
*/
override def find(p: A => Boolean): Option[A] = {
var these = this
while (!these.isEmpty) {
if (p(these.head)) return Some(these.head)
these = these.tail
}
None
}
/** Combines the elements of this list together using the binary
* function <code>f</code>, from left to right, and starting with
* the value <code>z</code>.
*
* !!! todo: perform speed with inherited version from Iterable, and drop
* if not significantly better
* @return <code>f(... (f(f(z, a<sub>0</sub>), a<sub>1</sub>) ...),
* a<sub>n</sub>)</code> if the list is
* <code>[a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub>]</code>.
*/
override def foldLeft[B](z: B)(f: (B, A) => B): B = {
var acc = z
var these = this
while (!these.isEmpty) {
acc = f(acc, these.head)
these = these.tail
}
acc
}
/** Combines the elements of this list together using the binary
* function <code>f</code>, from right to left, and starting with
* the value <code>z</code>.
*
* @return <code>f(a<sub>0</sub>, f(a<sub>1</sub>, f(..., f(a<sub>n</sub>, z)...)))</code>
* if the list is <code>[a<sub>0</sub>, a1, ..., a<sub>n</sub>]</code>.
*/
override def foldRight[B](z: B)(f: (A, B) => B): B =
if (this.isEmpty) z
else f(head, tail.foldRight(z)(f))
/** Combines the elements of this list together using the binary
* operator <code>op</code>, from left to right
* @param op The operator to apply
* @return <code>op(... op(a<sub>0</sub>,a<sub>1</sub>), ..., a<sub>n</sub>)</code>
if the list has elements
* <code>a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n</sub></code>.
* @throws Predef.UnsupportedOperationException if the list is empty.
*/
override def reduceLeft[B >: A](f: (B, A) => B): B =
if (isEmpty) throw new UnsupportedOperationException("empty.reduceLeft")
else tail.foldLeft[B](head)(f)
/** Combines the elements of this iterable object together using the binary
* operator <code>op</code>, from right to left
* @note Will not terminate for infinite-sized collections.
* @param op The operator to apply
*
* @return <code>a<sub>0</sub> op (... op (a<sub>n-1</sub> op a<sub>n</sub>)...)</code>
* if the iterable object has elements <code>a<sub>0</sub>, a<sub>1</sub>, ...,
* a<sub>n</sub></code>.
*
* @throws Predef.UnsupportedOperationException if the iterator is empty.
*/
override def reduceRight[B >: A](op: (A, B) => B): B =
if (isEmpty) throw new UnsupportedOperationException("Nil.reduceRight")
else if (tail.isEmpty) head
else op(head, tail.reduceRight(op))
/**
* Create a stream which contains all the elements of this iterable object.
* @note consider using <code>projection</code> for lazy behavior.
*/
override def toStream: Stream[A] = this
/** Defines the prefix of this object's <code>toString</code> representation as ``Stream''.
*/
override def stringPrefix = "Stream"
/** The last element of this stream.
*
* @throws Predef.NoSuchElementException if the stream is empty.
*/
override def last: A = {
if (isEmpty) throw new NoSuchElementException
var these = this
var nx = these.tail
while (!nx.isEmpty) {
these = nx
nx = nx.tail
}
these.head
}
/** Returns the rightmost <code>n</code> elements from this iterable.
* @param n the number of elements to take
*/
override def dropRight(n: Int): List[A] = {
val b = new ListBuffer[A]
var these = this
var lead = this drop n
while (!lead.isEmpty) {
b += these.head
these = these.tail
lead = lead.tail
}
b.toList
}
/** Returns true iff the other stream contains the same elements as this one.
*
* @note will not terminate for two infinite-sized streams.
* @param that the other stream
*/
def sameElements[B >: A](that: Stream[B]): Boolean = {
val these = this
val those = that
while (!these.isEmpty && !those.isEmpty && these.head == those.head) {}
these.isEmpty && those.isEmpty
}
// Overridden methods from Sequence
/** Result of comparing <code>length</code> with operand <code>len</code>.
* returns <code>x</code> where
* <code>x < 0</code> iff <code>this.length < len</code>
* <code>x == 0</code> iff <code>this.length == len</code>
* <code>x > 0</code> iff <code>this.length > len</code>.
*/
override def lengthCompare(len: Int): Int = {
var i = 0
var these = self
while (!these.isEmpty && i <= len) {
i += 1
these = these.tail
}
i - len
}
/** Is this partial function defined for the index <code>x</code>?
*/
override def isDefinedAt(x: Int): Boolean = x >= 0 && lengthCompare(x) >= 0
/** Returns length of longest segment starting from a start index `from`
* such that every element of the segment satisfies predicate `p`.
* @note may not terminate for infinite-sized collections.
* @param p the predicate
* @param from the start index
*/
override def segmentLength(p: A => Boolean, from: Int): Int = {
var i = from
var these = this drop from
while (!these.isEmpty && p(these.head)) {
i += 1
these = these.tail
}
i
}
/** Returns index of the first element starting from a start index
* satisying a predicate, or -1, if none exists.
*
* @note may not terminate for infinite-sized streams.
* @param p the predicate
* @param from the start index
*/
override def indexWhere(p: A => Boolean, from: Int): Int = {
var i = from
var these = this drop from
while (!these.isEmpty && !p(these.head)) {
i += 1
these = these.tail
}
if (these.isEmpty) -1 else i
}
/** Returns index of the last element satisying a predicate, or -1, if none exists.
*
* @param p the predicate
* @return the index of the last element satisfying <code>p</code>,
* or -1 if such an element does not exist
*/
override def lastIndexWhere(p: A => Boolean, end: Int): Int = {
var i = 0
var these = this
var last = -1
while (!these.isEmpty && i <= end) {
if (p(these.head)) last = i
}
i
}
/** A list consisting of all elements of this list in reverse order.
*/
override def reverse: List[A] = {
var result: List[A] = Nil
var these = this
while (!these.isEmpty) {
result = these.head :: result
these = these.tail
}
result
}
}
|