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