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