Having been tortured by remorse ever since tiar...

Having been tortured by remorse ever since tiark told me that r23934 had
made the hashmap slower, I crushed my previous efforts under the heel of
my boot, threw all the types out the window, poured acid on them, and
turned all the dials to the far other extreme. Pity the man who will
sell his soul for a few CPU cycles. (I am that man.) Review by rompf.

6 files changed, 251 insertions, 282 deletions

diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala
index e253cd6a05..bf65966e80 100644
--- a/src/library/scala/collection/immutable/HashMap.scala
+++ b/src/library/scala/collection/immutable/HashMap.scala
@@ -180,7 +180,9 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
     }
   }
 
-  private[collection] class HashMapCollision1[A,+B](private[HashMap] var hash: Int, var kvs: ListMap[A,B @uV]) 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 @uV] {
+
     override def size = kvs.size
 
     override def get0(key: A, hash: Int, level: Int): Option[B] =
@@ -222,8 +224,12 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
     }
   }
 
-  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] {
+  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 @uV] {
+
 /*
     def this (level: Int, m1: HashMap1[A,B], m2: HashMap1[A,B]) = {
       this(((m1.hash >>> level) & 0x1f) | ((m2.hash >>> level) & 0x1f), {
@@ -308,7 +314,9 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
       }
     }
 
-    override def iterator: Iterator[(A, B)] = new CovariantTrieIterator[A, B](elems)
+    override def iterator: Iterator[(A, B)] = new TrieIterator[(A, B)](elems.asInstanceOf[Array[Iterable[(A, B)]]]) {
+      final override def getElem(cc: AnyRef): (A, B) = cc.asInstanceOf[HashMap1[A, B]].ensurePair
+    }
 
 /*
 
@@ -452,35 +460,6 @@ time { mNew.iterator.foreach( p => ()) }
     }
   }
 
-  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
-  }
-
-  class TrieIterator[A, B](elems: Array[HashMap[A, B]]) extends TrieIteratorBase[(A, B), HashMap[A, B]](elems) {
-    import TrieIteratorBase._
-
-    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]
-
-    private[immutable] def determineType(x: HashMap[A, B]) = x match {
-      case _: HashMap1[_, _]          => CONTAINER_TYPE
-      case _: HashTrieMap[_, _]       => TRIE_TYPE
-      case _: HashMapCollision1[_, _] => COLLISION_TYPE
-    }
-
-    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
     var xs = Set[K]()
     for (elem <- x) xs += elem._1
diff --git a/src/library/scala/collection/immutable/HashSet.scala b/src/library/scala/collection/immutable/HashSet.scala
index 951f6d235e..c4b0c65d99 100644
--- a/src/library/scala/collection/immutable/HashSet.scala
+++ b/src/library/scala/collection/immutable/HashSet.scala
@@ -11,6 +11,7 @@
 package scala.collection
 package immutable
 
+import annotation.unchecked.{ uncheckedVariance => uV }
 import generic._
 import collection.parallel.immutable.ParHashSet
 
@@ -95,34 +96,11 @@ class HashSet[A] extends Set[A]
  */
 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]]
 
-  private object EmptyHashSet extends HashSet[Any] {
-  }
+  private object EmptyHashSet extends HashSet[Any] { }
 
   // TODO: add HashSet2, HashSet3, ...
 
@@ -152,7 +130,9 @@ object HashSet extends ImmutableSetFactory[HashSet] {
     override def foreach[U](f: A => U): Unit = f(key)
   }
 
-  private[immutable] 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 =
@@ -197,9 +177,8 @@ object HashSet extends ImmutableSetFactory[HashSet] {
 
   }
 
-
-  class HashTrieSet[A](private var bitmap: Int, private[HashSet] var elems: Array[HashSet[A]],
-      private var size0: Int) extends HashSet[A] {
+  class HashTrieSet[A](private var bitmap: Int, private[collection] var elems: Array[HashSet[A]], private var size0: Int)
+        extends HashSet[A] {
 
     override def size = size0
 
@@ -268,8 +247,9 @@ object HashSet extends ImmutableSetFactory[HashSet] {
       }
     }
 
-    override def iterator = new TrieIterator[A](elems)
-
+    override def iterator = new TrieIterator[A](elems.asInstanceOf[Array[Iterable[A]]]) {
+      final override def getElem(cc: AnyRef): A = cc.asInstanceOf[HashSet1[A]].key
+    }
 /*
 
 def time(block: =>Unit) = { val t0 = System.nanoTime; block; println("elapsed: " + (System.nanoTime - t0)/1000000.0) }
diff --git a/src/library/scala/collection/immutable/TrieIterator.scala b/src/library/scala/collection/immutable/TrieIterator.scala
new file mode 100644
index 0000000000..088b280b8a
--- /dev/null
+++ b/src/library/scala/collection/immutable/TrieIterator.scala
@@ -0,0 +1,219 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2011, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+package scala.collection
+package immutable
+
+import HashMap.{ HashTrieMap, HashMapCollision1, HashMap1 }
+import HashSet.{ HashTrieSet, HashSetCollision1, HashSet1 }
+import annotation.unchecked.{ uncheckedVariance => uV }
+import scala.annotation.tailrec
+
+/** Abandons any pretense of type safety for speed.  You can't say I
+ *  didn't try: see r23934.
+ */
+private[collection] abstract class TrieIterator[+T](elems: Array[Iterable[T]]) extends Iterator[T] {
+  outer =>
+
+  private[immutable] def getElem(x: AnyRef): T
+
+  def initDepth                                     = 0
+  def initArrayStack: Array[Array[Iterable[T @uV]]] = new Array[Array[Iterable[T]]](6)
+  def initPosStack                                  = new Array[Int](6)
+  def initArrayD: Array[Iterable[T @uV]]            = elems
+  def initPosD                                      = 0
+  def initSubIter: Iterator[T]                      = null // to traverse collision nodes
+
+  private[this] var depth                                     = initDepth
+  private[this] var arrayStack: Array[Array[Iterable[T @uV]]] = initArrayStack
+  private[this] var posStack                                  = initPosStack
+  private[this] var arrayD: Array[Iterable[T @uV]]            = initArrayD
+  private[this] var posD                                      = initPosD
+  private[this] var subIter                                   = initSubIter
+
+  private[this] def getElems(x: Iterable[T]): Array[Iterable[T]] = (x match {
+    case x: HashTrieMap[a, b] => x.elems
+    case x: HashTrieSet[T]    => x.elems
+  }).asInstanceOf[Array[Iterable[T]]]
+
+  private[this] def collisionToArray(x: Iterable[T]): Array[Iterable[T]] = (x match {
+    case x: HashMapCollision1[_, _] => x.kvs.map(x => HashMap(x)).toArray
+    case x: HashSetCollision1[_]    => x.ks.map(x => HashSet(x)).toArray
+  }).asInstanceOf[Array[Iterable[T]]]
+
+  private type SplitIterators = ((Iterator[T], Int), Iterator[T])
+
+  private def isTrie(x: AnyRef) = x match {
+    case _: HashTrieMap[_,_] | _: HashTrieSet[_] => true
+    case _                                       => false
+  }
+  private def isContainer(x: AnyRef) = x match {
+    case _: HashMap1[_, _] | _: HashSet1[_] => true
+    case _                                  => false
+  }
+
+  final class DupIterator(xs: Array[Iterable[T]]) extends {
+    override val initDepth                                     = outer.depth
+    override val initArrayStack: Array[Array[Iterable[T @uV]]] = outer.arrayStack
+    override val initPosStack                                  = outer.posStack
+    override val initArrayD: Array[Iterable[T @uV]]            = outer.arrayD
+    override val initPosD                                      = outer.posD
+    override val initSubIter                                   = outer.subIter
+  } with TrieIterator[T](xs) {
+    final override def getElem(x: AnyRef): T = outer.getElem(x)
+  }
+
+  def dupIterator: TrieIterator[T] = new DupIterator(elems)
+
+  private[this] def newIterator(xs: Array[Iterable[T]]) = new TrieIterator(xs) {
+    final override def getElem(x: AnyRef): T = outer.getElem(x)
+  }
+
+  private[this] def iteratorWithSize(arr: Array[Iterable[T]]): (Iterator[T], Int) =
+    (newIterator(arr), arr map (_.size) sum)
+
+  private[this] def arrayToIterators(arr: Array[Iterable[T]]): SplitIterators = {
+    val (fst, snd) = arr.splitAt(arr.length / 2)
+
+    (iteratorWithSize(snd), newIterator(fst))
+  }
+  private[this] def splitArray(ad: Array[Iterable[T]]): SplitIterators =
+    if (ad.length > 1) arrayToIterators(ad)
+    else ad(0) match {
+      case _: HashMapCollision1[_, _] | _: HashSetCollision1[_] =>
+        arrayToIterators(collisionToArray(ad(0)))
+      case _ =>
+        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)
+  }
+
+  @tailrec private[this] def next0(elems: Array[Iterable[T]], 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)
+
+    // Note: this block is over twice as fast written this way as it is
+    // as a pattern match.  Haven't started looking into why that is, but
+    // it's pretty sad the pattern matcher is that much slower.
+    if (isContainer(m))
+      getElem(m) // push current pos onto stack and descend
+    else if (isTrie(m)) {
+      if (depth >= 0) {
+        arrayStack(depth) = arrayD
+        posStack(depth) = posD
+      }
+      depth += 1
+      arrayD = getElems(m)
+      posD = 0
+      next0(getElems(m), 0)
+    }
+    else {
+      subIter = m.iterator
+      next
+    }
+    // The much slower version:
+    //
+    // m match {
+    //   case _: HashMap1[_, _] | _: HashSet1[_] =>
+    //     getElem(m) // push current pos onto stack and descend
+    //   case _: HashTrieMap[_,_] | _: HashTrieSet[_] =>
+    //     if (depth >= 0) {
+    //       arrayStack(depth) = arrayD
+    //       posStack(depth) = posD
+    //     }
+    //     depth += 1
+    //     arrayD = getElems(m)
+    //     posD = 0
+    //     next0(getElems(m), 0)
+    //   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 = Array[Iterable[T]](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) = Array[Iterable[T]](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
+          ((newIterator(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)
+          arrayToIterators(
+            if (isTrie(m)) getElems(m)
+            else collisionToArray(m)
+          )
+        }
+        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/src/library/scala/collection/immutable/TrieIteratorBase.scala b/src/library/scala/collection/immutable/TrieIteratorBase.scala
deleted file mode 100644
index 02126b456f..0000000000
--- a/src/library/scala/collection/immutable/TrieIteratorBase.scala
+++ /dev/null
@@ -1,184 +0,0 @@
-/*                     __                                               *\
-**     ________ ___   / /  ___     Scala API                            **
-**    / __/ __// _ | / /  / _ |    (c) 2003-2011, 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 _              => sys.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/src/library/scala/collection/parallel/immutable/ParHashMap.scala b/src/library/scala/collection/parallel/immutable/ParHashMap.scala
index c6006b54f6..b9b7cbd69d 100644
--- a/src/library/scala/collection/parallel/immutable/ParHashMap.scala
+++ b/src/library/scala/collection/parallel/immutable/ParHashMap.scala
@@ -6,15 +6,8 @@
 **                          |/                                          **
 \*                                                                      */
 
-
 package scala.collection.parallel.immutable
 
-
-
-
-
-
-
 import scala.collection.parallel.ParMapLike
 import scala.collection.parallel.Combiner
 import scala.collection.parallel.IterableSplitter
@@ -24,13 +17,9 @@ import scala.collection.generic.ParMapFactory
 import scala.collection.generic.CanCombineFrom
 import scala.collection.generic.GenericParMapTemplate
 import scala.collection.generic.GenericParMapCompanion
-import scala.collection.immutable.HashMap
-
-
+import scala.collection.immutable.{ HashMap, TrieIterator }
 import annotation.unchecked.uncheckedVariance
 
-
-
 /** Immutable parallel hash map, based on hash tries.
  *
  *  $paralleliterableinfo
@@ -87,9 +76,8 @@ self =>
   self: SignalContextPassingIterator[ParHashMapIterator] =>
     var i = 0
     def dup = triter match {
-      case t: HashMap.TrieIterator[_, _] =>
-        val dupt = t.dupIterator.asInstanceOf[Iterator[(K, V)]]
-        dupFromIterator(dupt)
+      case t: TrieIterator[_] =>
+        dupFromIterator(t.dupIterator)
       case _ =>
         val buff = triter.toBuffer
         triter = buff.iterator
@@ -101,9 +89,9 @@ self =>
       phit
     }
     def split: Seq[ParIterator] = if (remaining < 2) Seq(this) else triter match {
-      case t: HashMap.TrieIterator[_, _] =>
+      case t: TrieIterator[_] =>
         val previousRemaining = remaining
-        val ((fst, fstlength), snd) = t.asInstanceOf[HashMap.TrieIterator[K, V]].split
+        val ((fst, fstlength), snd) = t.split
         val sndlength = previousRemaining - fstlength
         Seq(
           new ParHashMapIterator(fst, fstlength) with SCPI,
diff --git a/src/library/scala/collection/parallel/immutable/ParHashSet.scala b/src/library/scala/collection/parallel/immutable/ParHashSet.scala
index c67fad867d..e3c408e4db 100644
--- a/src/library/scala/collection/parallel/immutable/ParHashSet.scala
+++ b/src/library/scala/collection/parallel/immutable/ParHashSet.scala
@@ -6,15 +6,8 @@
 **                          |/                                          **
 \*                                                                      */
 
-
 package scala.collection.parallel.immutable
 
-
-
-
-
-
-
 import scala.collection.parallel.ParSetLike
 import scala.collection.parallel.Combiner
 import scala.collection.parallel.IterableSplitter
@@ -25,12 +18,7 @@ import scala.collection.generic.CanCombineFrom
 import scala.collection.generic.GenericParTemplate
 import scala.collection.generic.GenericParCompanion
 import scala.collection.generic.GenericCompanion
-import scala.collection.immutable.HashSet
-
-
-
-
-
+import scala.collection.immutable.{ HashSet, TrieIterator }
 
 /** Immutable parallel hash set, based on hash tries.
  *
@@ -85,9 +73,8 @@ self =>
   self: SignalContextPassingIterator[ParHashSetIterator] =>
     var i = 0
     def dup = triter match {
-      case t: HashSet.TrieIterator[_] =>
-        val dupt = t.dupIterator.asInstanceOf[Iterator[T]]
-        dupFromIterator(dupt)
+      case t: TrieIterator[_] =>
+        dupFromIterator(t.dupIterator)
       case _ =>
         val buff = triter.toBuffer
         triter = buff.iterator
@@ -99,9 +86,9 @@ self =>
       phit
     }
     def split: Seq[ParIterator] = if (remaining < 2) Seq(this) else triter match {
-      case t: HashSet.TrieIterator[_] =>
+      case t: TrieIterator[_] =>
         val previousRemaining = remaining
-        val ((fst, fstlength), snd) = t.asInstanceOf[HashSet.TrieIterator[T]].split
+        val ((fst, fstlength), snd) = t.split
         val sndlength = previousRemaining - fstlength
         Seq(
           new ParHashSetIterator(fst, fstlength) with SCPI,