LongSet impl

LongSet.scala

import java.util

class LongSet {

  val buckets = scala.collection.mutable.HashMap[Int, util.BitSet]()

  private def position(n: Long): (Int, Int) =
    ( (n / Int.MaxValue).toInt, (n % Int.MaxValue).toInt)

  def set(n: Long): Unit = {
    val (bucket, index) = position(n)
    val bitsetO = buckets.get(bucket)
    if( bitsetO.isDefined ) {
      bitsetO.get.set(index)
    } else {
      val bitset = new util.BitSet()
      bitset.set(index)
      buckets.put(bucket, bitset)
    }
  }

  def contains(n: Long): Boolean = {
    val (bucket, index) = position(n)
    buckets.get(bucket).exists(_.get(index))
  }

}

// test
val ls = new LongSet()

ls.set(10)

assert(ls.contains(10))

ls.set(Int.MaxValue.toLong * 3 + 10L)
assert(ls.contains(Int.MaxValue.toLong *3 + 10L))