5 <title>CodeMirror: C-like mode</title>
6 <link rel="stylesheet" href="../../lib/codemirror.css">
7 <link rel="stylesheet" href="../../theme/ambiance.css">
8 <script src="../../lib/codemirror.js"></script>
9 <script src="../../addon/edit/matchbrackets.js"></script>
10 <script src="clike.js"></script>
11 <link rel="stylesheet" href="../../doc/docs.css">
20 html, form, .CodeMirror, .CodeMirror-scroll
28 <textarea id="code" name="code">
31 ** ________ ___ / / ___ Scala API **
32 ** / __/ __// _ | / / / _ | (c) 2003-2011, LAMP/EPFL **
33 ** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
34 ** /____/\___/_/ |_/____/_/ | | **
38 package scala.collection
41 import mutable.{ Builder, ListBuffer }
42 import annotation.{tailrec, migration, bridge}
43 import annotation.unchecked.{ uncheckedVariance => uV }
44 import parallel.ParIterable
46 /** A template trait for traversable collections of type `Traversable[A]`.
50 * @define traversableInfo
51 * This is a base trait of all kinds of $mutability Scala collections. It
52 * implements the behavior common to all collections, in terms of a method
53 * `foreach` with signature:
55 * def foreach[U](f: Elem => U): Unit
57 * Collection classes mixing in this trait provide a concrete
58 * `foreach` method which traverses all the
59 * elements contained in the collection, applying a given function to each.
60 * They also need to provide a method `newBuilder`
61 * which creates a builder for collections of the same kind.
63 * A traversable class might or might not have two properties: strictness
64 * and orderedness. Neither is represented as a type.
66 * The instances of a strict collection class have all their elements
67 * computed before they can be used as values. By contrast, instances of
68 * a non-strict collection class may defer computation of some of their
69 * elements until after the instance is available as a value.
70 * A typical example of a non-strict collection class is a
71 * <a href="../immutable/Stream.html" target="ContentFrame">
72 * `scala.collection.immutable.Stream`</a>.
73 * A more general class of examples are `TraversableViews`.
75 * If a collection is an instance of an ordered collection class, traversing
76 * its elements with `foreach` will always visit elements in the
77 * same order, even for different runs of the program. If the class is not
78 * ordered, `foreach` can visit elements in different orders for
79 * different runs (but it will keep the same order in the same run).'
81 * A typical example of a collection class which is not ordered is a
82 * `HashMap` of objects. The traversal order for hash maps will
83 * depend on the hash codes of its elements, and these hash codes might
84 * differ from one run to the next. By contrast, a `LinkedHashMap`
85 * is ordered because it's `foreach` method visits elements in the
86 * order they were inserted into the `HashMap`.
88 * @author Martin Odersky
91 * @tparam A the element type of the collection
92 * @tparam Repr the type of the actual collection containing the elements.
94 * @define Coll Traversable
95 * @define coll traversable collection
97 trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr]
98 with FilterMonadic[A, Repr]
99 with TraversableOnce[A]
100 with GenTraversableLike[A, Repr]
101 with Parallelizable[A, ParIterable[A]]
105 import Traversable.breaks._
107 /** The type implementing this traversable */
108 protected type Self = Repr
110 /** The collection of type $coll underlying this `TraversableLike` object.
111 * By default this is implemented as the `TraversableLike` object itself,
112 * but this can be overridden.
114 def repr: Repr = this.asInstanceOf[Repr]
116 /** The underlying collection seen as an instance of `$Coll`.
117 * By default this is implemented as the current collection object itself,
118 * but this can be overridden.
120 protected[this] def thisCollection: Traversable[A] = this.asInstanceOf[Traversable[A]]
122 /** A conversion from collections of type `Repr` to `$Coll` objects.
123 * By default this is implemented as just a cast, but this can be overridden.
125 protected[this] def toCollection(repr: Repr): Traversable[A] = repr.asInstanceOf[Traversable[A]]
127 /** Creates a new builder for this collection type.
129 protected[this] def newBuilder: Builder[A, Repr]
131 protected[this] def parCombiner = ParIterable.newCombiner[A]
133 /** Applies a function `f` to all elements of this $coll.
135 * Note: this method underlies the implementation of most other bulk operations.
136 * It's important to implement this method in an efficient way.
139 * @param f the function that is applied for its side-effect to every element.
140 * The result of function `f` is discarded.
142 * @tparam U the type parameter describing the result of function `f`.
143 * This result will always be ignored. Typically `U` is `Unit`,
144 * but this is not necessary.
146 * @usecase def foreach(f: A => Unit): Unit
148 def foreach[U](f: A => U): Unit
150 /** Tests whether this $coll is empty.
152 * @return `true` if the $coll contain no elements, `false` otherwise.
154 def isEmpty: Boolean = {
165 /** Tests whether this $coll is known to have a finite size.
166 * All strict collections are known to have finite size. For a non-strict collection
167 * such as `Stream`, the predicate returns `true` if all elements have been computed.
168 * It returns `false` if the stream is not yet evaluated to the end.
170 * Note: many collection methods will not work on collections of infinite sizes.
172 * @return `true` if this collection is known to have finite size, `false` otherwise.
174 def hasDefiniteSize = true
176 def ++[B >: A, That](that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
178 if (that.isInstanceOf[IndexedSeqLike[_, _]]) b.sizeHint(this, that.seq.size)
185 def ++[B >: A, That](that: TraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That =
186 ++(that: GenTraversableOnce[B])(bf)
188 /** Concatenates this $coll with the elements of a traversable collection.
189 * It differs from ++ in that the right operand determines the type of the
190 * resulting collection rather than the left one.
192 * @param that the traversable to append.
193 * @tparam B the element type of the returned collection.
194 * @tparam That $thatinfo
196 * @return a new collection of type `That` which contains all elements
197 * of this $coll followed by all elements of `that`.
199 * @usecase def ++:[B](that: TraversableOnce[B]): $Coll[B]
201 * @return a new $coll which contains all elements of this $coll
202 * followed by all elements of `that`.
204 def ++:[B >: A, That](that: TraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
206 if (that.isInstanceOf[IndexedSeqLike[_, _]]) b.sizeHint(this, that.size)
212 /** This overload exists because: for the implementation of ++: we should reuse
213 * that of ++ because many collections override it with more efficient versions.
214 * Since TraversableOnce has no '++' method, we have to implement that directly,
215 * but Traversable and down can use the overload.
217 def ++:[B >: A, That](that: Traversable[B])(implicit bf: CanBuildFrom[Repr, B, That]): That =
218 (that ++ seq)(breakOut)
220 def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
223 for (x <- this) b += f(x)
227 def flatMap[B, That](f: A => GenTraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
229 for (x <- this) b ++= f(x).seq
233 /** Selects all elements of this $coll which satisfy a predicate.
235 * @param p the predicate used to test elements.
236 * @return a new $coll consisting of all elements of this $coll that satisfy the given
237 * predicate `p`. The order of the elements is preserved.
239 def filter(p: A => Boolean): Repr = {
246 /** Selects all elements of this $coll which do not satisfy a predicate.
248 * @param p the predicate used to test elements.
249 * @return a new $coll consisting of all elements of this $coll that do not satisfy the given
250 * predicate `p`. The order of the elements is preserved.
252 def filterNot(p: A => Boolean): Repr = filter(!p(_))
254 def collect[B, That](pf: PartialFunction[A, B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
256 for (x <- this) if (pf.isDefinedAt(x)) b += pf(x)
260 /** Builds a new collection by applying an option-valued function to all
261 * elements of this $coll on which the function is defined.
263 * @param f the option-valued function which filters and maps the $coll.
264 * @tparam B the element type of the returned collection.
265 * @tparam That $thatinfo
267 * @return a new collection of type `That` resulting from applying the option-valued function
268 * `f` to each element and collecting all defined results.
269 * The order of the elements is preserved.
271 * @usecase def filterMap[B](f: A => Option[B]): $Coll[B]
273 * @param pf the partial function which filters and maps the $coll.
274 * @return a new $coll resulting from applying the given option-valued function
275 * `f` to each element and collecting all defined results.
276 * The order of the elements is preserved.
277 def filterMap[B, That](f: A => Option[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
281 case Some(y) => b += y
288 /** Partitions this $coll in two ${coll}s according to a predicate.
290 * @param p the predicate on which to partition.
291 * @return a pair of ${coll}s: the first $coll consists of all elements that
292 * satisfy the predicate `p` and the second $coll consists of all elements
293 * that don't. The relative order of the elements in the resulting ${coll}s
294 * is the same as in the original $coll.
296 def partition(p: A => Boolean): (Repr, Repr) = {
297 val l, r = newBuilder
298 for (x <- this) (if (p(x)) l else r) += x
302 def groupBy[K](f: A => K): immutable.Map[K, Repr] = {
303 val m = mutable.Map.empty[K, Builder[A, Repr]]
306 val bldr = m.getOrElseUpdate(key, newBuilder)
309 val b = immutable.Map.newBuilder[K, Repr]
316 /** Tests whether a predicate holds for all elements of this $coll.
318 * $mayNotTerminateInf
320 * @param p the predicate used to test elements.
321 * @return `true` if the given predicate `p` holds for all elements
322 * of this $coll, otherwise `false`.
324 def forall(p: A => Boolean): Boolean = {
328 if (!p(x)) { result = false; break }
333 /** Tests whether a predicate holds for some of the elements of this $coll.
335 * $mayNotTerminateInf
337 * @param p the predicate used to test elements.
338 * @return `true` if the given predicate `p` holds for some of the
339 * elements of this $coll, otherwise `false`.
341 def exists(p: A => Boolean): Boolean = {
345 if (p(x)) { result = true; break }
350 /** Finds the first element of the $coll satisfying a predicate, if any.
352 * $mayNotTerminateInf
355 * @param p the predicate used to test elements.
356 * @return an option value containing the first element in the $coll
357 * that satisfies `p`, or `None` if none exists.
359 def find(p: A => Boolean): Option[A] = {
360 var result: Option[A] = None
363 if (p(x)) { result = Some(x); break }
368 def scan[B >: A, That](z: B)(op: (B, B) => B)(implicit cbf: CanBuildFrom[Repr, B, That]): That = scanLeft(z)(op)
370 def scanLeft[B, That](z: B)(op: (B, A) => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
375 for (x <- this) { acc = op(acc, x); b += acc }
380 "This scanRight definition has changed in 2.9.\n" +
381 "The previous behavior can be reproduced with scanRight.reverse."
383 def scanRight[B, That](z: B)(op: (A, B) => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
384 var scanned = List(z)
386 for (x <- reversed) {
391 for (elem <- scanned) b += elem
395 /** Selects the first element of this $coll.
397 * @return the first element of this $coll.
398 * @throws `NoSuchElementException` if the $coll is empty.
401 var result: () => A = () => throw new NoSuchElementException
411 /** Optionally selects the first element.
413 * @return the first element of this $coll if it is nonempty, `None` if it is empty.
415 def headOption: Option[A] = if (isEmpty) None else Some(head)
417 /** Selects all elements except the first.
419 * @return a $coll consisting of all elements of this $coll
420 * except the first one.
421 * @throws `UnsupportedOperationException` if the $coll is empty.
423 override def tail: Repr = {
424 if (isEmpty) throw new UnsupportedOperationException("empty.tail")
428 /** Selects the last element.
430 * @return The last element of this $coll.
431 * @throws NoSuchElementException If the $coll is empty.
440 /** Optionally selects the last element.
442 * @return the last element of this $coll$ if it is nonempty, `None` if it is empty.
444 def lastOption: Option[A] = if (isEmpty) None else Some(last)
446 /** Selects all elements except the last.
448 * @return a $coll consisting of all elements of this $coll
449 * except the last one.
450 * @throws `UnsupportedOperationException` if the $coll is empty.
453 if (isEmpty) throw new UnsupportedOperationException("empty.init")
458 for (x <- this.seq) {
466 def take(n: Int): Repr = slice(0, n)
468 def drop(n: Int): Repr =
472 b ++= thisCollection result
474 else sliceWithKnownDelta(n, Int.MaxValue, -n)
476 def slice(from: Int, until: Int): Repr = sliceWithKnownBound(math.max(from, 0), until)
478 // Precondition: from >= 0, until > 0, builder already configured for building.
479 private[this] def sliceInternal(from: Int, until: Int, b: Builder[A, Repr]): Repr = {
482 for (x <- this.seq) {
483 if (i >= from) b += x
485 if (i >= until) break
490 // Precondition: from >= 0
491 private[scala] def sliceWithKnownDelta(from: Int, until: Int, delta: Int): Repr = {
493 if (until <= from) b.result
495 b.sizeHint(this, delta)
496 sliceInternal(from, until, b)
499 // Precondition: from >= 0
500 private[scala] def sliceWithKnownBound(from: Int, until: Int): Repr = {
502 if (until <= from) b.result
504 b.sizeHintBounded(until - from, this)
505 sliceInternal(from, until, b)
509 def takeWhile(p: A => Boolean): Repr = {
520 def dropWhile(p: A => Boolean): Repr = {
530 def span(p: A => Boolean): (Repr, Repr) = {
531 val l, r = newBuilder
534 toLeft = toLeft && p(x)
535 (if (toLeft) l else r) += x
540 def splitAt(n: Int): (Repr, Repr) = {
541 val l, r = newBuilder
542 l.sizeHintBounded(n, this)
543 if (n >= 0) r.sizeHint(this, -n)
546 (if (i < n) l else r) += x
552 /** Iterates over the tails of this $coll. The first value will be this
553 * $coll and the final one will be an empty $coll, with the intervening
554 * values the results of successive applications of `tail`.
556 * @return an iterator over all the tails of this $coll
557 * @example `List(1,2,3).tails = Iterator(List(1,2,3), List(2,3), List(3), Nil)`
559 def tails: Iterator[Repr] = iterateUntilEmpty(_.tail)
561 /** Iterates over the inits of this $coll. The first value will be this
562 * $coll and the final one will be an empty $coll, with the intervening
563 * values the results of successive applications of `init`.
565 * @return an iterator over all the inits of this $coll
566 * @example `List(1,2,3).inits = Iterator(List(1,2,3), List(1,2), List(1), Nil)`
568 def inits: Iterator[Repr] = iterateUntilEmpty(_.init)
570 /** Copies elements of this $coll to an array.
571 * Fills the given array `xs` with at most `len` elements of
572 * this $coll, starting at position `start`.
573 * Copying will stop once either the end of the current $coll is reached,
574 * or the end of the array is reached, or `len` elements have been copied.
576 * $willNotTerminateInf
578 * @param xs the array to fill.
579 * @param start the starting index.
580 * @param len the maximal number of elements to copy.
581 * @tparam B the type of the elements of the array.
584 * @usecase def copyToArray(xs: Array[A], start: Int, len: Int): Unit
586 def copyToArray[B >: A](xs: Array[B], start: Int, len: Int) {
588 val end = (start + len) min xs.length
598 def toTraversable: Traversable[A] = thisCollection
599 def toIterator: Iterator[A] = toStream.iterator
600 def toStream: Stream[A] = toBuffer.toStream
602 /** Converts this $coll to a string.
604 * @return a string representation of this collection. By default this
605 * string consists of the `stringPrefix` of this $coll,
606 * followed by all elements separated by commas and enclosed in parentheses.
608 override def toString = mkString(stringPrefix + "(", ", ", ")")
610 /** Defines the prefix of this object's `toString` representation.
612 * @return a string representation which starts the result of `toString`
613 * applied to this $coll. By default the string prefix is the
614 * simple name of the collection class $coll.
616 def stringPrefix : String = {
617 var string = repr.asInstanceOf[AnyRef].getClass.getName
618 val idx1 = string.lastIndexOf('.' : Int)
619 if (idx1 != -1) string = string.substring(idx1 + 1)
620 val idx2 = string.indexOf('$')
621 if (idx2 != -1) string = string.substring(0, idx2)
625 /** Creates a non-strict view of this $coll.
627 * @return a non-strict view of this $coll.
629 def view = new TraversableView[A, Repr] {
630 protected lazy val underlying = self.repr
631 override def foreach[U](f: A => U) = self foreach f
634 /** Creates a non-strict view of a slice of this $coll.
636 * Note: the difference between `view` and `slice` is that `view` produces
637 * a view of the current $coll, whereas `slice` produces a new $coll.
639 * Note: `view(from, to)` is equivalent to `view.slice(from, to)`
642 * @param from the index of the first element of the view
643 * @param until the index of the element following the view
644 * @return a non-strict view of a slice of this $coll, starting at index `from`
645 * and extending up to (but not including) index `until`.
647 def view(from: Int, until: Int): TraversableView[A, Repr] = view.slice(from, until)
649 /** Creates a non-strict filter of this $coll.
651 * Note: the difference between `c filter p` and `c withFilter p` is that
652 * the former creates a new collection, whereas the latter only
653 * restricts the domain of subsequent `map`, `flatMap`, `foreach`,
654 * and `withFilter` operations.
657 * @param p the predicate used to test elements.
658 * @return an object of class `WithFilter`, which supports
659 * `map`, `flatMap`, `foreach`, and `withFilter` operations.
660 * All these operations apply to those elements of this $coll which
661 * satisfy the predicate `p`.
663 def withFilter(p: A => Boolean): FilterMonadic[A, Repr] = new WithFilter(p)
665 /** A class supporting filtered operations. Instances of this class are
666 * returned by method `withFilter`.
668 class WithFilter(p: A => Boolean) extends FilterMonadic[A, Repr] {
670 /** Builds a new collection by applying a function to all elements of the
671 * outer $coll containing this `WithFilter` instance that satisfy predicate `p`.
673 * @param f the function to apply to each element.
674 * @tparam B the element type of the returned collection.
675 * @tparam That $thatinfo
677 * @return a new collection of type `That` resulting from applying
678 * the given function `f` to each element of the outer $coll
679 * that satisfies predicate `p` and collecting the results.
681 * @usecase def map[B](f: A => B): $Coll[B]
683 * @return a new $coll resulting from applying the given function
684 * `f` to each element of the outer $coll that satisfies
685 * predicate `p` and collecting the results.
687 def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That = {
694 /** Builds a new collection by applying a function to all elements of the
695 * outer $coll containing this `WithFilter` instance that satisfy
696 * predicate `p` and concatenating the results.
698 * @param f the function to apply to each element.
699 * @tparam B the element type of the returned collection.
700 * @tparam That $thatinfo
702 * @return a new collection of type `That` resulting from applying
703 * the given collection-valued function `f` to each element
704 * of the outer $coll that satisfies predicate `p` and
705 * concatenating the results.
707 * @usecase def flatMap[B](f: A => TraversableOnce[B]): $Coll[B]
709 * @return a new $coll resulting from applying the given collection-valued function
710 * `f` to each element of the outer $coll that satisfies predicate `p` and concatenating the results.
712 def flatMap[B, That](f: A => GenTraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That = {
715 if (p(x)) b ++= f(x).seq
719 /** Applies a function `f` to all elements of the outer $coll containing
720 * this `WithFilter` instance that satisfy predicate `p`.
722 * @param f the function that is applied for its side-effect to every element.
723 * The result of function `f` is discarded.
725 * @tparam U the type parameter describing the result of function `f`.
726 * This result will always be ignored. Typically `U` is `Unit`,
727 * but this is not necessary.
729 * @usecase def foreach(f: A => Unit): Unit
731 def foreach[U](f: A => U): Unit =
735 /** Further refines the filter for this $coll.
737 * @param q the predicate used to test elements.
738 * @return an object of class `WithFilter`, which supports
739 * `map`, `flatMap`, `foreach`, and `withFilter` operations.
740 * All these operations apply to those elements of this $coll which
741 * satisfy the predicate `q` in addition to the predicate `p`.
743 def withFilter(q: A => Boolean): WithFilter =
744 new WithFilter(x => p(x) && q(x))
747 // A helper for tails and inits.
748 private def iterateUntilEmpty(f: Traversable[A @uV] => Traversable[A @uV]): Iterator[Repr] = {
749 val it = Iterator.iterate(thisCollection)(f) takeWhile (x => !x.isEmpty)
750 it ++ Iterator(Nil) map (newBuilder ++= _ result)
759 var editor = CodeMirror.fromTextArea(document.getElementById("code"), {