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