diff options
author | Antonio Cunei <antonio.cunei@epfl.ch> | 2010-07-16 13:03:33 +0000 |
---|---|---|
committer | Antonio Cunei <antonio.cunei@epfl.ch> | 2010-07-16 13:03:33 +0000 |
commit | ed2532a39ac94d889294bf1ee4c7e29b8cfc8178 (patch) | |
tree | 73f9bdd71b00ceec06b93eeeb5457f2c0a005428 /src | |
parent | 05872beac8a47ea2a28194b7cde091a0ce3e0449 (diff) | |
download | scala-ed2532a39ac94d889294bf1ee4c7e29b8cfc8178.tar.gz scala-ed2532a39ac94d889294bf1ee4c7e29b8cfc8178.tar.bz2 scala-ed2532a39ac94d889294bf1ee4c7e29b8cfc8178.zip |
still aligning with trunk
Diffstat (limited to 'src')
8 files changed, 10 insertions, 707 deletions
diff --git a/src/library/scala/collection/TraversableLike.scala b/src/library/scala/collection/TraversableLike.scala index fd5d8ba72c..6f851fb5e7 100644 --- a/src/library/scala/collection/TraversableLike.scala +++ b/src/library/scala/collection/TraversableLike.scala @@ -330,17 +330,18 @@ trait TraversableLike[+A, +Repr] extends HasNewBuilder[A, Repr] * for which `f(x)` equals `k`. * */ - def groupBy[K](f: A => K): Map[K, Repr] = { - var m = Map[K, Builder[A, Repr]]() + def groupBy[K](f: A => K): immutable.Map[K, Repr] = { + val m = mutable.Map.empty[K, Builder[A, Repr]] for (elem <- this) { val key = f(elem) - val bldr = m get key match { - case None => val b = newBuilder; m = m updated (key, b); b - case Some(b) => b - } + val bldr = m.getOrElseUpdate(key, newBuilder) bldr += elem } - m map { case (k, b) => (k, b.result) } + val b = immutable.Map.newBuilder[K, Repr] + for ((k, v) <- m) + b += ((k, v.result)) + + b.result } /** Tests whether a predicate holds for all elements of this $coll. diff --git a/src/library/scala/collection/TraversableProxyLike.scala b/src/library/scala/collection/TraversableProxyLike.scala index 05c4c44f12..f2d91ded0c 100644 --- a/src/library/scala/collection/TraversableProxyLike.scala +++ b/src/library/scala/collection/TraversableProxyLike.scala @@ -37,7 +37,7 @@ trait TraversableProxyLike[+A, +Repr <: TraversableLike[A, Repr] with Traversabl override def filterNot(p: A => Boolean): Repr = self.filterNot(p) override def collect[B, That](pf: PartialFunction[A, B])(implicit bf: CanBuildFrom[Repr, B, That]): That = self.collect(pf)(bf) override def partition(p: A => Boolean): (Repr, Repr) = self.partition(p) - override def groupBy[K](f: A => K): Map[K, Repr] = self.groupBy(f) + override def groupBy[K](f: A => K): immutable.Map[K, Repr] = self.groupBy(f) override def forall(p: A => Boolean): Boolean = self.forall(p) override def exists(p: A => Boolean): Boolean = self.exists(p) override def count(p: A => Boolean): Int = self.count(p) diff --git a/src/library/scala/collection/TraversableViewLike.scala b/src/library/scala/collection/TraversableViewLike.scala index 7b443e54b8..9b5be82dd6 100644 --- a/src/library/scala/collection/TraversableViewLike.scala +++ b/src/library/scala/collection/TraversableViewLike.scala @@ -216,7 +216,7 @@ self => override def scanRight[B, That](z: B)(op: (A, B) => B)(implicit bf: CanBuildFrom[This, B, That]): That = newForced(thisSeq.scanRight(z)(op)).asInstanceOf[That] - override def groupBy[K](f: A => K): Map[K, This] = + override def groupBy[K](f: A => K): immutable.Map[K, This] = thisSeq.groupBy(f).mapValues(xs => newForced(xs).asInstanceOf[This]) override def stringPrefix = "TraversableView" diff --git a/src/library/scala/collection/parallel/Combiners.scala b/src/library/scala/collection/parallel/Combiners.scala deleted file mode 100644 index a37f642d42..0000000000 --- a/src/library/scala/collection/parallel/Combiners.scala +++ /dev/null @@ -1,66 +0,0 @@ -package scala.collection.parallel - - -import scala.collection.Parallel -import scala.collection.mutable.Builder -import scala.collection.generic.Sizing - - - -/** The base trait for all combiners. - * A combiner lets one construct collections incrementally just like - * a regular builder, but also implements an efficient merge operation of two builders - * via `combine` method. Once the collection is constructed, it may be obtained by invoking - * the `result` method. - * - * @tparam Elem the type of the elements added to the builder - * @tparam To the type of the collection the builder produces - * - * @author prokopec - */ -trait Combiner[-Elem, +To] extends Builder[Elem, To] with Sizing with Parallel with TaskSupport { - self: EnvironmentPassingCombiner[Elem, To] => - - type EPC = EnvironmentPassingCombiner[Elem, To] - - /** Combines the contents of the receiver builder and the `other` builder, - * producing a new builder containing both their elements. - * - * This method may combine the two builders by copying them into a larger collection, - * by producing a lazy view that gets evaluated once `result` is invoked, or use - * a merge operation specific to the data structure in question. - * - * Note that both the receiver builder and `other` builder become invalidated - * after the invocation of this method, and should be cleared (see `clear`) - * if they are to be used again. - * - * Also, combining two combiners `c1` and `c2` for which `c1 eq c2` is `true`, that is, - * they are the same objects in memories, always does nothing and returns the first combiner. - * - * @tparam N the type of elements contained by the `other` builder - * @tparam NewTo the type of collection produced by the `other` builder - * @param other the other builder - * @return the parallel builder containing both the elements of this and the `other` builder - */ - def combine[N <: Elem, NewTo >: To](other: Combiner[N, NewTo]): Combiner[N, NewTo] - -} - - -trait EnvironmentPassingCombiner[-Elem, +To] extends Combiner[Elem, To] { - abstract override def result = { - val res = super.result -// res.environment = environment - res - } -} - - - - - - - - - - diff --git a/src/library/scala/collection/parallel/Iterators.scala b/src/library/scala/collection/parallel/Iterators.scala deleted file mode 100644 index bfebff994c..0000000000 --- a/src/library/scala/collection/parallel/Iterators.scala +++ /dev/null @@ -1,443 +0,0 @@ -package scala.collection.parallel - - - -import scala.collection.Parallel -import scala.collection.generic.Signalling -import scala.collection.generic.DelegatedSignalling -import scala.collection.generic.CanCombineFrom -import scala.collection.mutable.Builder -import scala.collection.Iterator.empty - - - - - - -trait RemainsIterator[+T] extends Iterator[T] { - /** The number of elements this iterator has yet to iterate. - * This method doesn't change the state of the iterator. - */ - def remaining: Int -} - - -/** Augments iterators with additional methods, mostly transformers, - * assuming they iterate an iterable collection. - * - * @param T type of the elements iterated. - * @param Repr type of the collection iterator iterates. - */ -trait AugmentedIterableIterator[+T, +Repr <: Parallel] extends RemainsIterator[T] { - - def repr: Repr - - /* accessors */ - - override def count(p: T => Boolean): Int = { - var i = 0 - while (hasNext) if (p(next)) i += 1 - i - } - - def reduce[U >: T](op: (U, U) => U): U = { - var r: U = next - while (hasNext) r = op(r, next) - r - } - - def fold[U >: T](z: U)(op: (U, U) => U): U = { - var r = z - while (hasNext) r = op(r, next) - r - } - - override def sum[U >: T](implicit num: Numeric[U]): U = { - var r: U = num.zero - while (hasNext) r = num.plus(r, next) - r - } - - override def product[U >: T](implicit num: Numeric[U]): U = { - var r: U = num.one - while (hasNext) r = num.times(r, next) - r - } - - override def min[U >: T](implicit ord: Ordering[U]): T = { - var r = next - while (hasNext) { - val curr = next - if (ord.lteq(curr, r)) r = curr - } - r - } - - override def max[U >: T](implicit ord: Ordering[U]): T = { - var r = next - while (hasNext) { - val curr = next - if (ord.gteq(curr, r)) r = curr - } - r - } - - override def copyToArray[U >: T](array: Array[U], from: Int, len: Int) { - var i = from - val until = from + len - while (i < until && hasNext) { - array(i) = next - i += 1 - } - } - - /* transformers to combiners */ - - def map2combiner[S, That](f: T => S, cb: Combiner[S, That]): Combiner[S, That] = { - //val cb = pbf(repr) - cb.sizeHint(remaining) - while (hasNext) cb += f(next) - cb - } - - def collect2combiner[S, That](pf: PartialFunction[T, S], pbf: CanCombineFrom[Repr, S, That]): Combiner[S, That] = { - val cb = pbf(repr) - while (hasNext) { - val curr = next - if (pf.isDefinedAt(curr)) cb += pf(curr) - } - cb - } - - def flatmap2combiner[S, That](f: T => Traversable[S], pbf: CanCombineFrom[Repr, S, That]): Combiner[S, That] = { - val cb = pbf(repr) - while (hasNext) { - val traversable = f(next) - if (traversable.isInstanceOf[Iterable[_]]) cb ++= traversable.asInstanceOf[Iterable[S]].iterator - else cb ++= traversable - } - cb - } - - def copy2builder[U >: T, Coll, Bld <: Builder[U, Coll]](b: Bld): Bld = { - b.sizeHint(remaining) - while (hasNext) b += next - b - } - - def filter2combiner[U >: T, This >: Repr](pred: T => Boolean, cb: Combiner[U, This]): Combiner[U, This] = { - while (hasNext) { - val curr = next - if (pred(curr)) cb += curr - } - cb - } - - def filterNot2combiner[U >: T, This >: Repr](pred: T => Boolean, cb: Combiner[U, This]): Combiner[U, This] = { - while (hasNext) { - val curr = next - if (!pred(curr)) cb += curr - } - cb - } - - def partition2combiners[U >: T, This >: Repr](pred: T => Boolean, btrue: Combiner[U, This], bfalse: Combiner[U, This]) = { - while (hasNext) { - val curr = next - if (pred(curr)) btrue += curr - else bfalse += curr - } - (btrue, bfalse) - } - - def take2combiner[U >: T, This >: Repr](n: Int, cb: Combiner[U, This]): Combiner[U, This] = { - cb.sizeHint(n) - var left = n - while (left > 0) { - cb += next - left -= 1 - } - cb - } - - def drop2combiner[U >: T, This >: Repr](n: Int, cb: Combiner[U, This]): Combiner[U, This] = { - drop(n) - cb.sizeHint(remaining) - while (hasNext) cb += next - cb - } - - def slice2combiner[U >: T, This >: Repr](from: Int, until: Int, cb: Combiner[U, This]): Combiner[U, This] = { - drop(from) - var left = until - from - cb.sizeHint(left) - while (left > 0) { - cb += next - left -= 1 - } - cb - } - - def splitAt2combiners[U >: T, This >: Repr](at: Int, before: Combiner[U, This], after: Combiner[U, This]) = { - before.sizeHint(at) - after.sizeHint(remaining - at) - var left = at - while (left > 0) { - before += next - left -= 1 - } - while (hasNext) after += next - (before, after) - } - - def takeWhile2combiner[U >: T, This >: Repr](p: T => Boolean, cb: Combiner[U, This]) = { - var loop = true - while (hasNext && loop) { - val curr = next - if (p(curr)) cb += curr - else loop = false - } - (cb, loop) - } - - def span2combiners[U >: T, This >: Repr](p: T => Boolean, before: Combiner[U, This], after: Combiner[U, This]) = { - var isBefore = true - while (hasNext && isBefore) { - val curr = next - if (p(curr)) before += curr - else { - after.sizeHint(remaining + 1) - after += curr - isBefore = false - } - } - while (hasNext) after += next - (before, after) - } -} - - -trait AugmentedSeqIterator[+T, +Repr <: Parallel] extends AugmentedIterableIterator[T, Repr] { - - /** The exact number of elements this iterator has yet to iterate. - * This method doesn't change the state of the iterator. - */ - def remaining: Int - - /* accessors */ - - def prefixLength(pred: T => Boolean): Int = { - var total = 0 - var loop = true - while (hasNext && loop) { - if (pred(next)) total += 1 - else loop = false - } - total - } - - override def indexWhere(pred: T => Boolean): Int = { - var i = 0 - var loop = true - while (hasNext && loop) { - if (pred(next)) loop = false - else i += 1 - } - if (loop) -1 else i - } - - def lastIndexWhere(pred: T => Boolean): Int = { - var pos = -1 - var i = 0 - while (hasNext) { - if (pred(next)) pos = i - i += 1 - } - pos - } - - def corresponds[S](corr: (T, S) => Boolean)(that: Iterator[S]): Boolean = { - while (hasNext && that.hasNext) { - if (!corr(next, that.next)) return false - } - hasNext == that.hasNext - } - - /* transformers */ - - def reverse2combiner[U >: T, This >: Repr](cb: Combiner[U, This]): Combiner[U, This] = { - cb.sizeHint(remaining) - var lst = List[T]() - while (hasNext) lst ::= next - while (lst != Nil) { - cb += lst.head - lst = lst.tail - } - cb - } - - def reverseMap2combiner[S, That](f: T => S, cbf: CanCombineFrom[Repr, S, That]): Combiner[S, That] = { - val cb = cbf(repr) - cb.sizeHint(remaining) - var lst = List[S]() - while (hasNext) lst ::= f(next) - while (lst != Nil) { - cb += lst.head - lst = lst.tail - } - cb - } - - def updated2combiner[U >: T, That](index: Int, elem: U, cbf: CanCombineFrom[Repr, U, That]): Combiner[U, That] = { - val cb = cbf(repr) - cb.sizeHint(remaining) - var j = 0 - while (hasNext) { - if (j == index) { - cb += elem - next - } else cb += next - j += 1 - } - cb - } - -} - - - -trait ParallelIterableIterator[+T, +Repr <: Parallel] -extends AugmentedIterableIterator[T, Repr] - with Splitter[T] - with Signalling - with DelegatedSignalling -{ - def split: Seq[ParallelIterableIterator[T, Repr]] - - /** The number of elements this iterator has yet to traverse. This method - * doesn't change the state of the iterator. - * - * This method is used to provide size hints to builders and combiners, and - * to approximate positions of iterators within a data structure. - * - * '''Note''': This method may be implemented to return an upper bound on the number of elements - * in the iterator, instead of the exact number of elements to iterate. - * - * In that case, 2 considerations must be taken into account: - * - * 1) classes that inherit `ParallelIterable` must reimplement methods `take`, `drop`, `slice`, `splitAt` and `copyToArray`. - * - * 2) if an iterator provides an upper bound on the number of elements, then after splitting the sum - * of `remaining` values of split iterators must be less than or equal to this upper bound. - */ - def remaining: Int -} - - -trait ParallelSeqIterator[+T, +Repr <: Parallel] -extends ParallelIterableIterator[T, Repr] - with AugmentedSeqIterator[T, Repr] - with PreciseSplitter[T] -{ - def split: Seq[ParallelSeqIterator[T, Repr]] - def psplit(sizes: Int*): Seq[ParallelSeqIterator[T, Repr]] - - /** The number of elements this iterator has yet to traverse. This method - * doesn't change the state of the iterator. Unlike the version of this method in the supertrait, - * method `remaining` in `ParallelSeqLike.this.ParallelIterator` must return an exact number - * of elements remaining in the iterator. - * - * @return an exact number of elements this iterator has yet to iterate - */ - def remaining: Int -} - - -trait DelegatedIterator[+T, +Delegate <: Iterator[T]] extends RemainsIterator[T] { - val delegate: Delegate - def next = delegate.next - def hasNext = delegate.hasNext -} - - -trait Counting[+T] extends RemainsIterator[T] { - val initialSize: Int - def remaining = initialSize - traversed - var traversed = 0 - abstract override def next = { - val n = super.next - traversed += 1 - n - } -} - - -/** A mixin for iterators that traverse only filtered elements of a delegate. - */ -trait FilteredIterator[+T, +Delegate <: Iterator[T]] extends DelegatedIterator[T, Delegate] { - protected[this] val pred: T => Boolean - - private[this] var hd: T = _ - private var hdDefined = false - - override def hasNext: Boolean = hdDefined || { - do { - if (!delegate.hasNext) return false - hd = delegate.next - } while (!pred(hd)) - hdDefined = true - true - } - - override def next = if (hasNext) { hdDefined = false; hd } else empty.next -} - - -/** A mixin for iterators that traverse elements of the delegate iterator, and of another collection. - */ -trait AppendedIterator[+T, +Delegate <: Iterator[T]] extends DelegatedIterator[T, Delegate] { - // `rest` should never alias `delegate` - protected[this] val rest: Iterator[T] - - private[this] var current: Iterator[T] = delegate - - override def hasNext = (current.hasNext) || (current == delegate && rest.hasNext) - - override def next = { - if (!current.hasNext) current = rest - current.next - } - -} - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - diff --git a/src/library/scala/collection/parallel/Splitters.scala b/src/library/scala/collection/parallel/Splitters.scala deleted file mode 100644 index b3cad6d67a..0000000000 --- a/src/library/scala/collection/parallel/Splitters.scala +++ /dev/null @@ -1,86 +0,0 @@ -package scala.collection.parallel - - -import scala.collection.Seq - - -/** A splitter (or a split iterator) can be split into more splitters that traverse over - * disjoint subsets of elements. - * - * @tparam T type of the elements this parallel iterator traverses - * - * @since 2.8.1 - * @author prokopec - */ -trait Splitter[+T] extends Iterator[T] { - - /** Splits the iterator into a sequence of disjunct views. - * - * Returns a sequence of split iterators, each iterating over some subset of the - * elements in the collection. These subsets are disjoint and should be approximately - * equal in size. These subsets are not empty, unless the iterator is empty in which - * case this method returns a sequence with a single empty iterator. If the iterator has - * more than two elements, this method will return two or more iterators. - * - * Implementors are advised to keep this partition relatively small - two iterators are - * already enough when partitioning the collection, although there may be a few more. - * - * '''Note:''' this method actually invalidates the current iterator. - * - * @return a sequence of disjunct iterators of the collection - */ - def split: Seq[Splitter[T]] - -} - - -/** A precise splitter (or a precise split iterator) can be split into arbitrary number of splitters - * that traverse disjoint subsets of arbitrary sizes. - * - * Implementors might want to override the parameterless `split` method for efficiency. - * - * @tparam T type of the elements this parallel iterator traverses - * - * @since 2.8.1 - * @author prokopec - */ -trait PreciseSplitter[+T] extends Splitter[T] { - - /** Splits the iterator into disjunct views. - * - * This overloaded version of the `split` method is specific to precise parallel iterators. - * It returns a sequence of parallel iterators, each iterating some subset of the - * elements in this iterator. The sizes of the subiterators in the partition is equal to - * the size in the corresponding argument, as long as there are enough elements in this - * iterator to split it that way. - * - * If there aren't enough elements, a zero element iterator is appended for each additional argument. - * If there are additional elements, an additional iterator is appended at the end to compensate. - * - * For example, say we have a parallel iterator `ps` with 100 elements. Invoking: - * {{{ - * ps.split(50, 25, 25, 10, 5) - * }}} - * will return a sequence of five iterators, last two views being empty. On the other hand, calling: - * {{{ - * ps.split(50, 40) - * }}} - * will return a sequence of three iterators, last of them containing ten elements. - * - * '''Note:''' this method actually invalidates the current iterator. - * - * Unlike the case with `split` found in parallel iterable iterators, views returned by this method can be empty. - * - * @param sizes the sizes used to split this split iterator into iterators that traverse disjunct subsets - * @return a sequence of disjunct subsequence iterators of this parallel iterator - */ - def psplit(sizes: Int*): Seq[PreciseSplitter[T]] - - def split: Seq[PreciseSplitter[T]] - -} - - - - - diff --git a/src/library/scala/collection/parallel/immutable/ParallelIterable.scala b/src/library/scala/collection/parallel/immutable/ParallelIterable.scala deleted file mode 100644 index 92bf5ab706..0000000000 --- a/src/library/scala/collection/parallel/immutable/ParallelIterable.scala +++ /dev/null @@ -1,56 +0,0 @@ -package scala.collection.parallel.immutable - - -import scala.collection.generic._ - -import scala.collection.parallel.ParallelIterableLike -import scala.collection.parallel.Combiner - - - - - -// TODO uncomment when we add parallel vectors - -///** A template trait for immutable parallel iterable collections. -// * -// * $paralleliterableinfo -// * -// * $sideeffects -// * -// * @tparam A the element type of the collection -// * -// * @author prokopec -// * @since 2.8 -// */ -//trait ParallelIterable[A] extends collection.immutable.Iterable[A] -// with collection.parallel.ParallelIterable[A] -// with GenericParallelTemplate[A, ParallelIterable] -// with ParallelIterableLike[A, ParallelIterable[A], Iterable[A]] { -// override def companion: GenericCompanion[ParallelIterable] with GenericParallelCompanion[ParallelIterable] = ParallelIterable -//} -// -///** $factoryinfo -// */ -//object ParallelIterable extends ParallelFactory[ParallelIterable] { -// implicit def canBuildFrom[A]: CanBuildFromParallel[Coll, A, ParallelIterable[A]] = -// new GenericCanBuildFromParallel[A] -// -// def newBuilder[A]: Combiner[A, ParallelIterable[A]] = null // TODO -// -// def newCombiner[A]: Combiner[A, ParallelIterable[A]] = null // TODO -//} - - - - - - - - - - - - - - diff --git a/src/library/scala/collection/parallel/immutable/ParallelSeq.scala b/src/library/scala/collection/parallel/immutable/ParallelSeq.scala deleted file mode 100644 index ceb0dcc13d..0000000000 --- a/src/library/scala/collection/parallel/immutable/ParallelSeq.scala +++ /dev/null @@ -1,47 +0,0 @@ -package scala.collection.parallel.immutable - - -import scala.collection.generic.GenericParallelTemplate -import scala.collection.generic.GenericCompanion -import scala.collection.generic.GenericParallelCompanion -import scala.collection.generic.CanCombineFrom -import scala.collection.generic.ParallelFactory -import scala.collection.parallel.ParallelSeqLike -import scala.collection.parallel.Combiner - - - - - - -// TODO uncomment when we add parallel vectors - -///** An immutable variant of `ParallelSeq`. -// * -// * @define Coll mutable.ParallelSeq -// * @define coll mutable parallel sequence -// */ -//trait ParallelSeq[A] extends collection.immutable.IndexedSeq[A] -// with ParallelIterable[A] -// with collection.parallel.ParallelSeq[A] -// with GenericParallelTemplate[A, ParallelSeq] -// with ParallelSeqLike[A, ParallelSeq[A], Seq[A]] { -// override def companion: GenericCompanion[ParallelSeq] with GenericParallelCompanion[ParallelSeq] = ParallelSeq -// -//} -// -// -///** $factoryInfo -// * @define Coll mutable.ParallelSeq -// * @define coll mutable parallel sequence -// */ -//object ParallelSeq extends ParallelFactory[ParallelSeq] { -// implicit def canBuildFrom[T]: CanBuildFromParallel[Coll, T, ParallelSeq[T]] = new GenericCanBuildFromParallel[T] -// -// def newBuilder[A]: Combiner[A, ParallelSeq[A]] = null // TODO -// -// def newCombiner[A]: Combiner[A, ParallelSeq[A]] = null // TODO -//} - - - |