dune-grid  2.2.0
utility/persistentcontainer.hh
Go to the documentation of this file.
00001 #ifndef DUNE_PERSISTENTCONTAINER_HH
00002 #define DUNE_PERSISTENTCONTAINER_HH
00003 
00004 #include <cassert>
00005 #include <map>
00006 #include <vector>
00007 
00008 #include <dune/common/misc.hh>
00009 #include <dune/common/forloop.hh>
00010 #include <dune/grid/common/capabilities.hh>
00011 
00012 namespace Dune
00013 {
00042   template < class Grid, class Data, class Allocator=std::allocator<Data> >  
00043   class PersistentContainer;
00044 
00048   template <class Grid, class Index, class Vector>  
00049   class PersistentContainerVector
00050   {
00051   public:  
00052     typedef typename Vector::value_type Data;
00053     typedef Grid GridType;
00054   protected:
00055     const int codim_;
00056     const Index& index_;
00057     const double overEstimate_;
00058     Vector data_;
00059     
00060   public:  
00062     typedef typename GridType :: template Codim< 0 > :: Entity ElementType; 
00063 
00065     typedef typename Vector :: iterator Iterator ;
00067     typedef typename Vector :: const_iterator ConstIterator ;
00068 
00070     //         store data on entities of given codim using index to store data in vector.
00071     //         The overEstimate parameter can be used to allocate more memory than
00072     //         required to store the data.
00073     PersistentContainerVector( const GridType& grid, const int codim,
00074                                const Index& index,
00075                                const double overEstimate,
00076                                const typename Vector::allocator_type &allocator )
00077       : codim_( codim )
00078       , index_( index )
00079       , overEstimate_( overEstimate )   // this is not yet the right approach - will be revised
00080       , data_( index.size( codim ), Data(), allocator )
00081     {
00082     }
00083 
00085     PersistentContainerVector( const PersistentContainerVector& other ) 
00086       : codim_( other.codim_ )
00087       , index_( other.index_ )
00088       , overEstimate_( other.overEstimate_ )
00089       , data_( other.data_ )  
00090     {}
00091 
00093     const Index& index()
00094     {
00095       return index_;
00096     }
00097 
00099     template <class Entity> 
00100     Data& operator [] (const Entity& entity ) 
00101     { 
00102       assert( Entity :: codimension == codim_ );
00103       assert( (typename Index::IndexType) index_.index( entity ) < (typename Index::IndexType) data_.size() );
00104       return data_[ index_.index( entity ) ];
00105     }
00106 
00108     template <class Entity> 
00109     const Data& operator [] (const Entity& entity ) const
00110     { 
00111       assert( Entity :: codimension == codim_ );
00112       assert( (typename Index::IndexType) index_.index( entity ) < (typename Index::IndexType) data_.size() );
00113       return data_[ index_.index( entity ) ];
00114     }
00115 
00117     Data& operator () (const ElementType& element, const int subEntity ) 
00118     {
00119       assert( (typename Index::IndexType) index_.subIndex( element, subEntity, codim_ ) < (typename Index::IndexType) data_.size() );
00120       return data_[ index_.subIndex( element, subEntity, codim_ ) ];
00121     }
00122 
00124     const Data& operator () (const ElementType& element, const int subEntity ) const 
00125     {
00126       assert( (typename Index::IndexType) index_.subIndex( element, subEntity, codim_ ) < (typename Index::IndexType) data_.size() );
00127       return data_[ index_.subIndex( element, subEntity, codim_ ) ];
00128     }
00129 
00131     Iterator begin() 
00132     {
00133       return data_.begin();
00134     }
00135 
00137     ConstIterator begin() const
00138     {
00139       return data_.begin();
00140     }
00141 
00143     Iterator end() 
00144     {
00145       return data_.end();
00146     }
00147 
00149     ConstIterator end() const
00150     {
00151       return data_.end();
00152     }
00153 
00155     size_t size() const { return data_.size(); }
00156 
00158     void reserve( ) // need a better name
00159     {
00160       if( (typename Index::IndexType) index_.size( codim_ ) > (typename Index::IndexType) data_.size() ) 
00161         update( );
00162     }
00163 
00165     void clear( )
00166     {
00167       // clear all entries 
00168       data_.clear();
00169       // resize with new default value
00170       const size_t newSize = index_.size( codim_ );
00171       data_.resize( newSize, Data() );
00172     }
00173 
00175     void update( )
00176     { // this could be more sophisticated (although std::vector is not stupid and
00177       // overestimated on its own...
00178       const size_t newSize = index_.size( codim_ );
00179       if (newSize < data_.capacity())
00180         data_.resize(newSize, Data() );
00181       else
00182       {
00183         data_.reserve(newSize*overEstimate_);
00184         data_.resize(newSize, Data() );
00185       }
00186     }
00187   };
00188 
00192   template <class Grid, class Id, class Map>
00193   class PersistentContainerMap
00194   {
00195     typedef PersistentContainerMap< Grid, Id, Map > ThisType;
00196 
00197   protected:
00198     typedef typename Map :: mapped_type Data;
00199     typedef typename Id :: IdType  IdType;
00200     typedef Grid GridType;
00201     const GridType& grid_;
00202     const int codim_;
00203     const Id& id_;
00204     mutable Map data_;
00205 
00206     typedef typename Map :: iterator iterator ;
00207     typedef typename Map :: const_iterator const_iterator ;
00208 
00209     template <class D, class IteratorType >
00210     struct DataExtractor ;
00211 
00212     // Data type for iterator 
00213     template <class D>
00214     struct DataExtractor< D, iterator > 
00215     {
00216       typedef D Type ;
00217     };
00218 
00219     // Data type for const iterator 
00220     template <class D>
00221     struct DataExtractor< D, const_iterator > 
00222     {
00223       typedef const D Type ;
00224     };
00225 
00226     template <class IteratorType>
00227     class MyIterator
00228     {
00229       IteratorType it_;
00230     public: 
00231       // get correct data type (const or non-const)
00232       typedef typename DataExtractor<Data, IteratorType> :: Type value_type ;
00233 
00234       MyIterator(const IteratorType& it) : it_( it ) {}
00235       MyIterator(const MyIterator& other) : it_( other.it_ ) {}
00236 
00237       bool operator == (const MyIterator& other) const { return it_ == other.it_; }
00238       bool operator != (const MyIterator& other) const  { return it_ != other.it_; }
00239 
00240       MyIterator& operator ++ () 
00241       {
00242         ++it_;
00243         return *this;
00244       }
00245       value_type& operator * () { return (*it_).second; }
00246       value_type* operator -> () { return &((*it_).second); }
00247       MyIterator& operator = (const MyIterator& other) 
00248       {
00249         it_ = other.it_;
00250         return *this;
00251       }
00252     };
00253 
00254     template< int codim , bool gridHasCodim >
00255     struct AdaptCodimBase
00256     {
00257       static void apply ( ThisType &container, const Data& value , const int myCodim)
00258       {
00259         if( codim == myCodim )
00260           container.template adaptCodim< codim > ( value );
00261       }
00262     };
00263 
00264     template< int codim >
00265     struct AdaptCodimBase< codim, false >
00266     {
00267       static void apply ( ThisType &container, const Data& value , const int myCodim)
00268       {
00269       }
00270     };
00271 
00272     template< int codim >
00273     struct AdaptCodim
00274       : public AdaptCodimBase< codim, Capabilities :: hasEntity < GridType, codim > :: v >
00275     {
00276     };
00277 
00278   public:  
00279     typedef typename GridType :: template Codim< 0 > :: Entity ElementType; 
00280     typedef MyIterator< iterator > Iterator;
00281     typedef MyIterator< const_iterator > ConstIterator;
00282 
00284     //
00285     //         Container is to be used to store data on entities of given codim using id to store data in map.
00286     PersistentContainerMap( const GridType& grid, const int codim, const Id& id, 
00287                             const typename Map::key_compare& comp,
00288                             const typename Map::allocator_type &allocator )
00289       : grid_( grid )
00290       , codim_( codim )
00291       , id_( id )
00292       , data_(comp,allocator)
00293     {
00294     }
00296     //  unordered_map the constructor taking only an allocator is not available that is 
00297     //  why this constructor is added)
00298     //
00299     //         Container is to be used to store data on entities of given codim using id to store data in map.
00300     PersistentContainerMap( const GridType& grid, const int codim, const Id& id)
00301       : grid_( grid )
00302       , codim_( codim )
00303       , id_( id )
00304       , data_()
00305     {
00306     }
00307 
00309     PersistentContainerMap( const PersistentContainerMap& other ) 
00310       : grid_( other.grid_ )
00311       , codim_( other.codim_ )
00312       , id_( other.id_ )
00313       , data_( other.data_ )  
00314     {}
00315 
00317     template <class Entity> 
00318     Data& operator [] (const Entity& entity ) 
00319     { 
00320       assert( Entity :: codimension == codim_ );
00321       return data_[ id_.id( entity ) ];
00322     }
00323 
00325     template <class Entity> 
00326     const Data& operator [] (const Entity& entity ) const
00327     { 
00328       assert( Entity :: codimension == codim_ );
00329       return data_[ id_.id( entity ) ];
00330     }
00331 
00333     Data& operator () (const ElementType& element, const int subEntity ) 
00334     {
00335       return data_[ id_.subId( element, subEntity, codim_ ) ];
00336     }
00337 
00339     const Data& operator () (const ElementType& element, const int subEntity ) const 
00340     {
00341       return data_[ id_.subId( element, subEntity, codim_ ) ];
00342     }
00343 
00345     Iterator begin() 
00346     {
00347       return Iterator( data_.begin() );
00348     }
00349 
00351     ConstIterator begin() const
00352     {
00353       return ConstIterator( data_.begin() );
00354     }
00355 
00357     Iterator end() 
00358     {
00359       return Iterator( data_.end() );
00360     }
00361 
00363     ConstIterator end() const
00364     {
00365       return ConstIterator( data_.end() );
00366     }
00367 
00369     size_t size() const { return data_.size(); }
00370 
00372     void reserve()
00373     {
00374     }
00375 
00377     void clear( )
00378     {
00379       data_.clear();
00380     }
00381 
00383     void update( )
00384     { // this version could be implemented differently by only compressing
00385       update( Data() );
00386     }
00387   protected:  
00389     void update( const Data& value )
00390     {
00391       // loop over all codimensions (needed to make codim_ static)
00392       ForLoop< AdaptCodim, 0, GridType :: dimension > :: apply( *this, value, codim_ );
00393     }
00394 
00395     template <int codim> 
00396     void adaptCodim( const Data& value )
00397     {
00398       assert( codim_ == codim );
00399       // create empty map and swap it with current map (no need to copy twice)
00400       Map oldData;
00401       std::swap( oldData, data_ );
00402 
00403       const iterator olddataend = oldData.end();
00404       typedef typename GridType :: template Codim< codim > :: LevelIterator LevelIterator ;
00405       typedef typename LevelIterator :: Entity  Entity; 
00406       for(int l = 0; l <= grid_.maxLevel(); ++ l) 
00407       {
00408         const LevelIterator endit = grid_.template lend< codim > ( l );   
00409         for( LevelIterator it = grid_.template lbegin< codim > ( l ); it != endit; ++ it )
00410         {
00411           const Entity& entity = * it ;
00412           const IdType id = id_.id( entity );
00413           Data& data = data_[ id ];
00414           iterator entry = oldData.find( id );
00415           if( entry != olddataend )
00416             data = (*entry).second;
00417         }
00418       }
00419     }
00420   };
00421 
00422   // PersistentContainer (default is to use PersistentContainerMap)
00423   // -------------------
00424   template < class Grid, class Data, class Allocator>  
00425   class PersistentContainer
00426   : public PersistentContainerMap< Grid, typename Grid::Traits::LocalIdSet, 
00427              std::map<const typename Grid::Traits::LocalIdSet::IdType, Data, 
00428                       std::less<const typename Grid::Traits::LocalIdSet::IdType>,
00429                       typename Allocator::template rebind<typename Grid::Traits::LocalIdSet::IdType>::other > >
00430   {
00431   public:  
00432     typedef Grid GridType;
00433   protected:  
00434     typedef typename Grid::Traits::LocalIdSet IdSet;
00435     typedef typename IdSet::IdType IdType;
00436     typedef typename Allocator::template rebind<IdType>::other IdAllocator;
00437     typedef std::map<const IdType, Data, std::less<const IdType>,
00438                      IdAllocator> Map;
00439     typedef PersistentContainerMap< Grid, IdSet, Map > BaseType;
00440 
00441   public:
00444     PersistentContainer ( const GridType &grid, const int codim, const Allocator &allocator=Allocator() )
00445     : BaseType( grid, codim, grid.localIdSet(), std::less<const IdType>(), allocator )
00446     {}
00447   };
00448 
00449 #if 0 // the following implementation can be used for a grid providing a hash for the id type
00450 #include <unordered_map>
00451   template < class MyGrid, class Data, class Allocator >  
00452   class PersistentContainer
00453   : public PersistentContainerMap< MyGrid, typename MyGrid::Traits::LocalIdSet, 
00454              std::unordered_map<const typename MyGrid::Traits::LocalIdSet::IdType, Data, 
00455                       std::hash<typename MyGrid::Traits::LocalIdSet::IdType>,
00456                       std::equal_to<const typename MyGrid::Traits::LocalIdSet::IdType>, Allocator> >
00457   {
00458     typedef MyGrid GridType;
00459     typedef typename GridType::Traits::LocalIdSet IdSet;
00460     typedef typename IdSet::IdType IdType;
00461     typedef std::unordered_map<const IdType, Data, std::hash<IdType>, std::equal_to<const IdType>, Allocator> Map;
00462     typedef PersistentContainerMap< GridType, IdSet, Map > BaseType;
00463 
00464   public:
00470     PersistentContainer ( const GridType &grid, const int codim, const Allocator &allocator=Allocator() )
00471     : BaseType( grid, codim, grid.localIdSet() ) 
00472     {}
00473   };
00474 #endif
00475 } // end namespace Dune
00476 
00477 #endif // end DUNE_PERSISTENTCONTAINER_HH