diff options
author | Geoffrey Washburn <geoffrey.washburn@epfl.ch> | 2008-08-06 12:38:40 +0000 |
---|---|---|
committer | Geoffrey Washburn <geoffrey.washburn@epfl.ch> | 2008-08-06 12:38:40 +0000 |
commit | f07ac82ac24574719db524add05d46e30b3f1502 (patch) | |
tree | 403c8afed67ba2d94ee690ca5e50d17b8b4481a8 /src/library | |
parent | 8a8230837a330c90132f093d299400fd98f1cadf (diff) | |
download | scala-f07ac82ac24574719db524add05d46e30b3f1502.tar.gz scala-f07ac82ac24574719db524add05d46e30b3f1502.tar.bz2 scala-f07ac82ac24574719db524add05d46e30b3f1502.zip |
Checked in David's update to LongMap and IntMap.
Diffstat (limited to 'src/library')
-rw-r--r-- | src/library/scala/collection/immutable/IntMap.scala | 12 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/LongMap.scala | 13 |
2 files changed, 23 insertions, 2 deletions
diff --git a/src/library/scala/collection/immutable/IntMap.scala b/src/library/scala/collection/immutable/IntMap.scala index 71b10610a3..0d54fcd671 100644 --- a/src/library/scala/collection/immutable/IntMap.scala +++ b/src/library/scala/collection/immutable/IntMap.scala @@ -7,7 +7,17 @@ private[immutable] object IntMapUtils{ 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 branchMask(i : Int, j : Int) = java.lang.Integer.highestOneBit(i ^ j); + 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); 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 b23537aca6..953a89952e 100644 --- a/src/library/scala/collection/immutable/LongMap.scala +++ b/src/library/scala/collection/immutable/LongMap.scala @@ -7,7 +7,18 @@ private[immutable] object LongMapUtils{ 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) = java.lang.Long.highestOneBit(i ^ j); + 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); + } def join[T](p1 : Long, t1 : LongMap[T], p2 : Long, t2 : LongMap[T]) : LongMap[T] = { val m = branchMask(p1, p2); |