1 /** 2 * 3 * Copyright (c) 2005-2021 by Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU) 4 * info_at_agrum_dot_org 5 * 6 * This library is free software: you can redistribute it and/or modify 7 * it under the terms of the GNU Lesser General Public License as published by 8 * the Free Software Foundation, either version 3 of the License, or 9 * (at your option) any later version. 10 * 11 * This library is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU Lesser General Public License for more details. 15 * 16 * You should have received a copy of the GNU Lesser General Public License 17 * along with this library. If not, see <http://www.gnu.org/licenses/>. 18 * 19 */ 20 21 22 /** @file 23 * @brief Inline implementation of the base node set class for graphs 24 * 25 * @author Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU) 26 * 27 */ 28 29 // to ease parsing by IDE 30 #include <agrum/tools/graphs/parts/nodeGraphPart.h> 31 32 namespace gum { 33 34 //=================NODEGRAPHPARTITERATOR============================ 35 36 /// ensure that the nodeId is either end() either a valid NodeId validate_()37 INLINE void NodeGraphPartIterator::validate_() noexcept { 38 valid_ = false; 39 40 if (pos_ > nodes_->bound()) { pos_ = nodes_->bound(); } 41 42 while (pos_ < nodes_->bound()) { 43 if (!nodes_->_inHoles_(pos_)) { 44 valid_ = true; 45 return; 46 } 47 48 ++pos_; 49 } 50 } 51 52 /// default constructor 53 INLINE NodeGraphPartIterator(const NodeGraphPart & nodes)54 NodeGraphPartIterator::NodeGraphPartIterator(const NodeGraphPart& nodes) noexcept : 55 nodes_(&nodes) { 56 GUM_CONSTRUCTOR(NodeGraphPartIterator); 57 } 58 59 /// copy constructor NodeGraphPartIterator(const NodeGraphPartIterator & it)60 INLINE NodeGraphPartIterator::NodeGraphPartIterator(const NodeGraphPartIterator& it) noexcept : 61 nodes_(it.nodes_), pos_(it.pos_), valid_(it.valid_) { 62 GUM_CONS_CPY(NodeGraphPartIterator); 63 } 64 65 /// move constructor NodeGraphPartIterator(NodeGraphPartIterator && it)66 INLINE NodeGraphPartIterator::NodeGraphPartIterator(NodeGraphPartIterator&& it) noexcept : 67 nodes_(it.nodes_), pos_(it.pos_), valid_(it.valid_) { 68 GUM_CONS_MOV(NodeGraphPartIterator); 69 } 70 71 /// destructor ~NodeGraphPartIterator()72 INLINE NodeGraphPartIterator::~NodeGraphPartIterator() noexcept { 73 GUM_DESTRUCTOR(NodeGraphPartIterator); 74 } 75 76 /// copy assignment operator 77 INLINE NodeGraphPartIterator& 78 NodeGraphPartIterator::operator=(const NodeGraphPartIterator& it) noexcept { 79 nodes_ = it.nodes_; 80 pos_ = it.pos_; 81 valid_ = it.valid_; 82 GUM_OP_CPY(NodeGraphPartIterator); 83 84 return *this; 85 } 86 87 /// move assignment operator 88 INLINE NodeGraphPartIterator& 89 NodeGraphPartIterator::operator=(NodeGraphPartIterator&& it) noexcept { 90 nodes_ = it.nodes_; 91 pos_ = it.pos_; 92 valid_ = it.valid_; 93 GUM_OP_MOV(NodeGraphPartIterator); 94 95 return *this; 96 } 97 98 /// checks whether two iterators point toward the same node 99 INLINE 100 bool NodeGraphPartIterator::operator==(const NodeGraphPartIterator& it) const noexcept { 101 return ((pos_ == it.pos_) && (valid_ == it.valid_) && (nodes_ == it.nodes_)); 102 } 103 104 /// checks whether two iterators point toward different nodes 105 INLINE 106 bool NodeGraphPartIterator::operator!=(const NodeGraphPartIterator& it) const noexcept { 107 return !(operator==(it)); 108 } 109 110 /// increment the iterator 111 INLINE NodeGraphPartIterator& NodeGraphPartIterator::operator++() noexcept { 112 ++pos_; 113 validate_(); 114 return *this; 115 } 116 117 /// dereferencing operator 118 INLINE NodeId NodeGraphPartIterator::operator*() const { 119 if (!valid_) { GUM_ERROR(UndefinedIteratorValue, "This iterator is not valid !") } 120 121 return pos_; 122 } 123 124 // unsafe private method setPos_(NodeId id)125 INLINE void NodeGraphPartIterator::setPos_(NodeId id) noexcept { 126 pos_ = id; 127 128 if (pos_ >= nodes_->bound()) { 129 pos_ = nodes_->bound(); 130 valid_ = false; 131 } else { 132 valid_ = nodes_->exists(pos_); 133 } 134 } 135 136 //=================NODEGRAPHPARTITERATORSAFE============================ 137 138 /// default constructor 139 INLINE NodeGraphPartIteratorSafe(const NodeGraphPart & nodes)140 NodeGraphPartIteratorSafe::NodeGraphPartIteratorSafe(const NodeGraphPart& nodes) : 141 NodeGraphPartIterator(nodes) { 142 GUM_CONNECT(*const_cast< NodeGraphPart* >(&nodes), 143 onNodeDeleted, 144 *this, 145 NodeGraphPartIteratorSafe::whenNodeDeleted); 146 GUM_CONSTRUCTOR(NodeGraphPartIteratorSafe); 147 } 148 149 /// copy constructor 150 INLINE NodeGraphPartIteratorSafe(const NodeGraphPartIteratorSafe & it)151 NodeGraphPartIteratorSafe::NodeGraphPartIteratorSafe(const NodeGraphPartIteratorSafe& it) : 152 NodeGraphPartIterator(it) { 153 GUM_CONNECT(*const_cast< NodeGraphPart* >(nodes_), 154 onNodeDeleted, 155 *this, 156 NodeGraphPartIteratorSafe::whenNodeDeleted); 157 GUM_CONS_CPY(NodeGraphPartIteratorSafe); 158 } 159 160 /// move constructor 161 INLINE NodeGraphPartIteratorSafe(NodeGraphPartIteratorSafe && it)162 NodeGraphPartIteratorSafe::NodeGraphPartIteratorSafe(NodeGraphPartIteratorSafe&& it) : 163 NodeGraphPartIterator(std::move(it)) { 164 GUM_CONNECT(*const_cast< NodeGraphPart* >(nodes_), 165 onNodeDeleted, 166 *this, 167 NodeGraphPartIteratorSafe::whenNodeDeleted); 168 GUM_CONS_MOV(NodeGraphPartIteratorSafe); 169 } 170 171 /// destructor ~NodeGraphPartIteratorSafe()172 INLINE NodeGraphPartIteratorSafe::~NodeGraphPartIteratorSafe() { 173 GUM_DESTRUCTOR(NodeGraphPartIteratorSafe); 174 } 175 176 /// copy assignment operator 177 INLINE NodeGraphPartIteratorSafe& 178 NodeGraphPartIteratorSafe::operator=(const NodeGraphPartIteratorSafe& it) { 179 // avoid self assignment 180 if (&it != this) { 181 NodeGraphPartIterator::operator=(it); 182 Listener:: operator=(it); 183 GUM_OP_CPY(NodeGraphPartIteratorSafe); 184 } 185 186 return *this; 187 } 188 189 /// move assignment operator 190 INLINE NodeGraphPartIteratorSafe& 191 NodeGraphPartIteratorSafe::operator=(NodeGraphPartIteratorSafe&& it) { 192 // avoid self assignment 193 if (&it != this) { 194 NodeGraphPartIterator::operator=(std::move(it)); 195 Listener:: operator=(std::move(it)); 196 GUM_OP_MOV(NodeGraphPartIteratorSafe); 197 } 198 199 return *this; 200 } 201 202 //=================NODEGRAPHPART============================ 203 204 INLINE NodeGraphPart& NodeGraphPart::operator=(const NodeGraphPart& p) { 205 // avoid self assignment 206 if (this != &p) { populateNodes(p); } 207 208 return *this; 209 } 210 nextNodeId()211 INLINE NodeId NodeGraphPart::nextNodeId() const { 212 NodeId next = 0; 213 214 // return the first hole if holes exist 215 if (_holes_ && (!_holes_->empty())) 216 next = *(_holes_->begin()); 217 else // in other case 218 next = _boundVal_; 219 220 return next; 221 } 222 223 // _holes_ is assumed to be not nullptr and id is assumed to be in _holes_ _eraseHole_(NodeId id)224 INLINE void NodeGraphPart::_eraseHole_(NodeId id) { 225 _holes_->erase(id); 226 227 if (_holes_->empty()) { 228 delete _holes_; 229 _holes_ = nullptr; 230 } 231 } 232 233 // warning: do not try to use function addNodeWithId ( const NodeId id ) within 234 // function addNodeWithId(): as both functions are virtual, this may create 235 // bugs within the graphs hierarchy (i.e., virtual functions calling 236 // recursively 237 // each other along the hierarchy) that are not easy to debug. addNode()238 INLINE NodeId NodeGraphPart::addNode() { 239 NodeId newNode; 240 241 // fill the first hole if holes exist 242 if (_holes_ && (!_holes_->empty())) { 243 newNode = *(_holes_->begin()); 244 _eraseHole_(newNode); 245 } else { 246 newNode = _boundVal_; 247 ++_boundVal_; 248 _updateEndIteratorSafe_(); 249 } 250 251 GUM_EMIT1(onNodeAdded, newNode); 252 253 return newNode; 254 } 255 addNodes(Size N)256 INLINE std::vector< NodeId > NodeGraphPart::addNodes(Size N) { 257 std::vector< NodeId > v; 258 v.reserve(N); 259 for (Idx i = 0; i < N; i++) 260 v.push_back(this->addNode()); 261 return v; 262 } 263 264 sizeNodes()265 INLINE Size NodeGraphPart::sizeNodes() const { 266 return (_holes_) ? (_boundVal_ - _holes_->size()) : _boundVal_; 267 } 268 size()269 INLINE Size NodeGraphPart::size() const { return sizeNodes(); } 270 existsNode(const NodeId node)271 INLINE bool NodeGraphPart::existsNode(const NodeId node) const { 272 if (node >= _boundVal_) return false; 273 274 return (!_inHoles_(node)); 275 } 276 exists(const NodeId node)277 INLINE bool NodeGraphPart::exists(const NodeId node) const { return existsNode(node); } 278 eraseNode(const NodeId node)279 INLINE void NodeGraphPart::eraseNode(const NodeId node) { 280 if (!existsNode(node)) return; 281 282 _addHole_(node); 283 284 GUM_EMIT1(onNodeDeleted, node); 285 } 286 emptyNodes()287 INLINE bool NodeGraphPart::emptyNodes() const { return (sizeNodes() == 0); } 288 empty()289 INLINE bool NodeGraphPart::empty() const { return emptyNodes(); } 290 bound()291 INLINE NodeId NodeGraphPart::bound() const { return _boundVal_; } 292 clearNodes()293 INLINE void NodeGraphPart::clearNodes() { _clearNodes_(); } 294 295 // warning: clear is an alias for clearNodes but it should never be the case 296 // that the code of clear is just a call to clearNodes: as both methods are 297 // virtual, this could induce bugs within the graphs hierarchy (i.e., virtual 298 // functions calling recursively each other along the hierarchy) that are not 299 // easy to debug. Hence, the code of clearNodes should be duplicated here. clear()300 INLINE void NodeGraphPart::clear() { _clearNodes_(); } 301 beginSafe()302 INLINE NodeGraphPartIteratorSafe NodeGraphPart::beginSafe() const { 303 NodeGraphPartIteratorSafe it(*this); 304 it.validate_(); // stop the iterator at the first not-in-holes 305 return it; 306 } 307 _updateEndIteratorSafe_()308 INLINE void NodeGraphPart::_updateEndIteratorSafe_() { _endIteratorSafe_.setPos_(_boundVal_); } 309 endSafe()310 INLINE const NodeGraphPartIteratorSafe& NodeGraphPart::endSafe() const noexcept { 311 return _endIteratorSafe_; 312 } 313 begin()314 INLINE NodeGraphPartIterator NodeGraphPart::begin() const noexcept { 315 NodeGraphPartIterator it(*this); 316 it.validate_(); // stop the iterator at the first not-in-holes 317 return it; 318 } 319 end()320 INLINE const NodeGraphPartIterator& NodeGraphPart::end() const noexcept { 321 return _endIteratorSafe_; 322 } 323 324 INLINE bool NodeGraphPart::operator==(const NodeGraphPart& p) const { 325 if (_boundVal_ != p._boundVal_) return false; 326 327 if (_holes_) 328 if (p._holes_) 329 return (*_holes_ == *p._holes_); 330 else 331 return false; 332 else if (p._holes_) 333 return false; 334 335 return true; 336 } 337 338 INLINE bool NodeGraphPart::operator!=(const NodeGraphPart& p) const { return !operator==(p); } 339 asNodeSet()340 INLINE NodeSet NodeGraphPart::asNodeSet() const { 341 NodeSet son(sizeNodes()); 342 343 if (!empty()) { 344 for (NodeId n = 0; n < _boundVal_; ++n) { 345 if (!_inHoles_(n)) son.insert(n); 346 } 347 } 348 349 return son; 350 } 351 nodes()352 INLINE const NodeGraphPart& NodeGraphPart::nodes() const { 353 return *(static_cast< const NodeGraphPart* >(this)); 354 } 355 _inHoles_(NodeId id)356 INLINE bool NodeGraphPart::_inHoles_(NodeId id) const { return _holes_ && _holes_->contains(id); } 357 358 /// @return the size of _holes_ _sizeHoles_()359 INLINE Size NodeGraphPart::_sizeHoles_() const { return _holes_ ? _holes_->size() : (Size)0; } 360 361 } /* namespace gum */ 362