Opened 8 years ago
Closed 8 years ago
#10615 closed Feature Requests (wontfix)
R-Tree: add constructor that converts any range<T> to the trees value type
| Reported by: | anonymous | Owned by: | Barend Gehrels |
|---|---|---|---|
| Milestone: | To Be Determined | Component: | geometry |
| Version: | Boost 1.56.0 | Severity: | Optimization |
| Keywords: | Cc: |
Description
I'd suggest adding a new constructor to rtree for bulk loading. It should take a range of any value and a function that converts the ranges value to the rtrees value.
My use case would be a (in my example: random access) container of points I need to put into an rtree with rtree::value_type being std::pair<point, container_index>. At the moment I need to
- transform my container of points to a container of pairs
- bulk load that new container of pairs
- let rtree constructor copy my container of pairs
- delete my intermediate container of pairs
I'd really like to move the transformation done in the first step into rtree ctor to avoid creating a temporary container just to copy it into rtree and destroy it immediately after the rtree is created.
Change History (4)
comment:1 by , 8 years ago
comment:2 by , 8 years ago
Thanks for your quick reply. That seems like the solution I've searched for (though in the wrong spot as I've looked in rtree when Boost.Range might do the trick) but a first test gives me compile errors about missing type and reference typedefs in boost::transform_iterator, a missing class template named result in what seems to be the lambda function fun in your example and again no matching function for call to begin(const boost::range_detail::transformed_range) and end with the same signature as begin.
So I'll try to sort out my problems and/or condense my code into a small example to seek further advice. Anyway, you can close this ticket, since even if constructing an rtree from an adapted range would fail right now your suggested solution is far more elegant and can be done without writing new library code.
As a sidenote - I might have overlooked it - but an example of rtree creation from an adapted range would probably help some narrow-minded users like me to realize that Boost.Range isn't just a few templates you need to specialize in order to get your stuff into Geometry.
comment:3 by , 8 years ago
So again, thank you and consider this solved. After I found time to actually read the Boost.Range documentation and not just wildly try stuff out it was easy to adapt my code and remove the additional copying of the container of points. For future reference I'll post a more complete solution, since it was not immediately obvious to me that I needed to create a good old functor instead of a lambda.
class my_point; //a point type known to Boost.Geometry typedef std::vector<my_point> point_list; typedef std::pair<my_point, point_list::size_type> indexed_point; struct add_index { typedef indexed_point result_type; template<typename T> inline result_type operator()(const T &v) const { return std::make_pair(v.value(), v.index()); } }; point_list p; //fill with points rtree<indexed_point, /*Parameters*/> rt1(p | boost::adaptors::indexed() | boost::adaptors::transformed(add_index()));
Thanks again for your hint and sorry for the noise in here.
comment:4 by , 8 years ago
| Resolution: | → wontfix |
|---|---|
| Status: | new → closed |
In my original example there is only transformed() used because initially I thought about calculating the index of a Point using iterator/pointer arithmetic, so something rather unsafe because if we at some later time changed vector to some other container the indexes would be invalid. So your solution using indexed() adaptor is more "correct".
Actually I thought that transformed() requires standard unary predicates like STL algorithms to e.g. support lambda functions. But now when I think of it, it'd require C++11 or Boost.TypeOf. Anyway it's inconvenient that it doesn't. If it did then e.g. in C++14 we could write:
// This doesn't work for now
rtree<indexed_point, /*Parameters*/>
rt1(p | boost::adaptors::indexed()
| boost::adaptors::transformed(
[](auto v) { return std::make_pair(v.value(), v.index()); }
));
Regarding the docs/example, the docs and the code can always be improved. I expect that your use case is quite common so an example could be helpful.
There is a hint in the docs, in the section Queries->Inserting query results into the other R-tree:
You may pass the result Range directly into the constructor or insert() member function.
RTree rt4(rt1 | bgi::adaptors::queried(bgi::intersects(Box(/*...*/)))));
but maybe something similar should be placed in the section Creation and Modification since it may be not obvious how Boost.Range and the rtree could be used together.
Thanks for suggestions!
AFAIU this musn't be done in the ctor. Doesn't transform adaptor meet your needs? Should this proposed ctor work differently than the code below? I'd prefer to not extend the interface if it was really not necessary.
rtree rt1(values | boost::adaptors::transformed(fun)); rtree rt2(boost::adaptors::transform(values, fun));