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.crConstructors
-
.new(size : Int, initial : Bool = false)
Creates a new
BitArrayofsize bits. -
.new(size : Int, & : Int32 -> _)
Creates a new
BitArrayofsize bits and invokes the given block once for each index ofself, setting the bit at that index totrueif 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 givenvalue at the givenindex.
-
#all? : Bool
Returns
trueif all of the elements of the collection are truthy. -
#any? : Bool
Returns
trueif at least one of the collection's members is truthy. -
#count(item : Bool) : Int32
Returns the number of times thatitem is present in the bit array.
-
#dup
Returns a new
BitArraywith all of the same elements. -
#fill(value : Bool, start : Int, count : Int) : self
Replacescount or less (if there aren't enough) elements starting at the givenstart index withvalue.
-
#fill(value : Bool) : self
Replaces every element in
selfwith the givenvalue. - #hash(hasher)
-
#includes?(obj : Bool) : Bool
Returns
trueif the collection containsobj,falseotherwise. -
#index(obj : Bool, offset : Int = 0) : Int32 | Nil
Returns the index of the first appearance ofobj in
selfstarting from the givenoffset, ornilif 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
trueif all of the elements of the collection are falsey. -
#one? : Bool
Returns
trueif 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 ofobj in
self, ornilifobj is not inself. -
#rotate!(n : Int = 1) : self
Shifts all elements of
selfto the leftn 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
Bytesable to read and write bytes from a buffer. -
#toggle(start : Int, count : Int)
Togglescount or less (if there aren't enough) bits starting at the givenstart index.
-
#toggle(range : Range)
Toggles all bits that are within the givenrange.
-
#toggle(index) : Nil
Toggles the bit at the givenindex.
-
#unsafe_fetch(index : Int) : Bool
Returns the element at the givenindex, without doing any bounds check.
-
#unsafe_put(index : Int, value : Bool)
Sets the element at the givenindex tovalue, 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 | 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 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!, 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
Creates a newBitArray ofsize bits.
initial optionally sets the starting value,true orfalse, for all bits
in the array.
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
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[]
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]
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
Returnstrue if all of the elements of the collection are truthy.
[nil, true, 99].all? # => false
[15].all? # => true
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.
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
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]
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]
Returnstrue if the collection containsobj,false otherwise.
ba = BitArray.new(8, true)
ba.includes?(true) # => true
ba.includes?(false) # => false
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
Creates a string representation ofself.
require "bit_array"
ba = BitArray.new(5)
ba.to_s # => "BitArray[00000]"
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]
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?.
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
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
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]
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}
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 ofself.
require "bit_array"
ba = BitArray.new(5)
ba.to_s # => "BitArray[00000]"
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.
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]"
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]"
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
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.
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.