Added object set

(bzr r14954.1.1)

9 files changed, 555 insertions, 8 deletions

diff --git a/CMakeScripts/DefineDependsandFlags.cmake b/CMakeScripts/DefineDependsandFlags.cmake
index 0f4ba46c6..bf3954a62 100644
--- a/CMakeScripts/DefineDependsandFlags.cmake
+++ b/CMakeScripts/DefineDependsandFlags.cmake
@@ -10,6 +10,8 @@ list(APPEND INKSCAPE_INCS ${PROJECT_SOURCE_DIR}
     # generated includes
     ${CMAKE_BINARY_DIR}/include
 )
+# TODO temporary flag
+set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
 
 # ----------------------------------------------------------------------------
 # Files we include
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index df25728f4..802a79c4f 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -229,7 +229,9 @@ set(inkscape_SRC
 	message-context.cpp
 	message-stack.cpp
 	mod360.cpp
+	object.cpp
 	object-hierarchy.cpp
+	object-set.cpp
 	object-snapper.cpp
 	path-chemistry.cpp
 	persp3d-reference.cpp
@@ -353,7 +355,9 @@ set(inkscape_SRC
 	mod360-test.h
 	mod360.h
 	number-opt-number.h
+	object.h
 	object-hierarchy.h
+	object-set.h
 	object-snapper.h
 	object-test.h
 	path-chemistry.h
diff --git a/src/object-set.cpp b/src/object-set.cpp
new file mode 100644
index 000000000..f071aa4d6
--- /dev/null
+++ b/src/object-set.cpp
@@ -0,0 +1,133 @@
+/*
+ * Multiindex container for selection
+ *
+ * Authors:
+ *   Adrian Boguszewski
+ *
+ * Copyright (C) 2016 Adrian Boguszewski
+ *
+ * Released under GNU GPL, read the file 'COPYING' for more information
+ */
+
+#include "object-set.h"
+
+bool ObjectSet::add(Object* object) {
+    // any ancestor is in the set - do nothing
+    if (_anyAncestorIsInSet(object)) {
+        return false;
+    }
+
+    // check if there is mutual ancestor for some elements, which can replace all of them in the set
+    Object* o = _getMutualAncestor(object);
+
+    // remove all descendants from the set
+    _removeDescendantsFromSet(o);
+
+    _add(o);
+    return true;
+}
+
+bool ObjectSet::remove(Object* object) {
+    // object is the top of subtree
+    if (contains(object)) {
+        _remove(object);
+        return true;
+    }
+
+    // any ancestor of object is in the set
+    if (_anyAncestorIsInSet(object)) {
+        _removeAncestorsFromSet(object);
+        return true;
+    }
+
+    // no object nor any parent in the set
+    return false;
+}
+
+bool ObjectSet::contains(Object* object) {
+    return container.get<hashed>().find(object) != container.get<hashed>().end();
+}
+
+void ObjectSet::clear() {
+    for (auto object: container) {
+        _remove(object);
+    }
+}
+
+int ObjectSet::size() {
+    return container.size();
+}
+
+bool ObjectSet::_anyAncestorIsInSet(Object *object) {
+    Object* o = object;
+    while (o != nullptr) {
+        if (contains(o)) {
+            return true;
+        }
+        o = o->getParent();
+    }
+
+    return false;
+}
+
+void ObjectSet::_removeDescendantsFromSet(Object *object) {
+    for (auto& child: object->getChildren()) {
+        if (contains(&child)) {
+            _remove(&child);
+            // there is certainly no children of this child in the set
+            continue;
+        }
+
+        _removeDescendantsFromSet(&child);
+    }
+}
+
+void ObjectSet::_remove(Object *object) {
+    releaseConnections[object].disconnect();
+    releaseConnections.erase(object);
+    container.get<hashed>().erase(object);
+}
+
+void ObjectSet::_add(Object *object) {
+    releaseConnections[object] = object->connectRelease(sigc::mem_fun(*this, &ObjectSet::remove));
+    container.push_back(object);
+}
+
+Object *ObjectSet::_getMutualAncestor(Object *object) {
+    Object *o = object;
+
+    bool flag = true;
+    while (o->getParent() != nullptr) {
+        for (auto &child: o->getParent()->getChildren()) {
+            if(&child != o && !contains(&child)) {
+                flag = false;
+                break;
+            }
+        }
+        if (!flag) {
+            break;
+        }
+        o = o->getParent();
+    }
+    return o;
+}
+
+void ObjectSet::_removeAncestorsFromSet(Object *object) {
+    Object* o = object;
+    while (o->getParent() != nullptr) {
+        for (auto &child: o->getParent()->getChildren()) {
+            if (&child != o) {
+                _add(&child);
+            }
+        }
+        if (contains(o->getParent())) {
+            _remove(o->getParent());
+            break;
+        }
+        o = o->getParent();
+    }
+}
+
+ObjectSet::~ObjectSet() {
+    clear();
+}
diff --git a/src/object-set.h b/src/object-set.h
new file mode 100644
index 000000000..a3962356b
--- /dev/null
+++ b/src/object-set.h
@@ -0,0 +1,58 @@
+/*
+ * Multiindex container for selection
+ *
+ * Authors:
+ *   Adrian Boguszewski
+ *
+ * Copyright (C) 2016 Adrian Boguszewski
+ *
+ * Released under GNU GPL, read the file 'COPYING' for more information
+ */
+
+#ifndef INKSCAPE_PROTOTYPE_OBJECTSET_H
+#define INKSCAPE_PROTOTYPE_OBJECTSET_H
+
+#include "object.h"
+#include <string>
+#include <unordered_map>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/identity.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <sigc++/connection.h>
+
+struct hashed{};
+
+typedef boost::multi_index_container<
+        Object*,
+        boost::multi_index::indexed_by<
+                boost::multi_index::sequenced<>,
+                boost::multi_index::hashed_unique<
+                        boost::multi_index::tag<hashed>,
+                        boost::multi_index::identity<Object*>>
+        >> multi_index_container;
+
+class ObjectSet {
+public:
+    ObjectSet() {};
+    ~ObjectSet();
+    bool add(Object* object);
+    bool remove(Object* object);
+    bool contains(Object* object);
+    void clear();
+    int size();
+
+private:
+    void _add(Object* object);
+    void _remove(Object* object);
+    bool _anyAncestorIsInSet(Object *object);
+    void _removeDescendantsFromSet(Object *object);
+    void _removeAncestorsFromSet(Object *object);
+    Object *_getMutualAncestor(Object *object);
+
+    multi_index_container container;
+    std::unordered_map<Object*, sigc::connection> releaseConnections;
+};
+
+
+#endif //INKSCAPE_PROTOTYPE_OBJECTSET_H
diff --git a/src/object.cpp b/src/object.cpp
new file mode 100644
index 000000000..c05d50b3a
--- /dev/null
+++ b/src/object.cpp
@@ -0,0 +1,50 @@
+/*
+ * Temporary file
+ *
+ * Authors:
+ *   Adrian Boguszewski
+ *
+ * Copyright (C) 2016 Adrian Boguszewski
+ *
+ * Released under GNU GPL, read the file 'COPYING' for more information
+ */
+
+#include "object.h"
+
+Object::Object(std::string name) : name(name), parent(NULL) { }
+
+Object::~Object() {
+    // only for this prototype
+    // call destructor on every child
+    children.clear_and_dispose(delete_disposer());
+    release_signal.emit(this);
+}
+
+const std::string& Object::getName() const {
+    return name;
+}
+
+Object *Object::getParent()  {
+    return parent;
+}
+
+bool Object::isDescendantOf(Object *o) {
+    Object* p = parent;
+    while(p != NULL) {
+        if (p == o) {
+            return true;
+        }
+        p = p->parent;
+    }
+    return false;
+}
+
+void Object::addChild(Object* o) {
+    o->parent = this;
+    children.push_back(*o);
+}
+
+sigc::connection Object::connectRelease(sigc::slot<bool, Object*> slot) {
+    return release_signal.connect(slot);
+}
+
diff --git a/src/object.h b/src/object.h
new file mode 100644
index 000000000..a5ad5692e
--- /dev/null
+++ b/src/object.h
@@ -0,0 +1,76 @@
+/*
+ * Temporary file
+ *
+ * Authors:
+ *   Adrian Boguszewski
+ *
+ * Copyright (C) 2016 Adrian Boguszewski
+ *
+ * Released under GNU GPL, read the file 'COPYING' for more information
+ */
+
+#ifndef INKSCAPE_PROTOTYPE_OBJECT_H
+#define INKSCAPE_PROTOTYPE_OBJECT_H
+
+#include <string>
+#include <sigc++/signal.h>
+#include <sigc++/connection.h>
+#include <boost/intrusive/list.hpp>
+
+// this causes some warning, but it's only for this prototype
+class Object;
+struct delete_disposer
+{
+    void operator()(Object *delete_this) {
+        delete delete_this;
+    }
+};
+
+class Object {
+private:
+    std::string name;
+    Object* parent;
+
+    typedef boost::intrusive::list_member_hook<
+            boost::intrusive::link_mode<
+                    boost::intrusive::auto_unlink
+            >> list_hook;
+    list_hook child_hook;
+
+    typedef boost::intrusive::list<
+            Object,
+            boost::intrusive::constant_time_size<false>,
+            boost::intrusive::member_hook<
+                    Object,
+                    list_hook,
+                    &Object::child_hook
+            >> list;
+    list children;
+
+    sigc::signal<bool, Object*> release_signal;
+
+public:
+    Object(std::string name);
+    virtual ~Object();
+
+    list &getChildren() {
+        return children;
+    }
+
+    const std::string &getName() const;
+    Object * getParent() ;
+
+    sigc::connection connectRelease(sigc::slot<bool, Object*> slot);
+    void addChild(Object* o);
+    bool isDescendantOf(Object* o);
+
+    bool operator==(Object o) {
+        return name == o.name;
+    }
+
+    bool operator!=(Object o) {
+        return name != o.name;
+    }
+};
+
+#endif //INKSCAPE_PROTOTYPE_OBJECT_H
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
index 8da39d627..26d3572e0 100644
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -14,7 +14,6 @@ set_source_files_properties(
 		${CMAKE_BINARY_DIR}/src/inkscape-version.cpp
 		PROPERTIES GENERATED TRUE)
 
-# include_directories(${CMAKE_CURRENT_BINARY_DIR}/__/src)
 include_directories(${CMAKE_BINARY_DIR}/src)
 
 add_executable(unittest
@@ -23,10 +22,10 @@ add_executable(unittest
 	src/attributes-test.cpp
 	src/color-profile-test.cpp
 	src/dir-util-test.cpp
+		src/object-test.cpp
+	src/object-set-test.cpp
 )
 
-target_link_libraries(unittest inkscape_base)
-
 add_dependencies(unittest inkscape_version)
 
 set (_optional_unittest_libs )
@@ -37,9 +36,7 @@ endif()
 
 target_link_libraries(unittest
 	gmock_main
-
-	# order from automake
-	#sp_LIB
+	inkscape_base
 
 	#inkscape_LIB
 	#sp_LIB # annoying, we need both!
@@ -63,5 +60,3 @@ target_link_libraries(unittest
 add_test(BaseTest ${EXECUTABLE_OUTPUT_PATH}/unittest)
 
 add_dependencies(check unittest)
-
-#
diff --git a/test/src/object-set-test.cpp b/test/src/object-set-test.cpp
new file mode 100644
index 000000000..20d0c9474
--- /dev/null
+++ b/test/src/object-set-test.cpp
@@ -0,0 +1,173 @@
+#include <gtest/gtest.h>
+#include "object-set.h"
+
+class ObjectSetTest: public testing::Test {
+public:
+    ObjectSetTest() {
+        A = new Object("A");
+        B = new Object("B");
+        C = new Object("C");
+        D = new Object("D");
+        E = new Object("E");
+        F = new Object("F");
+        G = new Object("G");
+        H = new Object("H");
+        X = new Object("X");
+    }
+    ~ObjectSetTest() {
+        delete X;
+        delete H;
+        delete G;
+        delete F;
+        delete E;
+        delete D;
+        delete C;
+        delete B;
+        delete A;
+    }
+    Object* A;
+    Object* B;
+    Object* C;
+    Object* D;
+    Object* E;
+    Object* F;
+    Object* G;
+    Object* H;
+    Object* X;
+    ObjectSet set;
+    ObjectSet set2;
+};
+
+TEST_F(ObjectSetTest, Basics) {
+    EXPECT_EQ(0, set.size());
+    set.add(A);
+    EXPECT_EQ(1, set.size());
+    EXPECT_TRUE(set.contains(A));
+    set.add(B);
+    set.add(C);
+    EXPECT_EQ(3, set.size());
+    EXPECT_TRUE(set.contains(B));
+    EXPECT_TRUE(set.contains(C));
+    EXPECT_FALSE(set.contains(D));
+    EXPECT_FALSE(set.contains(X));
+    set.remove(A);
+    EXPECT_EQ(2, set.size());
+    EXPECT_FALSE(set.contains(A));
+    set.clear();
+    EXPECT_EQ(0, set.size());
+}
+
+TEST_F(ObjectSetTest, Autoremoving) {
+    Object* Q = new Object("Q");
+    set.add(Q);
+    EXPECT_TRUE(set.contains(Q));
+    EXPECT_EQ(1, set.size());
+    delete Q;
+    EXPECT_EQ(0, set.size());
+}
+
+TEST_F(ObjectSetTest, BasicDescendants) {
+    A->addChild(B);
+    B->addChild(C);
+    A->addChild(D);
+    bool resultB = set.add(B);
+    bool resultB2 = set.add(B);
+    EXPECT_TRUE(resultB);
+    EXPECT_FALSE(resultB2);
+    EXPECT_TRUE(set.contains(B));
+    bool resultC = set.add(C);
+    EXPECT_FALSE(resultC);
+    EXPECT_FALSE(set.contains(C));
+    EXPECT_EQ(1, set.size());
+    bool resultA = set.add(A);
+    EXPECT_TRUE(resultA);
+    EXPECT_EQ(1, set.size());
+    EXPECT_TRUE(set.contains(A));
+    EXPECT_FALSE(set.contains(B));
+}
+
+TEST_F(ObjectSetTest, AdvancedDescendants) {
+    A->addChild(B);
+    A->addChild(C);
+    A->addChild(X);
+    B->addChild(D);
+    B->addChild(E);
+    C->addChild(F);
+    C->addChild(G);
+    C->addChild(H);
+    set.add(A);
+    bool resultF = set.remove(F);
+    EXPECT_TRUE(resultF);
+    EXPECT_EQ(4, set.size());
+    EXPECT_FALSE(set.contains(F));
+    EXPECT_TRUE(set.contains(B));
+    EXPECT_TRUE(set.contains(G));
+    EXPECT_TRUE(set.contains(H));
+    EXPECT_TRUE(set.contains(X));
+    bool resultF2 = set.add(F);
+    EXPECT_TRUE(resultF2);
+    EXPECT_EQ(1, set.size());
+    EXPECT_TRUE(set.contains(A));
+}
+
+TEST_F(ObjectSetTest, Removing) {
+    A->addChild(B);
+    A->addChild(C);
+    A->addChild(X);
+    B->addChild(D);
+    B->addChild(E);
+    C->addChild(F);
+    C->addChild(G);
+    C->addChild(H);
+    bool removeH = set.remove(H);
+    EXPECT_FALSE(removeH);
+    set.add(A);
+    bool removeX = set.remove(X);
+    EXPECT_TRUE(removeX);
+    EXPECT_EQ(2, set.size());
+    EXPECT_TRUE(set.contains(B));
+    EXPECT_TRUE(set.contains(C));
+    EXPECT_FALSE(set.contains(X));
+    EXPECT_FALSE(set.contains(A));
+    bool removeX2 = set.remove(X);
+    EXPECT_FALSE(removeX2);
+    EXPECT_EQ(2, set.size());
+    bool removeA = set.remove(A);
+    EXPECT_FALSE(removeA);
+    EXPECT_EQ(2, set.size());
+    bool removeC = set.remove(C);
+    EXPECT_TRUE(removeC);
+    EXPECT_EQ(1, set.size());
+    EXPECT_TRUE(set.contains(B));
+    EXPECT_FALSE(set.contains(C));
+}
+
+TEST_F(ObjectSetTest, TwoSets) {
+    Object* Q = new Object("Q");
+    A->addChild(B);
+    A->addChild(Q);
+    set.add(A);
+    set2.add(A);
+    EXPECT_EQ(1, set.size());
+    EXPECT_EQ(1, set2.size());
+    set.remove(B);
+    EXPECT_EQ(1, set.size());
+    EXPECT_TRUE(set.contains(Q));
+    EXPECT_EQ(1, set2.size());
+    EXPECT_TRUE(set2.contains(A));
+    delete Q;
+    EXPECT_EQ(0, set.size());
+    EXPECT_EQ(1, set2.size());
+    EXPECT_TRUE(set2.contains(A));
+}
+
+TEST_F(ObjectSetTest, SetRemoving) {
+    ObjectSet *objectSet = new ObjectSet();
+    A->addChild(B);
+    objectSet->add(A);
+    objectSet->add(C);
+    EXPECT_EQ(2, objectSet->size());
+    delete objectSet;
+    EXPECT_EQ("A", A->getName());
+    EXPECT_EQ("C", C->getName());
+}
diff --git a/test/src/object-test.cpp b/test/src/object-test.cpp
new file mode 100644
index 000000000..83e90b2ec
--- /dev/null
+++ b/test/src/object-test.cpp
@@ -0,0 +1,56 @@
+#include "gtest/gtest.h"
+#include "object.h"
+
+class ObjectTest: public testing::Test {
+public:
+    ObjectTest() {
+        object = new Object("parent");
+        childOfChild = new Object("childOfChild");
+        child = new Object("child");
+        child2 = new Object("child2");
+        object2 = new Object("object2");
+        child3 = new Object("child3");
+    }
+    ~ObjectTest() {
+        delete child3;
+        delete child2;
+        delete childOfChild;
+        delete child;
+        delete object2;
+        delete object;
+    }
+    Object* object;
+    Object* object2;
+    Object* child;
+    Object* childOfChild;
+    Object* child2;
+    Object* child3;
+};
+
+TEST_F(ObjectTest, AddChild) {
+    EXPECT_EQ(0, object->getChildren().size());
+    object->addChild(child);
+    EXPECT_EQ(1, object->getChildren().size());
+    EXPECT_EQ(child, &(object->getChildren().front()));
+    EXPECT_EQ(object, child->getParent());
+}
+
+TEST_F(ObjectTest, IsDescendantOf) {
+    object->addChild(child);
+    child->addChild(childOfChild);
+    object->addChild(child2);
+    object2->addChild(child3);
+    EXPECT_TRUE(child->isDescendantOf(object));
+    EXPECT_TRUE(childOfChild->isDescendantOf(child));
+    EXPECT_TRUE(childOfChild->isDescendantOf(object));
+    EXPECT_TRUE(child2->isDescendantOf(object));
+    EXPECT_TRUE(child3->isDescendantOf(object2));
+    EXPECT_FALSE(child->isDescendantOf(child2));
+    EXPECT_FALSE(child2->isDescendantOf(child));
+    EXPECT_FALSE(object->isDescendantOf(childOfChild));
+    EXPECT_FALSE(object->isDescendantOf(child));
+    EXPECT_FALSE(object->isDescendantOf(object2));
+    EXPECT_FALSE(object2->isDescendantOf(object));
+    EXPECT_FALSE(child2->isDescendantOf(child3));
+    EXPECT_FALSE(child3->isDescendantOf(child2));
+}