Tulip  4.1.0
Better Visualization Through Research
 All Classes Files Functions Variables Enumerations Enumerator Properties Groups Pages
IdManager.h
1 /*
2  *
3  * This file is part of Tulip (www.tulip-software.org)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux 1 and Inria Bordeaux - Sud Ouest
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 DOXYGEN_NOTFOR_DEVEL
22 
23 #ifndef _TULIPIDMANAGER_H
24 #define _TULIPIDMANAGER_H
25 #include <set>
26 #include <iostream>
27 #include <tulip/Iterator.h>
28 
29 namespace tlp {
30 
31 // define a minimal structure to hold the state of an id manager
32 struct IdManagerState {
33  // the first id in use
34  unsigned int firstId;
35  // the next id to use
36  unsigned int nextId;
37  // the unused ids between the first and the next
38  std::set<unsigned int> freeIds;
39 
40  IdManagerState(): firstId(0), nextId(0) {}
41 };
42 
43 // define a class to iterate through the non free ids
44 // of an IdManagerState
45 template <typename TYPE>
46 class IdManagerIterator:public Iterator<TYPE> {
47 
48 private:
49  unsigned int current;
50  unsigned int last;
51  const std::set<unsigned int>& freeIds;
52  std::set<unsigned int>::const_iterator it;
53 
54 public:
55 
56  IdManagerIterator(const IdManagerState& infos):
57  current(infos.firstId), last(infos.nextId), freeIds(infos.freeIds), it(freeIds.begin()) {
58 #ifdef TLP_NO_IDS_REUSE
59  std::set<unsigned int>::const_reverse_iterator itr;
60  itr = freeIds.rbegin();
61 
62  while(itr != freeIds.rend() && (*itr) == last - 1) {
63  --last;
64  ++itr;
65  }
66 
67 #endif
68  }
69  ~IdManagerIterator() {}
70 
71  bool hasNext() {
72  return (current < last);
73  }
74 
75  TYPE next() {
76  unsigned int tmp = current;
77  ++current;
78 
79  while(it != freeIds.end()) {
80  if (current < *it) return (TYPE) tmp;
81 
82  ++current;
83  ++it;
84  }
85 
86  return (TYPE) tmp;
87  }
88 };
89 
90 /// class for the management of the identifiers : node, edge
91 class TLP_SCOPE IdManager {
92 
93  // the current state
94  IdManagerState state;
95 
96 public:
97  IdManager() {}
98  /**
99  * Returns true if the id is not used else false.
100  */
101  bool is_free(unsigned int) const;
102  /**
103  * Free the id given in parameter.
104  */
105  void free(const unsigned int);
106  /**
107  * Returns a new id.
108  */
109  unsigned int get() {
110 #ifdef TLP_NO_IDS_REUSE
111  return state.nextId++;
112 #else
113  return state.freeIds.empty() ? state.nextId++ : getFreeId();
114 #endif
115  }
116  /**
117  * Returns the first id of a range of nb new ids.
118  */
119  unsigned int getFirstOfRange(unsigned nb) {
120  unsigned int first = state.nextId;
121  state.nextId += nb;
122  return first;
123  }
124 
125 #ifndef TLP_NO_IDS_REUSE
126  /**
127  * remove and return the first available id from the free ids
128  */
129  unsigned int getFreeId();
130 #endif
131  /**
132  * assuming the given id is free.
133  * remove it from free ids
134  * (used to ensure the same id when loading a graph with subgraphs)
135  */
136  void getFreeId(unsigned int id);
137  /**
138  * return the current state of the Id manager
139  */
140  const IdManagerState& getState() {
141  return state;
142  }
143  /**
144  * restore a saved state, used by push/pop
145  */
146  void restoreState(const IdManagerState& infos) {
147  state = infos;
148  }
149  /**
150  * Returns an iterator on all the used ids. Warning, if
151  * the idManager is modified (free, get) this iterator
152  * will be invalid.
153  */
154  template<typename TYPE>
155  Iterator<TYPE>* getIds() const {
156  return new IdManagerIterator<TYPE>(state);
157  }
158 
159  friend std::ostream& operator<<(std::ostream &, const IdManager &);
160  friend class IdManagerTest;
161 };
162 
163 std::ostream& operator<<(std::ostream &,const IdManager &);
164 
165 }
166 
167 #endif
168 #endif //DOXYGEN_NOTFOR_DEVEL
169 ///@endcond