Geometry Boost List: Re: [geometry] sort points on single coordinate

Subject: Re: [geometry] sort points on single coordinate
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2015-07-15 17:14:41

Hi Hussein,

2015-07-15 20:11 GMT+02:00 Hussein Almashouq <hussein.almashouq_at_[hidden]
>:

> Greeting to all,
>
> Currently I'm using std::sort  on boost points on x-coordinte as follows
>
> typedef bg::model::point<long long, 2, bg::cs::cartesian> point;
>
> typedef std::pair<point, long long>  value_type;
>
>  std::vector<value_type> values;
>
> // for single attribute sort on point data sets
> // std::sort needs custom comparison operator
>
> struct PointLessX {
>     bool operator()(const value_type& p, const value_type& q) const
>     {
>         return bg::get<0>(p.first) < bg::get<0>(q.first);
>     }
> };
>
>
>     std::cout << "Sorting the data " << std::endl;
>     PointLessX x;
>     std::sort(values.begin(), values.end(), x);
>
>
>
> The above code is working fine but a bit slow when the # of points exceeds
> 10M.
>
> I looked at boost sort package and it seems it overcomes this issue
>
>
> http://www.boost.org/doc/libs/1_58_0/libs/sort/doc/html/index.html#sort.overview.intro
>
> However , I could not  figure out how to adapt it to sort my boost points
> which are of value type long. It seem that  I have to define some bit shift
> operator.
>
> Any suggestion please ?
>

I'm guessing you'd like to use integer_sort() ?
Have you tried to implement it like in this example:
http://www.boost.org/doc/libs/1_58_0/libs/sort/example/rightshiftsample.cpp
?

So indeed implement the rightshift function object:

struct RightShiftX {
  inline long long operator()(value_type const& p, unsigned offset) const {
return bg::get<0>(p.first) >> offset; }
};

And then pass both function objects into the sorting function:

boost::sort::spreadsort::integer_sort(values.begin(), values.end(),
RightShiftX(), PointLessX());

Regards,
Adam

P.S. This is a question more closely related to Boost.Sort than
Boost.Geometry. It could be asked on Boost-Users mailing list.