diff options
Diffstat (limited to 'src/library/scala/collection/immutable')
26 files changed, 1006 insertions, 1073 deletions
diff --git a/src/library/scala/collection/immutable/BitSet.scala b/src/library/scala/collection/immutable/BitSet.scala index 70543aa3a6..ecf3326c7f 100644 --- a/src/library/scala/collection/immutable/BitSet.scala +++ b/src/library/scala/collection/immutable/BitSet.scala @@ -14,7 +14,7 @@ package immutable import generic._ import BitSetLike.{LogWL, updateArray} -import mutable.{ Builder, SetBuilder } +import mutable.Builder /** A class for immutable bitsets. * $bitsetinfo @@ -68,6 +68,8 @@ object BitSet extends BitSetFactory[BitSet] { /** The empty bitset */ val empty: BitSet = new BitSet1(0L) + private def createSmall(a: Long, b: Long): BitSet = if (b == 0L) new BitSet1(a) else new BitSet2(a, b) + /** A builder that takes advantage of mutable BitSets. */ def newBuilder: Builder[Int, BitSet] = new Builder[Int, BitSet] { private[this] val b = new mutable.BitSet @@ -84,7 +86,7 @@ object BitSet extends BitSetFactory[BitSet] { val len = elems.length if (len == 0) empty else if (len == 1) new BitSet1(elems(0)) - else if (len == 2) new BitSet2(elems(0), elems(1)) + else if (len == 2) createSmall(elems(0), elems(1)) else { val a = new Array[Long](len) Array.copy(elems, 0, a, 0, len) @@ -99,17 +101,24 @@ object BitSet extends BitSetFactory[BitSet] { val len = elems.length if (len == 0) empty else if (len == 1) new BitSet1(elems(0)) - else if (len == 2) new BitSet2(elems(0), elems(1)) + else if (len == 2) createSmall(elems(0), elems(1)) else new BitSetN(elems) } + @SerialVersionUID(2260107458435649300L) class BitSet1(val elems: Long) extends BitSet { protected def nwords = 1 protected def word(idx: Int) = if (idx == 0) elems else 0L protected def updateWord(idx: Int, w: Long): BitSet = if (idx == 0) new BitSet1(w) - else if (idx == 1) new BitSet2(elems, w) + else if (idx == 1) createSmall(elems, w) else fromBitMaskNoCopy(updateArray(Array(elems), idx, w)) + override def head: Int = + if (elems == 0L) throw new NoSuchElementException("Empty BitSet") + else java.lang.Long.numberOfTrailingZeros(elems) + override def tail: BitSet = + if (elems == 0L) throw new NoSuchElementException("Empty BitSet") + else new BitSet1(elems - java.lang.Long.lowestOneBit(elems)) } class BitSet2(val elems0: Long, elems1: Long) extends BitSet { @@ -117,8 +126,20 @@ object BitSet extends BitSetFactory[BitSet] { protected def word(idx: Int) = if (idx == 0) elems0 else if (idx == 1) elems1 else 0L protected def updateWord(idx: Int, w: Long): BitSet = if (idx == 0) new BitSet2(w, elems1) - else if (idx == 1) new BitSet2(elems0, w) + else if (idx == 1) createSmall(elems0, w) else fromBitMaskNoCopy(updateArray(Array(elems0, elems1), idx, w)) + override def head: Int = + if (elems0 == 0L) { + if (elems1 == 0) throw new NoSuchElementException("Empty BitSet") + 64 + java.lang.Long.numberOfTrailingZeros(elems1) + } + else java.lang.Long.numberOfTrailingZeros(elems0) + override def tail: BitSet = + if (elems0 == 0L) { + if (elems1 == 0L) throw new NoSuchElementException("Empty BitSet") + createSmall(elems0, elems1 - java.lang.Long.lowestOneBit(elems1)) + } + else new BitSet2(elems0 - java.lang.Long.lowestOneBit(elems0), elems1) } /** The implementing class for bit sets with elements >= 128 (exceeding @@ -131,5 +152,15 @@ object BitSet extends BitSetFactory[BitSet] { protected def nwords = elems.length protected def word(idx: Int) = if (idx < nwords) elems(idx) else 0L protected def updateWord(idx: Int, w: Long): BitSet = fromBitMaskNoCopy(updateArray(elems, idx, w)) + override def tail: BitSet = { + val n = nwords + var i = 0 + while (i < n) { + val wi = word(i) + if (wi != 0L) return fromBitMaskNoCopy(updateArray(elems, i, wi - java.lang.Long.lowestOneBit(wi))) + i += 1 + } + throw new NoSuchElementException("Empty BitSet") + } } } diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala index 3e482f1369..627f723cb0 100644 --- a/src/library/scala/collection/immutable/HashMap.scala +++ b/src/library/scala/collection/immutable/HashMap.scala @@ -33,8 +33,7 @@ import parallel.immutable.ParHashMap * @define willNotTerminateInf */ @SerialVersionUID(2L) -@deprecatedInheritance("The implementation details of immutable hash maps make inheriting from them unwise.", "2.11.0") -class HashMap[A, +B] extends AbstractMap[A, B] +sealed class HashMap[A, +B] extends AbstractMap[A, B] with Map[A, B] with MapLike[A, B, HashMap[A, B]] with Serializable @@ -53,6 +52,9 @@ class HashMap[A, +B] extends AbstractMap[A, B] def get(key: A): Option[B] = get0(key, computeHash(key), 0) + override final def contains(key: A): Boolean = + contains0(key, computeHash(key), 0) + override def updated [B1 >: B] (key: A, value: B1): HashMap[A, B1] = updated0(key, computeHash(key), 0, value, null, null) @@ -65,6 +67,8 @@ class HashMap[A, +B] extends AbstractMap[A, B] def - (key: A): HashMap[A, B] = removed0(key, computeHash(key), 0) + override def tail: HashMap[A, B] = this - head._1 + override def filter(p: ((A, B)) => Boolean) = { val buffer = new Array[HashMap[A, B]](bufferSize(size)) nullToEmpty(filter0(p, false, 0, buffer, 0)) @@ -91,7 +95,7 @@ class HashMap[A, +B] extends AbstractMap[A, B] import HashMap.{Merger, MergeFunction, liftMerger} private[collection] def get0(key: A, hash: Int, level: Int): Option[B] = None - + protected def contains0(key: A, hash: Int, level: Int): Boolean = false private[collection] def updated0[B1 >: B](key: A, hash: Int, level: Int, value: B1, kv: (A, B1), merger: Merger[A, B1]): HashMap[A, B1] = new HashMap.HashMap1(key, hash, value, kv) @@ -156,7 +160,10 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { implicit def canBuildFrom[A, B]: CanBuildFrom[Coll, (A, B), HashMap[A, B]] = new MapCanBuildFrom[A, B] def empty[A, B]: HashMap[A, B] = EmptyHashMap.asInstanceOf[HashMap[A, B]] - private object EmptyHashMap extends HashMap[Any, Nothing] { } + private object EmptyHashMap extends HashMap[Any, Nothing] { + override def head: (Any, Nothing) = throw new NoSuchElementException("Empty Map") + override def tail: HashMap[Any, Nothing] = throw new NoSuchElementException("Empty Map") + } // utility method to create a HashTrieMap from two leaf HashMaps (HashMap1 or HashMapCollision1) with non-colliding hash code) private def makeHashTrieMap[A, B](hash0:Int, elem0:HashMap[A, B], hash1:Int, elem1:HashMap[A, B], level:Int, size:Int) : HashTrieMap[A, B] = { @@ -181,6 +188,7 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { } } + @deprecatedInheritance("This class will be made final in a future release.", "2.12.2") class HashMap1[A,+B](private[collection] val key: A, private[collection] val hash: Int, private[collection] val value: (B @uV), private[collection] var kv: (A,B @uV)) extends HashMap[A,B] { override def size = 1 @@ -191,6 +199,8 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { override def get0(key: A, hash: Int, level: Int): Option[B] = if (hash == this.hash && key == this.key) Some(value) else None + override protected def contains0(key: A, hash: Int, level: Int): Boolean = + hash == this.hash && key == this.key private[collection] override def updated0[B1 >: B](key: A, hash: Int, level: Int, value: B1, kv: (A, B1), merger: Merger[A, B1]): HashMap[A, B1] = if (hash == this.hash && key == this.key ) { if (merger eq null) { @@ -235,6 +245,9 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { override def get0(key: A, hash: Int, level: Int): Option[B] = if (hash == this.hash) kvs.get(key) else None + override protected def contains0(key: A, hash: Int, level: Int): Boolean = + hash == this.hash && kvs.contains(key) + private[collection] override def updated0[B1 >: B](key: A, hash: Int, level: Int, value: B1, kv: (A, B1), merger: Merger[A, B1]): HashMap[A, B1] = if (hash == this.hash) { if ((merger eq null) || !kvs.contains(key)) new HashMapCollision1(hash, kvs.updated(key, value)) @@ -290,6 +303,7 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { } } + @deprecatedInheritance("This class will be made final in a future release.", "2.12.2") class HashTrieMap[A, +B]( private[collection] val bitmap: Int, private[collection] val elems: Array[HashMap[A, B @uV]], @@ -302,21 +316,41 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { override def size = size0 override def get0(key: A, hash: Int, level: Int): Option[B] = { + // Note: this code is duplicated with `contains0` + val index = (hash >>> level) & 0x1f + if (bitmap == - 1) { + elems(index).get0(key, hash, level + 5) + } else { + val mask = (1 << index) + if ((bitmap & mask) != 0) { + val offset = Integer.bitCount(bitmap & (mask - 1)) + elems(offset).get0(key, hash, level + 5) + } else { + None + } + } + } + + override protected def contains0(key: A, hash: Int, level: Int): Boolean = { + // Note: this code is duplicated from `get0` val index = (hash >>> level) & 0x1f - val mask = (1 << index) if (bitmap == - 1) { - elems(index & 0x1f).get0(key, hash, level + 5) - } else if ((bitmap & mask) != 0) { - val offset = Integer.bitCount(bitmap & (mask-1)) - elems(offset).get0(key, hash, level + 5) - } else - None + elems(index).contains0(key, hash, level + 5) + } else { + val mask = (1 << index) + if ((bitmap & mask) != 0) { + val offset = Integer.bitCount(bitmap & (mask - 1)) + elems(offset).contains0(key, hash, level + 5) + } else { + false + } + } } private[collection] override def updated0[B1 >: B](key: A, hash: Int, level: Int, value: B1, kv: (A, B1), merger: Merger[A, B1]): HashMap[A, B1] = { val index = (hash >>> level) & 0x1f val mask = (1 << index) - val offset = Integer.bitCount(bitmap & (mask-1)) + val offset = Integer.bitCount(bitmap & (mask - 1)) if ((bitmap & mask) != 0) { val sub = elems(offset) val subNew = sub.updated0(key, hash, level + 5, value, kv, merger) @@ -338,7 +372,7 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { override def removed0(key: A, hash: Int, level: Int): HashMap[A, B] = { val index = (hash >>> level) & 0x1f val mask = (1 << index) - val offset = Integer.bitCount(bitmap & (mask-1)) + val offset = Integer.bitCount(bitmap & (mask - 1)) if ((bitmap & mask) != 0) { val sub = elems(offset) val subNew = sub.removed0(key, hash, level + 5) diff --git a/src/library/scala/collection/immutable/HashSet.scala b/src/library/scala/collection/immutable/HashSet.scala index 050e90b49b..fc937e3a22 100644 --- a/src/library/scala/collection/immutable/HashSet.scala +++ b/src/library/scala/collection/immutable/HashSet.scala @@ -31,8 +31,7 @@ import scala.annotation.tailrec * @define coll immutable hash set */ @SerialVersionUID(2L) -@deprecatedInheritance("The implementation details of immutable hash sets make inheriting from them unwise.", "2.11.0") -class HashSet[A] extends AbstractSet[A] +sealed class HashSet[A] extends AbstractSet[A] with Set[A] with GenericSetTemplate[A, HashSet] with SetLike[A, HashSet[A]] @@ -162,6 +161,8 @@ class HashSet[A] extends AbstractSet[A] def - (e: A): HashSet[A] = nullToEmpty(removed0(e, computeHash(e), 0)) + override def tail: HashSet[A] = this - head + override def filter(p: A => Boolean) = { val buffer = new Array[HashSet[A]](bufferSize(size)) nullToEmpty(filter0(p, false, 0, buffer, 0)) @@ -187,7 +188,7 @@ class HashSet[A] extends AbstractSet[A] protected def get0(key: A, hash: Int, level: Int): Boolean = false - def updated0(key: A, hash: Int, level: Int): HashSet[A] = + private[collection] def updated0(key: A, hash: Int, level: Int): HashSet[A] = new HashSet.HashSet1(key, hash) protected def removed0(key: A, hash: Int, level: Int): HashSet[A] = this @@ -213,7 +214,10 @@ object HashSet extends ImmutableSetFactory[HashSet] { /** $setCanBuildFromInfo */ implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, HashSet[A]] = setCanBuildFrom[A] - private object EmptyHashSet extends HashSet[Any] { } + private object EmptyHashSet extends HashSet[Any] { + override def head: Any = throw new NoSuchElementException("Empty Set") + override def tail: HashSet[Any] = throw new NoSuchElementException("Empty Set") + } private[collection] def emptyInstance: HashSet[Any] = EmptyHashSet // utility method to create a HashTrieSet from two leaf HashSets (HashSet1 or HashSetCollision1) with non-colliding hash code) @@ -250,10 +254,10 @@ object HashSet extends ImmutableSetFactory[HashSet] { class HashSet1[A](private[HashSet] val key: A, private[HashSet] val hash: Int) extends LeafHashSet[A] { override def size = 1 - override def get0(key: A, hash: Int, level: Int): Boolean = + override protected def get0(key: A, hash: Int, level: Int): Boolean = (hash == this.hash && key == this.key) - override def subsetOf0(that: HashSet[A], level: Int) = { + override protected def subsetOf0(that: HashSet[A], level: Int) = { // check if that contains this.key // we use get0 with our key and hash at the correct level instead of calling contains, // which would not work since that might not be a top-level HashSet @@ -261,7 +265,7 @@ object HashSet extends ImmutableSetFactory[HashSet] { that.get0(key, hash, level) } - override def updated0(key: A, hash: Int, level: Int): HashSet[A] = + override private[collection] def updated0(key: A, hash: Int, level: Int): HashSet[A] = if (hash == this.hash && key == this.key) this else { if (hash != this.hash) { @@ -306,7 +310,7 @@ object HashSet extends ImmutableSetFactory[HashSet] { override private[immutable] def diff0(that: HashSet[A], level: Int, buffer: Array[HashSet[A]], offset0: Int): HashSet[A] = if (that.get0(key, hash, level)) null else this - override def removed0(key: A, hash: Int, level: Int): HashSet[A] = + override protected def removed0(key: A, hash: Int, level: Int): HashSet[A] = if (hash == this.hash && key == this.key) null else this override protected def filter0(p: A => Boolean, negate: Boolean, level: Int, buffer: Array[HashSet[A]], offset0: Int): HashSet[A] = @@ -320,10 +324,10 @@ object HashSet extends ImmutableSetFactory[HashSet] { override def size = ks.size - override def get0(key: A, hash: Int, level: Int): Boolean = + override protected def get0(key: A, hash: Int, level: Int): Boolean = if (hash == this.hash) ks.contains(key) else false - override def subsetOf0(that: HashSet[A], level: Int) = { + override protected def subsetOf0(that: HashSet[A], level: Int) = { // we have to check each element // we use get0 with our hash at the correct level instead of calling contains, // which would not work since that might not be a top-level HashSet @@ -331,11 +335,11 @@ object HashSet extends ImmutableSetFactory[HashSet] { ks.forall(key => that.get0(key, hash, level)) } - override def updated0(key: A, hash: Int, level: Int): HashSet[A] = + override private[collection] def updated0(key: A, hash: Int, level: Int): HashSet[A] = if (hash == this.hash) new HashSetCollision1(hash, ks + key) else makeHashTrieSet(this.hash, this, hash, new HashSet1(key, hash), level) - override def union0(that: LeafHashSet[A], level: Int): HashSet[A] = that match { + override private[immutable] def union0(that: LeafHashSet[A], level: Int): HashSet[A] = that match { case that if that.hash != this.hash => // different hash code, so there is no need to investigate further. // Just create a branch node containing the two. @@ -368,7 +372,7 @@ object HashSet extends ImmutableSetFactory[HashSet] { } } - override def union0(that: HashSet[A], level: Int, buffer: Array[HashSet[A]], offset0: Int): HashSet[A] = that match { + override private[immutable] def union0(that: HashSet[A], level: Int, buffer: Array[HashSet[A]], offset0: Int): HashSet[A] = that match { case that: LeafHashSet[A] => // switch to the simpler Tree/Leaf implementation this.union0(that, level) @@ -425,7 +429,7 @@ object HashSet extends ImmutableSetFactory[HashSet] { } } - override def removed0(key: A, hash: Int, level: Int): HashSet[A] = + override protected def removed0(key: A, hash: Int, level: Int): HashSet[A] = if (hash == this.hash) { val ks1 = ks - key ks1.size match { @@ -522,7 +526,7 @@ object HashSet extends ImmutableSetFactory[HashSet] { override def size = size0 - override def get0(key: A, hash: Int, level: Int): Boolean = { + override protected def get0(key: A, hash: Int, level: Int): Boolean = { val index = (hash >>> level) & 0x1f val mask = (1 << index) if (bitmap == - 1) { @@ -534,7 +538,7 @@ object HashSet extends ImmutableSetFactory[HashSet] { false } - override def updated0(key: A, hash: Int, level: Int): HashSet[A] = { + override private[collection] def updated0(key: A, hash: Int, level: Int): HashSet[A] = { val index = (hash >>> level) & 0x1f val mask = (1 << index) val offset = Integer.bitCount(bitmap & (mask-1)) @@ -836,7 +840,7 @@ object HashSet extends ImmutableSetFactory[HashSet] { case _ => this } - override def removed0(key: A, hash: Int, level: Int): HashSet[A] = { + override protected def removed0(key: A, hash: Int, level: Int): HashSet[A] = { val index = (hash >>> level) & 0x1f val mask = (1 << index) val offset = Integer.bitCount(bitmap & (mask-1)) @@ -873,7 +877,7 @@ object HashSet extends ImmutableSetFactory[HashSet] { } } - override def subsetOf0(that: HashSet[A], level: Int): Boolean = if (that eq this) true else that match { + override protected def subsetOf0(that: HashSet[A], level: Int): Boolean = if (that eq this) true else that match { case that: HashTrieSet[A] if this.size0 <= that.size0 => // create local mutable copies of members var abm = this.bitmap diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala index 8e8bf953f3..550b987cb6 100644 --- a/src/library/scala/collection/immutable/List.scala +++ b/src/library/scala/collection/immutable/List.scala @@ -13,7 +13,7 @@ package immutable import generic._ import mutable.{Builder, ListBuffer} import scala.annotation.tailrec -import java.io._ +import java.io.{ObjectOutputStream, ObjectInputStream} /** A class for immutable linked lists representing ordered collections * of elements of type `A`. @@ -25,6 +25,8 @@ import java.io._ * This class is optimal for last-in-first-out (LIFO), stack-like access patterns. If you need another access * pattern, for example, random access or FIFO, consider using a collection more suited to this than `List`. * + * $usesMutableState + * * ==Performance== * '''Time:''' `List` has `O(1)` prepend and head/tail access. Most other operations are `O(n)` on the number of elements in the list. * This includes the index-based lookup of elements, `length`, `append` and `reverse`. @@ -86,11 +88,9 @@ sealed abstract class List[+A] extends AbstractSeq[A] with Product with GenericTraversableTemplate[A, List] with LinearSeqOptimized[A, List[A]] - with Serializable { + with scala.Serializable { override def companion: GenericCompanion[List] = List - import scala.collection.{Iterable, Traversable, Seq, IndexedSeq} - def isEmpty: Boolean def head: A def tail: List[A] @@ -276,8 +276,7 @@ sealed abstract class List[+A] extends AbstractSeq[A] } (b.toList, these) } - - @noinline // TODO - fix optimizer bug that requires noinline (see SI-8334) + final override def map[B, That](f: A => B)(implicit bf: CanBuildFrom[List[A], B, That]): That = { if (bf eq List.ReusableCBF) { if (this eq Nil) Nil.asInstanceOf[That] else { @@ -295,8 +294,7 @@ sealed abstract class List[+A] extends AbstractSeq[A] } else super.map(f) } - - @noinline // TODO - fix optimizer bug that requires noinline for map; applied here to be safe (see SI-8334) + final override def collect[B, That](pf: PartialFunction[A, B])(implicit bf: CanBuildFrom[List[A], B, That]): That = { if (bf eq List.ReusableCBF) { if (this eq Nil) Nil.asInstanceOf[That] else { @@ -325,8 +323,7 @@ sealed abstract class List[+A] extends AbstractSeq[A] } else super.collect(pf) } - - @noinline // TODO - fix optimizer bug that requires noinline for map; applied here to be safe (see SI-8334) + final override def flatMap[B, That](f: A => GenTraversableOnce[B])(implicit bf: CanBuildFrom[List[A], B, That]): That = { if (bf eq List.ReusableCBF) { if (this eq Nil) Nil.asInstanceOf[That] else { @@ -414,7 +411,7 @@ sealed abstract class List[+A] extends AbstractSeq[A] else new Stream.Cons(head, tail.toStream) // Create a proxy for Java serialization that allows us to avoid mutation - // during de-serialization. This is the Serialization Proxy Pattern. + // during deserialization. This is the Serialization Proxy Pattern. protected final def writeReplace(): AnyRef = new List.SerializationProxy(this) } @@ -466,7 +463,7 @@ object List extends SeqFactory[List] { override def empty[A]: List[A] = Nil override def apply[A](xs: A*): List[A] = xs.toList - + private[collection] val partialNotApplied = new Function1[Any, Any] { def apply(x: Any): Any = this } @SerialVersionUID(1L) @@ -482,7 +479,7 @@ object List extends SeqFactory[List] { out.writeObject(ListSerializeEnd) } - // Java serialization calls this before readResolve during de-serialization. + // Java serialization calls this before readResolve during deserialization. // Read the whole list and store it in `orig`. private def readObject(in: ObjectInputStream) { in.defaultReadObject() diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala index 1eedf93269..589f8bbba9 100644 --- a/src/library/scala/collection/immutable/ListMap.scala +++ b/src/library/scala/collection/immutable/ListMap.scala @@ -6,202 +6,161 @@ ** |/ ** \* */ - - package scala package collection package immutable import generic._ -import scala.annotation.{tailrec, bridge} - -/** $factoryInfo - * @since 1 - * @see [[http://docs.scala-lang.org/overviews/collections/concrete-immutable-collection-classes.html#list_maps "Scala's Collection Library overview"]] - * section on `List Maps` for more information. - * - * @define Coll immutable.ListMap - * @define coll immutable list map - */ +import scala.annotation.tailrec + +/** + * $factoryInfo + * + * Note that each element insertion takes O(n) time, which means that creating a list map with + * n elements will take O(n^2^) time. This makes the builder suitable only for a small number of + * elements. + * + * @see [[http://docs.scala-lang.org/overviews/collections/concrete-immutable-collection-classes.html#list_maps "Scala's Collection Library overview"]] + * section on `List Maps` for more information. + * @since 1 + * @define Coll ListMap + * @define coll list map + */ object ListMap extends ImmutableMapFactory[ListMap] { - /** $mapCanBuildFromInfo */ + + /** + * $mapCanBuildFromInfo + */ implicit def canBuildFrom[A, B]: CanBuildFrom[Coll, (A, B), ListMap[A, B]] = new MapCanBuildFrom[A, B] + def empty[A, B]: ListMap[A, B] = EmptyListMap.asInstanceOf[ListMap[A, B]] - private object EmptyListMap extends ListMap[Any, Nothing] { } + @SerialVersionUID(-8256686706655863282L) + private object EmptyListMap extends ListMap[Any, Nothing] } -/** This class implements immutable maps using a list-based data structure, which preserves insertion order. - * Instances of `ListMap` represent empty maps; they can be either created by - * calling the constructor directly, or by applying the function `ListMap.empty`. - * - * @tparam A the type of the keys in this list map. - * @tparam B the type of the values associated with the keys. - * - * @author Matthias Zenger - * @author Martin Odersky - * @version 2.0, 01/01/2007 - * @since 1 - * @define Coll immutable.ListMap - * @define coll immutable list map - * @define mayNotTerminateInf - * @define willNotTerminateInf - */ +/** + * This class implements immutable maps using a list-based data structure. List map iterators and + * traversal methods visit key-value pairs in the order whey were first inserted. + * + * Entries are stored internally in reversed insertion order, which means the newest key is at the + * head of the list. As such, methods such as `head` and `tail` are O(n), while `last` and `init` + * are O(1). Other operations, such as inserting or removing entries, are also O(n), which makes + * this collection suitable only for a small number of elements. + * + * Instances of `ListMap` represent empty maps; they can be either created by calling the + * constructor directly, or by applying the function `ListMap.empty`. + * + * @tparam A the type of the keys contained in this list map + * @tparam B the type of the values associated with the keys + * + * @author Matthias Zenger + * @author Martin Odersky + * @version 2.0, 01/01/2007 + * @since 1 + * @define Coll ListMap + * @define coll list map + * @define mayNotTerminateInf + * @define willNotTerminateInf + */ @SerialVersionUID(301002838095710379L) -@deprecatedInheritance("The semantics of immutable collections makes inheriting from ListMap error-prone.", "2.11.0") -class ListMap[A, +B] -extends AbstractMap[A, B] - with Map[A, B] - with MapLike[A, B, ListMap[A, B]] - with Serializable { +sealed class ListMap[A, +B] extends AbstractMap[A, B] + with Map[A, B] + with MapLike[A, B, ListMap[A, B]] + with Serializable { override def empty = ListMap.empty - /** Returns the number of mappings in this map. - * - * @return number of mappings in this map. - */ override def size: Int = 0 + override def isEmpty: Boolean = true - /** Checks if this map maps `key` to a value and return the - * value if it exists. - * - * @param key the key of the mapping of interest - * @return the value of the mapping, if it exists - */ def get(key: A): Option[B] = None - /** This method allows one to create a new map with an additional mapping - * from `key` to `value`. If the map contains already a mapping for `key`, - * it will be overridden by this function. - * - * @param key the key element of the updated entry. - * @param value the value element of the updated entry. - */ - override def updated [B1 >: B] (key: A, value: B1): ListMap[A, B1] = - new Node[B1](key, value) - - /** Add a key/value pair to this map. - * @param kv the key/value pair - * @return A new map with the new binding added to this map - */ - def + [B1 >: B] (kv: (A, B1)): ListMap[A, B1] = updated(kv._1, kv._2) - - /** Adds two or more elements to this collection and returns - * either the collection itself (if it is mutable), or a new collection - * with the added elements. - * - * @param elem1 the first element to add. - * @param elem2 the second element to add. - * @param elems the remaining elements to add. - */ - override def + [B1 >: B] (elem1: (A, B1), elem2: (A, B1), elems: (A, B1) *): ListMap[A, B1] = - this + elem1 + elem2 ++ elems - - /** 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 updated[B1 >: B](key: A, value: B1): ListMap[A, B1] = new Node[B1](key, value) + + def +[B1 >: B](kv: (A, B1)): ListMap[A, B1] = new Node[B1](kv._1, kv._2) + def -(key: A): ListMap[A, B] = this + override def ++[B1 >: B](xs: GenTraversableOnce[(A, B1)]): ListMap[A, B1] = - ((repr: ListMap[A, B1]) /: xs.seq) (_ + _) - - /** This creates a new mapping without the given `key`. - * If the map does not contain a mapping for the given key, the - * method returns the same map. - * - * @param key a map without a mapping for the given key. - */ - def - (key: A): ListMap[A, B] = this - - /** Returns an iterator over key-value pairs. - */ - def iterator: Iterator[(A,B)] = - new AbstractIterator[(A,B)] { - var self: ListMap[A,B] = ListMap.this - def hasNext = !self.isEmpty - def next(): (A,B) = - if (!hasNext) throw new NoSuchElementException("next on empty iterator") - else { val res = (self.key, self.value); self = self.next; res } - }.toList.reverseIterator - - protected def key: A = throw new NoSuchElementException("empty map") - protected def value: B = throw new NoSuchElementException("empty map") - protected def next: ListMap[A, B] = throw new NoSuchElementException("empty map") - - /** This class represents an entry in the `ListMap`. - */ + if (xs.isEmpty) this + else ((repr: ListMap[A, B1]) /: xs) (_ + _) + + def iterator: Iterator[(A, B)] = { + def reverseList = { + var curr: ListMap[A, B] = this + var res: List[(A, B)] = Nil + while (!curr.isEmpty) { + res = (curr.key, curr.value) :: res + curr = curr.next + } + res + } + reverseList.iterator + } + + protected def key: A = throw new NoSuchElementException("key of empty map") + protected def value: B = throw new NoSuchElementException("value of empty map") + protected def next: ListMap[A, B] = throw new NoSuchElementException("next of empty map") + + override def stringPrefix = "ListMap" + + /** + * Represents an entry in the `ListMap`. + */ @SerialVersionUID(-6453056603889598734L) protected class Node[B1 >: B](override protected val key: A, override protected val value: B1) extends ListMap[A, B1] with Serializable { - /** Returns the number of mappings in this map. - * - * @return number of mappings. - */ - override def size: Int = size0(this, 0) - - // to allow tail recursion and prevent stack overflows - @tailrec private def size0(cur: ListMap[A, B1], acc: Int): Int = if (cur.isEmpty) acc else size0(cur.next, acc + 1) - - /** Is this an empty map? - * - * @return true, iff the map is empty. - */ - override def isEmpty: Boolean = false - /** Retrieves the value which is associated with the given key. This - * method throws an exception if there is no mapping from the given - * key to a value. - * - * @param k the key - * @return the value associated with the given key. - */ - override def apply(k: A): B1 = apply0(this, k) + override def size: Int = sizeInternal(this, 0) + @tailrec private[this] def sizeInternal(cur: ListMap[A, B1], acc: Int): Int = + if (cur.isEmpty) acc + else sizeInternal(cur.next, acc + 1) - @tailrec private def apply0(cur: ListMap[A, B1], k: A): B1 = - if (cur.isEmpty) throw new NoSuchElementException("key not found: "+k) + override def isEmpty: Boolean = false + + override def apply(k: A): B1 = applyInternal(this, k) + + @tailrec private[this] def applyInternal(cur: ListMap[A, B1], k: A): B1 = + if (cur.isEmpty) throw new NoSuchElementException("key not found: " + k) else if (k == cur.key) cur.value - else apply0(cur.next, k) - - /** Checks if this map maps `key` to a value and return the - * value if it exists. - * - * @param k the key of the mapping of interest - * @return the value of the mapping, if it exists - */ - override def get(k: A): Option[B1] = get0(this, k) - - @tailrec private def get0(cur: ListMap[A, B1], k: A): Option[B1] = - if (k == cur.key) Some(cur.value) - else if (cur.next.nonEmpty) get0(cur.next, k) else None - - /** This method allows one to create a new map with an additional mapping - * from `key` to `value`. If the map contains already a mapping for `key`, - * it will be overridden by this function. - */ - override def updated [B2 >: B1](k: A, v: B2): ListMap[A, B2] = { + else applyInternal(cur.next, k) + + override def get(k: A): Option[B1] = getInternal(this, k) + + @tailrec private[this] def getInternal(cur: ListMap[A, B1], k: A): Option[B1] = + if (cur.isEmpty) None + else if (k == cur.key) Some(cur.value) + else getInternal(cur.next, k) + + override def contains(k: A): Boolean = containsInternal(this, k) + + @tailrec private[this] def containsInternal(cur: ListMap[A, B1], k: A): Boolean = + if(cur.isEmpty) false + else if (k == cur.key) true + else containsInternal(cur.next, k) + + override def updated[B2 >: B1](k: A, v: B2): ListMap[A, B2] = { val m = this - k new m.Node[B2](k, v) } - /** Creates a new mapping without the given `key`. - * If the map does not contain a mapping for the given key, the - * method returns the same map. - */ - override def - (k: A): ListMap[A, B1] = remove0(k, this, Nil) - - @tailrec private def remove0(k: A, cur: ListMap[A, B1], acc: List[ListMap[A, B1]]): ListMap[A, B1] = - if (cur.isEmpty) - acc.last - else if (k == cur.key) - (cur.next /: acc) { - case (t, h) => val tt = t; new tt.Node(h.key, h.value) // SI-7459 - } - else - remove0(k, cur.next, cur::acc) + override def +[B2 >: B1](kv: (A, B2)): ListMap[A, B2] = { + val m = this - kv._1 + new m.Node[B2](kv._1, kv._2) + } + + override def -(k: A): ListMap[A, B1] = removeInternal(k, this, Nil) + + @tailrec private[this] def removeInternal(k: A, cur: ListMap[A, B1], acc: List[ListMap[A, B1]]): ListMap[A, B1] = + if (cur.isEmpty) acc.last + else if (k == cur.key) (cur.next /: acc) { case (t, h) => new t.Node(h.key, h.value) } + else removeInternal(k, cur.next, cur :: acc) override protected def next: ListMap[A, B1] = ListMap.this + + override def last: (A, B1) = (key, value) + override def init: ListMap[A, B1] = next } } diff --git a/src/library/scala/collection/immutable/ListSet.scala b/src/library/scala/collection/immutable/ListSet.scala index adc975479a..d9795e9161 100644 --- a/src/library/scala/collection/immutable/ListSet.scala +++ b/src/library/scala/collection/immutable/ListSet.scala @@ -11,174 +11,126 @@ package collection package immutable import generic._ -import scala.annotation.{tailrec, bridge} -import mutable.{ ListBuffer, Builder } - -/** $factoryInfo - * @define Coll immutable.ListSet - * @define coll immutable list set - * @since 1 - */ +import scala.annotation.tailrec + +/** + * $factoryInfo + * + * Note that each element insertion takes O(n) time, which means that creating a list set with + * n elements will take O(n^2^) time. This makes the builder suitable only for a small number of + * elements. + * + * @since 1 + * @define Coll ListSet + * @define coll list set + */ object ListSet extends ImmutableSetFactory[ListSet] { - /** setCanBuildFromInfo */ - implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, ListSet[A]] = setCanBuildFrom[A] - override def newBuilder[A]: Builder[A, ListSet[A]] = new ListSetBuilder[A] + /** + * $setCanBuildFromInfo + */ + implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, ListSet[A]] = + setCanBuildFrom[A] - private object EmptyListSet extends ListSet[Any] { } + @SerialVersionUID(5010379588739277132L) + private object EmptyListSet extends ListSet[Any] private[collection] def emptyInstance: ListSet[Any] = EmptyListSet - - /** A custom builder because forgetfully adding elements one at - * a time to a list backed set puts the "squared" in N^2. There is a - * temporary space cost, but it's improbable a list backed set could - * become large enough for this to matter given its pricy element lookup. - */ - class ListSetBuilder[Elem](initial: ListSet[Elem]) extends Builder[Elem, ListSet[Elem]] { - def this() = this(empty[Elem]) - protected val elems = (new mutable.ListBuffer[Elem] ++= initial).reverse - protected val seen = new mutable.HashSet[Elem] ++= initial - - def +=(x: Elem): this.type = { - if (!seen(x)) { - elems += x - seen += x - } - this - } - def clear() = { elems.clear() ; seen.clear() } - def result() = elems.foldLeft(empty[Elem])(_ unchecked_+ _) - } } -/** This class implements immutable sets using a list-based data - * structure. Instances of `ListSet` represent - * empty sets; they can be either created by calling the constructor - * directly, or by applying the function `ListSet.empty`. - * - * @tparam A the type of the elements contained in this list set. - * - * @author Matthias Zenger - * @version 1.0, 09/07/2003 - * @since 1 - * @define Coll immutable.ListSet - * @define coll immutable list set - * @define mayNotTerminateInf - * @define willNotTerminateInf - */ -@deprecatedInheritance("The semantics of immutable collections makes inheriting from ListSet error-prone.", "2.11.0") -class ListSet[A] extends AbstractSet[A] - with Set[A] - with GenericSetTemplate[A, ListSet] - with SetLike[A, ListSet[A]] - with Serializable{ self => +/** + * This class implements immutable sets using a list-based data structure. List set iterators and + * traversal methods visit elements in the order whey were first inserted. + * + * Elements are stored internally in reversed insertion order, which means the newest element is at + * the head of the list. As such, methods such as `head` and `tail` are O(n), while `last` and + * `init` are O(1). Other operations, such as inserting or removing entries, are also O(n), which + * makes this collection suitable only for a small number of elements. + * + * Instances of `ListSet` represent empty sets; they can be either created by calling the + * constructor directly, or by applying the function `ListSet.empty`. + * + * @tparam A the type of the elements contained in this list set + * + * @author Matthias Zenger + * @version 1.0, 09/07/2003 + * @since 1 + * @define Coll ListSet + * @define coll list set + * @define mayNotTerminateInf + * @define willNotTerminateInf + */ +@SerialVersionUID(-8417059026623606218L) +sealed class ListSet[A] extends AbstractSet[A] + with Set[A] + with GenericSetTemplate[A, ListSet] + with SetLike[A, ListSet[A]] + with Serializable { + override def companion: GenericCompanion[ListSet] = ListSet - /** Returns the number of elements in this set. - * - * @return number of set elements. - */ override def size: Int = 0 override def isEmpty: Boolean = true - /** Checks if this set contains element `elem`. - * - * @param elem the element to check for membership. - * @return `'''true'''`, iff `elem` is contained in this set. - */ def contains(elem: A): Boolean = false - /** This method creates a new set with an additional element. - */ - def + (elem: A): ListSet[A] = new Node(elem) - - /** `-` can be used to remove a single element. - */ - def - (elem: A): ListSet[A] = this + def +(elem: A): ListSet[A] = new Node(elem) + def -(elem: A): ListSet[A] = this - /** If we are bulk adding elements and desire a runtime measured in - * sub-interstellar time units, we better find a way to avoid traversing - * the collection on each element. That's what the custom builder does, - * so we take the easy way out and add ourselves and the argument to - * a new builder. - */ override def ++(xs: GenTraversableOnce[A]): ListSet[A] = if (xs.isEmpty) this - else (new ListSet.ListSetBuilder(this) ++= xs.seq).result() - - private[ListSet] def unchecked_+(e: A): ListSet[A] = new Node(e) - private[ListSet] def unchecked_outer: ListSet[A] = - throw new NoSuchElementException("Empty ListSet has no outer pointer") - - /** Creates a new iterator over all elements contained in this set. - * - * @throws java.util.NoSuchElementException - * @return the new iterator - */ - def iterator: Iterator[A] = new AbstractIterator[A] { - var that: ListSet[A] = self - def hasNext = that.nonEmpty - def next: A = - if (hasNext) { - val res = that.head - that = that.tail - res + else (repr /: xs) (_ + _) + + def iterator: Iterator[A] = { + def reverseList = { + var curr: ListSet[A] = this + var res: List[A] = Nil + while (!curr.isEmpty) { + res = curr.elem :: res + curr = curr.next } - else Iterator.empty.next() + res + } + reverseList.iterator } - /** - * @throws java.util.NoSuchElementException - */ - override def head: A = throw new NoSuchElementException("Set has no elements") + protected def elem: A = throw new NoSuchElementException("elem of empty set") + protected def next: ListSet[A] = throw new NoSuchElementException("next of empty set") - /** - * @throws java.util.NoSuchElementException - */ - override def tail: ListSet[A] = throw new NoSuchElementException("Next of an empty set") + override def toSet[B >: A]: Set[B] = this.asInstanceOf[ListSet[B]] override def stringPrefix = "ListSet" - /** Represents an entry in the `ListSet`. - */ - protected class Node(override val head: A) extends ListSet[A] with Serializable { - override private[ListSet] def unchecked_outer = self + /** + * Represents an entry in the `ListSet`. + */ + @SerialVersionUID(-787710309854855049L) + protected class Node(override protected val elem: A) extends ListSet[A] with Serializable { - /** Returns the number of elements in this set. - * - * @return number of set elements. - */ override def size = sizeInternal(this, 0) - @tailrec private def sizeInternal(n: ListSet[A], acc: Int): Int = + + @tailrec private[this] def sizeInternal(n: ListSet[A], acc: Int): Int = if (n.isEmpty) acc - else sizeInternal(n.unchecked_outer, acc + 1) + else sizeInternal(n.next, acc + 1) - /** Checks if this set is empty. - * - * @return true, iff there is no element in the set. - */ override def isEmpty: Boolean = false - /** Checks if this set contains element `elem`. - * - * @param e the element to check for membership. - * @return `'''true'''`, iff `elem` is contained in this set. - */ override def contains(e: A) = containsInternal(this, e) - @tailrec private def containsInternal(n: ListSet[A], e: A): Boolean = - !n.isEmpty && (n.head == e || containsInternal(n.unchecked_outer, e)) - /** This method creates a new set with an additional element. - */ + @tailrec private[this] def containsInternal(n: ListSet[A], e: A): Boolean = + !n.isEmpty && (n.elem == e || containsInternal(n.next, e)) + override def +(e: A): ListSet[A] = if (contains(e)) this else new Node(e) - /** `-` can be used to remove a single element from a set. - */ - override def -(e: A): ListSet[A] = if (e == head) self else { - val tail = self - e; new tail.Node(head) - } + override def -(e: A): ListSet[A] = removeInternal(e, this, Nil) + + @tailrec private[this] def removeInternal(k: A, cur: ListSet[A], acc: List[ListSet[A]]): ListSet[A] = + if (cur.isEmpty) acc.last + else if (k == cur.elem) (cur.next /: acc) { case (t, h) => new t.Node(h.elem) } + else removeInternal(k, cur.next, cur :: acc) - override def tail: ListSet[A] = self + override protected def next: ListSet[A] = ListSet.this + + override def last: A = elem + override def init: ListSet[A] = next } - - override def toSet[B >: A]: Set[B] = this.asInstanceOf[ListSet[B]] } diff --git a/src/library/scala/collection/immutable/Map.scala b/src/library/scala/collection/immutable/Map.scala index 2c5b444c70..4107b6414d 100644 --- a/src/library/scala/collection/immutable/Map.scala +++ b/src/library/scala/collection/immutable/Map.scala @@ -18,30 +18,30 @@ import generic._ * functionality for the abstract methods in `Map`: * * {{{ - * def get(key: A): Option[B] - * def iterator: Iterator[(A, B)] - * def + [B1 >: B](kv: (A, B1)): Map[A, B1] - * def -(key: A): Map[A, B] + * def get(key: K): Option[V] + * def iterator: Iterator[(K, V)] + * def + [V1 >: V](kv: (K, V1)): Map[K, V1] + * def -(key: K): Map[K, V] * }}} * * @since 1 */ -trait Map[A, +B] extends Iterable[(A, B)] -// with GenMap[A, B] - with scala.collection.Map[A, B] - with MapLike[A, B, Map[A, B]] { self => +trait Map[K, +V] extends Iterable[(K, V)] +// with GenMap[K, V] + with scala.collection.Map[K, V] + with MapLike[K, V, Map[K, V]] { self => - override def empty: Map[A, B] = Map.empty + override def empty: Map[K, V] = Map.empty /** Returns this $coll as an immutable map. * * A new map will not be built; lazy collections will stay lazy. */ @deprecatedOverriding("Immutable maps should do nothing on toMap except return themselves cast as a map.", "2.11.0") - override def toMap[T, U](implicit ev: (A, B) <:< (T, U)): immutable.Map[T, U] = + override def toMap[T, U](implicit ev: (K, V) <:< (T, U)): immutable.Map[T, U] = self.asInstanceOf[immutable.Map[T, U]] - override def seq: Map[A, B] = this + override def seq: Map[K, V] = this /** The same map with a given default function. * Note: `get`, `contains`, `iterator`, `keys`, etc are not affected by `withDefault`. @@ -51,7 +51,7 @@ trait Map[A, +B] extends Iterable[(A, B)] * @param d the function mapping keys to values, used for non-present keys * @return a wrapper of the map with a default value */ - def withDefault[B1 >: B](d: A => B1): immutable.Map[A, B1] = new Map.WithDefault[A, B1](this, d) + def withDefault[V1 >: V](d: K => V1): immutable.Map[K, V1] = new Map.WithDefault[K, V1](this, d) /** The same map with a given default value. * Note: `get`, `contains`, `iterator`, `keys`, etc are not affected by `withDefaultValue`. @@ -61,15 +61,15 @@ trait Map[A, +B] extends Iterable[(A, B)] * @param d default value used for non-present keys * @return a wrapper of the map with a default value */ - def withDefaultValue[B1 >: B](d: B1): immutable.Map[A, B1] = new Map.WithDefault[A, B1](this, x => d) + def withDefaultValue[V1 >: V](d: V1): immutable.Map[K, V1] = new Map.WithDefault[K, V1](this, x => d) /** Add a key/value pair to this map. * @param key the key * @param value the value * @return A new map with the new binding added to this map */ - override def updated [B1 >: B](key: A, value: B1): Map[A, B1] - def + [B1 >: B](kv: (A, B1)): Map[A, B1] + override def updated [V1 >: V](key: K, value: V1): Map[K, V1] + def + [V1 >: V](kv: (K, V1)): Map[K, V1] } /** $factoryInfo @@ -79,116 +79,138 @@ trait Map[A, +B] extends Iterable[(A, B)] object Map extends ImmutableMapFactory[Map] { /** $mapCanBuildFromInfo */ - implicit def canBuildFrom[A, B]: CanBuildFrom[Coll, (A, B), Map[A, B]] = new MapCanBuildFrom[A, B] + implicit def canBuildFrom[K, V]: CanBuildFrom[Coll, (K, V), Map[K, V]] = new MapCanBuildFrom[K, V] - def empty[A, B]: Map[A, B] = EmptyMap.asInstanceOf[Map[A, B]] + def empty[K, V]: Map[K, V] = EmptyMap.asInstanceOf[Map[K, V]] - class WithDefault[A, +B](underlying: Map[A, B], d: A => B) extends scala.collection.Map.WithDefault[A, B](underlying, d) with Map[A, B] { + class WithDefault[K, +V](underlying: Map[K, V], d: K => V) extends scala.collection.Map.WithDefault[K, V](underlying, d) with Map[K, V] { override def empty = new WithDefault(underlying.empty, d) - override def updated[B1 >: B](key: A, value: B1): WithDefault[A, B1] = new WithDefault[A, B1](underlying.updated[B1](key, value), d) - override def + [B1 >: B](kv: (A, B1)): WithDefault[A, B1] = updated(kv._1, kv._2) - override def - (key: A): WithDefault[A, B] = new WithDefault(underlying - key, d) - override def withDefault[B1 >: B](d: A => B1): immutable.Map[A, B1] = new WithDefault[A, B1](underlying, d) - override def withDefaultValue[B1 >: B](d: B1): immutable.Map[A, B1] = new WithDefault[A, B1](underlying, x => d) + override def updated[V1 >: V](key: K, value: V1): WithDefault[K, V1] = new WithDefault[K, V1](underlying.updated[V1](key, value), d) + override def + [V1 >: V](kv: (K, V1)): WithDefault[K, V1] = updated(kv._1, kv._2) + override def - (key: K): WithDefault[K, V] = new WithDefault(underlying - key, d) + override def withDefault[V1 >: V](d: K => V1): immutable.Map[K, V1] = new WithDefault[K, V1](underlying, d) + override def withDefaultValue[V1 >: V](d: V1): immutable.Map[K, V1] = new WithDefault[K, V1](underlying, x => d) } private object EmptyMap extends AbstractMap[Any, Nothing] with Map[Any, Nothing] with Serializable { override def size: Int = 0 + override def apply(key: Any) = throw new NoSuchElementException("key not found: " + key) + override def contains(key: Any) = false def get(key: Any): Option[Nothing] = None def iterator: Iterator[(Any, Nothing)] = Iterator.empty - override def updated [B1] (key: Any, value: B1): Map[Any, B1] = new Map1(key, value) - def + [B1](kv: (Any, B1)): Map[Any, B1] = updated(kv._1, kv._2) + override def updated [V1] (key: Any, value: V1): Map[Any, V1] = new Map1(key, value) + def + [V1](kv: (Any, V1)): Map[Any, V1] = updated(kv._1, kv._2) def - (key: Any): Map[Any, Nothing] = this } - class Map1[A, +B](key1: A, value1: B) extends AbstractMap[A, B] with Map[A, B] with Serializable { + class Map1[K, +V](key1: K, value1: V) extends AbstractMap[K, V] with Map[K, V] with Serializable { override def size = 1 - def get(key: A): Option[B] = + override def apply(key: K) = if (key == key1) value1 else throw new NoSuchElementException("key not found: " + key) + override def contains(key: K) = key == key1 + def get(key: K): Option[V] = if (key == key1) Some(value1) else None def iterator = Iterator((key1, value1)) - override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] = + override def updated [V1 >: V] (key: K, value: V1): Map[K, V1] = if (key == key1) new Map1(key1, value) else new Map2(key1, value1, key, value) - def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2) - def - (key: A): Map[A, B] = + def + [V1 >: V](kv: (K, V1)): Map[K, V1] = updated(kv._1, kv._2) + def - (key: K): Map[K, V] = if (key == key1) Map.empty else this - override def foreach[U](f: ((A, B)) => U): Unit = { + override def foreach[U](f: ((K, V)) => U): Unit = { f((key1, value1)) } } - class Map2[A, +B](key1: A, value1: B, key2: A, value2: B) extends AbstractMap[A, B] with Map[A, B] with Serializable { + class Map2[K, +V](key1: K, value1: V, key2: K, value2: V) extends AbstractMap[K, V] with Map[K, V] with Serializable { override def size = 2 - def get(key: A): Option[B] = + override def apply(key: K) = + if (key == key1) value1 + else if (key == key2) value2 + else throw new NoSuchElementException("key not found: " + key) + override def contains(key: K) = (key == key1) || (key == key2) + def get(key: K): Option[V] = if (key == key1) Some(value1) else if (key == key2) Some(value2) else None def iterator = Iterator((key1, value1), (key2, value2)) - override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] = + override def updated [V1 >: V] (key: K, value: V1): Map[K, V1] = if (key == key1) new Map2(key1, value, key2, value2) else if (key == key2) new Map2(key1, value1, key2, value) else new Map3(key1, value1, key2, value2, key, value) - def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2) - def - (key: A): Map[A, B] = + def + [V1 >: V](kv: (K, V1)): Map[K, V1] = updated(kv._1, kv._2) + def - (key: K): Map[K, V] = if (key == key1) new Map1(key2, value2) else if (key == key2) new Map1(key1, value1) else this - override def foreach[U](f: ((A, B)) => U): Unit = { + override def foreach[U](f: ((K, V)) => U): Unit = { f((key1, value1)); f((key2, value2)) } } - class Map3[A, +B](key1: A, value1: B, key2: A, value2: B, key3: A, value3: B) extends AbstractMap[A, B] with Map[A, B] with Serializable { + class Map3[K, +V](key1: K, value1: V, key2: K, value2: V, key3: K, value3: V) extends AbstractMap[K, V] with Map[K, V] with Serializable { override def size = 3 - def get(key: A): Option[B] = + override def apply(key: K) = + if (key == key1) value1 + else if (key == key2) value2 + else if (key == key3) value3 + else throw new NoSuchElementException("key not found: " + key) + override def contains(key: K) = (key == key1) || (key == key2) || (key == key3) + def get(key: K): Option[V] = if (key == key1) Some(value1) else if (key == key2) Some(value2) else if (key == key3) Some(value3) else None def iterator = Iterator((key1, value1), (key2, value2), (key3, value3)) - override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] = + override def updated [V1 >: V] (key: K, value: V1): Map[K, V1] = if (key == key1) new Map3(key1, value, key2, value2, key3, value3) else if (key == key2) new Map3(key1, value1, key2, value, key3, value3) else if (key == key3) new Map3(key1, value1, key2, value2, key3, value) else new Map4(key1, value1, key2, value2, key3, value3, key, value) - def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2) - def - (key: A): Map[A, B] = + def + [V1 >: V](kv: (K, V1)): Map[K, V1] = updated(kv._1, kv._2) + def - (key: K): Map[K, V] = if (key == key1) new Map2(key2, value2, key3, value3) else if (key == key2) new Map2(key1, value1, key3, value3) else if (key == key3) new Map2(key1, value1, key2, value2) else this - override def foreach[U](f: ((A, B)) => U): Unit = { + override def foreach[U](f: ((K, V)) => U): Unit = { f((key1, value1)); f((key2, value2)); f((key3, value3)) } } - class Map4[A, +B](key1: A, value1: B, key2: A, value2: B, key3: A, value3: B, key4: A, value4: B) extends AbstractMap[A, B] with Map[A, B] with Serializable { + class Map4[K, +V](key1: K, value1: V, key2: K, value2: V, key3: K, value3: V, key4: K, value4: V) extends AbstractMap[K, V] with Map[K, V] with Serializable { override def size = 4 - def get(key: A): Option[B] = + override def apply(key: K) = + if (key == key1) value1 + else if (key == key2) value2 + else if (key == key3) value3 + else if (key == key4) value4 + else throw new NoSuchElementException("key not found: " + key) + override def contains(key: K) = (key == key1) || (key == key2) || (key == key3) || (key == key4) + def get(key: K): Option[V] = if (key == key1) Some(value1) else if (key == key2) Some(value2) else if (key == key3) Some(value3) else if (key == key4) Some(value4) else None def iterator = Iterator((key1, value1), (key2, value2), (key3, value3), (key4, value4)) - override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] = + override def updated [V1 >: V] (key: K, value: V1): Map[K, V1] = if (key == key1) new Map4(key1, value, key2, value2, key3, value3, key4, value4) else if (key == key2) new Map4(key1, value1, key2, value, key3, value3, key4, value4) else if (key == key3) new Map4(key1, value1, key2, value2, key3, value, key4, value4) else if (key == key4) new Map4(key1, value1, key2, value2, key3, value3, key4, value) - else new HashMap + ((key1, value1), (key2, value2), (key3, value3), (key4, value4), (key, value)) - def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2) - def - (key: A): Map[A, B] = + else (new HashMap).updated(key1,value1).updated(key2, value2).updated(key3, value3).updated(key4, value4).updated(key, value) + def + [V1 >: V](kv: (K, V1)): Map[K, V1] = updated(kv._1, kv._2) + def - (key: K): Map[K, V] = if (key == key1) new Map3(key2, value2, key3, value3, key4, value4) else if (key == key2) new Map3(key1, value1, key3, value3, key4, value4) else if (key == key3) new Map3(key1, value1, key2, value2, key4, value4) else if (key == key4) new Map3(key1, value1, key2, value2, key3, value3) else this - override def foreach[U](f: ((A, B)) => U): Unit = { + override def foreach[U](f: ((K, V)) => U): Unit = { f((key1, value1)); f((key2, value2)); f((key3, value3)); f((key4, value4)) } } } /** Explicit instantiation of the `Map` trait to reduce class file size in subclasses. */ -abstract class AbstractMap[A, +B] extends scala.collection.AbstractMap[A, B] with Map[A, B] +abstract class AbstractMap[K, +V] extends scala.collection.AbstractMap[K, V] with Map[K, V] diff --git a/src/library/scala/collection/immutable/MapLike.scala b/src/library/scala/collection/immutable/MapLike.scala index bd5b9c9faf..5867383b52 100644 --- a/src/library/scala/collection/immutable/MapLike.scala +++ b/src/library/scala/collection/immutable/MapLike.scala @@ -14,16 +14,16 @@ import generic._ import parallel.immutable.ParMap /** - * A generic template for immutable maps from keys of type `A` - * to values of type `B`. + * A generic template for immutable maps from keys of type `K` + * to values of type `V`. * To implement a concrete map, you need to provide implementations of the * following methods (where `This` is the type of the actual map implementation): * * {{{ - * def get(key: A): Option[B] - * def iterator: Iterator[(A, B)] - * def + [B1 >: B](kv: (A, B)): Map[A, B1] - * def - (key: A): This + * def get(key: K): Option[V] + * def iterator: Iterator[(K, V)] + * def + [V1 >: V](kv: (K, V)): Map[K, V1] + * def - (key: K): This * }}} * * If you wish that transformer methods like `take`, `drop`, `filter` return the @@ -36,8 +36,8 @@ import parallel.immutable.ParMap * It is also good idea to override methods `foreach` and * `size` for efficiency. * - * @tparam A the type of the keys contained in this collection. - * @tparam B the type of the values associated with the keys. + * @tparam K the type of the keys contained in this collection. + * @tparam V the type of the values associated with the keys. * @tparam This The type of the actual map implementation. * * @author Martin Odersky @@ -46,26 +46,26 @@ import parallel.immutable.ParMap * @define Coll immutable.Map * @define coll immutable map */ -trait MapLike[A, +B, +This <: MapLike[A, B, This] with Map[A, B]] - extends scala.collection.MapLike[A, B, This] - with Parallelizable[(A, B), ParMap[A, B]] +trait MapLike[K, +V, +This <: MapLike[K, V, This] with Map[K, V]] + extends scala.collection.MapLike[K, V, This] + with Parallelizable[(K, V), ParMap[K, V]] { self => - protected[this] override def parCombiner = ParMap.newCombiner[A, B] + protected[this] override def parCombiner = ParMap.newCombiner[K, V] /** A new immutable map containing updating this map with a given key/value mapping. * @param key the key * @param value the value * @return A new map with the new key/value mapping */ - override def updated [B1 >: B](key: A, value: B1): immutable.Map[A, B1] = this + ((key, value)) + override def updated [V1 >: V](key: K, value: V1): immutable.Map[K, V1] = this + ((key, value)) /** Add a key/value pair to this map, returning a new map. * @param kv the key/value pair. * @return A new map with the new binding added to this map. */ - def + [B1 >: B] (kv: (A, B1)): immutable.Map[A, B1] + def + [V1 >: V] (kv: (K, V1)): immutable.Map[K, V1] /** Adds two or more elements to this collection and returns * a new collection. @@ -75,7 +75,7 @@ self => * @param elems the remaining elements to add. * @return A new map with the new bindings added to this map. */ - override def + [B1 >: B] (elem1: (A, B1), elem2: (A, B1), elems: (A, B1) *): immutable.Map[A, B1] = + override def + [V1 >: V] (elem1: (K, V1), elem2: (K, V1), elems: (K, V1) *): immutable.Map[K, V1] = this + elem1 + elem2 ++ elems /** Adds a number of elements provided by a traversable object @@ -84,40 +84,40 @@ self => * @param xs the traversable object consisting of key-value pairs. * @return a new immutable map with the bindings of this map and those from `xs`. */ - override def ++[B1 >: B](xs: GenTraversableOnce[(A, B1)]): immutable.Map[A, B1] = - ((repr: immutable.Map[A, B1]) /: xs.seq) (_ + _) + override def ++[V1 >: V](xs: GenTraversableOnce[(K, V1)]): immutable.Map[K, V1] = + ((repr: immutable.Map[K, V1]) /: xs.seq) (_ + _) /** Filters this map by retaining only keys satisfying a predicate. * @param p the predicate used to test keys * @return an immutable map consisting only of those key value pairs of this map where the key satisfies * the predicate `p`. The resulting map wraps the original map without copying any elements. */ - override def filterKeys(p: A => Boolean): Map[A, B] = new FilteredKeys(p) with DefaultMap[A, B] + override def filterKeys(p: K => Boolean): Map[K, V] = new FilteredKeys(p) with DefaultMap[K, V] /** Transforms this map by applying a function to every retrieved value. * @param f the function used to transform values of this map. * @return a map view which maps every key of this map * to `f(this(key))`. The resulting map wraps the original map without copying any elements. */ - override def mapValues[C](f: B => C): Map[A, C] = new MappedValues(f) with DefaultMap[A, C] + override def mapValues[W](f: V => W): Map[K, W] = new MappedValues(f) with DefaultMap[K, W] /** Collects all keys of this map in a set. * @return a set containing all keys of this map. */ - override def keySet: immutable.Set[A] = new ImmutableDefaultKeySet + override def keySet: immutable.Set[K] = new ImmutableDefaultKeySet - protected class ImmutableDefaultKeySet extends super.DefaultKeySet with immutable.Set[A] { - override def + (elem: A): immutable.Set[A] = + protected class ImmutableDefaultKeySet extends super.DefaultKeySet with immutable.Set[K] { + override def + (elem: K): immutable.Set[K] = if (this(elem)) this - else immutable.Set[A]() ++ this + elem - override def - (elem: A): immutable.Set[A] = - if (this(elem)) immutable.Set[A]() ++ this - elem + else immutable.Set[K]() ++ this + elem + override def - (elem: K): immutable.Set[K] = + if (this(elem)) immutable.Set[K]() ++ this - elem else this // ImmutableDefaultKeySet is only protected, so we won't warn on override. // Someone could override in a way that makes widening not okay // (e.g. by overriding +, though the version in this class is fine) - override def toSet[B >: A]: Set[B] = this.asInstanceOf[Set[B]] + override def toSet[B >: K]: Set[B] = this.asInstanceOf[Set[B]] } /** This function transforms all the values of mappings contained @@ -126,10 +126,9 @@ self => * @param f A function over keys and values * @return the updated map */ - def transform[C, That](f: (A, B) => C)(implicit bf: CanBuildFrom[This, (A, C), That]): That = { + def transform[W, That](f: (K, V) => W)(implicit bf: CanBuildFrom[This, (K, W), That]): That = { val b = bf(repr) for ((key, value) <- this) b += ((key, f(key, value))) b.result() } } - diff --git a/src/library/scala/collection/immutable/MapProxy.scala b/src/library/scala/collection/immutable/MapProxy.scala index d126b9e7a6..0d1c17d4b3 100644 --- a/src/library/scala/collection/immutable/MapProxy.scala +++ b/src/library/scala/collection/immutable/MapProxy.scala @@ -23,7 +23,7 @@ package immutable * @version 2.0, 31/12/2006 * @since 2.8 */ -@deprecated("Proxying is deprecated due to lack of use and compiler-level support.", "2.11.0") +@deprecated("proxying is deprecated due to lack of use and compiler-level support", "2.11.0") trait MapProxy[A, +B] extends Map[A, B] with MapProxyLike[A, B, Map[A, B]] { override def repr = this private def newProxy[B1 >: B](newSelf: Map[A, B1]): MapProxy[A, B1] = diff --git a/src/library/scala/collection/immutable/NumericRange.scala b/src/library/scala/collection/immutable/NumericRange.scala index 59b8a40c64..f1b831bf75 100644 --- a/src/library/scala/collection/immutable/NumericRange.scala +++ b/src/library/scala/collection/immutable/NumericRange.scala @@ -10,8 +10,6 @@ package scala package collection package immutable -import mutable.{ Builder, ListBuffer } - // TODO: Now the specialization exists there is no clear reason to have // separate classes for Range/NumericRange. Investigate and consolidate. @@ -121,7 +119,7 @@ extends AbstractSeq[T] with IndexedSeq[T] with Serializable { // (Integral <: Ordering). This can happen for custom Integral types. // - The Ordering is the default Ordering of a well-known Integral type. if ((ord eq num) || defaultOrdering.get(num).exists(ord eq _)) { - if (num.signum(step) > 0) start + if (num.signum(step) > 0) head else last } else super.min(ord) @@ -129,7 +127,7 @@ extends AbstractSeq[T] with IndexedSeq[T] with Serializable { // See comment for fast path in min(). if ((ord eq num) || defaultOrdering.get(num).exists(ord eq _)) { if (num.signum(step) > 0) last - else start + else head } else super.max(ord) // Motivated by the desire for Double ranges with BigDecimal precision, @@ -168,6 +166,12 @@ extends AbstractSeq[T] with IndexedSeq[T] with Serializable { override def isEmpty = underlyingRange.isEmpty override def apply(idx: Int): A = fm(underlyingRange(idx)) override def containsTyped(el: A) = underlyingRange exists (x => fm(x) == el) + + override def toString = { + def simpleOf(x: Any): String = x.getClass.getName.split("\\.").last + val stepped = simpleOf(underlyingRange.step) + s"${super.toString} (using $underlyingRange of $stepped)" + } } } @@ -198,7 +202,7 @@ extends AbstractSeq[T] with IndexedSeq[T] with Serializable { // Either numRangeElements or (head + last) must be even, so divide the even one before multiplying val a = head.toLong val b = last.toLong - val ans = + val ans = if ((numRangeElements & 1) == 0) (numRangeElements / 2) * (a + b) else numRangeElements * { // Sum is even, but we might overflow it, so divide in pieces and add back remainder @@ -257,9 +261,11 @@ extends AbstractSeq[T] with IndexedSeq[T] with Serializable { super.equals(other) } - override def toString() = { - val endStr = if (length > Range.MAX_PRINT) ", ... )" else ")" - take(Range.MAX_PRINT).mkString("NumericRange(", ", ", endStr) + override def toString = { + val empty = if (isEmpty) "empty " else "" + val preposition = if (isInclusive) "to" else "until" + val stepped = if (step == 1) "" else s" by $step" + s"${empty}NumericRange $start $preposition $end$stepped" } } diff --git a/src/library/scala/collection/immutable/PagedSeq.scala b/src/library/scala/collection/immutable/PagedSeq.scala index 982c10687c..01854b1797 100644 --- a/src/library/scala/collection/immutable/PagedSeq.scala +++ b/src/library/scala/collection/immutable/PagedSeq.scala @@ -12,8 +12,7 @@ package scala package collection package immutable -import java.io._ -import scala.util.matching.Regex +import java.io.{File, FileReader, Reader} import scala.reflect.ClassTag /** The `PagedSeq` object defines a lazy implementations of @@ -23,7 +22,7 @@ import scala.reflect.ClassTag * `fromIterator` and `fromIterable` provide generalised instances of `PagedSeq` * @since 2.7 */ -@deprecated("This object will be moved to the scala-parser-combinators module", "2.11.8") +@deprecated("this object will be moved to the scala-parser-combinators module", "2.11.8") object PagedSeq { final val UndeterminedEnd = Int.MaxValue @@ -127,7 +126,7 @@ import PagedSeq._ * @define mayNotTerminateInf * @define willNotTerminateInf */ -@deprecated("This class will be moved to the scala-parser-combinators module", "2.11.8") +@deprecated("this class will be moved to the scala-parser-combinators module", "2.11.8") class PagedSeq[T: ClassTag] protected( more: (Array[T], Int, Int) => Int, first1: Page[T], diff --git a/src/library/scala/collection/immutable/Queue.scala b/src/library/scala/collection/immutable/Queue.scala index 16cdc6d080..5081b39bdc 100644 --- a/src/library/scala/collection/immutable/Queue.scala +++ b/src/library/scala/collection/immutable/Queue.scala @@ -12,7 +12,6 @@ package immutable import generic._ import mutable.{ Builder, ListBuffer } -import scala.annotation.tailrec /** `Queue` objects implement data structures that allow to * insert and retrieve elements in a first-in-first-out (FIFO) manner. @@ -38,8 +37,7 @@ import scala.annotation.tailrec */ @SerialVersionUID(-7622936493364270175L) -@deprecatedInheritance("The implementation details of immutable queues make inheriting from them unwise.", "2.11.0") -class Queue[+A] protected(protected val in: List[A], protected val out: List[A]) +sealed class Queue[+A] protected(protected val in: List[A], protected val out: List[A]) extends AbstractSeq[A] with LinearSeq[A] with GenericTraversableTemplate[A, Queue] @@ -86,6 +84,14 @@ class Queue[+A] protected(protected val in: List[A], protected val out: List[A]) else if (in.nonEmpty) new Queue(Nil, in.reverse.tail) else throw new NoSuchElementException("tail on empty queue") + /* This is made to avoid inefficient implementation of iterator. */ + override def forall(p: A => Boolean): Boolean = + in.forall(p) && out.forall(p) + + /* This is made to avoid inefficient implementation of iterator. */ + override def exists(p: A => Boolean): Boolean = + in.exists(p) || out.exists(p) + /** Returns the length of the queue. */ override def length = in.length + out.length @@ -100,6 +106,15 @@ class Queue[+A] protected(protected val in: List[A], protected val out: List[A]) case _ => super.:+(elem)(bf) } + override def ++[B >: A, That](that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[Queue[A], B, That]): That = { + if (bf eq Queue.ReusableCBF) { + val thatQueue = that.asInstanceOf[Queue[B]] + new Queue[B](thatQueue.in ++ (thatQueue.out reverse_::: this.in), this.out).asInstanceOf[That] + } else { + super.++(that)(bf) + } + } + /** Creates a new queue with element added at the end * of the old queue. * diff --git a/src/library/scala/collection/immutable/Range.scala b/src/library/scala/collection/immutable/Range.scala index ca6720da19..82203b3d1a 100644 --- a/src/library/scala/collection/immutable/Range.scala +++ b/src/library/scala/collection/immutable/Range.scala @@ -33,7 +33,7 @@ import scala.collection.parallel.immutable.ParRange * `init`) are also permitted on overfull ranges. * * @param start the start of this range. - * @param end the end of the range. For exclusive ranges, e.g. + * @param end the end of the range. For exclusive ranges, e.g. * `Range(0,3)` or `(0 until 3)`, this is one * step past the last one in the range. For inclusive * ranges, e.g. `Range.inclusive(0,3)` or `(0 to 3)`, @@ -57,8 +57,7 @@ import scala.collection.parallel.immutable.ParRange * and its complexity is O(1). */ @SerialVersionUID(7618862778670199309L) -@deprecatedInheritance("The implementation details of Range makes inheriting from it unwise.", "2.11.0") -class Range(val start: Int, val end: Int, val step: Int) +sealed class Range(val start: Int, val end: Int, val step: Int) extends scala.collection.AbstractSeq[Int] with IndexedSeq[Int] with scala.collection.CustomParallelizable[Int, ParRange] @@ -81,8 +80,8 @@ extends scala.collection.AbstractSeq[Int] || (start < end && step < 0) || (start == end && !isInclusive) ) - @deprecated("This method will be made private, use `length` instead.", "2.11") - final val numRangeElements: Int = { + + private val numRangeElements: Int = { if (step == 0) throw new IllegalArgumentException("step cannot be 0.") else if (isEmpty) 0 else { @@ -91,21 +90,17 @@ extends scala.collection.AbstractSeq[Int] else len.toInt } } - @deprecated("This method will be made private, use `last` instead.", "2.11") - final val lastElement = - if (isEmpty) start - step - else step match { - case 1 => if (isInclusive) end else end-1 - case -1 => if (isInclusive) end else end+1 - case _ => - val remainder = (gap % step).toInt - if (remainder != 0) end - remainder - else if (isInclusive) end - else end - step - } - - @deprecated("This method will be made private.", "2.11") - final val terminalElement = lastElement + step + + // This field has a sensible value only for non-empty ranges + private val lastElement = step match { + case 1 => if (isInclusive) end else end-1 + case -1 => if (isInclusive) end else end+1 + case _ => + val remainder = (gap % step).toInt + if (remainder != 0) end - remainder + else if (isInclusive) end + else end - step + } /** The last element of this range. This method will return the correct value * even if there are too many elements to iterate over. @@ -199,6 +194,23 @@ extends scala.collection.AbstractSeq[Int] } ) + /** Creates a new range containing the elements starting at `from` up to but not including `until`. + * + * $doesNotUseBuilders + * + * @param from the element at which to start + * @param until the element at which to end (not included in the range) + * @return a new range consisting of a contiguous interval of values in the old range + */ + override def slice(from: Int, until: Int): Range = + if (from <= 0) take(until) + else if (until >= numRangeElements && numRangeElements >= 0) drop(from) + else { + val fromValue = locationAfterN(from) + if (from >= until) newEmptyRange(fromValue) + else new Range.Inclusive(fromValue, locationAfterN(until-1), step) + } + /** Creates a new range containing all the elements of this range except the last one. * * $doesNotUseBuilders @@ -380,22 +392,20 @@ extends scala.collection.AbstractSeq[Int] case _ => super.equals(other) } - /** Note: hashCode can't be overridden without breaking Seq's - * equals contract. - */ - override def toString() = { - val endStr = - if (numRangeElements > Range.MAX_PRINT || (!isEmpty && numRangeElements < 0)) ", ... )" else ")" - take(Range.MAX_PRINT).mkString("Range(", ", ", endStr) + /* Note: hashCode can't be overridden without breaking Seq's equals contract. */ + + override def toString = { + val preposition = if (isInclusive) "to" else "until" + val stepped = if (step == 1) "" else s" by $step" + val prefix = if (isEmpty) "empty " else if (!isExact) "inexact " else "" + s"${prefix}Range $start $preposition $end$stepped" } } /** A companion object for the `Range` class. */ object Range { - private[immutable] val MAX_PRINT = 512 // some arbitrary value - /** Counts the number of range elements. * @pre step != 0 * If the size of the range exceeds Int.MaxValue, the @@ -427,7 +437,7 @@ object Range { def count(start: Int, end: Int, step: Int): Int = count(start, end, step, isInclusive = false) - class Inclusive(start: Int, end: Int, step: Int) extends Range(start, end, step) { + final class Inclusive(start: Int, end: Int, step: Int) extends Range(start, end, step) { // override def par = new ParRange(this) override def isInclusive = true override protected def copy(start: Int, end: Int, step: Int): Range = new Inclusive(start, end, step) @@ -496,8 +506,9 @@ object Range { // As there is no appealing default step size for not-really-integral ranges, // we offer a partially constructed object. - class Partial[T, U](f: T => U) { + class Partial[T, U](private val f: T => U) extends AnyVal { def by(x: T): U = f(x) + override def toString = "Range requires step" } // Illustrating genericity with Int Range, which should have the same behavior diff --git a/src/library/scala/collection/immutable/Set.scala b/src/library/scala/collection/immutable/Set.scala index 031e5248c1..0f16f97cb0 100644 --- a/src/library/scala/collection/immutable/Set.scala +++ b/src/library/scala/collection/immutable/Set.scala @@ -65,6 +65,7 @@ object Set extends ImmutableSetFactory[Set] { implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Set[A]] = setCanBuildFrom[A] /** An optimized representation for immutable empty sets */ + @SerialVersionUID(-2443710944435909512L) private object EmptySet extends AbstractSet[Any] with Set[Any] with Serializable { override def size: Int = 0 def contains(elem: Any): Boolean = false @@ -103,10 +104,11 @@ object Set extends ImmutableSetFactory[Set] { if (p(elem1)) Some(elem1) else None } + override def head: A = elem1 + override def tail: Set[A] = Set.empty // Why is Set1 non-final? Need to fix that! @deprecatedOverriding("This immutable set should do nothing on toSet but cast itself to a Set with a wider element type.", "2.11.8") override def toSet[B >: A]: Set[B] = this.asInstanceOf[Set1[B]] - } /** An optimized representation for immutable sets of size 2 */ @@ -138,6 +140,8 @@ object Set extends ImmutableSetFactory[Set] { else if (p(elem2)) Some(elem2) else None } + override def head: A = elem1 + override def tail: Set[A] = new Set1(elem2) // Why is Set2 non-final? Need to fix that! @deprecatedOverriding("This immutable set should do nothing on toSet but cast itself to a Set with a wider element type.", "2.11.8") override def toSet[B >: A]: Set[B] = this.asInstanceOf[Set2[B]] @@ -174,6 +178,8 @@ object Set extends ImmutableSetFactory[Set] { else if (p(elem3)) Some(elem3) else None } + override def head: A = elem1 + override def tail: Set[A] = new Set2(elem2, elem3) // Why is Set3 non-final? Need to fix that! @deprecatedOverriding("This immutable set should do nothing on toSet but cast itself to a Set with a wider element type.", "2.11.8") override def toSet[B >: A]: Set[B] = this.asInstanceOf[Set3[B]] @@ -187,7 +193,7 @@ object Set extends ImmutableSetFactory[Set] { elem == elem1 || elem == elem2 || elem == elem3 || elem == elem4 def + (elem: A): Set[A] = if (contains(elem)) this - else new HashSet[A] + (elem1, elem2, elem3, elem4, elem) + else new HashSet[A] + elem1 + elem2 + elem3 + elem4 + elem def - (elem: A): Set[A] = if (elem == elem1) new Set3(elem2, elem3, elem4) else if (elem == elem2) new Set3(elem1, elem3, elem4) @@ -212,6 +218,8 @@ object Set extends ImmutableSetFactory[Set] { else if (p(elem4)) Some(elem4) else None } + override def head: A = elem1 + override def tail: Set[A] = new Set3(elem2, elem3, elem4) // Why is Set4 non-final? Need to fix that! @deprecatedOverriding("This immutable set should do nothing on toSet but cast itself to a Set with a wider element type.", "2.11.8") override def toSet[B >: A]: Set[B] = this.asInstanceOf[Set4[B]] diff --git a/src/library/scala/collection/immutable/SetProxy.scala b/src/library/scala/collection/immutable/SetProxy.scala index d505185e1d..b421b48597 100644 --- a/src/library/scala/collection/immutable/SetProxy.scala +++ b/src/library/scala/collection/immutable/SetProxy.scala @@ -12,8 +12,7 @@ package scala package collection package immutable -/** This is a simple wrapper class for <a href="Set.html" - * target="contentFrame">`scala.collection.immutable.Set`</a>. +/** This is a simple wrapper class for [[scala.collection.immutable.Set]]. * * It is most useful for assembling customized set abstractions * dynamically using object composition and forwarding. @@ -22,7 +21,7 @@ package immutable * * @since 2.8 */ -@deprecated("Proxying is deprecated due to lack of use and compiler-level support.", "2.11.0") +@deprecated("proxying is deprecated due to lack of use and compiler-level support.", "2.11.0") trait SetProxy[A] extends Set[A] with SetProxyLike[A, Set[A]] { override def repr = this private def newProxy[B >: A](newSelf: Set[B]): SetProxy[B] = diff --git a/src/library/scala/collection/immutable/SortedMap.scala b/src/library/scala/collection/immutable/SortedMap.scala index 682788e18e..0f3bd2e195 100644 --- a/src/library/scala/collection/immutable/SortedMap.scala +++ b/src/library/scala/collection/immutable/SortedMap.scala @@ -14,7 +14,6 @@ package immutable import generic._ import mutable.Builder -import scala.annotation.unchecked.uncheckedVariance /** A map whose keys are sorted. * diff --git a/src/library/scala/collection/immutable/SortedSet.scala b/src/library/scala/collection/immutable/SortedSet.scala index 4a8859a7ab..75b2b1f4dc 100644 --- a/src/library/scala/collection/immutable/SortedSet.scala +++ b/src/library/scala/collection/immutable/SortedSet.scala @@ -13,7 +13,6 @@ package collection package immutable import generic._ -import mutable.Builder /** A subtrait of `collection.SortedSet` which represents sorted sets * which cannot be mutated. @@ -38,6 +37,6 @@ object SortedSet extends ImmutableSortedSetFactory[SortedSet] { /** $sortedSetCanBuildFromInfo */ def canBuildFrom[A](implicit ord: Ordering[A]): CanBuildFrom[Coll, A, SortedSet[A]] = newCanBuildFrom[A] def empty[A](implicit ord: Ordering[A]): SortedSet[A] = TreeSet.empty[A] - // Force a declaration here so that BitSet's (which does not inherit from SortedSetFactory) can be more specific + // Force a declaration here so that BitSet (which does not inherit from SortedSetFactory) can be more specific override implicit def newCanBuildFrom[A](implicit ord : Ordering[A]) : CanBuildFrom[Coll, A, SortedSet[A]] = super.newCanBuildFrom } diff --git a/src/library/scala/collection/immutable/Stack.scala b/src/library/scala/collection/immutable/Stack.scala index 1c28093b2c..02bdadb5dd 100644 --- a/src/library/scala/collection/immutable/Stack.scala +++ b/src/library/scala/collection/immutable/Stack.scala @@ -46,7 +46,7 @@ object Stack extends SeqFactory[Stack] { * @define willNotTerminateInf */ @SerialVersionUID(1976480595012942526L) -@deprecated("Stack is an inelegant and potentially poorly-performing wrapper around List. Use List instead: stack push x becomes x :: list; stack.pop is list.tail.", "2.11.0") +@deprecated("Stack is an inelegant and potentially poorly-performing wrapper around List. Use List instead: stack push x becomes x :: list; stack.pop is list.tail.", "2.11.0") class Stack[+A] protected (protected val elems: List[A]) extends AbstractSeq[A] with LinearSeq[A] diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala index d3be809255..8f26de153a 100644 --- a/src/library/scala/collection/immutable/Stream.scala +++ b/src/library/scala/collection/immutable/Stream.scala @@ -11,7 +11,7 @@ package collection package immutable import generic._ -import mutable.{Builder, StringBuilder, LazyBuilder, ListBuffer} +import mutable.{Builder, StringBuilder, LazyBuilder} import scala.annotation.tailrec import Stream.cons import scala.language.implicitConversions @@ -23,7 +23,7 @@ import scala.language.implicitConversions * import scala.math.BigInt * object Main extends App { * - * val fibs: Stream[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map { n => n._1 + n._2 } + * lazy val fibs: Stream[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map { n => n._1 + n._2 } * * fibs take 5 foreach println * } @@ -46,7 +46,7 @@ import scala.language.implicitConversions * import scala.math.BigInt * object Main extends App { * - * val fibs: Stream[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip( + * lazy val fibs: Stream[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip( * fibs.tail).map(n => { * println("Adding %d and %d".format(n._1, n._2)) * n._1 + n._2 @@ -162,7 +162,7 @@ import scala.language.implicitConversions * // The first time we try to access the tail we're going to need more * // information which will require us to recurse, which will require us to * // recurse, which... - * val sov: Stream[Vector[Int]] = Vector(0) #:: sov.zip(sov.tail).map { n => n._1 ++ n._2 } + * lazy val sov: Stream[Vector[Int]] = Vector(0) #:: sov.zip(sov.tail).map { n => n._1 ++ n._2 } * }}} * * The definition of `fibs` above creates a larger number of objects than @@ -198,16 +198,13 @@ import scala.language.implicitConversions * @define orderDependentFold * @define willTerminateInf Note: lazily evaluated; will terminate for infinite-sized collections. */ -@deprecatedInheritance("This class will be sealed.", "2.11.0") -abstract class Stream[+A] extends AbstractSeq[A] +sealed abstract class Stream[+A] extends AbstractSeq[A] with LinearSeq[A] with GenericTraversableTemplate[A, Stream] with LinearSeqOptimized[A, Stream[A]] - with Serializable { -self => - override def companion: GenericCompanion[Stream] = Stream + with Serializable { self => - import scala.collection.{Traversable, Iterable, Seq, IndexedSeq} + override def companion: GenericCompanion[Stream] = Stream /** Indicates whether or not the `Stream` is empty. * @@ -360,7 +357,7 @@ self => * `List(BigInt(12)) ++ fibs`. * * @tparam B The element type of the returned collection.'''That''' - * @param that The [[scala.collection.GenTraversableOnce]] the be concatenated + * @param that The [[scala.collection.GenTraversableOnce]] to be concatenated * to this `Stream`. * @return A new collection containing the result of concatenating `this` with * `that`. @@ -499,80 +496,19 @@ self => ) else super.flatMap(f)(bf) - /** Returns all the elements of this `Stream` that satisfy the predicate `p` - * in a new `Stream` - i.e., it is still a lazy data structure. The order of - * the elements is preserved - * - * @param p the predicate used to filter the stream. - * @return the elements of this stream satisfying `p`. - * - * @example {{{ - * $naturalsEx - * naturalsFrom(1) filter { _ % 5 == 0 } take 10 mkString(", ") - * // produces "5, 10, 15, 20, 25, 30, 35, 40, 45, 50" - * }}} - */ - override def filter(p: A => Boolean): Stream[A] = { + override private[scala] def filterImpl(p: A => Boolean, isFlipped: Boolean): Stream[A] = { // optimization: drop leading prefix of elems for which f returns false // var rest = this dropWhile (!p(_)) - forget DRY principle - GC can't collect otherwise var rest = this - while (!rest.isEmpty && !p(rest.head)) rest = rest.tail + while (!rest.isEmpty && p(rest.head) == isFlipped) rest = rest.tail // private utility func to avoid `this` on stack (would be needed for the lazy arg) - if (rest.nonEmpty) Stream.filteredTail(rest, p) + if (rest.nonEmpty) Stream.filteredTail(rest, p, isFlipped) else Stream.Empty } - override final def withFilter(p: A => Boolean): StreamWithFilter = new StreamWithFilter(p) - - /** A lazier implementation of WithFilter than TraversableLike's. - */ - final class StreamWithFilter(p: A => Boolean) extends WithFilter(p) { - - override def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Stream[A], B, That]): That = { - def tailMap(coll: Stream[A]): Stream[B] = { - var head: A = null.asInstanceOf[A] - var tail: Stream[A] = coll - while (true) { - if (tail.isEmpty) - return Stream.Empty - head = tail.head - tail = tail.tail - if (p(head)) - return cons(f(head), tailMap(tail)) - } - throw new RuntimeException() - } - - if (isStreamBuilder(bf)) asThat(tailMap(Stream.this)) - else super.map(f)(bf) - } - - override def flatMap[B, That](f: A => GenTraversableOnce[B])(implicit bf: CanBuildFrom[Stream[A], B, That]): That = { - def tailFlatMap(coll: Stream[A]): Stream[B] = { - var head: A = null.asInstanceOf[A] - var tail: Stream[A] = coll - while (true) { - if (tail.isEmpty) - return Stream.Empty - head = tail.head - tail = tail.tail - if (p(head)) - return f(head).toStream append tailFlatMap(tail) - } - throw new RuntimeException() - } - - if (isStreamBuilder(bf)) asThat(tailFlatMap(Stream.this)) - else super.flatMap(f)(bf) - } - - override def foreach[U](f: A => U) = - for (x <- self) - if (p(x)) f(x) - - override def withFilter(q: A => Boolean): StreamWithFilter = - new StreamWithFilter(x => p(x) && q(x)) - } + /** A FilterMonadic which allows GC of the head of stream during processing */ + @noinline // Workaround SI-9137, see https://github.com/scala/scala/pull/4284#issuecomment-73180791 + override final def withFilter(p: A => Boolean): FilterMonadic[A, Stream[A]] = new Stream.StreamWithFilter(this, p) /** A lazier Iterator than LinearSeqLike's. */ override def iterator: Iterator[A] = new StreamIterator(self) @@ -1093,6 +1029,8 @@ self => */ override def stringPrefix = "Stream" + override def equals(that: Any): Boolean = + if (this eq that.asInstanceOf[AnyRef]) true else super.equals(that) } /** A specialized, extra-lazy implementation of a stream iterator, so it can @@ -1152,14 +1090,12 @@ object Stream extends SeqFactory[Stream] { /** Creates a new builder for a stream */ def newBuilder[A]: Builder[A, Stream[A]] = new StreamBuilder[A] - import scala.collection.{Iterable, Seq, IndexedSeq} - /** A builder for streams * @note This builder is lazy only in the sense that it does not go downs the spine * of traversables that are added as a whole. If more laziness can be achieved, * this builder should be bypassed. */ - class StreamBuilder[A] extends scala.collection.mutable.LazyBuilder[A, Stream[A]] { + class StreamBuilder[A] extends LazyBuilder[A, Stream[A]] { def result: Stream[A] = parts.toStream flatMap (_.toStream) } @@ -1183,11 +1119,11 @@ object Stream extends SeqFactory[Stream] { /** Construct a stream consisting of a given first element followed by elements * from a lazily evaluated Stream. */ - def #::(hd: A): Stream[A] = cons(hd, tl) + def #::[B >: A](hd: B): Stream[B] = cons(hd, tl) /** Construct a stream consisting of the concatenation of the given stream and * a lazily evaluated Stream. */ - def #:::(prefix: Stream[A]): Stream[A] = prefix append tl + def #:::[B >: A](prefix: Stream[B]): Stream[B] = prefix append tl } /** A wrapper method that adds `#::` for cons and `#:::` for concat as operations @@ -1237,6 +1173,27 @@ object Stream extends SeqFactory[Stream] { tlVal } + + override /*LinearSeqOptimized*/ + def sameElements[B >: A](that: GenIterable[B]): Boolean = { + @tailrec def consEq(a: Cons[_], b: Cons[_]): Boolean = { + if (a.head != b.head) false + else { + a.tail match { + case at: Cons[_] => + b.tail match { + case bt: Cons[_] => (at eq bt) || consEq(at, bt) + case _ => false + } + case _ => b.tail.isEmpty + } + } + } + that match { + case that: Cons[_] => consEq(this, that) + case _ => super.sameElements(that) + } + } } /** An infinite stream that repeatedly applies a given function to a start value. @@ -1295,13 +1252,36 @@ object Stream extends SeqFactory[Stream] { else cons(start, range(start + step, end, step)) } - private[immutable] def filteredTail[A](stream: Stream[A], p: A => Boolean) = { - cons(stream.head, stream.tail filter p) + private[immutable] def filteredTail[A](stream: Stream[A], p: A => Boolean, isFlipped: Boolean) = { + cons(stream.head, stream.tail.filterImpl(p, isFlipped)) } private[immutable] def collectedTail[A, B, That](head: B, stream: Stream[A], pf: PartialFunction[A, B], bf: CanBuildFrom[Stream[A], B, That]) = { cons(head, stream.tail.collect(pf)(bf).asInstanceOf[Stream[B]]) } -} + /** An implementation of `FilterMonadic` allowing GC of the filtered-out elements of + * the `Stream` as it is processed. + * + * Because this is not an inner class of `Stream` with a reference to the original + * head, it is now possible for GC to collect any leading and filtered-out elements + * which do not satisfy the filter, while the tail is still processing (see SI-8990). + */ + private[immutable] final class StreamWithFilter[A](sl: => Stream[A], p: A => Boolean) extends FilterMonadic[A, Stream[A]] { + private var s = sl // set to null to allow GC after filtered + private lazy val filtered = { val f = s filter p; s = null; f } // don't set to null if throw during filter + + def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Stream[A], B, That]): That = + filtered map f + + def flatMap[B, That](f: A => scala.collection.GenTraversableOnce[B])(implicit bf: CanBuildFrom[Stream[A], B, That]): That = + filtered flatMap f + def foreach[U](f: A => U): Unit = + filtered foreach f + + def withFilter(q: A => Boolean): FilterMonadic[A, Stream[A]] = + new StreamWithFilter[A](filtered, q) + } + +} diff --git a/src/library/scala/collection/immutable/StreamViewLike.scala b/src/library/scala/collection/immutable/StreamViewLike.scala index c2eb85815d..4d7eaeff2a 100644 --- a/src/library/scala/collection/immutable/StreamViewLike.scala +++ b/src/library/scala/collection/immutable/StreamViewLike.scala @@ -53,6 +53,7 @@ extends SeqView[A, Coll] /** boilerplate */ protected override def newForced[B](xs: => scala.collection.GenSeq[B]): Transformed[B] = new { val forced = xs } with AbstractTransformed[B] with Forced[B] protected override def newAppended[B >: A](that: scala.collection.GenTraversable[B]): Transformed[B] = new { val rest = that } with AbstractTransformed[B] with Appended[B] + protected override def newPrepended[B >: A](that: scala.collection.GenTraversable[B]): Transformed[B] = new { protected[this] val fst = that } with AbstractTransformed[B] with Prepended[B] protected override def newMapped[B](f: A => B): Transformed[B] = new { val mapping = f } with AbstractTransformed[B] with Mapped[B] protected override def newFlatMapped[B](f: A => scala.collection.GenTraversableOnce[B]): Transformed[B] = new { val mapping = f } with AbstractTransformed[B] with FlatMapped[B] protected override def newFiltered(p: A => Boolean): Transformed[A] = new { val pred = p } with AbstractTransformed[A] with Filtered @@ -67,7 +68,6 @@ extends SeqView[A, Coll] protected override def newPatched[B >: A](_from: Int, _patch: scala.collection.GenSeq[B], _replaced: Int): Transformed[B] = { new { val from = _from; val patch = _patch; val replaced = _replaced } with AbstractTransformed[B] with Patched[B] } - protected override def newPrepended[B >: A](elem: B): Transformed[B] = new { protected[this] val fst = elem } with AbstractTransformed[B] with Prepended[B] override def stringPrefix = "StreamView" } diff --git a/src/library/scala/collection/immutable/StringLike.scala b/src/library/scala/collection/immutable/StringLike.scala index 232d67df4f..fce0f073aa 100644 --- a/src/library/scala/collection/immutable/StringLike.scala +++ b/src/library/scala/collection/immutable/StringLike.scala @@ -10,7 +10,7 @@ package scala package collection package immutable -import mutable.{ ArrayBuilder, Builder } +import mutable.Builder import scala.util.matching.Regex import scala.math.ScalaNumber import scala.reflect.ClassTag @@ -100,11 +100,13 @@ self => /** Return all lines in this string in an iterator, including trailing * line end characters. * - * The number of strings returned is one greater than the number of line - * end characters in this string. For an empty string, a single empty - * line is returned. A line end character is one of - * - `LF` - line feed (`0x0A` hex) - * - `FF` - form feed (`0x0C` hex) + * This method is analogous to `s.split(EOL).toIterator`, + * except that any existing line endings are preserved in the result strings, + * and the empty string yields an empty iterator. + * + * A line end character is one of + * - `LF` - line feed (`0x0A`) + * - `FF` - form feed (`0x0C`) */ def linesWithSeparators: Iterator[String] = new AbstractIterator[String] { val str = self.toString @@ -121,17 +123,17 @@ self => } /** Return all lines in this string in an iterator, excluding trailing line - * end characters, i.e., apply `.stripLineEnd` to all lines + * end characters; i.e., apply `.stripLineEnd` to all lines * returned by `linesWithSeparators`. */ def lines: Iterator[String] = linesWithSeparators map (line => new WrappedString(line).stripLineEnd) /** Return all lines in this string in an iterator, excluding trailing line - * end characters, i.e., apply `.stripLineEnd` to all lines + * end characters; i.e., apply `.stripLineEnd` to all lines * returned by `linesWithSeparators`. */ - @deprecated("Use `lines` instead.","2.11.0") + @deprecated("use `lines` instead","2.11.0") def linesIterator: Iterator[String] = linesWithSeparators map (line => new WrappedString(line).stripLineEnd) @@ -163,20 +165,14 @@ self => if (toString.endsWith(suffix)) toString.substring(0, toString.length() - suffix.length) else toString - /** Replace all literal occurrences of `literal` with the string `replacement`. - * This is equivalent to [[java.lang.String#replaceAll]] except that both arguments - * are appropriately quoted to avoid being interpreted as metacharacters. + /** Replace all literal occurrences of `literal` with the literal string `replacement`. + * This method is equivalent to [[java.lang.String#replace]]. * * @param literal the string which should be replaced everywhere it occurs * @param replacement the replacement string * @return the resulting string */ - def replaceAllLiterally(literal: String, replacement: String): String = { - val arg1 = Regex.quote(literal) - val arg2 = Regex.quoteReplacement(replacement) - - toString.replaceAll(arg1, arg2) - } + def replaceAllLiterally(literal: String, replacement: String): String = toString.replace(literal, replacement) /** For every line in this string: * @@ -202,35 +198,64 @@ self => */ def stripMargin: String = stripMargin('|') - private def escape(ch: Char): String = "\\Q" + ch + "\\E" - - def split(separator: Char): Array[String] = { - val thisString = toString - var pos = thisString.indexOf(separator) - - if (pos != -1) { - val res = new ArrayBuilder.ofRef[String] - - var prev = 0 - do { - res += thisString.substring(prev, pos) - prev = pos + 1 - pos = thisString.indexOf(separator, prev) - } while (pos != -1) - - if (prev != thisString.length) - res += thisString.substring(prev, thisString.length) - - val initialResult = res.result() - pos = initialResult.length - while (pos > 0 && initialResult(pos - 1).isEmpty) pos = pos - 1 - if (pos != initialResult.length) { - val trimmed = new Array[String](pos) - Array.copy(initialResult, 0, trimmed, 0, pos) - trimmed - } else initialResult - } else Array[String](thisString) - } + private def escape(ch: Char): String = if ( + (ch >= 'a') && (ch <= 'z') || + (ch >= 'A') && (ch <= 'Z') || + (ch >= '0' && ch <= '9')) ch.toString + else "\\" + ch + + /** Split this string around the separator character + * + * If this string is the empty string, returns an array of strings + * that contains a single empty string. + * + * If this string is not the empty string, returns an array containing + * the substrings terminated by the start of the string, the end of the + * string or the separator character, excluding empty trailing substrings + * + * If the separator character is a surrogate character, only split on + * matching surrogate characters if they are not part of a surrogate pair + * + * The behaviour follows, and is implemented in terms of <a href="http://docs.oracle.com/javase/7/docs/api/java/lang/String.html#split%28java.lang.String%29">String.split(re: String)</a> + * + * + * @example {{{ + * "a.b".split('.') //returns Array("a", "b") + * + * //splitting the empty string always returns the array with a single + * //empty string + * "".split('.') //returns Array("") + * + * //only trailing empty substrings are removed + * "a.".split('.') //returns Array("a") + * ".a.".split('.') //returns Array("", "a") + * "..a..".split('.') //returns Array("", "", "a") + * + * //all parts are empty and trailing + * ".".split('.') //returns Array() + * "..".split('.') //returns Array() + * + * //surrogate pairs + * val high = 0xD852.toChar + * val low = 0xDF62.toChar + * val highstring = high.toString + * val lowstring = low.toString + * + * //well-formed surrogate pairs are not split + * val highlow = highstring + lowstring + * highlow.split(high) //returns Array(highlow) + * + * //bare surrogate characters are split + * val bare = "_" + highstring + "_" + * bare.split(high) //returns Array("_", "_") + * + * }}} + * + * @param separator the character used as a delimiter + */ + def split(separator: Char): Array[String] = + toString.split(escape(separator)) + @throws(classOf[java.util.regex.PatternSyntaxException]) def split(separators: Array[Char]): Array[String] = { @@ -256,31 +281,39 @@ self => def r(groupNames: String*): Regex = new Regex(toString, groupNames: _*) /** - * @throws java.lang.IllegalArgumentException - If the string does not contain a parsable boolean. + * @throws java.lang.IllegalArgumentException If the string does not contain a parsable `Boolean`. */ def toBoolean: Boolean = parseBoolean(toString) /** - * @throws java.lang.NumberFormatException - If the string does not contain a parsable byte. + * Parse as a `Byte` (string must contain only decimal digits and optional leading `-`). + * @throws java.lang.NumberFormatException If the string does not contain a parsable `Byte`. */ def toByte: Byte = java.lang.Byte.parseByte(toString) /** - * @throws java.lang.NumberFormatException - If the string does not contain a parsable short. + * Parse as a `Short` (string must contain only decimal digits and optional leading `-`). + * @throws java.lang.NumberFormatException If the string does not contain a parsable `Short`. */ def toShort: Short = java.lang.Short.parseShort(toString) /** - * @throws java.lang.NumberFormatException - If the string does not contain a parsable int. + * Parse as an `Int` (string must contain only decimal digits and optional leading `-`). + * @throws java.lang.NumberFormatException If the string does not contain a parsable `Int`. */ def toInt: Int = java.lang.Integer.parseInt(toString) /** - * @throws java.lang.NumberFormatException - If the string does not contain a parsable long. + * Parse as a `Long` (string must contain only decimal digits and optional leading `-`). + * @throws java.lang.NumberFormatException If the string does not contain a parsable `Long`. */ def toLong: Long = java.lang.Long.parseLong(toString) /** - * @throws java.lang.NumberFormatException - If the string does not contain a parsable float. + * Parse as a `Float` (surrounding whitespace is removed with a `trim`). + * @throws java.lang.NumberFormatException If the string does not contain a parsable `Float`. + * @throws java.lang.NullPointerException If the string is null. */ def toFloat: Float = java.lang.Float.parseFloat(toString) /** - * @throws java.lang.NumberFormatException - If the string does not contain a parsable double. + * Parse as a `Double` (surrounding whitespace is removed with a `trim`). + * @throws java.lang.NumberFormatException If the string does not contain a parsable `Double`. + * @throws java.lang.NullPointerException If the string is null. */ def toDouble: Double = java.lang.Double.parseDouble(toString) @@ -306,8 +339,7 @@ self => * holes. * * The interpretation of the formatting patterns is described in - * <a href="" target="contentFrame" class="java/util/Formatter"> - * `java.util.Formatter`</a>, with the addition that + * [[java.util.Formatter]], with the addition that * classes deriving from `ScalaNumber` (such as [[scala.BigInt]] and * [[scala.BigDecimal]]) are unwrapped to pass a type which `Formatter` * understands. @@ -322,8 +354,7 @@ self => * which influences formatting as in `java.lang.String`'s format. * * The interpretation of the formatting patterns is described in - * <a href="" target="contentFrame" class="java/util/Formatter"> - * `java.util.Formatter`</a>, with the addition that + * [[java.util.Formatter]], with the addition that * classes deriving from `ScalaNumber` (such as `scala.BigInt` and * `scala.BigDecimal`) are unwrapped to pass a type which `Formatter` * understands. diff --git a/src/library/scala/collection/immutable/Traversable.scala b/src/library/scala/collection/immutable/Traversable.scala index 5fc0607a00..3d4ba95a16 100644 --- a/src/library/scala/collection/immutable/Traversable.scala +++ b/src/library/scala/collection/immutable/Traversable.scala @@ -18,6 +18,17 @@ import mutable.Builder /** A trait for traversable collections that are guaranteed immutable. * $traversableInfo * @define mutability immutable + * + * @define usesMutableState + * + * Note: Despite being an immutable collection, the implementation uses mutable state internally during + * construction. These state changes are invisible in single-threaded code but can lead to race conditions + * in some multi-threaded scenarios. The state of a new collection instance may not have been "published" + * (in the sense of the Java Memory Model specification), so that an unsynchronized non-volatile read from + * another thread may observe the object in an invalid state (see + * [[https://issues.scala-lang.org/browse/SI-7838 SI-7838]] for details). Note that such a read is not + * guaranteed to ''ever'' see the written object at all, and should therefore not be used, regardless + * of this issue. The easiest workaround is to exchange values between threads through a volatile var. */ trait Traversable[+A] extends scala.collection.Traversable[A] // with GenTraversable[A] diff --git a/src/library/scala/collection/immutable/TreeMap.scala b/src/library/scala/collection/immutable/TreeMap.scala index b845b76026..2d1bf0f6b1 100644 --- a/src/library/scala/collection/immutable/TreeMap.scala +++ b/src/library/scala/collection/immutable/TreeMap.scala @@ -44,8 +44,7 @@ object TreeMap extends ImmutableSortedMapFactory[TreeMap] { * @define mayNotTerminateInf * @define willNotTerminateInf */ -@deprecatedInheritance("The implementation details of immutable tree maps make inheriting from them unwise.", "2.11.0") -class TreeMap[A, +B] private (tree: RB.Tree[A, B])(implicit val ordering: Ordering[A]) +final class TreeMap[A, +B] private (tree: RB.Tree[A, B])(implicit val ordering: Ordering[A]) extends SortedMap[A, B] with SortedMapLike[A, B, TreeMap[A, B]] with MapLike[A, B, TreeMap[A, B]] diff --git a/src/library/scala/collection/immutable/TreeSet.scala b/src/library/scala/collection/immutable/TreeSet.scala index 2800030d67..2cdf3b3521 100644 --- a/src/library/scala/collection/immutable/TreeSet.scala +++ b/src/library/scala/collection/immutable/TreeSet.scala @@ -49,8 +49,7 @@ object TreeSet extends ImmutableSortedSetFactory[TreeSet] { * @define willNotTerminateInf */ @SerialVersionUID(-5685982407650748405L) -@deprecatedInheritance("The implementation details of immutable tree sets make inheriting from them unwise.", "2.11.0") -class TreeSet[A] private (tree: RB.Tree[A, Unit])(implicit val ordering: Ordering[A]) +final class TreeSet[A] private (tree: RB.Tree[A, Unit])(implicit val ordering: Ordering[A]) extends SortedSet[A] with SortedSetLike[A, TreeSet[A]] with Serializable { if (ordering eq null) diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala index 5a9734a99e..1093084b9d 100644 --- a/src/library/scala/collection/immutable/Vector.scala +++ b/src/library/scala/collection/immutable/Vector.scala @@ -11,9 +11,8 @@ package collection package immutable import scala.annotation.unchecked.uncheckedVariance -import scala.compat.Platform import scala.collection.generic._ -import scala.collection.mutable.Builder +import scala.collection.mutable.{Builder, ReusableBuilder} import scala.collection.parallel.immutable.ParVector /** Companion object to the Vector class @@ -24,7 +23,7 @@ object Vector extends IndexedSeqFactory[Vector] { ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]] private[immutable] val NIL = new Vector[Nothing](0, 0, 0) override def empty[A]: Vector[A] = NIL - + // Constants governing concat strategy for performance private final val Log2ConcatFaster = 5 private final val TinyAppendFaster = 2 @@ -40,6 +39,8 @@ object Vector extends IndexedSeqFactory[Vector] { * endian bit-mapped vector trie with a branching factor of 32. Locality is very good, but not * contiguous, which is good for very large sequences. * + * $usesMutableState + * * @see [[http://docs.scala-lang.org/overviews/collections/concrete-immutable-collection-classes.html#vectors "Scala's Collection Library overview"]] * section on `Vectors` for more information. * @@ -59,6 +60,7 @@ object Vector extends IndexedSeqFactory[Vector] { * @define mayNotTerminateInf * @define willNotTerminateInf */ +@SerialVersionUID(-1334388273712300479L) final class Vector[+A] private[immutable] (private[collection] val startIndex: Int, private[collection] val endIndex: Int, focus: Int) extends AbstractSeq[A] with IndexedSeq[A] @@ -69,12 +71,7 @@ extends AbstractSeq[A] with CustomParallelizable[A, ParVector[A]] { self => -override def companion: GenericCompanion[Vector] = Vector - - //assert(startIndex >= 0, startIndex+"<0") - //assert(startIndex <= endIndex, startIndex+">"+endIndex) - //assert(focus >= 0, focus+"<0") - //assert(focus <= endIndex, focus+">"+endIndex) + override def companion: GenericCompanion[Vector] = Vector private[immutable] var dirty = false @@ -98,8 +95,6 @@ override def companion: GenericCompanion[Vector] = Vector s } - - // can still be improved override /*SeqLike*/ def reverseIterator: Iterator[A] = new AbstractIterator[A] { private var i = self.length @@ -111,22 +106,18 @@ override def companion: GenericCompanion[Vector] = Vector } else Iterator.empty.next() } - // TODO: reverse - - // TODO: check performance of foreach/map etc. should override or not? // Ideally, clients will inline calls to map all the way down, including the iterator/builder methods. // In principle, escape analysis could even remove the iterator/builder allocations and do it // with local variables exclusively. But we're not quite there yet ... def apply(index: Int): A = { val idx = checkRangeConvert(index) - //println("get elem: "+index + "/"+idx + "(focus:" +focus+" xor:"+(idx^focus)+" depth:"+depth+")") getElem(idx, idx ^ focus) } private def checkRangeConvert(index: Int) = { val idx = index + startIndex - if (0 <= index && idx < endIndex) + if (index >= 0 && idx < endIndex) idx else throw new IndexOutOfBoundsException(index.toString) @@ -135,7 +126,7 @@ override def companion: GenericCompanion[Vector] = Vector // If we have a default builder, there are faster ways to perform some operations @inline private[this] def isDefaultCBF[A, B, That](bf: CanBuildFrom[Vector[A], B, That]): Boolean = (bf eq IndexedSeq.ReusableCBF) || (bf eq collection.immutable.Seq.ReusableCBF) || (bf eq collection.Seq.ReusableCBF) - + // SeqLike api override def updated[B >: A, That](index: Int, elem: B)(implicit bf: CanBuildFrom[Vector[A], B, That]): That = @@ -189,31 +180,36 @@ override def companion: GenericCompanion[Vector] = Vector Vector.empty } - override /*IterableLike*/ def head: A = { + override /*IterableLike*/ + def head: A = { if (isEmpty) throw new UnsupportedOperationException("empty.head") apply(0) } - override /*TraversableLike*/ def tail: Vector[A] = { + override /*TraversableLike*/ + def tail: Vector[A] = { if (isEmpty) throw new UnsupportedOperationException("empty.tail") drop(1) } - override /*TraversableLike*/ def last: A = { + override /*TraversableLike*/ + def last: A = { if (isEmpty) throw new UnsupportedOperationException("empty.last") - apply(length-1) + apply(length - 1) } - override /*TraversableLike*/ def init: Vector[A] = { + override /*TraversableLike*/ + def init: Vector[A] = { if (isEmpty) throw new UnsupportedOperationException("empty.init") dropRight(1) } - override /*IterableLike*/ def slice(from: Int, until: Int): Vector[A] = + override /*IterableLike*/ + def slice(from: Int, until: Int): Vector[A] = take(until).drop(from) - override /*IterableLike*/ def splitAt(n: Int): (Vector[A], Vector[A]) = (take(n), drop(n)) - + override /*IterableLike*/ + def splitAt(n: Int): (Vector[A], Vector[A]) = (take(n), drop(n)) // concat (suboptimal but avoids worst performance gotchas) override def ++[B >: A, That](that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[Vector[A], B, That]): That = { @@ -225,11 +221,11 @@ override def companion: GenericCompanion[Vector] = Vector val again = if (!that.isTraversableAgain) that.toVector else that.seq again.size match { // Often it's better to append small numbers of elements (or prepend if RHS is a vector) - case n if n <= TinyAppendFaster || n < (this.size >> Log2ConcatFaster) => + case n if n <= TinyAppendFaster || n < (this.size >>> Log2ConcatFaster) => var v: Vector[B] = this for (x <- again) v = v :+ x v.asInstanceOf[That] - case n if this.size < (n >> Log2ConcatFaster) && again.isInstanceOf[Vector[_]] => + case n if this.size < (n >>> Log2ConcatFaster) && again.isInstanceOf[Vector[_]] => var v = again.asInstanceOf[Vector[B]] val ri = this.reverseIterator while (ri.hasNext) v = ri.next +: v @@ -241,8 +237,6 @@ override def companion: GenericCompanion[Vector] = Vector else super.++(that.seq) } - - // semi-private api private[immutable] def updateAt[B >: A](index: Int, elem: B): Vector[B] = { @@ -251,11 +245,10 @@ override def companion: GenericCompanion[Vector] = Vector s.initFrom(this) s.dirty = dirty s.gotoPosWritable(focus, idx, focus ^ idx) // if dirty commit changes; go to new pos and prepare for writing - s.display0(idx & 0x1f) = elem.asInstanceOf[AnyRef] + s.display0(idx & 31) = elem.asInstanceOf[AnyRef] s } - private def gotoPosWritable(oldIndex: Int, newIndex: Int, xor: Int) = if (dirty) { gotoPosWritable1(oldIndex, newIndex, xor) } else { @@ -270,7 +263,7 @@ override def companion: GenericCompanion[Vector] = Vector dirty = true } - private[immutable] def appendFront[B>:A](value: B): Vector[B] = { + private[immutable] def appendFront[B >: A](value: B): Vector[B] = { if (endIndex != startIndex) { val blockIndex = (startIndex - 1) & ~31 val lo = (startIndex - 1) & 31 @@ -284,61 +277,46 @@ override def companion: GenericCompanion[Vector] = Vector s } else { - val freeSpace = ((1<<5*(depth)) - endIndex) // free space at the right given the current tree-structure depth - val shift = freeSpace & ~((1<<5*(depth-1))-1) // number of elements by which we'll shift right (only move at top level) - val shiftBlocks = freeSpace >>> 5*(depth-1) // number of top-level blocks + val freeSpace = (1 << (5 * depth)) - endIndex // free space at the right given the current tree-structure depth + val shift = freeSpace & ~((1 << (5 * (depth - 1))) - 1) // number of elements by which we'll shift right (only move at top level) + val shiftBlocks = freeSpace >>> (5 * (depth - 1)) // number of top-level blocks - //println("----- appendFront " + value + " at " + (startIndex - 1) + " reached block start") if (shift != 0) { // case A: we can shift right on the top level - debug() - //println("shifting right by " + shiftBlocks + " at level " + (depth-1) + " (had "+freeSpace+" free space)") - if (depth > 1) { val newBlockIndex = blockIndex + shift val newFocus = focus + shift + val s = new Vector(startIndex - 1 + shift, endIndex + shift, newBlockIndex) s.initFrom(this) s.dirty = dirty s.shiftTopLevel(0, shiftBlocks) // shift right by n blocks - s.debug() s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // maybe create pos; prepare for writing s.display0(lo) = value.asInstanceOf[AnyRef] - //assert(depth == s.depth) s } else { val newBlockIndex = blockIndex + 32 val newFocus = focus - //assert(newBlockIndex == 0) - //assert(newFocus == 0) - val s = new Vector(startIndex - 1 + shift, endIndex + shift, newBlockIndex) s.initFrom(this) s.dirty = dirty s.shiftTopLevel(0, shiftBlocks) // shift right by n elements s.gotoPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // prepare for writing - s.display0(shift-1) = value.asInstanceOf[AnyRef] - s.debug() + s.display0(shift - 1) = value.asInstanceOf[AnyRef] s } } else if (blockIndex < 0) { // case B: we need to move the whole structure - val move = (1 << 5*(depth+1)) - (1 << 5*(depth)) - //println("moving right by " + move + " at level " + (depth-1) + " (had "+freeSpace+" free space)") - + val move = (1 << (5 * (depth + 1))) - (1 << (5 * depth)) val newBlockIndex = blockIndex + move val newFocus = focus + move - val s = new Vector(startIndex - 1 + move, endIndex + move, newBlockIndex) s.initFrom(this) s.dirty = dirty - s.debug() s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // could optimize: we know it will create a whole branch s.display0(lo) = value.asInstanceOf[AnyRef] - s.debug() - //assert(s.depth == depth+1) s } else { val newBlockIndex = blockIndex @@ -349,31 +327,26 @@ override def companion: GenericCompanion[Vector] = Vector s.dirty = dirty s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(lo) = value.asInstanceOf[AnyRef] - //assert(s.depth == depth) s } - } } else { // empty vector, just insert single element at the back val elems = new Array[AnyRef](32) elems(31) = value.asInstanceOf[AnyRef] - val s = new Vector(31,32,0) + val s = new Vector(31, 32, 0) s.depth = 1 s.display0 = elems s } } - private[immutable] def appendBack[B>:A](value: B): Vector[B] = { -// //println("------- append " + value) -// debug() + private[immutable] def appendBack[B >: A](value: B): Vector[B] = { if (endIndex != startIndex) { val blockIndex = endIndex & ~31 val lo = endIndex & 31 if (endIndex != blockIndex) { - //println("will make writable block (from "+focus+") at: " + blockIndex) val s = new Vector(startIndex, endIndex + 1, blockIndex) s.initFrom(this) s.dirty = dirty @@ -381,41 +354,31 @@ override def companion: GenericCompanion[Vector] = Vector s.display0(lo) = value.asInstanceOf[AnyRef] s } else { - val shift = startIndex & ~((1<<5*(depth-1))-1) - val shiftBlocks = startIndex >>> 5*(depth-1) - - //println("----- appendBack " + value + " at " + endIndex + " reached block end") + val shift = startIndex & ~((1 << (5 * (depth - 1))) - 1) + val shiftBlocks = startIndex >>> (5 * (depth - 1)) if (shift != 0) { - debug() - //println("shifting left by " + shiftBlocks + " at level " + (depth-1) + " (had "+startIndex+" free space)") if (depth > 1) { val newBlockIndex = blockIndex - shift val newFocus = focus - shift + val s = new Vector(startIndex - shift, endIndex + 1 - shift, newBlockIndex) s.initFrom(this) s.dirty = dirty s.shiftTopLevel(shiftBlocks, 0) // shift left by n blocks - s.debug() s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(lo) = value.asInstanceOf[AnyRef] - s.debug() - //assert(depth == s.depth) s } else { val newBlockIndex = blockIndex - 32 val newFocus = focus - //assert(newBlockIndex == 0) - //assert(newFocus == 0) - val s = new Vector(startIndex - shift, endIndex + 1 - shift, newBlockIndex) s.initFrom(this) s.dirty = dirty s.shiftTopLevel(shiftBlocks, 0) // shift right by n elements s.gotoPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(32 - shift) = value.asInstanceOf[AnyRef] - s.debug() s } } else { @@ -427,18 +390,13 @@ override def companion: GenericCompanion[Vector] = Vector s.dirty = dirty s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(lo) = value.asInstanceOf[AnyRef] - //assert(s.depth == depth+1) might or might not create new level! - if (s.depth == depth+1) { - //println("creating new level " + s.depth + " (had "+0+" free space)") - s.debug() - } s } } } else { val elems = new Array[AnyRef](32) elems(0) = value.asInstanceOf[AnyRef] - val s = new Vector(0,1,0) + val s = new Vector(0, 1, 0) s.depth = 1 s.display0 = elems s @@ -449,39 +407,39 @@ override def companion: GenericCompanion[Vector] = Vector // low-level implementation (needs cleanup, maybe move to util class) private def shiftTopLevel(oldLeft: Int, newLeft: Int) = (depth - 1) match { - case 0 => - display0 = copyRange(display0, oldLeft, newLeft) - case 1 => - display1 = copyRange(display1, oldLeft, newLeft) - case 2 => - display2 = copyRange(display2, oldLeft, newLeft) - case 3 => - display3 = copyRange(display3, oldLeft, newLeft) - case 4 => - display4 = copyRange(display4, oldLeft, newLeft) - case 5 => - display5 = copyRange(display5, oldLeft, newLeft) + case 0 => display0 = copyRange(display0, oldLeft, newLeft) + case 1 => display1 = copyRange(display1, oldLeft, newLeft) + case 2 => display2 = copyRange(display2, oldLeft, newLeft) + case 3 => display3 = copyRange(display3, oldLeft, newLeft) + case 4 => display4 = copyRange(display4, oldLeft, newLeft) + case 5 => display5 = copyRange(display5, oldLeft, newLeft) } private def zeroLeft(array: Array[AnyRef], index: Int): Unit = { - var i = 0; while (i < index) { array(i) = null; i+=1 } + var i = 0 + while (i < index) { + array(i) = null + i += 1 + } } private def zeroRight(array: Array[AnyRef], index: Int): Unit = { - var i = index; while (i < array.length) { array(i) = null; i+=1 } + var i = index + while (i < array.length) { + array(i) = null + i += 1 + } } private def copyLeft(array: Array[AnyRef], right: Int): Array[AnyRef] = { -// if (array eq null) -// println("OUCH!!! " + right + "/" + depth + "/"+startIndex + "/" + endIndex + "/" + focus) - val a2 = new Array[AnyRef](array.length) - Platform.arraycopy(array, 0, a2, 0, right) - a2 + val copy = new Array[AnyRef](array.length) + java.lang.System.arraycopy(array, 0, copy, 0, right) + copy } private def copyRight(array: Array[AnyRef], left: Int): Array[AnyRef] = { - val a2 = new Array[AnyRef](array.length) - Platform.arraycopy(array, left, a2, left, a2.length - left) - a2 + val copy = new Array[AnyRef](array.length) + java.lang.System.arraycopy(array, left, copy, left, copy.length - left) + copy } private def preClean(depth: Int) = { @@ -513,38 +471,33 @@ override def companion: GenericCompanion[Vector] = Vector // requires structure is at index cutIndex and writable at level 0 private def cleanLeftEdge(cutIndex: Int) = { - if (cutIndex < (1 << 5)) { + if (cutIndex < (1 << 5)) { zeroLeft(display0, cutIndex) - } else - if (cutIndex < (1 << 10)) { - zeroLeft(display0, cutIndex & 0x1f) - display1 = copyRight(display1, (cutIndex >>> 5)) - } else - if (cutIndex < (1 << 15)) { - zeroLeft(display0, cutIndex & 0x1f) - display1 = copyRight(display1, (cutIndex >>> 5) & 0x1f) - display2 = copyRight(display2, (cutIndex >>> 10)) - } else - if (cutIndex < (1 << 20)) { - zeroLeft(display0, cutIndex & 0x1f) - display1 = copyRight(display1, (cutIndex >>> 5) & 0x1f) - display2 = copyRight(display2, (cutIndex >>> 10) & 0x1f) - display3 = copyRight(display3, (cutIndex >>> 15)) - } else - if (cutIndex < (1 << 25)) { - zeroLeft(display0, cutIndex & 0x1f) - display1 = copyRight(display1, (cutIndex >>> 5) & 0x1f) - display2 = copyRight(display2, (cutIndex >>> 10) & 0x1f) - display3 = copyRight(display3, (cutIndex >>> 15) & 0x1f) - display4 = copyRight(display4, (cutIndex >>> 20)) - } else - if (cutIndex < (1 << 30)) { - zeroLeft(display0, cutIndex & 0x1f) - display1 = copyRight(display1, (cutIndex >>> 5) & 0x1f) - display2 = copyRight(display2, (cutIndex >>> 10) & 0x1f) - display3 = copyRight(display3, (cutIndex >>> 15) & 0x1f) - display4 = copyRight(display4, (cutIndex >>> 20) & 0x1f) - display5 = copyRight(display5, (cutIndex >>> 25)) + } else if (cutIndex < (1 << 10)) { + zeroLeft(display0, cutIndex & 31) + display1 = copyRight(display1, cutIndex >>> 5) + } else if (cutIndex < (1 << 15)) { + zeroLeft(display0, cutIndex & 31) + display1 = copyRight(display1, (cutIndex >>> 5) & 31) + display2 = copyRight(display2, cutIndex >>> 10) + } else if (cutIndex < (1 << 20)) { + zeroLeft(display0, cutIndex & 31) + display1 = copyRight(display1, (cutIndex >>> 5) & 31) + display2 = copyRight(display2, (cutIndex >>> 10) & 31) + display3 = copyRight(display3, cutIndex >>> 15) + } else if (cutIndex < (1 << 25)) { + zeroLeft(display0, cutIndex & 31) + display1 = copyRight(display1, (cutIndex >>> 5) & 31) + display2 = copyRight(display2, (cutIndex >>> 10) & 31) + display3 = copyRight(display3, (cutIndex >>> 15) & 31) + display4 = copyRight(display4, cutIndex >>> 20) + } else if (cutIndex < (1 << 30)) { + zeroLeft(display0, cutIndex & 31) + display1 = copyRight(display1, (cutIndex >>> 5) & 31) + display2 = copyRight(display2, (cutIndex >>> 10) & 31) + display3 = copyRight(display3, (cutIndex >>> 15) & 31) + display4 = copyRight(display4, (cutIndex >>> 20) & 31) + display5 = copyRight(display5, cutIndex >>> 25) } else { throw new IllegalArgumentException() } @@ -552,49 +505,43 @@ override def companion: GenericCompanion[Vector] = Vector // requires structure is writable and at index cutIndex private def cleanRightEdge(cutIndex: Int) = { - // we're actually sitting one block left if cutIndex lies on a block boundary // this means that we'll end up erasing the whole block!! - if (cutIndex <= (1 << 5)) { + if (cutIndex <= (1 << 5)) { zeroRight(display0, cutIndex) - } else - if (cutIndex <= (1 << 10)) { - zeroRight(display0, ((cutIndex-1) & 0x1f) + 1) - display1 = copyLeft(display1, (cutIndex >>> 5)) - } else - if (cutIndex <= (1 << 15)) { - zeroRight(display0, ((cutIndex-1) & 0x1f) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 0x1f) + 1) - display2 = copyLeft(display2, (cutIndex >>> 10)) - } else - if (cutIndex <= (1 << 20)) { - zeroRight(display0, ((cutIndex-1) & 0x1f) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 0x1f) + 1) - display2 = copyLeft(display2, (((cutIndex-1) >>> 10) & 0x1f) + 1) - display3 = copyLeft(display3, (cutIndex >>> 15)) - } else - if (cutIndex <= (1 << 25)) { - zeroRight(display0, ((cutIndex-1) & 0x1f) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 0x1f) + 1) - display2 = copyLeft(display2, (((cutIndex-1) >>> 10) & 0x1f) + 1) - display3 = copyLeft(display3, (((cutIndex-1) >>> 15) & 0x1f) + 1) - display4 = copyLeft(display4, (cutIndex >>> 20)) - } else - if (cutIndex <= (1 << 30)) { - zeroRight(display0, ((cutIndex-1) & 0x1f) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 0x1f) + 1) - display2 = copyLeft(display2, (((cutIndex-1) >>> 10) & 0x1f) + 1) - display3 = copyLeft(display3, (((cutIndex-1) >>> 15) & 0x1f) + 1) - display4 = copyLeft(display4, (((cutIndex-1) >>> 20) & 0x1f) + 1) - display5 = copyLeft(display5, (cutIndex >>> 25)) + } else if (cutIndex <= (1 << 10)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, cutIndex >>> 5) + } else if (cutIndex <= (1 << 15)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, (((cutIndex - 1) >>> 5) & 31) + 1) + display2 = copyLeft(display2, cutIndex >>> 10) + } else if (cutIndex <= (1 << 20)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, (((cutIndex - 1) >>> 5) & 31) + 1) + display2 = copyLeft(display2, (((cutIndex - 1) >>> 10) & 31) + 1) + display3 = copyLeft(display3, cutIndex >>> 15) + } else if (cutIndex <= (1 << 25)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, (((cutIndex - 1) >>> 5) & 31) + 1) + display2 = copyLeft(display2, (((cutIndex - 1) >>> 10) & 31) + 1) + display3 = copyLeft(display3, (((cutIndex - 1) >>> 15) & 31) + 1) + display4 = copyLeft(display4, cutIndex >>> 20) + } else if (cutIndex <= (1 << 30)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, (((cutIndex - 1) >>> 5) & 31) + 1) + display2 = copyLeft(display2, (((cutIndex - 1) >>> 10) & 31) + 1) + display3 = copyLeft(display3, (((cutIndex - 1) >>> 15) & 31) + 1) + display4 = copyLeft(display4, (((cutIndex - 1) >>> 20) & 31) + 1) + display5 = copyLeft(display5, cutIndex >>> 25) } else { throw new IllegalArgumentException() } } private def requiredDepth(xor: Int) = { - if (xor < (1 << 5)) 1 + if (xor < (1 << 5)) 1 else if (xor < (1 << 10)) 2 else if (xor < (1 << 15)) 3 else if (xor < (1 << 20)) 4 @@ -607,24 +554,11 @@ override def companion: GenericCompanion[Vector] = Vector val blockIndex = cutIndex & ~31 val xor = cutIndex ^ (endIndex - 1) val d = requiredDepth(xor) - val shift = (cutIndex & ~((1 << (5*d))-1)) - - //println("cut front at " + cutIndex + ".." + endIndex + " (xor: "+xor+" shift: " + shift + " d: " + d +")") - -/* - val s = new Vector(cutIndex-shift, endIndex-shift, blockIndex-shift) - s.initFrom(this) - if (s.depth > 1) - s.gotoPos(blockIndex, focus ^ blockIndex) - s.depth = d - s.stabilize(blockIndex-shift) - s.cleanLeftEdge(cutIndex-shift) - s -*/ + val shift = cutIndex & ~((1 << (5 * d)) - 1) // need to init with full display iff going to cutIndex requires swapping block at level >= d - val s = new Vector(cutIndex-shift, endIndex-shift, blockIndex-shift) + val s = new Vector(cutIndex - shift, endIndex - shift, blockIndex - shift) s.initFrom(this) s.dirty = dirty s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex) @@ -637,25 +571,18 @@ override def companion: GenericCompanion[Vector] = Vector val blockIndex = (cutIndex - 1) & ~31 val xor = startIndex ^ (cutIndex - 1) val d = requiredDepth(xor) - val shift = (startIndex & ~((1 << (5*d))-1)) - -/* - println("cut back at " + startIndex + ".." + cutIndex + " (xor: "+xor+" d: " + d +")") - if (cutIndex == blockIndex + 32) - println("OUCH!!!") -*/ - val s = new Vector(startIndex-shift, cutIndex-shift, blockIndex-shift) + val shift = startIndex & ~((1 << (5 * d)) - 1) + + val s = new Vector(startIndex - shift, cutIndex - shift, blockIndex - shift) s.initFrom(this) s.dirty = dirty s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex) s.preClean(d) - s.cleanRightEdge(cutIndex-shift) + s.cleanRightEdge(cutIndex - shift) s } - } - class VectorIterator[+A](_startIndex: Int, endIndex: Int) extends AbstractIterator[A] with Iterator[A] @@ -678,7 +605,7 @@ extends AbstractIterator[A] if (lo == endLo) { if (blockIndex + lo < endIndex) { - val newBlockIndex = blockIndex+32 + val newBlockIndex = blockIndex + 32 gotoNextBlockStart(newBlockIndex, blockIndex ^ newBlockIndex) blockIndex = newBlockIndex @@ -704,8 +631,8 @@ extends AbstractIterator[A] } } - -final class VectorBuilder[A]() extends Builder[A,Vector[A]] with VectorPointer[A @uncheckedVariance] { +/** A class to build instances of `Vector`. This builder is reusable. */ +final class VectorBuilder[A]() extends ReusableBuilder[A, Vector[A]] with VectorPointer[A @uncheckedVariance] { // possible alternative: start with display0 = null, blockIndex = -32, lo = 32 // to avoid allocating initial array if the result will be empty anyways @@ -716,9 +643,9 @@ final class VectorBuilder[A]() extends Builder[A,Vector[A]] with VectorPointer[A private var blockIndex = 0 private var lo = 0 - def += (elem: A): this.type = { + def +=(elem: A): this.type = { if (lo >= display0.length) { - val newBlockIndex = blockIndex+32 + val newBlockIndex = blockIndex + 32 gotoNextBlockStartWritable(newBlockIndex, blockIndex ^ newBlockIndex) blockIndex = newBlockIndex lo = 0 @@ -728,8 +655,7 @@ final class VectorBuilder[A]() extends Builder[A,Vector[A]] with VectorPointer[A this } - override def ++=(xs: TraversableOnce[A]): this.type = - super.++=(xs) + override def ++=(xs: TraversableOnce[A]): this.type = super.++=(xs) def result: Vector[A] = { val size = blockIndex + lo @@ -749,10 +675,8 @@ final class VectorBuilder[A]() extends Builder[A,Vector[A]] with VectorPointer[A } } - - private[immutable] trait VectorPointer[T] { - private[immutable] var depth: Int = _ + private[immutable] var depth: Int = _ private[immutable] var display0: Array[AnyRef] = _ private[immutable] var display1: Array[AnyRef] = _ private[immutable] var display2: Array[AnyRef] = _ @@ -797,98 +721,102 @@ private[immutable] trait VectorPointer[T] { } } - // requires structure is at pos oldIndex = xor ^ index private[immutable] final def getElem(index: Int, xor: Int): T = { - if (xor < (1 << 5)) { // level = 0 - display0(index & 31).asInstanceOf[T] - } else - if (xor < (1 << 10)) { // level = 1 - display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else - if (xor < (1 << 15)) { // level = 2 - display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]]((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else - if (xor < (1 << 20)) { // level = 3 - display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]]((index >> 10) & 31).asInstanceOf[Array[AnyRef]]((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else - if (xor < (1 << 25)) { // level = 4 - display4((index >> 20) & 31).asInstanceOf[Array[AnyRef]]((index >> 15) & 31).asInstanceOf[Array[AnyRef]]((index >> 10) & 31).asInstanceOf[Array[AnyRef]]((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else - if (xor < (1 << 30)) { // level = 5 - display5((index >> 25) & 31).asInstanceOf[Array[AnyRef]]((index >> 20) & 31).asInstanceOf[Array[AnyRef]]((index >> 15) & 31).asInstanceOf[Array[AnyRef]]((index >> 10) & 31).asInstanceOf[Array[AnyRef]]((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else { // level = 6 + if (xor < (1 << 5)) { // level = 0 + (display0 + (index & 31).asInstanceOf[T]) + } else if (xor < (1 << 10)) { // level = 1 + (display1 + ((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + (index & 31).asInstanceOf[T]) + } else if (xor < (1 << 15)) { // level = 2 + (display2 + ((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + (index & 31).asInstanceOf[T]) + } else if (xor < (1 << 20)) { // level = 3 + (display3 + ((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + (index & 31).asInstanceOf[T]) + } else if (xor < (1 << 25)) { // level = 4 + (display4 + ((index >>> 20) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + (index & 31).asInstanceOf[T]) + } else if (xor < (1 << 30)) { // level = 5 + (display5 + ((index >>> 25) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 20) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + (index & 31).asInstanceOf[T]) + } else { // level = 6 throw new IllegalArgumentException() } } - // go to specific position // requires structure is at pos oldIndex = xor ^ index, // ensures structure is at pos index private[immutable] final def gotoPos(index: Int, xor: Int): Unit = { - if (xor < (1 << 5)) { // level = 0 (could maybe removed) - } else - if (xor < (1 << 10)) { // level = 1 - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 15)) { // level = 2 - display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 20)) { // level = 3 - display2 = display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 25)) { // level = 4 - display3 = display4((index >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 30)) { // level = 5 - display4 = display5((index >> 25) & 31).asInstanceOf[Array[AnyRef]] - display3 = display4((index >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else { // level = 6 + if (xor < (1 << 5)) { // level = 0 + // we're already at the block start pos + } else if (xor < (1 << 10)) { // level = 1 + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 15)) { // level = 2 + display1 = display2((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 20)) { // level = 3 + display2 = display3((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 25)) { // level = 4 + display3 = display4((index >>> 20) & 31).asInstanceOf[Array[AnyRef]] + display2 = display3((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 30)) { // level = 5 + display4 = display5((index >>> 25) & 31).asInstanceOf[Array[AnyRef]] + display3 = display4((index >>> 20) & 31).asInstanceOf[Array[AnyRef]] + display2 = display3((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + } else { // level = 6 throw new IllegalArgumentException() } } - - // USED BY ITERATOR // xor: oldIndex ^ index private[immutable] final def gotoNextBlockStart(index: Int, xor: Int): Unit = { // goto block start pos - if (xor < (1 << 10)) { // level = 1 - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 15)) { // level = 2 - display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] + if (xor < (1 << 10)) { // level = 1 + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 15)) { // level = 2 + display1 = display2((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] display0 = display1(0).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 20)) { // level = 3 - display2 = display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 20)) { // level = 3 + display2 = display3((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] display1 = display2(0).asInstanceOf[Array[AnyRef]] display0 = display1(0).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 25)) { // level = 4 - display3 = display4((index >> 20) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 25)) { // level = 4 + display3 = display4((index >>> 20) & 31).asInstanceOf[Array[AnyRef]] display2 = display3(0).asInstanceOf[Array[AnyRef]] display1 = display2(0).asInstanceOf[Array[AnyRef]] display0 = display1(0).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 30)) { // level = 5 - display4 = display5((index >> 25) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 30)) { // level = 5 + display4 = display5((index >>> 25) & 31).asInstanceOf[Array[AnyRef]] display3 = display4(0).asInstanceOf[Array[AnyRef]] display2 = display3(0).asInstanceOf[Array[AnyRef]] display1 = display2(0).asInstanceOf[Array[AnyRef]] display0 = display1(0).asInstanceOf[Array[AnyRef]] - } else { // level = 6 + } else { // level = 6 throw new IllegalArgumentException() } } @@ -897,73 +825,65 @@ private[immutable] trait VectorPointer[T] { // xor: oldIndex ^ index private[immutable] final def gotoNextBlockStartWritable(index: Int, xor: Int): Unit = { // goto block start pos - if (xor < (1 << 10)) { // level = 1 - if (depth == 1) { display1 = new Array(32); display1(0) = display0; depth+=1} + if (xor < (1 << 10)) { // level = 1 + if (depth == 1) { display1 = new Array(32); display1(0) = display0; depth += 1 } display0 = new Array(32) - display1((index >> 5) & 31) = display0 - } else - if (xor < (1 << 15)) { // level = 2 - if (depth == 2) { display2 = new Array(32); display2(0) = display1; depth+=1} + display1((index >>> 5) & 31) = display0 + } else if (xor < (1 << 15)) { // level = 2 + if (depth == 2) { display2 = new Array(32); display2(0) = display1; depth += 1 } display0 = new Array(32) display1 = new Array(32) - display1((index >> 5) & 31) = display0 - display2((index >> 10) & 31) = display1 - } else - if (xor < (1 << 20)) { // level = 3 - if (depth == 3) { display3 = new Array(32); display3(0) = display2; depth+=1} + display1((index >>> 5) & 31) = display0 + display2((index >>> 10) & 31) = display1 + } else if (xor < (1 << 20)) { // level = 3 + if (depth == 3) { display3 = new Array(32); display3(0) = display2; depth += 1 } display0 = new Array(32) display1 = new Array(32) display2 = new Array(32) - display1((index >> 5) & 31) = display0 - display2((index >> 10) & 31) = display1 - display3((index >> 15) & 31) = display2 - } else - if (xor < (1 << 25)) { // level = 4 - if (depth == 4) { display4 = new Array(32); display4(0) = display3; depth+=1} + display1((index >>> 5) & 31) = display0 + display2((index >>> 10) & 31) = display1 + display3((index >>> 15) & 31) = display2 + } else if (xor < (1 << 25)) { // level = 4 + if (depth == 4) { display4 = new Array(32); display4(0) = display3; depth += 1 } display0 = new Array(32) display1 = new Array(32) display2 = new Array(32) display3 = new Array(32) - display1((index >> 5) & 31) = display0 - display2((index >> 10) & 31) = display1 - display3((index >> 15) & 31) = display2 - display4((index >> 20) & 31) = display3 - } else - if (xor < (1 << 30)) { // level = 5 - if (depth == 5) { display5 = new Array(32); display5(0) = display4; depth+=1} + display1((index >>> 5) & 31) = display0 + display2((index >>> 10) & 31) = display1 + display3((index >>> 15) & 31) = display2 + display4((index >>> 20) & 31) = display3 + } else if (xor < (1 << 30)) { // level = 5 + if (depth == 5) { display5 = new Array(32); display5(0) = display4; depth += 1 } display0 = new Array(32) display1 = new Array(32) display2 = new Array(32) display3 = new Array(32) display4 = new Array(32) - display1((index >> 5) & 31) = display0 - display2((index >> 10) & 31) = display1 - display3((index >> 15) & 31) = display2 - display4((index >> 20) & 31) = display3 - display5((index >> 25) & 31) = display4 - } else { // level = 6 + display1((index >>> 5) & 31) = display0 + display2((index >>> 10) & 31) = display1 + display3((index >>> 15) & 31) = display2 + display4((index >>> 20) & 31) = display3 + display5((index >>> 25) & 31) = display4 + } else { // level = 6 throw new IllegalArgumentException() } } - - // STUFF BELOW USED BY APPEND / UPDATE - private[immutable] final def copyOf(a: Array[AnyRef]) = { - val b = new Array[AnyRef](a.length) - Platform.arraycopy(a, 0, b, 0, a.length) - b + private[immutable] final def copyOf(a: Array[AnyRef]): Array[AnyRef] = { + val copy = new Array[AnyRef](a.length) + java.lang.System.arraycopy(a, 0, copy, 0, a.length) + copy } - private[immutable] final def nullSlotAndCopy(array: Array[AnyRef], index: Int) = { - //println("copy and null") + private[immutable] final def nullSlotAndCopy(array: Array[AnyRef], index: Int): Array[AnyRef] = { val x = array(index) array(index) = null copyOf(x.asInstanceOf[Array[AnyRef]]) } - // make sure there is no aliasing // requires structure is at pos index // ensures structure is clean and at pos index and writable at all levels except 0 @@ -975,40 +895,39 @@ private[immutable] trait VectorPointer[T] { display3 = copyOf(display3) display2 = copyOf(display2) display1 = copyOf(display1) - display5((index >> 25) & 31) = display4 - display4((index >> 20) & 31) = display3 - display3((index >> 15) & 31) = display2 - display2((index >> 10) & 31) = display1 - display1((index >> 5) & 31) = display0 + display5((index >>> 25) & 31) = display4 + display4((index >>> 20) & 31) = display3 + display3((index >>> 15) & 31) = display2 + display2((index >>> 10) & 31) = display1 + display1((index >>> 5) & 31) = display0 case 4 => display4 = copyOf(display4) display3 = copyOf(display3) display2 = copyOf(display2) display1 = copyOf(display1) - display4((index >> 20) & 31) = display3 - display3((index >> 15) & 31) = display2 - display2((index >> 10) & 31) = display1 - display1((index >> 5) & 31) = display0 + display4((index >>> 20) & 31) = display3 + display3((index >>> 15) & 31) = display2 + display2((index >>> 10) & 31) = display1 + display1((index >>> 5) & 31) = display0 case 3 => display3 = copyOf(display3) display2 = copyOf(display2) display1 = copyOf(display1) - display3((index >> 15) & 31) = display2 - display2((index >> 10) & 31) = display1 - display1((index >> 5) & 31) = display0 + display3((index >>> 15) & 31) = display2 + display2((index >>> 10) & 31) = display1 + display1((index >>> 5) & 31) = display0 case 2 => display2 = copyOf(display2) display1 = copyOf(display1) - display2((index >> 10) & 31) = display1 - display1((index >> 5) & 31) = display0 + display2((index >>> 10) & 31) = display1 + display1((index >>> 5) & 31) = display0 case 1 => display1 = copyOf(display1) - display1((index >> 5) & 31) = display0 + display1((index >>> 5) & 31) = display0 case 0 => } - /// USED IN UPDATE AND APPEND BACK // prepare for writing at an existing position @@ -1018,29 +937,29 @@ private[immutable] trait VectorPointer[T] { private[immutable] final def gotoPosWritable0(newIndex: Int, xor: Int): Unit = (depth - 1) match { case 5 => display5 = copyOf(display5) - display4 = nullSlotAndCopy(display5, (newIndex >> 25) & 31).asInstanceOf[Array[AnyRef]] - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display4 = nullSlotAndCopy(display5, (newIndex >>> 25) & 31) + display3 = nullSlotAndCopy(display4, (newIndex >>> 20) & 31) + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 4 => display4 = copyOf(display4) - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display3 = nullSlotAndCopy(display4, (newIndex >>> 20) & 31) + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 3 => display3 = copyOf(display3) - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 2 => display2 = copyOf(display2) - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 1 => display1 = copyOf(display1) - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 0 => display0 = copyOf(display0) } @@ -1049,64 +968,59 @@ private[immutable] trait VectorPointer[T] { // requires structure is dirty and at pos oldIndex, // ensures structure is dirty and at pos newIndex and writable at level 0 private[immutable] final def gotoPosWritable1(oldIndex: Int, newIndex: Int, xor: Int): Unit = { - if (xor < (1 << 5)) { // level = 0 + if (xor < (1 << 5)) { // level = 0 display0 = copyOf(display0) - } else - if (xor < (1 << 10)) { // level = 1 + } else if (xor < (1 << 10)) { // level = 1 display1 = copyOf(display1) - display1((oldIndex >> 5) & 31) = display0 - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) - } else - if (xor < (1 << 15)) { // level = 2 + display1((oldIndex >>> 5) & 31) = display0 + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) + } else if (xor < (1 << 15)) { // level = 2 display1 = copyOf(display1) display2 = copyOf(display2) - display1((oldIndex >> 5) & 31) = display0 - display2((oldIndex >> 10) & 31) = display1 - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 20)) { // level = 3 + display1((oldIndex >>> 5) & 31) = display0 + display2((oldIndex >>> 10) & 31) = display1 + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) + } else if (xor < (1 << 20)) { // level = 3 display1 = copyOf(display1) display2 = copyOf(display2) display3 = copyOf(display3) - display1((oldIndex >> 5) & 31) = display0 - display2((oldIndex >> 10) & 31) = display1 - display3((oldIndex >> 15) & 31) = display2 - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 25)) { // level = 4 + display1((oldIndex >>> 5) & 31) = display0 + display2((oldIndex >>> 10) & 31) = display1 + display3((oldIndex >>> 15) & 31) = display2 + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) + } else if (xor < (1 << 25)) { // level = 4 display1 = copyOf(display1) display2 = copyOf(display2) display3 = copyOf(display3) display4 = copyOf(display4) - display1((oldIndex >> 5) & 31) = display0 - display2((oldIndex >> 10) & 31) = display1 - display3((oldIndex >> 15) & 31) = display2 - display4((oldIndex >> 20) & 31) = display3 - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 30)) { // level = 5 + display1((oldIndex >>> 5) & 31) = display0 + display2((oldIndex >>> 10) & 31) = display1 + display3((oldIndex >>> 15) & 31) = display2 + display4((oldIndex >>> 20) & 31) = display3 + display3 = nullSlotAndCopy(display4, (newIndex >>> 20) & 31) + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) + } else if (xor < (1 << 30)) { // level = 5 display1 = copyOf(display1) display2 = copyOf(display2) display3 = copyOf(display3) display4 = copyOf(display4) display5 = copyOf(display5) - display1((oldIndex >> 5) & 31) = display0 - display2((oldIndex >> 10) & 31) = display1 - display3((oldIndex >> 15) & 31) = display2 - display4((oldIndex >> 20) & 31) = display3 - display5((oldIndex >> 25) & 31) = display4 - display4 = nullSlotAndCopy(display5, (newIndex >> 25) & 31).asInstanceOf[Array[AnyRef]] - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else { // level = 6 + display1((oldIndex >>> 5) & 31) = display0 + display2((oldIndex >>> 10) & 31) = display1 + display3((oldIndex >>> 15) & 31) = display2 + display4((oldIndex >>> 20) & 31) = display3 + display5((oldIndex >>> 25) & 31) = display4 + display4 = nullSlotAndCopy(display5, (newIndex >>> 25) & 31) + display3 = nullSlotAndCopy(display4, (newIndex >>> 20) & 31) + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) + } else { // level = 6 throw new IllegalArgumentException() } } @@ -1116,117 +1030,83 @@ private[immutable] trait VectorPointer[T] { private[immutable] final def copyRange(array: Array[AnyRef], oldLeft: Int, newLeft: Int) = { val elems = new Array[AnyRef](32) - Platform.arraycopy(array, oldLeft, elems, newLeft, 32 - math.max(newLeft,oldLeft)) + java.lang.System.arraycopy(array, oldLeft, elems, newLeft, 32 - math.max(newLeft, oldLeft)) elems } - - // USED IN APPEND // create a new block at the bottom level (and possibly nodes on its path) and prepares for writing // requires structure is clean and at pos oldIndex, // ensures structure is dirty and at pos newIndex and writable at level 0 private[immutable] final def gotoFreshPosWritable0(oldIndex: Int, newIndex: Int, xor: Int): Unit = { // goto block start pos - if (xor < (1 << 5)) { // level = 0 - //println("XXX clean with low xor") - } else - if (xor < (1 << 10)) { // level = 1 + if (xor < (1 << 5)) { // level = 0 + // we're already at the block start + } else if (xor < (1 << 10)) { // level = 1 if (depth == 1) { display1 = new Array(32) - display1((oldIndex >> 5) & 31) = display0 - depth +=1 + display1((oldIndex >>> 5) & 31) = display0 + depth += 1 } display0 = new Array(32) - } else - if (xor < (1 << 15)) { // level = 2 + } else if (xor < (1 << 15)) { // level = 2 if (depth == 2) { display2 = new Array(32) - display2((oldIndex >> 10) & 31) = display1 - depth +=1 + display2((oldIndex >>> 10) & 31) = display1 + depth += 1 } - display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((newIndex >>> 10) & 31).asInstanceOf[Array[AnyRef]] if (display1 == null) display1 = new Array(32) display0 = new Array(32) - } else - if (xor < (1 << 20)) { // level = 3 + } else if (xor < (1 << 20)) { // level = 3 if (depth == 3) { display3 = new Array(32) - display3((oldIndex >> 15) & 31) = display2 - depth +=1 + display3((oldIndex >>> 15) & 31) = display2 + depth += 1 } - display2 = display3((newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] + display2 = display3((newIndex >>> 15) & 31).asInstanceOf[Array[AnyRef]] if (display2 == null) display2 = new Array(32) - display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((newIndex >>> 10) & 31).asInstanceOf[Array[AnyRef]] if (display1 == null) display1 = new Array(32) display0 = new Array(32) - } else - if (xor < (1 << 25)) { // level = 4 + } else if (xor < (1 << 25)) { // level = 4 if (depth == 4) { display4 = new Array(32) - display4((oldIndex >> 20) & 31) = display3 - depth +=1 + display4((oldIndex >>> 20) & 31) = display3 + depth += 1 } - display3 = display4((newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] + display3 = display4((newIndex >>> 20) & 31).asInstanceOf[Array[AnyRef]] if (display3 == null) display3 = new Array(32) - display2 = display3((newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] + display2 = display3((newIndex >>> 15) & 31).asInstanceOf[Array[AnyRef]] if (display2 == null) display2 = new Array(32) - display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((newIndex >>> 10) & 31).asInstanceOf[Array[AnyRef]] if (display1 == null) display1 = new Array(32) display0 = new Array(32) - } else - if (xor < (1 << 30)) { // level = 5 + } else if (xor < (1 << 30)) { // level = 5 if (depth == 5) { display5 = new Array(32) - display5((oldIndex >> 25) & 31) = display4 - depth +=1 + display5((oldIndex >>> 25) & 31) = display4 + depth += 1 } - display4 = display5((newIndex >> 25) & 31).asInstanceOf[Array[AnyRef]] + display4 = display5((newIndex >>> 25) & 31).asInstanceOf[Array[AnyRef]] if (display4 == null) display4 = new Array(32) - display3 = display4((newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] + display3 = display4((newIndex >>> 20) & 31).asInstanceOf[Array[AnyRef]] if (display3 == null) display3 = new Array(32) - display2 = display3((newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] + display2 = display3((newIndex >>> 15) & 31).asInstanceOf[Array[AnyRef]] if (display2 == null) display2 = new Array(32) - display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((newIndex >>> 10) & 31).asInstanceOf[Array[AnyRef]] if (display1 == null) display1 = new Array(32) display0 = new Array(32) - } else { // level = 6 + } else { // level = 6 throw new IllegalArgumentException() } } - // requires structure is dirty and at pos oldIndex, // ensures structure is dirty and at pos newIndex and writable at level 0 private[immutable] final def gotoFreshPosWritable1(oldIndex: Int, newIndex: Int, xor: Int): Unit = { stabilize(oldIndex) gotoFreshPosWritable0(oldIndex, newIndex, xor) } - - - - - // DEBUG STUFF - - private[immutable] def debug(): Unit = { - return -/* - //println("DISPLAY 5: " + display5 + " ---> " + (if (display5 ne null) display5.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 4: " + display4 + " ---> " + (if (display4 ne null) display4.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 3: " + display3 + " ---> " + (if (display3 ne null) display3.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 2: " + display2 + " ---> " + (if (display2 ne null) display2.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 1: " + display1 + " ---> " + (if (display1 ne null) display1.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 0: " + display0 + " ---> " + (if (display0 ne null) display0.map(x=> if (x eq null) "." else x.toString).mkString(" ") else "null")) -*/ - //println("DISPLAY 5: " + (if (display5 ne null) display5.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 4: " + (if (display4 ne null) display4.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 3: " + (if (display3 ne null) display3.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 2: " + (if (display2 ne null) display2.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 1: " + (if (display1 ne null) display1.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 0: " + (if (display0 ne null) display0.map(x=> if (x eq null) "." else x.toString).mkString(" ") else "null")) - } - - } - diff --git a/src/library/scala/collection/immutable/WrappedString.scala b/src/library/scala/collection/immutable/WrappedString.scala index 7592316650..8726bd2ed9 100644 --- a/src/library/scala/collection/immutable/WrappedString.scala +++ b/src/library/scala/collection/immutable/WrappedString.scala @@ -29,8 +29,7 @@ import mutable.{Builder, StringBuilder} * @define Coll `WrappedString` * @define coll wrapped string */ -@deprecatedInheritance("Inherit from StringLike instead of WrappedString.", "2.11.0") -class WrappedString(val self: String) extends AbstractSeq[Char] with IndexedSeq[Char] with StringLike[WrappedString] { +final class WrappedString(val self: String) extends AbstractSeq[Char] with IndexedSeq[Char] with StringLike[WrappedString] { override protected[this] def thisCollection: WrappedString = this override protected[this] def toCollection(repr: WrappedString): WrappedString = repr |