Some serious hash tries bugs fixed.

Plus one wild goose chase and test fixes.

No review.

14 files changed, 239 insertions, 57 deletions

diff --git a/src/library/scala/collection/MapLike.scala b/src/library/scala/collection/MapLike.scala
index ebf95dde81..ae1d2cc6e8 100644
--- a/src/library/scala/collection/MapLike.scala
+++ b/src/library/scala/collection/MapLike.scala
@@ -347,7 +347,8 @@ self =>
       try {
         this forall {
           case (k, v) => that.get(k.asInstanceOf[b]) match {
-            case Some(`v`) => true
+            case Some(`v`) =>
+              true
             case _ => false
           }
         }
diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala
index 684f9bced4..32542b9359 100644
--- a/src/library/scala/collection/immutable/HashMap.scala
+++ b/src/library/scala/collection/immutable/HashMap.scala
@@ -71,7 +71,7 @@ class HashMap[A, +B] extends Map[A,B] with MapLike[A, B, HashMap[A, B]] with Par
     h ^ (h >>> 10)
   }
 
-  protected def computeHash(key: A) = improve(elemHashCode(key))
+  private[collection] def computeHash(key: A) = improve(elemHashCode(key))
 
   protected type Merger[B1] = ((A, B1), (A, B1)) => (A, B1)
 
@@ -115,6 +115,10 @@ object HashMap extends ImmutableMapFactory[HashMap] {
   class HashMap1[A,+B](private[HashMap] var key: A, private[HashMap] var hash: Int, private[HashMap] var value: (B @uncheckedVariance), private[HashMap] var kv: (A,B @uncheckedVariance)) extends HashMap[A,B] {
     override def size = 1
 
+    private[collection] def getKey = key
+    private[collection] def getHash = hash
+    private[collection] def computeHashFor(k: A) = computeHash(k)
+
     override def get0(key: A, hash: Int, level: Int): Option[B] =
       if (hash == this.hash && key == this.key) Some(value) else None
 
@@ -520,11 +524,23 @@ time { mNew.iterator.foreach( p => ()) }
     // 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) {
-        val (fst, snd) = arrayD.splitAt(arrayD.length / 2)
-        val szfst = fst.foldLeft(0)(_ + _.size)
-        return ((new TrieIterator(fst), szfst), new TrieIterator(snd))
+        return splitArray(arrayD)
       }
 
       // otherwise, some elements have been iterated over
@@ -563,13 +579,11 @@ time { mNew.iterator.foreach( p => ()) }
           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[_, _] => c.asInstanceOf[HashMapCollision1[A, B]].kvs.toArray map { HashMap() + _ }
+              case c: HashMapCollision1[a, b] => collisionToArray(c).asInstanceOf[Array[HashMap[A, B]]]
               case ht: HashTrieMap[_, _] => ht.asInstanceOf[HashTrieMap[A, B]].elems
               case _ => error("cannot divide single element")
             }
-            val (fst, snd) = arr.splitAt(arr.length / 2)
-            val szsnd = snd.foldLeft(0)(_ + _.size)
-            ((new TrieIterator(snd), szsnd), new TrieIterator(fst))
+            arrayToIterators(arr)
           } else {
             // 3b) arrayD has more free elements
             val (fst, snd) = arrayD.splitAt(arrayD.length - (arrayD.length - posD + 1) / 2)
diff --git a/src/library/scala/collection/immutable/HashSet.scala b/src/library/scala/collection/immutable/HashSet.scala
index 3f04d63b40..7d27531e8d 100644
--- a/src/library/scala/collection/immutable/HashSet.scala
+++ b/src/library/scala/collection/immutable/HashSet.scala
@@ -70,7 +70,7 @@ class HashSet[A] extends Set[A]
     h ^ (h >>> 10)
   }
 
-  protected def computeHash(key: A) = improve(elemHashCode(key))
+  private[collection] def computeHash(key: A) = improve(elemHashCode(key))
 
   protected def get0(key: A, hash: Int, level: Int): Boolean = false
 
@@ -335,11 +335,23 @@ time { mNew.iterator.foreach( p => ()) }
     // 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) {
-        val (fst, snd) = arrayD.splitAt(arrayD.length / 2)
-        val szfst = fst.foldLeft(0)(_ + _.size)
-        return ((new TrieIterator(fst), szfst), new TrieIterator(snd))
+        return splitArray(arrayD)
       }
 
       // otherwise, some elements have been iterated over
@@ -378,13 +390,11 @@ time { mNew.iterator.foreach( p => ()) }
           if (posD == arrayD.length - 1) {
             // 3a) positioned at the last element of arrayD
             val arr: Array[HashSet[A]] = arrayD(posD) match {
-              case c: HashSetCollision1[_] => c.asInstanceOf[HashSetCollision1[A]].ks.toList map { HashSet() + _ } toArray
+              case c: HashSetCollision1[a] => collisionToArray(c).asInstanceOf[Array[HashSet[A]]]
               case ht: HashTrieSet[_] => ht.asInstanceOf[HashTrieSet[A]].elems
               case _ => error("cannot divide single element")
             }
-            val (fst, snd) = arr.splitAt(arr.length / 2)
-            val szsnd = snd.foldLeft(0)(_ + _.size)
-            ((new TrieIterator(snd), szsnd), new TrieIterator(fst))
+            arrayToIterators(arr)
           } else {
             // 3b) arrayD has more free elements
             val (fst, snd) = arrayD.splitAt(arrayD.length - (arrayD.length - posD + 1) / 2)
diff --git a/src/library/scala/collection/parallel/ParIterableLike.scala b/src/library/scala/collection/parallel/ParIterableLike.scala
index 3d839119b0..3a83140a53 100644
--- a/src/library/scala/collection/parallel/ParIterableLike.scala
+++ b/src/library/scala/collection/parallel/ParIterableLike.scala
@@ -983,7 +983,11 @@ self =>
   extends Transformer[(Combiner[U, This], Combiner[U, This]), Span[U, This]] {
     var result: (Combiner[U, This], Combiner[U, This]) = null
     def leaf(prev: Option[(Combiner[U, This], Combiner[U, This])]) = if (pos < pit.indexFlag) {
-      result = pit.span2combiners(pred, reuse(prev.map(_._1), cbf()), reuse(prev.map(_._2), cbf()))
+      // val lst = pit.toList
+      // val pa = mutable.ParArray(lst: _*)
+      // val str = "At leaf we will iterate: " + pa.parallelIterator.toList
+      result = pit.span2combiners(pred, cbf(), cbf()) // do NOT reuse old combiners here, lest ye be surprised
+      // println("\nAt leaf result is: " + result)
       if (result._2.size > 0) pit.setIndexFlagIfLesser(pos)
     } else {
       result = (reuse(prev.map(_._2), cbf()), pit.copy2builder[U, This, Combiner[U, This]](reuse(prev.map(_._2), cbf())))
diff --git a/src/library/scala/collection/parallel/immutable/ParHashMap.scala b/src/library/scala/collection/parallel/immutable/ParHashMap.scala
index 7cc0adbb4f..07caafb417 100644
--- a/src/library/scala/collection/parallel/immutable/ParHashMap.scala
+++ b/src/library/scala/collection/parallel/immutable/ParHashMap.scala
@@ -82,7 +82,8 @@ self =>
     }
     def next: (K, V) = {
       i += 1
-      triter.next
+      val r = triter.next
+      r
     }
     def hasNext: Boolean = {
       i < sz
@@ -90,6 +91,21 @@ self =>
     def remaining = sz - i
   }
 
+  private[parallel] def printDebugInfo {
+    println("Parallel hash trie")
+    println("Top level inner trie type: " + trie.getClass)
+    trie match {
+      case hm: HashMap.HashMap1[k, v] =>
+        println("single node type")
+        println("key stored: " + hm.getKey)
+        println("hash of key: " + hm.getHash)
+        println("computed hash of " + hm.getKey + ": " + hm.computeHashFor(hm.getKey))
+        println("trie.get(key): " + hm.get(hm.getKey))
+      case _ =>
+        println("other kind of node")
+    }
+  }
+
 }
 
 
@@ -112,10 +128,11 @@ private[immutable] abstract class HashMapCombiner[K, V]
 extends collection.parallel.BucketCombiner[(K, V), ParHashMap[K, V], (K, V), HashMapCombiner[K, V]](HashMapCombiner.rootsize) {
 self: EnvironmentPassingCombiner[(K, V), ParHashMap[K, V]] =>
   import HashMapCombiner._
+  val emptyTrie = HashMap.empty[K, V]
 
   def +=(elem: (K, V)) = {
     sz += 1
-    val hc = elem._1.##
+    val hc = emptyTrie.computeHash(elem._1)
     val pos = hc & 0x1f
     if (lasts(pos) eq null) {
       // initialize bucket
@@ -149,6 +166,10 @@ self: EnvironmentPassingCombiner[(K, V), ParHashMap[K, V]] =>
     }
   }
 
+  override def toString = {
+    "HashTrieCombiner(buckets:\n\t" + heads.filter(_ != null).mkString("\n\t") + ")\n"
+  }
+
   /* tasks */
 
   class CreateTrie(buckets: Array[Unrolled[(K, V)]], root: Array[HashMap[K, V]], offset: Int, howmany: Int) extends super.Task[Unit, CreateTrie] {
@@ -171,7 +192,7 @@ self: EnvironmentPassingCombiner[(K, V), ParHashMap[K, V]] =>
         val chunksz = unrolled.size
         while (i < chunksz) {
           val kv = chunkarr(i)
-          val hc = kv._1.##
+          val hc = trie.computeHash(kv._1)
           trie = trie.updated0(kv._1, hc, rootbits, kv._2, kv, null)
           i += 1
         }
diff --git a/src/library/scala/collection/parallel/immutable/ParHashSet.scala b/src/library/scala/collection/parallel/immutable/ParHashSet.scala
index c9554ae1eb..33e2e7102a 100644
--- a/src/library/scala/collection/parallel/immutable/ParHashSet.scala
+++ b/src/library/scala/collection/parallel/immutable/ParHashSet.scala
@@ -106,10 +106,11 @@ private[immutable] abstract class HashSetCombiner[T]
 extends collection.parallel.BucketCombiner[T, ParHashSet[T], Any, HashSetCombiner[T]](HashSetCombiner.rootsize) {
 self: EnvironmentPassingCombiner[T, ParHashSet[T]] =>
   import HashSetCombiner._
+  val emptyTrie = HashSet.empty[T]
 
   def +=(elem: T) = {
     sz += 1
-    val hc = elem.##
+    val hc = emptyTrie.computeHash(elem)
     val pos = hc & 0x1f
     if (lasts(pos) eq null) {
       // initialize bucket
@@ -166,7 +167,7 @@ self: EnvironmentPassingCombiner[T, ParHashSet[T]] =>
         val chunksz = unrolled.size
         while (i < chunksz) {
           val v = chunkarr(i).asInstanceOf[T]
-          val hc = v.##
+          val hc = trie.computeHash(v)
           trie = trie.updated0(v, hc, rootbits)
           i += 1
         }
diff --git a/src/library/scala/collection/parallel/package.scala b/src/library/scala/collection/parallel/package.scala
index bb53dcdaaa..de3a790727 100644
--- a/src/library/scala/collection/parallel/package.scala
+++ b/src/library/scala/collection/parallel/package.scala
@@ -116,7 +116,7 @@ package object parallel {
         unrolled = unrolled.next
       }
     }
-    override def toString = array.mkString("Unrolled(", ", ", ")")
+    override def toString = array.take(size).mkString("Unrolled(", ", ", ")") + (if (next ne null) next.toString else "")
   }
 
   /** A helper iterator for iterating very small array buffers.
diff --git a/test/files/scalacheck/parallel-collections/IntOperators.scala b/test/files/scalacheck/parallel-collections/IntOperators.scala
index e330bec985..bd937808db 100644
--- a/test/files/scalacheck/parallel-collections/IntOperators.scala
+++ b/test/files/scalacheck/parallel-collections/IntOperators.scala
@@ -11,7 +11,7 @@ trait IntOperators extends Operators[Int] {
   def existsPredicates = List(_ >= 0, _ < 0, _ % 2 == 0, _ == 55, _ == 505, _ == 5005)
   def findPredicates = List(_ >= 0, _ % 2 == 0, _ < 0, _ == 50, _ == 500, _ == 5000)
   def mapFunctions = List(-_)
-  def partialMapFunctions = List({case x => -x}, { case 0 => -1; case x if x > 0 => x + 1})
+  def partialMapFunctions = List({case x => -x}, { case 0 => -1; case x if x > 0 => x + 1}, {case x if x % 3 == 0 => x / 3})
   def flatMapFunctions = List(
       (n: Int) => if (n < 0) List() else if (n % 2 == 0) List(1, 2, 3) else List(4, 5, 6),
       (n: Int) => List[Int](),
diff --git a/test/files/scalacheck/parallel-collections/ParallelArrayCheck.scala b/test/files/scalacheck/parallel-collections/ParallelArrayCheck.scala
index 394dc6b370..01e40ed62b 100644
--- a/test/files/scalacheck/parallel-collections/ParallelArrayCheck.scala
+++ b/test/files/scalacheck/parallel-collections/ParallelArrayCheck.scala
@@ -22,6 +22,8 @@ abstract class ParallelArrayCheck[T](tp: String) extends ParallelSeqCheck[T]("Pa
 
   def isCheckingViews = false
 
+  def hasStrictOrder = true
+
   def instances(vals: Seq[Gen[T]]): Gen[Seq[T]] = sized { sz =>
     val a = new mutable.ArrayBuffer[T](sz)
     val gen = vals(rnd.nextInt(vals.size))
diff --git a/test/files/scalacheck/parallel-collections/ParallelHashMapCheck.scala b/test/files/scalacheck/parallel-collections/ParallelHashMapCheck.scala
index 1224ec8d4d..51c35140dd 100644
--- a/test/files/scalacheck/parallel-collections/ParallelHashMapCheck.scala
+++ b/test/files/scalacheck/parallel-collections/ParallelHashMapCheck.scala
@@ -14,7 +14,7 @@ import scala.collection._
 import scala.collection.parallel.ops._
 
 
-abstract class ParallelHashMapCheck[K, V](tp: String) extends ParallelIterableCheck[(K, V)]("immutable.ParHashMap[" + tp + "]") {
+abstract class ParallelHashMapCheck[K, V](tp: String) extends ParallelMapCheck[K, V]("immutable.ParHashMap[" + tp + "]") {
   ForkJoinTasks.defaultForkJoinPool.setMaximumPoolSize(Runtime.getRuntime.availableProcessors * 2)
   ForkJoinTasks.defaultForkJoinPool.setParallelism(Runtime.getRuntime.availableProcessors * 2)
 
@@ -22,6 +22,8 @@ abstract class ParallelHashMapCheck[K, V](tp: String) extends ParallelIterableCh
 
   def isCheckingViews = false
 
+  def hasStrictOrder = false
+
   def instances(vals: Seq[Gen[(K, V)]]): Gen[Iterable[(K, V)]] = sized { sz =>
     var hm = new immutable.HashMap[K, V]
     val gen = vals(rnd.nextInt(vals.size))
@@ -53,6 +55,13 @@ with PairValues[Int, Int]
   val intoperators = new IntOperators {}
   def voperators = intoperators
   def koperators = intoperators
+
+  override def printDataStructureDebugInfo(ds: AnyRef) = ds match {
+    case pm: ParHashMap[k, v] =>
+      pm.printDebugInfo
+    case _ =>
+      println("could not match data structure type: " + ds.getClass)
+  }
 }
 
 
diff --git a/test/files/scalacheck/parallel-collections/ParallelIterableCheck.scala b/test/files/scalacheck/parallel-collections/ParallelIterableCheck.scala
index bc08947af4..ea42e5efa3 100644
--- a/test/files/scalacheck/parallel-collections/ParallelIterableCheck.scala
+++ b/test/files/scalacheck/parallel-collections/ParallelIterableCheck.scala
@@ -21,6 +21,11 @@ abstract class ParallelIterableCheck[T](collName: String) extends Properties(col
   def instances(valgens: Seq[Gen[T]]): Gen[Traversable[T]]
   def fromTraversable(t: Traversable[T]): CollType
   def isCheckingViews: Boolean
+  def hasStrictOrder: Boolean
+
+  def printDataStructureDebugInfo(cf: AnyRef) {
+    // can be overridden in subclasses
+  }
 
   val rnd = new scala.util.Random
 
@@ -94,18 +99,26 @@ abstract class ParallelIterableCheck[T](collName: String) extends Properties(col
     results.reduceLeft(_ && _)
   }
 
+  def areEqual(t1: Traversable[T], t2: Traversable[T]) = if (hasStrictOrder) {
+    t1 == t2
+  } else (t1, t2) match { // it is slightly delicate what `equal` means if the order is not strict
+    case (m1: Map[_, _], m2: Map[_, _]) => m1 == m2
+    case (i1: Iterable[_], i2: Iterable[_]) => i1.toSet == i2.toSet
+    case _ => t1 == t2
+  }
+
   property("mappings must be equal") = forAll(collectionPairs) { case (t, coll) =>
     val results = for ((f, ind) <- mapFunctions.zipWithIndex) yield {
       val ms = t.map(f)
       val mp = coll.map(f)
-      if (ms != mp) {
+      if (!areEqual(ms, mp)) {
         println(t)
         println(coll)
         println("mapped to: ")
         println(ms)
         println(mp)
       }
-      ("op index: " + ind) |: ms == mp
+      ("op index: " + ind) |: areEqual(ms, mp)
     }
     results.reduceLeft(_ && _)
   }
@@ -114,26 +127,39 @@ abstract class ParallelIterableCheck[T](collName: String) extends Properties(col
     val results = for ((f, ind) <- partialMapFunctions.zipWithIndex) yield {
       val ps = t.collect(f)
       val pp = coll.collect(f)
-      if (ps != pp) {
+      if (!areEqual(ps, pp)) {
         println(t)
         println(coll)
         println("collected to: ")
         println(ps)
         println(pp)
       }
-      ("op index: " + ind) |: ps == pp
+      ("op index: " + ind) |: areEqual(ps, pp)
     }
     results.reduceLeft(_ && _)
   }
 
   property("flatMaps must be equal") = forAll(collectionPairs) { case (t, coll) =>
     (for ((f, ind) <- flatMapFunctions.zipWithIndex)
-      yield ("op index: " + ind) |: t.flatMap(f) == coll.flatMap(f)).reduceLeft(_ && _)
+      yield ("op index: " + ind) |: areEqual(t.flatMap(f), coll.flatMap(f))).reduceLeft(_ && _)
   }
 
   property("filters must be equal") = forAll(collectionPairs) { case (t, coll) =>
-    (for ((p, ind) <- filterPredicates.zipWithIndex)
-      yield ("op index: " + ind) |: t.filter(p) == coll.filter(p)).reduceLeft(_ && _)
+    (for ((p, ind) <- filterPredicates.zipWithIndex) yield {
+      val tf = t.filter(p)
+      val cf = coll.filter(p)
+      if (tf != cf || cf != tf) {
+        println(t)
+        println(coll)
+        println("filtered to:")
+        println(cf)
+        println(tf)
+        println("tf == cf - " + (tf == cf))
+        println("cf == tf - " + (cf == tf))
+        printDataStructureDebugInfo(cf)
+      }
+      ("op index: " + ind) |: tf == cf && cf == tf
+    }).reduceLeft(_ && _)
   }
 
   property("filterNots must be equal") = forAll(collectionPairs) { case (t, coll) =>
@@ -155,15 +181,15 @@ abstract class ParallelIterableCheck[T](collName: String) extends Properties(col
     }).reduceLeft(_ && _)
   }
 
-  property("takes must be equal") = forAll(collectionPairsWithLengths) { case (t, coll, n) =>
+  if (hasStrictOrder) property("takes must be equal") = forAll(collectionPairsWithLengths) { case (t, coll, n) =>
     ("take " + n + " elements") |: t.take(n) == coll.take(n)
   }
 
-  property("drops must be equal") = forAll(collectionPairsWithLengths) { case (t, coll, n) =>
+  if (hasStrictOrder) property("drops must be equal") = forAll(collectionPairsWithLengths) { case (t, coll, n) =>
     ("drop " + n + " elements") |: t.drop(n) == coll.drop(n)
   }
 
-  property("slices must be equal") = forAll(collectionPairsWith2Indices)
+  if (hasStrictOrder) property("slices must be equal") = forAll(collectionPairsWith2Indices)
   { case (t, coll, fr, slicelength) =>
     val from = if (fr < 0) 0 else fr
     val until = if (from + slicelength > t.size) t.size else from + slicelength
@@ -187,7 +213,7 @@ abstract class ParallelIterableCheck[T](collName: String) extends Properties(col
     ("slice from " + from + " until " + until) |: tsl == collsl
   }
 
-  property("splits must be equal") = forAll(collectionPairsWithLengths) { case (t, coll, n) =>
+  if (hasStrictOrder) property("splits must be equal") = forAll(collectionPairsWithLengths) { case (t, coll, n) =>
     val tspl = t.splitAt(n)
     val cspl = coll.splitAt(n)
     if (tspl != cspl) {
@@ -200,64 +226,88 @@ abstract class ParallelIterableCheck[T](collName: String) extends Properties(col
     ("splitAt " + n) |: tspl == cspl
   }
 
-  property("takeWhiles must be equal") = forAll(collectionPairs) { case (t, coll) =>
-    (for ((pred, ind) <- takeWhilePredicates.zipWithIndex)
-      yield ("operator " + ind) |: t.takeWhile(pred) == coll.takeWhile(pred)).reduceLeft(_ && _)
+  if (hasStrictOrder) property("takeWhiles must be equal") = forAll(collectionPairs) { case (t, coll) =>
+    (for ((pred, ind) <- takeWhilePredicates.zipWithIndex) yield {
+      val tt = t.takeWhile(pred)
+      val ct = coll.takeWhile(pred)
+      if (tt != ct) {
+        println("from: " + t)
+        println("and: " + coll)
+        println("taking while...")
+        println(tt)
+        println(ct)
+      }
+      ("operator " + ind) |: tt == ct
+    }).reduceLeft(_ && _)
   }
 
-  property("spans must be equal") = forAll(collectionPairs) { case (t, coll) =>
+  if (hasStrictOrder) property("spans must be equal") = forAll(collectionPairs) { case (t, coll) =>
     (for ((pred, ind) <- spanPredicates.zipWithIndex) yield {
       val tsp = t.span(pred)
       val csp = coll.span(pred)
       if (tsp != csp) {
         println("from: " + t)
         println("and: " + coll)
+        println("span with predicate " + ind)
         println(tsp)
         println(csp)
+        println("---------------------------------")
+        println(coll.span(pred))
+        println("---------------------------------")
       }
       ("operator " + ind) |: tsp == csp
     }).reduceLeft(_ && _)
   }
 
-  property("dropWhiles must be equal") = forAll(collectionPairs) { case (t, coll) =>
+  if (hasStrictOrder) property("dropWhiles must be equal") = forAll(collectionPairs) { case (t, coll) =>
     (for ((pred, ind) <- dropWhilePredicates.zipWithIndex) yield {
       ("operator " + ind) |: t.dropWhile(pred) == coll.dropWhile(pred)
     }).reduceLeft(_ && _)
   }
 
   property("folds must be equal for assoc. operators") = forAll(collectionPairs) { case (t, coll) =>
-    (for (((first, op), ind) <- foldArguments.zipWithIndex)
-      yield ("operator " + ind) |: t.foldLeft(first)(op) == coll.fold(first)(op)).reduceLeft(_ && _)
+    (for (((first, op), ind) <- foldArguments.zipWithIndex) yield {
+      val tres = t.foldLeft(first)(op)
+      val cres = coll.fold(first)(op)
+      if (cres != tres) {
+        println("from: " + t)
+        println("and: " + coll)
+        println("folds are: ")
+        println(tres)
+        println(cres)
+      }
+      ("operator " + ind) |: tres == cres
+    }).reduceLeft(_ && _)
   }
 
   property("++s must be equal") = forAll(collectionTriplets) { case (t, coll, colltoadd) =>
     val toadd = colltoadd
-    val tr = t ++ toadd
-    val cr = coll ++ fromTraversable(toadd).iterator
-    if (!tr.toList.iterator.sameElements(cr.iterator)) {
+    val tr = t ++ toadd.iterator
+    val cr = coll ++ toadd.iterator
+    if (areEqual(tr, cr)) {
       println("from: " + t)
       println("and: " + coll.iterator.toList)
       println("adding: " + toadd)
       println(tr.toList)
       println(cr.iterator.toList)
     }
-    ("adding " |: tr == cr) &&
+    ("adding " |: areEqual(tr, cr)) &&
     (for ((trav, ind) <- (addAllTraversables).zipWithIndex) yield {
       val tadded = t ++ trav
-      val cadded = coll ++ fromTraversable(trav.toList)
-      if (tadded != cadded) {
+      val cadded = coll ++ collection.parallel.mutable.ParArray(trav.toSeq: _*)
+      if (!areEqual(tadded, cadded)) {
         println("----------------------")
         println("from: " + t)
-        println("and: " + coll.iterator.toList)
+        println("and: " + coll)
         println("adding: " + trav)
-        println(tadded.toList)
-        println(cadded.iterator.toList)
+        println(tadded)
+        println(cadded)
       }
-      ("traversable " + ind) |: (tadded) == (cadded)
+      ("traversable " + ind) |: areEqual(tadded, cadded)
     }).reduceLeft(_ && _)
   }
 
-  property("copies to array must be equal") = forAll(collectionPairs) { case (t, coll) =>
+  if (hasStrictOrder) property("copies to array must be equal") = forAll(collectionPairs) { case (t, coll) =>
     val tarr = newArray(t.size)
     val collarr = newArray(coll.size)
     t.copyToArray(tarr, 0, t.size)
diff --git a/test/files/scalacheck/parallel-collections/ParallelMapCheck1.scala b/test/files/scalacheck/parallel-collections/ParallelMapCheck1.scala
new file mode 100644
index 0000000000..6b30f61b57
--- /dev/null
+++ b/test/files/scalacheck/parallel-collections/ParallelMapCheck1.scala
@@ -0,0 +1,67 @@
+package scala.collection.parallel
+
+
+
+import org.scalacheck._
+import org.scalacheck.Gen
+import org.scalacheck.Gen._
+import org.scalacheck.Prop._
+import org.scalacheck.Properties
+
+import scala.collection._
+import scala.collection.parallel._
+
+
+
+
+abstract class ParallelMapCheck[K, V](collname: String) extends ParallelIterableCheck[(K, V)](collname) {
+  type CollType <: ParMap[K, V] with Sequentializable[(K, V), Map[K, V]]
+
+  property("gets iterated keys") = forAll(collectionPairs) {
+    case (t, coll) =>
+    val containsT = for ((k, v) <- t) yield (coll.get(k) == Some(v))
+    val containsSelf = for ((k, v) <- coll) yield (coll.get(k) == Some(v))
+    ("Par contains elements of seq map" |: containsT.forall(_ == true)) &&
+    ("Par contains elements of itself" |: containsSelf.forall(_ == true))
+  }
+
+}
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
diff --git a/test/files/scalacheck/parallel-collections/ParallelRangeCheck.scala b/test/files/scalacheck/parallel-collections/ParallelRangeCheck.scala
index 91296a2030..d2a05a66c9 100644
--- a/test/files/scalacheck/parallel-collections/ParallelRangeCheck.scala
+++ b/test/files/scalacheck/parallel-collections/ParallelRangeCheck.scala
@@ -23,6 +23,8 @@ object ParallelRangeCheck extends ParallelSeqCheck[Int]("ParallelRange[Int]") wi
 
   type CollType = collection.parallel.ParSeq[Int]
 
+  def hasStrictOrder = true
+
   def isCheckingViews = false
 
   def instances(vals: Seq[Gen[Int]]): Gen[Seq[Int]] = sized { start =>
diff --git a/test/files/scalacheck/parallel-collections/pc.scala b/test/files/scalacheck/parallel-collections/pc.scala
index 04b7168286..cb57a6e205 100644
--- a/test/files/scalacheck/parallel-collections/pc.scala
+++ b/test/files/scalacheck/parallel-collections/pc.scala
@@ -17,7 +17,7 @@ class ParCollProperties extends Properties("Parallel collections") {
   //include(immutable.ParallelRangeCheck)
 
   // parallel immutable hash maps (tries)
-  include(immutable.IntIntParallelHashMapCheck)
+  //include(immutable.IntIntParallelHashMapCheck)
 
   // parallel immutable hash sets (tries)
 
@@ -40,7 +40,8 @@ object Test {
     org.scalacheck.Test.checkProperties(
       org.scalacheck.Test.Params(
         rng = new java.util.Random(5134L),
-        testCallback = new ConsoleReporter(0)
+        testCallback = new ConsoleReporter(0),
+        workers = 1
       ),
       pc
     )