View source for GSoC 2016 Better data structure for selections

This page contains information about "Better data structure for selections" implemented by [[User:AdrianBoguszewski|Adrian Boguszewski]]. The mentor is [[User:Tweenk|Krzysztof Kosiński]].

The code is avaiable here: [https://code.launchpad.net/~adrianboguszewski/inkscape/adrian]. It has been merged into trunk in rev. 15047.

==Project==

===Goal===

This project would involve implementing an <code>Inkscape::ObjectSet</code> object that would serve as a base for <code>Inkscape::Selection</code>. The internal data structure should support fast lookup (checking whether a given object belongs to the set) and preserve the order of insertion (so that we can still determine which object was selected first or last). Internally, <code>ObjectSet</code> can be based on a Boost multi-index container with a list index and a hash index.

===Implementation===

Following work has been done:
* created ObjectSet class to be a base class for Selection - ObjectSet has a multi_index_container from Boost [http://www.boost.org/doc/libs/1_61_0/libs/multi_index/doc/tutorial/basics.html] instead many containers like vectors, lists and sets
* created appropiate tests for this class in GoogleTest framework
* replaced some functions returning vector to return range [http://www.boost.org/doc/libs/1_61_0/libs/range/doc/html/range/reference/adaptors/introduction.html]
* replaced own children list implementation from SPObject with boost intrusive list
* added tests for new children list
* replaced parameters in some functions (Selection with ObjectSet)
* improved spray tool (there is no need to use selection now)
* tests are split into separate executables

===Problems===

The main and not solved problem at the same time is a segmentation fault occurring when range functions are used. For example: if you declare range as follows:
 typedef boost::any_range<
     XML::Node*,
     boost::bidirectional_traversal_tag,
     XML::Node* const&,
     std::ptrdiff_t> XMLNodeRange;
 
 struct is_item {
     bool operator()(SPObject* obj) {
         return SP_IS_ITEM(obj);
     }
 };
 
 struct object_to_node {
     typedef XML::Node* result_type;
     XML::Node* operator()(SPObject* obj) const {
         return obj->getRepr();
     }
 };

and then call following function:

 XMLNodeRange ObjectSet::xmlNodes() {
     return XMLNodeRange(container.get<random_access>() | boost::adaptors::filtered(is_item()) | boost::adaptors::transformed(object_to_node()));
 }

the objects inside the range are invalid and cause segmantation fault, but if you declare XMLNodeRange like below:

 typedef decltype(MultiIndexContainer().get<random_access>() | boost::adaptors::filtered(is_item()) | boost::adaptors::transformed(object_to_node())) XMLNodeRange;

everything works.

Here is a minimal code, which causes above issue: [https://github.com/adrianboguszewski/inkscape-range-problems]

===Examples===

* create new ObjectSet object from Selection object (containing the same objects)

 ObjectSet object_set = *desktop->getSelection()

* get items from object set

 auto items = selection->items();

* iterate xml nodes in object set

 auto nodes = selection->xmlNodes();
     for (auto l = nodes.begin(); l != nodes.end() ;++l) {
         // do something
     }

* iterate SPObject children

 for (auto& child: object->children) {
     \\ do sth
 }