The past discussions on geometric libraries focused on how to define points. What matters even more however is how geometric objects are designed. There is a natural subtyping relationship between geometric objects. Deriving a square from a rectangle is usually frowned upon in OOP, because it can easily break the Liskov Substitution Principle if the objects are mutable. Making them immutable, however, solves the issue altogether. Morever, by using static subtyping, e.g. with concepts, we have multiple dispatch for free and don't pay any performance overhead, making such a design much better than with OOP. Concepts being non-intrusive, a mutable object may well be implemented but the concept can be a read-only view. Note that while I'm talking about concepts, I don't necessarily mean C++0x concepts, it could also be an alternative system. I would like to be able to write generic algorithms for geometric objects. Say I write an algorithm for any simple polygon. That algorithm should work with any simple quadrilateral, simple triangle, a rectangle, etc. Then I rewrite the same algorithm for convex polygons. So non-convex simple polygons should invoke the old algorithm, and convex ones the new one. So a system to find best matches is required. If we consider the subtyping graph for rectangle (which is not the most complex object, but certainly is complex enough to expose a complex graph), here is what we get: Rectangle < Right-angled Trapezium < Trapezium < ConvexQuadrilateral < Parallelogram < Trapezium ConvexQuadrilateral < SimpleQuadrilateral < Quadrilateral < Polygon < ConvexPolygon < SimplePolygon SimplePolygon < InsideSimplePolygonalLine SimplePolygon < Polygon Polygon < PolygonHole < Curve Polygon < InsidePolygonalLine InsideSimplePolygonalLine < InsideSimpleClosedCurve InsideSimplePolygonalLine < InsidePolygonalLine < InsideClosedCurve InsideSimpleClosedCurve < InsideClosedCurve < Curve SimpleClosedCurve < ClosedCurve < Curve InsideSimpleClosedCurve -> SimpleClosedCurve (composition thingy) InsideClosedCurve -> ClosedCurve (composition thingy) Curve < Object For clarification, a curve is here defined as the image of a continuous map from a real interval to the space. That is to say any set of points that is "connected". A simple curve is a curve that doesn't cross itself (just like simple polygons), which means the the map is injective, and a closed curve is a curve where the application comes from a closed interval and where the image is the same on both boundaries. A closed simple curve is a closed curve that is injective but for the boundaries. InsideClosedCurve defines the space with is "inside" a closed curve, which could also be defined by another map (known as a space-filling curve, but they are harder to manipulate, at least for polygons). A Polygon is an InsideClosedCurve with the closed curve being line segments within a plan. A PolygonHole is a Polygon which may have holes themselves defined by closed curves. An Object is a possibly (likely, even) infinite set of points in space. There is quite a complexity and redundancy here. It would be nice if it was possible to enhance that somehow. And that graph probably isn't fully complete, for example "right-angled" should probably be made separate propriety from trapezium. Also there should probably be Polytope somewhere. And PolygonHole lacks specializations too. The worse is the Inside thingies. I suppose having template concepts of some kind could help. Therefore I am wondering if there is any way to make the design simpler and more elegant. Indeed, such a design seems hard to maintain, it doesn't scale so well, and if I want to include something in there I probably have to modify other concepts as well. A geometric object is really just a set of proprieties. Working with meta-functions like is_quadrilateral, is_convex or is_simple seems like less work and verbosity. But how can such a system provide subtyping and best matches? Any comments and ideas are welcome.
Mathias wrote:
Therefore I am wondering if there is any way to make the design simpler and more elegant. Indeed, such a design seems hard to maintain, it doesn't scale so well, and if I want to include something in there I probably have to modify other concepts as well.
A geometric object is really just a set of proprieties. Working with meta-functions like is_quadrilateral, is_convex or is_simple seems like less work and verbosity. But how can such a system provide subtyping and best matches?
Any comments and ideas are welcome.
Thank you, Mathias, for raising these questions. I have been playing with subtyping of tags that indicate the conceptual type of a geometry object. In this way I can achieve static polymorphism of templated geometry data structures. A good example of such an object hierarchy of tags is the polygon tags I have created for my library: polygon_90_concept is the base most type of polygon. It's corners are restricted to multiples of 90 degrees and its edges are axis-parallel. It is the base most type because it is the most restricted. polygon_90_with_holes_concept inherits from polygon_90_concept and extends the idea of an axis-parallel polygon with the ability to contain axis-parallel polygonal holes. polygon_45_concept inherits from polygon_90_concept, and extents the idea of an axis parallel polygon by allowing its edges to also be 45 degree sloping. polygon_45_with_holes_concept cannot inherit from both polygon_90_with_holes_concept and polygon_45_concept because the multiple inheritance semantic in C++ lacks utility. I inherit it from polygon_45_concept and am forced to overload functions in the library to make it appear that polygon_90_with_holes_concept and polygon_45_with_holes_concept have static polymorphism. similarly polygon_concept inherits from polygon_45_concept allowing arbitrary angle corners and edges and polygon_with_holes_concept inherits from polygon_concept and I have to again overload functions to achieve the appearance of static polymorphism in the library. Now consider an algorithm such as one that slices a polygon into trapezoids. template <typename output_container_type, typename polygon_data_type> void get_trapezoids(output_container_type& output, const polygon_data_type& polygon); We wand to select the most efficient algorithm for the type of polygon provided. There should be several implementations that depend upon the conceptual type of the input polygon. These are accessed through get_trapezoids dispatch functions. I make them static members of the tag struct struct polygon_concept { template <typename output_container_type, typename polygon_data_type> static void get_trapezoids(output_container_type& output, const polygon_data_type& polygon); }; and dispatch to them by looking up the conceptual type template <typename coordinate_data_type> struct geometry_concept<polygon_data<coordinate_data_type> > { typedef polygon_concept type; }; and then accessing its static member function that implements the algorithm. This produces pleasing error msgs when such function is not provided: error: no function get_trapezoids in struct rectangle_concept Furthermore, we want to dynamically downcast the conceptual type of geometric data types. If a polygon happens to be a rectangle, or convex, we can apply a much more efficient algorithm than in the general case. In my library I might check if object that is tagged as polygon_concept might represent an axis-parallel or 45-degree polygon like so: template <typename output_container_type, typename polygon_data_type> void polygon_concept::get_trapezoids(output_container_type& output, const polygon_data_type& polygon) { CONCEPT_ID id = concept_downcast(polygon); if(id == POLYGON_90_CONCEPT) { polygon_90_concept::get_trapezoids(output, polygon); return; } else if(id == POLYGON_45_CONCEPT) { polygon_45_concept::get_trapezoids(output, polygon); return; } //implementation of arbitrary angle slicing of polygon into trapezoids } It's not perfect. One of the major challenges is that the volume of code in the API is huge, and has an inertia that once implemented it is very labor intensive to change even a minor aspect of the design because the impact is global. The revised library is 23 thousand lines of code--that's a mountain that I don't move lightly. One annoyance is that I can't dispatch based upon a runtime value without enumerating possible values. The only way to factor that out I can think of is with a macro, and I'm reluctant to use macros merely to save myself typing. I don't want to move all dispatch to runtime for obvious reasons of lack of ability to inline leading to degraded performance. The code also becomes very repetitive, especially where I have to duplicate functions. As you said, making the library complete is an extreme challenge because the number of functions required scales super-linearly to the number of conceptual object types in the system. Inheritance and static polymorphism of conceptual types helps some. If only an arbitrary angle implementation of an algorithm is available, it can be implemented in the base polygon_90_concept and chosen by static polymorphism of the tags for all polygon data types that inherit from polygon_90_concept. Clearly a similar design could be implemented based on SFINAE overloading instead of tag dispatching, but I have gotten the idea into my head that SPINAE overloading of template functions has a higher compile time cost than tag dispatching based overloading. It seems unnecessary and wasteful to check and recheck that an object models a concept every time it is used. It is also unclear to me how I would implement dynamic subtyping behavior based on runtime checks that downcast the conceptual type if I used SFINAE overloading unless I duplicated every SFINAE overloaded API with a non-SFINAE protected API that I could call in such cases. That could be tedious. Regards, Luke
Simonson, Lucanus J wrote:
polygon_90_concept is the base most type of polygon. It's corners are restricted to multiples of 90 degrees and its edges are axis-parallel. It is the base most type because it is the most restricted.
Well, there is something wrong here. The base type should be the less restricted one, not the most restricted one. In my hierarchy, the base type is "Object" (in lack of a better name) which is a potentially infinite set of points. That's as less restricted as it gets, I'm sure. Then Curve inherits from it, it is a "connected" set of points. Then Polygon inherits from it (indirectly, there are a few useful things in between), then more restricted polygons, etc.
polygon_90_with_holes_concept inherits from polygon_90_concept and extends the idea of an axis-parallel polygon with the ability to contain axis-parallel polygonal holes.
A polygon_90_with_holes is not a polygon_90. The inverse, however, is true. Indeed, if you consider a polygon with holes as a polygon, you forget some information and the polygon with holes is not well represented anymore. In the other direction, a polygon being considered as a polygon with holes is not a problem, it just happens to have a number of holes with is zero.
polygon_45_concept inherits from polygon_90_concept, and extents the idea of an axis parallel polygon by allowing its edges to also be 45 degree sloping.
Same, if the angles are multiples of 45 they're not necessarily multiples of 90. So a polygon with angles multiples of 45 is not a polygon with angles multiples of 90. However, a polygon with angles multiples of 90 is a polygon with angles multiples of 45, so polygon_90 should inherit from polygon_45. Your design fails to comply with the basics of subtyping: the Liskov Substitutability Principle. As a result, you cannot write generic code, you are forced to specialize everything, even when it is not useful. I would even say that it is broken beyond repair, since it cannot possibly support polymorphism. The invariant of a base can (will) be broken by any type/concept that derives from it, rendering the whole hierarchy not only useless but also dangerous.
Furthermore, we want to dynamically downcast the conceptual type of geometric data types. If a polygon happens to be a rectangle, or convex, we can apply a much more efficient algorithm than in the general case. In my library I might check if object that is tagged as polygon_concept might represent an axis-parallel or 45-degree polygon like so:
template <typename output_container_type, typename polygon_data_type> void polygon_concept::get_trapezoids(output_container_type& output, const polygon_data_type& polygon) { CONCEPT_ID id = concept_downcast(polygon); if(id == POLYGON_90_CONCEPT) { polygon_90_concept::get_trapezoids(output, polygon); return; } else if(id == POLYGON_45_CONCEPT) { polygon_45_concept::get_trapezoids(output, polygon); return; } //implementation of arbitrary angle slicing of polygon into trapezoids }
It's not perfect. One of the major challenges is that the volume of code in the API is huge, and has an inertia that once implemented it is very labor intensive to change even a minor aspect of the design because the impact is global. The revised library is 23 thousand lines of code--that's a mountain that I don't move lightly.
Well it doesn't even seem to be using the fact that the types are related. Where is the static polymorphism in it? Also, since you're taking the output as an argument, that necessarily means your objects are mutable. Which means doing the hierarchy the other way around can't work either, since the base can break the invariant of the derived. You may want to read that article on Wikipedia: http://en.wikipedia.org/wiki/Circle-ellipse_problem Basically, inheriting an Ellipse from a Circle is always wrong, and inheriting a Circle from an Ellipse is wrong if the Ellipse view of the Circle is mutable.
One annoyance is that I can't dispatch based upon a runtime value without enumerating possible values. The only way to factor that out I can think of is with a macro, and I'm reluctant to use macros merely to save myself typing. I don't want to move all dispatch to runtime for obvious reasons of lack of ability to inline leading to degraded performance.
The code also becomes very repetitive, especially where I have to duplicate functions. As you said, making the library complete is an extreme challenge because the number of functions required scales super-linearly to the number of conceptual object types in the system. Inheritance and static polymorphism of conceptual types helps some. If only an arbitrary angle implementation of an algorithm is available, it can be implemented in the base polygon_90_concept and chosen by static polymorphism of the tags for all polygon data types that inherit from polygon_90_concept.
Clearly a similar design could be implemented based on SFINAE overloading instead of tag dispatching, but I have gotten the idea into my head that SPINAE overloading of template functions has a higher compile time cost than tag dispatching based overloading. It seems unnecessary and wasteful to check and recheck that an object models a concept every time it is used. It is also unclear to me how I would implement dynamic subtyping behavior based on runtime checks that downcast the conceptual type if I used SFINAE overloading unless I duplicated every SFINAE overloaded API with a non-SFINAE protected API that I could call in such cases. That could be tedious.
No compile-time solution can possibly be as wasteful as a runtime linear branching (that even requires you to state all cases) as you gave in your example.
Hello,
polygon_90_concept is the base most type of polygon. It's corners are restricted to multiples of 90 degrees and its edges are axis-parallel. It is the base most type because it is the most restricted.
That's exactly what I thought while reading Luke's explanation.
You may want to read that article on Wikipedia: http://en.wikipedia.org/wiki/Circle-ellipse_problem
Basically, inheriting an Ellipse from a Circle is always wrong, and inheriting a Circle from an Ellipse is wrong if the Ellipse view of the Circle is mutable.
Wouldn't a typically C++-like approach be to use traits to ask each shape to present itself as an ellipse if it can? ellipse_traits<X>::get_length() and ellipse_traits<X>::get_width() would give the length and width that X has when viewed as an ellipse. ellipse_traits<ellipse> would simply define them as being its length and width. ellipse_traits<circle> would define them as both being its radius. specialization ellipse_traits<rectangle> would not exist, meaning that a rectangle is-not-an ellipse. ellipse and circle would obviously be 2 completely separated classes. Do you think this approach is valid and could be generalized to all geometric shapes? Bruno
Wouldn't a typically C++-like approach be to use traits to ask each shape to present itself as an ellipse if it can?
ellipse_traits<X>::get_length() and ellipse_traits<X>::get_width() would give the length and width that X has when viewed as an ellipse. ellipse_traits<ellipse> would simply define them as being its length and width. ellipse_traits<circle> would define them as both being its radius. specialization ellipse_traits<rectangle> would not exist, meaning that a rectangle is-not-an ellipse. ellipse and circle would obviously be 2 completely separated classes.
Do you think this approach is valid and could be generalized to all geometric shapes?
Now you have way to state "X can be viewed as an ellipse". But how would you state "if X can be viewed as a circle, then it can be viewed as an ellipse (in the way that ellipse_traits<X>::get_width() returns circle_traits<X>::get_radius()"?
Now you have way to state "X can be viewed as an ellipse". But how would you state "if X can be viewed as a circle, then it can be viewed as an ellipse (in the way that ellipse_traits<X>::get_width() returns circle_traits<X>::get_radius()"?
This comes to say: if circle_traits is specialized for X, then ellipse_traits is specialized for X. And to forward the right functions in ellipse_traits<X> to the right ones in circle_traits<X>. enable_if can help doing that. Unfortunately I don't know if it's possible to know at compile-time if a specialization exists. But we can use a trick. I think I got to achieve what you're asking for: // the primary ellipse_traits template <class X, class Enable = void> struct ellipse_traits {}; // the primary circle_traits template <class X> struct circle_traits { // at this stage it's not specialized... typedef mpl::false_ specialized; }; // the following means litterally: " if circle_traits is specialized for X, // then ellipse_traits<X> exists and it's width() is defined in terms of the // circle's radius" template <class X> struct ellipse_traits< X, typename enable_if<typename circle_traits<X>::specialized>::type > { static void width() { circle_traits<X>::radius(); } }; // an ellipse class struct ellipse; // an ellipse has its own ellipse_traits, let's define them template <> struct ellipse_traits<ellipse> { static void width() { cout << "ellipse width" << endl; } }; // a circle class struct circle; // circle_traits of a circle template <> struct circle_traits<circle> { static void radius() { cout << "circle radius" << endl; } // now it's specialized typedef mpl::true_ specialized; }; int main(int, char** argv) { ellipse_traits<ellipse>::width(); ellipse_traits<circle>::width(); return 0; } The output is: ellipse width circle radius The "specialized" typedef is a bit weird, as it forces the user to sort of say "yes, I've really specialized it". But the goal is reached I think: I have never explicitly specialized ellipse_traits<circle>. I have only said that if circle_traits<X> exists then ellipse_traits<X> exists and ellipse_traits<X>::width() is circle_traits<X>::radius(), except if a better specialization of ellipse_traits<X> exists. And the compiler correctly understood what I meant when I asked for ellipse_traits<circle>::width(). Does anybody know a way to know if a specialization exists without using this kind of trick? Bruno
Bruno wrote:
The "specialized" typedef is a bit weird, as it forces the user to sort of say "yes, I've really specialized it". But the goal is reached I think: I have never explicitly specialized ellipse_traits<circle>. I have only said that if circle_traits<X> exists then ellipse_traits<X> exists and ellipse_traits<X>::width() is circle_traits<X>::radius(), except if a better specialization of ellipse_traits<X> exists. And the compiler correctly understood what I meant when I asked for ellipse_traits<circle>::width().
Does anybody know a way to know if a specialization exists without using this kind of trick?
I was in the middle of typing up a proposal for what Bruno suggests, but had a different solution to knowing whether a specialization exists. My solution was simply to register the conceptual type of the object with a meta function, which indicates both that the corresponding traits should also be defined as well as an easy way to tell what conceptual type that object most closely models. template <typename T1, typename T2> struct SFINAE_is_same_type {}; template <typename T> struct SFINAE_is_same_type<T, T> { typedef void type; } template <typename T> struct geometry_concept {}; struct circle_concept {}; struct circle_data_type {}; template <> struct geometry_concept<circle_data_type> { typedef circle_concept type; }; template <class X> struct ellipse_traits< X, typename SFINAE_is_same_type< typename geometry_concept<X>::type, circle_concept>::type > { static void width() { cout << "another way to get at ellipse width" << endl; } }; I'm not sure which way is better, but I provide the geometry_concept meta-function anyway to use for tag dispatching/SFNAE purposes. Regards, Luke
I was in the middle of typing up a proposal for what Bruno suggests, but had a different solution to knowing whether a specialization exists. My solution was simply to register the conceptual type of the object with a meta function, which indicates both that the corresponding traits should also be defined as well as an easy way to tell what conceptual type that object most closely models.
<snip>
Indeed it's another right approach I think, don't know either which one would be the best one. Unless I missed something, you can use the Boost.TypeTraits's is_same in conjunction with enable_if instead of your SFINAE_is_same_type. Bruno
Bruno wrote:
Indeed it's another right approach I think, don't know either which one would be the best one. Unless I missed something, you can use the Boost.TypeTraits's is_same in conjunction with enable_if instead of your SFINAE_is_same_type.
The thing you are missing is the rather unfortunate circumstance I find myself in where two of my primary groups of users refuse to allow any boost dependency in their core libraries. Apparently, boost has a reputation for making the life of the build environment manager a pain. I'm left out in the cold like an orphan staring in through the frost-covered window on Christmas Eve. The last thing we need is SFINAE based selection of functions instead of tag dispatching because tag dispatching on object type forces me to implement lots of empty wrapper functions that redirect calls to the right implementation. template <typename T> struct is_polygon_concept {}; template <> struct is_polygon_concept<rectangle_concept> { typedef void type; } template <> struct is_polygon_concept<polygon_concept> { typedef void type; } template <> struct is_polygon_concept<polygon_with_holes_concept> { typedef void type; } template <> struct is_polygon_concept<polygon_set_concept> { typedef void type; } template <typename T, typename T2> sruct requires { typedef T2 type; } template <typename T> typename requires< typename is_polygon_concept< typename geometry_concept<T>::type >::type, perimeter_return_type>::type perimeter(const T& polygon) { typename polygon_traits<T>::iterator_edges itr = polygon_traits<T>::begin_edges(polygon); typename polygon_traits<T>::iterator end = polytope_traits<T>::end_edges(polygon); perimeter_return_type retval = perimeter_return_type(0); for(; itr != end; ++itr) { perimeter_return_type += length(*itr); } return retval; } Assuming the appropriate specializations for adapting concepts to polygon concept are provided by the library, the perimeter function works on triangle, rectangle, convex polygon, axis parallel polygon, etc. Assuming rectangle is already specialized for axis parallel polygon implementing polygon specialization of rectangle is unnecessary if it is specialized for axis parallel polygon. It is critically important to take advantage of this extra layer of abstraction because without it the number of functions the library author is required to write in order to handle all the conceptual geometry types the users would want is intractably large. Note that perimeter cannot be called on a circle because is_polygon_concept fails to substitute circle for T. This provides the semantic of geometric subtyping that Mathias first suggested, but by meta-function and SFINAE rather than inheritance. We will probably need to create separate mutable traits for geometry types so that they are not accessible through the regular traits. template <typename T, typename enable = void> struct ellipse_traits { typedef T::coordinate_type coordinate_type; coordinate_type width(const T& ellipse); }; template <typename T, typename enable = void> struct mutable_ellipse_traits { template <typename coord_type> void set_width(T& ellipse, coord_type value); } mutable_ellipse_traits is not specialized for circle when ellipse traits is, and is_ellipse_concept would need a complementing is_mutable_ellipse_concept to complete this pattern. We might specialize mutable_circle_traits for elipse because we can write circle data to an ellipse. Regards, Luke
Hello,
Unless I missed something, you can use the Boost.TypeTraits's is_same in conjunction with enable_if instead of your SFINAE_is_same_type.
The thing you are missing is the rather unfortunate circumstance I find myself in where two of my primary groups of users refuse to allow any boost dependency in their core libraries. Apparently, boost has a reputation for making the life of the build environment manager a pain.
Integrating Boost inside our build system in my company is absolutely not more a pain than for any other third-party library (I'd even say less than for some of them). And anyway, a good compromise would be at least to accept header-only parts of Boost...
mutable_ellipse_traits is not specialized for circle when ellipse traits is, and is_ellipse_concept would need a complementing is_mutable_ellipse_concept to complete this pattern. We might specialize mutable_circle_traits for elipse because we can write circle data to an ellipse.
Yes indeed, this is the part that was missing to really handle the circle-ellipse problem. The design sounds good to me like that... Bruno
mutable_ellipse_traits is not specialized for circle when ellipse traits >>is, and is_ellipse_concept would need a complementing >>is_mutable_ellipse_concept to complete this pattern. We might specialize >>mutable_circle_traits for elipse because we can write circle data to an >>ellipse.
Bruno wrote:
Yes indeed, this is the part that was missing to really handle the circle-ellipse problem. The design sounds good to me like that...
Sounds good, but there is a problem. Consider the assign function: template <typename T1, typename T2, typename T3> struct requires_2 { typedef T3 type; }; //assigns anything that can provide a read only interface //that models ellipse to anything that can model the mutable //interface of ellipse template <typename T1, typename T2> typename requires_2< typename is_mutable_ellipse_concept< typename geometry_concept<T1>::type>::type, typename is_ellipse_concept< typename geometry_concept<T2>::type>::type, T1>::type & assign(T1& lvalue, const T2& rvalue); //assigns anything that can provide a read only interface that //models circle to anything that can model the mutable interface //of circle template <typename T1, typename T2> typename requires_2< typename is_mutable_circle_concept< typename geometry_concept<T1>::type>::type, typename is_circle_concept< typename geometry_concept<T2>::type>::type, T1>::type & assign(T1& lvalue, const T2& rvalue); So far so good, but if circle models immutable ellipse and ellipse models mutable circle it results in ambiguous function definition when you try to assign a circle to an ellipse because it can either view the circle as a read only ellipse or view the ellipse as a write only circle. Basically, mutable traits should only be enabled for an object that is genuinely of that conceptual type and the immutable traits are sufficient to provide all desired copy conversion semantics. This is sufficient to solve the problem. I'm not 100% happy with the result because I have to write O(n^2) meta-function partial specializations given n conceptual types in a subtyping hierarchy. SFINAE only works if substitution fails at the first level of instantiation, so I cannot create a hierarchy of partial specializations, but have to make every is-a relationship explicit. Luke
Luke wrote:
I was in the middle of typing up a proposal for what Bruno suggests, but >> had a different solution to knowing whether a specialization exists. My >>solution was simply to register the conceptual type of the object with a >>meta function, which indicates both that the corresponding traits should >>also be defined as well as an easy way to tell what conceptual type that >>object most closely models.
Bruno replied to Luke:
Indeed it's another right approach I think, don't know either which one would be the best one.
After refactoring the majority of my library to use my approach I have come up with a rational for using the meta-function rather than inspecting the traits for the existence of a member that indicates that it has been specialized for a given type. It is very convenient to define default traits that apply to any type T. This allows the user (and the library author) to conform the public interface of their classes to the default definition of a class that models the concept. A good example of this is the iterator traits, which default to look for value_type and so forth, but can be specialized if needed. In my library, I want any vector of objects that model rectangle, for instance, can be treated as an aggregation of manhattan polygonal data and serve as a valid argument to functions that operate on aggregations of geometry data, such as boolean operations. I also want to allow individual polygons or rectangles to behave as read only aggregations of geometry data. By using some meta-function based indirection I implemented a default definition of the traits for aggregations of geometry data that is applicable to any object that models rectangle, polygon, or list/vector of such. In this way, a user need only define the traits for their polygon type and immediately get access to functions that operate on collections of their polygon through the library API. I can then use other meta functions to protect the declarations of those functions using SFINAE rather than depend on a specialization of the traits being defined for every combination of container and geometry data type. Assuming UserPolygon has specialized the polygon traits the following syntax is legal. UserPolygon p; std::list<UserPolygon> plist1, plist2; // self assignment OR of result of an AND operation between // a polygon and a list of polygons plist1 += P * plist2; //assign the result of bloating by three the XOR of a polygon and //a list of polygons assign(plist1, (p ^ plist2) + 3); Note that the operator functions are fully protected by SFINAE to prevent collision with other generic operator declarations. It is much more intuitive to a user to define the traits for their polygon and have all higher order functionality that depends on their polygon type work out-of-the-box rather than have to define additional traits for higher order concepts. Is there a way that can be accomplished without default definitions for traits? Regards, Luke
On Fri, Nov 14, 2008 at 2:18 PM, Bruno Lalande <bruno.lalande@gmail.com> wrote:
The "specialized" typedef is a bit weird, as it forces the user to sort of say "yes, I've really specialized it". But the goal is reached I think: I have never explicitly specialized ellipse_traits<circle>. I have only said that if circle_traits<X> exists then ellipse_traits<X> exists and ellipse_traits<X>::width() is circle_traits<X>::radius(), except if a better specialization of ellipse_traits<X> exists. And the compiler correctly understood what I meant when I asked for ellipse_traits<circle>::width().
Does anybody know a way to know if a specialization exists without using this kind of trick?
I've done something similar, where the default template implementation has a member typedef of a particular type `not_specialized`. You can see this at: http://tinyurl.com/5dba48 (look at port_binary_operation_impl and are_port_binary_operable) In this case, the member typedef used is result_type but it can be anything. The mechanism basically checks whether a particular template instantiation has a result_type that is_same as not_specialized. If it has no result_type, or the result_type is something different, it knows that the template has been specialized. The method is not perfect as you can fool it into thinking that the template has not been specialized for certain arguments by setting the typedef used to not_specialized. I don't know whether there is a way to prevent that (perhaps make `not_specialized` a private nested struct of something?) Best, Stjepan
I've done something similar, where the default template implementation has a member typedef of a particular type `not_specialized`. You can see this at:
(look at port_binary_operation_impl and are_port_binary_operable)
Very similar indeed, good idea to use an already needed nested type instead of my "specialized" one, it prevents the user from having to know about the trick, which was my main problem about it.
The method is not perfect as you can fool it into thinking that the template has not been specialized for certain arguments by setting the typedef used to not_specialized. I don't know whether there is a way to prevent that (perhaps make `not_specialized` a private nested struct of something?)
Yep, letting "not_specialized" being private will certainly solve this slight problem. Bruno
Bruno Lalande wrote:
int main(int, char** argv) { ellipse_traits<ellipse>::width(); ellipse_traits<circle>::width(); return 0; }
Sorry for the late reply, but from a quick glance I can tell this is just single dispatch. Geometric algorithms really need multi-dispatch.
Bruno Lalande wrote:
int main(int, char** argv) { ellipse_traits<ellipse>::width(); ellipse_traits<circle>::width(); return 0; }
Mathias G wrote:
Sorry for the late reply, but from a quick glance I can tell this is just single dispatch. Geometric algorithms really need multi-dispatch.
Hmm, I have three boolean algorithms. One for manhattan data, which is a small constant factor slower than std::sort, one for data that includes 45 degree edges, which is a small constant factor slower than the manhattan algorithm and a very very slow, but robust arbitrary angle algorithm. I use operator syntax to call boolean operations. polygon_45_data<int> p45; polygon_90_data<int> p90; polygon_data<int> p; p90 & p90; //calls manhattan intersection boolean algorithm p45 | p90; //calls 45 union boolean algorithm p45 - p45; //calls 45 and not boolean algorithm p ^ p90; //calls arbitrary angle xor boolean algorithm These operators are overloaded with SFINAE on return type such that three intersection operators are sufficient to cover all valid combinations of any geometry type, rectangle, six flavors of polgyons with and without holes in the manhattan, 45, or general domains, and std containers thereof as well as my data structures that serve as the inputs to the boolean algorithms //manhattan boolean intersection operator //works on any two manhattan geometric data types template <typename geometry_type_1, typename geometry_type_2> typename requires_2< typename is_polygon_90_set_type<geometry_type_1>::type::type, typename is_polygon_90_set_type<geometry_type_2>::type::type, polygon_90_set_view<geometry_type_1, geometry_type_2, boolean_op::BinaryAnd> >::type operator&(const geometry_type_1& lvalue, const geometry_type_2& rvalue) { return polygon_90_set_view<geometry_type_1, geometry_type_2, boolean_op::BinaryAnd> (lvalue, rvalue, polygon_90_set_traits<geometry_type_1>::orient(lvalue), boolean_op::BinaryAnd()); } //45 degree boolean intersection operator //works with any combination of 45 and 90 template <typename geometry_type_1, typename geometry_type_2> typename requires_3< typename is_polygon_45_or_90_set_type<geometry_type_1>::type::type, typename is_polygon_45_or_90_set_type<geometry_type_2>::type::type, typename is_either_polygon_45_set_type<geometry_type_1, `` geometry_type_2>::type::type, polygon_45_set_view<geometry_type_1, geometry_type_2, 1> >::type operator&(const geometry_type_1& lvalue, const geometry_type_2& rvalue) { return polygon_45_set_view<geometry_type_1, geometry_type_2, 1> (lvalue, rvalue); } //arbitrary angle boolean intersection operator //works with any combination of arbitrary angle, 45 and 90 template <typename geometry_type_1, typename geometry_type_2> typename requires_3< typename is_any_polygon_set_type<geometry_type_1>::type::type, typename is_any_polygon_set_type<geometry_type_2>::type::type, typename is_either_polygon_set_type<geometry_type_1, geometry_type_2>::type::type, polygon_set_view<geometry_type_1, geometry_type_2, 1> >::type operator&(const geometry_type_1& lvalue, const geometry_type_2& rvalue) { return polygon_set_view<geometry_type_1, geometry_type_2, 1> (lvalue, rvalue); } Is this what you mean by multiple dispatch, Mathias? I will be checking the complete working code into the sandbox shortly, but I want to make an internal release of it first. By the way, I notice the boost con deadline for submission abstracts is fast approaching. What would the boost community like to see in a boost con abstract about geometry from me? Regards, Luke
Simonson, Lucanus J wrote:
These operators are overloaded with SFINAE on return type such that three intersection operators are sufficient to cover all valid combinations of any geometry type, rectangle, six flavors of polgyons with and without holes in the manhattan, 45, or general domains, and std containers thereof as well as my data structures that serve as the inputs to the boolean algorithms
//manhattan boolean intersection operator //works on any two manhattan geometric data types template <typename geometry_type_1, typename geometry_type_2> typename requires_2< typename is_polygon_90_set_type<geometry_type_1>::type::type, typename is_polygon_90_set_type<geometry_type_2>::type::type, polygon_90_set_view<geometry_type_1, geometry_type_2, boolean_op::BinaryAnd> >::type operator&(const geometry_type_1& lvalue, const geometry_type_2& rvalue) { return polygon_90_set_view<geometry_type_1, geometry_type_2, boolean_op::BinaryAnd> (lvalue, rvalue, polygon_90_set_traits<geometry_type_1>::orient(lvalue), boolean_op::BinaryAnd()); }
//45 degree boolean intersection operator //works with any combination of 45 and 90 template <typename geometry_type_1, typename geometry_type_2> typename requires_3< typename is_polygon_45_or_90_set_type<geometry_type_1>::type::type, typename is_polygon_45_or_90_set_type<geometry_type_2>::type::type, typename is_either_polygon_45_set_type<geometry_type_1, `` geometry_type_2>::type::type, polygon_45_set_view<geometry_type_1, geometry_type_2, 1> >::type operator&(const geometry_type_1& lvalue, const geometry_type_2& rvalue) { return polygon_45_set_view<geometry_type_1, geometry_type_2, 1> (lvalue, rvalue); }
//arbitrary angle boolean intersection operator //works with any combination of arbitrary angle, 45 and 90 template <typename geometry_type_1, typename geometry_type_2> typename requires_3< typename is_any_polygon_set_type<geometry_type_1>::type::type, typename is_any_polygon_set_type<geometry_type_2>::type::type, typename is_either_polygon_set_type<geometry_type_1, geometry_type_2>::type::type, polygon_set_view<geometry_type_1, geometry_type_2, 1> >::type operator&(const geometry_type_1& lvalue, const geometry_type_2& rvalue) { return polygon_set_view<geometry_type_1, geometry_type_2, 1> (lvalue, rvalue); }
Is this what you mean by multiple dispatch, Mathias?
Overloading certainly is ad-hoc polymorphism with multiple-dispatch based on the static type. So yes. However, isn't this ambiguous? A 90 degree polygon should match all three overloads.
Mathias wrote:
Overloading certainly is ad-hoc polymorphism with multiple-dispatch based on the static type. So yes. However, isn't this ambiguous? A 90 degree polygon should match all three overloads.
Yes, a single 90 degree polygon should match all three overloads, but two 90 degree polygons can only match the correct operator. Each operator takes two arguments. is_either_polygon_45_set_type<T1, T2> evaluates to a type only if one or the other or both T1 and T2 are of 45 degree flavor. That means that two 90 degree polygons can't instantiate a function that requires is_either_polgyon_45_set_type on its two arguments. Similarly with is_either_polygon_set_type, only if one of the arguments is of arbitrary angle flavor will the arbitrary angle intersection operator be instantiated. Luke
On Dec 4, 2008, at 2:05 PM, Simonson, Lucanus J wrote:
These operators are overloaded with SFINAE on return type such that three intersection operators are sufficient to cover all valid combinations of any geometry type, rectangle, six flavors of polgyons with and without holes in the manhattan, 45, or general domains, and std containers thereof as well as my data structures that serve as the inputs to the boolean algorithms
This approach leads to an combinatorial number of overloads, does it not? Surely there must be a way to do static multiple dispatch using metaprogramming instead. I agree with the goal 100% and I want to see a rich interface like this in Boost. Just wondering if the implementation ends up bulkier than it needs to be.
By the way, I notice the boost con deadline for submission abstracts is fast approaching. What would the boost community like to see in a boost con abstract about geometry from me?
If you get a spot, leave some time for discussion. ;-) Are any of the other geometry authors planning to attend? Is there any chance for a panel? I am very glad to see some progress here - it's a tough problem which should be nicely solvable with the abstractions and tools provided by Boost. Cheers, Gordon
On Dec 4, 2008, at 2:05 PM, Simonson, Lucanus J wrote:
These operators are overloaded with SFINAE on return type such that three intersection operators are sufficient to cover all valid combinations of any geometry type, rectangle, six flavors of polgyons with and without holes in the manhattan, 45, or general domains, and std containers thereof as well as my data structures that serve as the inputs to the boolean algorithms
Gordon wrote:
This approach leads to an combinatorial number of overloads, does it not? Surely there must be a way to do static multiple dispatch using metaprogramming instead.
No, there are three algorithms and three overloads. Any combination of many possible inputs resolves to the correct algorithm through metaprogramming. This operator API is concepts based. Previously I had a real problem with tag dispatching leading to exactly the problem you call out where a combinatorial number of overloads was required. Concepts is much more powerful than tag dispatching and got the number of functions I needed to type down to linear to the number of algorithms I wanted to expose. As it is I got a repetitive stress injury from typing typename, typedef ::type the < > and _ chars and saving ever twenty seconds with :w because I'm a vi user. Regards, Luke
On Dec 6, 2008, at 12:39 AM, Simonson, Lucanus J wrote:
Gordon wrote:
This approach leads to an combinatorial number of overloads, does it not? Surely there must be a way to do static multiple dispatch using metaprogramming instead.
No, there are three algorithms and three overloads. Any combination of many possible inputs resolves to the correct algorithm through metaprogramming. This operator API is concepts based.
Excellent, I misunderstood. I think that design should scale much better for new concepts. Personally I want beziers and splinegons. Looking forward to seeing this and how it merges with the other implementations.
As it is I got a repetitive stress injury from typing typename, typedef ::type the < > and _ chars and saving ever twenty seconds with :w because I'm a vi user.
I got RSI before I knew about metaprogramming too. Now I think more and type less. :D Gordon
Bruno wrote:
Wouldn't a typically C++-like approach be to use traits to ask each shape to present itself as an ellipse if it can?
ellipse_traits<X>::get_length() and ellipse_traits<X>::get_width() would give the length and width that X has when viewed as an ellipse. ellipse_traits<ellipse> would simply define them as being its length and width. ellipse_traits<circle> would define them as both being its radius. specialization ellipse_traits<rectangle> would not exist, meaning that a rectangle is-not-an ellipse. ellipse and circle would obviously be 2 completely separated classes.
Do you think this approach is valid and could be generalized to all geometric shapes?
Thomas replied:
Now you have way to state "X can be viewed as an ellipse". But how would you state "if X can be viewed as a circle, then it can be viewed as an ellipse (in the way that ellipse_traits<X>::get_width() returns circle_traits<X>::get_radius()"?
The approach is valid and could be generalized to all geometric shapes, but it is simply too labor intensive a proposition to implement all traits of all types that a given type could represent itself as. I am currently facing the problem that I am trying to overload every function for every valid conceptual type it can accept. This becomes a serious problem because it is very hard to implement a complete API and the work required simply to provide the functions I was getting for free through inheritance is leading to some significant code bloat. What we need is a 2nd level of abstraction. In addition to abstracting away the raw type of a geometric object we also need to be able to abstract away the conceptual type of a geometric object and write functions that work in terms of categories of conceptual types. For instance if there were some mechanism by which all rectangle, all flavors of polygon, any collection of polygons etc. could represent themselves as an iterator range over edges through a single template instantiation then a single implementation of perimeter would work on the whole phylogeny of piecewise linear 2d solid figures. That template when instantiated on a conceptually rectangle type would instantiate a template that depends upon only the rectangle traits provided for that type. In this way the user need only specialize the traits that pertain directly to their object type. Luke
Thank you, Mathias and Bruno for your helpful and frank feedback on my design. You'll no doubt have noted that I came to the same conclusion as you in my 2nd reply to Mathias yesterday. I came into work this morning planning to eliminate all inheritance relationships from the implementation. Mathias wrote:
No compile-time solution can possibly be as wasteful as a runtime linear branching (that even requires you to state all cases) as you gave in your example.
The runtime case was for selecting algorithms based on whether the data stored by the object is simpler than what the object is capable of storing, which can only be known at runtime. It was not an alternative to static selection of algorithms, but in addition to it. A polygon with holes can degenerate into a polygon without holes, a convex polygon, an axis-parallel polygon, a rectangle, a single segment, a single point or nothing at all. The need to identify degeneracy at runtime should be obvious. I'm introducing runtime degeneracy dependent optimizations into the code, which is a requirement coming from my users. This means I have to select an algorithm based on the runtime characteristics of the data in an object in addition to that object's static type. In my type system, arbitrary-angle polygon set is the most general concept and all others are special cases of it. Any object could represent itself as a read-only polygon set. I have been thinking for some time that I should separate the mutable and immutable traits of an object type. A rectangle would want to provide immutable traits for all the more general types that are capable of representing a rectangle, but provide the mutable traits for rectangle only. It would be onerous to provide all those specializations explicitly, so I would like to use a template to auto-generate them based upon the immutable traits of the rectangle concept alone. Regard, Luke
Simonson, Lucanus J wrote:
Thank you, Mathias and Bruno for your helpful and frank feedback on my design.
I was afraid I had been a little harsh. Good to know you were not hurt by my comments ;).
The runtime case was for selecting algorithms based on whether the data stored by the object is simpler than what the object is capable of storing, which can only be known at runtime.
So you have both runtime and compile-time detections on what some geometric object is. How do you factor the code? Ideally, it would be nice to be able to fuse the compile-time and the runtime mechanisms. A is_rectangle meta-function is not much different than a is_rectangle function, after all. Maybe it is possible to generate the runtime function from the compile-time function. Also, you could try to do your forwarding automatically Instead of template <typename output_container_type, typename polygon_data_type> void polygon_concept::get_trapezoids(output_container_type& output, const polygon_data_type& polygon) { CONCEPT_ID id = concept_downcast(polygon); if(id == POLYGON_90_CONCEPT) { polygon_90_concept::get_trapezoids(output, polygon); return; } else if(id == POLYGON_45_CONCEPT) { polygon_45_concept::get_trapezoids(output, polygon); return; } //implementation of arbitrary angle slicing of polygon into trapezoids } You could write template <typename output_container_type, typename polygon_data_type> void polygon_concept::get_trapezoids(output_container_type& output, const polygon_data_type& polygon) { //implementation of arbitrary angle slicing of polygon into trapezoids } template <typename output_container_type, typename polygon_data_type> void polygon_concept::get_trapezoids(output_container_type& output, const polygon_data_type& polygon) { visit<polygon_90_concept, polygon_45_concept>( polygon, bind(get_trapezoids, output, _1), bind(get_trapezoids_polygon, output, _1) ); } the visit function would attempt to downcast the first argument to all types in the list and then call the second argument with the downcasted object. If no downcast is possible, it calls the third argument. That's a possible and simplistic design, there are certainly better ones. The main issue is that it doesn't allow multiple dispatch.
Mathias wrote:
There is a natural subtyping relationship between geometric objects. Deriving a square from a rectangle is usually frowned upon in OOP, because it can easily break the Liskov Substitution Principle if the objects are mutable. Making them immutable, however, solves the issue altogether.
Now, finally, I see your point. Clearly if a rectangle output is expected you cannot pass it a mutable square to hold the result, but making such syntax illegal by preventing the generic API from modifying objects seems like a drastic measure. It eliminates more than half the utility of the mechanism. The polygon_90 and polygon in my library are similar to your rectangle and square example. There is no inheritance relationship that does not violate Liskov's substitution principle, but my polygon inherits from polygon_90. Right now, my library does not protect the user from invoking an undefined behavior by passing an arbitrary angle polygon as input into a function that expects an axis-parallel polygon. This is a troubling lack of static type safety that didn't bother me much before now, but should have. Overall, I've been frustrated that there is little to be gained from inheritance. The only benefit at this juncture is it saves me from writing a handful of functions in the few cases where I use it. It would be reasonable to eliminate inheritance and provide explicit overloads of each function required. Such a change would actually be relatively little code change in my library. The effect of static polymorphism of geometry objects in the API can be achieved by explicitly overloading all functions for all types that make sense. That allows us to achieve the exact semantics that we are after. Unfortunately, it is a huge effort to provide explicit overloads for all possible types. The number of types in the system needs to be kept down to keep the implementation effort tractable, but doing so could easily lead to a library that favors some application domains over others. Regards, Luke
Simonson, Lucanus J wrote:
Clearly if a rectangle output is expected you cannot pass it a mutable square to hold the result, but making such syntax illegal by preventing the generic API from modifying objects seems like a drastic measure. It eliminates more than half the utility of the mechanism.
I require any type fulfilling a concept to be constructible from an object of any type which fulfills that same concept. So I can simply return any object, which will then be copied into the structure of the user. If the object is light and the compiler is good, there shouldn't be any penalty. I personally strongly dislike the idea of providing output as arguments, so I suppose I'm quite biased on that limitation.
Simonson, Lucanus J wrote:
Clearly if a rectangle output is expected you cannot pass it a mutable square to hold the result, but making such syntax illegal by preventing >> the generic API from modifying objects seems like a drastic measure. It >> eliminates more than half the utility of the mechanism.
I require any type fulfilling a concept to be constructible from an object of any type which fulfills that same concept. So I can simply return any object, which will then be copied into the structure of the user. If the object is light and the compiler is good, there shouldn't be any penalty.
I personally strongly dislike the idea of providing output as arguments, so I suppose I'm quite biased on that limitation.
I don't like it either, but I have little choice. I can't require that any type fulfilling a concept be constructible from any object that also fulfills that concept and I cannot overload the copy constructor or assignment operator of unknown geometry type T. Also, geometry objects can be arbitrarily heavy. One polygon has the potential to be many megabytes in my application domain. While it is possible to return by value for light objects and pass outputs as arguments for heavy objects, it would make for a highly inconsistent and unintuitive API. I also like to write API with an accumulate semantic where possible so that the output argument appends to rather than overwriting its contents. Luke
Also, geometry objects can be arbitrarily heavy. One polygon has the
Simonson, Lucanus J wrote: potential to be many megabytes in my application domain.
While it is possible to return by value for light objects and pass outputs as arguments for heavy objects, it would make for a highly inconsistent and unintuitive API.
For clarification, by light objects I mean proxies and adaptors, in a DSEL kind of way. Basically the aim is that the algorithm is not applied when you call the function, but when you copy the result. The spirit is fairly similar to the range adaptors of Boost.RangeEx for example.
AMDG Mathias Gaunard wrote:
Clearly if a rectangle output is expected you cannot pass it a mutable square to hold the result, but making such syntax illegal by preventing the generic API from modifying objects seems like a drastic measure. It eliminates more than half the utility of the mechanism.
I require any type fulfilling a concept to be constructible from an object of any type which fulfills that same concept.
Wait. How does that work: Right triangle models Triangle. Equilateral triangle models Triangle. Therefore, right triangle can be converted to equilateral triangle? In Christ, Steven Watanabe
Steven Watanabe wrote:
Wait. How does that work:
Right triangle models Triangle. Equilateral triangle models Triangle. Therefore, right triangle can be converted to equilateral triangle?
Actually I meant only the concept it directly models, not the ones which are indirectly so. A model of Right triangle can be constructed from any model of Right triangle, but not from a model of Triangle. The idea is to be able to have similar mechanisms to that of containers/ranges with adaptors, such as this example: SomeContainer a = transform(some_range, some_function); (actually you have to write SomeContainer a( begin(transform(some_range, some_function)), end(transform(some_range, some_function)) );) with transform = make_transform_range from Boost.RangeEx. This results in something fairly equivalent to SomeContainer a; std::transform( some_range.begin(), some_range.end(), std::back_inserter(a), some_function ); Maybe it shouldn't be required however. For ranges which are proxies or adaptors it makes little sense to be able to be constructed from any range.
participants (7)
-
Bruno Lalande -
Gordon Woodhull -
Mathias Gaunard -
Simonson, Lucanus J -
Steven Watanabe -
Stjepan Rajko -
Thomas Klimpel