![]() |
Tulip
4.6.0
Better Visualization Through Research
|
00001 /* 00002 * 00003 * This file is part of Tulip (www.tulip-software.org) 00004 * 00005 * Authors: David Auber and the Tulip development Team 00006 * from LaBRI, University of Bordeaux 00007 * 00008 * Tulip is free software; you can redistribute it and/or modify 00009 * it under the terms of the GNU Lesser General Public License 00010 * as published by the Free Software Foundation, either version 3 00011 * of the License, or (at your option) any later version. 00012 * 00013 * Tulip is distributed in the hope that it will be useful, 00014 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00016 * See the GNU General Public License for more details. 00017 * 00018 */ 00019 ///@cond DOXYGEN_HIDDEN 00020 00021 #ifndef DOXYGEN_NOTFOR_DEVEL 00022 00023 #ifndef _TULIPIDMANAGER_H 00024 #define _TULIPIDMANAGER_H 00025 #include <set> 00026 #include <iostream> 00027 #include <tulip/Iterator.h> 00028 00029 namespace tlp { 00030 00031 // define a minimal structure to hold the state of an id manager 00032 struct IdManagerState { 00033 // the first id in use 00034 unsigned int firstId; 00035 // the next id to use 00036 unsigned int nextId; 00037 // the unused ids between the first and the next 00038 std::set<unsigned int> freeIds; 00039 00040 IdManagerState(): firstId(0), nextId(0) {} 00041 }; 00042 00043 // define a class to iterate through the non free ids 00044 // of an IdManagerState 00045 template <typename TYPE> 00046 class IdManagerIterator:public Iterator<TYPE> { 00047 00048 private: 00049 unsigned int current; 00050 unsigned int last; 00051 const std::set<unsigned int>& freeIds; 00052 std::set<unsigned int>::const_iterator it; 00053 00054 public: 00055 00056 IdManagerIterator(const IdManagerState& infos): 00057 current(infos.firstId), last(infos.nextId), freeIds(infos.freeIds), it(freeIds.begin()) { 00058 #ifdef TLP_NO_IDS_REUSE 00059 std::set<unsigned int>::const_reverse_iterator itr; 00060 itr = freeIds.rbegin(); 00061 00062 while(itr != freeIds.rend() && (*itr) == last - 1) { 00063 --last; 00064 ++itr; 00065 } 00066 00067 #endif 00068 } 00069 ~IdManagerIterator() {} 00070 00071 bool hasNext() { 00072 return (current < last); 00073 } 00074 00075 TYPE next() { 00076 unsigned int tmp = current; 00077 ++current; 00078 00079 while(it != freeIds.end()) { 00080 if (current < *it) return (TYPE) tmp; 00081 00082 ++current; 00083 ++it; 00084 } 00085 00086 return (TYPE) tmp; 00087 } 00088 }; 00089 00090 /// class for the management of the identifiers : node, edge 00091 class TLP_SCOPE IdManager { 00092 00093 // the current state 00094 IdManagerState state; 00095 00096 public: 00097 IdManager() {} 00098 /** 00099 * Returns true if the id is not used else false. 00100 */ 00101 bool is_free(unsigned int) const; 00102 /** 00103 * Free the id given in parameter. 00104 */ 00105 void free(const unsigned int); 00106 /** 00107 * Returns a new id. 00108 */ 00109 unsigned int get() { 00110 #ifdef TLP_NO_IDS_REUSE 00111 return state.nextId++; 00112 #else 00113 return state.freeIds.empty() ? state.nextId++ : getFreeId(); 00114 #endif 00115 } 00116 /** 00117 * Returns the first id of a range of nb new ids. 00118 */ 00119 unsigned int getFirstOfRange(unsigned nb) { 00120 unsigned int first = state.nextId; 00121 state.nextId += nb; 00122 return first; 00123 } 00124 00125 #ifndef TLP_NO_IDS_REUSE 00126 /** 00127 * remove and return the first available id from the free ids 00128 */ 00129 unsigned int getFreeId(); 00130 #endif 00131 /** 00132 * assuming the given id is free. 00133 * remove it from free ids 00134 * (used to ensure the same id when loading a graph with subgraphs) 00135 */ 00136 void getFreeId(unsigned int id); 00137 /** 00138 * return the current state of the Id manager 00139 */ 00140 const IdManagerState& getState() { 00141 return state; 00142 } 00143 /** 00144 * restore a saved state, used by push/pop 00145 */ 00146 void restoreState(const IdManagerState& infos) { 00147 state = infos; 00148 } 00149 /** 00150 * Returns an iterator on all the used ids. Warning, if 00151 * the idManager is modified (free, get) this iterator 00152 * will be invalid. 00153 */ 00154 template<typename TYPE> 00155 Iterator<TYPE>* getIds() const { 00156 return new IdManagerIterator<TYPE>(state); 00157 } 00158 00159 friend std::ostream& operator<<(std::ostream &, const IdManager &); 00160 friend class IdManagerTest; 00161 }; 00162 00163 std::ostream& operator<<(std::ostream &,const IdManager &); 00164 00165 } 00166 00167 #endif 00168 #endif //DOXYGEN_NOTFOR_DEVEL 00169 ///@endcond