Scala mode

x
 
1
2
  /*                     __                                               *\
3
  **     ________ ___   / /  ___     Scala API                            **
4
  **    / __/ __// _ | / /  / _ |    (c) 2003-2011, LAMP/EPFL             **
5
  **  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
6
  ** /____/\___/_/ |_/____/_/ | |                                         **
7
  **                          |/                                          **
8
  \*                                                                      */
9
10
  package scala.collection
11
12
  import generic._
13
  import mutable.{ Builder, ListBuffer }
14
  import annotation.{tailrec, migration, bridge}
15
  import annotation.unchecked.{ uncheckedVariance => uV }
16
  import parallel.ParIterable
17
18
  /** A template trait for traversable collections of type `Traversable[A]`.
19
   *  
20
   *  $traversableInfo
21
   *  @define mutability
22
   *  @define traversableInfo
23
   *  This is a base trait of all kinds of $mutability Scala collections. It
24
   *  implements the behavior common to all collections, in terms of a method
25
   *  `foreach` with signature:
26
   * {{{
27
   *     def foreach[U](f: Elem => U): Unit
28
   * }}}
29
   *  Collection classes mixing in this trait provide a concrete 
30
   *  `foreach` method which traverses all the
31
   *  elements contained in the collection, applying a given function to each.
32
   *  They also need to provide a method `newBuilder`
33
   *  which creates a builder for collections of the same kind.
34
   *  
35
   *  A traversable class might or might not have two properties: strictness
36
   *  and orderedness. Neither is represented as a type.
37
   *  
38
   *  The instances of a strict collection class have all their elements
39
   *  computed before they can be used as values. By contrast, instances of
40
   *  a non-strict collection class may defer computation of some of their
41
   *  elements until after the instance is available as a value.
42
   *  A typical example of a non-strict collection class is a
43
   *  <a href="../immutable/Stream.html" target="ContentFrame">
44
   *  `scala.collection.immutable.Stream`</a>.
45
   *  A more general class of examples are `TraversableViews`.
46
   *  
47
   *  If a collection is an instance of an ordered collection class, traversing
48
   *  its elements with `foreach` will always visit elements in the
49
   *  same order, even for different runs of the program. If the class is not
50
   *  ordered, `foreach` can visit elements in different orders for
51
   *  different runs (but it will keep the same order in the same run).'
52
   * 
53
   *  A typical example of a collection class which is not ordered is a
54
   *  `HashMap` of objects. The traversal order for hash maps will
55
   *  depend on the hash codes of its elements, and these hash codes might
56
   *  differ from one run to the next. By contrast, a `LinkedHashMap`
57
   *  is ordered because it's `foreach` method visits elements in the
58
   *  order they were inserted into the `HashMap`.
59
   *
60
   *  @author Martin Odersky
61
   *  @version 2.8
62
   *  @since   2.8
63
   *  @tparam A    the element type of the collection
64
   *  @tparam Repr the type of the actual collection containing the elements.
65
   *
66
   *  @define Coll Traversable
67
   *  @define coll traversable collection
68
   */
69
  trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr] 
70
                                      with FilterMonadic[A, Repr]
71
                                      with TraversableOnce[A]
72
                                      with GenTraversableLike[A, Repr]
73
                                      with Parallelizable[A, ParIterable[A]]
74
  {
75
    self =>
76
77
    import Traversable.breaks._
78
79
    /** The type implementing this traversable */
80
    protected type Self = Repr
81
82
    /** The collection of type $coll underlying this `TraversableLike` object.
83
     *  By default this is implemented as the `TraversableLike` object itself,
84
     *  but this can be overridden.
85
     */
86
    def repr: Repr = this.asInstanceOf[Repr]
87
88
    /** The underlying collection seen as an instance of `$Coll`.
89
     *  By default this is implemented as the current collection object itself,
90
     *  but this can be overridden.
91
     */
92
    protected[this] def thisCollection: Traversable[A] = this.asInstanceOf[Traversable[A]]
93
94
    /** A conversion from collections of type `Repr` to `$Coll` objects.
95
     *  By default this is implemented as just a cast, but this can be overridden.
96
     */
97
    protected[this] def toCollection(repr: Repr): Traversable[A] = repr.asInstanceOf[Traversable[A]]
98
99
    /** Creates a new builder for this collection type.
100
     */
101
    protected[this] def newBuilder: Builder[A, Repr]
102
103
    protected[this] def parCombiner = ParIterable.newCombiner[A]
104
105
    /** Applies a function `f` to all elements of this $coll.
106
     *  
107
     *    Note: this method underlies the implementation of most other bulk operations.
108
     *    It's important to implement this method in an efficient way.
109
     *  
110
     *
111
     *  @param  f   the function that is applied for its side-effect to every element.
112
     *              The result of function `f` is discarded.
113
     *              
114
     *  @tparam  U  the type parameter describing the result of function `f`. 
115
     *              This result will always be ignored. Typically `U` is `Unit`,
116
     *              but this is not necessary.
117
     *
118
     *  @usecase def foreach(f: A => Unit): Unit
119
     */
120
    def foreach[U](f: A => U): Unit
121
122
    /** Tests whether this $coll is empty.
123
     *
124
     *  @return    `true` if the $coll contain no elements, `false` otherwise.
125
     */
126
    def isEmpty: Boolean = {
127
      var result = true
128
      breakable {
129
        for (x <- this) {
130
          result = false
131
          break
132
        }
133
      }
134
      result
135
    }
136
137
    /** Tests whether this $coll is known to have a finite size.
138
     *  All strict collections are known to have finite size. For a non-strict collection
139
     *  such as `Stream`, the predicate returns `true` if all elements have been computed.
140
     *  It returns `false` if the stream is not yet evaluated to the end.
141
     *
142
     *  Note: many collection methods will not work on collections of infinite sizes. 
143
     *
144
     *  @return  `true` if this collection is known to have finite size, `false` otherwise.
145
     */
146
    def hasDefiniteSize = true
147
148
    def ++[B >: A, That](that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
149
      val b = bf(repr)
150
      if (that.isInstanceOf[IndexedSeqLike[_, _]]) b.sizeHint(this, that.seq.size)
151
      b ++= thisCollection
152
      b ++= that.seq
153
      b.result
154
    }
155
156
    @bridge
157
    def ++[B >: A, That](that: TraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That =
158
      ++(that: GenTraversableOnce[B])(bf)
159
160
    /** Concatenates this $coll with the elements of a traversable collection.
161
     *  It differs from ++ in that the right operand determines the type of the
162
     *  resulting collection rather than the left one.
163
     * 
164
     *  @param that   the traversable to append.
165
     *  @tparam B     the element type of the returned collection. 
166
     *  @tparam That  $thatinfo
167
     *  @param bf     $bfinfo
168
     *  @return       a new collection of type `That` which contains all elements
169
     *                of this $coll followed by all elements of `that`.
170
     * 
171
     *  @usecase def ++:[B](that: TraversableOnce[B]): $Coll[B]
172
     *  
173
     *  @return       a new $coll which contains all elements of this $coll
174
     *                followed by all elements of `that`.
175
     */
176
    def ++:[B >: A, That](that: TraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
177
      val b = bf(repr)
178
      if (that.isInstanceOf[IndexedSeqLike[_, _]]) b.sizeHint(this, that.size)
179
      b ++= that
180
      b ++= thisCollection
181
      b.result
182
    }
183
184
    /** This overload exists because: for the implementation of ++: we should reuse
185
     *  that of ++ because many collections override it with more efficient versions.
186
     *  Since TraversableOnce has no '++' method, we have to implement that directly,
187
     *  but Traversable and down can use the overload.
188
     */
189
    def ++:[B >: A, That](that: Traversable[B])(implicit bf: CanBuildFrom[Repr, B, That]): That =
190
      (that ++ seq)(breakOut)
191
192
    def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
193
      val b = bf(repr)
194
      b.sizeHint(this) 
195
      for (x <- this) b += f(x)
196
      b.result
197
    }
198
199
    def flatMap[B, That](f: A => GenTraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
200
      val b = bf(repr)
201
      for (x <- this) b ++= f(x).seq
202
      b.result
203
    }
204
205
    /** Selects all elements of this $coll which satisfy a predicate.
206
     *
207
     *  @param p     the predicate used to test elements.
208
     *  @return      a new $coll consisting of all elements of this $coll that satisfy the given
209
     *               predicate `p`. The order of the elements is preserved.
210
     */
211
    def filter(p: A => Boolean): Repr = {
212
      val b = newBuilder
213
      for (x <- this) 
214
        if (p(x)) b += x
215
      b.result
216
    }
217
218
    /** Selects all elements of this $coll which do not satisfy a predicate.
219
     *
220
     *  @param p     the predicate used to test elements.
221
     *  @return      a new $coll consisting of all elements of this $coll that do not satisfy the given
222
     *               predicate `p`. The order of the elements is preserved.
223
     */
224
    def filterNot(p: A => Boolean): Repr = filter(!p(_))
225
226
    def collect[B, That](pf: PartialFunction[A, B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
227
      val b = bf(repr)
228
      for (x <- this) if (pf.isDefinedAt(x)) b += pf(x)
229
      b.result
230
    }
231
232
    /** Builds a new collection by applying an option-valued function to all
233
     *  elements of this $coll on which the function is defined.
234
     *
235
     *  @param f      the option-valued function which filters and maps the $coll.
236
     *  @tparam B     the element type of the returned collection.
237
     *  @tparam That  $thatinfo
238
     *  @param bf     $bfinfo
239
     *  @return       a new collection of type `That` resulting from applying the option-valued function
240
     *                `f` to each element and collecting all defined results.
241
     *                The order of the elements is preserved.
242
     *
243
     *  @usecase def filterMap[B](f: A => Option[B]): $Coll[B]
244
     *  
245
     *  @param pf     the partial function which filters and maps the $coll.
246
     *  @return       a new $coll resulting from applying the given option-valued function
247
     *                `f` to each element and collecting all defined results.
248
     *                The order of the elements is preserved.
249
    def filterMap[B, That](f: A => Option[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
250
      val b = bf(repr)
251
      for (x <- this) 
252
        f(x) match {
253
          case Some(y) => b += y
254
          case _ =>
255
        }
256
      b.result
257
    }
258
     */
259
260
    /** Partitions this $coll in two ${coll}s according to a predicate.
261
     *
262
     *  @param p the predicate on which to partition.
263
     *  @return  a pair of ${coll}s: the first $coll consists of all elements that 
264
     *           satisfy the predicate `p` and the second $coll consists of all elements
265
     *           that don't. The relative order of the elements in the resulting ${coll}s
266
     *           is the same as in the original $coll.
267
     */
268
    def partition(p: A => Boolean): (Repr, Repr) = {
269
      val l, r = newBuilder
270
      for (x <- this) (if (p(x)) l else r) += x
271
      (l.result, r.result)
272
    }
273
274
    def groupBy[K](f: A => K): immutable.Map[K, Repr] = {
275
      val m = mutable.Map.empty[K, Builder[A, Repr]]
276
      for (elem <- this) {
277
        val key = f(elem)
278
        val bldr = m.getOrElseUpdate(key, newBuilder)
279
        bldr += elem
280
      }
281
      val b = immutable.Map.newBuilder[K, Repr]
282
      for ((k, v) <- m)
283
        b += ((k, v.result))
284
285
      b.result
286
    }
287
288
    /** Tests whether a predicate holds for all elements of this $coll.
289
     *
290
     *  $mayNotTerminateInf
291
     *
292
     *  @param   p     the predicate used to test elements.
293
     *  @return        `true` if the given predicate `p` holds for all elements
294
     *                 of this $coll, otherwise `false`.
295
     */
296
    def forall(p: A => Boolean): Boolean = {
297
      var result = true
298
      breakable {
299
        for (x <- this)
300
          if (!p(x)) { result = false; break }
301
      }
302
      result
303
    }
304
305
    /** Tests whether a predicate holds for some of the elements of this $coll.
306
     *
307
     *  $mayNotTerminateInf
308
     *
309
     *  @param   p     the predicate used to test elements.
310
     *  @return        `true` if the given predicate `p` holds for some of the
311
     *                 elements of this $coll, otherwise `false`.
312
     */
313
    def exists(p: A => Boolean): Boolean = {
314
      var result = false
315
      breakable {
316
        for (x <- this)
317
          if (p(x)) { result = true; break }
318
      }
319
      result
320
    }
321
322
    /** Finds the first element of the $coll satisfying a predicate, if any.
323
     * 
324
     *  $mayNotTerminateInf
325
     *  $orderDependent
326
     *
327
     *  @param p    the predicate used to test elements.
328
     *  @return     an option value containing the first element in the $coll
329
     *              that satisfies `p`, or `None` if none exists.
330
     */
331
    def find(p: A => Boolean): Option[A] = {
332
      var result: Option[A] = None
333
      breakable {
334
        for (x <- this)
335
          if (p(x)) { result = Some(x); break }
336
      }
337
      result
338
    }
339
340
    def scan[B >: A, That](z: B)(op: (B, B) => B)(implicit cbf: CanBuildFrom[Repr, B, That]): That = scanLeft(z)(op)
341
342
    def scanLeft[B, That](z: B)(op: (B, A) => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
343
      val b = bf(repr)
344
      b.sizeHint(this, 1)
345
      var acc = z
346
      b += acc
347
      for (x <- this) { acc = op(acc, x); b += acc }
348
      b.result
349
    }
350
351
    @migration(2, 9,
352
      "This scanRight definition has changed in 2.9.\n" +
353
      "The previous behavior can be reproduced with scanRight.reverse."
354
    )
355
    def scanRight[B, That](z: B)(op: (A, B) => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
356
      var scanned = List(z)
357
      var acc = z
358
      for (x <- reversed) {
359
        acc = op(x, acc)
360
        scanned ::= acc
361
      }
362
      val b = bf(repr)
363
      for (elem <- scanned) b += elem
364
      b.result
365
    }
366
367
    /** Selects the first element of this $coll.
368
     *  $orderDependent
369
     *  @return  the first element of this $coll.
370
     *  @throws `NoSuchElementException` if the $coll is empty.
371
     */
372
    def head: A = {
373
      var result: () => A = () => throw new NoSuchElementException
374
      breakable {
375
        for (x <- this) {
376
          result = () => x
377
          break
378
        }
379
      }
380
      result()
381
    }
382
383
    /** Optionally selects the first element.
384
     *  $orderDependent
385
     *  @return  the first element of this $coll if it is nonempty, `None` if it is empty.
386
     */
387
    def headOption: Option[A] = if (isEmpty) None else Some(head)
388
389
    /** Selects all elements except the first.
390
     *  $orderDependent
391
     *  @return  a $coll consisting of all elements of this $coll
392
     *           except the first one.
393
     *  @throws `UnsupportedOperationException` if the $coll is empty.
394
     */ 
395
    override def tail: Repr = {
396
      if (isEmpty) throw new UnsupportedOperationException("empty.tail")
397
      drop(1)
398
    }
399
400
    /** Selects the last element.
401
      * $orderDependent
402
      * @return The last element of this $coll.
403
      * @throws NoSuchElementException If the $coll is empty.
404
      */
405
    def last: A = {
406
      var lst = head
407
      for (x <- this)
408
        lst = x
409
      lst
410
    }
411
412
    /** Optionally selects the last element.
413
     *  $orderDependent
414
     *  @return  the last element of this $coll$ if it is nonempty, `None` if it is empty.
415
     */
416
    def lastOption: Option[A] = if (isEmpty) None else Some(last)
417
418
    /** Selects all elements except the last.
419
     *  $orderDependent
420
     *  @return  a $coll consisting of all elements of this $coll
421
     *           except the last one.
422
     *  @throws `UnsupportedOperationException` if the $coll is empty.
423
     */
424
    def init: Repr = {
425
      if (isEmpty) throw new UnsupportedOperationException("empty.init")
426
      var lst = head
427
      var follow = false
428
      val b = newBuilder
429
      b.sizeHint(this, -1)
430
      for (x <- this.seq) {
431
        if (follow) b += lst
432
        else follow = true
433
        lst = x
434
      }
435
      b.result
436
    }
437
438
    def take(n: Int): Repr = slice(0, n)
439
440
    def drop(n: Int): Repr = 
441
      if (n <= 0) {
442
        val b = newBuilder
443
        b.sizeHint(this)
444
        b ++= thisCollection result
445
      }
446
      else sliceWithKnownDelta(n, Int.MaxValue, -n)
447
448
    def slice(from: Int, until: Int): Repr = sliceWithKnownBound(math.max(from, 0), until)
449
450
    // Precondition: from >= 0, until > 0, builder already configured for building.
451
    private[this] def sliceInternal(from: Int, until: Int, b: Builder[A, Repr]): Repr = {
452
      var i = 0
453
      breakable {
454
        for (x <- this.seq) {
455
          if (i >= from) b += x
456
          i += 1
457
          if (i >= until) break
458
        }
459
      }
460
      b.result
461
    }
462
    // Precondition: from >= 0
463
    private[scala] def sliceWithKnownDelta(from: Int, until: Int, delta: Int): Repr = {
464
      val b = newBuilder
465
      if (until <= from) b.result
466
      else {
467
        b.sizeHint(this, delta)
468
        sliceInternal(from, until, b)
469
      }
470
    }
471
    // Precondition: from >= 0
472
    private[scala] def sliceWithKnownBound(from: Int, until: Int): Repr = {
473
      val b = newBuilder
474
      if (until <= from) b.result
475
      else {
476
        b.sizeHintBounded(until - from, this)      
477
        sliceInternal(from, until, b)
478
      }
479
    }
480
481
    def takeWhile(p: A => Boolean): Repr = {
482
      val b = newBuilder
483
      breakable {
484
        for (x <- this) {
485
          if (!p(x)) break
486
          b += x
487
        }
488
      }
489
      b.result
490
    }
491
492
    def dropWhile(p: A => Boolean): Repr = {
493
      val b = newBuilder
494
      var go = false
495
      for (x <- this) {
496
        if (!p(x)) go = true
497
        if (go) b += x
498
      }
499
      b.result
500
    }
501
502
    def span(p: A => Boolean): (Repr, Repr) = {
503
      val l, r = newBuilder
504
      var toLeft = true
505
      for (x <- this) {
506
        toLeft = toLeft && p(x)
507
        (if (toLeft) l else r) += x
508
      }
509
      (l.result, r.result)
510
    }
511
512
    def splitAt(n: Int): (Repr, Repr) = {
513
      val l, r = newBuilder
514
      l.sizeHintBounded(n, this)
515
      if (n >= 0) r.sizeHint(this, -n)
516
      var i = 0
517
      for (x <- this) {
518
        (if (i < n) l else r) += x
519
        i += 1
520
      }
521
      (l.result, r.result)
522
    }
523
524
    /** Iterates over the tails of this $coll. The first value will be this
525
     *  $coll and the final one will be an empty $coll, with the intervening
526
     *  values the results of successive applications of `tail`.
527
     *
528
     *  @return   an iterator over all the tails of this $coll
529
     *  @example  `List(1,2,3).tails = Iterator(List(1,2,3), List(2,3), List(3), Nil)`
530
     */  
531
    def tails: Iterator[Repr] = iterateUntilEmpty(_.tail)
532
533
    /** Iterates over the inits of this $coll. The first value will be this
534
     *  $coll and the final one will be an empty $coll, with the intervening
535
     *  values the results of successive applications of `init`.
536
     *
537
     *  @return  an iterator over all the inits of this $coll
538
     *  @example  `List(1,2,3).inits = Iterator(List(1,2,3), List(1,2), List(1), Nil)`
539
     */
540
    def inits: Iterator[Repr] = iterateUntilEmpty(_.init)
541
542
    /** Copies elements of this $coll to an array.
543
     *  Fills the given array `xs` with at most `len` elements of
544
     *  this $coll, starting at position `start`.
545
     *  Copying will stop once either the end of the current $coll is reached,
546
     *  or the end of the array is reached, or `len` elements have been copied.
547
     *
548
     *  $willNotTerminateInf
549
     * 
550
     *  @param  xs     the array to fill.
551
     *  @param  start  the starting index.
552
     *  @param  len    the maximal number of elements to copy.
553
     *  @tparam B      the type of the elements of the array. 
554
     * 
555
     *
556
     *  @usecase def copyToArray(xs: Array[A], start: Int, len: Int): Unit
557
     */
558
    def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) {
559
      var i = start
560
      val end = (start + len) min xs.length
561
      breakable {
562
        for (x <- this) {
563
          if (i >= end) break
564
          xs(i) = x
565
          i += 1
566
        }
567
      }
568
    }
569
570
    def toTraversable: Traversable[A] = thisCollection
571
    def toIterator: Iterator[A] = toStream.iterator
572
    def toStream: Stream[A] = toBuffer.toStream
573
574
    /** Converts this $coll to a string.
575
     *
576
     *  @return   a string representation of this collection. By default this
577
     *            string consists of the `stringPrefix` of this $coll,
578
     *            followed by all elements separated by commas and enclosed in parentheses.
579
     */
580
    override def toString = mkString(stringPrefix + "(", ", ", ")")
581
582
    /** Defines the prefix of this object's `toString` representation.
583
     *
584
     *  @return  a string representation which starts the result of `toString`
585
     *           applied to this $coll. By default the string prefix is the
586
     *           simple name of the collection class $coll.
587
     */
588
    def stringPrefix : String = {
589
      var string = repr.asInstanceOf[AnyRef].getClass.getName
590
      val idx1 = string.lastIndexOf('.' : Int)
591
      if (idx1 != -1) string = string.substring(idx1 + 1)
592
      val idx2 = string.indexOf('$')
593
      if (idx2 != -1) string = string.substring(0, idx2)
594
      string
595
    }
596
597
    /** Creates a non-strict view of this $coll.
598
     * 
599
     *  @return a non-strict view of this $coll.
600
     */
601
    def view = new TraversableView[A, Repr] {
602
      protected lazy val underlying = self.repr
603
      override def foreach[U](f: A => U) = self foreach f
604
    }
605
606
    /** Creates a non-strict view of a slice of this $coll.
607
     *
608
     *  Note: the difference between `view` and `slice` is that `view` produces
609
     *        a view of the current $coll, whereas `slice` produces a new $coll.
610
     * 
611
     *  Note: `view(from, to)` is equivalent to `view.slice(from, to)`
612
     *  $orderDependent
613
     * 
614
     *  @param from   the index of the first element of the view
615
     *  @param until  the index of the element following the view
616
     *  @return a non-strict view of a slice of this $coll, starting at index `from`
617
     *  and extending up to (but not including) index `until`.
618
     */
619
    def view(from: Int, until: Int): TraversableView[A, Repr] = view.slice(from, until)
620
621
    /** Creates a non-strict filter of this $coll.
622
     *
623
     *  Note: the difference between `c filter p` and `c withFilter p` is that
624
     *        the former creates a new collection, whereas the latter only
625
     *        restricts the domain of subsequent `map`, `flatMap`, `foreach`,
626
     *        and `withFilter` operations.
627
     *  $orderDependent
628
     * 
629
     *  @param p   the predicate used to test elements.
630
     *  @return    an object of class `WithFilter`, which supports
631
     *             `map`, `flatMap`, `foreach`, and `withFilter` operations.
632
     *             All these operations apply to those elements of this $coll which
633
     *             satisfy the predicate `p`.
634
     */
635
    def withFilter(p: A => Boolean): FilterMonadic[A, Repr] = new WithFilter(p)
636
637
    /** A class supporting filtered operations. Instances of this class are
638
     *  returned by method `withFilter`.
639
     */
640
    class WithFilter(p: A => Boolean) extends FilterMonadic[A, Repr] {
641
642
      /** Builds a new collection by applying a function to all elements of the
643
       *  outer $coll containing this `WithFilter` instance that satisfy predicate `p`.
644
       *
645
       *  @param f      the function to apply to each element.
646
       *  @tparam B     the element type of the returned collection.
647
       *  @tparam That  $thatinfo
648
       *  @param bf     $bfinfo
649
       *  @return       a new collection of type `That` resulting from applying
650
       *                the given function `f` to each element of the outer $coll
651
       *                that satisfies predicate `p` and collecting the results.
652
       *
653
       *  @usecase def map[B](f: A => B): $Coll[B] 
654
       *  
655
       *  @return       a new $coll resulting from applying the given function
656
       *                `f` to each element of the outer $coll that satisfies
657
       *                predicate `p` and collecting the results.
658
       */
659
      def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
660
        val b = bf(repr)
661
        for (x <- self) 
662
          if (p(x)) b += f(x)
663
        b.result
664
      }
665
666
      /** Builds a new collection by applying a function to all elements of the
667
       *  outer $coll containing this `WithFilter` instance that satisfy
668
       *  predicate `p` and concatenating the results. 
669
       *
670
       *  @param f      the function to apply to each element.
671
       *  @tparam B     the element type of the returned collection.
672
       *  @tparam That  $thatinfo
673
       *  @param bf     $bfinfo
674
       *  @return       a new collection of type `That` resulting from applying
675
       *                the given collection-valued function `f` to each element
676
       *                of the outer $coll that satisfies predicate `p` and
677
       *                concatenating the results.
678
       *
679
       *  @usecase def flatMap[B](f: A => TraversableOnce[B]): $Coll[B]
680
       * 
681
       *  @return       a new $coll resulting from applying the given collection-valued function
682
       *                `f` to each element of the outer $coll that satisfies predicate `p` and concatenating the results.
683
       */
684
      def flatMap[B, That](f: A => GenTraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
685
        val b = bf(repr)
686
        for (x <- self) 
687
          if (p(x)) b ++= f(x).seq
688
        b.result
689
      }
690
691
      /** Applies a function `f` to all elements of the outer $coll containing
692
       *  this `WithFilter` instance that satisfy predicate `p`.
693
       *
694
       *  @param  f   the function that is applied for its side-effect to every element.
695
       *              The result of function `f` is discarded.
696
       *              
697
       *  @tparam  U  the type parameter describing the result of function `f`. 
698
       *              This result will always be ignored. Typically `U` is `Unit`,
699
       *              but this is not necessary.
700
       *
701
       *  @usecase def foreach(f: A => Unit): Unit
702
       */   
703
      def foreach[U](f: A => U): Unit = 
704
        for (x <- self) 
705
          if (p(x)) f(x)
706
707
      /** Further refines the filter for this $coll.
708
       *
709
       *  @param q   the predicate used to test elements.
710
       *  @return    an object of class `WithFilter`, which supports
711
       *             `map`, `flatMap`, `foreach`, and `withFilter` operations.
712
       *             All these operations apply to those elements of this $coll which
713
       *             satisfy the predicate `q` in addition to the predicate `p`.
714
       */
715
      def withFilter(q: A => Boolean): WithFilter = 
716
        new WithFilter(x => p(x) && q(x))
717
    }
718
719
    // A helper for tails and inits.
720
    private def iterateUntilEmpty(f: Traversable[A @uV] => Traversable[A @uV]): Iterator[Repr] = {
721
      val it = Iterator.iterate(thisCollection)(f) takeWhile (x => !x.isEmpty)
722
      it ++ Iterator(Nil) map (newBuilder ++= _ result)
723
    }
724
  }
725
726
727