struct BitArray

Overview

BitArray is an array data structure that compactly stores bits.

Bits externally represented as Bools are stored internally as UInt32s. The total number of bits stored is set at creation and is immutable.

BitArray includes all the methods in Enumerable.

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

Included Modules

Defined in:

bit_array.cr

Constructors

Instance Method Summary

Instance methods inherited from module Indexable(Bool)

[](index : Int) [], []?(index : Int) []?, bsearch(&block) bsearch, bsearch_index(&block) bsearch_index, dig(index : Int, *subindexes) dig, dig?(index : Int, *subindexes) dig?, each(&block)
each
each(*, start : Int, count : Int, &block)
each(*, within range : Range(Int, Int), &block)
each
, each_index(*, start : Int, count : Int, &block)
each_index(&block) : Nil
each_index
each_index
, empty? empty?, equals?(other, &block)
equals?(other : Indexable, &block)
equals?
, fetch(index, default)
fetch(index : Int, &block)
fetch
, first(&block)
first
first
, first? first?, hash(hasher) hash, index(object, offset : Int = 0)
index(offset : Int = 0, &block)
index
, join(separator = "") join, last
last(&block)
last
, last? last?, reverse_each(&block) : Nil
reverse_each
reverse_each
, rindex(value, offset = size - 1)
rindex(offset = size - 1, &block)
rindex
, sample(random = Random::DEFAULT) sample, size size, to_a to_a, unsafe_fetch(index : Int) unsafe_fetch, values_at(*indexes : Int) values_at, zip(other : Indexable(U), &block : T, U -> ) forall U
zip(other : Indexable(U)) : Array(Tuple(T, U)) forall U
zip
, zip?(other : Indexable(U), &block : T, U? -> ) forall U
zip?(other : Indexable(U)) : Array(Tuple(T, U?)) forall U
zip?

Instance methods inherited from module Enumerable(Bool)

all?(&block)
all?(pattern)
all?
all?
, any?(&block)
any?(pattern)
any?
any?
, chunks(&block : T -> U) forall U chunks, compact_map(&block) compact_map, count(item)
count(&block)
count
, cycle(&block)
cycle(n, &block)
cycle
, each(&block : T -> UNDERSCORE) each, each_cons(count : Int, reuse = false, &block) each_cons, each_slice(count : Int, reuse = false, &block) each_slice, each_with_index(offset = 0, &block) each_with_index, each_with_object(obj, &block) each_with_object, find(if_none = nil, &block) find, first(count : Int)
first
first
, first? first?, flat_map(&block : T -> Array(U) | Iterator(U) | U) forall U flat_map, grep(pattern) grep, group_by(&block : T -> U) forall U group_by, in_groups_of(size : Int, filled_up_with : U = nil) forall U
in_groups_of(size : Int, filled_up_with : U = nil, reuse = false, &block) forall U
in_groups_of
, includes?(obj) includes?, index(&block)
index(obj)
index
, index_by(&block : T -> U) forall U index_by, join(separator, io)
join(separator = "")
join(separator, io, &block)
join(separator = "", &block)
join
, map(&block : T -> U) forall U map, map_with_index(&block : T, Int32 -> U) forall U map_with_index, max max, max? max?, max_by(&block : T -> U) forall U max_by, max_by?(&block : T -> U) forall U max_by?, max_of(&block : T -> U) forall U max_of, max_of?(&block : T -> U) forall U max_of?, min min, min? min?, min_by(&block : T -> U) forall U min_by, min_by?(&block : T -> U) forall U min_by?, min_of(&block : T -> U) forall U min_of, min_of?(&block : T -> U) forall U min_of?, minmax minmax, minmax? minmax?, minmax_by(&block : T -> U) forall U minmax_by, minmax_by?(&block : T -> U) forall U minmax_by?, minmax_of(&block : T -> U) forall U minmax_of, minmax_of?(&block : T -> U) forall U minmax_of?, none?(&block)
none?(pattern)
none?
none?
, one?(&block)
one?(pattern)
one?
one?
, partition(&block) partition, product
product(initial : Number, &block)
product(&block)
product(initial : Number)
product
, reduce(memo, &block)
reduce(&block)
reduce
, reject(&block : T -> )
reject(type : U.class) forall U
reject(pattern)
reject
, select(type : U.class) forall U
select(&block : T -> )
select(pattern)
select
, size size, skip(count : Int) skip, skip_while(&block) skip_while, sum(initial)
sum
sum(initial, &block)
sum(&block)
sum
, take_while(&block) take_while, to_a to_a, to_h
to_h(&block : T -> Tuple(K, V)) forall K, V
to_h
, to_set to_set

Instance methods inherited from module Iterable(Bool)

chunk(reuse = false, &block : T -> U) forall U chunk, chunk_while(reuse : Bool | Array(T) = false, &block : T, T -> B) forall B chunk_while, cycle(n)
cycle
cycle
, each each, each_cons(count : Int, reuse = false) each_cons, each_slice(count : Int, reuse = false) each_slice, each_with_index(offset = 0) each_with_index, each_with_object(obj) each_with_object, slice_after(reuse : Bool | Array(T) = false, &block : T -> B) forall B
slice_after(pattern, reuse : Bool | Array(T) = false)
slice_after
, slice_before(reuse : Bool | Array(T) = false, &block : T -> B) forall B
slice_before(pattern, reuse : Bool | Array(T) = false)
slice_before
, slice_when(reuse : Bool | Array(T) = false, &block : T, T -> B) forall B slice_when

Instance methods inherited from struct Struct

==(other) : Bool ==, hash(hasher) hash, inspect(io : IO) : Nil inspect, pretty_print(pp) : Nil pretty_print, to_s(io) to_s

Instance methods inherited from struct Value

==(other : JSON::Any)
==(other : YAML::Any)
==(other)
==
, dup dup

Instance methods inherited from class Object

!=(other) !=, !~(other) !~, ==(other) ==, ===(other : JSON::Any)
===(other : YAML::Any)
===(other)
===
, =~(other) =~, class class, dup dup, hash(hasher)
hash
hash
, inspect(io : IO)
inspect
inspect
, itself itself, not_nil! not_nil!, pretty_inspect(width = 79, newline = "\n", indent = 0) : String pretty_inspect, pretty_print(pp : PrettyPrint) : Nil pretty_print, tap(&block) tap, to_json(io : IO)
to_json
to_json
, to_pretty_json(indent : String = " ")
to_pretty_json(io : IO, indent : String = " ")
to_pretty_json
, to_s
to_s(io : IO)
to_s
, to_yaml(io : IO)
to_yaml
to_yaml
, try(&block) try, unsafe_as(type : T.class) forall T unsafe_as

Constructor methods inherited from class Object

from_json(string_or_io, root : String) : self
from_json(string_or_io) : self
from_json
, from_yaml(string_or_io : String | IO) : self from_yaml

Constructor Detail

def self.new(size, 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.


[View source]

Instance Method Detail

def ==(other : BitArray) #

[View source]
def ==(other) #

[View source]
def [](start : Int, count : Int) #

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.

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[]

[View source]
def [](range : Range(Int, Int)) #

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.

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]

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

Sets the bit at the given index. Negative indices can be used to start counting from the end of the array. Raises IndexError if trying to access a bit outside the array's range.

ba = BitArray.new(5)
ba[3] = true

[View source]
def hash(hasher) #

[View source]
def inspect(io : IO) #

Creates a string representation of self.

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

[View source]
def invert #

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

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

[View source]
def size : Int32 #

The number of bits the BitArray stores


[View source]
def to_s(io : IO) #

Creates a string representation of self.

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

[View source]
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.


[View source]
def toggle(index) #

Toggles the bit at the given index. A false bit becomes a true bit, and vice versa. Negative indices can be used to start counting from the end of the array. Raises IndexError if trying to access a bit outside the array's range.

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

[View source]
def unsafe_fetch(index : Int) #

[View source]