Tulip  4.10.0
Better Visualization Through Research
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
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 #include <set>
24 #include <iostream>
25 #include <tulip/Iterator.h>
26 
27 namespace tlp {
28 
29 // define a minimal structure to hold the state of an id manager
30 struct IdManagerState {
31  // the first id in use
32  unsigned int firstId;
33  // the next id to use
34  unsigned int nextId;
35  // the unused ids between the first and the next
36  std::set<unsigned int> freeIds;
37 
38  IdManagerState(): firstId(0), nextId(0) {}
39 };
40 
41 // define a class to iterate through the non free ids
42 // of an IdManagerState
43 template <typename TYPE>
44 class IdManagerIterator:public Iterator<TYPE> {
45 
46 private:
47  unsigned int current;
48  unsigned int last;
49  const std::set<unsigned int>& freeIds;
50  std::set<unsigned int>::const_iterator it;
51 
52 public:
53 
54  IdManagerIterator(const IdManagerState& infos):
55  current(infos.firstId), last(infos.nextId), freeIds(infos.freeIds), it(freeIds.begin()) {
56 #ifdef TLP_NO_IDS_REUSE
57  std::set<unsigned int>::const_reverse_iterator itr;
58  itr = freeIds.rbegin();
59 
60  while(itr != freeIds.rend() && (*itr) == last - 1) {
61  --last;
62  ++itr;
63  }
64 
65 #endif
66  }
67  ~IdManagerIterator() {}
68 
69  bool hasNext() {
70  return (current < last);
71  }
72 
73  TYPE next() {
74  unsigned int tmp = current;
75  ++current;
76 
77  while(it != freeIds.end()) {
78  if (current < *it) return (TYPE) tmp;
79 
80  ++current;
81  ++it;
82  }
83 
84  return (TYPE) tmp;
85  }
86 };
87 
88 /// class for the management of the identifiers : node, edge
89 class TLP_SCOPE IdManager {
90 
91  // the current state
92  IdManagerState state;
93 
94 public:
95  IdManager() {}
96  /**
97  * Returns true if the id is not used else false.
98  */
99  bool is_free(unsigned int) const;
100  /**
101  * Free the id given in parameter.
102  */
103  void free(const unsigned int);
104  /**
105  * Returns a new id.
106  */
107  unsigned int get() {
108 #ifdef TLP_NO_IDS_REUSE
109  return state.nextId++;
110 #else
111  return state.firstId ?
112  --state.firstId :
113  (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 
169 ///@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