Mercurial > code
changeset 251:0b7566e27eaa
TreeNode:
* use std::unique_ptr as children to avoid useless copy/move constructor calls
of the element type.
* add over 1000 lines of unit test.
* TreeNode is now considered ready to use.
| author | David Demelier <markand@malikania.fr> |
|---|---|
| date | Thu, 02 Oct 2014 11:17:08 +0200 |
| parents | b686a09fb9c6 |
| children | 19bfc11f77c2 |
| files | C++/Tests/TreeNode/CMakeLists.txt C++/Tests/TreeNode/main.cpp C++/TreeNode.h CMakeLists.txt |
| diffstat | 4 files changed, 1350 insertions(+), 198 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/C++/Tests/TreeNode/CMakeLists.txt Thu Oct 02 11:17:08 2014 +0200 @@ -0,0 +1,25 @@ +# +# CMakeLists.txt -- tests for TreeNode +# +# Copyright (c) 2013, 2014 David Demelier <markand@malikania.fr> +# +# Permission to use, copy, modify, and/or distribute this software for any +# purpose with or without fee is hereby granted, provided that the above +# copyright notice and this permission notice appear in all copies. +# +# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES +# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR +# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN +# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF +# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. +# + +set( + SOURCES + ${code_SOURCE_DIR}/C++/TreeNode.h + main.cpp +) + +define_test(treenode "${SOURCES}")
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/C++/Tests/TreeNode/main.cpp Thu Oct 02 11:17:08 2014 +0200 @@ -0,0 +1,1241 @@ +/* + * main.cpp -- main test file for TreeNode + * + * Copyright (c) 2013, 2014 David Demelier <markand@malikania.fr> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <string> + +#include <gtest/gtest.h> + +#include <TreeNode.h> + +class Object final : public TreeNode<Object> { +private: + std::string m_name; + +public: + Object(std::string name) + : TreeNode() + { + m_name = std::move(name); + } + + const std::string &name() const + { + return m_name; + } +}; + +/* + * Random trees are created and then we test each node with the following preferred order: + * + * ASSERT_(TRUE|FALSE) isRoot() + * ASSERT_(TRUE|FALSE) isLeaf() + * ASSERT_EQ countChildren() + * ASSERT_EQ() name() + * ASSERT_TRUE & addresses + */ + +/* -------------------------------------------------------- + * Basic construction and insertion + * -------------------------------------------------------- */ + +/* + * @root + */ +TEST(Basic, construct) +{ + Object object("root"); + + ASSERT_TRUE(object.isRoot()); + ASSERT_TRUE(object.isLeaf()); + ASSERT_EQ(0, object.countChildren()); + ASSERT_EQ("root", object.name()); +} + +/* + * @root -> append move -> @root + * | + * @a + */ +TEST(Insertion, simpleAppendMove) +{ + Object object("root"); + Object a("a"); + + object.append(std::move(a)); + + // test root + ASSERT_TRUE(object.isRoot()); + ASSERT_FALSE(object.isLeaf()); + ASSERT_EQ(1, object.countChildren()); + ASSERT_EQ("root", object.name()); + + // test moved a + ASSERT_FALSE(object[0].isRoot()); + ASSERT_TRUE(object[0].isLeaf()); + ASSERT_EQ("a", object[0].name()); + ASSERT_TRUE(&object == &object[0].parent()); + + // test original a + ASSERT_TRUE(a.isRoot()); + ASSERT_TRUE(a.isLeaf()); + ASSERT_EQ(0, a.countChildren()); +} + +/* + * @root -> append copy -> @root + * | + * @a + */ +TEST(Insertion, simpleAppendCopy) +{ + Object object("root"); + Object copy("b"); + + object.append(copy); + + // test root + ASSERT_TRUE(object.isRoot()); + ASSERT_FALSE(object.isLeaf()); + ASSERT_EQ(1, object.countChildren()); + ASSERT_EQ("root", object.name()); + + // test copied b + ASSERT_FALSE(object[0].isRoot()); + ASSERT_TRUE(object[0].isLeaf()); + ASSERT_EQ("b", object[0].name()); + ASSERT_TRUE(&object == &object[0].parent()); + + // test original b + ASSERT_TRUE(copy.isRoot()); + ASSERT_TRUE(copy.isLeaf()); + ASSERT_EQ(0, copy.countChildren()); + ASSERT_EQ("b", copy.name()); +} + +/* + * @root -> append move -> @root + * / \ + * 1@ @2 + */ +TEST(Insertion, doubleAppendMove) +{ + Object object("root"); + Object o1("1"); + Object o2("2"); + + object.append(std::move(o1)); + object.append(std::move(o2)); + + // test root + ASSERT_TRUE(object.isRoot()); + ASSERT_FALSE(object.isLeaf()); + ASSERT_EQ(2, object.countChildren()); + ASSERT_EQ("root", object.name()); + + // test moved 1 + ASSERT_FALSE(object[0].isRoot()); + ASSERT_TRUE(object[0].isLeaf()); + ASSERT_EQ(0, object[0].countChildren()); + ASSERT_EQ("1", object[0].name()); + ASSERT_TRUE(&object == &object[0].parent()); + + // test moved 2 + ASSERT_FALSE(object[1].isRoot()); + ASSERT_TRUE(object[1].isLeaf()); + ASSERT_EQ("2", object[1].name()); + ASSERT_EQ(0, object[1].countChildren()); + ASSERT_TRUE(&object == &object[1].parent()); + + // test original 1 + ASSERT_TRUE(o1.isRoot()); + ASSERT_TRUE(o1.isLeaf()); + ASSERT_EQ(0, o1.countChildren()); + + // test original 2 + ASSERT_TRUE(o2.isRoot()); + ASSERT_TRUE(o2.isLeaf()); + ASSERT_EQ(0, o2.countChildren()); +} + +/* + * @root -> append copy -> @root + * / \ + * 1@ @2 + */ +TEST(Insertion, doubleAppendCopy) +{ + Object object("root"); + Object o1("1"); + Object o2("2"); + + object.append(o1); + object.append(o2); + + // test root + ASSERT_TRUE(object.isRoot()); + ASSERT_FALSE(object.isLeaf()); + ASSERT_EQ(2, object.countChildren()); + ASSERT_EQ("root", object.name()); + + // test copied 1 + ASSERT_FALSE(object[0].isRoot()); + ASSERT_TRUE(object[0].isLeaf()); + ASSERT_EQ(0, object[0].countChildren()); + ASSERT_EQ("1", object[0].name()); + ASSERT_TRUE(&object == &object[0].parent()); + + // test copied 2 + ASSERT_FALSE(object[1].isRoot()); + ASSERT_TRUE(object[1].isLeaf()); + ASSERT_EQ(0, object[1].countChildren()); + ASSERT_EQ("2", object[1].name()); + ASSERT_TRUE(&object == &object[1].parent()); + + // test original 1 + ASSERT_TRUE(o1.isRoot()); + ASSERT_TRUE(o1.isLeaf()); + ASSERT_EQ(0, o1.countChildren()); + ASSERT_EQ("1", o1.name()); + + // test original 2 + ASSERT_TRUE(o2.isRoot()); + ASSERT_TRUE(o2.isLeaf()); + ASSERT_EQ(0, o2.countChildren()); + ASSERT_EQ("2", o2.name()); +} + +/* + * @root -> push move -> @root + * | + * @a + */ +TEST(Insertion, simplePushMove) +{ + Object object("root"); + Object a("a"); + + object.push(std::move(a)); + + // test root + ASSERT_TRUE(object.isRoot()); + ASSERT_FALSE(object.isLeaf()); + ASSERT_EQ(1, object.countChildren()); + ASSERT_EQ("a", object[0].name()); + + // test moved a + ASSERT_FALSE(object[0].isRoot()); + ASSERT_TRUE(object[0].isLeaf()); + ASSERT_EQ(0, object[0].countChildren()); + ASSERT_EQ("a", object[0].name()); + ASSERT_TRUE(&object == &object[0].parent()); + + // test original a + ASSERT_TRUE(a.isRoot()); + ASSERT_TRUE(a.isLeaf()); + ASSERT_EQ(0, a.countChildren()); +} + +/* + * @root -> push copy -> @root + * | + * @a + */ +TEST(Insertion, simplePushCopy) +{ + Object object("root"); + Object copy("a"); + + object.push(copy); + + // test root + ASSERT_TRUE(object.isRoot()); + ASSERT_FALSE(object.isLeaf()); + ASSERT_EQ(1, object.countChildren()); + ASSERT_EQ("a", object[0].name()); + + // test copied a + ASSERT_FALSE(object[0].isRoot()); + ASSERT_TRUE(object[0].isLeaf()); + ASSERT_EQ(0, object[0].countChildren()); + ASSERT_EQ("a", object[0].name()); + ASSERT_TRUE(&object == &object[0].parent()); + + // test original b + ASSERT_TRUE(copy.isRoot()); + ASSERT_TRUE(copy.isLeaf()); + ASSERT_EQ(0, copy.countChildren()); + ASSERT_EQ("a", copy.name()); +} + +/* + * @root -> push move -> @root + * / \ + * 2@ @1 + */ +TEST(Insertion, doublePushMove) +{ + Object object("root"); + Object o1("1"); + Object o2("2"); + + object.push(std::move(o1)); + object.push(std::move(o2)); + + // test root + ASSERT_TRUE(object.isRoot()); + ASSERT_FALSE(object.isLeaf()); + ASSERT_EQ(2, object.countChildren()); + ASSERT_EQ("root", object.name()); + + // test moved 2 + ASSERT_FALSE(object[0].isRoot()); + ASSERT_TRUE(object[0].isLeaf()); + ASSERT_EQ(0, object[0].countChildren()); + ASSERT_EQ("2", object[0].name()); + ASSERT_TRUE(&object == &object[0].parent()); + + // test moved 1 + ASSERT_FALSE(object[1].isRoot()); + ASSERT_TRUE(object[1].isLeaf()); + ASSERT_EQ("1", object[1].name()); + ASSERT_EQ(0, object[1].countChildren()); + ASSERT_TRUE(&object == &object[1].parent()); + + // test original 1 + ASSERT_TRUE(o1.isRoot()); + ASSERT_TRUE(o1.isLeaf()); + ASSERT_EQ(0, o1.countChildren()); + + // test original 2 + ASSERT_TRUE(o2.isRoot()); + ASSERT_TRUE(o2.isLeaf()); + ASSERT_EQ(0, o2.countChildren()); +} + +/* + * @root -> push copy -> @root + * / \ + * 2@ @1 + */ +TEST(Insertion, doublePushCopy) +{ + Object object("root"); + Object o1("1"); + Object o2("2"); + + object.push(o1); + object.push(o2); + + // test root + ASSERT_TRUE(object.isRoot()); + ASSERT_FALSE(object.isLeaf()); + ASSERT_EQ(2, object.countChildren()); + ASSERT_EQ("root", object.name()); + + // test copied 2 + ASSERT_FALSE(object[0].isRoot()); + ASSERT_TRUE(object[0].isLeaf()); + ASSERT_EQ(0, object[0].countChildren()); + ASSERT_EQ("2", object[0].name()); + ASSERT_TRUE(&object == &object[0].parent()); + + // test copied 1 + ASSERT_FALSE(object[1].isRoot()); + ASSERT_TRUE(object[1].isLeaf()); + ASSERT_EQ(0, object[1].countChildren()); + ASSERT_EQ("1", object[1].name()); + ASSERT_TRUE(&object == &object[1].parent()); + + // test original 1 + ASSERT_TRUE(o1.isRoot()); + ASSERT_TRUE(o1.isLeaf()); + ASSERT_EQ(0, o1.countChildren()); + ASSERT_EQ("1", o1.name()); + + // test original 2 + ASSERT_TRUE(o2.isRoot()); + ASSERT_TRUE(o2.isLeaf()); + ASSERT_EQ(0, o2.countChildren()); + ASSERT_EQ("2", o2.name()); +} + +/* -------------------------------------------------------- + * Sub insertion + * -------------------------------------------------------- */ + +/* + * @root + * / \ + * / \ + * a@ @b + * / \ / \ + * c@ d@ @e @f + */ +TEST(SubInsert, append) +{ + Object object("root"); + + object.append(Object("a")); + object.append(Object("b")); + + object[0].append(Object("c")); + object[0].append(Object("d")); + object[1].append(Object("e")); + object[1].append(Object("f")); + + // test root + ASSERT_TRUE(object.isRoot()); + ASSERT_FALSE(object.isLeaf()); + ASSERT_EQ(2, object.countChildren()); + ASSERT_EQ("root", object.name()); + + // test a + ASSERT_FALSE(object[0].isRoot()); + ASSERT_FALSE(object[0].isLeaf()); + ASSERT_EQ(2, object[0].countChildren()); + ASSERT_EQ("a", object[0].name()); + ASSERT_TRUE(&object == &object[0].parent()); + + // test b + ASSERT_FALSE(object[1].isRoot()); + ASSERT_FALSE(object[1].isLeaf()); + ASSERT_EQ(2, object[1].countChildren()); + ASSERT_EQ("b", object[1].name()); + ASSERT_TRUE(&object == &object[1].parent()); + + // test c + ASSERT_FALSE(object[0][0].isRoot()); + ASSERT_TRUE(object[0][0].isLeaf()); + ASSERT_EQ(0, object[0][0].countChildren()); + ASSERT_EQ("c", object[0][0].name()); + ASSERT_TRUE(&object[0] == &object[0][0].parent()); + + // test d + ASSERT_FALSE(object[0][1].isRoot()); + ASSERT_TRUE(object[0][1].isLeaf()); + ASSERT_EQ(0, object[0][1].countChildren()); + ASSERT_EQ("d", object[0][1].name()); + ASSERT_TRUE(&object[0] == &object[0][1].parent()); + + // test e + ASSERT_FALSE(object[1][0].isRoot()); + ASSERT_TRUE(object[1][0].isLeaf()); + ASSERT_EQ(0, object[1][0].countChildren()); + ASSERT_EQ("e", object[1][0].name()); + ASSERT_TRUE(&object[1] == &object[1][0].parent()); + + // test f + ASSERT_FALSE(object[1][1].isRoot()); + ASSERT_TRUE(object[1][1].isLeaf()); + ASSERT_EQ(0, object[1][1].countChildren()); + ASSERT_EQ("f", object[1][1].name()); + ASSERT_TRUE(&object[1] == &object[1][1].parent()); +} + +/* + * @root + * / \ + * / \ + * b@ @a + * / \ / \ + * d@ c@ @f @e + */ +TEST(SubInsert, push) +{ + Object object("root"); + + object.push(Object("a")); + object.push(Object("b")); + + object[0].push(Object("c")); + object[0].push(Object("d")); + object[1].push(Object("e")); + object[1].push(Object("f")); + + // test root + ASSERT_TRUE(object.isRoot()); + ASSERT_FALSE(object.isLeaf()); + ASSERT_EQ(2, object.countChildren()); + ASSERT_EQ("root", object.name()); + + // test b + ASSERT_FALSE(object[0].isRoot()); + ASSERT_FALSE(object[0].isLeaf()); + ASSERT_EQ(2, object[0].countChildren()); + ASSERT_EQ("b", object[0].name()); + ASSERT_TRUE(&object == &object[0].parent()); + + // test a + ASSERT_FALSE(object[1].isRoot()); + ASSERT_FALSE(object[1].isLeaf()); + ASSERT_EQ(2, object[1].countChildren()); + ASSERT_EQ("a", object[1].name()); + ASSERT_TRUE(&object == &object[1].parent()); + + // test d + ASSERT_FALSE(object[0][0].isRoot()); + ASSERT_TRUE(object[0][0].isLeaf()); + ASSERT_EQ(0, object[0][0].countChildren()); + ASSERT_EQ("d", object[0][0].name()); + ASSERT_TRUE(&object[0] == &object[0][0].parent()); + + // test c + ASSERT_FALSE(object[0][1].isRoot()); + ASSERT_TRUE(object[0][1].isLeaf()); + ASSERT_EQ(0, object[0][1].countChildren()); + ASSERT_EQ("c", object[0][1].name()); + ASSERT_TRUE(&object[0] == &object[0][1].parent()); + + // test f + ASSERT_FALSE(object[1][0].isRoot()); + ASSERT_TRUE(object[1][0].isLeaf()); + ASSERT_EQ(0, object[1][0].countChildren()); + ASSERT_EQ("f", object[1][0].name()); + ASSERT_TRUE(&object[1] == &object[1][0].parent()); + + // test e + ASSERT_FALSE(object[1][1].isRoot()); + ASSERT_TRUE(object[1][1].isLeaf()); + ASSERT_EQ(0, object[1][1].countChildren()); + ASSERT_EQ("e", object[1][1].name()); + ASSERT_TRUE(&object[1] == &object[1][1].parent()); +} + +/* -------------------------------------------------------- + * Move constructor + * -------------------------------------------------------- */ + +TEST(MoveConstructor, simple) +{ + Object root("root"); + Object moved(std::move(root)); + + // test root + ASSERT_TRUE(root.isRoot()); + ASSERT_TRUE(root.isLeaf()); + ASSERT_EQ(0, root.countChildren()); + + // test moved + ASSERT_TRUE(moved.isRoot()); + ASSERT_TRUE(moved.isLeaf()); + ASSERT_EQ(0, moved.countChildren()); + ASSERT_EQ("root", moved.name()); +} + +/* + * @root -> copy + * / \ + * / \ + * a@ @b + */ +TEST(MoveConstructor, oneLevel) +{ + Object root("root"); + + root.append(Object("a")); + root.append(Object("b")); + + Object moved(std::move(root)); + ASSERT_TRUE(moved.isRoot()); + ASSERT_EQ(2, moved.countChildren()); + ASSERT_EQ("a", moved[0].name()); + ASSERT_EQ("b", moved[1].name()); + ASSERT_EQ("root", moved[0].parent().name()); + ASSERT_EQ("root", moved[1].parent().name()); + ASSERT_TRUE(&moved == &moved[0].parent()); + ASSERT_TRUE(&moved == &moved[1].parent()); +} + +/* + * @root -> copy + * / \ + * / \ + * a@ @b + * / \ / \ + * c@ d@ @e @f + * + */ +TEST(MoveConstructor, twoLevels) +{ + Object root("root"); + + root.append(Object("a")); + root.append(Object("b")); + + root[0].append(Object("c")); + root[0].append(Object("d")); + root[1].append(Object("e")); + root[1].append(Object("f")); + + Object moved(std::move(root)); + + // test root + ASSERT_TRUE(moved.isRoot()); + ASSERT_EQ(2, moved.countChildren()); + + // test a, b + ASSERT_EQ("a", moved[0].name()); + ASSERT_EQ("b", moved[1].name()); + ASSERT_EQ(2, moved[0].countChildren()); + ASSERT_EQ(2, moved[1].countChildren()); + ASSERT_EQ("root", moved[0].parent().name()); + ASSERT_EQ("root", moved[1].parent().name()); + ASSERT_TRUE(&moved == &moved[0].parent()); + ASSERT_TRUE(&moved == &moved[1].parent()); + + // test c, d + ASSERT_EQ("c", moved[0][0].name()); + ASSERT_EQ("d", moved[0][1].name()); + ASSERT_EQ("a", moved[0][0].parent().name()); + ASSERT_EQ("a", moved[0][1].parent().name()); + ASSERT_TRUE(&moved[0] == &moved[0][0].parent()); + ASSERT_TRUE(&moved[0] == &moved[0][1].parent()); + ASSERT_TRUE(moved[0][0].isLeaf()); + ASSERT_TRUE(moved[0][1].isLeaf()); + ASSERT_FALSE(moved[0][0].isRoot()); + ASSERT_FALSE(moved[0][1].isRoot()); + + // test e, f + ASSERT_EQ("e", moved[1][0].name()); + ASSERT_EQ("f", moved[1][1].name()); + ASSERT_EQ("b", moved[1][0].parent().name()); + ASSERT_EQ("b", moved[1][1].parent().name()); + ASSERT_TRUE(&moved[1] == &moved[1][0].parent()); + ASSERT_TRUE(&moved[1] == &moved[1][1].parent()); + ASSERT_TRUE(moved[1][0].isLeaf()); + ASSERT_TRUE(moved[1][1].isLeaf()); + ASSERT_FALSE(moved[1][0].isRoot()); + ASSERT_FALSE(moved[1][1].isRoot()); +} + +/* -------------------------------------------------------- + * Copy constructor + * -------------------------------------------------------- */ + +TEST(CopyConstructor, simple) +{ + Object root("root"); + Object moved(root); + + // test root + ASSERT_TRUE(root.isRoot()); + ASSERT_TRUE(root.isLeaf()); + ASSERT_EQ(0, root.countChildren()); + ASSERT_EQ("root", root.name()); + + // test copy + ASSERT_TRUE(moved.isRoot()); + ASSERT_TRUE(moved.isLeaf()); + ASSERT_EQ(0, moved.countChildren()); + ASSERT_EQ("root", moved.name()); +} + +/* + * @root -> copy + * / \ + * / \ + * a@ @b + */ +TEST(CopyConstructor, oneLevel) +{ + Object root("root"); + + root.append(Object("a")); + root.append(Object("b")); + + Object copy(root); + + ASSERT_TRUE(root.isRoot()); + ASSERT_FALSE(root.isLeaf()); + ASSERT_TRUE(copy.isRoot()); + ASSERT_FALSE(copy.isLeaf()); + ASSERT_EQ("root", root.name()); + ASSERT_EQ("root", copy.name()); + ASSERT_EQ("a", root[0].name()); + ASSERT_EQ("b", root[1].name()); + ASSERT_EQ("a", copy[0].name()); + ASSERT_EQ("b", copy[1].name()); + ASSERT_TRUE(&root == &root[0].parent()); + ASSERT_TRUE(&root == &root[1].parent()); + ASSERT_TRUE(© == ©[0].parent()); + ASSERT_TRUE(© == ©[1].parent()); +} + +/* + * @root -> copy + * / \ + * / \ + * a@ @b + * / \ / \ + * c@ d@ @e @f + * + */ +TEST(CopyConstructor, twoLevels) +{ + Object root("root"); + + root.append(Object("a")); + root.append(Object("b")); + + root[0].append(Object("c")); + root[0].append(Object("d")); + root[1].append(Object("e")); + root[1].append(Object("f")); + + Object copy(root); + + ASSERT_FALSE(root.isLeaf()); + ASSERT_FALSE(copy.isLeaf()); + ASSERT_EQ("root", root.name()); + ASSERT_EQ("root", copy.name()); + ASSERT_EQ("a", root[0].name()); + ASSERT_EQ("a", copy[0].name()); + ASSERT_EQ("c", root[0][0].name()); + ASSERT_EQ("c", copy[0][0].name()); + ASSERT_EQ("d", root[0][1].name()); + ASSERT_EQ("d", copy[0][1].name()); + ASSERT_EQ("b", root[1].name()); + ASSERT_EQ("b", copy[1].name()); + ASSERT_EQ("e", root[1][0].name()); + ASSERT_EQ("e", copy[1][0].name()); + ASSERT_EQ("f", root[1][1].name()); + ASSERT_EQ("f", copy[1][1].name()); + ASSERT_TRUE(&root == &root[0].parent()); + ASSERT_TRUE(&root == &root[1].parent()); + ASSERT_TRUE(© == ©[0].parent()); + ASSERT_TRUE(© == ©[1].parent()); + ASSERT_TRUE(&root[0] == &root[0][0].parent()); + ASSERT_TRUE(&root[0] == &root[0][1].parent()); + ASSERT_TRUE(©[0] == ©[0][0].parent()); + ASSERT_TRUE(©[0] == ©[0][1].parent()); + ASSERT_TRUE(&root[1] == &root[1][0].parent()); + ASSERT_TRUE(&root[1] == &root[1][1].parent()); + ASSERT_TRUE(©[1] == ©[1][0].parent()); + ASSERT_TRUE(©[1] == ©[1][1].parent()); +} + +/* -------------------------------------------------------- + * Move extraction + * -------------------------------------------------------- */ + +/* + * @root + * / \ + * / \ + * a@ @b -> move -> @b + */ +TEST(MoveExtraction, simple) +{ + Object root("root"); + + root.append(Object("a")); + root.append(Object("b")); + + Object moved(std::move(root[1])); + + // test root + ASSERT_TRUE(root.isRoot()); + ASSERT_EQ(2, root.countChildren()); + ASSERT_EQ("root", root.name()); + + // test a + ASSERT_TRUE(root[0].isLeaf()); + ASSERT_FALSE(root[0].isRoot()); + ASSERT_EQ("a", root[0].name()); + ASSERT_EQ(0, root[0].countChildren()); + ASSERT_TRUE(&root == &root[0].parent()); + + // test b + ASSERT_TRUE(root[1].isLeaf()); + ASSERT_FALSE(root[1].isRoot()); + ASSERT_EQ(0, root[1].countChildren()); + ASSERT_TRUE(&root == &root[1].parent()); + + // test moved b + ASSERT_TRUE(moved.isRoot()); + ASSERT_TRUE(moved.isLeaf()); + ASSERT_EQ(0, moved.countChildren()); + ASSERT_EQ("b", moved.name()); +} + +/* + * @root + * / \ + * / \ + * a@ @b -> move + * / \ / \ + * c@ d@ @e @f + * \ + * @g + */ +TEST(MoveExtraction, bigger) +{ + Object root("root"); + + root.append(Object("a")); + root.append(Object("b")); + + root[0].append(Object("c")); + root[0].append(Object("d")); + root[1].append(Object("e")); + root[1].append(Object("f")); + root[1][1].append(Object("g")); + + Object moved(std::move(root[1])); + + // test root + ASSERT_TRUE(root.isRoot()); + ASSERT_FALSE(root.isLeaf()); + ASSERT_EQ(2, root.countChildren()); + ASSERT_EQ("root", root.name()); + + // test a + ASSERT_FALSE(root[0].isRoot()); + ASSERT_FALSE(root[0].isLeaf()); + ASSERT_EQ(2, root[0].countChildren()); + ASSERT_EQ("a", root[0].name()); + ASSERT_TRUE(&root == &root[0].parent()); + + // test c + ASSERT_FALSE(root[0][0].isRoot()); + ASSERT_TRUE(root[0][0].isLeaf()); + ASSERT_EQ(0, root[0][0].countChildren()); + ASSERT_EQ("c", root[0][0].name()); + ASSERT_TRUE(&root[0] == &root[0][0].parent()); + + // test d + ASSERT_FALSE(root[0][1].isRoot()); + ASSERT_TRUE(root[0][1].isLeaf()); + ASSERT_EQ(0, root[0][1].countChildren()); + ASSERT_EQ("d", root[0][1].name()); + ASSERT_TRUE(&root[0] == &root[0][1].parent()); + + // test b + ASSERT_FALSE(root[1].isRoot()); + ASSERT_TRUE(root[1].isLeaf()); + ASSERT_EQ(0, root[1].countChildren()); + ASSERT_TRUE(&root == &root[1].parent()); + + // test moved b + ASSERT_TRUE(moved.isRoot()); + ASSERT_FALSE(moved.isLeaf()); + ASSERT_EQ(2, moved.countChildren()); + ASSERT_EQ("b", moved.name()); + + // test moved b-e + ASSERT_FALSE(moved[0].isRoot()); + ASSERT_TRUE(moved[0].isLeaf()); + ASSERT_EQ(0, moved[0].countChildren()); + ASSERT_EQ("e", moved[0].name()); + ASSERT_TRUE(&moved == &moved[0].parent()); + + // test moved b-f + ASSERT_FALSE(moved[1].isRoot()); + ASSERT_FALSE(moved[1].isLeaf()); + ASSERT_EQ(1, moved[1].countChildren()); + ASSERT_EQ("f", moved[1].name()); + ASSERT_TRUE(&moved == &moved[1].parent()); + + // test moved b-g + ASSERT_FALSE(moved[1][0].isRoot()); + ASSERT_TRUE(moved[1][0].isLeaf()); + ASSERT_EQ(0, moved[1][0].countChildren()); + ASSERT_EQ("g", moved[1][0].name()); + ASSERT_TRUE(&moved[1] == &moved[1][0].parent()); +} + +/* -------------------------------------------------------- + * Copy extraction + * -------------------------------------------------------- */ + +/* + * @root + * / \ + * / \ + * a@ @b -> copy -> @b + */ +TEST(CopyExtraction, simple) +{ + Object root("root"); + + root.append(Object("a")); + root.append(Object("b")); + + Object copy(root[1]); + + // test root + ASSERT_TRUE(root.isRoot()); + ASSERT_EQ(2, root.countChildren()); + ASSERT_EQ("root", root.name()); + + // test a + ASSERT_TRUE(root[0].isLeaf()); + ASSERT_FALSE(root[0].isRoot()); + ASSERT_EQ(0, root[0].countChildren()); + ASSERT_EQ("a", root[0].name()); + ASSERT_TRUE(&root == &root[0].parent()); + + // test b + ASSERT_TRUE(root[1].isLeaf()); + ASSERT_FALSE(root[1].isRoot()); + ASSERT_EQ(0, root[1].countChildren()); + ASSERT_EQ("b", root[1].name()); + ASSERT_TRUE(&root == &root[1].parent()); + + // test copied b + ASSERT_TRUE(copy.isRoot()); + ASSERT_TRUE(copy.isLeaf()); + ASSERT_EQ(0, copy.countChildren()); + ASSERT_EQ("b", copy.name()); +} + +/* + * @root + * / \ + * / \ + * a@ @b -> copy + * / \ / \ + * c@ d@ @e @f + * \ + * @g + */ +TEST(CopyExtraction, bigger) +{ + Object root("root"); + + root.append(Object("a")); + root.append(Object("b")); + + root[0].append(Object("c")); + root[0].append(Object("d")); + root[1].append(Object("e")); + root[1].append(Object("f")); + root[1][1].append(Object("g")); + + Object copy(root[1]); + + // test root + ASSERT_TRUE(root.isRoot()); + ASSERT_FALSE(root.isLeaf()); + ASSERT_EQ(2, root.countChildren()); + ASSERT_EQ("root", root.name()); + + // test a + ASSERT_FALSE(root[0].isRoot()); + ASSERT_FALSE(root[0].isLeaf()); + ASSERT_EQ(2, root[0].countChildren()); + ASSERT_EQ("a", root[0].name()); + ASSERT_TRUE(&root == &root[0].parent()); + + // test c + ASSERT_FALSE(root[0][0].isRoot()); + ASSERT_TRUE(root[0][0].isLeaf()); + ASSERT_EQ(0, root[0][0].countChildren()); + ASSERT_EQ("c", root[0][0].name()); + ASSERT_TRUE(&root[0] == &root[0][0].parent()); + + // test d + ASSERT_FALSE(root[0][1].isRoot()); + ASSERT_TRUE(root[0][1].isLeaf()); + ASSERT_EQ(0, root[0][1].countChildren()); + ASSERT_EQ("d", root[0][1].name()); + ASSERT_TRUE(&root[0] == &root[0][1].parent()); + + // test b + ASSERT_FALSE(root[1].isRoot()); + ASSERT_FALSE(root[1].isLeaf()); + ASSERT_EQ(2, root[1].countChildren()); + ASSERT_TRUE(&root == &root[1].parent()); + + // test e + ASSERT_FALSE(root[1][0].isRoot()); + ASSERT_TRUE(root[1][0].isLeaf()); + ASSERT_EQ(0, root[1][0].countChildren()); + ASSERT_EQ("e", root[1][0].name()); + ASSERT_TRUE(&root[1] == &root[1][0].parent()); + + // test f + ASSERT_FALSE(root[1][1].isRoot()); + ASSERT_FALSE(root[1][1].isLeaf()); + ASSERT_EQ(1, root[1][1].countChildren()); + ASSERT_EQ("f", root[1][1].name()); + ASSERT_TRUE(&root[1] == &root[1][1].parent()); + + // test g + ASSERT_FALSE(root[1][1][0].isRoot()); + ASSERT_TRUE(root[1][1][0].isLeaf()); + ASSERT_EQ(0, root[1][1][0].countChildren()); + ASSERT_EQ("g", root[1][1][0].name()); + ASSERT_TRUE(&root[1][1] == &root[1][1][0].parent()); + + // test copied b + ASSERT_TRUE(copy.isRoot()); + ASSERT_FALSE(copy.isLeaf()); + ASSERT_EQ(2, copy.countChildren()); + ASSERT_EQ("b", copy.name()); + + // test copied b-e + ASSERT_FALSE(copy[0].isRoot()); + ASSERT_TRUE(copy[0].isLeaf()); + ASSERT_EQ(0, copy[0].countChildren()); + ASSERT_EQ("e", copy[0].name()); + ASSERT_TRUE(© == ©[0].parent()); + + // test copied b-f + ASSERT_FALSE(copy[1].isRoot()); + ASSERT_FALSE(copy[1].isLeaf()); + ASSERT_EQ(1, copy[1].countChildren()); + ASSERT_EQ("f", copy[1].name()); + ASSERT_TRUE(© == ©[1].parent()); + + // test copied b-g + ASSERT_FALSE(copy[1][0].isRoot()); + ASSERT_TRUE(copy[1][0].isLeaf()); + ASSERT_EQ(0, copy[1][0].countChildren()); + ASSERT_EQ("g", copy[1][0].name()); + ASSERT_TRUE(©[1] == ©[1][0].parent()); +} + +/* -------------------------------------------------------- + * Move assignment + * -------------------------------------------------------- */ + +/* + * @root -> @moved + */ +TEST(MoveAssignment, simple) +{ + Object root("root"); + Object moved("dummy"); + + moved = std::move(root); + + // test root + ASSERT_TRUE(root.isRoot()); + ASSERT_TRUE(root.isLeaf()); + ASSERT_EQ(0, root.countChildren()); + + // test moved + ASSERT_TRUE(moved.isRoot()); + ASSERT_TRUE(moved.isLeaf()); + ASSERT_EQ(0, moved.countChildren()); + ASSERT_EQ("root", moved.name()); +} + +/* + * @root + * / \ + * / \ + * a@ @b <- move <- @x + * / \ / \ / \ + * c@ d@ @e @f y@ @z + * \ + * @g + */ +TEST(MoveAssignment, bigger) +{ + Object root("root"); + + root.append(Object("a")); + root.append(Object("b")); + + root[0].append(Object("c")); + root[0].append(Object("d")); + root[1].append(Object("e")); + root[1].append(Object("f")); + root[1][1].append(Object("g")); + + Object moved("x"); + + moved.append(Object("y")); + moved.append(Object("z")); + + root[1] = std::move(moved); + + // test root + ASSERT_TRUE(root.isRoot()); + ASSERT_FALSE(root.isLeaf()); + ASSERT_EQ(2, root.countChildren()); + ASSERT_EQ("root", root.name()); + + // test a + ASSERT_FALSE(root[0].isRoot()); + ASSERT_FALSE(root[0].isLeaf()); + ASSERT_EQ(2, root[0].countChildren()); + ASSERT_EQ("a", root[0].name()); + ASSERT_TRUE(&root == &root[0].parent()); + + // test c + ASSERT_FALSE(root[0][0].isRoot()); + ASSERT_TRUE(root[0][0].isLeaf()); + ASSERT_EQ(0, root[0][0].countChildren()); + ASSERT_EQ("c", root[0][0].name()); + ASSERT_TRUE(&root[0] == &root[0][0].parent()); + + // test copied x to b + ASSERT_FALSE(root[1].isRoot()); + ASSERT_FALSE(root[1].isLeaf()); + ASSERT_EQ(2, root[1].countChildren()); + ASSERT_EQ("x", root[1].name()); + ASSERT_TRUE(&root == &root[1].parent()); + + // test y + ASSERT_FALSE(root[1][0].isRoot()); + ASSERT_TRUE(root[1][0].isLeaf()); + ASSERT_EQ(0, root[1][0].countChildren()); + ASSERT_EQ("y", root[1][0].name()); + ASSERT_TRUE(&root[1] == &root[1][0].parent()); + + // test z + ASSERT_FALSE(root[1][1].isRoot()); + ASSERT_TRUE(root[1][1].isLeaf()); + ASSERT_EQ(0, root[1][1].countChildren()); + ASSERT_EQ("z", root[1][1].name()); + ASSERT_TRUE(&root[1] == &root[1][1].parent()); + + // test moved + ASSERT_TRUE(moved.isRoot()); + ASSERT_TRUE(moved.isLeaf()); + ASSERT_EQ(0, moved.countChildren()); +} + +/* -------------------------------------------------------- + * Copy assignment + * -------------------------------------------------------- */ + +/* + * @root -> @copy + */ +TEST(CopyAssignment, simple) +{ + Object root("root"); + Object copy("copy"); + + copy = root; + + // test root + ASSERT_TRUE(root.isRoot()); + ASSERT_TRUE(root.isLeaf()); + ASSERT_EQ(0, root.countChildren()); + ASSERT_EQ("root", root.name()); + + // test copied + ASSERT_TRUE(copy.isRoot()); + ASSERT_TRUE(copy.isLeaf()); + ASSERT_EQ(0, copy.countChildren()); + ASSERT_EQ("root", copy.name()); +} + +/* + * @root + * / \ + * / \ + * a@ @b <- copy <- @x + * / \ / \ / \ + * c@ d@ @e @f y@ @z + * \ + * @g + */ +TEST(CopyAssignment, bigger) +{ + Object root("root"); + + root.append(Object("a")); + root.append(Object("b")); + + root[0].append(Object("c")); + root[0].append(Object("d")); + root[1].append(Object("e")); + root[1].append(Object("f")); + root[1][1].append(Object("g")); + + Object copy("x"); + + copy.append(Object("y")); + copy.append(Object("z")); + + root[1] = copy; + + // test root + ASSERT_TRUE(root.isRoot()); + ASSERT_FALSE(root.isLeaf()); + ASSERT_EQ(2, root.countChildren()); + ASSERT_EQ("root", root.name()); + + // test a + ASSERT_FALSE(root[0].isRoot()); + ASSERT_FALSE(root[0].isLeaf()); + ASSERT_EQ(2, root[0].countChildren()); + ASSERT_EQ("a", root[0].name()); + ASSERT_TRUE(&root == &root[0].parent()); + + // test c + ASSERT_FALSE(root[0][0].isRoot()); + ASSERT_TRUE(root[0][0].isLeaf()); + ASSERT_EQ(0, root[0][0].countChildren()); + ASSERT_EQ("c", root[0][0].name()); + ASSERT_TRUE(&root[0] == &root[0][0].parent()); + + // test copied x to b + ASSERT_FALSE(root[1].isRoot()); + ASSERT_FALSE(root[1].isLeaf()); + ASSERT_EQ(2, root[1].countChildren()); + ASSERT_EQ("x", root[1].name()); + ASSERT_TRUE(&root == &root[1].parent()); + + // test y + ASSERT_FALSE(root[1][0].isRoot()); + ASSERT_TRUE(root[1][0].isLeaf()); + ASSERT_EQ(0, root[1][0].countChildren()); + ASSERT_EQ("y", root[1][0].name()); + ASSERT_TRUE(&root[1] == &root[1][0].parent()); + + // test z + ASSERT_FALSE(root[1][1].isRoot()); + ASSERT_TRUE(root[1][1].isLeaf()); + ASSERT_EQ(0, root[1][1].countChildren()); + ASSERT_EQ("z", root[1][1].name()); + ASSERT_TRUE(&root[1] == &root[1][1].parent()); + + // test original x + ASSERT_TRUE(copy.isRoot()); + ASSERT_FALSE(copy.isLeaf()); + ASSERT_EQ(2, copy.countChildren()); + ASSERT_EQ("x", copy.name()); + + // test original y + ASSERT_FALSE(copy[0].isRoot()); + ASSERT_TRUE(copy[0].isLeaf()); + ASSERT_EQ(0, copy[0].countChildren()); + ASSERT_EQ("y", copy[0].name()); + ASSERT_TRUE(© == ©[0].parent()); + + // test original z + ASSERT_FALSE(copy[1].isRoot()); + ASSERT_TRUE(copy[1].isLeaf()); + ASSERT_EQ(0, copy[1].countChildren()); + ASSERT_EQ("z", copy[1].name()); + ASSERT_TRUE(© == ©[1].parent()); +} + +int main(int argc, char **argv) +{ + testing::InitGoogleTest(&argc, argv); + + return RUN_ALL_TESTS(); +} \ No newline at end of file
--- a/C++/TreeNode.h Wed Oct 01 14:39:24 2014 +0200 +++ b/C++/TreeNode.h Thu Oct 02 11:17:08 2014 +0200 @@ -24,112 +24,11 @@ * @brief N-ary tree without pointers */ -#include <algorithm> +#include <deque> +#include <memory> #include <stdexcept> -#include <type_traits> -#include <vector> - -namespace -{ - -/** - * @class ContainerTraits - * @brief Check capabilities - * - * This class checks for several functions in the container to disable or enable functions - * depending on the container. - * - * Provides the following static members: - * - * pushCopy - Set to true if we can push to the beginning by lvalue - * pushMove - Set to true if we can push to the beginning by rvalue - * appendCopy - Set to true if we can append to the end by lvalue - * appendMove - Set to true if we can append to the end by rvalue - * at - Set to true if container has at (also require typedef size_type) - * constAt - Set to true if container has const at (also require typedef size_type) - */ -template <typename Container, typename Type> -class ContainerTraits -{ -private: - typedef char Yes[2]; - typedef char No[1]; - - template <typename U, void (U::*)(const Type &)> - struct InsertCopy; - - template <typename U, void (U::*)(Type &&)> - struct InsertMove; - - template <typename U, const Type &(U::*)(typename U::size_type) const> - struct ConstAt; - - template <typename U, Type &(U::*)(typename U::size_type)> - struct At; - - /* - * Container::push_front(const T &) - */ - - template <typename U> - static Yes &testPushCopy(InsertCopy<U, &U::push_front> *); - template <typename U> - static No &testPushCopy(...); - /* - * Container::push_front(T &&) - */ - - template <typename U> - static Yes &testPushMove(InsertMove<U, &U::push_front> *); - template <typename U> - static No &testPushMove(...); - - /* - * Container::push_back(const T &) - */ - - template <typename U> - static Yes &testAppendCopy(InsertCopy<U, &U::push_back> *); - template <typename U> - static No &testAppendCopy(...); - - /* - * Container::push_back(T &&) - */ - - template <typename U> - static Yes &testAppendMove(InsertMove<U, &U::push_back> *); - template <typename U> - static No &testAppendMove(...); - - - /* - * Container::at(size_type) - */ - - template <typename U> - static Yes &testConstAt(ConstAt<U, &U::at> *); - template <typename U> - static No &testConstAt(...); - - /* - * Container::at(size_type) - */ - - template <typename U> - static Yes &testAt(At<U, &U::at> *); - template <typename U> - static No &testAt(...); - -public: - static const bool pushCopy = sizeof (testPushCopy<Container>(nullptr)) == sizeof (Yes); - static const bool pushMove = sizeof (testPushMove<Container>(nullptr)) == sizeof (Yes); - static const bool appendCopy = sizeof (testAppendCopy<Container>(nullptr)) == sizeof( Yes); - static const bool appendMove = sizeof (testAppendMove<Container>(nullptr)) == sizeof (Yes); - static const bool constAt = sizeof (testConstAt<Container>(nullptr)) == sizeof (Yes); - static const bool at = sizeof (testAt<Container>(nullptr)) == sizeof (Yes); -}; +namespace { /** * @class TypeTraits @@ -154,15 +53,15 @@ static_assert(sizeof (char) != sizeof (long), "buy a new compiler"); template <typename Value> - static auto check(Value *u) -> decltype(*u == *u, char(0)); + static constexpr auto check(Value *u) -> decltype(*u == *u, char(0)); - static long check(...); + static constexpr long check(...); - static const bool value = sizeof (check((U*)0)) == sizeof (char); + static constexpr const bool value = sizeof (check((U *)0)) == sizeof (char); }; public: - static const bool equalityComparable = HasEqualsTo<T>::value; + static constexpr const bool equalityComparable = HasEqualsTo<T>::value; }; } // !namespace @@ -171,79 +70,36 @@ * @class TreeNode * @brief Safe C++11 N-ary tree * - * This class template can be used to implement N-ary trees without any pointers. It uses - * move semantics and copy constructs to avoid usage of pointers. - * - * The container must have at least the following types: - * size_type - Typedef for indexation - * - * And the following functions: - * T &at(size_type) - Indexation at specified index - * const T &at(size_type) const - Indexation at specified index (const version) - * - * The typename T must be at least one of the following requirement: - * CopyConstructible - * MoveConstructible - * Comparable with operator== - + * This class use a std::deque as the container, it allocate object on the heap to avoid useless + * copy and move when adding new elements. */ -template <typename T, typename Container = std::vector<T>> -class TNewTreeNode -{ - static_assert(ContainerTraits<Container, T>::at, "container must have at(size_type)"); - static_assert(ContainerTraits<Container, T>::constAt, "container must have at(size_type) const"); - +template <typename T> +class TreeNode { private: - TNewTreeNode *m_parent; - Container m_children; + using Container = std::deque<std::unique_ptr<T>>; -public: - /* - * This is used by move constructors and assignment. It removes the - * reference to the object in the old tree. - */ - inline void updateOther(TNewTreeNode &&other) - { - if (other.m_parent) { - Container &children = other.m_parent->m_children; - - children.erase(std::find_if(children.begin(), children.end(), [&] (TNewTreeNode &i) { - return &other == &i; - })); - } - - other.m_parent = nullptr; - } - - /* - * When reallocation of m_children occurs, we need to update the relations. - */ - inline void refreshChildren() - { - for (T &child : m_children) - child.m_parent = this; - } + TreeNode *m_parent { nullptr }; + Container m_children; public: /** * Default constructor. */ - TNewTreeNode() - : m_parent(nullptr) - { - } + TreeNode() = default; /** * Copy constructor. * * @param other the other node */ - TNewTreeNode(const TNewTreeNode &other) + TreeNode(const TreeNode &other) { m_parent = nullptr; - m_children = other.m_children; - refreshChildren(); + for (const auto &c : other.m_children) { + m_children.push_back(std::make_unique<T>(*c)); + m_children.back()->m_parent = this; + } } /** @@ -251,13 +107,16 @@ * * @param other the other node */ - TNewTreeNode(TNewTreeNode &&other) + TreeNode(TreeNode &&other) { m_parent = nullptr; m_children = std::move(other.m_children); - updateOther(std::move(other)); - refreshChildren(); + // Update children to update to *this + for (auto &c : m_children) + c->m_parent = this; + + other.m_children.clear(); } /** @@ -265,13 +124,14 @@ * * @param other the other node */ - TNewTreeNode &operator=(const TNewTreeNode &other) + TreeNode &operator=(const TreeNode &other) { - m_children = other.m_children; + m_children.clear(); - refreshChildren(); - - return *this; + for (const auto &c : other.m_children) { + m_children.push_back(std::make_unique<T>(*c)); + m_children.back()->m_parent = this; + } } /** @@ -279,14 +139,15 @@ * * @param other the other node */ - TNewTreeNode &operator=(TNewTreeNode &&other) + TreeNode &operator=(TreeNode &&other) { m_children = std::move(other.m_children); - updateOther(std::move(other)); - refreshChildren(); + // Update children to update to *this + for (auto &c : m_children) + c->m_parent = this; - return *this; + other.m_children.clear(); } /** @@ -294,11 +155,10 @@ * * @param child the children */ - template <typename Value> - void push(const Value &child, typename std::enable_if<ContainerTraits<Container, Value>::pushCopy>::type * = 0) + void push(const T &child) { - m_children.push_front(child); - refreshChildren(); + m_children.push_front(std::make_unique<T>(child)); + m_children.front()->m_parent = this; } /** @@ -306,11 +166,22 @@ * * @param child the children */ - template <typename Value> - void push(Value &&child, typename std::enable_if<std::is_rvalue_reference<Value&&>::value && ContainerTraits<Container, Value>::pushMove>::type * = 0) + void push(T &&child) { - m_children.push_front(std::move(child)); - refreshChildren(); + m_children.push_front(std::make_unique<T>(std::move(child))); + m_children.front()->m_parent = this; + } + + /** + * Construct an element at the beginning in place. + * + * @param args the arguments + */ + template <typename... Args> + void pushNew(Args&&... args) + { + m_children.emplace_front(std::make_unique<T>(std::forward<Args>(args)...)); + m_children.front()->m_parent = this; } /** @@ -318,11 +189,10 @@ * * @param child the children */ - template <typename Value> - void append(const Value &child, typename std::enable_if<ContainerTraits<Container, Value>::appendCopy>::type * = 0) + void append(const T &child) { - m_children.push_back(child); - refreshChildren(); + m_children.push_back(std::make_unique<T>(child)); + m_children.back()->m_parent = this; } /** @@ -330,11 +200,22 @@ * * @param child the children */ - template <typename Value> - void append(Value &&child, typename std::enable_if<std::is_rvalue_reference<Value &&>::value && ContainerTraits<Container, Value>::appendMove>::type * = 0) + void append(T &&child) { - m_children.push_back(std::move(child)); - refreshChildren(); + m_children.push_back(std::make_unique<T>(std::move(child))); + m_children.back()->m_parent = this; + } + + /** + * Construct an element at the end in place. + * + * @param args the arguments + */ + template <typename... Args> + void appendNew(Args&&... args) + { + m_children.emplace_back(std::make_unique<T>(std::forward<Args>(args)...)); + m_children.back()->m_parent = this; } /** @@ -396,13 +277,13 @@ } /** - * Find a children in this. The type must have operator==. + * Find a child in this. The type must have operator==. * * @param child the child * @return the index or -1 if not found */ template <typename Value> - int indexOf(const Value &child, typename std::enable_if<TypeTraits<Value>::equalityComparable>::type * = 0) const + int indexOf(const Value &child, typename std::enable_if<TypeTraits<Value>::equalityComparable>::type * = nullptr) const { for (int i = 0; i < (int)m_children.size(); ++i) if (m_children[i] == child) @@ -412,7 +293,7 @@ } /** - * Access a children. + * Access a child. * * @param index the index * @return the reference to the children node @@ -420,11 +301,11 @@ */ T &operator[](int index) { - return static_cast<T &>(m_children.at(index)); + return static_cast<T &>(*m_children.at(index)); } /** - * Access a children. + * Access a child. * * @param index the index * @return the reference to the children node @@ -432,7 +313,7 @@ */ const T &operator[](int index) const { - return static_cast<const T &>(m_children.at(index)); + return static_cast<const T &>(*m_children.at(index)); } };
--- a/CMakeLists.txt Wed Oct 01 14:39:24 2014 +0200 +++ b/CMakeLists.txt Thu Oct 02 11:17:08 2014 +0200 @@ -56,6 +56,7 @@ option(WITH_PACK "Enable pack functions" On) option(WITH_PARSER "Enable parser tests" On) option(WITH_SOCKET "Enable sockets tests" On) +option(WITH_TREENODE "Enable treenode tests" On) option(WITH_UTF8 "Enable Utf8 functions tests" On) option(WITH_XMLPARSER "Enable XML tests" On) @@ -95,6 +96,10 @@ add_subdirectory(C++/Tests/Parser) endif () +if (WITH_TREENODE) + add_subdirectory(C++/Tests/TreeNode) +endif () + if (WITH_XDG AND UNIX) add_subdirectory(C++/Tests/Xdg) endif ()