TreeContainer.cpp

#include "treeContainer.h"

//structors
treeContainer::tree::tree()
{
    Root = std::make_shared<_Node>(0);
    //link Root with itself
    Root->ParentNode = Root.get();
    Root->NextNode = Root.get();
    Root->PrevNode = Root.get();

    _node_iterator = std::make_shared<_node_iterator_impl>();
    _const_node_iterator = std::make_shared<_const_node_iterator_impl>();
    _reverse_node_iterator = std::make_shared<_reverse_node_iterator_impl>();
    _const_reverse_node_iterator = std::make_shared<_const_reverse_node_iterator_impl>();
    _child_iterator = std::make_shared<_child_iterator_impl>();
    _const_child_iterator = std::make_shared<_const_child_iterator_impl>();
    _reverse_child_iterator = std::make_shared<_reverse_child_iterator_impl>();
    _const_reverse_child_iterator = std::make_shared<_const_reverse_child_iterator_impl>();
}

treeContainer::tree::~tree()
{
    clear();
    Root = nullptr;
}

/*--------------------------------------------------------------------------------------------------------------------------------------*/

//Functions

//Remove all Nodes from tree
void treeContainer::tree::clear()
{
    clear(tree_iterator(_node_iterator, Root.get()));
}

//Remove all childnodes from Node
void treeContainer::tree::clear(const tree_iterator& node)
{
    if(node._node->FirstNode) remove(tree_iterator(_node_iterator, node._node->FirstNode), tree_iterator(_node_iterator, node._node->LastNode));
}

//move "node" to end of "it"
void treeContainer::tree::move(const tree_iterator& parent, const tree_iterator& node)
{
    parent._node->appendNode(node._node->getPtr());
}

//move "node" to parent of "it" with position after "it"
void treeContainer::tree::insertAfter(const tree_iterator& pos, const tree_iterator& node)
{
    pos._node->insertAfter(node._node->getPtr());
}

//move "node" to parent of "it" with position before "it"
void treeContainer::tree::insertPrevious(const tree_iterator& pos, const tree_iterator& node)
{
    pos._node->insertPrevious(node._node->getPtr());
}

//swap two Nodes
void treeContainer::tree::swap(const tree_iterator& it_1, const tree_iterator& it_2)
{
    tree_iterator temp(_node_iterator, it_2._node->PrevNode);

    insertPrevious(it_1, it_2);
    insertAfter(temp, it_1);
}

//Remove node
treeContainer::tree::tree_iterator treeContainer::tree::remove(const tree_iterator& pos)
{
    return remove(pos, pos);
}

//Remove nodes in range
treeContainer::tree::tree_iterator treeContainer::tree::remove(const tree_iterator& first, const tree_iterator& last)
{
    tree_iterator it(_node_iterator,last._node), end(_node_iterator,first._node);
    _Node* rem = it._node;

    while(rem != end._node)
    {
        --it;
        rem->remove();
        rem = it._node;
    }
    --it;
    rem->remove();

    return tree_iterator(it);
}

//Returns depth of Node
int treeContainer::tree::getDepth(const tree_iterator& node)
{
    int deep = 0;
    _Node* tmp = node._node;
    while (tmp->ParentNode != tmp)
    {
        deep++;
        tmp = tmp->ParentNode;
    }

    return deep-1;
}

/*--------------------------------------------------------------------------------------------------------------------------------------*/

//Functions begin()/end()
treeContainer::tree::tree_iterator treeContainer::tree::begin()
{
    if(Root->FirstNode) return tree_iterator(_node_iterator, Root->FirstNode);
    else return tree_iterator(_node_iterator, Root.get());
}
treeContainer::tree::tree_iterator treeContainer::tree::cbegin() const
{
    if(Root->FirstNode) return tree_iterator(_const_node_iterator, Root->FirstNode);
    else return tree_iterator(_const_node_iterator, Root.get());
}
treeContainer::tree::tree_iterator treeContainer::tree::rbegin()
{
    tree_iterator ret(_reverse_node_iterator, Root.get());
    return tree_iterator(++ret);
}
treeContainer::tree::tree_iterator treeContainer::tree::crbegin() const
{
    tree_iterator ret(_const_reverse_node_iterator, Root.get());
    return tree_iterator(++ret);
}
treeContainer::tree::tree_iterator treeContainer::tree::begin(const tree_iterator& parent)
{
    return tree_iterator(_child_iterator, parent._node->FirstNode);
}
treeContainer::tree::tree_iterator treeContainer::tree::cbegin(const tree_iterator& parent) const
{
    return tree_iterator(_const_child_iterator, parent._node->FirstNode);
}
treeContainer::tree::tree_iterator treeContainer::tree::rbegin(const tree_iterator& parent)
{
    return tree_iterator(_reverse_child_iterator, parent._node->LastNode);
}
treeContainer::tree::tree_iterator treeContainer::tree::crbegin(const tree_iterator& parent) const
{
    return tree_iterator(_const_reverse_child_iterator, parent._node->LastNode);
}
treeContainer::tree::tree_iterator treeContainer::tree::end()
{
    return tree_iterator(_node_iterator, Root.get());
}
treeContainer::tree::tree_iterator treeContainer::tree::cend() const
{
    return tree_iterator(_const_node_iterator, Root.get());
}
treeContainer::tree::tree_iterator treeContainer::tree::rend()
{
    return tree_iterator(_reverse_node_iterator, Root.get());
}
treeContainer::tree::tree_iterator treeContainer::tree::crend() const
{
    return tree_iterator(_const_reverse_node_iterator, Root.get());
}
treeContainer::tree::tree_iterator treeContainer::tree::end(const tree_iterator& parent)
{
    tree_iterator tmp(_node_iterator, parent._node->LastNode);
    ++tmp;
    return tree_iterator(_child_iterator, tmp._node);
}
treeContainer::tree::tree_iterator treeContainer::tree::cend(const tree_iterator& parent) const
{
    tree_iterator tmp(_node_iterator, parent._node->LastNode);
    ++tmp;
    return tree_iterator(_const_child_iterator, tmp._node);
}
treeContainer::tree::tree_iterator treeContainer::tree::rend(const tree_iterator& parent)
{
    tree_iterator tmp(_node_iterator, parent._node->FirstNode);
    --tmp;
    return tree_iterator(_reverse_child_iterator, tmp._node);
}
treeContainer::tree::tree_iterator treeContainer::tree::crend(const tree_iterator& parent) const
{
    tree_iterator tmp(_node_iterator, parent._node->FirstNode);
    --tmp;
    return tree_iterator(_const_reverse_child_iterator, tmp._node);
}

//Functions get iterator of type
treeContainer::tree::tree_iterator treeContainer::tree::node_iterator(const tree_iterator& pos)
{
    return tree_iterator(_node_iterator, pos._node);
}
treeContainer::tree::tree_iterator treeContainer::tree::const_node_iterator(const tree_iterator& pos)
{
    return tree_iterator(_const_node_iterator, pos._node);
}
treeContainer::tree::tree_iterator treeContainer::tree::reverse_node_iterator(const tree_iterator& pos)
{
    return tree_iterator(_reverse_node_iterator, pos._node);
}
treeContainer::tree::tree_iterator treeContainer::tree::const_reverse_node_iterator(const tree_iterator& pos)
{
    return tree_iterator(_const_reverse_node_iterator, pos._node);
}
treeContainer::tree::tree_iterator treeContainer::tree::child_iterator(const tree_iterator& pos)
{
    return tree_iterator(_child_iterator, pos._node);
}
treeContainer::tree::tree_iterator treeContainer::tree::const_child_iterator(const tree_iterator& pos)
{
    return tree_iterator(_const_child_iterator, pos._node);
}
treeContainer::tree::tree_iterator treeContainer::tree::reverse_child_iterator(const tree_iterator& pos)
{
    return tree_iterator(_reverse_child_iterator, pos._node);
}
treeContainer::tree::tree_iterator treeContainer::tree::const_reverse_child_iterator(const tree_iterator& pos)
{
    return tree_iterator(_const_reverse_child_iterator, pos._node);
}

/*--------------------------------------------------------------------------------------------------------------------------------------*/

//class Node
//structors
treeContainer::tree::_Node::_Node() {}

treeContainer::tree::_Node::~_Node() {}

/*--------------------------------------------------------------------------------------------------------------------------------------*/

//class Node
//functions

//get shared_pointer of this
std::shared_ptr<treeContainer::tree::_Node> treeContainer::tree::_Node::getPtr()
{
    for(auto it = ParentNode->Children.begin(); it != ParentNode->Children.end(); ++it)
    {
        if(it->get() == this) return *it;
    }
    return nullptr;
}

//append node as last child of this
treeContainer::tree::_Node* treeContainer::tree::_Node::appendNode(const std::shared_ptr<_Node>& node)
{
    pushNewNode(node);

    if(!FirstNode) FirstNode = LastNode = node.get();
    else
    {
        linkNodes(LastNode, node.get());
        LastNode = node.get();
    }

    return node.get();
}

//insert node after this to children of parent
treeContainer::tree::_Node* treeContainer::tree::_Node::insertAfter(const std::shared_ptr<_Node>& node)
{
    ParentNode->pushNewNode(node);

    linkNodes(node.get(), NextNode);
    linkNodes(this, node.get());

    if(ParentNode->LastNode == this) ParentNode->LastNode = node.get();

    return node.get();
}

//insert node previous to this to children of parent
treeContainer::tree::_Node* treeContainer::tree::_Node::insertPrevious(const std::shared_ptr<_Node>& node)
{
    ParentNode->pushNewNode(node);

    linkNodes(PrevNode, node.get());
    linkNodes(node.get(), this);

    if(ParentNode->FirstNode == this) ParentNode->FirstNode = node.get();

    return node.get();
}

//remove this
void treeContainer::tree::_Node::remove()
{
    if(ParentNode != this) //is root?
    {
        ParentNode->erase(this);
        extract();
    }
}

//erase this from children of parent
void treeContainer::tree::_Node::erase(_Node* node)
{
    for(auto it = Children.begin(); it != Children.end(); ++it)
    {
        if(it->get() == node)
        {
            Children.erase(it);
            return;
        }
    }
}

//extract this from all linked nodes
void treeContainer::tree::_Node::extract()
{
    linkNodes(PrevNode, NextNode);
    if(ParentNode && ParentNode->FirstNode == this) ParentNode->FirstNode = NextNode;
    if(ParentNode && ParentNode->LastNode == this) ParentNode->LastNode = PrevNode;

    PrevNode = NextNode = nullptr;
    ParentNode = nullptr;
}

//get type_index of stored value
std::type_index treeContainer::tree::_Node::getValueType()
{
    return Value->getType();
}

//add existing node to this
void treeContainer::tree::_Node::pushNewNode(const std::shared_ptr<_Node>& node)
{
    Children.push_back(node);

    if(node->ParentNode) node->ParentNode->erase(node.get());

    node->extract();
    node->ParentNode = this;
}

//Link two nodes, first is the previuos node, second the next
void treeContainer::tree::_Node::linkNodes(_Node *first, _Node *second)
{
    if(first != 0) first->NextNode = second;
    if(second != 0) second->PrevNode = first;
}