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
Included Modules
Defined in:
bit_array.crConstructors
-
.new(size : Int, initial : Bool = false)
Creates a new
BitArray
of size bits. -
.new(size : Int, & : Int32 -> _)
Creates a new
BitArray
of size bits and invokes the given block once for each index ofself
, setting the bit at that index totrue
if the block is truthy.
Instance Method Summary
- #==(other : BitArray)
-
#[](start : Int, count : Int) : BitArray
Returns count or less (if there aren't enough) elements starting at the given start index.
-
#[](range : Range) : BitArray
Returns all elements that are within the given range.
-
#[]=(index : Int, value : Bool) : Bool
Sets the given value at the given index.
-
#all? : Bool
Returns
true
if all of the elements of the collection are truthy. -
#any? : Bool
Returns
true
if at least one of the collection's members is truthy. -
#count(item : Bool) : Int32
Returns the number of times that item is present in the bit array.
-
#dup
Returns a new
BitArray
with all of the same elements. -
#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.
-
#fill(value : Bool) : self
Replaces every element in
self
with the given value. - #hash(hasher)
-
#includes?(obj : Bool) : Bool
Returns
true
if the collection contains obj,false
otherwise. -
#index(obj : Bool, offset : Int = 0) : Int32 | Nil
Returns the index of the first appearance of obj in
self
starting from the given offset, ornil
if the value is not inself
. -
#inspect(io : IO) : Nil
Creates a string representation of
self
. -
#invert : Nil
Inverts all bits in the array.
-
#none? : Bool
Returns
true
if all of the elements of the collection are falsey. -
#one? : Bool
Returns
true
if only one element in this enumerable is truthy. -
#reverse! : self
Reverses in-place all the elements of
self
. -
#rindex(obj : Bool, offset : Int = size - 1) : Int32 | Nil
Returns the index of the last appearance of obj in
self
, ornil
if obj is not inself
. -
#rotate!(n : Int = 1) : self
Shifts all elements of
self
to the left n times. -
#size : Int32
The number of bits the BitArray stores
-
#tally(hash)
Tallies the collection.
-
#tally : Hash(Bool, Int32)
Tallies the collection.
-
#to_s(io : IO) : Nil
Creates a string representation of
self
. -
#to_slice : Bytes
Returns a
Bytes
able to read and write bytes from a buffer. -
#toggle(start : Int, count : Int)
Toggles count or less (if there aren't enough) bits starting at the given start index.
-
#toggle(range : Range)
Toggles all bits that are within the given range.
-
#toggle(index) : Nil
Toggles the bit at the given index.
-
#unsafe_fetch(index : Int) : Bool
Returns the element at the given index, without doing any bounds check.
-
#unsafe_put(index : Int, value : Bool)
Sets the element at the given index to value, without doing any bounds check.
Instance methods inherited from module Indexable::Mutable(Bool)
[]=(index : Int, value : T) : T
[]=,
fill(value : T, start : Int, count : Int) : selffill(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 = 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, 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 = Random::DEFAULT) : Array(T)
sample(random : Random = Random::DEFAULT) 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 Uaccumulate : 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!, 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 = Random::DEFAULT) : Array(T)
sample(random : 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)
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) : 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!(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, root : String)from_json(string_or_io) from_json, from_yaml(string_or_io : String | IO) from_yaml
Constructor Detail
Creates a new BitArray
of size bits.
initial optionally sets the starting value, true
or false
, for all bits
in the array.
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
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[]
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]
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
Returns true
if all of the elements of the collection are truthy.
[nil, true, 99].all? # => false
[15].all? # => true
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.
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
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]
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]
Returns true
if the collection contains obj, false
otherwise.
ba = BitArray.new(8, true)
ba.includes?(true) # => true
ba.includes?(false) # => false
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
Creates a string representation of self
.
require "bit_array"
ba = BitArray.new(5)
ba.to_s # => "BitArray[00000]"
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]
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?
.
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
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
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]
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}
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}
Creates a string representation of self
.
require "bit_array"
ba = BitArray.new(5)
ba.to_s # => "BitArray[00000]"
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.
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]"
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]"
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
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.
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.