GSoC 2016 Better data structure for selections

This page contains information about "Better data structure for selections" implemented by Adrian Boguszewski. The mentor is Krzysztof Kosiński.

The code is avaiable here: [1]. It has been merged into trunk in rev. 15047.

Project

Goal

This project would involve implementing an Inkscape::ObjectSet object that would serve as a base for Inkscape::Selection. 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, ObjectSet 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 [2] 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 [3]
• 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: [4]

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
}