[boost] GTL redesign and review process

From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2008-05-05 02:08:43

I thought I'd update those who are interested in on my progress
redesigning the generic interfaces of my geometry type system.

After implementing compile time accessors in the point_concept class and
noticing that specializing them required explicit specialization of all
possible values of the template parameter I realized that this won't
work for more general interfaces.  Specifically, polygons require
iterator semantics at their interfaces.  That means that the arguments
to the set() interface of a polygon_concept would need to be templated
for the iterator type, since that function should take an iterator
range.  Since functions cannot be partially specialized I moved the
accessors back into the point_traits<T> stuct, where it is the struct
that is specialized, and the functions can keep their template parameter
lists when the user specialized the traits for their type.  This however
led to a erroneous attempt to wrap the point_traits accessor with a
templated function (such as a wrapper in the point_concept struct).  In
the example below, I show a free function wrapper.  Directly
instantiating and calling the point_traits<T>::get<int>(T) function
compiles, but calling the free function wrapper does not compile and
gives an error about operator<.  

//demo point type
struct point_data {
        int coords_[2];
        int get(int orient) const { return coords_[orient]; }
        typedef int coordinate_type;
};

template <typename T>
struct point_traits {
  typedef typename T::coordinate_type coordinate_type;

  template<int orient>
  static inline coordinate_type get(const T& point) {
    return point.get(orient);
  }

};

template <int orient, typename T>
typename point_traits<T>::coordinate_type get(const T& point) {
        return point_traits<T>::get<orient>(point);
}

int main() {
        point_data pt;
        //this line compiles
        int value0 = point_traits<point_data>::get<0>(pt);
        //this line does not compile
        int value = get<0>(pt);
        return 0;
}

Note, if the free function directly uses the API of the data type it
compiles, but as I explained initially, I need the indirection of going
through the point_traits struct to allow specialization without getting
burned by the language disallowing partial specialization of functions.
This leaves me in something of a pickle.  Because it was what I wanted
to do anyway in the first place, my solution is to take the orient
parameter out of the template list and make it runtime.  The compiler
readily accepts that syntax.  After rewriting the example code that way,
and getting it compiling and working satisfactorily, I was very pleased
to notice that all of the code that looked like:
  if(orient == HORIOZNTAL) return get<HORIZONTAL>(point); 
  return get<VERTICAL>(point);
was gone, and access through any path of indirection would result in no
if statements needing to be executed.  I did implement a compile time
accessor in the point concept (it calls the runtime one in the
point_traits struct) but it doesn't make a lot of sense to have it,
since:
  template <typename T>	
  typename point_traits<T>::coordinate_type 
  point_concept::x(const T& point);
is more concise.  Since this isn't a tuple or some n-dimensional
hyper-point there is no need for meta-programming its accessors.  

So, I also went ahead and implemented the pattern for polygon data
types.  I translated some of the algorithms that operate on a polygon to
use the new interface to get a taste for what was in store for me.  In
the guts of the polygon_type related code is an algorithm (implemented
as an iterator) for converting the "compact" representation of a
manhattan polygon with one integer per edge to a sequence of points at
its vertices.  The increment operator looks thusly:
    inline iterator_points& operator++() {
      ++iter_;
      if(iter_ == iter_end_) {
        if(point_concept::get<HORIZONTAL>(pt) != firstX_) {
              --iter_;
              point_concept::set<HORIZONTAL>(pt, firstX_);
        }
      } else {
        point_concept::set(pt_, orient_, *iter_);
        orient_.turn90();
      }
      return *this;
    }
Note: that most of the time it updates a point pt_, which is a member of
the iterator_points class based on the *runtime* value of orient_, and
then changes the runtime value each time it is called.  When executed in
a loop this results in no branch instructions other than the ones
checking for loop termination (and the special case for last vertex).
If I used compile time accessors as the interface to the data type there
would be an extra branch in that loop for no good reason when using my
own point type (the common case.) 

Thoughts?

Thanks,
Luke