Skip to content

Instantly share code, notes, and snippets.

@aishfenton
Created February 10, 2017 23:38
Show Gist options
  • Save aishfenton/8dd5841974289eb6f0e79f3a7edb236c to your computer and use it in GitHub Desktop.
Save aishfenton/8dd5841974289eb6f0e79f3a7edb236c to your computer and use it in GitHub Desktop.
ArrayMap.scala
trait EnumMap[A, B] {
def apply(a: A): B
}
// Quick sketch, untested.
final class ArrayEnumMap[A, @spec B : ClassTag](xs: Seq[(A,B)]) extends EnumMap[A,B] {
val (keys, values) = mkEntries(xs)
val size = keys.length
def mkEntries(xs: Seq[(A,B)]): (Array[Int], Seq[B]) = {
val sorted = xs.sortBy(_._1.hashCode)
(sorted.map(_._1.hashCode).toArray, sorted.map(_._2))
}
@inline
def apply(a: A) = {
val hash = a.hashCode
var high = size
var low = 0
var i = (high - low) >> 1
while (hash != keys(i) && high != low) {
if (hash < keys(i)) high = i else low = i
i = low + ((high - low) >> 1)
}
values(i)
}
}
object ArrayEnumMap {
def apply[A, @spec B : ClassTag](xs: (A,B)*) = new ArrayEnumMap(xs)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment