PETE Tutorial 2
Integrating with the Standard Template Library

Contents:
    Introduction
    Required Definitions
    Checking Conformance
    Using Vectors with PETE
    Summary
    Source Files
        Eval.h
        VectorDefs.in
        Vector.cpp

Introduction

This tutorial shows how to use PETE to manipulate expressions involving classes taken from pre-existing libraries---in this case, from the C++ Standard Template Library (STL). The STL's vector<> class is a generic resizeable one-dimensional array, which provides fast, constant-time element access in exchange for making extension expensive. Like the STL's other container classes, vector<> is used both as-is, and as a basis for more specialized data structures, such as fixed-size queues and stacks. This tutorial will show how to use PETE to improve the performance of elementwise expressions on numeric vectors, and how to automatically determine whether two or more vectors conform (i.e. have the same length).

The source files for this example are included in the examples/Vector directory of the PETE distribution. These files are:

Required Definitions

Most of the definitions required to integrate vector<> with PETE are generated automatically by MakeOperators using the information in VectorDefs.in. The file Eval.h contains the few extra definitions that must be written by hand. Of these, the most important is the function evaluate(), on lines 102-128. This function's arguments are:

The overloaded assignment operators in VectorOperators.h must be able to find an evaluate() to match every assignment in the user's program. PETE's protocol therefore requires that every class used on the left-hand-side (LHS) in assignment expressions define a function with this name and signature.

The first thing evaluate() does is check that its target and expression conform, i.e. have the same length. It does this by applying the PETE function forEach() with a user-defined functor SizeLeaf() to the expression rhs on line 115. This functor returns true if the size of each vector<> at a leaf of PETE's expression tree matches the size of the LHS vector, which is passed as a contructor argument to the SizeLeaf. We use an AndCombine object to combine results at non-leaf nodes. In order for the right-hand-side (RHS) to conform, all leaves must agree. The definition of SizeLeaf is discussed below.

If its expression and target conform, evaluate() carries out the required assignment by looping over their mutual index range (line 110). For each index value, forEach() is used to evaluate the expression, and the given assignment operator's overloaded operator() method is used to transfer those values to the target vector. Note that a direct assignment is not used, since the assignment could involve +=, |=, or any one of C++'s other combine-and-assign operators.

The two other definitions that must be present for PETE to work with vector<> are specializations of CreateLeaf<> and LeafFunctor<>. The first one of these specializations, on lines 29-35, specifies that we store references to the vector<> objects themselves at the leaves of the PETE expression tree.

The specialization of LeafFunctor<> for vector<> and EvalLeaf1 on lines 86-95 is what tells PETE how to extract elements from a vector<>. The '1' in EvalLeaf1 indicates that the class is used to access singly-indexed structures; similar classes called EvalLeaf2, EvalLeaf3, and so on are used to access more complex classes.

Given an instance of EvalLeaf1, and a vector<>, this specialization of LeafFunctor<> defines a inline static method called apply(), which takes the index value stored in the EvalLeaf1 and fetches the corresponding vector<> element. Making this method static means that instances of LeafFunctor<> never have to be created, while making it inline ensures that the compiler will replace uses of it with its body. Thus, specializations of LeafFunctor<> present container element access to compilers in a uniform way, without any efficiency cost.

Finally, the VectorDefs.in file, which is used to generate the standard operator overloadings for vector<>, is identical to the one used in the previous tutorial, except for a substitution of vector<T[n]> for Vec3. (Recall that the [n] notation is a placeholder for an automatically generated index, so that if vector<> is used as a formal parameter two or more times, the instances will be labeled vector<T1>, vector<T2>, and so on.)

Checking Conformance

Our only remaining task is to implement the conformance checking used by evaluate(). The first step is to write a simple functor that holds a size to compare against and contains a method to return whether an argument matches this value. This is the Sizefunctor class appearing in lines 43-55 of Eval.h.

Once we've created the functor class, we then need to tell PETE how to apply it at the leaves of the expression tree. We know that these leaves can consist of either Scalar<> or vector<> objects. We therefore need to supply two LeafFunctor<> specializations. The first, in lines 57-68 works for scalars and always returns true since scalars always conform. The second, in lines 70-79, uses SizeLeaf's operator() function to compare the size of the vector<> object stored at a leaf with the reference value.

Using Vectors with PETE

The program in Vector.cpp shows how to use the definitions given above. The program starts by creating and initializing five vectors. It then calls PETE's assign() function to evaluate expressions involving vectors and scalars, and copy their values into other vectors. Note that assign() must be called by name because the STL pre-defines operator= for all of its types.

Summary

This tutorial has shown how to extend PETE so that it can handle expressions involving classes taken from a pre-existing library---in this case, the Standard Template Library. The definitions required to do this are simple and well-defined, as are the definitions required to perform other calculations (in this case, conformance checking) on those pre-defined classes.

Source Files

Eval.h


001  #ifndef PETE_EXAMPLES_VECTOR_EVAL_H
002  #define PETE_EXAMPLES_VECTOR_EVAL_H
003  
004  //-----------------------------------------------------------------------------
005  // Includes
006  //-----------------------------------------------------------------------------
007  
008  #include <iostream.h>
009  #include <vector.h>
010  #include "PETE/PETE.h"
011  #include "VectorOperators.h"
012  
013  //-----------------------------------------------------------------------------
014  // This file contains several class definitions that are used to evaluate
015  // expressions containing STL vectors.  The main function defined at the end
016  // is evaluate(lhs,op,rhs), which allows the syntax:
017  // vector<int> a,b,c;
018  // evaluate(a,OpAssign(),b+c);
019  //
020  // evaluate() is called by all the global assignment operator functions
021  // defined in VectorOperators.h
022  //-----------------------------------------------------------------------------
023  
024  //-----------------------------------------------------------------------------
025  // We need to specialize CreateLeaf<T> for our class, so that operators
026  // know what to stick in the leaves of the expression tree.
027  //-----------------------------------------------------------------------------
028  
029  template<class T, class Allocator>
030  struct CreateLeaf<vector<T, Allocator> >
031  {
032    typedef Reference<vector<T> > Leaf_t;
033    inline static
034    Leaf_t make(const vector<T, Allocator> &a) { return Leaf_t(a); }
035  };
036  
037  //-----------------------------------------------------------------------------
038  // We need to write a functor that is capable of comparing the size of
039  // the vector with a stored value. Then, we supply LeafFunctor specializations
040  // for Scalar<T> and STL vector leaves.
041  //-----------------------------------------------------------------------------
042  
043  class SizeLeaf
044  {
045  public:
046  
047    SizeLeaf(int s) : size_m(s) { }
048    SizeLeaf(const SizeLeaf &model) : size_m(model.size_m) { }
049    bool operator()(int s) const { return size_m == s; }
050    
051  private:
052    
053    int size_m;
054    
055  };
056  
057  template<class T>
058  struct LeafFunctor<Scalar<T>, SizeLeaf>
059  {
060    typedef bool Type_t;
061    inline static
062    bool apply(const Scalar<T> &, const SizeLeaf &) 
063    {
064      // Scalars always conform.
065      
066      return true;
067    }
068  };
069  
070  template<class T, class Allocator>
071  struct LeafFunctor<vector<T, Allocator>, SizeLeaf>
072  {
073    typedef bool Type_t;
074    inline static
075    bool apply(const vector<T, Allocator> &v, const SizeLeaf &s) 
076    {
077      return s(v.size());
078    }
079  };
080  
081  //-----------------------------------------------------------------------------
082  // EvalLeaf1 is used to evaluate expression with vectors.
083  // (It's already defined for Scalar values.)
084  //-----------------------------------------------------------------------------
085  
086  template<class T, class Allocator>
087  struct LeafFunctor<vector<T, Allocator>,EvalLeaf1>
088  {
089    typedef T Type_t;
090    inline static
091    Type_t apply(const vector<T, Allocator>& vec,const EvalLeaf1 &f)
092    {
093      return vec[f.val1()];
094    }
095  };
096  
097  //-----------------------------------------------------------------------------
098  // Loop over vector and evaluate the expression at each location.
099  //-----------------------------------------------------------------------------
100  
101  template<class T, class Allocator, class Op, class RHS>
102  inline void evaluate(vector<T, Allocator> &lhs, const Op &op, 
103    const Expression<RHS> &rhs)
104  {
105    if (forEach(rhs, SizeLeaf(lhs.size()), AndCombine()))
106      {
107        // We get here if the vectors on the RHS are the same size as those on
108        // the LHS.
109        
110        for (int i = 0; i < lhs.size(); ++i)
111          {
112            // The actual assignment operation is performed here.
113            // PETE operator tags all define operator() to perform the operation.
114            // (In this case op performs an assignment.) forEach is used 
115            // to compute the rhs value.  EvalLeaf1 gets the
116            // values at each node using random access, and the tag 
117            // OpCombine tells forEach to use the operator tags in the expression 
118            // to combine values together.
119  
120            op(lhs[i], forEach(rhs, EvalLeaf1(i), OpCombine()));
121          }
122      }
123    else
124      {
125        cerr << "Error: LHS and RHS don't conform." << endl;
126        exit(1);
127      }
128  }
129  
130  #endif // PETE_EXAMPLES_VECTOR_EVAL_H

VectorDefs.in


001  classes
002  -----
003    ARG   = "class T[n]"
004    CLASS = "vector<T[n]>"

Vector.cpp


001  #include "Eval.h"
002
003  int main()
004  {
005    int i;
006    const int n = 10;
007    vector<int> a, b, c, d;
008    vector<double> e(n);
009
010    for (i = 0; i < n; ++i)
011    {
012      a.push_back(i);
013      b.push_back(2*i);
014      c.push_back(3*i);
015      d.push_back(i);
016    }
017
018    assign(b, 2);
019    assign(d, a + b * c);
020    a += where(d < 30, b, c);
021
022    assign(e, c);
023    e += e - 4 / (c + 1);
024
025    for (i = 0;i < n; ++i)
026      {
027        cout << " a(" << i << ") = " << a[i]
028          << " b(" << i << ") = " << b[i]
029          << " c(" << i << ") = " << c[i]
030          << " d(" << i << ") = " << d[i]
031          << " e(" << i << ") = " << e[i]
032          << endl;
033      }
034  }


[Prev] [Home] [Next]
Copyright © Los Alamos National Laboratory 1999