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 Source implementation of nodes sets
24  *
25  * @author Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU)
26  *
27  */
28 #include <agrum/tools/graphs/parts/nodeGraphPart.h>
29 
30 #ifdef GUM_NO_INLINE
31 #  include <agrum/tools/graphs/parts/nodeGraphPart_inl.h>
32 #endif   // GUM_NOINLINE
33 
34 namespace gum {
35 
36   ///////////////////// NodeGraphPart
NodeGraphPart(Size holes_size,bool holes_resize_policy)37   NodeGraphPart::NodeGraphPart(Size holes_size, bool holes_resize_policy) :
38       _holes_size_(holes_size), _holes_resize_policy_(holes_resize_policy),
39       _endIteratorSafe_(*this), _boundVal_(0) {
40     _holes_ = nullptr;
41     GUM_CONSTRUCTOR(NodeGraphPart);
42     _updateEndIteratorSafe_();
43   }
44 
NodeGraphPart(const NodeGraphPart & s)45   NodeGraphPart::NodeGraphPart(const NodeGraphPart& s) :
46       _holes_size_(s._holes_size_), _holes_resize_policy_(s._holes_resize_policy_),
47       _endIteratorSafe_(*this), _boundVal_(s._boundVal_) {
48     _holes_ = nullptr;
49 
50     if (s._holes_) _holes_ = new NodeSet(*s._holes_);
51 
52     _updateEndIteratorSafe_();
53 
54     GUM_CONS_CPY(NodeGraphPart);
55   }
56 
~NodeGraphPart()57   NodeGraphPart::~NodeGraphPart() {
58     if (_holes_) delete _holes_;
59 
60     GUM_DESTRUCTOR(NodeGraphPart);
61   }
62 
populateNodes(const NodeGraphPart & s)63   void NodeGraphPart::populateNodes(const NodeGraphPart& s) {
64     clear();   // "virtual" flush of the nodes set
65     _holes_size_          = s._holes_size_;
66     _holes_resize_policy_ = s._holes_resize_policy_;
67 
68     if (s._holes_) _holes_ = new NodeSet(*s._holes_);
69 
70     _boundVal_ = s._boundVal_;
71 
72     _updateEndIteratorSafe_();
73   }
74 
75   // id is assumed to belong to NodeGraphPart
_addHole_(NodeId node)76   void NodeGraphPart::_addHole_(NodeId node) {
77     // we assume that the node exists
78     if (node + 1 == _boundVal_) {
79       // we remove the max : no new hole and maybe a bunch of holes to remove
80       --_boundVal_;
81 
82       if (_holes_) {
83         while (_holes_->contains(_boundVal_ - 1)) {
84           // a bunch of holes to remove. We do not use inHoles for optimisation
85           // :
86           // not to repeat the test if ( _holes_) each time
87           _holes_->erase(--_boundVal_);
88         }
89 
90         if (_holes_->empty()) {
91           delete _holes_;
92           _holes_ = nullptr;
93         }
94       }
95 
96       _updateEndIteratorSafe_();
97     } else {
98       if (!_holes_) _holes_ = new NodeSet(_holes_size_, _holes_resize_policy_);
99 
100       _holes_->insert(node);
101     }
102   }
103 
toString() const104   std::string NodeGraphPart::toString() const {
105     std::stringstream s;
106     bool              first = true;
107     s << "{";
108 
109     for (NodeId id = 0; id < _boundVal_; ++id) {
110       if (_inHoles_(id)) continue;
111 
112       if (first) {
113         first = false;
114       } else {
115         s << ",";
116       }
117 
118       s << id;
119     }
120 
121     s << "}";
122 
123     return s.str();
124   }
125 
operator <<(std::ostream & stream,const NodeGraphPart & set)126   std::ostream& operator<<(std::ostream& stream, const NodeGraphPart& set) {
127     stream << set.toString();
128     return stream;
129   }
130 
addNodeWithId(const NodeId id)131   void NodeGraphPart::addNodeWithId(const NodeId id) {
132     if (id >= _boundVal_) {
133       if (id > _boundVal_) {   // we have to add holes
134         if (!_holes_) _holes_ = new NodeSet(_holes_size_, _holes_resize_policy_);
135 
136         for (NodeId i = _boundVal_; i < id; ++i)
137           _holes_->insert(i);
138       }
139 
140       _boundVal_ = id + 1;
141 
142       _updateEndIteratorSafe_();
143     } else {
144       if (_inHoles_(id)) {   // we fill a hole
145         _eraseHole_(id);
146       } else {
147         GUM_ERROR(DuplicateElement, "Id " << id << " is already used")
148       }
149     }
150 
151     GUM_EMIT1(onNodeAdded, id);
152   }
153 
_clearNodes_()154   void NodeGraphPart::_clearNodes_() {
155     NodeId bound = _boundVal_;
156     _boundVal_   = 0;
157 
158     if (onNodeDeleted.hasListener()) {
159       for (NodeId n = 0; n < bound; ++n) {
160         if (!_inHoles_(n)) GUM_EMIT1(onNodeDeleted, n);
161       }
162     }
163 
164     _updateEndIteratorSafe_();
165 
166     delete (_holes_);
167     _holes_ = nullptr;
168   }
169 
whenNodeDeleted(const void * src,NodeId id)170   void NodeGraphPartIteratorSafe::whenNodeDeleted(const void* src, NodeId id) {
171     if (id == pos_) {   // we just deleted the pos_ in NodeGraphPart
172       valid_ = false;
173     }
174 
175     if (pos_ >= nodes_->bound()) {   // moreover, it was the last position
176       pos_   = nodes_->bound();
177       valid_ = false;
178     }
179   }
180 
181 } /* namespace gum */
182