3

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.

Community
  • 1
  • 1
Asiri Rathnayake
  • 1,138
  • 1
  • 11
  • 27

2 Answers2

6

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.

Asiri Rathnayake
  • 1,138
  • 1
  • 11
  • 27
Kevin Wright
  • 49,540
  • 9
  • 105
  • 155
  • Since BitSet internally employs an array of Longs to represent the bit vector, access to that array would be vital in order to implement the shifting operations efficiently (since shift operations on Longs are natively supported). However on a wrapper implementation like the one you have suggested, it would only be possible to implement the said functionality using operations supported by the BitSet interface itself, which would not be that efficient IMHO. – Asiri Rathnayake Sep 07 '11 at 20:53
  • Thanks for the update, it sounds (hacky but) clever! I was thinking of using a mutable `BitSet` to avoid the unnecessary creation of objects but as you have mentioned this trick only works for immutable `BitSet`. Btw, I think you meant to say `BitSet` instead of `BitMap` in the last paragraph (?). – Asiri Rathnayake Sep 08 '11 at 06:24
  • It's undoubtably hacky, and not robust in the face of future BitSet implementations. But so long as you're willing to deal with that... – Kevin Wright Sep 08 '11 at 11:22
-3

You can just use map, for example to shift to left by 4 positions:

import collection.immutable.BitSet
val bitSet = BitSet(1,2,3)
bitSet map (_ + 4)
Anton Kovsharov
  • 1
  • 2