21 #ifndef _TULIPIDMANAGER_H 22 #define _TULIPIDMANAGER_H 29 #include <tulip/MutableContainer.h> 30 #include <tulip/StlIterator.h> 31 #include <tulip/ParallelTools.h> 36 struct IdManagerState {
42 std::set<unsigned int> freeIds;
44 IdManagerState() : firstId(0), nextId(0) {}
49 template <
typename TYPE>
50 class IdManagerIterator :
public Iterator<TYPE> {
55 const std::set<unsigned int> &freeIds;
56 std::set<unsigned int>::const_iterator it;
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();
65 while (itr != freeIds.rend() && (*itr) == last - 1) {
72 ~IdManagerIterator()
override {}
74 bool hasNext()
override {
75 return (current < last);
78 TYPE next()
override {
79 unsigned int tmp = current;
82 while (it != freeIds.end()) {
84 return static_cast<TYPE
>(tmp);
90 return static_cast<TYPE
>(tmp);
95 class TLP_SCOPE IdManager {
105 bool is_free(
unsigned int)
const;
109 void free(
const unsigned int);
114 #ifdef TLP_NO_IDS_REUSE 115 return state.nextId++;
117 return state.firstId ? --state.firstId : (state.freeIds.empty() ? state.nextId++ : getFreeId());
123 unsigned int getFirstOfRange(
unsigned nb) {
124 unsigned int first = state.nextId;
129 #ifndef TLP_NO_IDS_REUSE 133 unsigned int getFreeId();
140 void getFreeId(
unsigned int id);
144 const IdManagerState &getState() {
150 void restoreState(
const IdManagerState &info) {
158 template <
typename TYPE>
159 Iterator<TYPE> *getIds()
const {
160 return new IdManagerIterator<TYPE>(state);
163 friend std::ostream &
operator<<(std::ostream &,
const IdManager &);
164 friend class IdManagerTest;
167 std::ostream &
operator<<(std::ostream &,
const IdManager &);
171 template <
typename ID_TYPE>
172 class TLP_SCOPE IdContainer :
public std::vector<ID_TYPE> {
176 std::vector<unsigned int> pos;
178 inline ID_TYPE *&beginPtr() {
179 return reinterpret_cast<ID_TYPE **
>(
this)[0];
182 inline ID_TYPE *&sizePtr() {
183 return reinterpret_cast<ID_TYPE **
>(
this)[1];
186 inline void setSize(
unsigned int size) {
187 sizePtr() = beginPtr() + size;
191 IdContainer() :
std::vector<ID_TYPE>(), nbFree(0) {}
195 std::vector<ID_TYPE>::clear();
201 void reserve(
size_t nb) {
202 std::vector<ID_TYPE>::reserve(nb);
207 inline bool hasFree()
const {
212 inline unsigned int numberOfFree()
const {
217 inline bool isElement(ID_TYPE elt)
const {
218 unsigned int id = elt;
219 return id < pos.size() && pos[id] != UINT_MAX;
223 inline Iterator<ID_TYPE> *getElts()
const {
224 return new StlIterator<ID_TYPE, typename std::vector<ID_TYPE>::const_iterator>(this->begin(),
229 inline unsigned int getPos(ID_TYPE elt)
const {
230 assert(isElement(elt));
236 unsigned int freePos = this->size();
239 setSize(freePos + 1);
242 this->resize(freePos + 1);
243 pos.resize(freePos + 1);
244 (*this)[freePos] = ID_TYPE(freePos);
247 ID_TYPE elt = (*this)[freePos];
253 unsigned int getFirstOfRange(
unsigned int nb) {
254 unsigned int freePos = this->size();
255 unsigned int i = std::min(nbFree, nb);
258 setSize(freePos + i);
263 this->resize(freePos + nb);
264 pos.resize(freePos + nb);
267 (*
this)[freePos + i] = ID_TYPE(freePos + i);
270 for (i = 0; i < nb; ++i)
271 pos[(*
this)[freePos + i]] = freePos + i;
277 void free(ID_TYPE elt) {
278 unsigned int curPos = pos[elt];
279 unsigned int lastPos = this->size() - 1;
283 if (curPos != lastPos) {
285 tmp = (*this)[lastPos];
286 (*this)[lastPos] = (*this)[curPos];
287 assert((*
this)[curPos] == elt);
288 (*this)[curPos] = tmp;
308 void copyTo(IdContainer<ID_TYPE> &ids)
const {
309 unsigned int sz = std::vector<ID_TYPE>::size() + nbFree;
311 memcpy(ids.data(), this->data(), sz *
sizeof(ID_TYPE));
313 memcpy(ids.pos.data(), this->pos.data(), sz *
sizeof(
unsigned int));
315 ids.setSize(std::vector<ID_TYPE>::size());
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];
332 unsigned int nbElts = this->size();
338 std::sort(this->begin(), this->end());
344 template <
typename ID_TYPE>
345 class SGraphIdContainer :
public std::vector<ID_TYPE> {
347 MutableContainer<unsigned int> pos;
350 SGraphIdContainer() {
351 pos.setAll(UINT_MAX);
353 inline bool isElement(ID_TYPE elt)
const {
354 return (pos.get(elt) != UINT_MAX);
357 inline unsigned int getPos(ID_TYPE elt)
const {
358 assert(isElement(elt));
362 void add(ID_TYPE elt) {
363 assert(!isElement(elt));
365 pos.set(elt, this->size());
366 this->push_back(elt);
369 void clone(
const std::vector<ID_TYPE> &elts) {
370 static_cast<std::vector<ID_TYPE> &
>(*this) = elts;
371 unsigned int nb = elts.size();
373 for (
unsigned int i = 0; i < nb; ++i)
377 void remove(ID_TYPE elt) {
378 assert(isElement(elt));
380 unsigned int i = pos.get(elt);
381 assert(i < this->size());
383 unsigned int last = this->size() - 1;
386 pos.set(((*
this)[i] = (*
this)[last]), i);
391 pos.set(elt, UINT_MAX);
396 std::sort(this->begin(), this->end());
397 unsigned int nbElts = this->size();
399 for (
unsigned int i = 0; i < nbElts; ++i)
400 pos.set((*
this)[i], i);
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.