LogicalBitSet.scala

package cats.collections

sealed abstract class LogicalBitSet { lhs =>

  import LogicalBitSet.{Absent, Present}

  def apply(n: Int): Boolean =
    this match {
      case Present(bits) => bits(n)
      case Absent(bits) => !bits(n)
    }

  def size: Long =
    this match {
      case Present(bits) => bits.size
      case Absent(bits) => LogicalBitSet.MaxSize - bits.size
    }

  def +(n: Int): LogicalBitSet =
    this match {
      case Present(bits) => Present(bits + n)
      case Absent(bits) => Absent(bits - n)
    }

  def -(n: Int): LogicalBitSet =
    this match {
      case Present(bits) => Present(bits - n)
      case Absent(bits) => Absent(bits + n)
    }

  def unary_~ : LogicalBitSet =
    this match {
      case Present(bits) => Absent(bits)
      case Absent(bits) => Present(bits)
    }

  def &(rhs: LogicalBitSet): LogicalBitSet =
    (lhs, rhs) match {
      case (Present(bits0), Present(bits1)) => Present(bits0 & bits1)
      case (Absent(bits0), Absent(bits1)) => Absent(bits0 | bits1)
      case (Present(bits0), Absent(bits1)) => Present(bits0 -- bits1)
      case (Absent(bits0), Present(bits1)) => Present(bits1 -- bits0)
    }

  def |(rhs: LogicalBitSet): LogicalBitSet =
    (lhs, rhs) match {
      case (Present(bits0), Present(bits1)) => Present(bits0 | bits1)
      case (Absent(bits0), Absent(bits1)) => Absent(bits0 & bits1)
      case (Present(bits0), Absent(bits1)) => Absent(bits1 -- bits0)
      case (Absent(bits0), Present(bits1)) => Absent(bits0 -- bits1)
    }

  def ^(rhs: LogicalBitSet): LogicalBitSet =
    (lhs, rhs) match {
      case (Present(bits0), Present(bits1)) => Present(bits0 ^ bits1)
      case (Absent(bits0), Absent(bits1)) => Present(bits0 ^ bits1)
      case (Present(bits0), Absent(bits1)) => Present(bits0 & bits1)
      case (Absent(bits0), Present(bits1)) => Present(bits0 & bits1)
    }
}

object LogicalBitSet {

  final val MaxSize = 4294967296L

  def empty: LogicalBitSet = Empty
  val Empty: LogicalBitSet = Present(BitSet.empty)

  def full: LogicalBitSet = Full
  val Full: LogicalBitSet = Absent(BitSet.empty)

  case class Present(bits: BitSet) extends LogicalBitSet
  case class Absent(bits: BitSet) extends LogicalBitSet
}