sealed abstract class BitSet extends AnyRef
A fast, immutable BitSet.
This implementation is taken from cats-collections. https://github.com/typelevel/cats-collections/blob/0336992942aba9aba4a322b629447fcabe251920/core/src/main/scala/cats/collections/BitSet.scala
A Bitset is a specialized type of set that tracks the Int values
it contains: for each integer value, a BitSet uses a single bit to
track whether the value is present (1) or absent (0). Bitsets are
often sparse, since "missing" bits can be assumed to be zero.
Unlike scala's default immutable this BitSet does not do a full copy on each added value.
Internally the implementation is a tree. Each leaf uses an Array[Long] value to hold up to 2048 bits, and each branch uses an Array[BitSet] to hold up to 32 subtrees (null subtrees are treated as empty).
Bitset treats the values it stores as 32-bit unsigned values, which
is relevant to the internal addressing methods as well as the order
used by iterator.
The benchmarks suggest this bitset is MUCH faster than Scala's built-in bitset for cases where you may need many modifications and merges, (for example in a BloomFilter).
- Self Type
- BitSet
- Alphabetic
- By Inheritance
- BitSet
- AnyRef
- Any
- Hide All
- Show All
- Public
- Protected
Abstract Value Members
- abstract def &(rhs: BitSet): BitSet
Return the intersection of two bitsets as a new immutable bitset.
Return the intersection of two bitsets as a new immutable bitset.
The resulting bitset will only contain a value if that value is present in both input bitsets.
- abstract def +(n: Int): BitSet
Return a bitset that contains
nand whose other values are identical to this one's.Return a bitset that contains
nand whose other values are identical to this one's. If this bitset already containsnthen this method does nothing. - abstract def -(n: Int): BitSet
Return a bitset that does not contain
nand whose other values are identical to this one's.Return a bitset that does not contain
nand whose other values are identical to this one's. If this bitset does not containnthen this method does nothing. - abstract def --(rhs: BitSet): BitSet
Return this bitset minus the bits contained in the other bitset as a new immutable bitset.
Return this bitset minus the bits contained in the other bitset as a new immutable bitset.
The resulting bitset will contain exactly those values which do appear in the left-hand side but do not appear in the right-hand side.
If the bitsets do not intersect, the left-hand side will be returned.
- abstract def ^(rhs: BitSet): BitSet
Return the exclusive-or of two bitsets as a new immutable bitset.
- abstract def apply(n: Int): Boolean
Look for a particular value in the bitset.
Look for a particular value in the bitset.
Returns whether this value's bit is set.
- abstract def intersects(rhs: BitSet): Boolean
Returns whether the two bitsets intersect or not.
Returns whether the two bitsets intersect or not.
Equivalent to (x & y).nonEmpty but faster.
- abstract def isEmpty: Boolean
Returns false if this bitset contains values, true otherwise.
- abstract def iterator: Iterator[Int]
Iterate across all values in the bitset.
Iterate across all values in the bitset.
Values in the iterator will be seen in "unsigned order" (e.g. if present, -1 will always come last). Here's an abbreviated view of this order in practice:
0, 1, 2, ... 2147483646, 2147483647, -2147483648, -2147483647, ... -1
(This "unsigned order" is identical to the tree's internal order.)
- abstract def reverseIterator: Iterator[Int]
Iterate across all values in the bitset in reverse order.
Iterate across all values in the bitset in reverse order.
The order here is exactly the reverse of
.iterator. - abstract def size: Long
Returns the number of distinct values in this bitset.
Returns the number of distinct values in this bitset.
For branches, this method will return the sum of the sizes of all its subtrees. For leaves it returns the number of bits set in the leaf (i.e. the number of values the leaf contains).
- abstract def |(rhs: BitSet): BitSet
Return the union of two bitsets as a new immutable bitset.
Return the union of two bitsets as a new immutable bitset.
If either bitset contains a given value, the resulting bitset will also contain it.
Concrete Value Members
- final def !=(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- final def ##: Int
- Definition Classes
- AnyRef → Any
- final def ==(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- final def asInstanceOf[T0]: T0
- Definition Classes
- Any
- def clone(): AnyRef
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.CloneNotSupportedException]) @native()
- def compact: BitSet
Return a compacted bitset containing the same values as this one.
Return a compacted bitset containing the same values as this one.
This method is used to prune out "empty" branches that don't contain values. By default, bitset does not try to remove empty leaves when removing values (since repeatedly checking for this across many deletions would be expensive).
The bitset returned will have the same values as the current bitset, but is guaranteed not to contain any empty branches. Empty branches are not usually observable but would result in increased memory usage.
- final def eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- def equals(that: Any): Boolean
Universal equality.
Universal equality.
This method will only return true if the right argument is also a
BitSet. It does not attempt to coerce either argument in any way (unlike Scala collections, for example).Two bitsets can be equal even if they have different underlying tree structure. (For example, one bitset's tree may have empty branches that the other lacks.)
- Definition Classes
- BitSet → AnyRef → Any
- def finalize(): Unit
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.Throwable])
- final def getClass(): Class[_ <: AnyRef]
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
- def hashCode(): Int
Universal hash code.
Universal hash code.
Bitsets that are the equal will hash to the same value. As in
equals, the values present determine the hash code, as opposed to the tree structure.- Definition Classes
- BitSet → AnyRef → Any
- final def isInstanceOf[T0]: Boolean
- Definition Classes
- Any
- final def ne(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- def nonEmpty: Boolean
Returns true if this bitset contains values, false otherwise.
- final def notify(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
- final def notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
- final def synchronized[T0](arg0: => T0): T0
- Definition Classes
- AnyRef
- def toSet: Set[Int]
Present a view of this bitset as a
scala.Set[Int].Present a view of this bitset as a
scala.Set[Int].This is provided for compatibility with Scala collections. Many of the set operations are implemented in terms of
BitSet, but other operations (for examplemap) may copy these values into a differentSetimplementation. - def toString(): String
Produce a string representation of this BitSet.
Produce a string representation of this BitSet.
This representation will contain all the values in the bitset. For large bitsets, this operation may be very expensive.
- Definition Classes
- BitSet → AnyRef → Any
- final def wait(): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
- final def wait(arg0: Long, arg1: Int): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
- final def wait(arg0: Long): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException]) @native()