Tulip  5.2.0
Large graphs analysis and drawing
IdManager.h
1 /*
2  *
3  * This file is part of Tulip (http://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 
33 namespace tlp {
34 
35 // define a minimal structure to hold the state of an id manager
36 struct 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
49 template <typename TYPE>
50 class IdManagerIterator : public Iterator<TYPE> {
51 
52 private:
53  unsigned int current;
54  unsigned int last;
55  const std::set<unsigned int> &freeIds;
56  std::set<unsigned int>::const_iterator it;
57 
58 public:
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
95 class TLP_SCOPE IdManager {
96 
97  // the current state
98  IdManagerState state;
99 
100 public:
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 
167 std::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
171 template <typename ID_TYPE>
172 class 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 
190 public:
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
344 template <typename ID_TYPE>
345 class SGraphIdContainer : public std::vector<ID_TYPE> {
346  // used to store the elts positions in the vector
347  MutableContainer<unsigned int> pos;
348 
349 public:
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 loger 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 }
404 
405 #endif
406 
407 ///@endcond
void TLP_PARALLEL_MAP_INDICES(size_t maxIdx, const IdxFunction &idxFunction)
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.