diff options
| -rw-r--r-- | src/library/scala/collection/immutable/HashMap.scala | 178 | ||||
| -rw-r--r-- | src/library/scala/collection/immutable/HashSet.scala | 173 | ||||
| -rw-r--r-- | src/library/scala/collection/immutable/TrieIteratorBase.scala | 184 | ||||
| -rw-r--r-- | test/files/run/bug3984.scala | 35 |
4 files changed, 271 insertions, 299 deletions
diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala index a21e71158e..93023a3097 100644 --- a/src/library/scala/collection/immutable/HashMap.scala +++ b/src/library/scala/collection/immutable/HashMap.scala @@ -12,12 +12,9 @@ package scala.collection package immutable import generic._ -import annotation.unchecked.uncheckedVariance - - +import annotation.unchecked.{ uncheckedVariance=> uV } import parallel.immutable.ParHashMap - /** This class implements immutable maps using a hash trie. * * '''Note:''' the builder of a hash map returns specialized representations EmptyMap,Map1,..., Map4 @@ -96,7 +93,6 @@ class HashMap[A, +B] extends Map[A,B] with MapLike[A, B, HashMap[A, B]] with Par private type C = (A, B) override def toParMap[D, E](implicit ev: C <:< (D, E)) = par.asInstanceOf[ParHashMap[D, E]] - } /** $factoryInfo @@ -117,7 +113,7 @@ object HashMap extends ImmutableMapFactory[HashMap] { // TODO: add HashMap2, HashMap3, ... - class HashMap1[A,+B](private[HashMap] var key: A, private[HashMap] var hash: Int, private[collection] var value: (B @uncheckedVariance), private[collection] var kv: (A,B @uncheckedVariance)) extends HashMap[A,B] { + class HashMap1[A,+B](private[HashMap] var key: A, private[HashMap] var hash: Int, private[collection] var value: (B @uV), private[collection] var kv: (A,B @uV)) extends HashMap[A,B] { override def size = 1 private[collection] def getKey = key @@ -188,7 +184,7 @@ object HashMap extends ImmutableMapFactory[HashMap] { } } - private[collection] class HashMapCollision1[A,+B](private[HashMap] var hash: Int, var kvs: ListMap[A,B @uncheckedVariance]) extends HashMap[A,B] { + private[collection] class HashMapCollision1[A,+B](private[HashMap] var hash: Int, var kvs: ListMap[A,B @uV]) extends HashMap[A,B] { override def size = kvs.size override def get0(key: A, hash: Int, level: Int): Option[B] = @@ -219,7 +215,7 @@ object HashMap extends ImmutableMapFactory[HashMap] { override def foreach[U](f: ((A, B)) => U): Unit = kvs.foreach(f) override def split: Seq[HashMap[A, B]] = { val (x, y) = kvs.splitAt(kvs.size / 2) - def newhm(lm: ListMap[A, B @uncheckedVariance]) = new HashMapCollision1(hash, lm) + def newhm(lm: ListMap[A, B @uV]) = new HashMapCollision1(hash, lm) List(newhm(x), newhm(y)) } protected override def merge0[B1 >: B](that: HashMap[A, B1], level: Int, merger: Merger[B1]): HashMap[A, B1] = { @@ -230,7 +226,7 @@ object HashMap extends ImmutableMapFactory[HashMap] { } } - class HashTrieMap[A,+B](private[HashMap] var bitmap: Int, private[collection] var elems: Array[HashMap[A,B @uncheckedVariance]], + class HashTrieMap[A,+B](private[HashMap] var bitmap: Int, private[collection] var elems: Array[HashMap[A,B @uV]], private[HashMap] var size0: Int) extends HashMap[A,B] { /* def this (level: Int, m1: HashMap1[A,B], m2: HashMap1[A,B]) = { @@ -316,7 +312,7 @@ object HashMap extends ImmutableMapFactory[HashMap] { } } - override def iterator = new TrieIterator[A, B](elems) + override def iterator: Iterator[(A, B)] = new CovariantTrieIterator[A, B](elems) /* @@ -468,148 +464,35 @@ time { mNew.iterator.foreach( p => ()) } case hm: HashMap[_, _] => this case _ => system.error("section supposed to be unreachable.") } - } - class TrieIterator[A, +B](elems: Array[HashMap[A, B]]) extends Iterator[(A, B)] { - protected var depth = 0 - protected var arrayStack: Array[Array[HashMap[A, B @uncheckedVariance]]] = new Array[Array[HashMap[A,B]]](6) - protected var posStack = new Array[Int](6) - - protected var arrayD: Array[HashMap[A, B @uncheckedVariance]] = elems - protected var posD = 0 - - protected var subIter: Iterator[(A, B @uncheckedVariance)] = null // to traverse collision nodes - - def dupIterator: TrieIterator[A, B] = { - val t = new TrieIterator(elems) - t.depth = depth - t.arrayStack = arrayStack - t.posStack = posStack - t.arrayD = arrayD - t.posD = posD - t.subIter = subIter - t - } - - def hasNext = (subIter ne null) || depth >= 0 + class CovariantTrieIterator[A, +B](elems: Array[HashMap[A, B]]) extends Iterator[(A, B)] { + private[this] val it = new TrieIterator[A, B](elems) + def next = it.next + def hasNext = it.hasNext + } - def next: (A,B) = { - if (subIter ne null) { - val el = subIter.next - if (!subIter.hasNext) - subIter = null - el - } else - next0(arrayD, posD) - } + class TrieIterator[A, B](elems: Array[HashMap[A, B]]) extends TrieIteratorBase[(A, B), HashMap[A, B]](elems) { + import TrieIteratorBase._ - @scala.annotation.tailrec private[this] def next0(elems: Array[HashMap[A,B]], i: Int): (A,B) = { - if (i == elems.length-1) { // reached end of level, pop stack - depth -= 1 - if (depth >= 0) { - arrayD = arrayStack(depth) - posD = posStack(depth) - arrayStack(depth) = null - } else { - arrayD = null - posD = 0 - } - } else - posD += 1 + type This = TrieIterator[A, B] + private[immutable] def recreateIterator() = new TrieIterator(elems) + private[immutable] type ContainerType = HashMap1[A, B] + private[immutable] type TrieType = HashTrieMap[A, B] + private[immutable] type CollisionType = HashMapCollision1[A, B] - elems(i) match { - case m: HashTrieMap[_, _] => // push current pos onto stack and descend - if (depth >= 0) { - arrayStack(depth) = arrayD - posStack(depth) = posD - } - depth += 1 - val elems = m.elems.asInstanceOf[Array[HashMap[A, B]]] - arrayD = elems - posD = 0 - next0(elems, 0) - case m: HashMap1[_, _] => m.ensurePair - case m => - subIter = m.iterator - subIter.next - } + private[immutable] def determineType(x: HashMap[A, B]) = x match { + case _: HashMap1[_, _] => CONTAINER_TYPE + case _: HashTrieMap[_, _] => TRIE_TYPE + case _: HashMapCollision1[_, _] => COLLISION_TYPE } - // assumption: contains 2 or more elements - // splits this iterator into 2 iterators - // returns the 1st iterator, its number of elements, and the second iterator - def split: ((Iterator[(A, B)], Int), Iterator[(A, B)]) = { - def collisionToArray(c: HashMapCollision1[_, _]) = - c.asInstanceOf[HashMapCollision1[A, B]].kvs.toArray map { HashMap() + _ } - def arrayToIterators(arr: Array[HashMap[A, B]]) = { - val (fst, snd) = arr.splitAt(arr.length / 2) - val szsnd = snd.foldLeft(0)(_ + _.size) - ((new TrieIterator(snd), szsnd), new TrieIterator(fst)) - } - def splitArray(ad: Array[HashMap[A, B]]): ((Iterator[(A, B)], Int), Iterator[(A, B)]) = if (ad.length > 1) { - arrayToIterators(ad) - } else ad(0) match { - case c: HashMapCollision1[a, b] => arrayToIterators(collisionToArray(c.asInstanceOf[HashMapCollision1[A, B]])) - case hm: HashTrieMap[a, b] => splitArray(hm.elems.asInstanceOf[Array[HashMap[A, B]]]) - } - - // 0) simple case: no elements have been iterated - simply divide arrayD - if (arrayD != null && depth == 0 && posD == 0) { - return splitArray(arrayD) - } - - // otherwise, some elements have been iterated over - // 1) collision case: if we have a subIter, we return subIter and elements after it - if (subIter ne null) { - val buff = subIter.toBuffer - subIter = null - ((buff.iterator, buff.length), this) - } else { - // otherwise find the topmost array stack element - if (depth > 0) { - // 2) topmost comes before (is not) arrayD - // steal a portion of top to create a new iterator - val topmost = arrayStack(0) - if (posStack(0) == arrayStack(0).length - 1) { - // 2a) only a single entry left on top - // this means we have to modify this iterator - pop topmost - val snd = Array(arrayStack(0).last) - val szsnd = snd(0).size - // modify this - pop - depth -= 1 - arrayStack = arrayStack.tail ++ Array[Array[HashMap[A, B]]](null) - posStack = posStack.tail ++ Array[Int](0) - // we know that `this` is not empty, since it had something on the arrayStack and arrayStack elements are always non-empty - ((new TrieIterator[A, B](snd), szsnd), this) - } else { - // 2b) more than a single entry left on top - val (fst, snd) = arrayStack(0).splitAt(arrayStack(0).length - (arrayStack(0).length - posStack(0) + 1) / 2) - arrayStack(0) = fst - val szsnd = snd.foldLeft(0)(_ + _.size) - ((new TrieIterator[A, B](snd), szsnd), this) - } - } else { - // 3) no topmost element (arrayD is at the top) - // steal a portion of it and update this iterator - if (posD == arrayD.length - 1) { - // 3a) positioned at the last element of arrayD - val arr: Array[HashMap[A, B]] = arrayD(posD) match { - case c: HashMapCollision1[a, b] => collisionToArray(c).asInstanceOf[Array[HashMap[A, B]]] - case ht: HashTrieMap[_, _] => ht.asInstanceOf[HashTrieMap[A, B]].elems - case _ => system.error("cannot divide single element") - } - arrayToIterators(arr) - } else { - // 3b) arrayD has more free elements - val (fst, snd) = arrayD.splitAt(arrayD.length - (arrayD.length - posD + 1) / 2) - arrayD = fst - val szsnd = snd.foldLeft(0)(_ + _.size) - ((new TrieIterator[A, B](snd), szsnd), this) - } - } - } - } + private[immutable] def getElem(cc: ContainerType) = cc.ensurePair + private[immutable] def getElems(t: TrieType) = t.elems + private[immutable] def collisionToArray(c: CollisionType) = c.kvs map (x => HashMap(x)) toArray + private[immutable] def newThisType(xs: Array[HashMap[A, B]]) = new TrieIterator(xs) + private[immutable] def newDeepArray(size: Int) = new Array[Array[HashMap[A, B]]](size) + private[immutable] def newSingleArray(el: HashMap[A, B]) = Array(el) } private def check[K](x: HashMap[K, _], y: HashMap[K, _], xy: HashMap[K, _]) = { // TODO remove this debugging helper @@ -631,7 +514,8 @@ time { mNew.iterator.foreach( p => ()) } } else true } - @SerialVersionUID(2L) private class SerializationProxy[A,B](@transient private var orig: HashMap[A, B]) extends Serializable { + @SerialVersionUID(2L) + private class SerializationProxy[A,B](@transient private var orig: HashMap[A, B]) extends Serializable { private def writeObject(out: java.io.ObjectOutputStream) { val s = orig.size out.writeInt(s) @@ -653,6 +537,4 @@ time { mNew.iterator.foreach( p => ()) } private def readResolve(): AnyRef = orig } - } - diff --git a/src/library/scala/collection/immutable/HashSet.scala b/src/library/scala/collection/immutable/HashSet.scala index 6164b96634..1bf3b795f2 100644 --- a/src/library/scala/collection/immutable/HashSet.scala +++ b/src/library/scala/collection/immutable/HashSet.scala @@ -12,8 +12,6 @@ package scala.collection package immutable import generic._ -import annotation.unchecked.uncheckedVariance - import collection.parallel.immutable.ParHashSet /** This class implements immutable sets using a hash trie. @@ -81,11 +79,8 @@ class HashSet[A] extends Set[A] protected def removed0(key: A, hash: Int, level: Int): HashSet[A] = this protected def writeReplace(): AnyRef = new HashSet.SerializationProxy(this) - override def toParIterable = par - override def toParSet[B >: A] = par.asInstanceOf[ParHashSet[B]] - } /** $factoryInfo @@ -100,6 +95,29 @@ class HashSet[A] extends Set[A] * @define willNotTerminateInf */ object HashSet extends ImmutableSetFactory[HashSet] { + + class TrieIterator[A](elems: Array[HashSet[A]]) extends TrieIteratorBase[A, HashSet[A]](elems) { + import TrieIteratorBase._ + + type This = TrieIterator[A] + + private[immutable] def recreateIterator() = new TrieIterator(elems) + private[immutable] type ContainerType = HashSet1[A] + private[immutable] type TrieType = HashTrieSet[A] + private[immutable] type CollisionType = HashSetCollision1[A] + private[immutable] def determineType(x: HashSet[A]) = x match { + case _: HashSet1[_] => CONTAINER_TYPE + case _: HashTrieSet[_] => TRIE_TYPE + case _: HashSetCollision1[_] => COLLISION_TYPE + } + private[immutable] def getElem(cc: ContainerType): A = cc.key + private[immutable] def getElems(t: TrieType) = t.elems + private[immutable] def collisionToArray(c: CollisionType) = c.ks map (x => HashSet(x)) toArray + private[immutable] def newThisType(xs: Array[HashSet[A]]) = new TrieIterator(xs) + private[immutable] def newDeepArray(size: Int) = new Array[Array[HashSet[A]]](size) + private[immutable] def newSingleArray(el: HashSet[A]) = Array(el) + } + /** $setCanBuildFromInfo */ implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, HashSet[A]] = setCanBuildFrom[A] override def empty[A]: HashSet[A] = EmptyHashSet.asInstanceOf[HashSet[A]] @@ -135,7 +153,7 @@ object HashSet extends ImmutableSetFactory[HashSet] { override def foreach[U](f: A => U): Unit = f(key) } - private class HashSetCollision1[A](private[HashSet] var hash: Int, var ks: ListSet[A]) extends HashSet[A] { + private[immutable] class HashSetCollision1[A](private[HashSet] var hash: Int, var ks: ListSet[A]) extends HashSet[A] { override def size = ks.size override def get0(key: A, hash: Int, level: Int): Boolean = @@ -272,7 +290,6 @@ time { mNew.iterator.foreach( p => ()) } time { mNew.iterator.foreach( p => ()) } */ - override def foreach[U](f: A => U): Unit = { var i = 0; while (i < elems.length) { @@ -282,148 +299,6 @@ time { mNew.iterator.foreach( p => ()) } } } - - class TrieIterator[A](elems: Array[HashSet[A]]) extends Iterator[A] { - protected var depth = 0 - protected var arrayStack = new Array[Array[HashSet[A]]](6) - protected var posStack = new Array[Int](6) - - protected var arrayD = elems - protected var posD = 0 - - protected var subIter: Iterator[A] = null // to traverse collision nodes - - def dupIterator: TrieIterator[A] = { - val t = new TrieIterator(elems) - t.depth = depth - t.arrayStack = arrayStack - t.posStack = posStack - t.arrayD = arrayD - t.posD = posD - t.subIter = subIter - t - } - - def hasNext = (subIter ne null) || depth >= 0 - - def next: A = { - if (subIter ne null) { - val el = subIter.next - if (!subIter.hasNext) - subIter = null - el - } else - next0(arrayD, posD) - } - - @scala.annotation.tailrec private[this] def next0(elems: Array[HashSet[A]], i: Int): A = { - if (i == elems.length - 1) { // reached end of level, pop stack - depth -= 1 - if (depth >= 0) { - arrayD = arrayStack(depth) - posD = posStack(depth) - arrayStack(depth) = null - } else { - arrayD = null - posD = 0 - } - } else - posD += 1 - - elems(i) match { - case m: HashTrieSet[_] => // push current pos onto stack and descend - if (depth >= 0) { - arrayStack(depth) = arrayD - posStack(depth) = posD - } - depth += 1 - val elems = m.elems.asInstanceOf[Array[HashSet[A]]] - arrayD = elems - posD = 0 - next0(elems, 0) - case m: HashSet1[_] => m.key - case m => - subIter = m.iterator - next - } - } - - // assumption: contains 2 or more elements - // splits this iterator into 2 iterators - // returns the 1st iterator, its number of elements, and the second iterator - def split: ((Iterator[A], Int), Iterator[A]) = { - def collisionToArray(c: HashSetCollision1[_]) = - c.asInstanceOf[HashSetCollision1[A]].ks.toList map { HashSet() + _ } toArray - def arrayToIterators(arr: Array[HashSet[A]]) = { - val (fst, snd) = arr.splitAt(arr.length / 2) - val szsnd = snd.foldLeft(0)(_ + _.size) - ((new TrieIterator(snd), szsnd), new TrieIterator(fst)) - } - def splitArray(ad: Array[HashSet[A]]): ((Iterator[A], Int), Iterator[A]) = if (ad.length > 1) { - arrayToIterators(ad) - } else ad(0) match { - case c: HashSetCollision1[a] => arrayToIterators(collisionToArray(c.asInstanceOf[HashSetCollision1[A]])) - case hm: HashTrieSet[a] => splitArray(hm.elems.asInstanceOf[Array[HashSet[A]]]) - } - - // 0) simple case: no elements have been iterated - simply divide arrayD - if (arrayD != null && depth == 0 && posD == 0) { - return splitArray(arrayD) - } - - // otherwise, some elements have been iterated over - // 1) collision case: if we have a subIter, we return subIter and elements after it - if (subIter ne null) { - val buff = subIter.toBuffer - subIter = null - ((buff.iterator, buff.length), this) - } else { - // otherwise find the topmost array stack element - if (depth > 0) { - // 2) topmost comes before (is not) arrayD - // steal a portion of top to create a new iterator - val topmost = arrayStack(0) - if (posStack(0) == arrayStack(0).length - 1) { - // 2a) only a single entry left on top - // this means we have to modify this iterator - pop topmost - val snd = Array(arrayStack(0).last) - val szsnd = snd(0).size - // modify this - pop - depth -= 1 - arrayStack = arrayStack.tail ++ Array[Array[HashSet[A]]](null) - posStack = posStack.tail ++ Array[Int](0) - // we know that `this` is not empty, since it had something on the arrayStack and arrayStack elements are always non-empty - ((new TrieIterator[A](snd), szsnd), this) - } else { - // 2b) more than a single entry left on top - val (fst, snd) = arrayStack(0).splitAt(arrayStack(0).length - (arrayStack(0).length - posStack(0) + 1) / 2) - arrayStack(0) = fst - val szsnd = snd.foldLeft(0)(_ + _.size) - ((new TrieIterator[A](snd), szsnd), this) - } - } else { - // 3) no topmost element (arrayD is at the top) - // steal a portion of it and update this iterator - if (posD == arrayD.length - 1) { - // 3a) positioned at the last element of arrayD - val arr: Array[HashSet[A]] = arrayD(posD) match { - case c: HashSetCollision1[a] => collisionToArray(c).asInstanceOf[Array[HashSet[A]]] - case ht: HashTrieSet[_] => ht.asInstanceOf[HashTrieSet[A]].elems - case _ => system.error("cannot divide single element") - } - arrayToIterators(arr) - } else { - // 3b) arrayD has more free elements - val (fst, snd) = arrayD.splitAt(arrayD.length - (arrayD.length - posD + 1) / 2) - arrayD = fst - val szsnd = snd.foldLeft(0)(_ + _.size) - ((new TrieIterator[A](snd), szsnd), this) - } - } - } - } - } - @SerialVersionUID(2L) private class SerializationProxy[A,B](@transient private var orig: HashSet[A]) extends Serializable { private def writeObject(out: java.io.ObjectOutputStream) { val s = orig.size diff --git a/src/library/scala/collection/immutable/TrieIteratorBase.scala b/src/library/scala/collection/immutable/TrieIteratorBase.scala new file mode 100644 index 0000000000..40e21bc735 --- /dev/null +++ b/src/library/scala/collection/immutable/TrieIteratorBase.scala @@ -0,0 +1,184 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2010, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +package scala.collection +package immutable + +import annotation.unchecked.uncheckedVariance + +object TrieIteratorBase { + final val TRIE_TYPE = 0 + final val CONTAINER_TYPE = 1 + final val COLLISION_TYPE = 2 +} +import TrieIteratorBase._ + +private[immutable] abstract class TrieIteratorBase[+T, CC >: Null <: Iterable[T]](elems: Array[CC]) extends Iterator[T] { + private[immutable] def recreateIterator(): This + + // Since we can't match on abstract types, we call determineType to + // find out what it is and let the casting gods do the remainder. + private implicit def fixCC[U <: CC](x: CC): U = x.asInstanceOf[U] + + protected var depth = 0 + protected var arrayStack = newDeepArray(6) + protected var posStack = new Array[Int](6) + protected var arrayD = elems + protected var posD = 0 + protected var subIter: Iterator[T @uncheckedVariance] = null // to traverse collision nodes + + private[immutable] type TrieType <: CC + private[immutable] type ContainerType <: CC + private[immutable] type CollisionType <: CC + + // Returns one of the constants defined in TrieIteratorBase to determine type. + private[immutable] def determineType(x: CC): Int + private[immutable] def getElem(cc: ContainerType): T + private[immutable] def getElems(t: TrieType): Array[CC] + private[immutable] def collisionToArray(c: CollisionType): Array[CC] + private[immutable] def newThisType(xs: Array[CC]): Iterator[T] + private[immutable] def newDeepArray(size: Int): Array[Array[CC]] + private[immutable] def newSingleArray(el: CC): Array[CC] + + protected type This <: TrieIteratorBase[T, CC] + private type SplitIterators = ((Iterator[T], Int), Iterator[T]) + + def dupIterator: This = { + val t = recreateIterator() + + t.depth = depth + t.arrayStack = arrayStack + t.posStack = posStack + t.arrayD = arrayD + t.posD = posD + t.subIter = subIter + + t + } + + private def iteratorWithSize(arr: Array[CC]): (Iterator[T], Int) = + (newThisType(arr), arr map (_.size) sum) + + private def arrayToIterators(arr: Array[CC]): SplitIterators = { + val (fst, snd) = arr.splitAt(arr.length / 2) + + (iteratorWithSize(snd), newThisType(fst)) + } + private def splitArray(ad: Array[CC]): SplitIterators = + if (ad.length > 1) arrayToIterators(ad) + else determineType(ad(0)) match { + case COLLISION_TYPE => arrayToIterators(collisionToArray(ad(0))) + case TRIE_TYPE => splitArray(getElems(ad(0))) + } + + def hasNext = (subIter ne null) || depth >= 0 + def next: T = { + if (subIter ne null) { + val el = subIter.next + if (!subIter.hasNext) + subIter = null + el + } else + next0(arrayD, posD) + } + + @scala.annotation.tailrec private[this] def next0(elems: Array[CC], i: Int): T = { + if (i == elems.length-1) { // reached end of level, pop stack + depth -= 1 + if (depth >= 0) { + arrayD = arrayStack(depth) + posD = posStack(depth) + arrayStack(depth) = null + } else { + arrayD = null + posD = 0 + } + } else + posD += 1 + + val m = elems(i) + determineType(m) match { + case TRIE_TYPE => + if (depth >= 0) { + arrayStack(depth) = arrayD + posStack(depth) = posD + } + depth += 1 + arrayD = getElems(m) + posD = 0 + next0(getElems(m), 0) + case CONTAINER_TYPE => + getElem(m) // push current pos onto stack and descend + case _ => + subIter = m.iterator + next + } + } + + // assumption: contains 2 or more elements + // splits this iterator into 2 iterators + // returns the 1st iterator, its number of elements, and the second iterator + def split: SplitIterators = { + // 0) simple case: no elements have been iterated - simply divide arrayD + if (arrayD != null && depth == 0 && posD == 0) + return splitArray(arrayD) + + // otherwise, some elements have been iterated over + // 1) collision case: if we have a subIter, we return subIter and elements after it + if (subIter ne null) { + val buff = subIter.toBuffer + subIter = null + ((buff.iterator, buff.length), this) + } + else { + // otherwise find the topmost array stack element + if (depth > 0) { + // 2) topmost comes before (is not) arrayD + // steal a portion of top to create a new iterator + val topmost = arrayStack(0) + if (posStack(0) == arrayStack(0).length - 1) { + // 2a) only a single entry left on top + // this means we have to modify this iterator - pop topmost + val snd = newSingleArray(arrayStack(0).last) + val szsnd = snd(0).size + // modify this - pop + depth -= 1 + 1 until arrayStack.length foreach (i => arrayStack(i - 1) = arrayStack(i)) + arrayStack(arrayStack.length - 1) = newSingleArray(null) + posStack = posStack.tail ++ Array[Int](0) + // we know that `this` is not empty, since it had something on the arrayStack and arrayStack elements are always non-empty + ((newThisType(snd), szsnd), this) + } else { + // 2b) more than a single entry left on top + val (fst, snd) = arrayStack(0).splitAt(arrayStack(0).length - (arrayStack(0).length - posStack(0) + 1) / 2) + arrayStack(0) = fst + (iteratorWithSize(snd), this) + } + } else { + // 3) no topmost element (arrayD is at the top) + // steal a portion of it and update this iterator + if (posD == arrayD.length - 1) { + // 3a) positioned at the last element of arrayD + val m = arrayD(posD) + val arr: Array[CC] = determineType(m) match { + case COLLISION_TYPE => collisionToArray(m) + case TRIE_TYPE => getElems(m) + case _ => error("cannot divide single element") + } + arrayToIterators(arr) + } + else { + // 3b) arrayD has more free elements + val (fst, snd) = arrayD.splitAt(arrayD.length - (arrayD.length - posD + 1) / 2) + arrayD = fst + (iteratorWithSize(snd), this) + } + } + } + } +}
\ No newline at end of file diff --git a/test/files/run/bug3984.scala b/test/files/run/bug3984.scala index 3e4d2edf53..0747b0ee25 100644 --- a/test/files/run/bug3984.scala +++ b/test/files/run/bug3984.scala @@ -1,4 +1,4 @@ -object Test { +object SetBug { import scala.collection.immutable.{ Set => ImmutSet } import scala.collection.mutable.{ Set => MutSet } @@ -6,16 +6,47 @@ object Test { override def hashCode: Int = h } - def main (args: Array[String]) { + def run() { var is = ImmutSet.empty[IH] var ms = MutSet.empty[IH] for (ih <- List(IH(2,0),IH(0,0),IH(4,4),IH(6,4),IH(-8,1520786080))) { is = is + ih ms = ms + ih } + assert(is == ms) val x = IH(6,4) is = is - x ms = ms - x assert(is == ms) } } + +object MapBug { + import scala.collection.immutable.{ Map => ImmutMap } + import scala.collection.mutable.{ Map => MutMap } + + case class IH (i: Int, h: Int) { + override def hashCode: Int = h + } + + def run() { + var im = ImmutMap.empty[IH,IH] + var mm = MutMap.empty[IH,IH] + for (ih <- List(IH(2,0),IH(0,0),IH(4,4),IH(6,4),IH(-8,1520786080))) { + im = im + ((ih,ih)) + mm = mm + ((ih,ih)) + } + assert(im == mm) + val x = IH(6,4) + im = im - x + mm = mm - x + assert(im == mm) + } +} + +object Test { + def main(args: Array[String]): Unit = { + SetBug.run() + MapBug.run() + } +} |