vcglib: container_allocation_table.h Source File

00001 /****************************************************************************
00002 * VCGLib                                                            o o     *
00003 * Visual and Computer Graphics Library                            o     o   *
00004 *                                                                _   O  _   *
00005 * Copyright(C) 2004                                                \/)\/    *
00006 * Visual Computing Lab                                            /\/|      *
00007 * ISTI - Italian National Research Council                           |      *
00008 *                                                                    \      *
00009 * All rights reserved.                                                      *
00010 *                                                                           *
00011 * This program is free software; you can redistribute it and/or modify      *   
00012 * it under the terms of the GNU General Public License as published by      *
00013 * the Free Software Foundation; either version 2 of the License, or         *
00014 * (at your option) any later version.                                       *
00015 *                                                                           *
00016 * This program is distributed in the hope that it will be useful,           *
00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of            *
00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             *
00019 * GNU General Public License (http://www.gnu.org/licenses/gpl.txt)          *
00020 * for more details.                                                         *
00021 *                                                                           *
00022 ****************************************************************************/
00023 
00024   
00025 #ifndef __VCGLIB_CAT__
00026 #define __VCGLIB_CAT__
00027 
00028 #include <vector>
00029 #include <map>
00030 #include <string>
00031 #include <list>
00032 #include <algorithm>
00033 #include <assert.h>
00034 #include <vcg/container/entries_allocation_table.h>
00035 
00036 namespace vcg {
00051                 struct CATBaseBase{
00052 
00053                 };
00054 
00055 
00056 
00057 template <typename STL_CONT>
00058                                 class CATBase: public CATBaseBase{
00059 public:
00060 typedef  typename STL_CONT::value_type ValueType;
00061 
00062 virtual void Resort(ValueType*,ValueType*) =0;
00063 virtual void Remove(const STL_CONT&) = 0;
00064 virtual void AddDataElem(ValueType*,int)=0;
00065 virtual void Resize(ValueType*,int)=0;
00066 
00067 public:
00068 // ID serves as a type trait. 
00069 static int & Id(){
00070                         static int id=0;
00071                         return id;
00072                         }       
00073 };
00074 
00077 template <typename STL_CONT, class ENTRY_TYPE>
00078 class CATEntry: public CATBase<STL_CONT>{
00079 public:
00080 typedef  typename STL_CONT::value_type ValueType;
00081 typedef  ENTRY_TYPE EntryType;
00082 
00083 CATEntry(){if(Id()==0){
00084                                                         Id() = CATBase<STL_CONT>::Id()+1;
00085                                                         CATBase<STL_CONT>::Id() = Id();
00086                                                         }
00087                                         }
00088 
00089 
00090 static unsigned int Ord(const ValueType *);
00091 static ENTRY_TYPE & GetEntry(typename STL_CONT::value_type*pt);
00092 
00093 static  void  Insert( STL_CONT & c,bool cond=false );                           // insert a vector to trace
00094 virtual void    Remove(  const STL_CONT  &      c);                                                             // remove the container c
00095 static  void    RemoveIfEmpty(  const STL_CONT  &       c);                                     // remove the container c
00096 static  void    Remove(  ValueType  *   v);                                                                               // remove the container that contains v
00097 
00098 virtual void Resort(    ValueType* old_start,                   // resort the allocation table
00099                                                                                         ValueType* new_start);                  // after a container was moved
00100         
00101 protected:
00102 
00103 static std::list<ENTRY_TYPE >& AT(){                                                    // tallocation table
00104 static std::list<ENTRY_TYPE > allocation_table; 
00105                 return allocation_table;
00106         }
00107 static bool & UTD(){
00108         static bool upToDate;                                                                                                           // true if Lower() and  Upper() 
00109         return upToDate;                                                                                                                                // are up to date
00110         }
00111 
00112 static ValueType *& Lower() {
00113         static ValueType * lower;                                                                                       // pointer to the first element
00114         return lower;                                                                                                                                           // of the last container accessed
00115         }
00116 static ValueType *& Upper() {
00117         static ValueType * upper;                                                                                       // pointer to the first element
00118         return upper;                                                                                                                                           // if the container next to the last accessed
00119 }               
00120 
00121 static typename std::list<ENTRY_TYPE>::iterator  & Curr(){              // container that was last accessed
00122         static typename std::list<ENTRY_TYPE>::iterator currEntry;
00123         return currEntry;
00124 }
00125 
00126 
00127 static bool IsTheSameAsLast(const ValueType *pt);       // true if pt is in the  container
00128                                                                                                                                                                                         // that was accessed last
00129 static void Update(const ValueType*);                                                   // set Upper() e Lower() 
00130 static typename std::list<ENTRY_TYPE>::iterator FindBase(const ValueType * pt); 
00131                                                                                                                                                                                         // find the container that contains pt (naive)
00132 virtual  void  AddDataElem(typename STL_CONT::value_type * pt,int n);// add n element to the auxiliary data
00133 virtual  void  Resize(typename STL_CONT::value_type * pt,int n);// resize the  auxiliary data
00134 
00135 public:
00136 static int & Id(){                                                                                                                      // unique identifier of the istance
00137                 static int id=0;                                                                                                                // (used as type trait)
00138                 return id;
00139                 }
00140 };
00141 
00142 // --------------------------- CATEntry: implementation --------------------
00143 // derivazione fatta per i membri Occ (Optional Component Compact)
00144 template <typename STL_CONT, class ENTRY_TYPE>
00145 unsigned int CATEntry<STL_CONT,ENTRY_TYPE>::
00146 
00147 Ord(const ValueType * pt)
00148 {
00149         Update(pt);
00150         return (pt-Lower());
00151 }
00152 
00153 
00154 template <typename STL_CONT, class ENTRY_TYPE>
00155 typename std::list<ENTRY_TYPE>::iterator CATEntry<STL_CONT,ENTRY_TYPE>::
00156 
00157 FindBase(const ValueType * pt)
00158 {
00159 typename std::list<ENTRY_TYPE>::iterator ite,curr_base,_;
00160 ite = AT().begin();
00161 curr_base = AT().end();
00162 
00163 for(;ite != AT().end();ite++)
00164         if( pt < (*ite).Start())
00165                 return curr_base;
00166         else
00167                 curr_base = ite;
00168 
00169 return curr_base;
00170 }
00171 
00172 
00173 template <typename STL_CONT, class ENTRY_TYPE>
00174  bool CATEntry< STL_CONT, ENTRY_TYPE>::
00175  
00176 IsTheSameAsLast(const ValueType * pt)
00177 {
00178 return ( UTD() && ( !(Lower()> pt)) && (pt < Upper()) );
00179 }
00180 
00181 template <typename STL_CONT, class ENTRY_TYPE>
00182 void CATEntry< STL_CONT, ENTRY_TYPE>::
00183 
00184 Update(const ValueType * pt)
00185 {
00186 if(!IsTheSameAsLast(pt)){
00187         typename std::list<ENTRY_TYPE>::iterator lower_ite,upper_ite;
00188         lower_ite = FindBase(pt);
00189 
00190         assert( lower_ite!=AT().end());
00191 
00192         Lower() = (*lower_ite).Start();
00193         if( (*lower_ite).Start() == AT().back().Start())
00194                 Upper() = (ValueType *) 0xffffffff;
00195         else
00196         {
00197                 upper_ite = lower_ite;  ++upper_ite;    
00198                 Upper() = (*upper_ite).Start();
00199         }
00200         
00201         Curr() = lower_ite;
00202         UTD() = true;
00203         }
00204 }
00205 
00206 template <typename STL_CONT, class ENTRY_TYPE>
00207 void CATEntry< STL_CONT,  ENTRY_TYPE>::
00208 Resort(ValueType* old_start,ValueType* new_start)
00209 {
00210 AT().sort();
00211 UTD() = false;
00212 }
00213 
00214 template <typename STL_CONT, class ENTRY_TYPE>
00215 void CATEntry<STL_CONT, ENTRY_TYPE>::
00216 
00217 Remove( const STL_CONT & c )
00218 {
00219 typename std::list<ENTRY_TYPE>::iterator ite;
00220 for(ite = AT().begin(); ite != AT().end();  ++ite)
00221         if((*ite).C() == &c)
00222                 {
00223                         AT().erase(ite);
00224                         break;
00225                 }
00226 UTD() = false;
00227 }
00228 
00229 template <typename STL_CONT, class ENTRY_TYPE>
00230 void CATEntry<STL_CONT, ENTRY_TYPE>::
00231 
00232 RemoveIfEmpty( const STL_CONT & c )
00233 {
00234 typename std::list<ENTRY_TYPE>::iterator ite;
00235 for(ite = AT().begin(); ite != AT().end();  ++ite)
00236         if((*ite).C() == &c)
00237                         if(!(*ite).Empty())
00238                                 AT().erase(ite);
00239 UTD() = false;
00240 }
00241 
00242 template <typename STL_CONT, class ENTRY_TYPE>
00243 void CATEntry<STL_CONT, ENTRY_TYPE>::
00244 
00245 Remove(ValueType  *     pt)
00246 {
00247         typename std::list<ENTRY_TYPE>::iterator lower_ite;
00248         lower_ite = FindBase(pt);
00249         AT().erase(lower_ite);
00250         UTD() = false;
00251                 
00252 }
00253 
00254 template <typename STL_CONT, class ENTRY_TYPE>
00255 void CATEntry<STL_CONT, ENTRY_TYPE>::
00256 
00257 Insert( STL_CONT & c,bool cond )
00258 {
00259 ENTRY_TYPE entry(c);
00260 typename std::list<ENTRY_TYPE>::iterator lower_ite,upper_ite;
00261 upper_ite = FindBase( c.Pointer2begin());
00262 bool isIn = (upper_ite != AT().end());
00263 if(isIn){
00264         if((*upper_ite).C() != &c )
00265                                 ++upper_ite; 
00266         else
00267                 return;
00268         }
00269 lower_ite = AT().insert(upper_ite,entry);
00270 lower_ite->Reserve(c.capacity());
00271 lower_ite->Resize(c.size());
00272 UTD() = false;
00273 }
00274 
00275 template <typename STL_CONT, class ENTRY_TYPE>
00276 ENTRY_TYPE & CATEntry<STL_CONT, ENTRY_TYPE>::
00277 GetEntry(typename STL_CONT::value_type*pt){
00278 Update(pt);
00279 return *Curr();
00280 }
00281 
00282 template <typename STL_CONT, class ENTRY_TYPE>
00283 void CATEntry<STL_CONT, ENTRY_TYPE>::
00284 
00285 AddDataElem(typename STL_CONT::value_type * pt,int n)
00286 {
00287 Update(pt);
00288 Curr()->Push_back(n);
00289 }
00290 
00291 
00292 template <typename STL_CONT, class ENTRY_TYPE>
00293 void CATEntry<STL_CONT, ENTRY_TYPE>::
00294 
00295 Resize(typename STL_CONT::value_type * pt,int n)
00296 {
00297 Update(pt);
00298 Curr()->Resize(n);
00299 }
00300 
00301 
00302 //--------------------------------------------------------------------------------------------
00303 template <typename STL_CONT,class ATTR_TYPE>
00304 class CAT:public CATEntry<STL_CONT, EntryCAT<STL_CONT,ATTR_TYPE> >{
00305 typedef typename STL_CONT::value_type ValueType;
00306 typedef CATEntry<STL_CONT, EntryCAT<STL_CONT,ATTR_TYPE> > TT;
00307 public:
00308 static ATTR_TYPE & Get(const ValueType * pt);
00309 static CAT<STL_CONT,ATTR_TYPE> * New();
00310 static CAT<STL_CONT,ATTR_TYPE> *& Instance(){ static CAT<STL_CONT,ATTR_TYPE> *  instance=NULL; return instance;}
00311 }; 
00312 //---------------------- CAT: implementation---------------------------------------------------
00313 template <typename STL_CONT, class ATTR_TYPE>
00314 ATTR_TYPE & CAT<STL_CONT,ATTR_TYPE>::
00315 
00316 Get(const ValueType * pt)
00317 {
00318 int ord = Ord(pt);
00319 return TT::Curr()->Data()[ord];
00320 }
00321 
00322 struct Env{
00323 
00324                 static std::map< std::string,CATBaseBase *> & TypeNameBounds(){
00325                                 static std::map< std::string,CATBaseBase *>  ntb; return ntb;}
00326 
00327                 template <class TYPE_1,class TYPE_2>
00328                                 static CAT<TYPE_1,TYPE_2> *  newCAT(){
00329                                 std::string n = std::string(typeid(TYPE_1).name())+std::string(typeid(TYPE_2).name());
00330                                 std::map< std::string,CATBaseBase *>::iterator ti = TypeNameBounds().find(n);
00331                                 if(ti == TypeNameBounds().end()){
00332                                                 CAT<TYPE_1,TYPE_2> * res = new CAT<TYPE_1,TYPE_2>();
00333                                                 TypeNameBounds().insert(std::pair<std::string,CATBaseBase*>(n,res));
00334                                                 return res;
00335                                 }
00336                                 else (CAT<TYPE_1,TYPE_2> *) (*ti).second;
00337                 }
00338 };
00339 
00340 template <typename STL_CONT, class ATTR_TYPE>
00341 CAT<STL_CONT,ATTR_TYPE> * CAT<STL_CONT,ATTR_TYPE>::
00342 New(){
00343         if(Instance()==NULL) 
00344                 {
00345 //               Instance() =  new CAT<STL_CONT,ATTR_TYPE>();
00346                         Instance() = Env::newCAT<STL_CONT,ATTR_TYPE>();
00347                 }
00348         return Instance();
00349         }
00350 
00351 
00352 };//end namespace vcg
00353 
00354 #endif