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.

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) : 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::DEFAULT) : 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
, first(&) first, hash(hasher) hash, index(object, offset : Int = 0)
index(offset : Int = 0, & : T -> ) index
, join(separator : String | Char | Number = "") : String join, last : T
last(&) last
, last? : T? 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
, sample(n : Int, random = Random::DEFAULT) : Array(T)
sample(random = Random::DEFAULT) sample
, size size, to_a : Array(T) 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_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, first(&)
first(count : Int) : Array(T)
first : T first
, first? : T? 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
, includes?(obj) : Bool includes?, 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 : T max, max? : T? max?, max_by(& : T -> U) : T forall U max_by, max_by?(& : T -> U) : T? forall U max_by?, max_of(& : T -> U) : U forall U max_of, max_of?(& : T -> U) : U? forall U max_of?, min : T min, min? : T? min?, min_by(& : T -> U) : T forall U min_by, min_by?(& : T -> U) : T? forall U min_by?, min_of(& : T -> U) : U forall U min_of, min_of?(& : T -> U) : U? forall U min_of?, minmax : Tuple(T, T) minmax, minmax? : Tuple(T?, T?) 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, 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::DEFAULT) : Array(T)
sample(random = Random::DEFAULT) : 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(T, Int32) tally, tally_by(& : T -> U) : Hash(U, Int32) forall U tally_by, to_a to_a, to_h
to_h(& : T -> Tuple(K, V)) forall K, V to_h
, to_set : Set(T) 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_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 : IO) : Nil to_s

Instance methods inherited from struct 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! 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, root : String)
from_json(string_or_io) from_json
, from_yaml(string_or_io : String | IO) from_yaml

Constructor Detail

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

Creates a new BitArray of size bits.

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

Instance Method Detail

def ==(other : BitArray)Source

def [](start : Int, count : Int) : BitArraySource

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) : BitArraySource

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) : BoolSource

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 dupSource

Returns a new BitArray with all of the same elements.

def hash(hasher)Source

def inspect(io : IO) : NilSource

Creates a string representation of self.

require "bit_array"

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

def invert : NilSource

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 rotate!(n : Int = 1) : selfSource

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 : Int32Source

The number of bits the BitArray stores

def to_s(io : IO) : NilSource

Creates a string representation of self.

require "bit_array"

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

def to_slice : BytesSource

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)Source

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)Source

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) : NilSource

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) : BoolSource

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)Source

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.

© 2012–2021 Manas Technology Solutions.
Licensed under the Apache License, Version 2.0.
https://crystal-lang.org/api/1.2.1/BitArray.html