This class is a compressed bitmap. More...

#include <ewah.h>

Public Types
enum	{ RESERVEMEMORY = true }

enum	{ wordinbits = sizeof(uword) * 8 }

typedef EWAHBoolArraySetBitForwardIterator< uword >	const_iterator

Public Member Functions
void	trim ()
	Recover wasted memory usage.

bool	get (const size_t pos) const
	Query the value of bit i.

bool	empty () const
	Returns true if no bit is set.

bool	set (size_t i)
	Set the ith bit to true (starting at zero).

	operator std::string () const
	Transform into a string that presents a list of set bits.

void	makeSameSize (EWAHBoolArray &a)
	Make sure the two bitmaps have the same size (padding with zeroes if necessary).

const_iterator	begin () const
	Returns an iterator that can be used to access the position of the set bits.

const_iterator &	end () const
	Basically a bogus iterator that can be used together with begin() for constructions such as for(EWAHBoolArray<uword>::iterator i = b.begin(); i!=b.end(); ++i) {}.

std::vector< size_t >	toArray () const
	Retrieve the set bits.

void	logicaland (const EWAHBoolArray &a, EWAHBoolArray &container) const
	computes the logical and with another compressed bitmap answer goes into container Running time complexity is proportional to the sum of the compressed bitmap sizes.

EWAHBoolArray	logicaland (const EWAHBoolArray &a) const
	computes the logical and with another compressed bitmap Return the answer Running time complexity is proportional to the sum of the compressed bitmap sizes.

EWAHBoolArray	operator& (const EWAHBoolArray &a) const
	calls logicaland

void	logicalandnot (const EWAHBoolArray &a, EWAHBoolArray &container) const
	computes the logical and with another compressed bitmap answer goes into container Running time complexity is proportional to the sum of the compressed bitmap sizes.

EWAHBoolArray	operator- (const EWAHBoolArray &a) const
	calls logicalandnot

EWAHBoolArray	logicalandnot (const EWAHBoolArray &a) const
	computes the logical and not with another compressed bitmap Return the answer Running time complexity is proportional to the sum of the compressed bitmap sizes.

bool	intersects (const EWAHBoolArray &a) const
	tests whether the bitmaps "intersect" (have at least one 1-bit at the same position).

void	logicalor (const EWAHBoolArray &a, EWAHBoolArray &container) const
	computes the logical or with another compressed bitmap answer goes into container Running time complexity is proportional to the sum of the compressed bitmap sizes.

size_t	logicalorcount (const EWAHBoolArray &a) const
	computes the size (in number of set bits) of the logical or with another compressed bitmap Running time complexity is proportional to the sum of the compressed bitmap sizes.

size_t	logicalandcount (const EWAHBoolArray &a) const
	computes the size (in number of set bits) of the logical and with another compressed bitmap Running time complexity is proportional to the sum of the compressed bitmap sizes.

size_t	logicalandnotcount (const EWAHBoolArray &a) const
	computes the size (in number of set bits) of the logical and not with another compressed bitmap Running time complexity is proportional to the sum of the compressed bitmap sizes.

size_t	logicalxorcount (const EWAHBoolArray &a) const
	computes the size (in number of set bits) of the logical xor with another compressed bitmap Running time complexity is proportional to the sum of the compressed bitmap sizes.

EWAHBoolArray	logicalor (const EWAHBoolArray &a) const
	computes the logical or with another compressed bitmap Return the answer Running time complexity is proportional to the sum of the compressed bitmap sizes.

EWAHBoolArray	operator\| (const EWAHBoolArray &a) const
	calls logicalor

void	logicalxor (const EWAHBoolArray &a, EWAHBoolArray &container) const
	computes the logical xor with another compressed bitmap answer goes into container Running time complexity is proportional to the sum of the compressed bitmap sizes.

EWAHBoolArray	logicalxor (const EWAHBoolArray &a) const
	computes the logical xor with another compressed bitmap Return the answer Running time complexity is proportional to the sum of the compressed bitmap sizes.

EWAHBoolArray	operator^ (const EWAHBoolArray &a) const
	calls logicalxor

void	reset ()
	clear the content of the bitmap.

size_t	addWord (const uword newdata, const uint32_t bitsthatmatter=8 *sizeof(uword))
	convenience method.

void	printout (std::ostream &o=std::cout)

void	debugprintout () const
	Prints a verbose description of the content of the compressed bitmap.

size_t	sizeInBits () const
	Return the size in bits of this bitmap (this refers to the uncompressed size in bits).

size_t	sizeInBytes () const
	Return the size of the buffer in bytes.

size_t	addStreamOfEmptyWords (const bool v, size_t number)
	same as addEmptyWord, but you can do several in one shot! returns the number of words added (storage cost increase)

size_t	addStreamOfDirtyWords (const uword *v, const size_t number)
	add a stream of dirty words, returns the number of words added (storage cost increase)

size_t	addStreamOfNegatedDirtyWords (const uword *v, const size_t number)
	add a stream of dirty words, each one negated, returns the number of words added (storage cost increase)

size_t	padWithZeroes (const size_t totalbits)
	make sure the size of the array is totalbits bits by padding with zeroes.

size_t	sizeOnDisk (const bool savesizeinbits=true) const
	Compute the size on disk assuming that it was saved using the method "write".

size_t	write (std::ostream &out, const bool savesizeinbits=true) const
	Save this bitmap to a stream.

size_t	write (char *out, size_t capacity, const bool savesizeinbits=true) const
	same as write(std::ostream...), except that you provide a char pointer and a "capacity" (in bytes).

void	writeBuffer (std::ostream &out) const
	This only writes the content of the buffer (see write()) method.

size_t	bufferSize () const
	size (in words) of the underlying STL vector.

size_t	read (std::istream &in, const bool savesizeinbits=true)
	this is the counterpart to the write method.

size_t	read (const char *in, size_t capacity, const bool savesizeinbits=true)
	same as read(std::istream...), except that you provide a char pointer and a "capacity" (in bytes).

void	readBuffer (std::istream &in, const size_t buffersize)
	read the buffer from a stream, see method writeBuffer.

bool	operator== (const EWAHBoolArray &x) const
	We define two EWAHBoolArray as being equal if they have the same set bits.

bool	operator!= (const EWAHBoolArray &x) const
	We define two EWAHBoolArray as being different if they do not have the same set bits.

bool	operator== (const BoolArray< uword > &x) const

bool	operator!= (const BoolArray< uword > &x) const

EWAHBoolArrayIterator< uword >	uncompress () const
	Iterate over the uncompressed words.

EWAHBoolArrayRawIterator< uword >	raw_iterator () const
	To iterate over the compressed data.

void	append (const EWAHBoolArray &x)
	Appends the content of some other compressed bitmap at the end of the current bitmap.

BitmapStatistics	computeStatistics () const
	For research purposes.

BoolArray< uword >	toBoolArray () const
	For convenience, this fully uncompresses the bitmap.

template<class container >
void	appendSetBits (container &out, const size_t offset=0) const
	Convert to a list of positions of "set" bits.

std::vector< size_t >	toVector () const
	Returns a vector containing the position of the set bits in increasing order.

size_t	numberOfOnes () const
	Returns the number of bits set to the value 1.

void	swap (EWAHBoolArray &x)
	Swap the content of this bitmap with another bitmap.

const std::vector< uword > &	getBuffer () const

	EWAHBoolArray (const EWAHBoolArray &other)
	Please don't copy your bitmaps! The running time complexity of a copy is the size of the compressed bitmap.

EWAHBoolArray &	operator= (const EWAHBoolArray &x)
	Copies the content of one bitmap onto another.

	EWAHBoolArray (EWAHBoolArray &&other)
	Move constructor.

EWAHBoolArray &	operator= (EWAHBoolArray &&x)
	Move assignment operator.

void	expensive_copy (const EWAHBoolArray &x)
	This is equivalent to the operator =.

void	logicalnot (EWAHBoolArray &x) const
	Write the logical not of this bitmap in the provided container.

EWAHBoolArray< uword >	logicalnot () const
	Write the logical not of this bitmap in the provided container.

void	inplace_logicalnot ()
	Apply the logical not operation on this bitmap.

void	setSizeInBits (const size_t size)
	set size in bits.

void	fastaddStreamOfEmptyWords (const bool v, size_t number)
	Like addStreamOfEmptyWords but addStreamOfEmptyWords but does not return the cost increase, does not update sizeinbits.

void	fastaddStreamOfDirtyWords (const uword *v, const size_t number)
	LikeaddStreamOfDirtyWords but does not return the cost increse, does not update sizeinbits.

Static Public Member Functions
static EWAHBoolArray	bitmapOf (size_t n,...)

Detailed Description

template<class uword>
class ewah::EWAHBoolArray< uword >

This class is a compressed bitmap.

This is where compression happens. The underlying data structure is an STL vector.

Definition at line 197 of file runninglengthword.h.

Member Typedef Documentation

◆ const_iterator

template<class uword >

EWAHBoolArraySetBitForwardIterator<uword> ewah::EWAHBoolArray< uword >::const_iterator

Definition at line 156 of file ewah.h.

Member Enumeration Documentation

◆ anonymous enum

template<class uword >

anonymous enum

Definition at line 154 of file ewah.h.

◆ anonymous enum

template<class uword >

anonymous enum

Definition at line 581 of file ewah.h.

Constructor & Destructor Documentation

◆ EWAHBoolArray() [1/3]

template<class uword >

ewah::EWAHBoolArray< uword >::EWAHBoolArray ( )

inline

Definition at line 32 of file ewah.h.

◆ EWAHBoolArray() [2/3]

template<class uword >

ewah::EWAHBoolArray< uword >::EWAHBoolArray ( const EWAHBoolArray< uword > & other )

inline

Please don't copy your bitmaps! The running time complexity of a copy is the size of the compressed bitmap.

Definition at line 587 of file ewah.h.

◆ EWAHBoolArray() [3/3]

template<class uword >

ewah::EWAHBoolArray< uword >::EWAHBoolArray ( EWAHBoolArray< uword > && other )

inline

Move constructor.

Definition at line 606 of file ewah.h.

Member Function Documentation

◆ addStreamOfDirtyWords()

template<class uword >

size_t ewah::EWAHBoolArray< uword >::addStreamOfDirtyWords	(	const uword *	v,
		const size_t	number )

add a stream of dirty words, returns the number of words added (storage cost increase)

Definition at line 1002 of file ewah-inl.h.

◆ addStreamOfEmptyWords()

template<class uword >

size_t ewah::EWAHBoolArray< uword >::addStreamOfEmptyWords	(	const bool	v,
		size_t	number )

same as addEmptyWord, but you can do several in one shot! returns the number of words added (storage cost increase)

Definition at line 898 of file ewah-inl.h.

◆ addStreamOfNegatedDirtyWords()

template<class uword >

size_t ewah::EWAHBoolArray< uword >::addStreamOfNegatedDirtyWords	(	const uword *	v,
		const size_t	number )

add a stream of dirty words, each one negated, returns the number of words added (storage cost increase)

Definition at line 1069 of file ewah-inl.h.

◆ addWord()

template<class uword >

size_t ewah::EWAHBoolArray< uword >::addWord	(	const uword	newdata,
		const uint32_t	bitsthatmatter = 8 * sizeof(uword) )

inline

convenience method.

returns the number of words added (storage cost increase)

Definition at line 475 of file ewah-inl.h.

◆ append()

template<class uword >

void ewah::EWAHBoolArray< uword >::append ( const EWAHBoolArray< uword > & x )

Appends the content of some other compressed bitmap at the end of the current bitmap.

Definition at line 777 of file ewah-inl.h.

◆ appendSetBits()

template<class uword >

template<class container >

void ewah::EWAHBoolArray< uword >::appendSetBits	(	container &	out,
		const size_t	offset = 0 ) const

Convert to a list of positions of "set" bits.

The recommended container is vector<size_t>.

◆ begin()

template<class uword >

const_iterator ewah::EWAHBoolArray< uword >::begin ( ) const

inline

Returns an iterator that can be used to access the position of the set bits.

The running time complexity of a full scan is proportional to the number of set bits: be aware that if you have long strings of 1s, this can be very inefficient.

It can be much faster to use the toArray method if you want to retrieve the set bits.

Definition at line 168 of file ewah.h.

◆ bitmapOf()

template<class uword >

static EWAHBoolArray ewah::EWAHBoolArray< uword >::bitmapOf	(	size_t	n,
			... )

inlinestatic

Definition at line 34 of file ewah.h.

◆ bufferSize()

template<class uword >

size_t ewah::EWAHBoolArray< uword >::bufferSize ( ) const

inline

size (in words) of the underlying STL vector.

Definition at line 470 of file ewah.h.

◆ computeStatistics()

template<class uword >

BitmapStatistics ewah::EWAHBoolArray< uword >::computeStatistics ( ) const

For research purposes.

This computes the number of dirty words and the number of compressed words.

Definition at line 1635 of file ewah-inl.h.

◆ debugprintout()

template<class uword >

void ewah::EWAHBoolArray< uword >::debugprintout ( ) const

Prints a verbose description of the content of the compressed bitmap.

Definition at line 1651 of file ewah-inl.h.

◆ empty()

template<class uword >

bool ewah::EWAHBoolArray< uword >::empty ( ) const

inline

Returns true if no bit is set.

Definition at line 81 of file ewah.h.

◆ end()

template<class uword >

const_iterator & ewah::EWAHBoolArray< uword >::end ( ) const

inline

Basically a bogus iterator that can be used together with begin() for constructions such as for(EWAHBoolArray<uword>::iterator i = b.begin(); i!=b.end(); ++i) {}.

Definition at line 177 of file ewah.h.

◆ expensive_copy()

template<class uword >

void ewah::EWAHBoolArray< uword >::expensive_copy ( const EWAHBoolArray< uword > & x )

inline

This is equivalent to the operator =.

It is used to keep in mind that assignment can be expensive.

if you don't care to copy the bitmap (performance-wise), use this!

Definition at line 626 of file ewah.h.

◆ fastaddStreamOfDirtyWords()

template<class uword >

void ewah::EWAHBoolArray< uword >::fastaddStreamOfDirtyWords	(	const uword *	v,
		const size_t	number )

inline

LikeaddStreamOfDirtyWords but does not return the cost increse, does not update sizeinbits.

Definition at line 1036 of file ewah-inl.h.

◆ fastaddStreamOfEmptyWords()

template<class uword >

void ewah::EWAHBoolArray< uword >::fastaddStreamOfEmptyWords	(	const bool	v,
		size_t	number )

inline

Like addStreamOfEmptyWords but addStreamOfEmptyWords but does not return the cost increase, does not update sizeinbits.

Definition at line 953 of file ewah-inl.h.

◆ get()

template<class uword >

bool ewah::EWAHBoolArray< uword >::get ( const size_t pos ) const

inline

Query the value of bit i.

This runs in time proportional to the size of the bitmap. This is not meant to be use in a performance-sensitive context.

(This implementation is based on zhenjl's Go version of JavaEWAH.)

Definition at line 58 of file ewah.h.

◆ getBuffer()

template<class uword >

const std::vector< uword > & ewah::EWAHBoolArray< uword >::getBuffer ( ) const

inline

Definition at line 579 of file ewah.h.

◆ inplace_logicalnot()

template<class uword >

void ewah::EWAHBoolArray< uword >::inplace_logicalnot ( )

Apply the logical not operation on this bitmap.

Running time complexity is proportional to the compressed size of the bitmap. The current bitmap is not modified.

This function takes into account the sizeInBits value. You may need to call "padWithZeroes" to adjust the sizeInBits.

Definition at line 294 of file ewah-inl.h.

◆ intersects()

template<class uword >

bool ewah::EWAHBoolArray< uword >::intersects ( const EWAHBoolArray< uword > & a ) const

tests whether the bitmaps "intersect" (have at least one 1-bit at the same position).

This function does not modify the existing bitmaps. It is faster than calling logicaland.

Definition at line 1594 of file ewah-inl.h.

◆ logicaland() [1/2]

template<class uword >

EWAHBoolArray ewah::EWAHBoolArray< uword >::logicaland ( const EWAHBoolArray< uword > & a ) const

inline

computes the logical and with another compressed bitmap Return the answer Running time complexity is proportional to the sum of the compressed bitmap sizes.

The sizeInBits() of the result is equal to the maximum that of the current bitmap's sizeInBits() and that of a.sizeInBits().

Definition at line 207 of file ewah.h.

◆ logicaland() [2/2]

template<class uword >

void ewah::EWAHBoolArray< uword >::logicaland	(	const EWAHBoolArray< uword > &	a,
		EWAHBoolArray< uword > &	container ) const

computes the logical and with another compressed bitmap answer goes into container Running time complexity is proportional to the sum of the compressed bitmap sizes.

The sizeInBits() of the result is equal to the maximum that of the current bitmap's sizeInBits() and that of a.sizeInBits().

Definition at line 1381 of file ewah-inl.h.

◆ logicalandcount()

template<class uword >

size_t ewah::EWAHBoolArray< uword >::logicalandcount ( const EWAHBoolArray< uword > & a ) const

computes the size (in number of set bits) of the logical and with another compressed bitmap Running time complexity is proportional to the sum of the compressed bitmap sizes.

Definition at line 1555 of file ewah-inl.h.

◆ logicalandnot() [1/2]

template<class uword >

EWAHBoolArray ewah::EWAHBoolArray< uword >::logicalandnot ( const EWAHBoolArray< uword > & a ) const

inline

computes the logical and not with another compressed bitmap Return the answer Running time complexity is proportional to the sum of the compressed bitmap sizes.

The sizeInBits() of the result should be equal to that of the current bitmap irrespective of a.sizeInBits().

Definition at line 249 of file ewah.h.

◆ logicalandnot() [2/2]

template<class uword >

void ewah::EWAHBoolArray< uword >::logicalandnot	(	const EWAHBoolArray< uword > &	a,
		EWAHBoolArray< uword > &	container ) const

computes the logical and with another compressed bitmap answer goes into container Running time complexity is proportional to the sum of the compressed bitmap sizes.

The sizeInBits() of the result should be equal to that of the current bitmap irrespective of a.sizeInBits().

Definition at line 1436 of file ewah-inl.h.

◆ logicalandnotcount()

template<class uword >

size_t ewah::EWAHBoolArray< uword >::logicalandnotcount ( const EWAHBoolArray< uword > & a ) const

computes the size (in number of set bits) of the logical and not with another compressed bitmap Running time complexity is proportional to the sum of the compressed bitmap sizes.

Definition at line 1505 of file ewah-inl.h.

◆ logicalnot() [1/2]

template<class uword >

EWAHBoolArray< uword > ewah::EWAHBoolArray< uword >::logicalnot ( ) const

inline

Write the logical not of this bitmap in the provided container.

This function takes into account the sizeInBits value. You may need to call "padWithZeroes" to adjust the sizeInBits.

Definition at line 646 of file ewah.h.

◆ logicalnot() [2/2]

template<class uword >

void ewah::EWAHBoolArray< uword >::logicalnot ( EWAHBoolArray< uword > & x ) const

Write the logical not of this bitmap in the provided container.

This function takes into account the sizeInBits value. You may need to call "padWithZeroes" to adjust the sizeInBits.

Definition at line 418 of file ewah-inl.h.

◆ logicalor() [1/2]

template<class uword >

EWAHBoolArray ewah::EWAHBoolArray< uword >::logicalor ( const EWAHBoolArray< uword > & a ) const

inline

computes the logical or with another compressed bitmap Return the answer Running time complexity is proportional to the sum of the compressed bitmap sizes.

If you have many bitmaps, see fast_logicalor.

The sizeInBits() of the result is equal to the maximum that of the current bitmap's sizeInBits() and that of a.sizeInBits().

Definition at line 318 of file ewah.h.

◆ logicalor() [2/2]

template<class uword >

void ewah::EWAHBoolArray< uword >::logicalor	(	const EWAHBoolArray< uword > &	a,
		EWAHBoolArray< uword > &	container ) const

computes the logical or with another compressed bitmap answer goes into container Running time complexity is proportional to the sum of the compressed bitmap sizes.

If you have many bitmaps, see fast_logicalor_tocontainer.

The sizeInBits() of the result is equal to the maximum that of the current bitmap's sizeInBits() and that of a.sizeInBits().

Definition at line 1193 of file ewah-inl.h.

◆ logicalorcount()

template<class uword >

size_t ewah::EWAHBoolArray< uword >::logicalorcount ( const EWAHBoolArray< uword > & a ) const

computes the size (in number of set bits) of the logical or with another compressed bitmap Running time complexity is proportional to the sum of the compressed bitmap sizes.

Definition at line 1243 of file ewah-inl.h.

◆ logicalxor() [1/2]

template<class uword >

EWAHBoolArray ewah::EWAHBoolArray< uword >::logicalxor ( const EWAHBoolArray< uword > & a ) const

inline

computes the logical xor with another compressed bitmap Return the answer Running time complexity is proportional to the sum of the compressed bitmap sizes.

The sizeInBits() of the result is equal to the maximum that of the current bitmap's sizeInBits() and that of a.sizeInBits().

Definition at line 349 of file ewah.h.

◆ logicalxor() [2/2]

template<class uword >

void ewah::EWAHBoolArray< uword >::logicalxor	(	const EWAHBoolArray< uword > &	a,
		EWAHBoolArray< uword > &	container ) const

computes the logical xor with another compressed bitmap answer goes into container Running time complexity is proportional to the sum of the compressed bitmap sizes.

The sizeInBits() of the result is equal to the maximum that of the current bitmap's sizeInBits() and that of a.sizeInBits().

Definition at line 1288 of file ewah-inl.h.

◆ logicalxorcount()

template<class uword >

size_t ewah::EWAHBoolArray< uword >::logicalxorcount ( const EWAHBoolArray< uword > & a ) const

computes the size (in number of set bits) of the logical xor with another compressed bitmap Running time complexity is proportional to the sum of the compressed bitmap sizes.

Definition at line 1332 of file ewah-inl.h.

◆ makeSameSize()

template<class uword >

void ewah::EWAHBoolArray< uword >::makeSameSize ( EWAHBoolArray< uword > & a )

inline

Make sure the two bitmaps have the same size (padding with zeroes if necessary).

It has constant running time complexity.

This is useful when calling "logicalnot" functions.

This can an adverse effect of performance, especially when computing intersections.

Definition at line 147 of file ewah.h.

◆ numberOfOnes()

template<class uword >

size_t ewah::EWAHBoolArray< uword >::numberOfOnes ( ) const

Returns the number of bits set to the value 1.

The running time complexity is proportional to the compressed size of the bitmap.

This is sometimes called the cardinality.

Definition at line 365 of file ewah-inl.h.

◆ operator std::string()

template<class uword >

ewah::EWAHBoolArray< uword >::operator std::string ( ) const

inline

Transform into a string that presents a list of set bits.

The running time is linear in the compressed size of the bitmap.

Definition at line 120 of file ewah.h.

◆ operator!=() [1/2]

template<class uword >

bool ewah::EWAHBoolArray< uword >::operator!= ( const BoolArray< uword > & x ) const

Definition at line 892 of file ewah-inl.h.

◆ operator!=() [2/2]

template<class uword >

bool ewah::EWAHBoolArray< uword >::operator!= ( const EWAHBoolArray< uword > & x ) const

We define two EWAHBoolArray as being different if they do not have the same set bits.

Alternatively, B1!=B2 if and only if cardinality(B1 XOR B2) >0.

Definition at line 881 of file ewah-inl.h.

◆ operator&()

template<class uword >

EWAHBoolArray ewah::EWAHBoolArray< uword >::operator& ( const EWAHBoolArray< uword > & a ) const

inline

calls logicaland

Definition at line 216 of file ewah.h.

◆ operator-()

template<class uword >

EWAHBoolArray ewah::EWAHBoolArray< uword >::operator- ( const EWAHBoolArray< uword > & a ) const

inline

calls logicalandnot

Definition at line 235 of file ewah.h.

◆ operator=() [1/2]

template<class uword >

EWAHBoolArray & ewah::EWAHBoolArray< uword >::operator= ( const EWAHBoolArray< uword > & x )

inline

Copies the content of one bitmap onto another.

Running time complexity is proportional to the size of the compressed bitmap. please, never hard-copy this object. Use the swap method if you must.

Definition at line 596 of file ewah.h.

◆ operator=() [2/2]

template<class uword >

EWAHBoolArray & ewah::EWAHBoolArray< uword >::operator= ( EWAHBoolArray< uword > && x )

inline

Move assignment operator.

Definition at line 613 of file ewah.h.

◆ operator==() [1/2]

template<class uword >

bool ewah::EWAHBoolArray< uword >::operator== ( const BoolArray< uword > & x ) const

Definition at line 886 of file ewah-inl.h.

◆ operator==() [2/2]

template<class uword >

bool ewah::EWAHBoolArray< uword >::operator== ( const EWAHBoolArray< uword > & x ) const

We define two EWAHBoolArray as being equal if they have the same set bits.

Alternatively, B1==B2 if and only if cardinality(B1 XOR B2) ==0.

Definition at line 720 of file ewah-inl.h.

◆ operator^()

template<class uword >

EWAHBoolArray ewah::EWAHBoolArray< uword >::operator^ ( const EWAHBoolArray< uword > & a ) const

inline

calls logicalxor

Definition at line 358 of file ewah.h.

◆ operator|()

template<class uword >

EWAHBoolArray ewah::EWAHBoolArray< uword >::operator| ( const EWAHBoolArray< uword > & a ) const

inline

calls logicalor

Definition at line 327 of file ewah.h.

◆ padWithZeroes()

template<class uword >

size_t ewah::EWAHBoolArray< uword >::padWithZeroes ( const size_t totalbits )

make sure the size of the array is totalbits bits by padding with zeroes.

returns the number of words added (storage cost increase).

This is useful when calling "logicalnot" functions.

This can an adverse effect of performance, especially when computing intersections.

Definition at line 635 of file ewah-inl.h.

◆ printout()

template<class uword >

void ewah::EWAHBoolArray< uword >::printout ( std::ostream & o = std::cout )

inline

Definition at line 380 of file ewah.h.

◆ raw_iterator()

template<class uword >

EWAHBoolArrayRawIterator< uword > ewah::EWAHBoolArray< uword >::raw_iterator ( ) const

To iterate over the compressed data.

Can be faster than any other iterator. Running time complexity of a full scan is proportional to the compressed size of the bitmap.

Definition at line 715 of file ewah-inl.h.

◆ read() [1/2]

template<class uword >

size_t ewah::EWAHBoolArray< uword >::read	(	const char *	in,
		size_t	capacity,
		const bool	savesizeinbits = true )

same as read(std::istream...), except that you provide a char pointer and a "capacity" (in bytes).

The function never reads at or beyond "in+capacity". If the detected storage exceeds the given capacity, the value zero is returned: it should be considered an error. Otherwise, the number of bytes read is returned.

Definition at line 581 of file ewah-inl.h.

◆ read() [2/2]

template<class uword >

size_t ewah::EWAHBoolArray< uword >::read	(	std::istream &	in,
		const bool	savesizeinbits = true )

this is the counterpart to the write method.

if you set savesizeinbits=false, then you are responsible for setting the value fo the attribute sizeinbits (see method setSizeInBits).

Returns how many bytes were queried from the stream.

Definition at line 556 of file ewah-inl.h.

◆ readBuffer()

template<class uword >

void ewah::EWAHBoolArray< uword >::readBuffer	(	std::istream &	in,
		const size_t	buffersize )

inline

read the buffer from a stream, see method writeBuffer.

this is for advanced users.

Definition at line 495 of file ewah-inl.h.

◆ reset()

template<class uword >

void ewah::EWAHBoolArray< uword >::reset ( )

inline

clear the content of the bitmap.

It does not release the memory.

Definition at line 365 of file ewah.h.

◆ set()

template<class uword >

bool ewah::EWAHBoolArray< uword >::set ( size_t i )

Set the ith bit to true (starting at zero).

Auto-expands the bitmap. It has constant running time complexity. Note that you must set the bits in increasing order: set(1), set(2) is ok; set(2), set(1) is not ok. set(100), set(100) is also not ok.

Note: by design EWAH is not an updatable data structure in the sense that once bit 1000 is set, you cannot change the value of bits 0 to 1000.

Returns true if the value of the bit was changed, and false otherwise. (In practice, if you set the bits in strictly increasing order, it should always return true.)

Definition at line 257 of file ewah-inl.h.

◆ setSizeInBits()

template<class uword >

void ewah::EWAHBoolArray< uword >::setSizeInBits ( const size_t size )

inline

set size in bits.

This does not affect the compressed size. It runs in constant time. This should not normally be used, except as part of a deserialization process.

Definition at line 668 of file ewah.h.

◆ sizeInBits()

template<class uword >

size_t ewah::EWAHBoolArray< uword >::sizeInBits ( ) const

inline

Return the size in bits of this bitmap (this refers to the uncompressed size in bits).

You can increase it with padWithZeroes()

Definition at line 395 of file ewah.h.

◆ sizeInBytes()

template<class uword >

size_t ewah::EWAHBoolArray< uword >::sizeInBytes ( ) const

inline

Return the size of the buffer in bytes.

This is equivalent to the storage cost, minus some overhead. See sizeOnDisk to get the actual storage cost with overhead.

Definition at line 402 of file ewah.h.

◆ sizeOnDisk()

template<class uword >

size_t ewah::EWAHBoolArray< uword >::sizeOnDisk ( const bool savesizeinbits = true ) const

Compute the size on disk assuming that it was saved using the method "write".

Definition at line 1674 of file ewah-inl.h.

◆ swap()

template<class uword >

void ewah::EWAHBoolArray< uword >::swap ( EWAHBoolArray< uword > & x )

Swap the content of this bitmap with another bitmap.

No copying is done. (Running time complexity is constant.)

Definition at line 766 of file ewah-inl.h.

◆ toArray()

template<class uword >

std::vector< size_t > ewah::EWAHBoolArray< uword >::toArray ( ) const

Retrieve the set bits.

Can be much faster than iterating through the set bits with an iterator.

Definition at line 383 of file ewah-inl.h.

◆ toBoolArray()

template<class uword >

BoolArray< uword > ewah::EWAHBoolArray< uword >::toBoolArray ( ) const

For convenience, this fully uncompresses the bitmap.

Not fast!

Definition at line 833 of file ewah-inl.h.

◆ toVector()

template<class uword >

std::vector< size_t > ewah::EWAHBoolArray< uword >::toVector ( ) const

inline

Returns a vector containing the position of the set bits in increasing order.

This just calls "toArray".

Definition at line 562 of file ewah.h.

◆ trim()

template<class uword >

void ewah::EWAHBoolArray< uword >::trim ( )

inline

Recover wasted memory usage.

Fit buffers to the actual data.

Definition at line 48 of file ewah.h.

◆ uncompress()

template<class uword >

EWAHBoolArrayIterator< uword > ewah::EWAHBoolArray< uword >::uncompress ( ) const

Iterate over the uncompressed words.

Can be considerably faster than begin()/end(). Running time complexity of a full scan is proportional to the uncompressed size of the bitmap.

Definition at line 710 of file ewah-inl.h.

◆ write() [1/2]

template<class uword >

size_t ewah::EWAHBoolArray< uword >::write	(	char *	out,
		size_t	capacity,
		const bool	savesizeinbits = true ) const

same as write(std::ostream...), except that you provide a char pointer and a "capacity" (in bytes).

The function never writes at or beyond "out+capacity". If the storage needed exceeds the given capacity, the value zero is returned: it should be considered an error. Otherwise, the number of bytes copied is returned.

Definition at line 525 of file ewah-inl.h.

◆ write() [2/2]

template<class uword >

size_t ewah::EWAHBoolArray< uword >::write	(	std::ostream &	out,
		const bool	savesizeinbits = true ) const

Save this bitmap to a stream.

The file format is | sizeinbits | buffer lenth | buffer content| the sizeinbits part can be omitted if "savesizeinbits=false". Both sizeinbits and buffer length are saved using the uint64_t data type. Returns how many bytes were handed out to the stream.

Definition at line 503 of file ewah-inl.h.

◆ writeBuffer()

template<class uword >

void ewah::EWAHBoolArray< uword >::writeBuffer ( std::ostream & out ) const

inline

This only writes the content of the buffer (see write()) method.

It is for advanced users.

Definition at line 488 of file ewah-inl.h.

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

include/ewah/ewah.h
include/ewah/runninglengthword.h
include/ewah/ewah-inl.h

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

Member Typedef Documentation

◆ const_iterator

Member Enumeration Documentation

◆ anonymous enum

◆ anonymous enum

Constructor & Destructor Documentation

◆ EWAHBoolArray() [1/3]

◆ EWAHBoolArray() [2/3]

◆ EWAHBoolArray() [3/3]

Member Function Documentation

◆ addStreamOfDirtyWords()

◆ addStreamOfEmptyWords()

◆ addStreamOfNegatedDirtyWords()

◆ addWord()

◆ append()

◆ appendSetBits()

◆ begin()

◆ bitmapOf()

◆ bufferSize()

◆ computeStatistics()

◆ debugprintout()

◆ empty()

◆ end()

◆ expensive_copy()

◆ fastaddStreamOfDirtyWords()

◆ fastaddStreamOfEmptyWords()

◆ get()

◆ getBuffer()

◆ inplace_logicalnot()

◆ intersects()

◆ logicaland() [1/2]

◆ logicaland() [2/2]

◆ logicalandcount()

◆ logicalandnot() [1/2]

◆ logicalandnot() [2/2]

◆ logicalandnotcount()

◆ logicalnot() [1/2]

◆ logicalnot() [2/2]

◆ logicalor() [1/2]

◆ logicalor() [2/2]

◆ logicalorcount()

◆ logicalxor() [1/2]

◆ logicalxor() [2/2]

◆ logicalxorcount()

◆ makeSameSize()

◆ numberOfOnes()

◆ operator std::string()

◆ operator!=() [1/2]

◆ operator!=() [2/2]

◆ operator&()

◆ operator-()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==() [1/2]

◆ operator==() [2/2]

◆ operator^()

◆ operator|()

◆ padWithZeroes()

◆ printout()

◆ raw_iterator()

◆ read() [1/2]

◆ read() [2/2]

◆ readBuffer()

◆ reset()

◆ set()

◆ setSizeInBits()

◆ sizeInBits()

◆ sizeInBytes()

◆ sizeOnDisk()

◆ swap()

◆ toArray()

◆ toBoolArray()

◆ toVector()

◆ trim()

◆ uncompress()

◆ write() [1/2]