#include <evo/bit_array.h>

Detailed Description

template<class T = ulong, class TSize = SizeT>
class evo::BitArrayT< T, TSize >

Dynamic bit array container with similar interface to Array and List.

Template Parameters

T	Chunk value type for storing bits, must be an unsigned integer type – default: ulong
TSize	Size integer type, must be unsigned – default: SizeT

Features

Bits are stored internally as array of chunk values
Bits are positioned left-to-right, as if from an array of bools
Chunk values are stored sequentially in contiguous memory – random access uses constant time
No memory allocated by new empty bit array
No extra capacity allocation, sharing, or slicing like List

C++11:

Range-based for loop
BitArray arr;
for (auto bit : arr) {
}
Initialization lists (uint32 list)
BitArray arr = {0xFFFFFFFF, 0x00000000};
Move semantics
- Caution: Moving a BitArray invalidates any BitArraySubetT referencing it

Note that this is not a full EvoContainer and has more limited iterators.

For subset see BitArraySubsetT
For default size types use BitArray and BitArraySubset

Constructors

Read Access

asconst()
size()
- null(), empty()
- shared()
cbegin(), cend()
- begin(), end()
getbit()
extractl(), extractr()
format()
data() const
- operator[](Size) const
- hash()
operator==()
- operator!=()

Modifiers

setbit()
data()
resize()
- resize_pow2()
- unshare()
setbit(), setbits()
- clearbit(), clearbits()
- togglebit(), togglebits()
store()
load()
clear()
set()
shiftl(), shiftr()

Example

#include <evo/bit_array.h>
#include <evo/io.h>
using namespace evo;
static Console& c = con();
int main() {
    // Create 10-bit array 
    BitArray array(10);
    // Set first and last bits
    array.setbit(0);
    array.setbit(9);
    // Store integer 7 (111 in binary) in bits 2-4
    array.store(2, 3, 7u);
    // Get a couple individual bits
    const bool bit0 = array.getbit(0);      // true
    const bool bit1 = array.getbit(1);      // false
    // Extract and print integer from bits 2-4: 111
    c.out << array.extractr<uint16>(2, 3) << NL;
    // Extract and print integer in hex from all 10 bits: 1011100001
    const uint16 val = array.extractr<uint16>(0, 10);
    c.out << FmtUInt16(val, fHEX) << NL;
    return 0;
}

Output:

7

2E1

Public Types
typedef void	EvoContainerType
	Identify Evo container type. More...

typedef IteratorFw< ThisType >::Const	Iter
	Iterator (const) - IteratorFw. More...

typedef TSize	Size
	Size integer type. More...

typedef BitArraySubsetT< ThisType >	Subset
	Subset type for this bit array type. More...

typedef BitArrayT< T, TSize >	ThisType
	This bit array type. More...

typedef T	Value
	Chunk value type for bits. More...

Public Member Functions
	BitArrayT ()
	Default constructor sets as null. More...

	BitArrayT (Size bitsize)
	Constructor create bit array. More...

	BitArrayT (const ThisType &src)
	Copy constructor. More...

	BitArrayT (const ThisType &src, Size pos, Size count=ALL)
	Copy from another bit array. More...

	BitArrayT (const Subset &subset, Size pos=0, Size count=ALL)
	Copy from subset. More...

	BitArrayT (std::initializer_list< uint32 > init)
	Sequence constructor that initializes bits from a list of uint32 values (C++11). More...

	BitArrayT (ThisType &&src)
	Move constructor (C++11). More...

	~BitArrayT ()
	Destructor. More...

const ThisType &	asconst () const
	Explicitly use a const reference to this. More...

Iter	begin () const
	Get iterator at first item (const). More...

Iter	cbegin () const
	Get iterator at first item (const). More...

Iter	cend () const
	Get iterator at end (const). More...

bool	checkall () const
	Check if all bits are set in bit array (const). More...

bool	checkany () const
	Check if any bits are set in bit array (const). More...

ThisType &	clear ()
	Clear by freeing all values. More...

bool	clearbit (Size pos)
	Clear bit at position in bit array. More...

Size	clearbits (Size pos=0, Size count=ALL) const
	Clear count bits at position in bit array. More...

Size	countbits (bool value=true) const
	Count number of bits set or cleared (const). More...

const Value *	data () const
	Get data pointer (const). More...

bool	empty () const
	Get whether empty. More...

Iter	end () const
	Get iterator at end (const). More...

template<class U = uint32>
U	extractl (Size pos=0, Size count=ALL) const
	Extract bits from bit array. More...

template<class U = uint32>
U	extractr (Size pos=0, Size count=ALL) const
	Extract bits from bit array. More...

template<class U >
bool	format (U &out, int base=fBIN)
	Format bits to stream or string using base. More...

bool	getbit (Size pos) const
	Get bit at position in bit array (const). More...

ulong	hash (ulong seed=0) const
	Get data hash value for whole bit array. More...

Size	load (const char *str, Size size, int base=2)
	Parse and load bits from numeric string. More...

bool	null () const
	Get whether null. More...

bool	operator!= (const ThisType &data) const
	Inequality operator. More...

ThisType &	operator= (ThisType &&src)
	Move assignment operator (C++11). More...

ThisType &	operator= (const ThisType &src)
	Assignment operator. More...

bool	operator== (const ThisType &data) const
	Equality operator. More...

bool	operator[] (Size pos) const
	Get bit at position in bit array (const). More...

ThisType &	resize (Size bitsize)
	Resize while preserving existing data (modifier). More...

ThisType &	resize_pow2 (Size bitsize)
	Resize as power of 2 while preserving existing data (modifier). More...

ThisType &	set ()
	Set as null and empty. More...

ThisType &	set (const ThisType &src)
	Set as copy of another bit array. More...

ThisType &	set (const Subset &src)
	Set as copy of bit array subset. More...

bool	setbit (Size pos, bool value=true)
	Set or clear bit at position in bit array. More...

Size	setbits (Size pos=0, Size count=ALL, bool value=true)
	Set or clear count bits at position in bit array. More...

ThisType &	setempty ()
	Set as empty but not null. More...

bool	shared () const
	Get whether shared (false). More...

ThisType &	shiftl (uint count)
	Shift all bits in bit bit array to the left. More...

ThisType &	shiftr (uint count)
	Shift all bits in bit bit array to the right. More...

Size	size () const
	Get bit size. More...

template<class U >
bool	store (Size pos, Size count, U value)
	Stores bits from value in bit array. More...

bool	togglebit (Size pos)
	Toggle bit at position in bit array. More...

Size	togglebits (Size pos=0, uint count=ALL)
	Toggle count bits at position in bit array. More...

ThisType &	unshare ()
	Make data unique – no-op. More...

Friends
template<class >
class	BitArraySubsetT

Member Typedef Documentation

◆ EvoContainerType

typedef void EvoContainerType

Identify Evo container type.

◆ Iter

typedef IteratorFw<ThisType>::Const Iter

Iterator (const) - IteratorFw.

◆ Size

typedef TSize Size

Size integer type.

◆ Subset

typedef BitArraySubsetT<ThisType> Subset

Subset type for this bit array type.

◆ ThisType

typedef BitArrayT<T,TSize> ThisType

This bit array type.

◆ Value

typedef T Value

Chunk value type for bits.

Constructor & Destructor Documentation

◆ BitArrayT() [1/7]

BitArrayT ( )

inline

Default constructor sets as null.

◆ BitArrayT() [2/7]

BitArrayT ( Size bitsize )

inline

Constructor create bit array.

Parameters

bitsize Bit size to initialize with

◆ BitArrayT() [3/7]

BitArrayT ( const ThisType & src )

inline

Copy constructor.

Parameters

src	Bit array to copy

◆ BitArrayT() [4/7]

BitArrayT	(	const ThisType &	src,
		Size	pos,
		Size	count = `ALL`
	)

inline

Copy from another bit array.

Parameters

src	Bit array subset to copy from
pos	Bit position in src to copy from, 0 for first bit on left, etc
count	Number of bits to copy from src, ALL for all from pos

◆ BitArrayT() [5/7]

BitArrayT	(	const Subset &	subset,
		Size	pos = `0`,
		Size	count = `ALL`
	)

inline

Copy from subset.

This will resize() to count or subset size (whichever is lower), and copy

Parameters

subset	Bit array subset to copy from
pos	Bit position in subset to copy from, 0 for first bit on left, etc
count	Number of bits to copy from subset, ALL for all from pos

◆ ~BitArrayT()

~BitArrayT ( )

inline

Destructor.

◆ BitArrayT() [6/7]

BitArrayT ( std::initializer_list< uint32 > init )

inline

Sequence constructor that initializes bits from a list of uint32 values (C++11).

Parameters

init	Initializer list, passed as comma-separated uint32 values in braces `{ }`

◆ BitArrayT() [7/7]

BitArrayT ( ThisType && src )

inline

Move constructor (C++11).

Parameters

src	Source to move

Member Function Documentation

◆ asconst()

const ThisType& asconst ( ) const

inline

Explicitly use a const reference to this.

This is useful to force using this as const without casting

Returns: This

◆ begin()

Iter begin ( ) const

inline

Get iterator at first item (const).

This allows compatibility with range-based for loops and other libraries, otherwise use container Iter directly

Returns: Iterator at first item, or at end position if empty

See also: end(), cbegin()

◆ cbegin()

Iter cbegin ( ) const

inline

Get iterator at first item (const).

This allows compatibility with range-based for loops and other libraries, otherwise use container Iter directly

Returns: Iterator at first item, or at end position if empty

See also: Iter, cend(), begin(), end()

◆ cend()

Iter cend ( ) const

inline

Get iterator at end (const).

This allows compatibility with range-based for loops and other libraries, otherwise use container Iter directly
This really just creates an empty iterator

Returns: Iterator at end position

See also: Iter, cbegin(), begin(), end()

◆ checkall()

bool checkall ( ) const

inline

Check if all bits are set in bit array (const).

This scans and checks that all bits are set, and stops early if a bit isn't set

Returns: Whether all bits are set

◆ checkany()

bool checkany ( ) const

inline

Check if any bits are set in bit array (const).

This scans and checks that at least 1 bit is set, and stops early if a bit is set

Returns: Whether at least 1 bit is set, false if all bits are cleared

◆ clear()

ThisType& clear ( )

inline

Clear by freeing all values.

Does not set as null – null status is unchanged

Returns: This

◆ clearbit()

bool clearbit ( Size pos )

inline

Clear bit at position in bit array.

Bits are counted left-to-right, as if from an array of bools

Parameters

pos	Bit position to clear, 0 for first bit on left, etc

Returns: Whether successful, false if pos out of bounds

See also: clearbits(), setbit(), togglebit(), getbit()

◆ clearbits()

Size clearbits	(	Size	pos = `0`,
		Size	count = `ALL`
	)		const

inline

Clear count bits at position in bit array.

Bits are counted left-to-right, as if from an array of bools

Parameters

pos	Bit position to clear, 0 for first bit on left, etc
count	Number of bits to clear from pos, ALL for all from pos

Returns: Number of bits modified, 0 if out of bounds or count=0

See also: clearbit(), setbits(), togglebits()

◆ countbits()

Size countbits ( bool value = true ) const

inline

Count number of bits set or cleared (const).

This scans through all bits and counts the number of bits set or cleared
For best performace see notes for bits_popcount()

Parameters

value Whether to count bits set, false to count cleared bits (not set)

Returns: Number of bits set or cleared

◆ data()

const Value* data ( ) const

inline

Get data pointer (const).

Caution: Modifying the size of the array will invalidate returned pointer

Returns: Data pointer as read-only, NULL/invalid if empty

◆ empty()

bool empty ( ) const

inline

Get whether empty.

Empty when size() is 0

Returns: Whether empty

◆ end()

Iter end ( ) const

inline

Get iterator at end (const).

This allows compatibility with range-based for loops and other libraries, otherwise use container Iter directly
This really just creates an empty iterator

Returns: Iterator at end position

See also: begin(), cend()

◆ extractl()

U extractl	(	Size	pos = `0`,
		Size	count = `ALL`
	)		const

inline

Extract bits from bit array.

Bits are stored in chunks but are extracted left-to-right, as if from an array of bools
- This works the same regardless of chunk size, or system endianness
Extracted bits are left-aligned in the return value, and the left-most bit is the "first" bit (as if from an array of bools)
- Example with 3 extracted bits 111 returned as uint8: 11100000

Template Parameters

U	Return type for extracted bits, must be unsigned (uint, ulong, uint32, etc) – defaults to `ulong` in C++11 or newer

Parameters

pos	Bit position to extract from, 0 for first bit on left, etc
count	Number of bits to extract, truncated if larger than bitsize or return value

Returns: Extracted bits, aligned to the left

See also: extractr(), get(), store()

◆ extractr()

U extractr	(	Size	pos = `0`,
		Size	count = `ALL`
	)		const

inline

Extract bits from bit array.

Bits are stored in chunks but are extracted left-to-right, as if from an array of bools
- This works the same regardless of chunk size, or system endianness
Extracted bits returned are right-aligned so the result is an integer
- Example with 3 extracted bits 111 returned as uint8: 00000111 or 7 in decimal
A count larger than bits in return type will be truncated – this should be avoided as it may not be easy to tell how many bits were truncated
- For example, if you pass count=9 with return type uint8 then this uses count=8
Otherwise count may go out of bit array bounds without truncation – bits from out of bounds are set to 0 and still are right-aligned according to count

Template Parameters

U	Return type for extracted bits, must be unsigned (uint, ulong, uint32, etc) – defaults to `ulong` in C++11 or newer

Parameters

pos	Bit position to extract from, 0 for first bit on left, etc
count	Number of bits to extract, ALL for num bits in return type, truncated if larger than bits in return type

Returns: Extracted bits, aligned to the right

See also: extractl(), get(), store()

◆ format()

bool format	(	U &	out,
		int	base = `fBIN`
	)

inline

Format bits to stream or string using base.

If there aren't enough bits for the last digit then zero-bits are padded on the right to finish, ex: 1 set bit formatted as hex is 8, or 5 set bits formatted as hex is F8
- Bits are ordered left-to-right, as if from an array of bools, so this padding is added at the end
Call load() to load formatted bits (must use same base)

Template Parameters

U	Output string/stream type, deduced from arguments

Parameters

out	Output string or stream (or associated Format object) to format to
base	Base to format as, must be a power of 2 between 2-32 (inclusive), add 100 for lowercase letters, or use enum: fBIN for binary fOCT for octal fHEX for hexidecimal fHEXL for lowercase hexadecimal

Returns: Whether successful, false on stream error or if base is invalid

◆ getbit()

bool getbit ( Size pos ) const

inline

Get bit at position in bit array (const).

Bits are counted left-to-right, as if from an array of bools

Parameters

pos	Bit position to get, 0 for first bit on left, etc

Returns: Bit value, false if pos is out of bounds

See also: setbit(), clearbit(), togglebit()

◆ hash()

ulong hash ( ulong seed = 0 ) const

inline

Get data hash value for whole bit array.

Parameters

seed	Seed value for hashing multiple values, 0 if none

Returns: Hash value

◆ load()

Size load	(	const char *	str,
		Size	size,
		int	base = `2`
	)

inline

Parse and load bits from numeric string.

This resizes the bit array if needed to match the input string, current data is lost
Leading and trailing whitespace (spaces and tabs) in input string are ignored
This stops and returns 0 on invalid base or if an invalid digit is found
On error any bit values should be considered uninitialized
Call format() to save/format bits

Parameters

str	Pointer to string to load
size	String length to load
base	String number base to use: 2 for binary, 8 for octal, 16 for hex – must be a power of 2 in the range 2-32 (inclusive)

Returns: Number of bits loaded, 0 on error

◆ null()

bool null ( ) const

inline

Get whether null.

Always empty when null

Returns: Whether null

◆ operator!=()

bool operator!= ( const ThisType & data ) const

inline

Inequality operator.

Parameters

data	Data to compare to

Returns: Whether inequal

◆ operator=() [1/2]

ThisType& operator= ( ThisType && src )

inline

Move assignment operator (C++11).

Parameters

src	Source to move

Returns: This

◆ operator=() [2/2]

ThisType& operator= ( const ThisType & src )

inline

Assignment operator.

Parameters

src	Bit array to copy

Returns: This

◆ operator==()

bool operator== ( const ThisType & data ) const

inline

Equality operator.

Parameters

data	Data to compare to

Returns: Whether equal

◆ operator[]()

bool operator[] ( Size pos ) const

inline

Get bit at position in bit array (const).

Bits are counted left-to-right, as if from an array of bools

Parameters

pos	Bit position to get, 0 for first bit on left, etc

Returns: Bit value, false if pos is out of bounds

See also: getbit(), setbit()

◆ resize()

ThisType& resize ( Size bitsize )

inline

Resize while preserving existing data (modifier).

Parameters

bitsize New bit size to use

Returns: This

◆ resize_pow2()

ThisType& resize_pow2 ( Size bitsize )

inline

Resize as power of 2 while preserving existing data (modifier).

This makes sure size is always a power of 2, or 0 if empty
If desired size isn't a power of 2, this increases it to the next power of 2

Parameters

bitsize New size to use

Returns: This

◆ set() [1/3]

ThisType& set ( )

inline

Set as null and empty.

Returns: This

◆ set() [2/3]

ThisType& set ( const ThisType & src )

inline

Set as copy of another bit array.

Parameters

src	Data to copy

Returns: This

◆ set() [3/3]

ThisType& set ( const Subset & src )

inline

Set as copy of bit array subset.

This invalidates any existing subsets referrencing to this bit array

Parameters

src	Data to copy, which may reference this same BitArray

Returns: This

◆ setbit()

bool setbit	(	Size	pos,
		bool	value = `true`
	)

inline

Set or clear bit at position in bit array.

Bits are counted left-to-right, as if from an array of bools

Parameters

pos	Bit position to set, 0 for first bit on left, etc
value	Bit value to set, true to set bit, false to clear bit

Returns: Whether successful, false if pos out of bounds

See also: setbits(), clearbit(), togglebit(), getbit()

◆ setbits()

Size setbits	(	Size	pos = `0`,
		Size	count = `ALL`,
		bool	value = `true`
	)

inline

Set or clear count bits at position in bit array.

Bits are counted left-to-right, as if from an array of bools

Parameters

pos	Bit position to set, 0 for first bit on left, etc
count	Number of bits to set from pos, ALL for all from pos
value	Bit value to set, true to set bits, false to clear bits

Returns: Number of bits modified, 0 if out of bounds or count=0

See also: setbit(), clearbits(), togglebits()

◆ setempty()

ThisType& setempty ( )

inline

Set as empty but not null.

Returns: This

◆ shared()

bool shared ( ) const

inline

Get whether shared (false).

This doesn't support sharing so always returns false

Returns: Whether shared (always false)

◆ shiftl()

ThisType& shiftl ( uint count )

inline

Shift all bits in bit bit array to the left.

New vacated bits on the right are zero-filled

Parameters

count Count to shift

◆ shiftr()

ThisType& shiftr ( uint count )

inline

Shift all bits in bit bit array to the right.

New vacated bits on the left are zero-filled

Parameters

count Count to shift

◆ size()

Size size ( ) const

inline

Get bit size.

Returns: Size as number of bits stored

◆ store()

bool store	(	Size	pos,
		Size	count,
		U	value
	)

inline

Stores bits from value in bit array.

Bits are stored in chunks but are positioned left-to-right, as if in an array of bools
- This works the same regardless of chunk size, or system endianness
Value bits are taken from the right so integers can be stored
- Example value 00000111 with count=3 would store 111 (3 right-most bits) or 7 in decimal
Bits stored after end of bit array are truncated and lost
Caution: If count exceeds value size, count is capped at that size – only bits from value are stored

Template Parameters

U	Value type to store, signed value is treated as unsigned – inferred from `value` param

Parameters

pos	Bit position to store at, 0 for first bit on left, etc
count	Number of bits to store from value
value	Value to store (`count` right-most bits are stored)

Returns: Whether successful, false if pos is out of bounds

See also: setbit(), extract()

◆ togglebit()

bool togglebit ( Size pos )

inline

Toggle bit at position in bit array.

Bits are counted left-to-right, as if from an array of bools

Parameters

pos	Bit position to toggle, 0 for first bit on left, etc

Returns: Whether successful, false if pos out of bounds

See also: togglebits(), setbit(), clearbit(), getbit()

◆ togglebits()

Size togglebits	(	Size	pos = `0`,
		uint	count = `ALL`
	)

inline

Toggle count bits at position in bit array.

Bits are counted left-to-right, as if from an array of bools

Parameters

pos	Bit position to toggle, 0 for first bit on left, etc
count	Number of bits to toggle from pos, ALL for all from pos

Returns: Number of bits modified, 0 if out of bounds or count=0

See also: togglebit(), setbits(), clearbits()

◆ unshare()

ThisType& unshare ( )

inline

Make data unique – no-op.

BitArray doesn't support sharing so this is a no-op

Returns: This

Friends And Related Function Documentation

◆ BitArraySubsetT

friend class BitArraySubsetT

friend

The documentation for this class was generated from the following file:

evo/bit_array.h

Detailed Description

template<class T = ulong, class TSize = SizeT> class evo::BitArrayT< T, TSize >

Public Types

Public Member Functions

Friends

Member Typedef Documentation

◆ EvoContainerType

◆ Iter

◆ Size

◆ Subset

◆ ThisType

◆ Value

Constructor & Destructor Documentation

◆ BitArrayT() [1/7]

◆ BitArrayT() [2/7]

◆ BitArrayT() [3/7]

◆ BitArrayT() [4/7]

◆ BitArrayT() [5/7]

◆ ~BitArrayT()

◆ BitArrayT() [6/7]

◆ BitArrayT() [7/7]

Member Function Documentation

◆ asconst()

◆ begin()

◆ cbegin()

◆ cend()

◆ checkall()

◆ checkany()

◆ clear()

◆ clearbit()

◆ clearbits()

◆ countbits()

◆ data()

◆ empty()

◆ end()

◆ extractl()

◆ extractr()

◆ format()

◆ getbit()

◆ hash()

◆ load()

◆ null()

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator[]()

◆ resize()

◆ resize_pow2()

◆ set() [1/3]

◆ set() [2/3]

◆ set() [3/3]

◆ setbit()

◆ setbits()

◆ setempty()

◆ shared()

◆ shiftl()

◆ shiftr()

◆ size()

◆ store()

◆ togglebit()

◆ togglebits()

◆ unshare()

Friends And Related Function Documentation

◆ BitArraySubsetT

template<class T = ulong, class TSize = SizeT>
class evo::BitArrayT< T, TSize >