diff options
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; } |