atlas  0.6
atlas::bitvector Namespace Reference

## Classes

class  BitMatrix

class  BitVector

class  BitVectorList

struct  FirstBit

## Functions

template<size_t dim>
std::ostream & operator<< (std::ostream &strm, const BitVector< dim > &v)

template<size_t dim>
BitVector< dim > combination (const std::vector< BitVector< dim > > &b, size_t n, const BitSet< dim > &e)
Puts in |v| the linear combination of the elements of |b| given by |e|. More...

template<size_t dim>
BitSet< dim > combination (const std::vector< BitSet< dim > > &b, const BitSet< dim > &coef)
Returns the linear combination of the elements of |b| given by |coef|. More...

template<size_t dim>
bool combination_exists (const std::vector< BitVector< dim > > &b, const BitVector< dim > &rhs, BitSet< dim > &c)

template<size_t dimsol, size_t dimeq>
bool solvable (const std::vector< BitVector< dimeq > > &eqns, BitVector< dimsol > &sol)
Either find a solution of the system of equations |eqn|, putting it into |sol| and returning |true|, or return |false| if no solution exists. More...

template<size_t dim>
void identityMatrix (BitMatrix< dim > &m, size_t n)
Puts in m the identity matrix in rank n. More...

template<size_t dim>
void initBasis (std::vector< BitVector< dim > > &b, size_t n)
Initializes b to the canonical basis in dimension n. More...

template<size_t dim>
void Gauss_Jordan (BitSet< dim > &t, std::vector< BitVector< dim > > &b)
Replaces |b| by the ordered canonical basis of the vector space \$V\$ it spans. Flags in |t| the set of coordinate positions associated to |b|. More...

template<size_t dim>
void normalSpanAdd (std::vector< BitVector< dim > > &a, std::vector< size_t > &f, const BitVector< dim > &v)

template<size_t dim>
void spanAdd (std::vector< BitVector< dim > > &a, std::vector< size_t > &f, const BitVector< dim > &v)
Enlarges the basis |a| so as to span |v|. More...

template<size_t dim>
int_Vector lift (const BitVector< dim > &v)

template SmallBitVector combination (const std::vector< SmallBitVector > &b, size_t n, const BitSet< constants::RANK_MAX > &e)

template BitSet< constants::RANK_MAXcombination (const std::vector< BitSet< constants::RANK_MAX > > &, const BitSet< constants::RANK_MAX > &)

template void Gauss_Jordan (BitSet< constants::RANK_MAX > &t, std::vector< SmallBitVector > &b)

template bool combination_exists (const std::vector< SmallBitVector > &b, const SmallBitVector &rhs, BitSet< constants::RANK_MAX > &c)

template bool solvable (const std::vector< BitVector< constants::RANK_MAX+1 > > &eqns, SmallBitVector &sol)

template void identityMatrix (BitMatrix< constants::RANK_MAX > &, size_t)

template void initBasis (std::vector< SmallBitVector > &, size_t)

template int_Vector lift (const SmallBitVector &v)

template void initBasis< 64ul > (std::vector< BitVector< 64ul > > &b, size_t r)

BinaryEquation make_equation (const SmallBitVector &lhs, bool rhs)

## Function Documentation

template<size_t dim>
 BitVector< dim > atlas::bitvector::combination ( const std::vector< BitVector< dim > > & b, size_t n, const BitSet< dim > & e )

Puts in |v| the linear combination of the elements of |b| given by |e|.

NOTE : it is the caller's responsibility to check that |v| already has the correct size. (The right size cannot be determined here if |b.size()=0|.)

template<size_t dim>
 BitSet< dim > atlas::bitvector::combination ( const std::vector< BitSet< dim > > & b, const BitSet< dim > & coef )

Returns the linear combination of the elements of |b| given by |coef|.

Contrary to the previous case, there is no notion of size for |v|, and there is no need for any particular preparation.

 template SmallBitVector atlas::bitvector::combination ( const std::vector< SmallBitVector > & b, size_t n, const BitSet< constants::RANK_MAX > & e )
 template BitSet atlas::bitvector::combination ( const std::vector< BitSet< constants::RANK_MAX > > & , const BitSet< constants::RANK_MAX > & )
template<size_t dim>
 bool atlas::bitvector::combination_exists ( const std::vector< BitVector< dim > > & b, const BitVector< dim > & rhs, BitSet< dim > & c )

Find out whether any combination of the vectors in |b| adds to |rhs|, and if so flag such a combination in the bits of |c|. Nothing changes when |false|.

 template bool atlas::bitvector::combination_exists ( const std::vector< SmallBitVector > & b, const SmallBitVector & rhs, BitSet< constants::RANK_MAX > & c )
template<size_t dim>
 void atlas::bitvector::Gauss_Jordan ( BitSet< dim > & t, std::vector< BitVector< dim > > & b )

Replaces |b| by the ordered canonical basis of the vector space \$V\$ it spans. Flags in |t| the set of coordinate positions associated to |b|.

What is flagged in |t| is the set \$J\$ in described in the comment for |normalSpanAdd| below. For any \$j\$, only |b[j]| has a nonzero bit at the position \$j'\$ where number |j| among the raised bits of |t| is found; consequently, for any \$v V\$, the coordinate of |b[j]| in \$v\$ is \$v[j']\$.

This function works essentially by repeatedly calling |normalSpanAdd| for the vectors of |b|, replacing |b| by the resulting canonical basis at the end. However, the selected coordiante positions |f| do not come out increasingly this way, so we have to sort the canonical basis by leading bit position. This amounts to setting \$a'[k]=a[p(k)]\$ where \$p(0),p(l-1)\$ is the result of sorting \$f[0],f[l-1]\$ with \$l=f.size()=a.size()\$.

 template void atlas::bitvector::Gauss_Jordan ( BitSet< constants::RANK_MAX > & t, std::vector< SmallBitVector > & b )
template<size_t dim>
 void atlas::bitvector::identityMatrix ( BitMatrix< dim > & m, size_t n )

Puts in m the identity matrix in rank n.

Precondition: n <= dim;

 template void atlas::bitvector::identityMatrix ( BitMatrix< constants::RANK_MAX > & , size_t )
template<size_t dim>
 void atlas::bitvector::initBasis ( std::vector< BitVector< dim > > & b, size_t n )

Initializes b to the canonical basis in dimension n.

 template void atlas::bitvector::initBasis ( std::vector< SmallBitVector > & , size_t )
 template void atlas::bitvector::initBasis< 64ul > ( std::vector< BitVector< 64ul > > & b, size_t r )
template<size_t dim>
 int_Vector atlas::bitvector::lift ( const BitVector< dim > & v )
 template int_Vector atlas::bitvector::lift ( const SmallBitVector & v )
 BinaryEquation atlas::bitvector::make_equation ( const SmallBitVector & lhs, bool rhs )
inline
template<size_t dim>
 void atlas::bitvector::normalSpanAdd ( std::vector< BitVector< dim > > & a, std::vector< size_t > & f, const BitVector< dim > & v )

\$ such that the standard basis vectors \$e_i\$ for \$i I\$ generate a complementary subspace \$e_I\$ to \$V\$ (one can find such an \$I\$ by repeatedly throwing in \$e_i\$s linearly independent to \$V\$ and previously chosen ones). The normal basis of \$V\$ corresponding to \$I\$ is obtained by projecting the \$e_j\$ for \$j\$ in the complement \$J\$ of \$I\$ onto \$V\$ along \$e_I\$ (i.e., according to the direct sum decompostion \$k^d=V e_I\$). This can be visualised by viewing \$V\$ as the function-graph of a linear map from \$k^J\$ to \$k^I\$ (with the coordinates of domain and codomain interwoven at the positions \$J\$ and \$I\$, respectively); then the normal basis is the lift to the graph \$V\$ of the standard basis of \$k^J\$. We define the canonical basis of \$V\$ to be the normal basis for the complement \$I\$ of the lexicographically minimal possible set \$J\$ (lexicographic for the increasing sequences representing the subsets; in fact \$I\$ is lexicographically maximal since complementation reverses this ordering on fixed-size subsets). One can find this \$J\$ by repeatedly choosing the smallest index such that the projection from \$V\$ defined by extracting the coordinates at the selected indices remains surjective to the set of all possible coordinate tuples. (Intersect \$V\$ with the subspace defined by setting previously selected coordinates to zero; choose the smallest coordinate that can be nonzero.)

This function assumes that \$a\$ already contains the canonical basis of some subspace, and that the elements of |f| describe the corresponding set \$J\$. We add |v| to the subspace and extend |f|. Then |a| nor |f| are modified if |v| lies in the subspace generated by |a|. Otherwise a new element is added to |a|, a new coordinate index |n| is added to |f|, and the existing vectors in |a| are modified to clear their coordinate |n|.

template<size_t dim>
 std::ostream & atlas::bitvector::operator<< ( std::ostream & strm, const BitVector< dim > & v )
template<size_t dimsol, size_t dimeq>
 bool atlas::bitvector::solvable ( const std::vector< BitVector< dimeq > > & eqns, BitVector< dimsol > & sol )

Either find a solution of the system of equations |eqn|, putting it into |sol| and returning |true|, or return |false| if no solution exists.

Here |eqn| holds a system of equations, the last bit of each being interpreted as the right hand side.

 template bool atlas::bitvector::solvable ( const std::vector< BitVector< constants::RANK_MAX+1 > > & eqns, SmallBitVector & sol )
template<size_t dim>
 void atlas::bitvector::spanAdd ( std::vector< BitVector< dim > > & a, std::vector< size_t > & f, const BitVector< dim > & v )

Enlarges the basis |a| so as to span |v|.

This is a simplified version of |normalSpanAdd|

It is assumed that |a| contains a list of independent bitvectors all of size |v.size()|; then a reduction of |v| modulo the vectors of |a| is added to the list if |v| was independent, and if it was dependent nothing happens.

Here we still assume that the first set bits of the elements in |a| are all distinct, their positions are indicated in |f|, and bit number |f[i]| is cleared in |a[j]| whenever |i<j|; under these conditions reduction modulo~|a| can be performed by subtracting, for all |i| in increasing order, the vector |a[i]| if bit |f[i]| is currently set. We do not however assume that bit number |f[i]| is cleared in |a[j]| for all |j<i|, and as a consequence we do not need to modify previous vectors |a[i]| to maintain the condition for calling |spanAdd| again; this is the (only) difference with |normalSpanAdd|.