Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
IdManager.h
1/*
2 *
3 * This file is part of Tulip (https://tulip.labri.fr)
4 *
5 * Authors: David Auber and the Tulip development Team
6 * from LaBRI, University of Bordeaux
7 *
8 * Tulip is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU Lesser General Public License
10 * as published by the Free Software Foundation, either version 3
11 * of the License, or (at your option) any later version.
12 *
13 * Tulip is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16 * See the GNU General Public License for more details.
17 *
18 */
19///@cond DOXYGEN_HIDDEN
20
21#ifndef _TULIPIDMANAGER_H
22#define _TULIPIDMANAGER_H
23
24#include <algorithm>
25#include <climits>
26#include <set>
27#include <vector>
28#include <iostream>
29#include <tulip/MutableContainer.h>
30#include <tulip/StlIterator.h>
31#include <tulip/ParallelTools.h>
32
33namespace tlp {
34
35// define a minimal structure to hold the state of an id manager
36struct IdManagerState {
37 // the first id in use
38 unsigned int firstId;
39 // the next id to use
40 unsigned int nextId;
41 // the unused ids between the first and the next
42 std::set<unsigned int> freeIds;
43
44 IdManagerState() : firstId(0), nextId(0) {}
45};
46
47// define a class to iterate through the non free ids
48// of an IdManagerState
49template <typename TYPE>
50class IdManagerIterator : public Iterator<TYPE> {
51
52private:
53 unsigned int current;
54 unsigned int last;
55 const std::set<unsigned int> &freeIds;
56 std::set<unsigned int>::const_iterator it;
57
58public:
59 IdManagerIterator(const IdManagerState &info)
60 : current(info.firstId), last(info.nextId), freeIds(info.freeIds), it(freeIds.begin()) {
61#ifdef TLP_NO_IDS_REUSE
62 std::set<unsigned int>::const_reverse_iterator itr;
63 itr = freeIds.rbegin();
64
65 while (itr != freeIds.rend() && (*itr) == last - 1) {
66 --last;
67 ++itr;
68 }
69
70#endif
71 }
72 ~IdManagerIterator() override {}
73
74 bool hasNext() override {
75 return (current < last);
76 }
77
78 TYPE next() override {
79 unsigned int tmp = current;
80 ++current;
81
82 while (it != freeIds.end()) {
83 if (current < *it)
84 return static_cast<TYPE>(tmp);
85
86 ++current;
87 ++it;
88 }
89
90 return static_cast<TYPE>(tmp);
91 }
92};
93
94/// class for the management of the identifiers
95class TLP_SCOPE IdManager {
96
97 // the current state
98 IdManagerState state;
99
100public:
101 IdManager() {}
102 /**
103 * Returns true if the id is not used else false.
104 */
105 bool is_free(unsigned int) const;
106 /**
107 * Free the id given in parameter.
108 */
109 void free(const unsigned int);
110 /**
111 * Returns a new id.
112 */
113 unsigned int get() {
114#ifdef TLP_NO_IDS_REUSE
115 return state.nextId++;
116#else
117 return state.firstId ? --state.firstId : (state.freeIds.empty() ? state.nextId++ : getFreeId());
118#endif
119 }
120 /**
121 * Returns the first id of a range of nb new ids.
122 */
123 unsigned int getFirstOfRange(unsigned nb) {
124 unsigned int first = state.nextId;
125 state.nextId += nb;
126 return first;
127 }
128
129#ifndef TLP_NO_IDS_REUSE
130 /**
131 * remove and return the first available id from the free ids
132 */
133 unsigned int getFreeId();
134#endif
135 /**
136 * assuming the given id is free.
137 * remove it from free ids
138 * (used to ensure the same id when loading a graph with subgraphs)
139 */
140 void getFreeId(unsigned int id);
141 /**
142 * return the current state of the Id manager
143 */
144 const IdManagerState &getState() {
145 return state;
146 }
147 /**
148 * restore a saved state, used by push/pop
149 */
150 void restoreState(const IdManagerState &info) {
151 state = info;
152 }
153 /**
154 * Returns an iterator on all the used ids. Warning, if
155 * the idManager is modified (free, get) this iterator
156 * will be invalid.
157 */
158 template <typename TYPE>
159 Iterator<TYPE> *getIds() const {
160 return new IdManagerIterator<TYPE>(state);
161 }
162
163 friend std::ostream &operator<<(std::ostream &, const IdManager &);
164 friend class IdManagerTest;
165};
166
167std::ostream &operator<<(std::ostream &, const IdManager &);
168
169// class for the management of the identifiers: node, edge
170// or any type which can be easily cast in an unsigned int
171template <typename ID_TYPE>
172class TLP_SCOPE IdContainer : public std::vector<ID_TYPE> {
173 // the number of free ids
174 unsigned int nbFree;
175 // the position of the ids
176 std::vector<unsigned int> pos;
177
178 inline ID_TYPE *&beginPtr() {
179 return reinterpret_cast<ID_TYPE **>(this)[0];
180 }
181
182 inline ID_TYPE *&sizePtr() {
183 return reinterpret_cast<ID_TYPE **>(this)[1];
184 }
185
186 inline void setSize(unsigned int size) {
187 sizePtr() = beginPtr() + size;
188 }
189
190public:
191 IdContainer() : std::vector<ID_TYPE>(), nbFree(0) {}
192
193 // reset
194 void clear() {
195 std::vector<ID_TYPE>::clear();
196 pos.clear();
197 nbFree = 0;
198 }
199
200 // reserve enough room to store nb elts
201 void reserve(size_t nb) {
202 std::vector<ID_TYPE>::reserve(nb);
203 pos.reserve(nb);
204 }
205
206 // return whether there is free ids or not
207 inline bool hasFree() const {
208 return nbFree > 0;
209 }
210
211 // return the number of elts in the free storage
212 inline unsigned int numberOfFree() const {
213 return nbFree;
214 }
215
216 // return whether the id exist or not
217 inline bool isElement(ID_TYPE elt) const {
218 unsigned int id = elt;
219 return id < pos.size() && pos[id] != UINT_MAX;
220 }
221
222 // return an iterator on the existing elts
223 inline Iterator<ID_TYPE> *getElts() const {
224 return new StlIterator<ID_TYPE, typename std::vector<ID_TYPE>::const_iterator>(this->begin(),
225 this->end());
226 }
227
228 // return the position of an existing elt
229 inline unsigned int getPos(ID_TYPE elt) const {
230 assert(isElement(elt));
231 return pos[elt];
232 }
233
234 // return a new elt
235 ID_TYPE get() {
236 unsigned int freePos = this->size();
237
238 if (nbFree) {
239 setSize(freePos + 1);
240 --nbFree;
241 } else {
242 this->resize(freePos + 1);
243 pos.resize(freePos + 1);
244 (*this)[freePos] = ID_TYPE(freePos);
245 }
246
247 ID_TYPE elt = (*this)[freePos];
248 pos[elt] = freePos;
249 return elt;
250 }
251
252 // return the index of the first elt of a range of nb new elts
253 unsigned int getFirstOfRange(unsigned int nb) {
254 unsigned int freePos = this->size();
255 unsigned int i = std::min(nbFree, nb);
256
257 if (i) {
258 setSize(freePos + i);
259 nbFree -= i;
260 }
261
262 if (i < nb) {
263 this->resize(freePos + nb);
264 pos.resize(freePos + nb);
265
266 for (; i < nb; ++i)
267 (*this)[freePos + i] = ID_TYPE(freePos + i);
268 }
269
270 for (i = 0; i < nb; ++i)
271 pos[(*this)[freePos + i]] = freePos + i;
272
273 return freePos;
274 }
275
276 // push the elt in the free storage
277 void free(ID_TYPE elt) {
278 unsigned int curPos = pos[elt];
279 unsigned int lastPos = this->size() - 1;
280
281 ID_TYPE tmp;
282
283 if (curPos != lastPos) {
284 // swap the elt with the last one
285 tmp = (*this)[lastPos];
286 (*this)[lastPos] = (*this)[curPos];
287 assert((*this)[curPos] == elt);
288 (*this)[curPos] = tmp;
289 pos[tmp] = curPos;
290 }
291
292 pos[elt] = UINT_MAX;
293
294 if (lastPos) {
295 // lastPos is now the beginning
296 // of the freed elts
297 ++nbFree;
298 setSize(lastPos);
299 } else {
300 // all elts are freed so forget them
301 nbFree = 0;
302 setSize(0);
303 pos.resize(0);
304 }
305 }
306
307 // copy this into ids
308 void copyTo(IdContainer<ID_TYPE> &ids) const {
309 unsigned int sz = std::vector<ID_TYPE>::size() + nbFree;
310 ids.reserve(sz);
311 memcpy(ids.data(), this->data(), sz * sizeof(ID_TYPE));
312 ids.pos.resize(sz);
313 memcpy(ids.pos.data(), this->pos.data(), sz * sizeof(unsigned int));
314 ids.nbFree = nbFree;
315 ids.setSize(std::vector<ID_TYPE>::size());
316 }
317
318 // swap two elts
319 void swap(ID_TYPE a, ID_TYPE b) {
320 assert(isElement(a));
321 assert(isElement(b));
322 unsigned int pa = pos[a];
323 unsigned int tmp = pos[b];
324 pos[b] = pa;
325 pos[a] = tmp;
326 (*this)[pa] = b;
327 (*this)[tmp] = a;
328 }
329
330 // recompute elts positions
331 void reIndex() {
332 unsigned int nbElts = this->size();
333 TLP_PARALLEL_MAP_INDICES(nbElts, [&](unsigned int i) { pos[(*this)[i]] = i; });
334 }
335
336 // ascending sort
337 void sort() {
338 std::sort(this->begin(), this->end());
339 reIndex();
340 }
341};
342
343// used as nodes/edges container in GraphView
344template <typename ID_TYPE>
345class SGraphIdContainer : public std::vector<ID_TYPE> {
346 // used to store the elts positions in the vector
347 MutableContainer<unsigned int> pos;
348
349public:
350 SGraphIdContainer() {
351 pos.setAll(UINT_MAX);
352 }
353 inline bool isElement(ID_TYPE elt) const {
354 return (pos.get(elt) != UINT_MAX);
355 }
356
357 inline unsigned int getPos(ID_TYPE elt) const {
358 assert(isElement(elt));
359 return pos.get(elt);
360 }
361
362 void add(ID_TYPE elt) {
363 assert(!isElement(elt));
364 // put the elt at the end
365 pos.set(elt, this->size());
366 this->push_back(elt);
367 }
368
369 void clone(const std::vector<ID_TYPE> &elts) {
370 static_cast<std::vector<ID_TYPE> &>(*this) = elts;
371 unsigned int nb = elts.size();
372
373 for (unsigned int i = 0; i < nb; ++i)
374 pos.set(elts[i], i);
375 }
376
377 void remove(ID_TYPE elt) {
378 assert(isElement(elt));
379 // get the position of the elt to remove
380 unsigned int i = pos.get(elt);
381 assert(i < this->size());
382 // put the last elt at the freed position
383 unsigned int last = this->size() - 1;
384
385 if (i < last)
386 pos.set(((*this)[i] = (*this)[last]), i);
387
388 // resize the container
389 this->resize(last);
390 // the elt no longer exist in the container
391 pos.set(elt, UINT_MAX);
392 }
393
394 // ascending sort
395 void sort() {
396 std::sort(this->begin(), this->end());
397 unsigned int nbElts = this->size();
398
399 for (unsigned int i = 0; i < nbElts; ++i)
400 pos.set((*this)[i], i);
401 }
402};
403} // namespace tlp
404
405#endif
406
407///@endcond
std::ostream & operator<<(std::ostream &os, const Array< T, N > &array)
operator << stream operator to easily print an array, or save it to a file.