Empirical
BitMatrix.h
Go to the documentation of this file.
1 
11 #ifndef EMP_BIT_MATRIX_H
12 #define EMP_BIT_MATRIX_H
13 
14 #include <iostream>
15 #include <typeinfo>
16 
17 #include "BitSet.h"
18 
19 #ifndef functions
20 #include "functions.h"
21 #endif
22 
23 #include "bitset_utils.h"
24 
25 namespace emp {
26 
36 
37  template <size_t COLS, size_t ROWS>
38  class BitMatrix {
39  private:
40  BitSet<COLS*ROWS> bits;
41 
42  public:
43  template <size_t START_POS, size_t STEP_POS, size_t END_POS>
44  constexpr BitSet<COLS*ROWS> Mask() const {
45  return BitSet<COLS*ROWS>();
46  }
47 
49  template <size_t COL_ID>
50  static const BitSet<COLS*ROWS> & MaskCol() {
51  static bool init = false;
52  static BitSet<COLS*ROWS> mask;
53  if (!init) {
54  for (size_t i = 0; i < ROWS; i++) mask[i*COLS + COL_ID] = 1;
55  init = true;
56  }
57  return mask;
58  // return mask_pattern<COLS*ROWS, COL_ID, COLS, COLS*ROWS-1>();
59  }
60 
62  template <size_t ROW_ID>
63  static const BitSet<COLS*ROWS> & MaskRow() {
64  static bool init = false;
65  static BitSet<COLS*ROWS> mask;
66  if (!init) {
67  for (size_t i = 0; i < COLS; i++) mask[ROW_ID * COLS + i] = 1;
68  init = true;
69  }
70  return mask;
71  }
72 
73 // public:
74  BitMatrix() { ; }
75  BitMatrix(const BitSet<COLS*ROWS> & in_bits) : bits(in_bits) { ; }
76  BitMatrix(const BitMatrix & in_matrix) : bits(in_matrix.bits) { ; }
77  ~BitMatrix() { ; }
78 
80  constexpr size_t NumRows() const { return ROWS; }
81 
83  constexpr size_t NumCols() const { return COLS; }
84 
86  constexpr size_t GetSize() const { return ROWS * COLS; }
87 
89  inline static size_t ToCol(size_t id) { return id % COLS; }
90 
92  inline static size_t ToRow(size_t id) { return id / COLS; }
93 
95  inline static size_t ToID(size_t col, size_t row) { return row * COLS + col; }
96 
97  bool Any() const { return bits.any(); }
98  bool None() const { return bits.none(); }
99  bool All() const { return bits.all(); }
100 
101  bool Get(size_t col, size_t row) const { return bits[ToID(col,row)]; }
102  bool Get(size_t id) const { return bits[id]; }
103 
104  void Set(size_t col, size_t row, bool val=true) { bits[ToID(col, row)] = val; }
105  void Set(size_t id) { bits[id] = true; }
106  void Unset(size_t col, size_t row) { bits[ToID(col, row)] = false; }
107  void Unset(size_t id) { bits[id] = false; }
108  void Flip(size_t col, size_t row) { bits.flip(ToID(col, row)); }
109  void Flip(size_t id) { bits.flip(id); }
110 
111  void SetAll() { bits.SetAll(); }
112  void SetCol(size_t col) { bits |= MaskCol<0>() << col;}
113  void SetRow(size_t row) { bits |= (MaskRow<0>() << (row * COLS)); }
114  void Clear() { bits.Clear(); }
115  void ClearCol(size_t col) { bits &= ~(MaskCol<0>() << col); }
116  void ClearRow(size_t row) { bits &= ~(MaskRow<0>() << (row * COLS)); }
117 
118  // Count the number of set bits in the matrix.
119  size_t CountOnes() const { return bits.count(); }
120 
121  // Find the position of the first non-zero bit.
122  // size_t FindBit() const { return (~bits & (bits - 1)).count(); }
123 
124  int FindBit() const { return bits.FindBit(); }
125 
126  // Shift the whole matrix in the specified direction.
127  BitMatrix LeftShift() const { return ((bits & ~MaskCol<0>()) >> 1); }
128  BitMatrix RightShift() const { return ((bits << 1) & ~MaskCol<0>()); }
129  BitMatrix UpShift() const { return bits >> COLS; }
130  BitMatrix DownShift() const { return bits << COLS; }
131  BitMatrix ULShift() const { return ((bits & ~MaskCol<0>()) >> (COLS+1)); }
132  BitMatrix DLShift() const { return ((bits & ~MaskCol<0>()) << (COLS-1)); }
133  BitMatrix URShift() const { return ((bits >> (COLS-1)) & ~MaskCol<0>()); }
134  BitMatrix DRShift() const { return ((bits << (COLS+1)) & ~MaskCol<0>()); }
135 
136  // Find all points within one step of the ones on this bit matrix.
137  BitMatrix GetReach() const { return *this | LeftShift() | RightShift() | UpShift() | DownShift(); }
138 
139  // Find all points reachable from the start position.
140  BitMatrix GetRegion(size_t start_pos) const {
141  // Make sure we have a legal region, or else return an empty matrix.
142  if (start_pos < 0 || start_pos >= GetSize() || bits[start_pos] == 0) return BitMatrix();
143 
144  BitMatrix cur_region, last_region;
145  cur_region.Set(start_pos);
146 
147  while (cur_region != last_region) {
148  last_region = cur_region;
149  cur_region = *this & cur_region.GetReach();
150  }
151 
152  return cur_region;
153  }
154  BitMatrix GetRegion(size_t col, size_t row) const { return GetRegion(ToID(col,row)); }
155 
156  // Does this bit matrix represent a connected set of ones?
157  bool IsConnected() const { return GetRegion((size_t)FindBit()) == *this; }
158 
159  // Does this bit matrix have any 2x2 square of ones in it?
160  bool Has2x2() const { return (*this & UpShift() & LeftShift() & ULShift()).Any(); }
161 
162  void Print(std::ostream & os = std::cout) const {
163  for (size_t y = 0; y < ROWS; y++) {
164  for (size_t x = 0; x < COLS; x++) {
165  os << bits[ToID(x,y)];
166  }
167  os << std::endl;
168  }
169  }
170 
171  // Assignments and compound assignments
172  BitMatrix & operator=(const BitMatrix & in) { bits = in.bits; return *this; }
173  BitMatrix & operator&=(const BitMatrix & in) { bits &= in.bits; return *this; }
174  BitMatrix & operator|=(const BitMatrix & in) { bits |= in.bits; return *this; }
175  BitMatrix & operator^=(const BitMatrix & in) { bits ^= in.bits; return *this; }
176 
177  // Comparisons
178  bool operator==(const BitMatrix & in) const { return bits == in.bits; }
179  bool operator!=(const BitMatrix & in) const { return bits != in.bits; }
180 
181  // Logic operators
182  BitMatrix operator~() const { return ~bits; }
183  BitMatrix operator&(const BitMatrix & in) const { return bits & in.bits; }
184  BitMatrix operator|(const BitMatrix & in) const { return bits | in.bits; }
185  BitMatrix operator^(const BitMatrix & in) const { return bits ^ in.bits; }
186 
187  // Conversions
188  const BitSet<COLS*ROWS> & to_bitset() { return bits; }
189  };
190 }
191 
192 #endif
BitMatrix GetRegion(size_t col, size_t row) const
Definition: BitMatrix.h:154
void SetAll()
Definition: BitMatrix.h:111
const BitSet< COLS *ROWS > & to_bitset()
Definition: BitMatrix.h:188
bool Get(size_t id) const
Definition: BitMatrix.h:102
~BitMatrix()
Definition: BitMatrix.h:77
bool None() const
Definition: BitMatrix.h:98
bool any() const
Function to allow drop-in replacement with std::bitset.
Definition: BitSet.h:567
void ClearCol(size_t col)
Definition: BitMatrix.h:115
bool Any() const
Definition: BitMatrix.h:97
BitMatrix operator&(const BitMatrix &in) const
Definition: BitMatrix.h:183
size_t count() const
Function to allow drop-in replacement with std::bitset.
Definition: BitSet.h:573
BitMatrix operator~() const
Definition: BitMatrix.h:182
int FindBit() const
Definition: BitMatrix.h:124
void Print(std::ostream &os=std::cout) const
Definition: BitMatrix.h:162
bool Get(size_t col, size_t row) const
Definition: BitMatrix.h:101
void Set(size_t id)
Definition: BitMatrix.h:105
BitMatrix & operator&=(const BitMatrix &in)
Definition: BitMatrix.h:173
BitMatrix(const BitMatrix &in_matrix)
Definition: BitMatrix.h:76
size_t CountOnes() const
Definition: BitMatrix.h:119
void SetRow(size_t row)
Definition: BitMatrix.h:113
A set of simple functions to manipulate bitsets.
void Clear()
Definition: BitMatrix.h:114
bool Has2x2() const
Definition: BitMatrix.h:160
static size_t ToID(size_t col, size_t row)
Identify the ID associated with a specified row and column.
Definition: BitMatrix.h:95
BitSet & flip()
Function to allow drop-in replacement with std::bitset.
Definition: BitSet.h:576
A simple class to manage a COLS x ROWS matrix of bits.
Definition: BitMatrix.h:38
void SetCol(size_t col)
Definition: BitMatrix.h:112
BitMatrix GetReach() const
Definition: BitMatrix.h:137
bool All() const
Definition: BitMatrix.h:99
bool all() const
Function to allow drop-in replacement with std::bitset.
Definition: BitSet.h:564
static const PrintStr endl("<br>")
Pre-define emp::endl to insert a "<br>" and thus acting like a newline.
BitMatrix ULShift() const
Definition: BitMatrix.h:131
BitMatrix UpShift() const
Definition: BitMatrix.h:129
void ClearRow(size_t row)
Definition: BitMatrix.h:116
BitMatrix & operator|=(const BitMatrix &in)
Definition: BitMatrix.h:174
constexpr size_t NumCols() const
How many columns are in this matrix?
Definition: BitMatrix.h:83
A drop-in replacement for std::bitset, with additional bit magic features.
BitMatrix LeftShift() const
Definition: BitMatrix.h:127
BitMatrix()
Definition: BitMatrix.h:74
BitMatrix RightShift() const
Definition: BitMatrix.h:128
bool none() const
Function to allow drop-in replacement with std::bitset.
Definition: BitSet.h:570
static size_t ToRow(size_t id)
Identify which row a specific ID is part of.
Definition: BitMatrix.h:92
void Flip(size_t col, size_t row)
Definition: BitMatrix.h:108
static const BitSet< COLS *ROWS > & MaskRow()
Keep only a single row of values, reducing all others to zeros.
Definition: BitMatrix.h:63
static const BitSet< COLS *ROWS > & MaskCol()
Keep only a single column of values, reducing all others to zeros.
Definition: BitMatrix.h:50
int FindBit() const
Return the index of the first one in the sequence; return -1 if no ones are available.
Definition: BitSet.h:374
constexpr size_t GetSize() const
How many total cells are in this matrix?
Definition: BitMatrix.h:86
void Set(size_t col, size_t row, bool val=true)
Definition: BitMatrix.h:104
BitMatrix & operator=(const BitMatrix &in)
Definition: BitMatrix.h:172
If we are in emscripten, make sure to include the header.
Definition: array.h:37
BitMatrix(const BitSet< COLS *ROWS > &in_bits)
Definition: BitMatrix.h:75
BitMatrix GetRegion(size_t start_pos) const
Definition: BitMatrix.h:140
void Unset(size_t col, size_t row)
Definition: BitMatrix.h:106
BitMatrix DRShift() const
Definition: BitMatrix.h:134
void Unset(size_t id)
Definition: BitMatrix.h:107
static size_t ToCol(size_t id)
Identify which column a specific ID is part of.
Definition: BitMatrix.h:89
constexpr size_t NumRows() const
How many rows are in this matrix?
Definition: BitMatrix.h:80
void Flip(size_t id)
Definition: BitMatrix.h:109
void SetAll()
Set all bits to one.
Definition: BitSet.h:327
bool operator==(const BitMatrix &in) const
Definition: BitMatrix.h:178
BitMatrix operator|(const BitMatrix &in) const
Definition: BitMatrix.h:184
BitMatrix operator^(const BitMatrix &in) const
Definition: BitMatrix.h:185
BitMatrix DownShift() const
Definition: BitMatrix.h:130
bool IsConnected() const
Definition: BitMatrix.h:157
BitMatrix DLShift() const
Definition: BitMatrix.h:132
BitMatrix & operator^=(const BitMatrix &in)
Definition: BitMatrix.h:175
void Clear()
Set all bits to zero.
Definition: BitSet.h:324
constexpr BitSet< COLS *ROWS > Mask() const
Definition: BitMatrix.h:44
BitMatrix URShift() const
Definition: BitMatrix.h:133
bool operator!=(const BitMatrix &in) const
Definition: BitMatrix.h:179