struct BitArray

Overview

BitArray is an array data structure that compactly stores bits.

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

NOTE To useBitArray, you must explicitly import it withrequire "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

Included Modules

Defined in:

bit_array.cr

Constructors

Instance Method Summary

Instance methods inherited from module Indexable::Mutable(Bool)

[]=(index : Int, value : T) : T []=, fill(value : T, start : Int, count : Int) : self
fill(value : T, range : Range) : self
fill(value : T) : self
fill(start : Int, count : Int, & : Int32 -> T) : self
fill(range : Range, & : Int32 -> T) : self
fill(*, offset : Int = 0, & : Int32 -> T) : self
fill
, map!(& : T -> _) : self map!, map_with_index!(offset = 0, & : T, Int32 -> _) : self map_with_index!, reverse! : self reverse!, rotate!(n : Int = 1) : self rotate!, shuffle!(random : Random | Nil = nil) : self shuffle!, sort! : self
sort!(&block : T, T -> U) : self forall U
sort!
, sort_by!(&block : T -> _) : self sort_by!, swap(index0 : Int, index1 : Int) : self swap, unsafe_put(index : Int, value : T) unsafe_put, unstable_sort! : self
unstable_sort!(&block : T, T -> U) : self forall U
unstable_sort!
, unstable_sort_by!(&block : T -> _) : self unstable_sort_by!, update(index : Int, & : T -> _) : T update

Instance methods inherited from module Indexable(Bool)

[](index : Int) [], []?(index : Int) []?, bsearch(& : T -> _) bsearch, bsearch_index(& : T, Int32 -> _) bsearch_index, cartesian_product(*others : Indexable) cartesian_product, combinations(size : Int = self.size) combinations, dig(index : Int, *subindexes) dig, dig?(index : Int, *subindexes) dig?, each(& : T -> )
each
each(*, start : Int, count : Int, & : T -> )
each(*, within range : Range, & : T -> )
each
, each_cartesian(*others : Indexable, &)
each_cartesian(*others : Indexable)
each_cartesian
, each_combination(size : Int = self.size, reuse = false, &) : Nil
each_combination(size : Int = self.size, reuse = false)
each_combination
, each_index(& : Int32 -> ) : Nil
each_index
each_index(*, start : Int, count : Int, &)
each_index
, each_permutation(size : Int = self.size, reuse = false, &) : Nil
each_permutation(size : Int = self.size, reuse = false)
each_permutation
, each_repeated_combination(size : Int = self.size, reuse = false, &) : Nil
each_repeated_combination(size : Int = self.size, reuse = false)
each_repeated_combination
, empty? : Bool empty?, equals?(other : Indexable, &) : Bool
equals?(other, &)
equals?
, fetch(index : Int, &)
fetch(index, default)
fetch
, find(if_none, _offset offset : Int, & : T -> )
find(if_none = nil, *, offset : Int, & : T -> )
find
, find!(offset : Int = 0, & : T -> ) find!, first(&) first, hash(hasher) hash, index(object, offset : Int = 0)
index(offset : Int = 0, & : T -> )
index
, index!(obj, offset : Int = 0)
index!(offset : Int = 0, & : T -> )
index!
, join(separator : String | Char | Number = "") : String join, last : T
last(&)
last
, last? : T | Nil last?, permutations(size : Int = self.size) : Array(Array(T)) permutations, repeated_combinations(size : Int = self.size) : Array(Array(T)) repeated_combinations, reverse_each(& : T -> ) : Nil
reverse_each
reverse_each
, rindex(value, offset = size - 1)
rindex(offset = size - 1, & : T -> )
rindex
, rindex!(value, offset = size - 1)
rindex!(offset = size - 1, & : T -> )
rindex!
, sample(n : Int, random : Random | Nil = nil) : Array(T)
sample(random : Random | Nil = nil)
sample
, size size, to_a(& : T -> U) : Array(U) forall U to_a, unsafe_fetch(index : Int) unsafe_fetch, values_at(*indexes : Int) values_at

Class methods inherited from module Indexable(Bool)

cartesian_product(indexables : Indexable(Indexable)) cartesian_product, each_cartesian(indexables : Indexable(Indexable), reuse = false, &)
each_cartesian(indexables : Indexable(Indexable), reuse = false)
each_cartesian

Instance methods inherited from module Enumerable(Bool)

accumulate(initial : U) : Array(U) forall U
accumulate : Array(T)
accumulate(initial : U, &block : U, T -> U) : Array(U) forall U
accumulate(&block : T, T -> T) : Array(T)
accumulate
, all?(& : T -> ) : Bool
all?(pattern) : Bool
all? : Bool
all?
, any?(& : T -> ) : Bool
any?(pattern) : Bool
any? : Bool
any?
, chunks(&block : T -> U) forall U chunks, compact_map(& : T -> _) compact_map, count(& : T -> ) : Int32
count(item) : Int32
count
, cycle(n, & : T -> ) : Nil
cycle(& : T -> ) : Nil
cycle
, each(& : T -> ) each, each_cons(count : Int, reuse = false, &) each_cons, each_cons_pair(& : T, T -> ) : Nil each_cons_pair, each_slice(count : Int, reuse = false, &) each_slice, each_step(n : Int, *, offset : Int = 0, & : T -> ) : Nil each_step, each_with_index(offset = 0, &) each_with_index, each_with_object(obj : U, & : T, U -> ) : U forall U each_with_object, empty? : Bool empty?, find(if_none = nil, & : T -> ) find, find!(& : T -> ) : T find!, find_value(if_none = nil, & : T -> ) find_value, first(&)
first(count : Int) : Array(T)
first : T
first
, first? : T | Nil first?, flat_map(& : T -> _) flat_map, group_by(& : 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, &) forall U
in_groups_of
, in_slices_of(size : Int) : Array(Array(T)) in_slices_of, includes?(obj) : Bool includes?, index(& : T -> ) : Int32 | Nil
index(obj) : Int32 | Nil
index
, index!(& : T -> ) : Int32
index!(obj) : Int32
index!
, index_by(& : T -> U) : Hash(U, T) forall U index_by, join(io : IO, separator = "") : Nil
join(separator, io : IO) : Nil
join(separator = "") : String
join(io : IO, separator = "", & : T, IO -> )
join(separator, io : IO, &)
join(separator = "", & : T -> )
join
, map(& : T -> U) : Array(U) forall U map, map_with_index(offset = 0, & : T, Int32 -> U) : Array(U) forall U map_with_index, max(count : Int) : Array(T)
max : T
max
, max? : T | Nil max?, max_by(& : T -> U) : T forall U max_by, max_by?(& : T -> U) : T | Nil forall U max_by?, max_of(& : T -> U) : U forall U max_of, max_of?(& : T -> U) : U | Nil forall U max_of?, min(count : Int) : Array(T)
min : T
min
, min? : T | Nil min?, min_by(& : T -> U) : T forall U min_by, min_by?(& : T -> U) : T | Nil forall U min_by?, min_of(& : T -> U) : U forall U min_of, min_of?(& : T -> U) : U | Nil forall U min_of?, minmax : Tuple(T, T) minmax, minmax? : Tuple(T | Nil, T | Nil) minmax?, minmax_by(& : T -> U) : Tuple(T, T) forall U minmax_by, minmax_by?(& : T -> U) : Tuple(T, T) | Tuple(Nil, Nil) forall U minmax_by?, minmax_of(& : T -> U) : Tuple(U, U) forall U minmax_of, minmax_of?(& : T -> U) : Tuple(U, U) | Tuple(Nil, Nil) forall U minmax_of?, none?(& : T -> ) : Bool
none?(pattern) : Bool
none? : Bool
none?
, one?(& : T -> ) : Bool
one?(pattern) : Bool
one? : Bool
one?
, partition(& : T -> ) : Tuple(Array(T), Array(T))
partition(type : U.class) forall U
partition
, present? : Bool present?, product(initial : Number)
product
product(initial : Number, & : T -> )
product(& : T -> _)
product
, reduce(memo, &)
reduce(&)
reduce
, reduce?(&) reduce?, reject(& : T -> )
reject(type : U.class) forall U
reject(pattern) : Array(T)
reject
, sample(n : Int, random : Random | Nil = nil) : Array(T)
sample(random : Random | Nil = nil) : T
sample
, select(& : T -> )
select(type : U.class) : Array(U) forall U
select(pattern) : Array(T)
select
, size : Int32 size, skip(count : Int) skip, skip_while(& : T -> ) : Array(T) skip_while, sum(initial)
sum
sum(initial, & : T -> )
sum(& : T -> )
sum
, take_while(& : T -> ) : Array(T) take_while, tally(hash)
tally : Hash(T, Int32)
tally
, tally_by(hash, &)
tally_by(&block : T -> U) : Hash(U, Int32) forall U
tally_by
, to_a : Array(T)
to_a(& : T -> U) : Array(U) forall U
to_a
, to_h
to_h(& : T -> Tuple(K, V)) forall K, V
to_h
, to_set : Set(T)
to_set(&block : T -> U) : Set(U) forall U
to_set
, zip(*others : Indexable | Iterable | Iterator, &)
zip(*others : Indexable | Iterable | Iterator)
zip
, zip?(*others : Indexable | Iterable | Iterator, &)
zip?(*others : Indexable | Iterable | Iterator)
zip?

Class methods inherited from module Enumerable(Bool)

element_type(x) element_type

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_cons_pair each_cons_pair, each_slice(count : Int, reuse = false) each_slice, each_step(n : Int)
each_step(n : Int, *, offset : Int)
each_step
, 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 : YAML::Any)
==(other) : Bool
==
, hash(hasher) hash, inspect(io : IO) : Nil inspect, pretty_print(pp) : Nil pretty_print, to_s(io : IO) : Nil to_s

Class methods inherited from struct Struct

pre_initialize(address : Pointer) : Nil pre_initialize

Instance methods inherited from struct Value

==(other : Log::Metadata::Value)
==(other : JSON::Any)
==(other : YAML::Any)
==(other)
==
, dup dup

Instance methods inherited from class Object

! : Bool !, !=(other) !=, !~(other) !~, ==(other) ==, ===(other : JSON::Any)
===(other : YAML::Any)
===(other)
===
, =~(other) =~, as(type : Class) as, as?(type : Class) as?, class class, dup dup, hash(hasher)
hash
hash
, in?(collection : Object) : Bool
in?(*values : Object) : Bool
in?
, inspect(io : IO) : Nil
inspect : String
inspect
, is_a?(type : Class) : Bool is_a?, itself itself, nil? : Bool nil?, not_nil!(message)
not_nil!
not_nil!
, pretty_inspect(width = 79, newline = "\n", indent = 0) : String pretty_inspect, pretty_print(pp : PrettyPrint) : Nil pretty_print, responds_to?(name : Symbol) : Bool responds_to?, tap(&) tap, to_json(io : IO) : Nil
to_json : String
to_json
, to_pretty_json(indent : String = " ") : String
to_pretty_json(io : IO, indent : String = " ") : Nil
to_pretty_json
, to_s(io : IO) : Nil
to_s : String
to_s
, to_yaml(io : IO) : Nil
to_yaml : String
to_yaml
, try(&) try, unsafe_as(type : T.class) forall T unsafe_as

Class methods inherited from class Object

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

Macros inherited from class Object

class_getter(*names, &block) class_getter, class_getter!(*names) class_getter!, class_getter?(*names, &block) class_getter?, class_property(*names, &block) class_property, class_property!(*names) class_property!, class_property?(*names, &block) class_property?, class_setter(*names) class_setter, def_clone def_clone, def_equals(*fields) def_equals, def_equals_and_hash(*fields) def_equals_and_hash, def_hash(*fields) def_hash, delegate(*methods, to object) delegate, forward_missing_to(delegate) forward_missing_to, getter(*names, &block) getter, getter!(*names) getter!, getter?(*names, &block) getter?, property(*names, &block) property, property!(*names) property!, property?(*names, &block) property?, setter(*names) setter

Constructor Detail

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

Creates a newBitArray ofsize bits.

initial optionally sets the starting value,true orfalse, for all bits in the array.


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

Creates a newBitArray ofsize bits and invokes the given block once for each index ofself, setting the bit at that index totrue 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.

RaisesIndexError 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.

RaisesIndexError 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 givenvalue at the givenindex. Returnsvalue.

Negative indices can be used to start counting from the end of the container. RaisesIndexError 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 #

Returnstrue if all of the elements of the collection are truthy.

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

def any? : Bool #

Returnstrue 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 thatitem 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 newBitArray with all of the same elements.


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

Replacescount or less (if there aren't enough) elements starting at the givenstart index withvalue. Returnsself.

Negative values ofstart count from the end of the container.

RaisesIndexError if thestart index is out of range.

RaisesArgumentError ifcount 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 inself with the givenvalue. Returnsself.

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

def hash(hasher) #

def includes?(obj : Bool) : Bool #

Returnstrue if the collection containsobj,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 ofobj inself starting from the givenoffset, ornil if the value is not inself.

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 ofself.

require "bit_array"

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

def invert : Nil #

Inverts all bits in the array. Falses becometrue 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 #

Returnstrue 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 #

Returnstrue 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 ofself. Returnsself.


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

Returns the index of the last appearance ofobj inself, or nil ifobj is not inself.

Ifoffset is given, the search starts from that index towards the first elements inself.

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 ofself to the leftn times. Returnsself.

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 ahash to count occurrences. The value corresponding to each element must be an integer. The number of occurrences is added to each value inhash, andhash 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 ofself.

require "bit_array"

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

def to_slice : Bytes #

Returns aBytes able to read and write bytes from a buffer. The slice will be long enough to hold all the bits groups in bytes despite theUInt32 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) #

Togglescount or less (if there aren't enough) bits starting at the given start index. Afalse bit becomes atrue bit, and vice versa.

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

RaisesIndexError ifindex is out of range. RaisesArgumentError ifcount 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 givenrange. Afalse bit becomes a true bit, and vice versa.

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

RaisesIndexError 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 givenindex. Afalse bit becomes atrue bit, and vice versa.

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

RaisesIndexError ifindex 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 givenindex, without doing any bounds check.

Indexable makes sure to invoke this method withindex in0...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 givenindex tovalue, without doing any bounds check.

Indexable::Mutable makes sure to invoke this method withindex 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.