next up previous
Next: Efficiency Up: Generic Components for Grid Previous: Generic Components


A Case Study: Grid Functions

The implementation of a grid function depends crucially of the representation of the corresponding element type. If the elements of that type are numbered consecutively, for example if vertices are stored in an array (random-access sequence), it is possible to use STL vectors for the corresponding grid function. On the other hand, if no such enumeration is available (for example, if the corresponding elements are not permanently stored at all), we can resort to hash tables or balanced trees, depending on whether there can be defined a hash function or a total order on the element type.

We use element traits to provide the necessary information in a uniform way:

template<class E>
struct elem_traits {
   typedef grid_t;
   typedef handle_t;  // e.g. int
   typedef elem_t;    // == E
   typedef elem_tag;  // kind of elem., 
                      // e.g. vertex_tag
   typedef elem_iter; // sequence it. of grid_t

   typedef hasher_t;    // e.g. hash<handle_t>

   static size_type size     (grid_t const&);
   static elem_iter FirstElem(grid_t const&);
   static handle_t  handle   (elem_t const&);
};

For example, the traits contain a unified method of accessing the size of the underlying grid (size(grid_t const&)), when viewed as a container of the corresponding element type. This allows a vector-based implementation to initialize the vector size, without knowing the kind (vertex, edge or whatever) of the element:

template<class E, class T>
class grid_function_vector {
  typedef elem_traits<E>  et;
  vector<T> table;  // data
public:
 grid_function_vector(grid_t const& gg) 
    : g(&gg),  table(et::size(gg)) {}

  T& operator[](E const& e) 
   { return table[et::handle(e)];}

  /* ... */ 
};

We provide generic implementations for both the vector and hash table case. For a concrete element type E, one of these implementations can be chosen by partially specializing the grid function template for E, leaving the value type parameterized:

class MyVertex { ... };
class MyEdge   { ... };

template<class T>
grid_function<MyVertex,T> 
  : public grid_function_vector<MyVertex,T>
{ /*  repeat constructors */ };

template<class T>
grid_function<MyEdge,T> 
  : public grid_function_hash<MyEdge,T>
{ /*  repeat constructors */ };

Here, it is assumed that MyEdge is not apt for storing associated data in a vector, for instance, it might not be stored permanently.

For partial grid functions, we provide a default generic implementation, using grid_function_hash<>.


An interesting problem arises here, because we want a grid function to give iteration access to the set of elements on which it is explicitly defined. That is, a grid function on vertices should provide a type VertexIterator and a corresponding member function FirstVertex(). How can this be achieved, while minimizing code duplication?

We can implement the functionality in a generic way (e. g. using the traits to access the iteration capability of the underlying grid for total grid functions), thus obtaining ElementIterator and FirstElem(). It remains to map these to the desired names: There must be a type VertexIterator as a typedef for ElementIterator if the element type is a vertex type, and so on. This mapping is performed by the following template:

template<
 class ElemIt,   // to be renamed to
                 // VertexIterator etc.
 class ElemRge,  // range (grid fct) def. ElemIt,
                 // derives from map_elem_name<> 
                 // (Nackman-Barton trick)
 class elem_tag> // kind of element, 
                 // to be specialized
struct map_elem_name {};

// specialization for vertex
template<class ElemIt, class ElemRge>
struct map_elem_name<ElemIt, ElemRge, 
                     vertex_tag>
{ 
  typedef ElemIt  VertexIterator;
  VertexIterator  FirstVertex() const { 
    return VertexIterator( 
      static_cast<ElemRge const*>(this)->
                              FirstElem());
  }
};

// spec. for edge [not shown]
// ...

In order to inject the new specialized syntax provided by map_element_name<>, we use a sort of ``Nackman-Barton trick'' (2), deriving the final grid function from it:

template<class E, class T>
class partial_grid_function :
  // defines ElementIterator
  public grid_function_hash<E,T>, 
  public map_elem_name<
           ElementIterator,             
           partial_grid_function<E,T>,  
           elem_traits<E>::elem_tag>
{ /* constructors */ };

Further complications arise if in the 2D case, we want to provide both Edge and Facet names. Building on the techniques just described, the solution is easy, if the element traits of the 2D edge type provides edge2d_tag instead of edge_tag. We simply take the union of the corresponding map_elem_name<> specializations:

template<class ElemIt, class ElemR>
struct   map_elem_name<ElemIt,ElemR, edge2d_tag> : 
  public map_elem_name<ElemIt,ElemR, edge_tag>,
  public map_elem_name<ElemIt,ElemR, facet_tag> {};


next up previous
Next: Efficiency Up: Generic Components for Grid Previous: Generic Components
Guntram Berti 2000-09-29