Pulled some bit level operations into their own...

Pulled some bit level operations into their own file. It's pretty much
impossible to abstract across Int and Long with no penalty, but we
can at least have duplicated code in the same place to minimize the
challenge. No review.

5 files changed, 80 insertions, 88 deletions

diff --git a/src/library/scala/collection/generic/BitOperations.scala b/src/library/scala/collection/generic/BitOperations.scala
new file mode 100644
index 0000000000..aa3ccebfda
--- /dev/null
+++ b/src/library/scala/collection/generic/BitOperations.scala
@@ -0,0 +1,64 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2010, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+package scala.collection
+package generic
+
+/** Some bit operations.
+ *
+ *  See http://www.drmaciver.com/2008/08/unsigned-comparison-in-javascala/ for
+ *  an explanation of unsignedCompare.
+ */
+private[collection] object BitOperations {
+  trait Int {
+    type Int = scala.Int
+    def zero(i: Int, mask: Int)                 = (i & mask) == 0
+    def mask(i: Int, mask: Int)                 = i & (complement(mask - 1) ^ mask)
+    def hasMatch(key: Int, prefix: Int, m: Int) = mask(key, m) == prefix
+    def unsignedCompare(i: Int, j: Int)         = (i < j) ^ (i < 0) ^ (j < 0)
+    def shorter(m1: Int, m2: Int)               = unsignedCompare(m2, m1)
+    def complement(i: Int)                      = (-1) ^ i
+    def bits(num: Int)                          = 31 to 0 by -1 map (i => (num >>> i & 1) != 0)
+    def bitString(num: Int, sep: String = "")   = bits(num) map (b => if (b) "1" else "0") mkString sep
+
+    def highestOneBit(j: Int) = {
+      var i = j
+      i |= (i >>  1)
+      i |= (i >>  2)
+      i |= (i >>  4)
+      i |= (i >>  8)
+      i |= (i >> 16)
+      i - (i >>> 1)
+    }
+  }
+  object Int extends Int
+
+  trait Long {
+    type Long = scala.Long
+    def zero(i: Long, mask: Long)                  = (i & mask) == 0L
+    def mask(i: Long, mask: Long)                  = i & (complement(mask - 1) ^ mask)
+    def hasMatch(key: Long, prefix: Long, m: Long) = mask(key, m) == prefix
+    def unsignedCompare(i: Long, j: Long)          = (i < j) ^ (i < 0L) ^ (j < 0L)
+    def shorter(m1: Long, m2: Long)                = unsignedCompare(m2, m1)
+    def complement(i: Long)                        = (-1L) ^ i
+    def bits(num: Long)                            = 63L to 0L by -1L map (i => (num >>> i & 1L) != 0L)
+    def bitString(num: Long, sep: String = "")     = bits(num) map (b => if (b) "1" else "0") mkString sep
+
+    def highestOneBit(j: Long) = {
+      var i = j
+      i |= (i >>  1)
+      i |= (i >>  2)
+      i |= (i >>  4)
+      i |= (i >>  8)
+      i |= (i >> 16)
+      i |= (i >> 32)
+      i - (i >>> 1)
+    }
+  }
+  object Long extends Long
+}
diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala
index 93023a3097..26d7ff2eed 100644
--- a/src/library/scala/collection/immutable/HashMap.scala
+++ b/src/library/scala/collection/immutable/HashMap.scala
@@ -102,7 +102,7 @@ class HashMap[A, +B] extends Map[A,B] with MapLike[A, B, HashMap[A, B]] with Par
  *  @author  Tiark Rompf
  *  @since   2.3
  */
-object HashMap extends ImmutableMapFactory[HashMap] {
+object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int {
   /** $mapCanBuildFromInfo */
   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]]
@@ -344,14 +344,7 @@ time { mNew.iterator.foreach( p => ()) }
     }
 
     private def printBitmap(bm: Int) {
-      var i = 32
-      var b = bm
-      while (i != 0) {
-	print((b & 1) + " ")
-	b = b >>> 1
-	i -= 1
-      }
-      println
+      println(bitString(bm, " "))
     }
 
     private def posOf(n: Int, bm: Int) = {
@@ -434,13 +427,10 @@ time { mNew.iterator.foreach( p => ()) }
             // condition below is due to 2 things:
             // 1) no unsigned int compare on JVM
             // 2) 0 (no lsb) should always be greater in comparison
-            // also, search for unsigned compare Scala to find Dave's solution
-            // and compare a and b defined as below:
             val a = thislsb - 1
             val b = thatlsb - 1
-            // ! our case indeed is more specific, but this didn't help:
-            // if ((thislsb > 0 && thislsb < thatlsb) || thatlsb == 0 || (thatlsb < 0 && thislsb != 0)) {
-            if ((a < b) ^ (a < 0) ^ (b < 0)) {
+
+            if (unsignedCompare(thislsb - 1, thatlsb - 1)) {
               // println("an element from this trie")
               val m = thiselems(thisi)
               totalelems += m.size
diff --git a/src/library/scala/collection/immutable/IntMap.scala b/src/library/scala/collection/immutable/IntMap.scala
index e16c287345..6baa05c21a 100644
--- a/src/library/scala/collection/immutable/IntMap.scala
+++ b/src/library/scala/collection/immutable/IntMap.scala
@@ -6,40 +6,17 @@
 **                          |/                                          **
 \*                                                                      */
 
-
-
 package scala.collection
-package immutable;
-
-
-
-import scala.collection.generic.CanBuildFrom
-import scala.collection.mutable.Builder
-import scala.collection.mutable.MapBuilder
-
+package immutable
 
+import scala.collection.generic.{ CanBuildFrom, BitOperations }
+import scala.collection.mutable.{ Builder, MapBuilder }
 
 /** Utility class for integer maps.
  *  @author David MacIver
  */
-private[immutable] object IntMapUtils {
-  def zero(i : Int, mask : Int) = (i & mask) == 0;
-  def mask(i : Int, mask : Int) = i & (complement(mask - 1) ^ mask)
-  def hasMatch(key : Int, prefix : Int, m : Int) = mask(key, m) == prefix;
-  def unsignedCompare(i : Int, j : Int) = (i < j) ^ (i < 0) ^ (j < 0)
-  def shorter(m1 : Int, m2 : Int) = unsignedCompare(m2, m1)
-  def complement(i : Int) = (-1) ^ i;
-  def highestOneBit(j : Int) = {
-    var i = j;
-    i |= (i >>  1);
-    i |= (i >>  2);
-    i |= (i >>  4);
-    i |= (i >>  8);
-    i |= (i >> 16);
-    i - (i >>> 1);
-  }
-
-  def branchMask(i : Int, j : Int) = highestOneBit(i ^ j);
+private[immutable] object IntMapUtils extends BitOperations.Int {
+  def branchMask(i: Int, j: Int) = highestOneBit(i ^ j)
 
   def join[T](p1 : Int, t1 : IntMap[T], p2 : Int, t2 : IntMap[T]) : IntMap[T] = {
     val m = branchMask(p1, p2);
diff --git a/src/library/scala/collection/immutable/LongMap.scala b/src/library/scala/collection/immutable/LongMap.scala
index 54538b6b2d..f02c6fce66 100644
--- a/src/library/scala/collection/immutable/LongMap.scala
+++ b/src/library/scala/collection/immutable/LongMap.scala
@@ -6,40 +6,17 @@
 **                          |/                                          **
 \*                                                                      */
 
-
-
 package scala.collection
 package immutable
 
-
-import scala.collection.generic.CanBuildFrom
-import scala.collection.mutable.Builder
-import scala.collection.mutable.MapBuilder
-
-
+import scala.collection.generic.{ CanBuildFrom, BitOperations }
+import scala.collection.mutable.{ Builder, MapBuilder }
 
 /** Utility class for long maps.
  *  @author David MacIver
  */
-private[immutable] object LongMapUtils{
-  def zero(i : Long, mask : Long) = (i & mask) == 0L;
-  def mask(i : Long, mask : Long) = i & (complement(mask - 1) ^ mask)
-  def hasMatch(key : Long, prefix : Long, m : Long) = mask(key, m) == prefix;
-  def unsignedCompare(i : Long, j : Long) = (i < j) ^ (i < 0) ^ (j < 0)
-  def shorter(m1 : Long, m2 : Long) = unsignedCompare(m2, m1)
-  def complement(i : Long) = (-1) ^ i;
-  def branchMask(i : Long, j : Long) = highestOneBit(i ^ j);
-
-  def highestOneBit(j : Long) = {
-    var i = j;
-    i |= (i >>  1);
-    i |= (i >>  2);
-    i |= (i >>  4);
-    i |= (i >>  8);
-    i |= (i >> 16);
-    i |= (i >> 32);
-    i - (i >>> 1);
-  }
+private[immutable] object LongMapUtils extends BitOperations.Long {
+  def branchMask(i: Long, j: Long) = highestOneBit(i ^ j)
 
   def join[T](p1 : Long, t1 : LongMap[T], p2 : Long, t2 : LongMap[T]) : LongMap[T] = {
     val m = branchMask(p1, p2);
diff --git a/src/library/scala/collection/mutable/OpenHashMap.scala b/src/library/scala/collection/mutable/OpenHashMap.scala
index 9c31cc5a6f..29dfc3ad19 100644
--- a/src/library/scala/collection/mutable/OpenHashMap.scala
+++ b/src/library/scala/collection/mutable/OpenHashMap.scala
@@ -6,12 +6,9 @@
 **                          |/                                          **
 \*                                                                      */
 
-
-
 package scala.collection
 package mutable
 
-
 /**
  *  @define Coll OpenHashMap
  *  @define coll open hash map
@@ -19,29 +16,16 @@ package mutable
  *  @since 2.7
  */
 object OpenHashMap {
-  def apply[K, V](elems : (K, V)*) = {
-    val dict = new OpenHashMap[K, V];
-    elems.foreach({case (x, y) => dict(x) = y});
-    dict;
-  }
+  import generic.BitOperations.Int.highestOneBit
 
-  def empty[K, V] = new OpenHashMap[K, V];
+  def apply[K, V](elems : (K, V)*) = new OpenHashMap[K, V] ++= elems
+  def empty[K, V] = new OpenHashMap[K, V]
 
   final private class OpenEntry[Key, Value](val key: Key,
                                             val hash: Int,
                                             var value: Option[Value])
                 extends HashEntry[Key, OpenEntry[Key, Value]]
 
-  private[mutable] def highestOneBit(j : Int) = { // This should really go somewhere central as we're now code sharing by cut and paste. :(
-    var i = j;
-    i |= (i >>  1);
-    i |= (i >>  2);
-    i |= (i >>  4);
-    i |= (i >>  8);
-    i |= (i >> 16);
-    i - (i >>> 1);
-  }
-
   private[mutable] def nextPowerOfTwo(i : Int) = highestOneBit(i) << 1;
 }