gf2mat.h

Go to the documentation of this file.

#ifndef GF2MAT_H
#define GF2MAT_H

#include <itpp/base/vec.h>
#include <itpp/base/mat.h>
#include <itpp/base/svec.h>
#include <itpp/base/smat.h>
#include <itpp/base/itfile.h>
#include <itpp/itexports.h>

namespace itpp
{

#if (defined(_MSC_VER) && defined(ITPP_SHARED_LIB))
//MSVC needs to explicitely instantiate required templates while building the
//shared library. Also, these definitions are marked as imported when library is
//linked with user's code.

template class ITPP_EXPORT Sparse_Mat<bin>;
template class ITPP_EXPORT Sparse_Vec<bin>;
template class ITPP_EXPORT Mat<unsigned char>;

#endif


// ----------------------------------------------------------------------
// Sparse GF(2) matrix class
// ----------------------------------------------------------------------

typedef Sparse_Vec<bin> GF2vec_sparse;

typedef Sparse_Mat<bin> GF2mat_sparse;


// ----------------------------------------------------------------------
// Alist parameterization of sparse GF(2) matrix class
// ----------------------------------------------------------------------

class ITPP_EXPORT GF2mat_sparse_alist
{
public:
  GF2mat_sparse_alist() : data_ok(false) {}
  GF2mat_sparse_alist(const std::string &fname);

  void read(const std::string &fname);
  void write(const std::string &fname) const;

  GF2mat_sparse to_sparse(bool transpose = false) const;

  void from_sparse(const GF2mat_sparse &mat, bool transpose = false);

protected:
  bool data_ok;
  int M;
  int N;
  imat mlist;
  imat nlist;
  ivec num_mlist;
  ivec num_nlist;
  int max_num_m;
  int max_num_n;
};


// ----------------------------------------------------------------------
// Dense GF(2) matrix class
// ----------------------------------------------------------------------

class ITPP_EXPORT GF2mat
{
public:

  // ----------- Constructors -----------

  GF2mat();

  GF2mat(int m, int n);

  GF2mat(const GF2mat_sparse &X);

  GF2mat(const GF2mat_sparse &X, int m1, int n1, int m2, int n2);

  GF2mat(const GF2mat_sparse &X, const ivec &columns);

  GF2mat(const bvec &x, bool is_column = true);

  GF2mat(const bmat &X);

  void set_size(int m, int n, bool copy = false);

  GF2mat_sparse sparsify() const;

  bvec bvecify() const;

  // ----------- Elementwise manipulation and simple functions -------------

  inline bin get(int i, int j) const;

  inline bin operator()(int i, int j) const { return get(i, j); };

  inline void set(int i, int j, bin s);

  inline void addto_element(int i, int j, bin s);

  void set_col(int j, bvec x);

  void set_row(int i, bvec x);

  bool is_zero() const;

  void swap_rows(int i, int j);

  void swap_cols(int i, int j);

  void permute_rows(ivec &perm, bool I);

  void permute_cols(ivec &perm, bool I);

  GF2mat transpose() const;

  GF2mat get_submatrix(int m1, int n1, int m2, int n2) const;

  GF2mat concatenate_horizontal(const GF2mat &X) const;

  GF2mat concatenate_vertical(const GF2mat &X) const;

  bvec get_row(int i) const;

  bvec get_col(int j) const;

  double density() const;

  int rows() const { return nrows; }

  int cols() const { return ncols; }

  void add_rows(int i, int j);

  // ---------- Linear algebra --------------

  GF2mat inverse() const;

  int row_rank() const;

  int T_fact(GF2mat &T, GF2mat &U, ivec &P) const;

  int T_fact_update_bitflip(GF2mat &T, GF2mat &U,
                            ivec &P, int rank, int r, int c) const;

  bool T_fact_update_addcol(GF2mat &T, GF2mat &U,
                            ivec &P, bvec newcol) const;

  // ----- Operators -----------

  void operator=(const GF2mat &X);

  bool operator==(const GF2mat &X) const;

  // ----- Friends ------

  friend ITPP_EXPORT GF2mat operator*(const GF2mat &X, const GF2mat &Y);

  friend ITPP_EXPORT bvec operator*(const GF2mat &X, const bvec &y);

  friend ITPP_EXPORT GF2mat operator+(const GF2mat &X, const GF2mat &Y);

  friend ITPP_EXPORT std::ostream &operator<<(std::ostream &os, const GF2mat &X);

  friend ITPP_EXPORT it_file &operator<<(it_file &f, const GF2mat &X);

  friend ITPP_EXPORT it_ifile &operator>>(it_ifile &f, GF2mat &X);

  friend ITPP_EXPORT GF2mat mult_trans(const GF2mat &X, const GF2mat &Y);

private:
  int nrows, ncols;            // number of rows and columns of matrix
  int nwords;                  // number of bytes used
  Mat<unsigned char> data;   // data structure

  // This value is used to perform division by bit shift and is equal to
  // log2(8)
  static const unsigned char shift_divisor = 3;

  // This value is used as a mask when computing the bit position of the
  // division remainder
  static const unsigned char rem_mask = (1 << shift_divisor) - 1;
};


// ----------------------------------------------------------------------
// GF2mat related functions
// ----------------------------------------------------------------------

ITPP_EXPORT it_file &operator<<(it_file &f, const GF2mat &X);

ITPP_EXPORT it_ifile &operator>>(it_ifile &f, GF2mat &X);


ITPP_EXPORT GF2mat operator*(const GF2mat &X, const GF2mat &Y);

ITPP_EXPORT bvec operator*(const GF2mat &X, const bvec &y);

ITPP_EXPORT GF2mat operator+(const GF2mat &X, const GF2mat &Y);

ITPP_EXPORT std::ostream &operator<<(std::ostream &os, const GF2mat &X);

ITPP_EXPORT GF2mat gf2dense_eye(int m);

ITPP_EXPORT GF2mat mult_trans(const GF2mat &X, const GF2mat &Y);


// ----------------------------------------------------------------------
// Inline implementations
// ----------------------------------------------------------------------

inline void GF2mat::addto_element(int i, int j, bin s)
{
  it_assert_debug(i >= 0 && i < nrows, "GF2mat::addto_element()");
  it_assert_debug(j >= 0 && j < ncols, "GF2mat::addto_element()");
  if (s == 1)
    data(i, (j >> shift_divisor)) ^= (1 << (j & rem_mask));
}

inline bin GF2mat::get(int i, int j) const
{
  it_assert_debug(i >= 0 && i < nrows, "GF2mat::get_element()");
  it_assert_debug(j >= 0 && j < ncols, "GF2mat::get_element()");
  return (data(i, (j >> shift_divisor)) >> (j & rem_mask)) & 1;
}

inline void GF2mat::set(int i, int j, bin s)
{
  it_assert_debug(i >= 0 && i < nrows, "GF2mat::set_element()");
  it_assert_debug(j >= 0 && j < ncols, "GF2mat::set_element()");
  if (s == 1) // set bit to one
    data(i, (j >> shift_divisor)) |= (1 << (j & rem_mask));
  else // set bit to zero
    data(i, (j >> shift_divisor)) &= (~(1 << (j & rem_mask)));
}

} // namespace itpp

#endif // #ifndef GF2MAT_H