libsemigroups
blocks.h
1 //
2 // libsemigroups - C++ library for semigroups and monoids
3 // Copyright (C) 2016 James D. Mitchell
4 //
5 // This program is free software: you can redistribute it and/or modify
6 // it under the terms of the GNU General Public License as published by
7 // the Free Software Foundation, either version 3 of the License, or
8 // (at your option) any later version.
9 //
10 // This program is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU General Public License for more details.
14 //
15 // You should have received a copy of the GNU General Public License
16 // along with this program. If not, see <http://www.gnu.org/licenses/>.
17 //
18 
19 // This file contains the declaration of a blocks class, which is needed by the
20 // bipartitions code.
21 
22 #ifndef LIBSEMIGROUPS_SRC_BLOCKS_H_
23 #define LIBSEMIGROUPS_SRC_BLOCKS_H_
24 
25 #include <algorithm>
26 #include <functional>
27 #include <vector>
28 
29 #include "libsemigroups-debug.h"
30 
31 namespace libsemigroups {
32 
44 
45  class Blocks {
46  public:
50  Blocks() : _blocks(nullptr), _lookup(nullptr), _nr_blocks(0), _rank(0) {}
51 
65  Blocks(std::vector<u_int32_t>* blocks, std::vector<bool>* lookup)
66  : _blocks(blocks), _lookup(lookup), _nr_blocks(), _rank(UNDEFINED) {
67  LIBSEMIGROUPS_ASSERT(_blocks->size() != 0);
68  _nr_blocks = *(std::max_element(_blocks->begin(), _blocks->end())) + 1;
69  LIBSEMIGROUPS_ASSERT(_nr_blocks == _lookup->size());
70  }
71 
92  Blocks(std::vector<u_int32_t>* blocks,
93  std::vector<bool>* lookup,
94  u_int32_t nr_blocks)
95  : _blocks(blocks),
96  _lookup(lookup),
97  _nr_blocks(nr_blocks),
98  _rank(UNDEFINED) {
99  LIBSEMIGROUPS_ASSERT(_blocks->size() != 0);
100  LIBSEMIGROUPS_ASSERT(_nr_blocks == _lookup->size());
101  }
102 
105  Blocks& operator=(Blocks const& copy) = delete;
106 
111  Blocks(Blocks const& copy);
112 
117  delete _blocks;
118  delete _lookup;
119  }
120 
126  bool operator==(const Blocks& that) const;
127 
132  bool operator<(const Blocks& that) const;
133 
138  inline u_int32_t degree() const {
139  return (_nr_blocks == 0 ? 0 : _blocks->size());
140  }
141 
146  inline u_int32_t block(size_t pos) const {
147  LIBSEMIGROUPS_ASSERT(pos < _blocks->size());
148  return (*_blocks)[pos];
149  }
150 
157  inline bool is_transverse_block(size_t index) const {
158  LIBSEMIGROUPS_ASSERT(index < _nr_blocks);
159  return (*_lookup)[index];
160  }
161 
167  // FIXME better to have lookup_begin/end methods
168  inline std::vector<bool> const* lookup() const {
169  return _lookup;
170  }
171 
176  inline u_int32_t nr_blocks() const {
177  return _nr_blocks;
178  }
179 
184  u_int32_t rank();
185 
190  size_t hash_value() const;
191 
195  inline typename std::vector<u_int32_t>::const_iterator cbegin() const {
196  LIBSEMIGROUPS_ASSERT(_blocks != nullptr);
197  return _blocks->cbegin();
198  }
199 
203  inline typename std::vector<u_int32_t>::const_iterator cend() const {
204  LIBSEMIGROUPS_ASSERT(_blocks != nullptr);
205  return _blocks->cend();
206  }
207 
208  private:
209  std::vector<u_int32_t>* _blocks;
210  std::vector<bool>* _lookup;
211  u_int32_t _nr_blocks;
212  u_int32_t _rank;
213  static u_int32_t const UNDEFINED = std::numeric_limits<u_int32_t>::max();
214  };
215 } // namespace libsemigroups
216 
217 #endif // LIBSEMIGROUPS_SRC_BLOCKS_H_
Blocks()
A constructor.
Definition: blocks.h:50
~Blocks()
Default destructor.
Definition: blocks.h:116
std::vector< u_int32_t >::const_iterator cbegin() const
Returns a const_iterator pointing to the index of the first block.
Definition: blocks.h:195
Class for signed partitions of the set .
Definition: blocks.h:45
Blocks(std::vector< u_int32_t > *blocks, std::vector< bool > *lookup, u_int32_t nr_blocks)
A constructor.
Definition: blocks.h:92
bool operator==(const Blocks &that) const
Returns true if this equals that.
Definition: blocks.cc:48
bool is_transverse_block(size_t index) const
Returns true if the block with index index is transverse.
Definition: blocks.h:157
size_t hash_value() const
Returns a hash value for a this.
Definition: blocks.cc:85
u_int32_t nr_blocks() const
Returns the number of blocks in the Blocks object.
Definition: blocks.h:176
Namespace for everything in the libsemigroups library.
Definition: blocks.cc:32
Blocks & operator=(Blocks const &copy)=delete
The assignment operator is deleted for Blocks to avoid unintended copying.
u_int32_t rank()
Returns the number of signed (transverse) blocks in this.
Definition: blocks.cc:78
u_int32_t block(size_t pos) const
Returns the index of the block containing pos.
Definition: blocks.h:146
Blocks(std::vector< u_int32_t > *blocks, std::vector< bool > *lookup)
A constructor.
Definition: blocks.h:65
std::vector< bool > const * lookup() const
Returns a pointer to the lookup table for block indices.
Definition: blocks.h:168
std::vector< u_int32_t >::const_iterator cend() const
Returns a const_iterator referring to past-the-end of the last block.
Definition: blocks.h:203
u_int32_t degree() const
Returns the degree of a Blocks object.
Definition: blocks.h:138
bool operator<(const Blocks &that) const
Returns true if this is less than that.
Definition: blocks.cc:59