std::sort and third argument

I have to use st::sort. In the cmp function I have, I want to have a variable that I have computed preveiously, but will be for all the cmp calls the same. Now, because I was eager to see my result, I placed the variable (P0) as global... :/ ( heartbreaking ). Is there any way to do it a more elegant way?

And the relative code

Code:

Point_2 P0; //global
...
std::cout<<"SORT<----------------"<<std::endl;
std::sort(P.begin(), P.end(), cmp);
std::copy(P.begin(), P.end(), out);

...

// Definition of the function
bool cmp(const Point_2 &a, const Point_2 &b)
{
        double aRad = findRad(a, P0);
        double bRad = findRad(b, P0);

        if(aRad < bRad)
                return true;
        if(aRad == bRad)
        {
                if(a.y() > b.y())
                        return true;
                else if(a.y() == b.y() && a.x() > b.x())
                        return true;
                else
                        return false;
        }
        return false;
}

What is P0?

Is a point in R² . I have typedef'ed it.

Code:

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2      Point_2;

But then I have to read from the stream and decide which one of the points from this stream is really P0. I mean that I am finding that out at runtime. It is not a constant.
Here is the code

Code:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/convex_hull_2.h>
#include <stack>
#include <CGAL/Polygon_2.h>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2      Point_2;
typedef CGAL::Polygon_2<K> Polygon;

Point_2 P0;

bool duplicatePoint(std::vector< Point_2 >  &P, int pointPos, Point_2 &point);
bool cmp(const Point_2 &a, const Point_2 &b);
double findRad(const Point_2 &P, const Point_2 &P0);

int main()
{
  CGAL::set_ascii_mode(std::cin);
  CGAL::set_ascii_mode(std::cout);
  std::istream_iterator< Point_2 >  in_start( std::cin );
  std::istream_iterator< Point_2 >  in_end;
  std::ostream_iterator< Point_2 >  out( std::cout, "\n" );

  std::vector< Point_2 >  P (in_start, in_end);

  std::vector< Point_2 >  Q;

        P0 = P[1];
        int posP0 = 1;
        // Srart from zero, in case 1st and 2nd points
        // have same y coordinates
        for(int i = 0 ; i < P.size() ; i++)
        {
                if( duplicatePoint(P, i, P[i]) )
                        P.erase (P.begin()+i);
                if( P[i].y() < P0.y() )
                {
                        P0 = P[i];
                        posP0 = i;
                }
                if( P[i].y() == P0.y() )
                        if( P[i].x() < P0.x() )
                        {
                                P0 = P[i];
                                posP0 = i;
                        }
        }
....

Originally Posted by std10093

Is there any way to do it a more elegant way?

Well the third argument of std::sort is almost always a functor. A functor is a class that defines operator(), and in this case it would be your comparison. P0 can be declared as a member of the functor class and updated accordingly in operator().

Of course the key word here is functor so you might want to google it.

But I do not want the P0 to be updated

When I reach the line where sort is called, P0 is set and will not change until the program terminates. Is this is somehow helpful ?

Originally Posted by std10093

When I reach the line where sort is called, P0 is set and will not change until the program terminates. Is this is somehow helpful ?

That is perfectly fine: just initialise it in the constructor.

Originally Posted by std10093

But I do not want the P0 to be updated

When I reach the line where sort is called, P0 is set and will not change until the program terminates. Is this is somehow helpful ?

Then, um, don't update it. I'm under the wrong impression perhaps. If you need P0 for the comparison and nothing else, that is another reason to include it as a data member in the functor I think.

Hmm sorry for not getting what you want to say, but I want to be 100% I understood correct.
laserlight I do not have a constructor
Whiteflags, it is not clear to me if I need to use what you say or not

Maybe I should post all the code, so that you get the whole image

Code:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/convex_hull_2.h>
#include <stack>
#include <CGAL/Polygon_2.h>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2      Point_2;
typedef CGAL::Polygon_2<K> Polygon;

Point_2 P0;

bool duplicatePoint(std::vector< Point_2 >  &P, int pointPos, Point_2 &point);
bool cmp(const Point_2 &a, const Point_2 &b);
double findRad(const Point_2 &P, const Point_2 &P0);

int main()
{
  CGAL::set_ascii_mode(std::cin);
  CGAL::set_ascii_mode(std::cout);
  std::istream_iterator< Point_2 >  in_start( std::cin );
  std::istream_iterator< Point_2 >  in_end;
  std::ostream_iterator< Point_2 >  out( std::cout, "\n" );

  std::vector< Point_2 >  P (in_start, in_end);

  std::vector< Point_2 >  Q;

        P0 = P[1];
        int posP0 = 1;
        // Srart from zero, in case 1st and 2nd points
        // have same y coordinates
        for(int i = 0 ; i < P.size() ; i++)
        {
                if( duplicatePoint(P, i, P[i]) )
                        P.erase (P.begin()+i);
                if( P[i].y() < P0.y() )
                {
                        P0 = P[i];
                        posP0 = i;
                }
                if( P[i].y() == P0.y() )
                        if( P[i].x() < P0.x() )
                        {
                                P0 = P[i];
                                posP0 = i;
                        }
        }

        std::cout<<" MIN = " <<P0<<std::endl;

        P.erase(P.begin() + posP0);

        std::cout<<"input<----------------"<<std::endl;
        std::copy(P.begin(), P.end(), out);

        std::cout<<"SORT<----------------"<<std::endl;
        std::sort(P.begin(), P.end(), cmp);
        std::copy(P.begin(), P.end(), out);

        /* compute convex hull in Q from input P */
        Q = P;

//TEST  CGAL::convex_hull_2(Q.begin(), Q.end(), out ) ;

        std::stack<Point_2> S;
        S.push(P0);
        S.push(P.at(1));
        S.push(P.at(2));

        Point_2 TOP;
        Point_2 NEXTtoTOP;
        for( int i = 3 ; i < P.size() ; i++ )
        {
                std::cout<<"Loop "<<i<<std::endl;
                TOP = P.top();
                P.pop();
                NEXTtoTOP = P.top();
                P.push(TOP);


        }

        std::cout<<"result<----------------"<<std::endl;
        std::copy(Q.begin(), Q.end(), out);

        return 0;
}

bool duplicatePoint(std::vector< Point_2 >  &P, int pointPos, Point_2 &point)
{
        for(int i = 0 ; i < pointPos ; i++)
                if(P[i] == point)
                        return true;
        return false;
}

bool cmp(const Point_2 &a, const Point_2 &b)
{
        double aRad = findRad(a, P0);
        double bRad = findRad(b, P0);

        if(aRad < bRad)
                return true;
        if(aRad == bRad)
        {
                if(a.y() > b.y())
                        return true;
                else if(a.y() == b.y() && a.x() > b.x())
                        return true;
                else
                        return false;
        }
        return false;
}

double findRad(const Point_2 &P, const Point_2 &P0)
{
        double dx, dy;
// Here is where I need P0 <-------------------------------------------------
        dx = P.x() - P0.x();
        dy = P.y() - P0.y();

if( dx == 0 && dy ==0 )
        {
                std::cout<< " In function findRad, atan result is UNDEFINED! Return 0! "$
                return 0.0;
        }

        return( atan2(dx, dy) * (-1.00) );
}

There is an error when I call the stack, but I have fixed it in my latest version. Ignore the stack part

Originally Posted by std10093

I do not have a constructor

That's because you currently are using a function for the comparator; functions do not have constructors.

The idea here is to use a function object (functor), e.g.,

Code:

class Point_2_Compare
{
public:
    explicit Point_2_Compare(const Point_2 &P0_) : P0(P0_) {}

    bool operator()(const Point_2 &a, const Point_2 &b) const
    {
        double aRad = findRad(a, P0);
        double bRad = findRad(b, P0);

        if(aRad < bRad)
            return true;
        if(aRad == bRad)
        {
            if(a.y() > b.y())
                return true;
            else if(a.y() == b.y() && a.x() > b.x())
                return true;
            else
                return false;
        }
        return false;
    }
private:
    Point_2 P0;
};

// ...

std::sort(P.begin(), P.end(), Point_2_Compare(P0));

Now P0 can be declared in main.

WOW ! I didn't even know what that is! Brilliant! Many thanks to everybody!!!

You could use a lambda, too. It's mostly syntactic sugar (less code), but I'm throwing it in here for educational purposes (making you aware it exists and can be used).

Hmm I have heard about λ .. I am not going to use it, but I will have a google on it Thanks Elysia

Lambda functions fit perfectly for sort (provided you are using C++11). So to stress more Elysia's point here is how it would like like (or close to that).

Code:

std::sort(P.begin(), P.end(),
       [&](const Point_2 &a, const Point_2 &b)
{
          double aRad = findRad(a, P0);
          double bRad = findRad(b, P0);
 
          if(aRad < bRad)
              return true;
          if(aRad == bRad)
          {
            if(a.y() > b.y())
                return true;
            else if(a.y() == b.y() && a.x() > b.x())
                return true;
            else
                return false;
          }
          return false;
});

Apart from saving you code and not requiring you to define a one-use class, this makes it more optimal as well. For example, you don't need to copy PO into a temporary object (your functor) you can just access it provided it is within the scope. Of course, lambda usage implies that you won't be calling sort() all over your code, but once.

That's a bit much imo. I suppose I should be glad it's not like this in C++, but in python the lambda function has to be one statement long. Aside from that, std10093 wanted P0 to be associated with the comparison. With lambdas I think it has to be global again, which is not so great; with functors, it can just be a data member like everyone said.

I find that comparison function very difficult to reason about is correctness. A nicer way of writing it would be:

Code:

        double aRad = findRad(a, P0);
        double bRad = findRad(b, P0);

        if (aRad < bRad)
            return true;
        if (aRad > bRad)
            return false;

        if (a.y() > b.y())
            return true;
        if (a.y() < b.y())
            return false;

        return a.x() > b.x());