Box type with value and pointer type of points

[Mitsuru]

Dear all,

Box type (with minimum and corners of point type which contains x,y,z coordinates) is often used in programming.

Sometimes it is useful to use value type of points (c.f. Box_v) or pointer type of points (c.f. Box_p) case-by-case.
I am wondering if the both is integrated into one type by using template technique.

However, I cannot grasp the risks such as the below
(1) does constructor passed by value or by reference (or pointer) is correctly switched?
(2) Is access to coordinates well recognized? (dot operator and allow operator)
(3) When calling function which returns one of points, is it possible to return another type?
(c.f. if pointer type is contained, is it possible to return value type's? If so, how to program the counter type in template manner?)

If you have some experience, I would appreciate it if you could advise me.

Kind regards,


=========================================================================
struct Box_v{
point min_point;
point max_point;
}

struct Box_p{
point* min_point;
point* max_point;
}

template<typename point_t>
struct Box_t{
point_t min_point;
point_t max_point;
}
=========================================================================

[CABrouwers]

I would rather derive Box_v from Box_p. Then you can define all your methods in the Box_p classes and they will work for both classes. You will also be able to mix and match the two types. Of course, that increases the storage used by Box_v.

struct Box_p{
point* min_point;
point* max_point;
public:
box_p(point* min,point* max):min_point(min),max_point(max){}
}

struct Box_v: public: Box_p{
point min_point;
point max_point;
public:
Box_v((point* min,point* max):box_p(&min_point,&min_point),min_point(min),max_point(max){}
}

Alternatively, you can make both classes derive from a virtual class, where all your method are defined; and in each of the derived class, you program different accessor functions for the min and max points.


The problem with the template approach is that the pointer type and the value type will require different ways to access the data (with and without * dereferencing) which will be pervasive throughout the code. So you will end up having to specialize each template which defeats the purpose.

[Mitsuru]

Dear CABrouwers

Thank you for your comment.

I understand one way to handle the two types is to use derivation.
However, for my purpose, a lot of boxes are used,
so that memory & accessing consumption are needed to be less as possible as I can.

Perhaps, I think difference in access notation to points is coped with by following a manner of the boost geometry,
which enables static access to coordinates in both types.

https://www.boost.org/doc/libs/1_53_0/libs/geometry/doc/html/geometry/design.html


I suppose how to tackle the problem (3).
(In template techniques, is there describing way to judge typename is pointer or not, and convert them to value type?)

Kind regards

[CABrouwers]

Mitsuru,

Here is a solution to your problem based on derivation from a common virtual class

#include <iostream>
#include <math.h>


struct point{
    double x,y;
    point(double x_val, double y_val):x(x_val),y(y_val){}
};

struct Box_v; //forward declaration needed for  the line:  Box_v scale(double f);

//this is the base class where all the method can be defined for both versions. 
struct Box{
    virtual  point& min_point()=0;  //min_point/max_point accessor, =0 means it is virutal  and
    virtual  point& max_point()=0;  //needs to be implemented in every derived classes
    double area(){return fabs((max_point().x-min_point().y)*(max_point().y-min_point().y));} //one example of method;
    Box_v scale(double f); //this method always return Box_v version even if called from a Box_. This is only the declaration.
};


struct Box_v : public Box{   //Box_v derives from Box;
point _min_point;
point _max_point;
Box_v( point pmin, point pmax):_min_point(pmin),_max_point(pmax){}
 point& min_point(){return _min_point;}  //accessor for v version
 point& max_point(){return _max_point;}
};


struct Box_p : public Box{   //Box_v derives from Box;
 point* _min_point;
 point* _max_point;
Box_p( point* pmin, point* pmax):_min_point(pmin),_max_point(pmax){}
 point& min_point(){return * _min_point;} //accessor for p versions
 point& max_point(){return * _max_point;}
};

//this is the definition of the Box::scale, it needs to be located after Box_v is completely declared.
Box_v Box::scale(double f){return Box_v(point(min_point().x * f,min_point().y * f),point(max_point().x * f,max_point().y * f));}

int main(){
    
point p1(5,10);
point p2(15,30);

Box_v b1(p1,p2);
std::cout << "b1:" << b1.area() << std::endl;

Box_p b2(&p1,&p2);
std::cout << "b4:" <<  b2.area() << std::endl;

Box_v b3 = b1.scale(10);  
std::cout << "b3:" <<  b3.area() << std::endl;

Box_v b4 = b2.scale(10);  // scale always return a Box_v 
std::cout << "b4:" <<  b4.area() << std::endl;

Box &b5 = b2;  // you cannot create a Box you can have a reference for a Box, the correct version of the accessors will be called. 
std::cout << "b5:" <<  b5.area() << std::endl;

}

You could get to the same result with a template approach, but it would be more complicated. Think of a template as an automated way to write code. The end result would be exactly the same as the above. Templates are helpful when there is a lot of repetitive code, but if you look a the definition of Box_v and Box_p you see the code is very different because the pointer dereferencing operator is all over the Box_p version. You can achieve that in a template, but it would not be simpler. In the version above all the common code is pushed in the base version and there is no repetition.

By the way, I used pointers as in your example, but I suspect you probably want to use references,

Now, you might still want a template version in two cases

1. There is a very slight processor overhead when using virtual/ functions/classes. If you are really after the last % of speed, a template will do better (or you can just copy the code twice with the few necessary modifications!). You will have two unrelated classes stemming for the same template.

2. If what you are really trying to do is allow calling one single constructor with with either an lvalue Box(p1,p2) or with an rvalue Box(point(1,2),point(2,3)). In the first case, you will probably want to pass the argument by reference. In the second case, the points are temporary values that need to be stored in the class. Relying on template argument deduction you can "hide" the fact that you have two different classes. By combining this approach with the virtual class approach you can make your code look as if there was only one type of object. This is just cosmetics, in reality, you are letting the compiler do the job of figuring out when to use one of there other.
I posted something on the topic a few weeks ago http://www.cplusplus.com/forum/general/249654/

if you are interested, I can show you how to do that in your case.

[CABrouwers]

Mitsuru,

I found the time to do the template version. In the current form, it needs to be compiled under c++17.

I changed from pointers to references in the definition of the class but it accepts pointers in the constructor

The code uses SFINAE class specialization. It takes a little time to understand if you are not familiar.
(https://www.fluentcpp.com/2018/05/15/make-sfinae-pretty-1-what-value-sfinae-brings-to-code/)

And also I use auto-typing, which is not indispensable but make the code lighter.

Hope this helps.

CAB

#include <iostream>
#include <math.h>

// need to be compiled with c++17 otherwise the auto will need to be replaced. 

struct point{
    double x,y;
    point(double x_val, double y_val):x(x_val),y(y_val){}
};

template<class T,class X = nullptr_t > //the second parameter is used to specialize the class
class iBox; //forward declaration  of the derived template class need here because of the methd "auto scale()"

//this is the base class where all the method can be defined for both versions. 
class Box{
    public:
    virtual  point& min_point()=0;  //min_point/max_point accessor, =0 means it is virtual  and
    virtual  point& max_point()=0;  //needs to be implemented in every derived classes
    double area(){return fabs((max_point().x-min_point().x)*(max_point().y-min_point().y));} //one example of method;
    auto scale(double f); //this method always returns Box of type && 
};


template<class T>  //std::enable ... specilizes the case when the points are passed as references
class iBox<T,typename std::enable_if<std::is_lvalue_reference<T>::value,nullptr_t>::type> 
        : public Box {
point& _min_point;
point& _max_point;
public:
iBox(point& pmin, point& pmax):_min_point(pmin),_max_point(pmax){}
iBox(point* pmin, point* pmax):_min_point(*pmin),_max_point(*pmax){}
 point& min_point(){return _min_point;}  
 point& max_point(){return _max_point;}
};

template<class T> //std::enable ... specilizes the case when the points are passed as ralue (temporaries here)
class iBox<T,typename std::enable_if<std::is_rvalue_reference<T>::value,nullptr_t>::type> 
        : public Box{   
point _min_point;
point _max_point;
public:
iBox(T&& pmin,T&& pmax ):_min_point(std::move(pmin)),_max_point(std::move(pmax)){}
point& min_point(){return _min_point;} //accessor for p versions
point& max_point(){return _max_point;}
};


template<class T> //factory functions that dispathc the call the right calls, no need wiht c++17
iBox<T&> Make_Box(T& pmin, T& pmax ){return iBox<T&>(pmin,pmax);}

template<class T> //factory functions that dispathc the call the right calls, no need wiht c++17
iBox<T&> Make_Box(T* pmin, T* pmax ){return iBox<T&>(*pmin,*pmax);}

template<class T>
iBox<T&&> Make_Box(T&& pmin,T&& pmax ){ return iBox<T&&>(std::move(pmin),std::move(pmax));}

typedef decltype(Make_Box(point(0,0),point(0,0))) Box_v; //this just give a name to the two types of classes, it is not needed
typedef decltype(Make_Box(std::declval<point&>(),std::declval<point&>())) Box_r;

//this is the definition of the Box::scale, it needs to be located after iBox is completely declared.
auto Box::scale(double f){return Make_Box(point(min_point().x * f, min_point().y * f),point(max_point().x * f,max_point().y * f));}

int main(){
    
point p1(5,10);
point p2(15,30);

auto b1  = Make_Box(p1,p2);
std::cout << "b1:" << b1.area() << std::endl;

auto b2 = Make_Box(point(5,20),point(15,50));
std::cout << "b2:" <<  b2.area() << std::endl;

auto  b3 = b1.scale(10);  
std::cout << "b3:" <<  b3.area() << std::endl;

auto b4 = b2.scale(10);  // scale always return a Box_v 
std::cout << "b4:" <<  b4.area() << std::endl;

Box &b5 = b2;  // you cannot create a Box you but can createv a reference for a Box, the correct version of the accessors will be called. 
std::cout << "b5:" <<  b5.area() << std::endl;

Box_v  b6(point(5,20),point(15,50));

}

[Duthomhas]

@Mitsuru

I actually think that so far an important issue has been missed.

Sometimes it is useful to use value type of points (c.f. Box_v) or pointer type of points (c.f. Box_p) case-by-case.

No, it is not. It is a design failure to mix things like that.

When designing, choose a representation and stick to it. If some algorithm wants to be able to modify points, it should take a reference to a point (point_t& or *point_t), not the individual components of the point.

The most common case for a box is to union individual values against two points, and to interpret the second pair as required:

template <typename T>
struct Point {
  T x;
  T y;
  Point(): x(T()), y(T()) { }
  Point( T x, T y ): x(x), y(y) { }
};

template <typename T>
union Box {
  struct { T left, T top, T right, T bottom };
  struct { T x,    T y,   T width, T height };
  struct { Point<T> topLeft, bottomRight };
  Box(): left(T()), top(T()), right(T()), bottom(T()) { }
  Box( T width, T height ): left(T()), top(T()), right(width), bottom(height) { }
  Box( T left, T top, T right, T bottom ): left(left), top(top), right(right), bottom(bottom) { }
};

With this you can use it very conveniently for all kinds of point/box related issues:

  Image1.Canvas.Draw( 
    MyBitmap, Box<int>( x, y, x+MyBitmap.Width, y+MyBitmap.Height )
  );

  auto c = Intersect( Sprite1.BoundsBox, Sprite2.BoundsBox );
  if ((c.right - c.left) > 0)
  {
    // Collision!
  }
  else
  {
    // Miss!
  }

If a function needs to do any coordinate modification, it can either return a new point/box, or take a reference:

template <typename T>
void BoundsToSize( Box<T> & box )
{
  box.right  += box.left;
  box.bottom += box.top;
  box.topLeft = Point<T>( 0, 0 );
}

And using it:

  auto b = MyImage.BoundsRect;
  BoundsToSize( b );
  std::cout << "image width, height is " << b.width << ", " << b.height << "\n";

If you are forced to mix things as per your OP (because you are using a well-written library and also using one that was written stupidly), then simply translate between the two with a helper function:

Box_p Box_to_StupidBox( const Box_t& box )
{
  return Box_p(
    &box.min_point.x, &box.min_point.y,
    &box.max_point.x, &box.max_point.y );
}

Again, usable:

  auto b = Image1.BoundsRect;

  Other_API_Using_Box_p( Box_to_StupidBox( b ) );

  std::cout << "b is modified to: " << b.min_point.x << ...

Oh, one last thing: POSIX reserves names ending in “_t”. It is good advice to avoid using such constructs.

Borland/CodeGear/Embarcadero/whatever uses the Capital-T prefix:
    TBox

I have also seen it as a postfix (which the Standard Library also tends to do for templated names):
    BoxT

I personally use capitalization to distinguish things:

struct Student
{
  std::string surname, given_name;
  double grade;
  ...
};

int main()
{
  std::vector<Student> students;

  for (student : students)
  {
    std::cout 
      << student.surame
      << ", "
      << student.given_name[0]
      << " has a " << student.grade
      << "\n";
  }

Hope this helps.

[Mitsuru]

Dear CABrouwers

I deeply thank for your spending time to write code and teaching me.
I willingly study what you told me, and consider how to introduce it to my programs.
(SFINAE is new for me, thank you, I will learn the pattern).


Dear Duthomhas

Thank you for your advice.

>> I actually think that so far an important issue has been missed.
>> Sometimes it is useful to use value type of points (c.f. Box_v) or pointer type of points (c.f. Box_p) case-by-case.
>> No, it is not. It is a design failure to mix things like that.

Could you explain the reason you said?
For my intention, some geometric type (Not only box, but also triangle, polyhedron etc.) is assembled to shape forms, and they share some geometric primitives (Not only points, but also edges, faces).
It is well known that some data structures are used in order to save memory and computing time.
(Example is triangle meshes as the below Page16)
https://www.cs.cornell.edu/courses/cs4620/2017sp/slides/02trimesh.pdf

The above example is designed to refer the primitives by index numbers. But, if designed so, applying common functions (c.f. area, or center point calculations) entails construction of geometric types, which leads to overhead.
Perhaps, if pointer type (or reference type) of geometric type are mixed, this should lead to reducing such overhead and avoiding combinatorial explosion of implementation of each function.

As you said, is it important to stick to one representation?
I would like to know the reason.

>> (because you are using a well-written library and also using one that was written stupidly)
About boost and its geometry library? Partially I agree.

[Duthomhas]

Which is more overhead, a bunch of integers/floats/whatever...

or a bunch of integers/floats/whatever AND a bunch of pointers to all those integers/floats/whatever.


The Boost.Geometry seems to be fairly well-written IMHO. Further, I see no evidence it uses pointers at all, let alone anything like Box_p does.


However, Boost.Geometry has as a goal some fairly extreme flexibility, leading to some fairly complex template magic.

Unless you are writing a fairly complex system, you might consider it more worth your time to keep things simple, and avoid all the over-the-top template stuff that all the kids are sniffing these days. They’ll regret it later in life.

[CABrouwers]

Where is the fun if not in trying various things; sometimes with success, sometimes not. That's how one learns!

Also, kids prefer Python anyway.

[Duthomhas]

True, The Python is pretty good stuff.

[JLBorges]

> I am wondering if the both is integrated into one type by using template technique.

A discriminated union (a union-like-class) is a possibility. For example:

#include <iostream>
#include <utility>

using point = std::pair<double,double> ;

struct box
{
    struct values { point a ; point b ; };
    struct addresses
    {
        const point* pa ;
        const point* pb ;
        constexpr operator values() const { return { *pa, *pb } ; }
    };

    constexpr box( point a, point b ) : v{a,b} {}
    constexpr box( const point* pa, const point* pb ) : holds_values(false), a{pa,pb} {}
    /* explicit */ constexpr box( const values& v ) : v(v) {}
    /* explicit */ constexpr box( const addresses& a ) : holds_values(false), a(a) {}

    constexpr box( const box& ) = default ;
    box& operator= ( const box& that )
    {
        holds_values = that.holds_values ;
        if(holds_values) v = that.v ;
        else a = that.a ;
        return *this ;
    }
    ~box() = default ;

    constexpr operator values() const { return holds_values ? v : a ; }
    constexpr operator addresses() const { return holds_values ? addresses{ &v.a, &v.b } : a ; }

    private:
        bool holds_values = true ;
        union
        {
            values v ;
            addresses a ;
        };
};

void foo( box::values, box::addresses ) { std::cout << "foo: values - addresses\n" ; }
void bar( box::addresses, box::values ) { std::cout << "bar: addresses - values\n" ; }
void baz( box, box::addresses, box::values ) { std::cout << "baz: box - addresses - values\n" ; }

int main()
{
    const point left { 1, 2 }, right { 3, 4 } ;

    box a( left, right ) ;
    const box b( std::addressof(left), std::addressof(right) ) ;

    foo(a,b) ; // foo: values - addresses
    bar(a,b) ; // bar: addresses - values
    baz( a, a, a ) ; // baz: box - addresses - values

    a = b ;
    // etc.
}

http://coliru.stacked-crooked.com/a/3645db7abe7595d6
https://rextester.com/DUDE24002

[CABrouwers]

It works but if the goal of using pointers or references was to save memory, it defeats the purpose. The union will be sized to hold the four doubles required by two points, that's 32 bytes. To that, add one other byte per box for the bool and you get to 33 bytes. On the other hand, two pointers only require 8 bytes on a 32-bit machine and 16 bytes on a 64-bit one.

The approach is nifty but the larger the object the more wasteful it will be.

[Duthomhas]

Er, where are you getting four pointers from?

And you cannot optimize away storage requirements. Two doubles will require what two doubles require. In this case, the pointer space requirement will be <= the double space requirement.

The union will hold a maximum of 2*8 = 16 bytes.

[Mitsuru]

Dear Duthomhas

> Which is more overhead, a bunch of integers/floats/whatever...
> or a bunch of integers/floats/whatever AND a bunch of pointers to all those integers/floats/whatever.

To avoid both situations (And, to realize no use of integers/floats/whatever' indexing, but just use of pointers to geometric primitive's type in the data pool, and then, sometimes, values evaluated in some cases), I need some techniques I asked.

I greatly agree with your opinion, simple is best, because complex techniques relating to template often bothers us, particularly for usual systems. Probably it has possibility to induce unintended behaviors (And, trace of codes is difficult).

But, some specific-purpose (c.f. mathematical etc) library adopts it in the benefit of efficient switches of static data and procedures in the compile time.
(c.f. https://www.cgal.org/ )

I think limited usage of template, suitable to it, is probably proved to work well.

> Where is the fun if not in trying various things; sometimes with success, sometimes not. That's how one learns!

I so agree with you, and I am fond of python. Python also likes C++.

[Mitsuru]

As my opinion, pros and cons of template technique are owing to the background of programmers.
I do not stick to modern or classic techniques neither.

My purpose is to attain the goal I asked in this thread, and hear a lot of opinions to study.

Thank you for your cooperation.

[Duthomhas]

@Mitsuru
I think we are not communicating the same point.

If you need to store data (integers/floats/whatever), there is no way around storing that data. Either you have all the required values or you do not. It does not matter whether they are stored in some pool memory somewhere — they must exist (else they are not necessary!).

Adding things to manage pools of memory, structures to pointers of data — that is all overhead.

Some overhead is always necessary. But IMO, in the case of geometric primitives, redirecting every datum through a pointer is excessive — it is a 50–100 percent increase (depending on the relative size of your data and the pointers) in memory to do it that way, and a measurable increase in time to process (because of the constant pointer redirection) — these are not improvements in data management.

Templates do not add or remove data. They are just a technique for managing compiler input.

Beware the falsehood that all ideas are equal. Just because a thing can be done one way does not justify doing it in liu of the costs of designing, understanding, and maintaining it.

A good rule of thumb: complexity is only justified for specific, measurable improvements in time, storage, and/or access. Less any of those, it is an unjustified waste of effort.

Hope this helps.

[Mitsuru]

Dear Duthomhas

I agree with you, so that we should communicate the same point. (Template is merely one of a lot of techniques)

> Some overhead is always necessary. But IMO, in the case of geometric primitives, redirecting every datum > through a pointer is excessive — it is a 50–100 percent increase (depending on the relative size of your
> data and the pointers) in memory to do it that way, and a measurable increase in time to process (because > of the constant pointer redirection) — these are not improvements in data management

To communicate the same point, could you explain the above?
How does 50–100 percent increase in memory occur when pointers to base data are used?
If you are correct, I have to redesign my software architecture.
And, I hope you tell me your recommendation of data arrangement of geometric primitives.

This is important point for me, and deserves rethinking of my software's design.
I would appreciate it if you could tell me.

Kind regards

[Duthomhas]

#include <iostream>
#include <vector>

struct Point_Value
{
  double x, y;
  Point_Value( double x = 0, double y = 0 ): x(x), y(y) { }
};

struct Point_Pointer
{
  double* x;
  double* y;
  Point_Pointer( double* x = nullptr, double* y = nullptr ): x(x), y(y) { }
};

int main()
{
  std::vector <Point_Value> point_data;

  point_data.push_back( Point_Value( 1, 2 ) );
  point_data.push_back( Point_Value( 3, 4 ) );
  point_data.push_back( Point_Value( 5, 6 ) );
  point_data.push_back( Point_Value( 7, 8 ) );

  auto memory_requirement_1 = sizeof(Point_Value) * point_data.size();
  std::cout 
    << "Memory needed to store four points directly = " 
    << memory_requirement_1
    << "\n";
  for (const auto& p : point_data)
    std::cout << "(" << p.x << "," << p.y << ")\n";
  std::cout << "\n";
  

  std::vector <Point_Pointer> point_pointers;
  for (auto& p : point_data)
    point_pointers.push_back( Point_Pointer( &(p.x), &(p.y) ) );

  auto memory_requirement_2 = sizeof(Point_Pointer) * point_pointers.size() + memory_requirement_1;
  std::cout 
    << "Memory needed to store four points by reference = " 
    << memory_requirement_2
    << "\n";
  for (const auto& p : point_pointers)
    std::cout << "(" << *(p.x) << "," << *(p.y) << ")\n";
  std::cout << "\n";

  std::cout << "That is a " << (memory_requirement_2 * 100.0 / memory_requirement_1) << "% increase.\n";
}

Having a pointer to everything is ((size of a datum + size of a pointer) * number of data).

[Mitsuru]

Thank you, and I consider it.

[CABrouwers]

@Duthomhas

I didn't write four pointers but two. So we agree there, you really need only 16 bytes to store two pointers. However, you will use 33 bytes because of the union will have the size of the largest of the two potential values, which is the 32 bytes needed to hold four doubles. Add the bool and you get to 33. Also, every double version will carry the extra bool flag, so this is wasting memory in that side too.