Scala BitSet and shift operations

Question

I'm looking for a way to represent a set of integers with a bit vector (which would be the characteristic function of that set of integers) and be able to perform bitwise operations on this set.

Initially I thought scala's BitSet would be the ideal candidate. However, it seems BitSet doesn't support shifting operations according to the documentation 1. Upon further investigation I also found that the related Java BitSet implementation doesn't support shift operations either 2.

Am I left with the only option of implementing my own BitSet class which supports shift operations? Moreover, according to the description given in 3 it doesn't sound that difficult to support shift operations on the Scala's BitSet implementation, or have I misunderstood something here?

Thanks in advance.

Kevin Wright Kevin Wright · Accepted Answer · 2011-09-07T20:28:58

The usual trick when faced with a need for retrofitting new functionality is the "Pimp My Library" pattern. Implicitly convert the BitSet to a dedicated type intended to perform the added operation:

class ShiftableBitSet(bs: BitSet) {
  def shiftLeft(n: Int): BitSet = ... //impl goes here
}

implicit def bitsetIsShiftable(bs: BitSet) = new ShiftableBitSet(bs)

val sample = BitSet(1,2,3,5,7,9)
val shifted = sample.shiftLeft(2)

Alter shiftLeft to whatever name and with whatever arguments you prefer.

UPDATE

If you know for certain that you'll have an immutable BitSet, then a (slightly hacky) approach to access the raw underlying array is to pattern match. Not too painful either, as there are only 3 possible concrete subclasses for an immutable BitSet:

import collection.immutable.BitSet
val bitSet = BitSet(1,2,3)
bitSet match {
  case bs: BitSet.BitSet1 => Array(bs.elems)
  case bs: BitSet.BitSetN => bs.elems 
  case _ => error("unusable BitSet")
}

Annoyingly, the elems1 param to BitSet2 isn't a val, and the elems param to a mutable BitSet is marked protected. So it's not perfect, but should do the trick if your set is non-trivial and immutable. For the trivial cases, "normal" access to the set won't be too expensive.

And yes, this technique would be used within the wrapper as described above.

Scala BitSet and shift operations

2 Answers