diff options
author | Aleksandar Prokopec <axel22@gmail.com> | 2012-06-28 19:48:31 +0200 |
---|---|---|
committer | Aleksandar Prokopec <axel22@gmail.com> | 2012-06-28 19:48:31 +0200 |
commit | b379ff4f59c139ff7d2b77e7e808f0b74aa9f268 (patch) | |
tree | d531663cc08c71cc2631c119403af3032c71b543 /src/library | |
parent | 2f0d94c02ab328a3f8da25b5ab8f402a68143af3 (diff) | |
parent | 6f08c06a35a0b70c49e23a296b13ac391a460584 (diff) | |
download | scala-b379ff4f59c139ff7d2b77e7e808f0b74aa9f268.tar.gz scala-b379ff4f59c139ff7d2b77e7e808f0b74aa9f268.tar.bz2 scala-b379ff4f59c139ff7d2b77e7e808f0b74aa9f268.zip |
Merge branch 'master' into issue/5846,4597,4027,4112
Conflicts:
src/library/scala/collection/MapLike.scala
src/library/scala/collection/SortedMapLike.scala
Diffstat (limited to 'src/library')
30 files changed, 442 insertions, 389 deletions
diff --git a/src/library/scala/collection/GenTraversableOnce.scala b/src/library/scala/collection/GenTraversableOnce.scala index eadacd9209..e475865391 100644 --- a/src/library/scala/collection/GenTraversableOnce.scala +++ b/src/library/scala/collection/GenTraversableOnce.scala @@ -9,6 +9,8 @@ package scala.collection import scala.reflect.ClassTag +import scala.collection.generic.CanBuildFrom +import scala.annotation.unchecked.{ uncheckedVariance => uV } /** A template trait for all traversable-once objects which may be * traversed in parallel. @@ -552,4 +554,21 @@ trait GenTraversableOnce[+A] extends Any { * containing all key/value pairs of type `(T, U)` of this $coll. */ def toMap[K, V](implicit ev: A <:< (K, V)): GenMap[K, V] + + /** Converts this $coll to a Vector. + * $willNotTerminateInf + * @return a vector containing all elements of this $coll. + */ + def toVector: Vector[A] + + /** Converts this $coll into another by copying all elements. + * @tparam Col The collection type to build. + * @return a new collection containing all elements of this $coll. + * + * @usecase def convertTo[Col[_]]: Col[A] + * @inheritdoc + * $willNotTerminateInf + * @return a new collection containing all elements of this $coll. + */ + def convertTo[Col[_]](implicit cbf: CanBuildFrom[Nothing, A, Col[A @uV]]): Col[A @uV] } diff --git a/src/library/scala/collection/IterableViewLike.scala b/src/library/scala/collection/IterableViewLike.scala index c842475590..e0c8b21d09 100644 --- a/src/library/scala/collection/IterableViewLike.scala +++ b/src/library/scala/collection/IterableViewLike.scala @@ -44,7 +44,7 @@ trait IterableViewLike[+A, } /** Explicit instantiation of the `Transformed` trait to reduce class file size in subclasses. */ - private[collection] abstract class AbstractTransformed[+B] extends super[TraversableViewLike].Transformed[B] with Transformed[B] + private[collection] abstract class AbstractTransformed[+B] extends Iterable[B] with super[TraversableViewLike].Transformed[B] with Transformed[B] trait EmptyView extends Transformed[Nothing] with super[TraversableViewLike].EmptyView with super[GenIterableViewLike].EmptyView diff --git a/src/library/scala/collection/Iterator.scala b/src/library/scala/collection/Iterator.scala index b2bbc8d888..5f369de3b7 100644 --- a/src/library/scala/collection/Iterator.scala +++ b/src/library/scala/collection/Iterator.scala @@ -11,6 +11,8 @@ package scala.collection import mutable.ArrayBuffer import annotation.migration import immutable.Stream +import scala.collection.generic.CanBuildFrom +import scala.annotation.unchecked.{ uncheckedVariance => uV } /** The `Iterator` object provides various functions for creating specialized iterators. * @@ -1138,6 +1140,7 @@ trait Iterator[+A] extends TraversableOnce[A] { def toStream: Stream[A] = if (self.hasNext) Stream.cons(self.next, self.toStream) else Stream.empty[A] + /** Converts this iterator to a string. * diff --git a/src/library/scala/collection/SeqViewLike.scala b/src/library/scala/collection/SeqViewLike.scala index f64045c9f6..73f5dda11c 100644 --- a/src/library/scala/collection/SeqViewLike.scala +++ b/src/library/scala/collection/SeqViewLike.scala @@ -40,7 +40,7 @@ trait SeqViewLike[+A, } /** Explicit instantiation of the `Transformed` trait to reduce class file size in subclasses. */ - private[collection] abstract class AbstractTransformed[+B] extends super[IterableViewLike].AbstractTransformed[B] with Transformed[B] + private[collection] abstract class AbstractTransformed[+B] extends Seq[B] with super[IterableViewLike].Transformed[B] with Transformed[B] trait EmptyView extends Transformed[Nothing] with super[IterableViewLike].EmptyView with super[GenSeqViewLike].EmptyView diff --git a/src/library/scala/collection/SortedMapLike.scala b/src/library/scala/collection/SortedMapLike.scala index 1bef703053..f9e95230ea 100644 --- a/src/library/scala/collection/SortedMapLike.scala +++ b/src/library/scala/collection/SortedMapLike.scala @@ -83,6 +83,14 @@ self => override def rangeImpl(from : Option[A], until : Option[A]): SortedMap[A, C] = self.rangeImpl(from, until).mapValues(f) } + /** Adds a number of elements provided by a traversable object + * and returns a new collection with the added elements. + * + * @param xs the traversable object. + */ + override def ++[B1 >: B](xs: GenTraversableOnce[(A, B1)]): SortedMap[A, B1] = + ((repr: SortedMap[A, B1]) /: xs.seq) (_ + _) + } diff --git a/src/library/scala/collection/TraversableLike.scala b/src/library/scala/collection/TraversableLike.scala index 3716a318d9..e5861f5760 100644 --- a/src/library/scala/collection/TraversableLike.scala +++ b/src/library/scala/collection/TraversableLike.scala @@ -616,6 +616,13 @@ trait TraversableLike[+A, +Repr] extends Any def toTraversable: Traversable[A] = thisCollection def toIterator: Iterator[A] = toStream.iterator def toStream: Stream[A] = toBuffer.toStream + // Override to provide size hint. + override def convertTo[Col[_]](implicit cbf: CanBuildFrom[Nothing, A, Col[A @uV]]): Col[A @uV] = { + val b = cbf() + b.sizeHint(this) + b ++= thisCollection + b.result + } /** Converts this $coll to a string. * diff --git a/src/library/scala/collection/TraversableOnce.scala b/src/library/scala/collection/TraversableOnce.scala index 386ce2d95a..8dc6184d88 100644 --- a/src/library/scala/collection/TraversableOnce.scala +++ b/src/library/scala/collection/TraversableOnce.scala @@ -9,6 +9,7 @@ package scala.collection import mutable.{ Buffer, Builder, ListBuffer, ArrayBuffer } +import generic.CanBuildFrom import annotation.unchecked.{ uncheckedVariance => uV } import language.{implicitConversions, higherKinds} import reflect.ClassTag @@ -239,17 +240,25 @@ trait TraversableOnce[+A] extends Any with GenTraversableOnce[A] { def toTraversable: Traversable[A] - def toList: List[A] = (new ListBuffer[A] ++= seq).toList + def toList: List[A] = convertTo[List] def toIterable: Iterable[A] = toStream def toSeq: Seq[A] = toStream - def toIndexedSeq: immutable.IndexedSeq[A] = immutable.IndexedSeq() ++ seq + def toIndexedSeq: immutable.IndexedSeq[A] = convertTo[immutable.IndexedSeq] - def toBuffer[B >: A]: mutable.Buffer[B] = new ArrayBuffer[B] ++= seq + def toBuffer[B >: A]: mutable.Buffer[B] = convertTo[ArrayBuffer].asInstanceOf[mutable.Buffer[B]] - def toSet[B >: A]: immutable.Set[B] = immutable.Set() ++ seq + def toSet[B >: A]: immutable.Set[B] = convertTo[immutable.Set].asInstanceOf[immutable.Set[B]] + + def toVector: Vector[A] = convertTo[Vector] + + def convertTo[Col[_]](implicit cbf: CanBuildFrom[Nothing, A, Col[A @uV]]): Col[A @uV] = { + val b = cbf() + b ++= seq + b.result + } def toMap[T, U](implicit ev: A <:< (T, U)): immutable.Map[T, U] = { val b = immutable.Map.newBuilder[T, U] diff --git a/src/library/scala/collection/TraversableViewLike.scala b/src/library/scala/collection/TraversableViewLike.scala index eb2091a5f3..bf4f8205d6 100644 --- a/src/library/scala/collection/TraversableViewLike.scala +++ b/src/library/scala/collection/TraversableViewLike.scala @@ -117,7 +117,7 @@ trait TraversableViewLike[+A, } /** Explicit instantiation of the `Transformed` trait to reduce class file size in subclasses. */ - private[collection] abstract class AbstractTransformed[+B] extends Transformed[B] + private[collection] abstract class AbstractTransformed[+B] extends Traversable[B] with Transformed[B] trait EmptyView extends Transformed[Nothing] with super.EmptyView diff --git a/src/library/scala/collection/concurrent/TrieMap.scala b/src/library/scala/collection/concurrent/TrieMap.scala index 08e9125bd8..2d8217551a 100644 --- a/src/library/scala/collection/concurrent/TrieMap.scala +++ b/src/library/scala/collection/concurrent/TrieMap.scala @@ -473,7 +473,11 @@ extends CNodeBase[K, V] { private def computeSize(ct: TrieMap[K, V]): Int = { var i = 0 var sz = 0 - val offset = math.abs(util.Random.nextInt()) % array.length + val offset = + if (array.length > 0) + //util.Random.nextInt(array.length) /* <-- benchmarks show that this causes observable contention */ + scala.concurrent.forkjoin.ThreadLocalRandom.current.nextInt(0, array.length) + else 0 while (i < array.length) { val pos = (i + offset) % array.length array(pos) match { diff --git a/src/library/scala/collection/immutable/IntMap.scala b/src/library/scala/collection/immutable/IntMap.scala index 039a57041c..e895c94599 100644 --- a/src/library/scala/collection/immutable/IntMap.scala +++ b/src/library/scala/collection/immutable/IntMap.scala @@ -18,17 +18,17 @@ import scala.collection.mutable.{ Builder, MapBuilder } private[immutable] object IntMapUtils extends BitOperations.Int { def branchMask(i: Int, j: Int) = highestOneBit(i ^ j) - def join[T](p1 : Int, t1 : IntMap[T], p2 : Int, t2 : IntMap[T]) : IntMap[T] = { - val m = branchMask(p1, p2); - val p = mask(p1, m); + def join[T](p1: Int, t1: IntMap[T], p2: Int, t2: IntMap[T]): IntMap[T] = { + val m = branchMask(p1, p2) + val p = mask(p1, m) if (zero(p1, m)) IntMap.Bin(p, m, t1, t2) - else IntMap.Bin(p, m, t2, t1); + else IntMap.Bin(p, m, t2, t1) } - def bin[T](prefix : Int, mask : Int, left : IntMap[T], right : IntMap[T]) : IntMap[T] = (left, right) match { - case (left, IntMap.Nil) => left; - case (IntMap.Nil, right) => right; - case (left, right) => IntMap.Bin(prefix, mask, left, right); + def bin[T](prefix: Int, mask: Int, left: IntMap[T], right: IntMap[T]): IntMap[T] = (left, right) match { + case (left, IntMap.Nil) => left + case (IntMap.Nil, right) => right + case (left, right) => IntMap.Bin(prefix, mask, left, right) } } @@ -50,9 +50,9 @@ object IntMap { } def empty[T] : IntMap[T] = IntMap.Nil; - def singleton[T](key : Int, value : T) : IntMap[T] = IntMap.Tip(key, value); - def apply[T](elems : (Int, T)*) : IntMap[T] = - elems.foldLeft(empty[T])((x, y) => x.updated(y._1, y._2)); + def singleton[T](key: Int, value: T): IntMap[T] = IntMap.Tip(key, value); + def apply[T](elems: (Int, T)*): IntMap[T] = + elems.foldLeft(empty[T])((x, y) => x.updated(y._1, y._2)) private[immutable] case object Nil extends IntMap[Nothing] { // Important! Without this equals method in place, an infinite @@ -66,15 +66,15 @@ object IntMap { } } - private[immutable] case class Tip[+T](key : Int, value : T) extends IntMap[T]{ + private[immutable] case class Tip[+T](key: Int, value: T) extends IntMap[T]{ def withValue[S](s: S) = - if (s.asInstanceOf[AnyRef] eq value.asInstanceOf[AnyRef]) this.asInstanceOf[IntMap.Tip[S]]; - else IntMap.Tip(key, s); + if (s.asInstanceOf[AnyRef] eq value.asInstanceOf[AnyRef]) this.asInstanceOf[IntMap.Tip[S]] + else IntMap.Tip(key, s) } - private[immutable] case class Bin[+T](prefix : Int, mask : Int, left : IntMap[T], right : IntMap[T]) extends IntMap[T]{ - def bin[S](left : IntMap[S], right : IntMap[S]) : IntMap[S] = { - if ((this.left eq left) && (this.right eq right)) this.asInstanceOf[IntMap.Bin[S]]; - else IntMap.Bin[S](prefix, mask, left, right); + private[immutable] case class Bin[+T](prefix: Int, mask: Int, left: IntMap[T], right: IntMap[T]) extends IntMap[T] { + def bin[S](left: IntMap[S], right: IntMap[S]): IntMap[S] = { + if ((this.left eq left) && (this.right eq right)) this.asInstanceOf[IntMap.Bin[S]] + else IntMap.Bin[S](prefix, mask, left, right) } } @@ -83,60 +83,60 @@ object IntMap { import IntMap._ // Iterator over a non-empty IntMap. -private[immutable] abstract class IntMapIterator[V, T](it : IntMap[V]) extends AbstractIterator[T] { +private[immutable] abstract class IntMapIterator[V, T](it: IntMap[V]) extends AbstractIterator[T] { // Basically this uses a simple stack to emulate conversion over the tree. However // because we know that Ints are at least 32 bits we can have at most 32 IntMap.Bins and // one IntMap.Tip sitting on the tree at any point. Therefore we know the maximum stack // depth is 33 and - var index = 0; - var buffer = new Array[AnyRef](33); + var index = 0 + var buffer = new Array[AnyRef](33) def pop = { - index -= 1; - buffer(index).asInstanceOf[IntMap[V]]; + index -= 1 + buffer(index).asInstanceOf[IntMap[V]] } - def push(x : IntMap[V]) { - buffer(index) = x.asInstanceOf[AnyRef]; - index += 1; + def push(x: IntMap[V]) { + buffer(index) = x.asInstanceOf[AnyRef] + index += 1 } - push(it); + push(it) /** * What value do we assign to a tip? */ - def valueOf(tip : IntMap.Tip[V]) : T; + def valueOf(tip: IntMap.Tip[V]): T - def hasNext = index != 0; - final def next : T = + def hasNext = index != 0 + final def next: T = pop match { case IntMap.Bin(_,_, t@IntMap.Tip(_, _), right) => { - push(right); - valueOf(t); + push(right) + valueOf(t) } case IntMap.Bin(_, _, left, right) => { - push(right); - push(left); - next; + push(right) + push(left) + next } - case t@IntMap.Tip(_, _) => valueOf(t); + case t@IntMap.Tip(_, _) => valueOf(t) // This should never happen. We don't allow IntMap.Nil in subtrees of the IntMap // and don't return an IntMapIterator for IntMap.Nil. - case IntMap.Nil => sys.error("Empty maps not allowed as subtrees"); + case IntMap.Nil => sys.error("Empty maps not allowed as subtrees") } } -private[immutable] class IntMapEntryIterator[V](it : IntMap[V]) extends IntMapIterator[V, (Int, V)](it){ - def valueOf(tip : IntMap.Tip[V]) = (tip.key, tip.value); +private[immutable] class IntMapEntryIterator[V](it: IntMap[V]) extends IntMapIterator[V, (Int, V)](it) { + def valueOf(tip: IntMap.Tip[V]) = (tip.key, tip.value) } -private[immutable] class IntMapValueIterator[V](it : IntMap[V]) extends IntMapIterator[V, V](it){ - def valueOf(tip : IntMap.Tip[V]) = tip.value +private[immutable] class IntMapValueIterator[V](it: IntMap[V]) extends IntMapIterator[V, V](it) { + def valueOf(tip: IntMap.Tip[V]) = tip.value } -private[immutable] class IntMapKeyIterator[V](it : IntMap[V]) extends IntMapIterator[V, Int](it){ - def valueOf(tip : IntMap.Tip[V]) = tip.key +private[immutable] class IntMapKeyIterator[V](it: IntMap[V]) extends IntMapIterator[V, Int](it) { + def valueOf(tip: IntMap.Tip[V]) = tip.key } import IntMap._ @@ -145,7 +145,7 @@ import IntMap._ * <a href="http://citeseer.ist.psu.edu/okasaki98fast.html">Fast Mergeable Integer Maps</a> * by Okasaki and Gill. Essentially a trie based on binary digits of the integers. * - * Note: This class is as of 2.8 largely superseded by HashMap. + * '''Note:''' This class is as of 2.8 largely superseded by HashMap. * * @tparam T type of the values associated with integer keys. * @@ -155,17 +155,16 @@ import IntMap._ * @define mayNotTerminateInf * @define willNotTerminateInf */ -sealed abstract class IntMap[+T] -extends AbstractMap[Int, T] +sealed abstract class IntMap[+T] extends AbstractMap[Int, T] with Map[Int, T] with MapLike[Int, T, IntMap[T]] { - override def empty: IntMap[T] = IntMap.Nil; + override def empty: IntMap[T] = IntMap.Nil override def toList = { - val buffer = new scala.collection.mutable.ListBuffer[(Int, T)]; - foreach(buffer += _); - buffer.toList; + val buffer = new scala.collection.mutable.ListBuffer[(Int, T)] + foreach(buffer += _) + buffer.toList } /** @@ -173,109 +172,112 @@ extends AbstractMap[Int, T] * * @return an iterator over pairs of integer keys and corresponding values. */ - def iterator : Iterator[(Int, T)] = this match { - case IntMap.Nil => Iterator.empty; - case _ => new IntMapEntryIterator(this); + def iterator: Iterator[(Int, T)] = this match { + case IntMap.Nil => Iterator.empty + case _ => new IntMapEntryIterator(this) } /** * Loops over the key, value pairs of the map in unsigned order of the keys. */ - override final def foreach[U](f : ((Int, T)) => U) : Unit = this match { - case IntMap.Bin(_, _, left, right) => {left.foreach(f); right.foreach(f); } - case IntMap.Tip(key, value) => f((key, value)); - case IntMap.Nil => {}; + override final def foreach[U](f: ((Int, T)) => U): Unit = this match { + case IntMap.Bin(_, _, left, right) => { left.foreach(f); right.foreach(f) } + case IntMap.Tip(key, value) => f((key, value)) + case IntMap.Nil => } - override def keysIterator : Iterator[Int] = this match { - case IntMap.Nil => Iterator.empty; - case _ => new IntMapKeyIterator(this); + override def keysIterator: Iterator[Int] = this match { + case IntMap.Nil => Iterator.empty + case _ => new IntMapKeyIterator(this) } /** - * Loop over the keys of the map. The same as keys.foreach(f), but may + * Loop over the keys of the map. The same as `keys.foreach(f)`, but may * be more efficient. * * @param f The loop body */ - final def foreachKey(f : Int => Unit) : Unit = this match { - case IntMap.Bin(_, _, left, right) => {left.foreachKey(f); right.foreachKey(f); } - case IntMap.Tip(key, _) => f(key); - case IntMap.Nil => {} + final def foreachKey(f: Int => Unit): Unit = this match { + case IntMap.Bin(_, _, left, right) => { left.foreachKey(f); right.foreachKey(f) } + case IntMap.Tip(key, _) => f(key) + case IntMap.Nil => } - override def valuesIterator : Iterator[T] = this match { - case IntMap.Nil => Iterator.empty; - case _ => new IntMapValueIterator(this); + override def valuesIterator: Iterator[T] = this match { + case IntMap.Nil => Iterator.empty + case _ => new IntMapValueIterator(this) } /** - * Loop over the keys of the map. The same as keys.foreach(f), but may + * Loop over the keys of the map. The same as `keys.foreach(f)`, but may * be more efficient. * * @param f The loop body */ - final def foreachValue(f : T => Unit) : Unit = this match { - case IntMap.Bin(_, _, left, right) => {left.foreachValue(f); right.foreachValue(f); } - case IntMap.Tip(_, value) => f(value); - case IntMap.Nil => {}; + final def foreachValue(f: T => Unit): Unit = this match { + case IntMap.Bin(_, _, left, right) => { left.foreachValue(f); right.foreachValue(f) } + case IntMap.Tip(_, value) => f(value) + case IntMap.Nil => } override def stringPrefix = "IntMap" - override def isEmpty = this == IntMap.Nil; + override def isEmpty = this == IntMap.Nil - override def filter(f : ((Int, T)) => Boolean) : IntMap[T] = this match { + override def filter(f: ((Int, T)) => Boolean): IntMap[T] = this match { case IntMap.Bin(prefix, mask, left, right) => { - val (newleft, newright) = (left.filter(f), right.filter(f)); - if ((left eq newleft) && (right eq newright)) this; - else bin(prefix, mask, newleft, newright); + val (newleft, newright) = (left.filter(f), right.filter(f)) + if ((left eq newleft) && (right eq newright)) this + else bin(prefix, mask, newleft, newright) } case IntMap.Tip(key, value) => if (f((key, value))) this - else IntMap.Nil; - case IntMap.Nil => IntMap.Nil; + else IntMap.Nil + case IntMap.Nil => IntMap.Nil } - def transform[S](f : (Int, T) => S) : IntMap[S] = this match { - case b@IntMap.Bin(prefix, mask, left, right) => b.bin(left.transform(f), right.transform(f)); - case t@IntMap.Tip(key, value) => t.withValue(f(key, value)); - case IntMap.Nil => IntMap.Nil; + def transform[S](f: (Int, T) => S): IntMap[S] = this match { + case b@IntMap.Bin(prefix, mask, left, right) => b.bin(left.transform(f), right.transform(f)) + case t@IntMap.Tip(key, value) => t.withValue(f(key, value)) + case IntMap.Nil => IntMap.Nil } - final override def size : Int = this match { - case IntMap.Nil => 0; - case IntMap.Tip(_, _) => 1; - case IntMap.Bin(_, _, left, right) => left.size + right.size; + final override def size: Int = this match { + case IntMap.Nil => 0 + case IntMap.Tip(_, _) => 1 + case IntMap.Bin(_, _, left, right) => left.size + right.size } - final def get(key : Int) : Option[T] = this match { - case IntMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left.get(key) else right.get(key); - case IntMap.Tip(key2, value) => if (key == key2) Some(value) else None; - case IntMap.Nil => None; + final def get(key: Int): Option[T] = this match { + case IntMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left.get(key) else right.get(key) + case IntMap.Tip(key2, value) => if (key == key2) Some(value) else None + case IntMap.Nil => None } - final override def getOrElse[S >: T](key : Int, default : =>S) : S = this match { - case IntMap.Nil => default; - case IntMap.Tip(key2, value) => if (key == key2) value else default; - case IntMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left.getOrElse(key, default) else right.getOrElse(key, default); + final override def getOrElse[S >: T](key: Int, default: => S): S = this match { + case IntMap.Nil => default + case IntMap.Tip(key2, value) => if (key == key2) value else default + case IntMap.Bin(prefix, mask, left, right) => + if (zero(key, mask)) left.getOrElse(key, default) else right.getOrElse(key, default) } - final override def apply(key : Int) : T = this match { - case IntMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left(key) else right(key); - case IntMap.Tip(key2, value) => if (key == key2) value else sys.error("Key not found"); - case IntMap.Nil => sys.error("key not found"); + final override def apply(key: Int): T = this match { + case IntMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left(key) else right(key) + case IntMap.Tip(key2, value) => if (key == key2) value else sys.error("Key not found") + case IntMap.Nil => sys.error("key not found") } def + [S >: T] (kv: (Int, S)): IntMap[S] = updated(kv._1, kv._2) - override def updated[S >: T](key : Int, value : S) : IntMap[S] = this match { - case IntMap.Bin(prefix, mask, left, right) => if (!hasMatch(key, prefix, mask)) join(key, IntMap.Tip(key, value), prefix, this); - else if (zero(key, mask)) IntMap.Bin(prefix, mask, left.updated(key, value), right) - else IntMap.Bin(prefix, mask, left, right.updated(key, value)); - case IntMap.Tip(key2, value2) => if (key == key2) IntMap.Tip(key, value); - else join(key, IntMap.Tip(key, value), key2, this); - case IntMap.Nil => IntMap.Tip(key, value); + override def updated[S >: T](key: Int, value: S): IntMap[S] = this match { + case IntMap.Bin(prefix, mask, left, right) => + if (!hasMatch(key, prefix, mask)) join(key, IntMap.Tip(key, value), prefix, this) + else if (zero(key, mask)) IntMap.Bin(prefix, mask, left.updated(key, value), right) + else IntMap.Bin(prefix, mask, left, right.updated(key, value)) + case IntMap.Tip(key2, value2) => + if (key == key2) IntMap.Tip(key, value) + else join(key, IntMap.Tip(key, value), key2, this) + case IntMap.Nil => IntMap.Tip(key, value) } /** @@ -284,7 +286,7 @@ extends AbstractMap[Int, T] * Equivalent to: * {{{ * this.get(key) match { - * case None => this.update(key, value); + * case None => this.update(key, value) * case Some(oldvalue) => this.update(key, f(oldvalue, value) * } * }}} @@ -295,24 +297,26 @@ extends AbstractMap[Int, T] * @param f The function used to resolve conflicts. * @return The updated map. */ - def updateWith[S >: T](key : Int, value : S, f : (T, S) => S) : IntMap[S] = this match { - case IntMap.Bin(prefix, mask, left, right) => if (!hasMatch(key, prefix, mask)) join(key, IntMap.Tip(key, value), prefix, this); - else if (zero(key, mask)) IntMap.Bin(prefix, mask, left.updateWith(key, value, f), right) - else IntMap.Bin(prefix, mask, left, right.updateWith(key, value, f)); - case IntMap.Tip(key2, value2) => if (key == key2) IntMap.Tip(key, f(value2, value)); - else join(key, IntMap.Tip(key, value), key2, this); - case IntMap.Nil => IntMap.Tip(key, value); + def updateWith[S >: T](key: Int, value: S, f: (T, S) => S): IntMap[S] = this match { + case IntMap.Bin(prefix, mask, left, right) => + if (!hasMatch(key, prefix, mask)) join(key, IntMap.Tip(key, value), prefix, this) + else if (zero(key, mask)) IntMap.Bin(prefix, mask, left.updateWith(key, value, f), right) + else IntMap.Bin(prefix, mask, left, right.updateWith(key, value, f)) + case IntMap.Tip(key2, value2) => + if (key == key2) IntMap.Tip(key, f(value2, value)) + else join(key, IntMap.Tip(key, value), key2, this) + case IntMap.Nil => IntMap.Tip(key, value) } - def - (key : Int) : IntMap[T] = this match { + def - (key: Int): IntMap[T] = this match { case IntMap.Bin(prefix, mask, left, right) => - if (!hasMatch(key, prefix, mask)) this; - else if (zero(key, mask)) bin(prefix, mask, left - key, right); - else bin(prefix, mask, left, right - key); + if (!hasMatch(key, prefix, mask)) this + else if (zero(key, mask)) bin(prefix, mask, left - key, right) + else bin(prefix, mask, left, right - key) case IntMap.Tip(key2, _) => - if (key == key2) IntMap.Nil; - else this; - case IntMap.Nil => IntMap.Nil; + if (key == key2) IntMap.Nil + else this + case IntMap.Nil => IntMap.Nil } /** @@ -324,7 +328,7 @@ extends AbstractMap[Int, T] * @param f The transforming function. * @return The modified map. */ - def modifyOrRemove[S](f : (Int, T) => Option[S]) : IntMap[S] = this match { + def modifyOrRemove[S](f: (Int, T) => Option[S]): IntMap[S] = this match { case IntMap.Bin(prefix, mask, left, right) => val newleft = left.modifyOrRemove(f) val newright = right.modifyOrRemove(f) @@ -350,25 +354,25 @@ extends AbstractMap[Int, T] * @param f The function used to resolve conflicts between two mappings. * @return Union of `this` and `that`, with identical key conflicts resolved using the function `f`. */ - def unionWith[S >: T](that : IntMap[S], f : (Int, S, S) => S) : IntMap[S] = (this, that) match{ + def unionWith[S >: T](that: IntMap[S], f: (Int, S, S) => S): IntMap[S] = (this, that) match{ case (IntMap.Bin(p1, m1, l1, r1), that@(IntMap.Bin(p2, m2, l2, r2))) => if (shorter(m1, m2)) { - if (!hasMatch(p2, p1, m1)) join[S](p1, this, p2, that); // TODO: remove [S] when SI-5548 is fixed - else if (zero(p2, m1)) IntMap.Bin(p1, m1, l1.unionWith(that, f), r1); - else IntMap.Bin(p1, m1, l1, r1.unionWith(that, f)); + if (!hasMatch(p2, p1, m1)) join[S](p1, this, p2, that) // TODO: remove [S] when SI-5548 is fixed + else if (zero(p2, m1)) IntMap.Bin(p1, m1, l1.unionWith(that, f), r1) + else IntMap.Bin(p1, m1, l1, r1.unionWith(that, f)) } else if (shorter(m2, m1)){ - if (!hasMatch(p1, p2, m2)) join[S](p1, this, p2, that); // TODO: remove [S] when SI-5548 is fixed - else if (zero(p1, m2)) IntMap.Bin(p2, m2, this.unionWith(l2, f), r2); - else IntMap.Bin(p2, m2, l2, this.unionWith(r2, f)); + if (!hasMatch(p1, p2, m2)) join[S](p1, this, p2, that) // TODO: remove [S] when SI-5548 is fixed + else if (zero(p1, m2)) IntMap.Bin(p2, m2, this.unionWith(l2, f), r2) + else IntMap.Bin(p2, m2, l2, this.unionWith(r2, f)) } else { - if (p1 == p2) IntMap.Bin(p1, m1, l1.unionWith(l2,f), r1.unionWith(r2, f)); - else join[S](p1, this, p2, that); // TODO: remove [S] when SI-5548 is fixed + if (p1 == p2) IntMap.Bin(p1, m1, l1.unionWith(l2,f), r1.unionWith(r2, f)) + else join[S](p1, this, p2, that) // TODO: remove [S] when SI-5548 is fixed } - case (IntMap.Tip(key, value), x) => x.updateWith[S](key, value, (x, y) => f(key, y, x)); - case (x, IntMap.Tip(key, value)) => x.updateWith[S](key, value, (x, y) => f(key, x, y)); - case (IntMap.Nil, x) => x; - case (x, IntMap.Nil) => x; + case (IntMap.Tip(key, value), x) => x.updateWith[S](key, value, (x, y) => f(key, y, x)) + case (x, IntMap.Tip(key, value)) => x.updateWith[S](key, value, (x, y) => f(key, x, y)) + case (IntMap.Nil, x) => x + case (x, IntMap.Nil) => x } /** @@ -382,13 +386,13 @@ extends AbstractMap[Int, T] * @param f The combining function. * @return Intersection of `this` and `that`, with values for identical keys produced by function `f`. */ - def intersectionWith[S, R](that : IntMap[S], f : (Int, T, S) => R) : IntMap[R] = (this, that) match { + def intersectionWith[S, R](that: IntMap[S], f: (Int, T, S) => R): IntMap[R] = (this, that) match { case (IntMap.Bin(p1, m1, l1, r1), that@IntMap.Bin(p2, m2, l2, r2)) => if (shorter(m1, m2)) { if (!hasMatch(p2, p1, m1)) IntMap.Nil else if (zero(p2, m1)) l1.intersectionWith(that, f) else r1.intersectionWith(that, f) - } else if (m1 == m2) bin(p1, m1, l1.intersectionWith(l2, f), r1.intersectionWith(r2, f)); + } else if (m1 == m2) bin(p1, m1, l1.intersectionWith(l2, f), r1.intersectionWith(r2, f)) else { if (!hasMatch(p1, p2, m2)) IntMap.Nil else if (zero(p1, m2)) this.intersectionWith(l2, f) @@ -413,15 +417,16 @@ extends AbstractMap[Int, T] * @param that The map to intersect with. * @return A map with all the keys both in `this` and `that`, mapped to corresponding values from `this`. */ - def intersection[R](that : IntMap[R]) : IntMap[T] = this.intersectionWith(that, (key : Int, value : T, value2 : R) => value); + def intersection[R](that: IntMap[R]): IntMap[T] = + this.intersectionWith(that, (key: Int, value: T, value2: R) => value) - def ++[S >: T](that : IntMap[S]) = + def ++[S >: T](that: IntMap[S]) = this.unionWith[S](that, (key, x, y) => y) /** * The entry with the lowest key value considered in unsigned order. */ - final def firstKey : Int = this match { + final def firstKey: Int = this match { case Bin(_, _, l, r) => l.firstKey case Tip(k, v) => k case IntMap.Nil => sys.error("Empty set") @@ -430,7 +435,7 @@ extends AbstractMap[Int, T] /** * The entry with the highest key value considered in unsigned order. */ - final def lastKey : Int = this match { + final def lastKey: Int = this match { case Bin(_, _, l, r) => r.lastKey case Tip(k, v) => k case IntMap.Nil => sys.error("Empty set") diff --git a/src/library/scala/collection/immutable/LongMap.scala b/src/library/scala/collection/immutable/LongMap.scala index 8a316f37de..002027b162 100644 --- a/src/library/scala/collection/immutable/LongMap.scala +++ b/src/library/scala/collection/immutable/LongMap.scala @@ -18,17 +18,17 @@ import scala.collection.mutable.{ Builder, MapBuilder } private[immutable] object LongMapUtils extends BitOperations.Long { def branchMask(i: Long, j: Long) = highestOneBit(i ^ j) - def join[T](p1 : Long, t1 : LongMap[T], p2 : Long, t2 : LongMap[T]) : LongMap[T] = { - val m = branchMask(p1, p2); - val p = mask(p1, m); + def join[T](p1: Long, t1: LongMap[T], p2: Long, t2: LongMap[T]): LongMap[T] = { + val m = branchMask(p1, p2) + val p = mask(p1, m) if (zero(p1, m)) LongMap.Bin(p, m, t1, t2) - else LongMap.Bin(p, m, t2, t1); + else LongMap.Bin(p, m, t2, t1) } - def bin[T](prefix : Long, mask : Long, left : LongMap[T], right : LongMap[T]) : LongMap[T] = (left, right) match { - case (left, LongMap.Nil) => left; - case (LongMap.Nil, right) => right; - case (left, right) => LongMap.Bin(prefix, mask, left, right); + def bin[T](prefix: Long, mask: Long, left: LongMap[T], right: LongMap[T]): LongMap[T] = (left, right) match { + case (left, LongMap.Nil) => left + case (LongMap.Nil, right) => right + case (left, right) => LongMap.Bin(prefix, mask, left, right) } } @@ -49,29 +49,29 @@ object LongMap { def apply(): Builder[(Long, B), LongMap[B]] = new MapBuilder[Long, B, LongMap[B]](empty[B]) } - def empty[T] : LongMap[T] = LongMap.Nil; - def singleton[T](key : Long, value : T) : LongMap[T] = LongMap.Tip(key, value); - def apply[T](elems : (Long, T)*) : LongMap[T] = - elems.foldLeft(empty[T])((x, y) => x.updated(y._1, y._2)); + def empty[T]: LongMap[T] = LongMap.Nil + def singleton[T](key: Long, value: T): LongMap[T] = LongMap.Tip(key, value) + def apply[T](elems: (Long, T)*): LongMap[T] = + elems.foldLeft(empty[T])((x, y) => x.updated(y._1, y._2)) private[immutable] case object Nil extends LongMap[Nothing] { // Important, don't remove this! See IntMap for explanation. override def equals(that : Any) = that match { - case (that : AnyRef) if (this eq that) => true; - case (that : LongMap[_]) => false; // The only empty LongMaps are eq Nil - case that => super.equals(that); + case (that: AnyRef) if (this eq that) => true + case (that: LongMap[_]) => false // The only empty LongMaps are eq Nil + case that => super.equals(that) } - }; + } - private[immutable] case class Tip[+T](key : Long, value : T) extends LongMap[T]{ - def withValue[S](s : S) = - if (s.asInstanceOf[AnyRef] eq value.asInstanceOf[AnyRef]) this.asInstanceOf[LongMap.Tip[S]]; - else LongMap.Tip(key, s); + private[immutable] case class Tip[+T](key: Long, value: T) extends LongMap[T] { + def withValue[S](s: S) = + if (s.asInstanceOf[AnyRef] eq value.asInstanceOf[AnyRef]) this.asInstanceOf[LongMap.Tip[S]] + else LongMap.Tip(key, s) } - private[immutable] case class Bin[+T](prefix : Long, mask : Long, left : LongMap[T], right : LongMap[T]) extends LongMap[T]{ - def bin[S](left : LongMap[S], right : LongMap[S]) : LongMap[S] = { - if ((this.left eq left) && (this.right eq right)) this.asInstanceOf[LongMap.Bin[S]]; - else LongMap.Bin[S](prefix, mask, left, right); + private[immutable] case class Bin[+T](prefix: Long, mask: Long, left: LongMap[T], right: LongMap[T]) extends LongMap[T] { + def bin[S](left: LongMap[S], right: LongMap[S]): LongMap[S] = { + if ((this.left eq left) && (this.right eq right)) this.asInstanceOf[LongMap.Bin[S]] + else LongMap.Bin[S](prefix, mask, left, right) } } } @@ -79,64 +79,62 @@ object LongMap { import LongMap._ // Iterator over a non-empty LongMap. -private[immutable] abstract class LongMapIterator[V, T](it : LongMap[V]) extends AbstractIterator[T] { +private[immutable] abstract class LongMapIterator[V, T](it: LongMap[V]) extends AbstractIterator[T] { // Basically this uses a simple stack to emulate conversion over the tree. However // because we know that Longs are only 64 bits we can have at most 64 LongMap.Bins and // one LongMap.Tip sitting on the tree at any point. Therefore we know the maximum stack // depth is 65 - var index = 0; - var buffer = new Array[AnyRef](65); + var index = 0 + var buffer = new Array[AnyRef](65) def pop() = { - index -= 1; - buffer(index).asInstanceOf[LongMap[V]]; + index -= 1 + buffer(index).asInstanceOf[LongMap[V]] } - def push(x : LongMap[V]) { - buffer(index) = x.asInstanceOf[AnyRef]; - index += 1; + def push(x: LongMap[V]) { + buffer(index) = x.asInstanceOf[AnyRef] + index += 1 } push(it); /** * What value do we assign to a tip? */ - def valueOf(tip : LongMap.Tip[V]) : T; + def valueOf(tip: LongMap.Tip[V]): T - def hasNext = index != 0; - final def next : T = + def hasNext = index != 0 + final def next: T = pop() match { case LongMap.Bin(_,_, t@LongMap.Tip(_, _), right) => { - push(right); - valueOf(t); + push(right) + valueOf(t) } case LongMap.Bin(_, _, left, right) => { - push(right); - push(left); - next; + push(right) + push(left) + next } - case t@LongMap.Tip(_, _) => valueOf(t); + case t@LongMap.Tip(_, _) => valueOf(t) // This should never happen. We don't allow LongMap.Nil in subtrees of the LongMap // and don't return an LongMapIterator for LongMap.Nil. - case LongMap.Nil => sys.error("Empty maps not allowed as subtrees"); + case LongMap.Nil => sys.error("Empty maps not allowed as subtrees") } } -private[immutable] class LongMapEntryIterator[V](it : LongMap[V]) extends LongMapIterator[V, (Long, V)](it){ - def valueOf(tip : LongMap.Tip[V]) = (tip.key, tip.value); +private[immutable] class LongMapEntryIterator[V](it: LongMap[V]) extends LongMapIterator[V, (Long, V)](it){ + def valueOf(tip: LongMap.Tip[V]) = (tip.key, tip.value) } -private[immutable] class LongMapValueIterator[V](it : LongMap[V]) extends LongMapIterator[V, V](it){ - def valueOf(tip : LongMap.Tip[V]) = tip.value; +private[immutable] class LongMapValueIterator[V](it: LongMap[V]) extends LongMapIterator[V, V](it){ + def valueOf(tip: LongMap.Tip[V]) = tip.value } -private[immutable] class LongMapKeyIterator[V](it : LongMap[V]) extends LongMapIterator[V, Long](it){ - def valueOf(tip : LongMap.Tip[V]) = tip.key; +private[immutable] class LongMapKeyIterator[V](it: LongMap[V]) extends LongMapIterator[V, Long](it){ + def valueOf(tip: LongMap.Tip[V]) = tip.key } -import LongMap._; - /** * Specialised immutable map structure for long keys, based on * <a href="http://citeseer.ist.psu.edu/okasaki98fast.html">Fast Mergeable Long Maps</a> @@ -157,12 +155,12 @@ extends AbstractMap[Long, T] with Map[Long, T] with MapLike[Long, T, LongMap[T]] { - override def empty: LongMap[T] = LongMap.Nil; + override def empty: LongMap[T] = LongMap.Nil override def toList = { - val buffer = new scala.collection.mutable.ListBuffer[(Long, T)]; - foreach(buffer += _); - buffer.toList; + val buffer = new scala.collection.mutable.ListBuffer[(Long, T)] + foreach(buffer += _) + buffer.toList } /** @@ -171,22 +169,22 @@ extends AbstractMap[Long, T] * @return an iterator over pairs of long keys and corresponding values. */ def iterator: Iterator[(Long, T)] = this match { - case LongMap.Nil => Iterator.empty; - case _ => new LongMapEntryIterator(this); + case LongMap.Nil => Iterator.empty + case _ => new LongMapEntryIterator(this) } /** * Loops over the key, value pairs of the map in unsigned order of the keys. */ - override final def foreach[U](f : ((Long, T)) => U) : Unit = this match { - case LongMap.Bin(_, _, left, right) => {left.foreach(f); right.foreach(f); } + override final def foreach[U](f: ((Long, T)) => U): Unit = this match { + case LongMap.Bin(_, _, left, right) => { left.foreach(f); right.foreach(f) } case LongMap.Tip(key, value) => f((key, value)); - case LongMap.Nil => {}; + case LongMap.Nil => } - override def keysIterator : Iterator[Long] = this match { - case LongMap.Nil => Iterator.empty; - case _ => new LongMapKeyIterator(this); + override def keysIterator: Iterator[Long] = this match { + case LongMap.Nil => Iterator.empty + case _ => new LongMapKeyIterator(this) } /** @@ -195,15 +193,15 @@ extends AbstractMap[Long, T] * * @param f The loop body */ - final def foreachKey(f : Long => Unit) : Unit = this match { - case LongMap.Bin(_, _, left, right) => {left.foreachKey(f); right.foreachKey(f); } - case LongMap.Tip(key, _) => f(key); - case LongMap.Nil => {} + final def foreachKey(f: Long => Unit): Unit = this match { + case LongMap.Bin(_, _, left, right) => { left.foreachKey(f); right.foreachKey(f) } + case LongMap.Tip(key, _) => f(key) + case LongMap.Nil => } - override def valuesIterator : Iterator[T] = this match { - case LongMap.Nil => Iterator.empty; - case _ => new LongMapValueIterator(this); + override def valuesIterator: Iterator[T] = this match { + case LongMap.Nil => Iterator.empty + case _ => new LongMapValueIterator(this) } /** @@ -212,67 +210,70 @@ extends AbstractMap[Long, T] * * @param f The loop body */ - final def foreachValue(f : T => Unit) : Unit = this match { - case LongMap.Bin(_, _, left, right) => {left.foreachValue(f); right.foreachValue(f); } - case LongMap.Tip(_, value) => f(value); - case LongMap.Nil => {}; + final def foreachValue(f: T => Unit): Unit = this match { + case LongMap.Bin(_, _, left, right) => { left.foreachValue(f); right.foreachValue(f) } + case LongMap.Tip(_, value) => f(value) + case LongMap.Nil => } override def stringPrefix = "LongMap" - override def isEmpty = this == LongMap.Nil; + override def isEmpty = this == LongMap.Nil - override def filter(f : ((Long, T)) => Boolean) : LongMap[T] = this match { + override def filter(f: ((Long, T)) => Boolean): LongMap[T] = this match { case LongMap.Bin(prefix, mask, left, right) => { - val (newleft, newright) = (left.filter(f), right.filter(f)); - if ((left eq newleft) && (right eq newright)) this; - else bin(prefix, mask, newleft, newright); + val (newleft, newright) = (left.filter(f), right.filter(f)) + if ((left eq newleft) && (right eq newright)) this + else bin(prefix, mask, newleft, newright) } case LongMap.Tip(key, value) => if (f((key, value))) this - else LongMap.Nil; - case LongMap.Nil => LongMap.Nil; + else LongMap.Nil + case LongMap.Nil => LongMap.Nil } - def transform[S](f : (Long, T) => S) : LongMap[S] = this match { - case b@LongMap.Bin(prefix, mask, left, right) => b.bin(left.transform(f), right.transform(f)); - case t@LongMap.Tip(key, value) => t.withValue(f(key, value)); - case LongMap.Nil => LongMap.Nil; + def transform[S](f: (Long, T) => S): LongMap[S] = this match { + case b@LongMap.Bin(prefix, mask, left, right) => b.bin(left.transform(f), right.transform(f)) + case t@LongMap.Tip(key, value) => t.withValue(f(key, value)) + case LongMap.Nil => LongMap.Nil } - final override def size : Int = this match { - case LongMap.Nil => 0; - case LongMap.Tip(_, _) => 1; - case LongMap.Bin(_, _, left, right) => left.size + right.size; + final override def size: Int = this match { + case LongMap.Nil => 0 + case LongMap.Tip(_, _) => 1 + case LongMap.Bin(_, _, left, right) => left.size + right.size } - final def get(key : Long) : Option[T] = this match { - case LongMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left.get(key) else right.get(key); - case LongMap.Tip(key2, value) => if (key == key2) Some(value) else None; - case LongMap.Nil => None; + final def get(key: Long): Option[T] = this match { + case LongMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left.get(key) else right.get(key) + case LongMap.Tip(key2, value) => if (key == key2) Some(value) else None + case LongMap.Nil => None } - final override def getOrElse[S >: T](key : Long, default : =>S) : S = this match { - case LongMap.Nil => default; - case LongMap.Tip(key2, value) => if (key == key2) value else default; - case LongMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left.getOrElse(key, default) else right.getOrElse(key, default); + final override def getOrElse[S >: T](key: Long, default: => S): S = this match { + case LongMap.Nil => default + case LongMap.Tip(key2, value) => if (key == key2) value else default + case LongMap.Bin(prefix, mask, left, right) => + if (zero(key, mask)) left.getOrElse(key, default) else right.getOrElse(key, default) } - final override def apply(key : Long) : T = this match { - case LongMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left(key) else right(key); - case LongMap.Tip(key2, value) => if (key == key2) value else sys.error("Key not found"); - case LongMap.Nil => sys.error("key not found"); + final override def apply(key: Long): T = this match { + case LongMap.Bin(prefix, mask, left, right) => if (zero(key, mask)) left(key) else right(key) + case LongMap.Tip(key2, value) => if (key == key2) value else sys.error("Key not found") + case LongMap.Nil => sys.error("key not found") } def + [S >: T] (kv: (Long, S)): LongMap[S] = updated(kv._1, kv._2) - override def updated[S >: T](key : Long, value : S) : LongMap[S] = this match { - case LongMap.Bin(prefix, mask, left, right) => if (!hasMatch(key, prefix, mask)) join(key, LongMap.Tip(key, value), prefix, this); - else if (zero(key, mask)) LongMap.Bin(prefix, mask, left.updated(key, value), right) - else LongMap.Bin(prefix, mask, left, right.updated(key, value)); - case LongMap.Tip(key2, value2) => if (key == key2) LongMap.Tip(key, value); - else join(key, LongMap.Tip(key, value), key2, this); - case LongMap.Nil => LongMap.Tip(key, value); + override def updated[S >: T](key: Long, value: S): LongMap[S] = this match { + case LongMap.Bin(prefix, mask, left, right) => + if (!hasMatch(key, prefix, mask)) join(key, LongMap.Tip(key, value), prefix, this) + else if (zero(key, mask)) LongMap.Bin(prefix, mask, left.updated(key, value), right) + else LongMap.Bin(prefix, mask, left, right.updated(key, value)) + case LongMap.Tip(key2, value2) => + if (key == key2) LongMap.Tip(key, value) + else join(key, LongMap.Tip(key, value), key2, this) + case LongMap.Nil => LongMap.Tip(key, value) } /** @@ -281,7 +282,7 @@ extends AbstractMap[Long, T] * Equivalent to * {{{ * this.get(key) match { - * case None => this.update(key, value); + * case None => this.update(key, value) * case Some(oldvalue) => this.update(key, f(oldvalue, value) * } * }}} @@ -292,24 +293,26 @@ extends AbstractMap[Long, T] * @param f The function used to resolve conflicts. * @return The updated map. */ - def updateWith[S >: T](key : Long, value : S, f : (T, S) => S) : LongMap[S] = this match { - case LongMap.Bin(prefix, mask, left, right) => if (!hasMatch(key, prefix, mask)) join(key, LongMap.Tip(key, value), prefix, this); - else if (zero(key, mask)) LongMap.Bin(prefix, mask, left.updateWith(key, value, f), right) - else LongMap.Bin(prefix, mask, left, right.updateWith(key, value, f)); - case LongMap.Tip(key2, value2) => if (key == key2) LongMap.Tip(key, f(value2, value)); - else join(key, LongMap.Tip(key, value), key2, this); - case LongMap.Nil => LongMap.Tip(key, value); + def updateWith[S >: T](key: Long, value: S, f: (T, S) => S): LongMap[S] = this match { + case LongMap.Bin(prefix, mask, left, right) => + if (!hasMatch(key, prefix, mask)) join(key, LongMap.Tip(key, value), prefix, this) + else if (zero(key, mask)) LongMap.Bin(prefix, mask, left.updateWith(key, value, f), right) + else LongMap.Bin(prefix, mask, left, right.updateWith(key, value, f)) + case LongMap.Tip(key2, value2) => + if (key == key2) LongMap.Tip(key, f(value2, value)) + else join(key, LongMap.Tip(key, value), key2, this) + case LongMap.Nil => LongMap.Tip(key, value) } - def -(key : Long) : LongMap[T] = this match { + def -(key: Long): LongMap[T] = this match { case LongMap.Bin(prefix, mask, left, right) => - if (!hasMatch(key, prefix, mask)) this; - else if (zero(key, mask)) bin(prefix, mask, left - key, right); - else bin(prefix, mask, left, right - key); + if (!hasMatch(key, prefix, mask)) this + else if (zero(key, mask)) bin(prefix, mask, left - key, right) + else bin(prefix, mask, left, right - key) case LongMap.Tip(key2, _) => - if (key == key2) LongMap.Nil; - else this; - case LongMap.Nil => LongMap.Nil; + if (key == key2) LongMap.Nil + else this + case LongMap.Nil => LongMap.Nil } /** @@ -321,21 +324,21 @@ extends AbstractMap[Long, T] * @param f The transforming function. * @return The modified map. */ - def modifyOrRemove[S](f : (Long, T) => Option[S]) : LongMap[S] = this match { + def modifyOrRemove[S](f: (Long, T) => Option[S]): LongMap[S] = this match { case LongMap.Bin(prefix, mask, left, right) => { - val newleft = left.modifyOrRemove(f); - val newright = right.modifyOrRemove(f); - if ((left eq newleft) && (right eq newright)) this.asInstanceOf[LongMap[S]]; + val newleft = left.modifyOrRemove(f) + val newright = right.modifyOrRemove(f) + if ((left eq newleft) && (right eq newright)) this.asInstanceOf[LongMap[S]] else bin(prefix, mask, newleft, newright) } case LongMap.Tip(key, value) => f(key, value) match { - case None => LongMap.Nil; + case None => LongMap.Nil case Some(value2) => //hack to preserve sharing if (value.asInstanceOf[AnyRef] eq value2.asInstanceOf[AnyRef]) this.asInstanceOf[LongMap[S]] - else LongMap.Tip(key, value2); + else LongMap.Tip(key, value2) } - case LongMap.Nil => LongMap.Nil; + case LongMap.Nil => LongMap.Nil } /** @@ -346,25 +349,25 @@ extends AbstractMap[Long, T] * @param f The function used to resolve conflicts between two mappings. * @return Union of `this` and `that`, with identical key conflicts resolved using the function `f`. */ - def unionWith[S >: T](that : LongMap[S], f : (Long, S, S) => S) : LongMap[S] = (this, that) match{ + def unionWith[S >: T](that: LongMap[S], f: (Long, S, S) => S): LongMap[S] = (this, that) match{ case (LongMap.Bin(p1, m1, l1, r1), that@(LongMap.Bin(p2, m2, l2, r2))) => if (shorter(m1, m2)) { - if (!hasMatch(p2, p1, m1)) join[S](p1, this, p2, that); // TODO: remove [S] when SI-5548 is fixed - else if (zero(p2, m1)) LongMap.Bin(p1, m1, l1.unionWith(that, f), r1); - else LongMap.Bin(p1, m1, l1, r1.unionWith(that, f)); + if (!hasMatch(p2, p1, m1)) join[S](p1, this, p2, that) // TODO: remove [S] when SI-5548 is fixed + else if (zero(p2, m1)) LongMap.Bin(p1, m1, l1.unionWith(that, f), r1) + else LongMap.Bin(p1, m1, l1, r1.unionWith(that, f)) } else if (shorter(m2, m1)){ - if (!hasMatch(p1, p2, m2)) join[S](p1, this, p2, that); // TODO: remove [S] when SI-5548 is fixed - else if (zero(p1, m2)) LongMap.Bin(p2, m2, this.unionWith(l2, f), r2); - else LongMap.Bin(p2, m2, l2, this.unionWith(r2, f)); + if (!hasMatch(p1, p2, m2)) join[S](p1, this, p2, that) // TODO: remove [S] when SI-5548 is fixed + else if (zero(p1, m2)) LongMap.Bin(p2, m2, this.unionWith(l2, f), r2) + else LongMap.Bin(p2, m2, l2, this.unionWith(r2, f)) } else { - if (p1 == p2) LongMap.Bin(p1, m1, l1.unionWith(l2,f), r1.unionWith(r2, f)); - else join[S](p1, this, p2, that); // TODO: remove [S] when SI-5548 is fixed + if (p1 == p2) LongMap.Bin(p1, m1, l1.unionWith(l2,f), r1.unionWith(r2, f)) + else join[S](p1, this, p2, that) // TODO: remove [S] when SI-5548 is fixed } - case (LongMap.Tip(key, value), x) => x.updateWith[S](key, value, (x, y) => f(key, y, x)); // TODO: remove [S] when SI-5548 is fixed - case (x, LongMap.Tip(key, value)) => x.updateWith[S](key, value, (x, y) => f(key, x, y)); - case (LongMap.Nil, x) => x; - case (x, LongMap.Nil) => x; + case (LongMap.Tip(key, value), x) => x.updateWith[S](key, value, (x, y) => f(key, y, x)) // TODO: remove [S] when SI-5548 is fixed + case (x, LongMap.Tip(key, value)) => x.updateWith[S](key, value, (x, y) => f(key, x, y)) + case (LongMap.Nil, x) => x + case (x, LongMap.Nil) => x } /** @@ -378,27 +381,27 @@ extends AbstractMap[Long, T] * @param f The combining function. * @return Intersection of `this` and `that`, with values for identical keys produced by function `f`. */ - def intersectionWith[S, R](that : LongMap[S], f : (Long, T, S) => R) : LongMap[R] = (this, that) match { + def intersectionWith[S, R](that: LongMap[S], f: (Long, T, S) => R): LongMap[R] = (this, that) match { case (LongMap.Bin(p1, m1, l1, r1), that@LongMap.Bin(p2, m2, l2, r2)) => if (shorter(m1, m2)) { - if (!hasMatch(p2, p1, m1)) LongMap.Nil; - else if (zero(p2, m1)) l1.intersectionWith(that, f); - else r1.intersectionWith(that, f); - } else if (m1 == m2) bin(p1, m1, l1.intersectionWith(l2, f), r1.intersectionWith(r2, f)); + if (!hasMatch(p2, p1, m1)) LongMap.Nil + else if (zero(p2, m1)) l1.intersectionWith(that, f) + else r1.intersectionWith(that, f) + } else if (m1 == m2) bin(p1, m1, l1.intersectionWith(l2, f), r1.intersectionWith(r2, f)) else { - if (!hasMatch(p1, p2, m2)) LongMap.Nil; - else if (zero(p1, m2)) this.intersectionWith(l2, f); - else this.intersectionWith(r2, f); + if (!hasMatch(p1, p2, m2)) LongMap.Nil + else if (zero(p1, m2)) this.intersectionWith(l2, f) + else this.intersectionWith(r2, f) } case (LongMap.Tip(key, value), that) => that.get(key) match { - case None => LongMap.Nil; - case Some(value2) => LongMap.Tip(key, f(key, value, value2)); + case None => LongMap.Nil + case Some(value2) => LongMap.Tip(key, f(key, value, value2)) } case (_, LongMap.Tip(key, value)) => this.get(key) match { - case None => LongMap.Nil; - case Some(value2) => LongMap.Tip(key, f(key, value2, value)); + case None => LongMap.Nil + case Some(value2) => LongMap.Tip(key, f(key, value2, value)) } - case (_, _) => LongMap.Nil; + case (_, _) => LongMap.Nil } /** @@ -409,9 +412,10 @@ extends AbstractMap[Long, T] * @param that The map to intersect with. * @return A map with all the keys both in `this` and `that`, mapped to corresponding values from `this`. */ - def intersection[R](that : LongMap[R]) : LongMap[T] = this.intersectionWith(that, (key : Long, value : T, value2 : R) => value); + def intersection[R](that: LongMap[R]): LongMap[T] = + this.intersectionWith(that, (key: Long, value: T, value2: R) => value) - def ++[S >: T](that : LongMap[S]) = + def ++[S >: T](that: LongMap[S]) = this.unionWith[S](that, (key, x, y) => y) } diff --git a/src/library/scala/collection/immutable/RedBlackTree.scala b/src/library/scala/collection/immutable/RedBlackTree.scala index 0f28c4997b..4b573511d1 100644 --- a/src/library/scala/collection/immutable/RedBlackTree.scala +++ b/src/library/scala/collection/immutable/RedBlackTree.scala @@ -43,7 +43,7 @@ object RedBlackTree { } def count(tree: Tree[_, _]) = if (tree eq null) 0 else tree.count - def update[A, B, B1 >: B](tree: Tree[A, B], k: A, v: B1)(implicit ordering: Ordering[A]): Tree[A, B1] = blacken(upd(tree, k, v)) + def update[A, B, B1 >: B](tree: Tree[A, B], k: A, v: B1, overwrite: Boolean)(implicit ordering: Ordering[A]): Tree[A, B1] = blacken(upd(tree, k, v, overwrite)) def delete[A, B](tree: Tree[A, B], k: A)(implicit ordering: Ordering[A]): Tree[A, B] = blacken(del(tree, k)) def rangeImpl[A: Ordering, B](tree: Tree[A, B], from: Option[A], until: Option[A]): Tree[A, B] = (from, until) match { case (Some(from), Some(until)) => this.range(tree, from, until) @@ -122,17 +122,18 @@ object RedBlackTree { else mkTree(isBlack, x, xv, a, r) } - private[this] def upd[A, B, B1 >: B](tree: Tree[A, B], k: A, v: B1)(implicit ordering: Ordering[A]): Tree[A, B1] = if (tree eq null) { + private[this] def upd[A, B, B1 >: B](tree: Tree[A, B], k: A, v: B1, overwrite: Boolean)(implicit ordering: Ordering[A]): Tree[A, B1] = if (tree eq null) { RedTree(k, v, null, null) } else { val cmp = ordering.compare(k, tree.key) - if (cmp < 0) balanceLeft(isBlackTree(tree), tree.key, tree.value, upd(tree.left, k, v), tree.right) - else if (cmp > 0) balanceRight(isBlackTree(tree), tree.key, tree.value, tree.left, upd(tree.right, k, v)) - else mkTree(isBlackTree(tree), k, v, tree.left, tree.right) + if (cmp < 0) balanceLeft(isBlackTree(tree), tree.key, tree.value, upd(tree.left, k, v, overwrite), tree.right) + else if (cmp > 0) balanceRight(isBlackTree(tree), tree.key, tree.value, tree.left, upd(tree.right, k, v, overwrite)) + else if (overwrite || k != tree.key) mkTree(isBlackTree(tree), k, v, tree.left, tree.right) + else tree } - // Based on Stefan Kahrs' Haskell version of Okasaki's Red&Black Trees - // http://www.cse.unsw.edu.au/~dons/data/RedBlackTree.html + /* Based on Stefan Kahrs' Haskell version of Okasaki's Red&Black Trees + * http://www.cse.unsw.edu.au/~dons/data/RedBlackTree.html */ private[this] def del[A, B](tree: Tree[A, B], k: A)(implicit ordering: Ordering[A]): Tree[A, B] = if (tree eq null) null else { def balance(x: A, xv: B, tl: Tree[A, B], tr: Tree[A, B]) = if (isRedTree(tl)) { if (isRedTree(tr)) { @@ -216,7 +217,7 @@ object RedBlackTree { if (ordering.lt(tree.key, from)) return doFrom(tree.right, from) val newLeft = doFrom(tree.left, from) if (newLeft eq tree.left) tree - else if (newLeft eq null) upd(tree.right, tree.key, tree.value) + else if (newLeft eq null) upd(tree.right, tree.key, tree.value, false) else rebalance(tree, newLeft, tree.right) } private[this] def doTo[A, B](tree: Tree[A, B], to: A)(implicit ordering: Ordering[A]): Tree[A, B] = { @@ -224,7 +225,7 @@ object RedBlackTree { if (ordering.lt(to, tree.key)) return doTo(tree.left, to) val newRight = doTo(tree.right, to) if (newRight eq tree.right) tree - else if (newRight eq null) upd(tree.left, tree.key, tree.value) + else if (newRight eq null) upd(tree.left, tree.key, tree.value, false) else rebalance(tree, tree.left, newRight) } private[this] def doUntil[A, B](tree: Tree[A, B], until: A)(implicit ordering: Ordering[A]): Tree[A, B] = { @@ -232,7 +233,7 @@ object RedBlackTree { if (ordering.lteq(until, tree.key)) return doUntil(tree.left, until) val newRight = doUntil(tree.right, until) if (newRight eq tree.right) tree - else if (newRight eq null) upd(tree.left, tree.key, tree.value) + else if (newRight eq null) upd(tree.left, tree.key, tree.value, false) else rebalance(tree, tree.left, newRight) } private[this] def doRange[A, B](tree: Tree[A, B], from: A, until: A)(implicit ordering: Ordering[A]): Tree[A, B] = { @@ -242,8 +243,8 @@ object RedBlackTree { val newLeft = doFrom(tree.left, from) val newRight = doUntil(tree.right, until) if ((newLeft eq tree.left) && (newRight eq tree.right)) tree - else if (newLeft eq null) upd(newRight, tree.key, tree.value); - else if (newRight eq null) upd(newLeft, tree.key, tree.value); + else if (newLeft eq null) upd(newRight, tree.key, tree.value, false); + else if (newRight eq null) upd(newLeft, tree.key, tree.value, false); else rebalance(tree, newLeft, newRight) } @@ -254,7 +255,7 @@ object RedBlackTree { if (n > count) return doDrop(tree.right, n - count - 1) val newLeft = doDrop(tree.left, n) if (newLeft eq tree.left) tree - else if (newLeft eq null) upd(tree.right, tree.key, tree.value) + else if (newLeft eq null) upd(tree.right, tree.key, tree.value, false) else rebalance(tree, newLeft, tree.right) } private[this] def doTake[A: Ordering, B](tree: Tree[A, B], n: Int): Tree[A, B] = { @@ -264,7 +265,7 @@ object RedBlackTree { if (n <= count) return doTake(tree.left, n) val newRight = doTake(tree.right, n - count - 1) if (newRight eq tree.right) tree - else if (newRight eq null) upd(tree.left, tree.key, tree.value) + else if (newRight eq null) upd(tree.left, tree.key, tree.value, false) else rebalance(tree, tree.left, newRight) } private[this] def doSlice[A: Ordering, B](tree: Tree[A, B], from: Int, until: Int): Tree[A, B] = { @@ -275,8 +276,8 @@ object RedBlackTree { val newLeft = doDrop(tree.left, from) val newRight = doTake(tree.right, until - count - 1) if ((newLeft eq tree.left) && (newRight eq tree.right)) tree - else if (newLeft eq null) upd(newRight, tree.key, tree.value) - else if (newRight eq null) upd(newLeft, tree.key, tree.value) + else if (newLeft eq null) upd(newRight, tree.key, tree.value, false) + else if (newRight eq null) upd(newLeft, tree.key, tree.value, false) else rebalance(tree, newLeft, newRight) } diff --git a/src/library/scala/collection/immutable/TreeMap.scala b/src/library/scala/collection/immutable/TreeMap.scala index 4c1a5f2e03..51bc76efc3 100644 --- a/src/library/scala/collection/immutable/TreeMap.scala +++ b/src/library/scala/collection/immutable/TreeMap.scala @@ -131,7 +131,7 @@ class TreeMap[A, +B] private (tree: RB.Tree[A, B])(implicit val ordering: Orderi * @param value the value to be associated with `key` * @return a new $coll with the updated binding */ - override def updated [B1 >: B](key: A, value: B1): TreeMap[A, B1] = new TreeMap(RB.update(tree, key, value)) + override def updated [B1 >: B](key: A, value: B1): TreeMap[A, B1] = new TreeMap(RB.update(tree, key, value, true)) /** Add a key/value pair to this map. * @tparam B1 type of the value of the new binding, a supertype of `B` @@ -171,7 +171,7 @@ class TreeMap[A, +B] private (tree: RB.Tree[A, B])(implicit val ordering: Orderi */ def insert [B1 >: B](key: A, value: B1): TreeMap[A, B1] = { assert(!RB.contains(tree, key)) - new TreeMap(RB.update(tree, key, value)) + new TreeMap(RB.update(tree, key, value, true)) } def - (key:A): TreeMap[A, B] = diff --git a/src/library/scala/collection/immutable/TreeSet.scala b/src/library/scala/collection/immutable/TreeSet.scala index 882e828c5b..697da2bc4b 100644 --- a/src/library/scala/collection/immutable/TreeSet.scala +++ b/src/library/scala/collection/immutable/TreeSet.scala @@ -112,7 +112,7 @@ class TreeSet[A] private (tree: RB.Tree[A, Unit])(implicit val ordering: Orderin * @param elem a new element to add. * @return a new $coll containing `elem` and all the elements of this $coll. */ - def + (elem: A): TreeSet[A] = newSet(RB.update(tree, elem, ())) + def + (elem: A): TreeSet[A] = newSet(RB.update(tree, elem, (), false)) /** A new `TreeSet` with the entry added is returned, * assuming that elem is <em>not</em> in the TreeSet. @@ -122,7 +122,7 @@ class TreeSet[A] private (tree: RB.Tree[A, Unit])(implicit val ordering: Orderin */ def insert(elem: A): TreeSet[A] = { assert(!RB.contains(tree, elem)) - newSet(RB.update(tree, elem, ())) + newSet(RB.update(tree, elem, (), false)) } /** Creates a new `TreeSet` with the entry removed. diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala index 1395a8f52d..d100bf93df 100644 --- a/src/library/scala/collection/immutable/Vector.scala +++ b/src/library/scala/collection/immutable/Vector.scala @@ -77,6 +77,8 @@ override def companion: GenericCompanion[Vector] = Vector override def par = new ParVector(this) + override def toVector: Vector[A] = this + override def lengthCompare(len: Int): Int = length - len private[collection] final def initIterator[B >: A](s: VectorIterator[B]) { diff --git a/src/library/scala/collection/mutable/ArrayOps.scala b/src/library/scala/collection/mutable/ArrayOps.scala index 01636eb54e..7a595f211d 100644 --- a/src/library/scala/collection/mutable/ArrayOps.scala +++ b/src/library/scala/collection/mutable/ArrayOps.scala @@ -64,7 +64,7 @@ abstract class ArrayOps[T] extends ArrayLike[T, Array[T]] with CustomParalleliza * @param asTrav A function that converts elements of this array to rows - arrays of type `U`. * @return An array obtained by concatenating rows of this array. */ - def flatten[U, To](implicit asTrav: T => collection.Traversable[U], m: ClassTag[U]): Array[U] = { + def flatten[U](implicit asTrav: T => collection.Traversable[U], m: ClassTag[U]): Array[U] = { val b = Array.newBuilder[U] b.sizeHint(map{case is: collection.IndexedSeq[_] => is.size case _ => 0}.sum) for (xs <- this) diff --git a/src/library/scala/collection/mutable/LinkedHashMap.scala b/src/library/scala/collection/mutable/LinkedHashMap.scala index 4150cf9eba..5643e070f8 100644 --- a/src/library/scala/collection/mutable/LinkedHashMap.scala +++ b/src/library/scala/collection/mutable/LinkedHashMap.scala @@ -49,7 +49,8 @@ class LinkedHashMap[A, B] extends AbstractMap[A, B] with Map[A, B] with MapLike[A, B, LinkedHashMap[A, B]] with HashTable[A, LinkedEntry[A, B]] - with Serializable { + with Serializable +{ override def empty = LinkedHashMap.empty[A, B] override def size = tableSize @@ -107,7 +108,25 @@ class LinkedHashMap[A, B] extends AbstractMap[A, B] if (hasNext) { val res = (cur.key, cur.value); cur = cur.later; res } else Iterator.empty.next } + + protected class FilteredKeys(p: A => Boolean) extends super.FilteredKeys(p) { + override def empty = LinkedHashMap.empty + } + + override def filterKeys(p: A => Boolean): scala.collection.Map[A, B] = new FilteredKeys(p) + protected class MappedValues[C](f: B => C) extends super.MappedValues[C](f) { + override def empty = LinkedHashMap.empty + } + + override def mapValues[C](f: B => C): scala.collection.Map[A, C] = new MappedValues(f) + + protected class DefaultKeySet extends super.DefaultKeySet { + override def empty = LinkedHashSet.empty + } + + override def keySet: scala.collection.Set[A] = new DefaultKeySet + override def keysIterator: Iterator[A] = new AbstractIterator[A] { private var cur = firstEntry def hasNext = cur ne null diff --git a/src/library/scala/collection/parallel/ParIterableLike.scala b/src/library/scala/collection/parallel/ParIterableLike.scala index a447f1b5e4..815253b537 100644 --- a/src/library/scala/collection/parallel/ParIterableLike.scala +++ b/src/library/scala/collection/parallel/ParIterableLike.scala @@ -841,7 +841,7 @@ self: ParIterableLike[T, Repr, Sequential] => override def toBuffer[U >: T]: collection.mutable.Buffer[U] = seq.toBuffer // have additional, parallel buffers? - override def toTraversable: GenTraversable[T] = this.asInstanceOf[GenTraversable[T]] // TODO add ParTraversable[T] + override def toTraversable: GenTraversable[T] = this.asInstanceOf[GenTraversable[T]] override def toIterable: ParIterable[T] = this.asInstanceOf[ParIterable[T]] @@ -850,7 +850,13 @@ self: ParIterableLike[T, Repr, Sequential] => override def toSet[U >: T]: immutable.ParSet[U] = toParCollection[U, immutable.ParSet[U]](() => immutable.ParSet.newCombiner[U]) override def toMap[K, V](implicit ev: T <:< (K, V)): immutable.ParMap[K, V] = toParMap[K, V, immutable.ParMap[K, V]](() => immutable.ParMap.newCombiner[K, V]) + + override def toVector: Vector[T] = convertTo[Vector] + override def convertTo[Col[_]](implicit cbf: CanBuildFrom[Nothing, T, Col[T @uncheckedVariance]]): Col[T @uncheckedVariance] = if (cbf().isCombiner) { + toParCollection[T, Col[T]](() => cbf().asCombiner) + } else seq.convertTo(cbf) + /* tasks */ protected trait StrictSplitterCheckTask[R, Tp] extends Task[R, Tp] { diff --git a/src/library/scala/collection/parallel/immutable/ParIterable.scala b/src/library/scala/collection/parallel/immutable/ParIterable.scala index d8c42d74b0..349f4fa44c 100644 --- a/src/library/scala/collection/parallel/immutable/ParIterable.scala +++ b/src/library/scala/collection/parallel/immutable/ParIterable.scala @@ -34,6 +34,7 @@ extends collection/*.immutable*/.GenIterable[T] with collection.parallel.ParIterable[T] with GenericParTemplate[T, ParIterable] with ParIterableLike[T, ParIterable[T], collection.immutable.Iterable[T]] + with Immutable { override def companion: GenericCompanion[ParIterable] with GenericParCompanion[ParIterable] = ParIterable diff --git a/src/library/scala/collection/parallel/immutable/ParVector.scala b/src/library/scala/collection/parallel/immutable/ParVector.scala index 1ece663a1d..e4099f1809 100644 --- a/src/library/scala/collection/parallel/immutable/ParVector.scala +++ b/src/library/scala/collection/parallel/immutable/ParVector.scala @@ -62,6 +62,8 @@ extends ParSeq[T] override def seq: Vector[T] = vector + override def toVector: Vector[T] = vector + class ParVectorIterator(_start: Int, _end: Int) extends VectorIterator[T](_start, _end) with SeqSplitter[T] { def remaining: Int = remainingElementCount def dup: SeqSplitter[T] = (new ParVector(remainingVector)).splitter diff --git a/src/library/scala/collection/parallel/mutable/ParIterable.scala b/src/library/scala/collection/parallel/mutable/ParIterable.scala index 700d21d0bb..b5747a31cf 100644 --- a/src/library/scala/collection/parallel/mutable/ParIterable.scala +++ b/src/library/scala/collection/parallel/mutable/ParIterable.scala @@ -29,7 +29,8 @@ import scala.collection.GenIterable trait ParIterable[T] extends collection/*.mutable*/.GenIterable[T] with collection.parallel.ParIterable[T] with GenericParTemplate[T, ParIterable] - with ParIterableLike[T, ParIterable[T], Iterable[T]] { + with ParIterableLike[T, ParIterable[T], Iterable[T]] + with Mutable { override def companion: GenericCompanion[ParIterable] with GenericParCompanion[ParIterable] = ParIterable //protected[this] override def newBuilder = ParIterable.newBuilder[T] diff --git a/src/library/scala/concurrent/SyncVar.scala b/src/library/scala/concurrent/SyncVar.scala index 292014706d..5a6d95c2ed 100644 --- a/src/library/scala/concurrent/SyncVar.scala +++ b/src/library/scala/concurrent/SyncVar.scala @@ -53,8 +53,6 @@ class SyncVar[A] { value } - /** Waits for this SyncVar to become defined and returns - * the result */ def take(): A = synchronized { try get finally unsetVal() @@ -66,8 +64,7 @@ class SyncVar[A] { * the SyncVar. * * @param timeout the amount of milliseconds to wait, 0 means forever - * @return the value or a throws an exception if the timeout occurs - * @throws NoSuchElementException on timeout + * @return `None` if variable is undefined after `timeout`, `Some(value)` otherwise */ def take(timeout: Long): A = synchronized { try get(timeout).get @@ -75,28 +72,25 @@ class SyncVar[A] { } // TODO: this method should be private - // [Heather] the reason why: it doesn't take into consideration + // [Heather] the reason why: it doesn't take into consideration // whether or not the SyncVar is already defined. So, set has been // deprecated in order to eventually be able to make "setting" private @deprecated("Use `put` instead, as `set` is potentionally error-prone", "2.10.0") def set(x: A): Unit = setVal(x) - /** Places a value in the SyncVar. If the SyncVar already has a stored value, - * it waits until another thread takes it */ def put(x: A): Unit = synchronized { while (isDefined) wait() setVal(x) } - /** Checks whether a value is stored in the synchronized variable */ def isSet: Boolean = synchronized { isDefined } // TODO: this method should be private - // [Heather] the reason why: it doesn't take into consideration + // [Heather] the reason why: it doesn't take into consideration // whether or not the SyncVar is already defined. So, unset has been - // deprecated in order to eventually be able to make "unsetting" private + // deprecated in order to eventually be able to make "unsetting" private @deprecated("Use `take` instead, as `unset` is potentionally error-prone", "2.10.0") def unset(): Unit = synchronized { isDefined = false @@ -104,7 +98,7 @@ class SyncVar[A] { notifyAll() } - // `setVal` exists so as to retroactively deprecate `set` without + // `setVal` exists so as to retroactively deprecate `set` without // deprecation warnings where we use `set` internally. The // implementation of `set` was moved to `setVal` to achieve this private def setVal(x: A): Unit = synchronized { @@ -113,13 +107,13 @@ class SyncVar[A] { notifyAll() } - // `unsetVal` exists so as to retroactively deprecate `unset` without + // `unsetVal` exists so as to retroactively deprecate `unset` without // deprecation warnings where we use `unset` internally. The // implementation of `unset` was moved to `unsetVal` to achieve this private def unsetVal(): Unit = synchronized { isDefined = false value = None - notifyAll() + notifyAll() } } diff --git a/src/library/scala/reflect/ClassTag.scala b/src/library/scala/reflect/ClassTag.scala index f753dfbcbb..860e7bac28 100644 --- a/src/library/scala/reflect/ClassTag.scala +++ b/src/library/scala/reflect/ClassTag.scala @@ -52,7 +52,7 @@ trait ClassTag[T] extends Equals with Serializable { * `SomeExtractor(...)` is turned into `ct(SomeExtractor(...))` if `T` in `SomeExtractor.unapply(x: T)` * is uncheckable, but we have an instance of `ClassTag[T]`. */ - def unapply(x: Any): Option[T] = if (runtimeClass.isAssignableFrom(x.getClass)) Some(x.asInstanceOf[T]) else None + def unapply(x: Any): Option[T] = if (x != null && runtimeClass.isAssignableFrom(x.getClass)) Some(x.asInstanceOf[T]) else None /** case class accessories */ override def canEqual(x: Any) = x.isInstanceOf[ClassTag[_]] diff --git a/src/library/scala/reflect/base/Base.scala b/src/library/scala/reflect/base/Base.scala index 461eaa2e9e..490a9e8c03 100644 --- a/src/library/scala/reflect/base/Base.scala +++ b/src/library/scala/reflect/base/Base.scala @@ -451,7 +451,7 @@ class Base extends Universe { self => } } - def show(tree: Tree) = s"<tree ${tree.getClass}>" + def treeToString(tree: Tree) = s"<tree ${tree.getClass}>" trait TermTree extends Tree diff --git a/src/library/scala/reflect/base/Trees.scala b/src/library/scala/reflect/base/Trees.scala index 298d229570..2814450ae3 100644 --- a/src/library/scala/reflect/base/Trees.scala +++ b/src/library/scala/reflect/base/Trees.scala @@ -28,11 +28,11 @@ trait Trees { self: Universe => def isType: Boolean /** Obtains string representation of a tree */ - override def toString: String = show(this) + override def toString: String = treeToString(this) } /** Obtains string representation of a tree */ - def show(tree: Tree): String + protected def treeToString(tree: Tree): String /** Tree is the basis for scala's abstract syntax. The nodes are * implemented as case classes, and the parameters which initialize diff --git a/src/library/scala/reflect/compat.scala b/src/library/scala/reflect/compat.scala deleted file mode 100644 index fc0e5fbf9c..0000000000 --- a/src/library/scala/reflect/compat.scala +++ /dev/null @@ -1,33 +0,0 @@ -// [Eugene++] delete this once we merge with trunk and have a working IDE - -package scala.reflect { - trait ArrayTag[T] - trait ErasureTag[T] - trait ConcreteTypeTag[T] -} - -package scala.reflect.api { - trait TypeTags { - trait TypeTag[T] - trait ConcreteTypeTag[T] - } -} - -package scala { - import scala.reflect.base.{Universe => BaseUniverse} - - trait reflect_compat { - lazy val mirror: BaseUniverse = ??? - } -} - -package scala.reflect { - import language.experimental.macros - import scala.reflect.base.{Universe => BaseUniverse} - - trait internal_compat { - private[scala] def materializeArrayTag[T](u: BaseUniverse): ArrayTag[T] = ??? - private[scala] def materializeErasureTag[T](u: BaseUniverse): ErasureTag[T] = ??? - private[scala] def materializeConcreteTypeTag[T](u: BaseUniverse): ConcreteTypeTag[T] = ??? - } -}
\ No newline at end of file diff --git a/src/library/scala/reflect/makro/internal/package.scala b/src/library/scala/reflect/makro/internal/package.scala index d31a0f0d14..78cb0ffb10 100644 --- a/src/library/scala/reflect/makro/internal/package.scala +++ b/src/library/scala/reflect/makro/internal/package.scala @@ -9,7 +9,7 @@ import scala.reflect.base.{Universe => BaseUniverse} // // todo. once we have implicit macros for tag generation, we can remove these anchors // [Eugene++] how do I hide this from scaladoc? -package object internal extends scala.reflect.internal_compat { +package object internal { private[scala] def materializeClassTag[T](u: BaseUniverse): ClassTag[T] = macro ??? private[scala] def materializeAbsTypeTag[T](u: BaseUniverse): u.AbsTypeTag[T] = macro ??? private[scala] def materializeTypeTag[T](u: BaseUniverse): u.TypeTag[T] = macro ??? diff --git a/src/library/scala/reflect/package.scala b/src/library/scala/reflect/package.scala index 0ee58df2cd..2ebc82875e 100644 --- a/src/library/scala/reflect/package.scala +++ b/src/library/scala/reflect/package.scala @@ -1,6 +1,6 @@ package scala -package object reflect extends reflect_compat { +package object reflect { lazy val basis: base.Universe = new base.Base diff --git a/src/library/scala/util/control/Breaks.scala b/src/library/scala/util/control/Breaks.scala index d7f5a57f50..accda5b8f7 100644 --- a/src/library/scala/util/control/Breaks.scala +++ b/src/library/scala/util/control/Breaks.scala @@ -41,8 +41,8 @@ class Breaks { } } - trait TryBlock { - def catchBreak(onBreak: => Unit): Unit + sealed trait TryBlock[T] { + def catchBreak(onBreak: =>T): T } /** @@ -57,8 +57,8 @@ class Breaks { * } * }}} */ - def tryBreakable(op: => Unit) = new TryBlock { - def catchBreak(onBreak: => Unit) = try { + def tryBreakable[T](op: =>T) = new TryBlock[T] { + def catchBreak(onBreak: =>T) = try { op } catch { case ex: BreakControl => diff --git a/src/library/scala/util/control/ControlThrowable.scala b/src/library/scala/util/control/ControlThrowable.scala index 8cbe3064ef..64afb1f10f 100644 --- a/src/library/scala/util/control/ControlThrowable.scala +++ b/src/library/scala/util/control/ControlThrowable.scala @@ -24,8 +24,9 @@ package scala.util.control * try { * // Body might throw arbitrarily * } catch { - * case ce : ControlThrowable => throw ce // propagate - * case t : Exception => log(t) // log and suppress + * case c: ControlThrowable => throw c // propagate + * case t: Exception => log(t) // log and suppress + * } * }}} * * @author Miles Sabin |