Shape.cpp
// Shape.cpp
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2011
@import "Ceda/cxObject/IObjectVisitor.h"
@import "Ceda/cxObject/PrintReflectedType.h"
@import "Ceda/cxObject/PrintReflectedVariable.h"
@import "ExampleUtils.h"
@import "ValidateSerialisation.h"
#include <math.h>
/*
Shape is a value type that is able to hold either a Point, Line, Square, Rect, Circle or
Polygon value. Putting it another way, the set of all Shape values consists of the set
theoretic union over the set of Point, Line, Square, Rect, Circle and Polygon values.
On x86 we have the following sizes (in bytes of an instance in memory):
models
Point 8
Line 12
Square 12
Rect 16
Circle 12
Polygon 24
variant
Shape 28
sizeof(Shape) = 28 (for a 32 bit tag plus a buffer large enough for any of the types
in the union - the largest being 24 bytes for a Polygon). It is much more efficient than
using heap allocated objects to achieve polymorphism (e.g in a collection of shapes as an
xvector<Shape>). It eliminates the need for the programmer to worry about pointers and
memory leaks. Functions that iterate over vectors tend to work correctly. E.g.
serialisation of a vector to an archive or writing the elements of a vector to an
xostream.
Note that Shape is a closed variant type, meaning that new types cannot declare
themselves to be part of the variant after the fact. Whether this is appropriate
depends on the application.
In a way Shape is kind of like a retrospectively defined supertype of those 6 models
because a value (n.b. not a pointer to a variable!) of any one of them can be implicit
cast to a Shape value. E.g.
Point p(0,0);
Shape s = p;
It is important to be aware that the sense in which Circle is-a Shape is very different
to the normal OO notion of subtype. The former relates to value substitutability
(the set of circle values is a subset of the set of shape values), and the latter
relates to pointer to state machine substitutability (aka LSP) which would normally
suggest no inheritance amongst value types is possible (e.g. under LSP one would
conclude that a circle is not a shape because a shape variable holding a circle value
can be reassigned such that it no longer holds a circle). This is relevant to the
well known square is-a rectangle debate.
The implementation of the closed variant type is a little tricky because the types to
union over can have non-trivial constructors which means that a C++ union cannot be
used. When a Shape destructs it has to run the appropriate destructor (e.g. in the
case of the Polygon it needs to destruct the vector of points).
Free functions rather than class member functions
-------------------------------------------------
The convention for expressing OO in C++ is to bundle functions with the data. The
functions are called class member functions and have an implicit 'this' pointer, in
contrast to free functions.
Nevertheless member functions on models or variants are not supported. For example
the following will generate a compiler error:
$model Rect
{
Point p1;
Point p2;
// Error : member functions in models are not supported
float32 Area() const { return (p2.y-p1.y)*(p2.x-p1.x); }
};
Instead we use *free functions*, such as
float32 Area(const Rect& r)
Free functions can be added by clients independently of whoever wrote the model or
variant data types (perhaps in a different DLL). Free functions are the better choice
for operators on value types because all arguments are treated equally for the purposes
of implicit conversions. E.g. If Rect has a constructor from a Square then a free
function with signature Area(Rect) can be called for a Square. This doesn't work when
Area() is a class member function.
It is noteworthy that for ceda data model types, the data members are already
public, so encapsulation doesn't provide the excuse to bundle methods with the
data. Indeed, Scott Myers has an item saying that a class should have as few
methods as possible. Admittedly his reasoning was that methods gain access to the
private state so there should be as few methods as possible, and that doesn't apply
when all member variables are public anyway.
*/
namespace shape
{
////////////////////////////////////
$model Point
{
ceda::float32 x;
ceda::float32 y;
};
inline ceda::float32 Perim(const Point& p)
{
return 0;
}
inline ceda::float32 Area(const Point& p)
{
return 0;
}
inline ceda::float32 Dist(const Point& p1, const Point& p2)
{
ceda::float32 dx = p2.x - p1.x;
ceda::float32 dy = p2.y - p1.y;
return sqrt(dx*dx + dy*dy);
}
////////////////////////////////////
$model Line
{
Point p1;
Point p2;
};
inline ceda::float32 Length(const Line& l)
{
return Dist(l.p1, l.p2);
}
inline ceda::float32 Perim(const Line& l)
{
return 2*Length(l);
}
inline ceda::float32 Area(const Line& l)
{
return 0;
}
////////////////////////////////////
$model Square
{
Point p1; // bottom left corner
ceda::float32 w; // width and height
};
inline ceda::float32 Width(const Square& s)
{
return s.w;
}
inline ceda::float32 Height(const Square& s)
{
return s.w;
}
inline Point TopLeft(const Square& s)
{
return Point(s.p1.x, s.p1.y + s.w);
}
inline Point TopRight(const Square& s)
{
return Point(s.p1.x + s.w, s.p1.y + s.w);
}
inline Point BotLeft(const Square& s)
{
return s.p1;
}
inline Point BotRight(const Square& s)
{
return Point(s.p1.x + s.w, s.p1.y);
}
ceda::float32 Perim(const Square& s)
{
return 4 * s.w;
}
inline ceda::float32 Area(const Square& s)
{
return s.w * s.w;
}
////////////////////////////////////
$model Rect
{
Point p1; // bottom left corner
Point p2; // top right corner
// Note that this single argument constructor is not declared 'explicit' and therefore
// allows for implicit conversion from Square to Rect.
$$(const Square& s) : p1(s.p1), p2(p1.x+s.w, p1.y+s.w) {}
};
inline ceda::float32 Width(const Rect& r)
{
return r.p2.x - r.p1.x;
}
inline ceda::float32 Height(const Rect& r)
{
return r.p2.y - r.p1.y;
}
inline ceda::float32 Perim(const Rect& r)
{
return 2*(Width(r) + Height(r));
}
inline ceda::float32 Area(const Rect& r)
{
return Width(r) * Height(r);
}
inline Point TopLeft(const Rect& r)
{
return Point(r.p1.x, r.p2.y);
}
inline Point TopRight(const Rect& r)
{
return r.p2;
}
inline Point BotLeft(const Rect& r)
{
return r.p1;
}
inline Point BotRight(const Rect& r)
{
return Point(r.p2.x, r.p1.y);
}
inline const Rect& BoundingRect(const Line& l)
{
return (const Rect&) l;
}
////////////////////////////////////
const ceda::float32 PI = 3.14159f;
$model Circle
{
Point c;
ceda::float32 r;
};
inline ceda::float32 Width(const Circle& c)
{
return 2*c.r;
}
inline ceda::float32 Height(const Circle& c)
{
return 2*c.r;
}
ceda::float32 Perim(const Circle& c)
{
return 2*PI*c.r;
}
ceda::float32 Area(const Circle& c)
{
return PI*c.r*c.r;
}
////////////////////////////////////
$model Polygon
{
ceda::xvector<Point> V;
// Unfortunately C++ doesn't take transitive closure on implicit conversion.
// So even though have implicit conversion from Square to Rect, and Rect to Polygon
// we don't automatically get the conversion from Square to Polygon.
$$(const Square& s)
{
V.push_back(TopLeft(s));
V.push_back(TopRight(s));
V.push_back(BotRight(s));
V.push_back(BotLeft(s));
}
$$(const Rect& r)
{
V.push_back(TopLeft(r));
V.push_back(TopRight(r));
V.push_back(BotRight(r));
V.push_back(BotLeft(r));
}
};
// Returns segment from vertex i-1 to i
inline Line Segment(const Polygon& p, ceda::ssize_t i)
{
ceda::ssize_t previ = (i == 0 ? p.V.size() : i) - 1;
return Line(p.V[previ], p.V[i]);
}
inline ceda::ssize_t NumVertices(const Polygon& p)
{
return p.V.size();
}
inline ceda::ssize_t NumSegments(const Polygon& p)
{
return p.V.size();
}
ceda::float32 Perim(const Polygon& p)
{
ceda::float32 P = 0;
for (ceda::ssize_t i=0 ; i < NumSegments(p) ; ++i)
{
P += Length(Segment(p,i));
}
return P;
}
ceda::float32 Area(const Polygon& p)
{
ceda::float32 A = 0;
for (ceda::ssize_t i=0 ; i < NumSegments(p) ; ++i)
{
Line l = Segment(p,i);
A += (l.p2.x - l.p1.x) * (l.p1.y + l.p2.y);
}
return A/2;
}
////////////////////////////////////
$variant Shape
{
default Circle(Point(2,1),10);
Point;
Line;
Square;
Rect;
Circle;
Polygon;
};
/*
Polymorphic functions on variants
---------------------------------
The polymorphic Area(Shape) function is automatically written for you using a switch
statement on the tag, calling the appropriate Area() function on the data types
declared in the variant.
Since this form of polymorphism doesn't involve a vtable, it makes more sense to use
free functions than class methods:
float 32 Area(const Shape& s);
This is particular important for multiple dispatch, which makes it even clearer that
we don't treat the first argument specially.
*/
/*
Declare a polymorphic function to be generated on a variant. This generates the
following code:
ceda::float32 Area(shape::Shape const& s)
{
switch(s.GetTag())
{
case 0 : return Area(s.as<shape::Point>());
case 1 : return Area(s.as<shape::Line>());
case 2 : return Area(s.as<shape::Square>());
case 3 : return Area(s.as<shape::Rect>());
case 4 : return Area(s.as<shape::Circle>());
case 5 : return Area(s.as<shape::Polygon>());
default: cxAssertUnreachable();
}
}
*/
$polymorphic ceda::float32 Area([const Shape& s]);
// We can also pass by value for a polymorphic type
$polymorphic ceda::float32 Perim([Shape s]);
///////////////////////////////////////////////////////////////////////////////////////////////
// Mutative polymorphic functions
void Offset(Point& p, ceda::float32 dx, ceda::float32 dy)
{
p.x += dx;
p.y += dy;
}
void Offset(Line& l, ceda::float32 dx, ceda::float32 dy)
{
Offset(l.p1, dx,dy);
Offset(l.p2, dx,dy);
}
void Offset(Square& s, ceda::float32 dx, ceda::float32 dy)
{
Offset(s.p1, dx,dy);
}
void Offset(Rect& r, ceda::float32 dx, ceda::float32 dy)
{
Offset(r.p1, dx,dy);
Offset(r.p2, dx,dy);
}
void Offset(Circle& c, ceda::float32 dx, ceda::float32 dy)
{
Offset(c.c, dx,dy);
}
void Offset(Polygon& p, ceda::float32 dx, ceda::float32 dy)
{
for (ceda::ssize_t i=0 ; i < p.V.size() ; ++i)
{
Offset(p.V[i], dx,dy);
}
}
$polymorphic void Offset([Shape& s], ceda::float32 dx, ceda::float32 dy);
///////////////////////////////////////////////////////////////////////////////////////////////
/*
Multiple dispatch
-----------------
Multiple dispatch is normally a pain in C++.
To compute the area of intersection between two shapes requires multiple dispatch.
However there are N^2 combinations, and in any case these functions are too difficult
to implement for just an illustrative example. Therefore we implement 6x6 = 36 simple
stub functions instead.
*/
@def mShapesTypes = [Point, Line, Square, Rect, Circle, Polygon]
@for (T1 in mShapesTypes)
{
@for (T2 in mShapesTypes)
{
ceda::float32 AreaOfIntersection(const T1& t1, const T2& t2)
{
Tracer() << "AOI(" << t1 << ',' << t2 << ")\n";
return 0;
}
}
}
$polymorphic ceda::float32 AreaOfIntersection([const Shape& s1],[const Shape& s2]);
//////////////////////////////////////////////////////////////////////////////////////////
// Test code
void Compare(const Shape& s1,const Shape& s2)
{
if (s1 == s2)
{
Tracer() << s1 << " == " << s2 << '\n';
}
else
{
Tracer() << s1 << " != " << s2 << '\n';
}
}
void TraceInfo(Shape s)
{
@for (T in mShapesTypes)
{
if (s.is<T>())
{
Tracer() << @str(type = T value = ) << s.as<T>() << '\n';
}
}
Tracer() << "Area = " << Area(s) << '\n';
Tracer() << "Perim = " << Perim(s) << '\n';
}
Polygon MakeTriangle(Point p1, Point p2, Point p3)
{
Polygon pg;
pg.V.push_back(p1);
pg.V.push_back(p2);
pg.V.push_back(p3);
return pg;
}
void Run()
{
ceda::TraceGroup g("Shape");
@for (T in [Point, Line, Square, Rect, Circle, Polygon, Shape])
{
Tracer() << @str(Size of T = ) << sizeof(T) << '\n';
}
{
Shape s;
Tracer() << "\nDefault ctor : " << s << '\n';
TraceInfo(s);
}
@def mShapes =
{
[
Shape(),
Point(10,11),
Line(Point(0,0),Point(100,50)),
Square(Point(1,2),3),
Rect(Point(0,0),Point(100,50)),
Rect(Point(1,2),Point(4,5)),
Circle(Point(10,10),100),
Circle(Point(10,10),101),
MakeTriangle(Point(0,0), Point(50,50), Point(100,0)),
]
}
@for (v in mShapes)
{
{
Tracer() << "\n" << @str(v) << '\n';
Shape s = v;
Tracer() << s << '\n';
TraceInfo(s);
Offset(s, 20,25);
Tracer() << "offset(20,25) --> " << s << '\n';
if (s.is<Line>())
{
Tracer() << "length = " << Length(s.as<Line>()) << '\n';
}
if (s.is<Circle>())
{
s.as<Circle>().r *= 2;
Tracer() << "scaled circle radius by 2 --> " << s << '\n';
}
if (s.is<Point>())
{
s.as<Point>().x += 1000;
s.as<Point>().y += 1000;
Tracer() << "offset point by (1000,1000) --> " << s << '\n';
}
if (s.is<Polygon>())
{
s.as<Polygon>().V.push_back(Point(1,2));
Tracer() << "appended vertex (1,2) --> " << s << '\n';
}
if (s.is<Square>())
{
Rect r = s.as<Square>();
Tracer() << "as rectangle --> " << r << '\n';
{
ceda::TraceIndenter indent;
TraceInfo(r);
}
Polygon p = s.as<Square>();
Tracer() << "as polygon --> " << p << '\n';
{
ceda::TraceIndenter indent;
TraceInfo(p);
}
}
}
}
Tracer() << '\n';
@for (v1 in mShapes)
{
@for (v2 in mShapes)
{
{
Tracer() << @str(Calling AOI on v1 & v2) << '\n';
ceda::TraceIndenter indent;
AreaOfIntersection(v1,v2);
}
}
}
Tracer() << '\n';
@for (v1 in mShapes)
{
@for (v2 in mShapes)
{
Compare(v1,v2);
}
}
// Demonstrate serialisation of a xvector<Shape>
{
Tracer() << "\n";
ceda::xvector<Shape> L;
@for (v in mShapes)
{
L.push_back(v);
}
ValididateSerialisation(L);
}
}
}