Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::Bitset64< IndexType > Class Template Reference

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: