struct BitArray

Overview

`BitArray` is an array data structure that compactly stores bits.

Bits externally represented as `Bool`s are stored internally as `UInt32`s. The total number of bits stored is set at creation and is immutable.

NOTE To use `BitArray`, you must explicitly import it with `require "bit_array"`

Example

``````require "bit_array"

ba = BitArray.new(12) # => "BitArray[000000000000]"
ba[2]                 # => false
0.upto(5) { |i| ba[i * 2] = true }
ba    # => "BitArray[101010101010]"
ba[2] # => true``````

bit_array.cr

Constructor Detail

def self.new(size : Int, initial : Bool = false) #

Creates a new `BitArray` of size bits.

initial optionally sets the starting value, `true` or `false`, for all bits in the array.

def self.new(size : Int, & : Int32 -> _) #

Creates a new `BitArray` of size bits and invokes the given block once for each index of `self`, setting the bit at that index to `true` if the block is truthy.

``````BitArray.new(5) { |i| i >= 3 }     # => BitArray[00011]
BitArray.new(6) { |i| i if i < 2 } # => BitArray[110000]``````

Instance Method Detail

def ==(other : BitArray) #

def [](start : Int, count : Int) : BitArray #

Returns count or less (if there aren't enough) elements starting at the given start index.

Negative indices count backward from the end of the array (-1 is the last element). Additionally, an empty array is returned when the starting index for an element range is at the end of the array.

Raises `IndexError` if the starting index is out of range.

``````require "bit_array"

ba = BitArray.new(5)
ba[0] = true; ba[2] = true; ba[4] = true
ba # => BitArray[10101]

ba[-3, 3] # => BitArray[101]
ba[6, 1]  # raise indexError
ba[1, 2]  # => BitArray[01]
ba[5, 1]  # => BitArray[]``````

def [](range : Range) : BitArray #

Returns all elements that are within the given range.

Negative indices count backward from the end of the array (-1 is the last element). Additionally, an empty array is returned when the starting index for an element range is at the end of the array.

Raises `IndexError` if the starting index is out of range.

``````require "bit_array"

ba = BitArray.new(5)
ba[0] = true; ba[2] = true; ba[4] = true
ba # => BitArray[10101]

ba[1..3]    # => BitArray[010]
ba[4..7]    # => BitArray[1]
ba[6..10]   # raise IndexError
ba[5..10]   # => BitArray[]
ba[-2...-1] # => BitArray[0]``````

def []=(index : Int, value : Bool) : Bool #

Sets the given value at the given index. Returns value.

Negative indices can be used to start counting from the end of the container. Raises `IndexError` if trying to set an element outside the container's range.

``````ary = [1, 2, 3]
ary[0] = 5
ary # => [5, 2, 3]

ary[3] = 5 # raises IndexError``````

def all? : Bool #

Returns `true` if all of the elements of the collection are truthy.

``````[nil, true, 99].all? # => false
[15].all?            # => true``````

def any? : Bool #

Returns `true` if at least one of the collection's members is truthy.

``````[nil, true, 99].any? # => true
[nil, false].any?    # => false
([] of Int32).any?   # => false``````
• `#present?` does not consider truthiness of elements.
• `#any?(&)` and `#any(pattern)` allow custom conditions.

NOTE `#any?` usually has the same semantics as `#present?`. They only differ if the element type can be falsey (i.e. `T <= Nil || T <= Pointer || T <= Bool`). It's typically advised to prefer `#present?` unless these specific truthiness semantics are required.

def count(item : Bool) : Int32 #

Returns the number of times that item is present in the bit array.

``````ba = BitArray.new(12, true)
ba[3] = false
ba[7] = false
ba.count(true)  # => 10
ba.count(false) # => 2``````

def dup #

Returns a new `BitArray` with all of the same elements.

def fill(value : Bool, start : Int, count : Int) : self #

Replaces count or less (if there aren't enough) elements starting at the given start index with value. Returns `self`.

Negative values of start count from the end of the container.

Raises `IndexError` if the start index is out of range.

Raises `ArgumentError` if count is negative.

``````array = [1, 2, 3, 4, 5]
array.fill(9, 2, 2) # => [1, 2, 9, 9, 5]
array               # => [1, 2, 9, 9, 5]``````

def fill(value : Bool) : self #

Replaces every element in `self` with the given value. Returns `self`.

``````array = [1, 2, 3, 4]
array.fill(2) # => [2, 2, 2, 2]
array         # => [2, 2, 2, 2]``````

def hash(hasher) #

See `Object#hash(hasher)`

def includes?(obj : Bool) : Bool #

Returns `true` if the collection contains obj, `false` otherwise.

``````ba = BitArray.new(8, true)
ba.includes?(true)  # => true
ba.includes?(false) # => false``````

def index(obj : Bool, offset : Int = 0) : Int32 | Nil #

Returns the index of the first appearance of obj in `self` starting from the given offset, or `nil` if the value is not in `self`.

``````ba = BitArray.new(16)
ba[5] = ba[11] = true
ba.index(true)             # => 5
ba.index(true, offset: 8)  # => 11
ba.index(true, offset: 12) # => nil``````

def inspect(io : IO) : Nil #

Creates a string representation of `self`.

``````require "bit_array"

ba = BitArray.new(5)
ba.to_s # => "BitArray[00000]"``````

def invert : Nil #

Inverts all bits in the array. Falses become `true` and vice versa.

``````require "bit_array"

ba = BitArray.new(5)
ba[2] = true; ba[3] = true
ba # => BitArray[00110]
ba.invert
ba # => BitArray[11001]``````

def none? : Bool #

Returns `true` if all of the elements of the collection are falsey.

``````[nil, false].none?       # => true
[nil, false, true].none? # => false``````

It's the opposite of `#all?`.

def one? : Bool #

Returns `true` if only one element in this enumerable is truthy.

``````[1, false, false].one? # => true
[1, false, 3].one?     # => false
[1].one?               # => true
[false].one?           # => false``````

def reverse! : self #

Reverses in-place all the elements of `self`. Returns `self`.

def rindex(obj : Bool, offset : Int = size - 1) : Int32 | Nil #

Returns the index of the last appearance of obj in `self`, or `nil` if obj is not in `self`.

If offset is given, the search starts from that index towards the first elements in `self`.

``````ba = BitArray.new(16)
ba[5] = ba[11] = true
ba.rindex(true)            # => 11
ba.rindex(true, offset: 8) # => 5
ba.rindex(true, offset: 4) # => nil``````

def rotate!(n : Int = 1) : self #

Shifts all elements of `self` to the left n times. Returns `self`.

``````a1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
a2 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
a3 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

a1.rotate!
a2.rotate!(1)
a3.rotate!(3)

a1 # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
a2 # => [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
a3 # => [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]``````

def size : Int32 #

The number of bits the BitArray stores

def tally(hash) #

Tallies the collection. Accepts a hash to count occurrences. The value corresponding to each element must be an integer. The number of occurrences is added to each value in hash, and hash is returned.

``````hash = {} of Char => Int32
words = ["crystal", "ruby"]
words.each { |word| word.chars.tally(hash) }
hash # => {'c' => 1, 'r' => 2, 'y' => 2, 's' => 1, 't' => 1, 'a' => 1, 'l' => 1, 'u' => 1, 'b' => 1}``````

def tally : Hash(Bool, Int32) #

Tallies the collection. Returns a hash where the keys are the elements and the values are numbers of elements in the collection that correspond to the key.

``["a", "b", "c", "b"].tally # => {"a"=>1, "b"=>2, "c"=>1}``

def to_s(io : IO) : Nil #

Creates a string representation of `self`.

``````require "bit_array"

ba = BitArray.new(5)
ba.to_s # => "BitArray[00000]"``````

def to_slice : Bytes #

Returns a `Bytes` able to read and write bytes from a buffer. The slice will be long enough to hold all the bits groups in bytes despite the `UInt32` internal representation. It's useful for reading and writing a bit array from a byte buffer directly.

WARNING It is undefined behaviour to set any of the unused bits of a bit array to `true` via a slice.

def toggle(start : Int, count : Int) #

Toggles count or less (if there aren't enough) bits starting at the given start index. A `false` bit becomes a `true` bit, and vice versa.

Negative indices count backward from the end of the array (-1 is the last element).

Raises `IndexError` if index is out of range. Raises `ArgumentError` if count is a negative number.

``````require "bit_array"

ba = BitArray.new(5)
ba.to_s # => "BitArray[00000]"
ba.toggle(1, 3)
ba.to_s # => "BitArray[01110]"``````

def toggle(range : Range) #

Toggles all bits that are within the given range. A `false` bit becomes a `true` bit, and vice versa.

Negative indices count backward from the end of the array (-1 is the last element).

Raises `IndexError` if the starting index is out of range.

``````require "bit_array"

ba = BitArray.new(5)
ba.to_s # => "BitArray[00000]"
ba.toggle(1..-2)
ba.to_s # => "BitArray[01110]"``````

def toggle(index) : Nil #

Toggles the bit at the given index. A `false` bit becomes a `true` bit, and vice versa.

Negative indices count backward from the end of the array (-1 is the last element).

Raises `IndexError` if index is out of range.

``````require "bit_array"

ba = BitArray.new(5)
ba[3] # => false
ba.toggle(3)
ba[3] # => true``````

def unsafe_fetch(index : Int) : Bool #
Description copied from module Indexable(Bool)

Returns the element at the given index, without doing any bounds check.

`Indexable` makes sure to invoke this method with index in `0...size`, so converting negative indices to positive ones is not needed here.

Clients never invoke this method directly. Instead, they access elements with `#[](index)` and `#[]?(index)`.

This method should only be directly invoked if you are absolutely sure the index is in bounds, to avoid a bounds check for a small boost of performance.

def unsafe_put(index : Int, value : Bool) #
Description copied from module Indexable::Mutable(Bool)

Sets the element at the given index to value, without doing any bounds check.

`Indexable::Mutable` makes sure to invoke this method with index in `0...size`, so converting negative indices to positive ones is not needed here.

Clients never invoke this method directly. Instead, they modify elements with `#[]=(index, value)`.

This method should only be directly invoked if you are absolutely sure the index is in bounds, to avoid a bounds check for a small boost of performance.