Tulip  4.6.0
Better Visualization Through Research
library/tulip-core/include/tulip/IdManager.h
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
 All Classes Files Functions Variables Enumerations Enumerator Properties