Detailed Description

template<typename IndexType = int64_t>
class operations_research::Bitset64< IndexType >

This class is like an ITIVector<IndexType, bool> except that it provides a more efficient way to iterate over the positions set to true. It achieves this by caching the current uint64_t bucket in the Iterator and using LeastSignificantBitPosition64() to iterate over the positions at 1 in this bucket.

Definition at line 415 of file bitset.h.

#include <bitset.h>

Classes
class	ConstView
	When speed matter, caching the base pointer helps. More...
class	Iterator
class	View

Public Types
using	value_type = IndexType

Public Member Functions
	Bitset64 ()
	Bitset64 (IndexType size)
ConstView	const_view () const
View	view ()
IndexType	size () const
	Returns how many bits this Bitset64 can hold.
void	PushBack (bool value)
	Appends value at the end of the bitset.
void	resize (int size)
	Resizes the Bitset64 to the given number of bits. New bits are sets to 0.
void	Resize (IndexType size)
void	ClearAndResize (IndexType size)
	Changes the number of bits the Bitset64 can hold and set all of them to 0.
void	ClearAll ()
	Sets all bits to 0.
void	Clear (IndexType i)
	Sets the bit at position i to 0.
void	ClearBucket (IndexType i)
	Sets bucket containing bit i to 0.
void	ClearTwoBits (IndexType i)
	Clears the bits at position i and i ^ 1.
bool	AreOneOfTwoBitsSet (IndexType i) const
	Returns true if the bit at position i or the one at position i ^ 1 is set.
bool	IsSet (IndexType i) const
	Returns true if the bit at position i is set.
bool	operator[] (IndexType i) const
	Same as IsSet().
void	Set (IndexType i)
	Sets the bit at position i to 1.
void	Set (IndexType i, bool value)
	If value is true, sets the bit at position i to 1, sets it to 0 otherwise.
void	CopyBucket (const Bitset64< IndexType > &other, IndexType i)
	Copies bucket containing bit i from "other" to "this".
template<typename OtherIndexType>
void	SetContentFromBitset (const Bitset64< OtherIndexType > &other)
template<typename OtherIndexType>
void	SetContentFromBitsetOfSameSize (const Bitset64< OtherIndexType > &other)
	Same as SetContentFromBitset where "this" and "other" have the same size.
void	Intersection (const Bitset64< IndexType > &other)
void	SetToIntersectionOf (const Bitset64< IndexType > &a, const Bitset64< IndexType > &b)
	This one assume both given bitset to be of the same size.
void	Union (const Bitset64< IndexType > &other)
Iterator	begin () const
Iterator	end () const
std::string	DebugString () const
	Returns a 0/1 string representing the bitset.
bool	IsAllFalse () const

Static Public Member Functions
static uint64_t	ConditionalXorOfTwoBits (IndexType i, uint64_t use1, Bitset64< IndexType >::ConstView set1, uint64_t use2, Bitset64< IndexType >::ConstView set2)

Friends
template<class OtherIndexType>
class	Bitset64

Member Typedef Documentation

◆ value_type

template<typename IndexType = int64_t>

using operations_research::Bitset64< IndexType >::value_type = IndexType

Definition at line 417 of file bitset.h.

Constructor & Destructor Documentation

◆ Bitset64() [1/2]

template<typename IndexType = int64_t>

operations_research::Bitset64< IndexType >::Bitset64 ( )

inline

Definition at line 454 of file bitset.h.

◆ Bitset64() [2/2]

template<typename IndexType = int64_t>

operations_research::Bitset64< IndexType >::Bitset64 ( IndexType size )

inlineexplicit

Definition at line 455 of file bitset.h.

Member Function Documentation

◆ AreOneOfTwoBitsSet()

template<typename IndexType = int64_t>

bool operations_research::Bitset64< IndexType >::AreOneOfTwoBitsSet ( IndexType i ) const

inline

Returns true if the bit at position i or the one at position i ^ 1 is set.

Definition at line 526 of file bitset.h.

◆ begin()

template<typename IndexType = int64_t>

Iterator operations_research::Bitset64< IndexType >::begin ( ) const

inline

Allows range-based "for" loop on the non-zero positions: for (const IndexType index : bitset) {}

Definition at line 703 of file bitset.h.

◆ Clear()

template<typename IndexType = int64_t>

void operations_research::Bitset64< IndexType >::Clear ( IndexType i )

inline

Sets the bit at position i to 0.

Definition at line 505 of file bitset.h.

◆ ClearAll()

template<typename IndexType = int64_t>

void operations_research::Bitset64< IndexType >::ClearAll ( )

inline

Sets all bits to 0.

Definition at line 502 of file bitset.h.

◆ ClearAndResize()

template<typename IndexType = int64_t>

void operations_research::Bitset64< IndexType >::ClearAndResize ( IndexType size )

inline

Changes the number of bits the Bitset64 can hold and set all of them to 0.

Memset is 4x faster than data_.assign() as of 19/03/2014.

Todo: (user): Ideally if a realloc happens, we don't need to copy the old data...

Definition at line 488 of file bitset.h.

◆ ClearBucket()

template<typename IndexType = int64_t>

void operations_research::Bitset64< IndexType >::ClearBucket ( IndexType i )

inline

Sets bucket containing bit i to 0.

Definition at line 512 of file bitset.h.

◆ ClearTwoBits()

template<typename IndexType = int64_t>

void operations_research::Bitset64< IndexType >::ClearTwoBits ( IndexType i )

inline

Clears the bits at position i and i ^ 1.

Definition at line 519 of file bitset.h.

◆ ConditionalXorOfTwoBits()

template<typename IndexType = int64_t>

uint64_t operations_research::Bitset64< IndexType >::ConditionalXorOfTwoBits	(	IndexType	i,
		uint64_t	use1,
		Bitset64< IndexType >::ConstView	set1,
		uint64_t	use2,
		Bitset64< IndexType >::ConstView	set2 )

inlinestatic

Cryptic function! This is just an optimized version of a given piece of code and has probably little general use.

Definition at line 708 of file bitset.h.

◆ const_view()

template<typename IndexType = int64_t>

ConstView operations_research::Bitset64< IndexType >::const_view ( ) const

inline

Definition at line 459 of file bitset.h.

◆ CopyBucket()

template<typename IndexType = int64_t>

void operations_research::Bitset64< IndexType >::CopyBucket	(	const Bitset64< IndexType > &	other,
		IndexType	i )

inline

Copies bucket containing bit i from "other" to "this".

Definition at line 560 of file bitset.h.

◆ DebugString()

template<typename IndexType = int64_t>

std::string operations_research::Bitset64< IndexType >::DebugString ( ) const

inline

Returns a 0/1 string representing the bitset.

Definition at line 721 of file bitset.h.

◆ end()

template<typename IndexType = int64_t>

Iterator operations_research::Bitset64< IndexType >::end ( ) const

inline

Definition at line 704 of file bitset.h.

◆ Intersection()

template<typename IndexType = int64_t>

void operations_research::Bitset64< IndexType >::Intersection ( const Bitset64< IndexType > & other )

inline

Sets "this" to be the intersection of "this" and "other". The bitsets do not have to be the same size. If other is smaller, all the higher order bits are assumed to be 0.

Definition at line 592 of file bitset.h.

◆ IsAllFalse()

template<typename IndexType = int64_t>

bool operations_research::Bitset64< IndexType >::IsAllFalse ( ) const

inline

Definition at line 729 of file bitset.h.

◆ IsSet()

template<typename IndexType = int64_t>

bool operations_research::Bitset64< IndexType >::IsSet ( IndexType i ) const

inline

Returns true if the bit at position i is set.

Definition at line 533 of file bitset.h.

◆ operator[]()

template<typename IndexType = int64_t>

bool operations_research::Bitset64< IndexType >::operator[] ( IndexType i ) const

inline

Same as IsSet().

Definition at line 540 of file bitset.h.

◆ PushBack()

template<typename IndexType = int64_t>

void operations_research::Bitset64< IndexType >::PushBack ( bool value )

inline

Appends value at the end of the bitset.

Definition at line 466 of file bitset.h.

◆ Resize()

template<typename IndexType = int64_t>

void operations_research::Bitset64< IndexType >::Resize ( IndexType size )

inline

Definition at line 474 of file bitset.h.

◆ resize()

template<typename IndexType = int64_t>

void operations_research::Bitset64< IndexType >::resize ( int size )

inline

Resizes the Bitset64 to the given number of bits. New bits are sets to 0.

Definition at line 473 of file bitset.h.

◆ Set() [1/2]

template<typename IndexType = int64_t>

void operations_research::Bitset64< IndexType >::Set ( IndexType i )

inline

Sets the bit at position i to 1.

The c++ hardening is costly here, so we disable it.

Definition at line 543 of file bitset.h.

◆ Set() [2/2]

template<typename IndexType = int64_t>

void operations_research::Bitset64< IndexType >::Set	(	IndexType	i,
		bool	value )

inline

If value is true, sets the bit at position i to 1, sets it to 0 otherwise.

Definition at line 551 of file bitset.h.

◆ SetContentFromBitset()

template<typename IndexType = int64_t>

template<typename OtherIndexType>

void operations_research::Bitset64< IndexType >::SetContentFromBitset ( const Bitset64< OtherIndexType > & other )

inline

Copies "other" to "this". The bitsets do not have to be of the same size. If "other" is smaller, high order bits are not changed. If "other" is larger, its high order bits are ignored. In any case "this" is not resized.

Definition at line 569 of file bitset.h.

◆ SetContentFromBitsetOfSameSize()

template<typename IndexType = int64_t>

template<typename OtherIndexType>

void operations_research::Bitset64< IndexType >::SetContentFromBitsetOfSameSize ( const Bitset64< OtherIndexType > & other )

inline

Same as SetContentFromBitset where "this" and "other" have the same size.

Definition at line 584 of file bitset.h.

◆ SetToIntersectionOf()

template<typename IndexType = int64_t>

void operations_research::Bitset64< IndexType >::SetToIntersectionOf	(	const Bitset64< IndexType > &	a,
		const Bitset64< IndexType > &	b )

inline

This one assume both given bitset to be of the same size.

Copy buckets.

Definition at line 605 of file bitset.h.

◆ size()

template<typename IndexType = int64_t>

IndexType operations_research::Bitset64< IndexType >::size ( ) const

inline

Returns how many bits this Bitset64 can hold.

Definition at line 463 of file bitset.h.

◆ Union()

template<typename IndexType = int64_t>

void operations_research::Bitset64< IndexType >::Union ( const Bitset64< IndexType > & other )

inline

Sets "this" to be the union of "this" and "other". The bitsets do not have to be the same size. If other is smaller, all the higher order bits are assumed to be 0.

Definition at line 620 of file bitset.h.

◆ view()

template<typename IndexType = int64_t>

View operations_research::Bitset64< IndexType >::view ( )

inline

Definition at line 460 of file bitset.h.

◆ Bitset64

template<typename IndexType = int64_t>

template<class OtherIndexType>

friend class Bitset64

friend

Definition at line 743 of file bitset.h.

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

ortools/util/bitset.h

Detailed Description

Classes

Public Types

Public Member Functions

Static Public Member Functions

Friends

Member Typedef Documentation

◆ value_type

Constructor & Destructor Documentation

◆ Bitset64() [1/2]

◆ Bitset64() [2/2]

Member Function Documentation

◆ AreOneOfTwoBitsSet()

◆ begin()

◆ Clear()

◆ ClearAll()

◆ ClearAndResize()

◆ ClearBucket()

◆ ClearTwoBits()

◆ ConditionalXorOfTwoBits()

◆ const_view()

◆ CopyBucket()

◆ DebugString()

◆ end()

◆ Intersection()

◆ IsAllFalse()

◆ IsSet()

◆ operator[]()

◆ PushBack()

◆ Resize()

◆ resize()

◆ Set() [1/2]

◆ Set() [2/2]

◆ SetContentFromBitset()

◆ SetContentFromBitsetOfSameSize()

◆ SetToIntersectionOf()

◆ size()

◆ Union()

◆ view()

Friends And Related Symbol Documentation

◆ Bitset64