TreeContainer.cpp

#include "treeContainer.h"

//structors
treeContainer::tree::tree()
{
    myRoot = std::make_shared<Node>(0);
    myRoot->setParent(myRoot.get());
}

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

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

//Functions

//Remove all Nodes from tree
void treeContainer::tree::clear()
{
    myRoot->remove(1);
}

//Remove all childnodes from Node
void treeContainer::tree::clear(tree_iterator it)
{
    if(it.myNode->getFirst()) it.myNode->getFirst()->remove(1);
}

//move "node" to end of "it"
treeContainer::node_iterator treeContainer::tree::move(tree_iterator it, tree_iterator node)
{
    it.myNode->appendNode(node.myNode->getPtr());
    return node_iterator(node);
}

//move "node" to parent of "it" with position after "it"
treeContainer::node_iterator treeContainer::tree::insertAfter(tree_iterator it, tree_iterator node)
{
    it.myNode->insertAfter(node.myNode->getPtr());
    return node_iterator(node);
}

//move "node" to parent of "it" with position before "it"
treeContainer::node_iterator treeContainer::tree::insertPrevious(tree_iterator it, tree_iterator node)
{
    it.myNode->insertPrevious(node.myNode->getPtr());
    return node_iterator(node);
}

//swap two Nodes
void treeContainer::tree::swap(tree_iterator it_1, tree_iterator it_2)
{
    node_iterator temp(it_2.myNode->getPrev());

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

//Remove node
void treeContainer::tree::remove(tree_iterator it)
{
    it.myNode->remove(0);
}

//Remove all childnodes from it to End
void treeContainer::tree::removeToEnd(tree_iterator it)
{
    it.myNode->remove(1);
}

//Remove all childnodes from it to Start
void treeContainer::tree::removeToStart(tree_iterator it)
{
    it.myNode->remove(2);
}

//Returns depth of Node
int treeContainer::tree::getDepth(tree_iterator it)
{
    int deep = 0;
    Node* node = it.myNode;
    while (node->getParent() != node)
    {
        deep++;
        node = node->getParent();
    }

    return deep-1;
}

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

//Functions begin()/end()
treeContainer::node_iterator treeContainer::tree::begin()
{
    if(myRoot->getFirst()) return node_iterator(myRoot->getFirst());
    else return node_iterator(myRoot->getEnd());

}
treeContainer::const_node_iterator treeContainer::tree::cbegin() const
{
    return const_node_iterator(myRoot->getFirst());;
}
treeContainer::reverse_node_iterator treeContainer::tree::rbegin()
{
    return reverse_node_iterator(myRoot->getEnd()->getPrev());
}
treeContainer::const_reverse_node_iterator treeContainer::tree::crbegin() const
{
    return const_reverse_node_iterator(myRoot->getEnd()->getPrev());
}
treeContainer::child_iterator treeContainer::tree::begin(tree_iterator it)
{
    return child_iterator(it);
}
treeContainer::const_child_iterator treeContainer::tree::cbegin(tree_iterator it) const
{
    return const_child_iterator(it);
}
treeContainer::reverse_child_iterator treeContainer::tree::rbegin(tree_iterator it)
{
    return reverse_child_iterator(it);
}
treeContainer::const_reverse_child_iterator treeContainer::tree::crbegin(tree_iterator it) const
{
    return const_reverse_child_iterator(it);
}
treeContainer::deep_child_iterator treeContainer::tree::dbegin(tree_iterator it)
{
    return deep_child_iterator(it);
}
treeContainer::const_deep_child_iterator treeContainer::tree::cdbegin(tree_iterator it) const
{
    return const_deep_child_iterator(it);
}
treeContainer::reverse_deep_child_iterator treeContainer::tree::rdbegin(tree_iterator it)
{
    return reverse_deep_child_iterator(it);
}
treeContainer::const_reverse_deep_child_iterator treeContainer::tree::crdbegin(tree_iterator it) const
{
    return const_reverse_deep_child_iterator(it);
}
treeContainer::node_iterator treeContainer::tree::end()
{
    return node_iterator(myRoot->getEnd());
}
treeContainer::const_node_iterator treeContainer::tree::cend() const
{
    return const_node_iterator(myRoot->getEnd());
}
treeContainer::reverse_node_iterator treeContainer::tree::rend()
{
    return reverse_node_iterator(myRoot->getStart());
}
treeContainer::const_reverse_node_iterator treeContainer::tree::crend() const
{
    return const_reverse_node_iterator(myRoot->getStart());
}
treeContainer::child_iterator treeContainer::tree::end(tree_iterator it)
{
    return child_iterator(it.myNode->mySentinelEnd.get());
}
treeContainer::const_child_iterator treeContainer::tree::cend(tree_iterator it) const
{
    return const_child_iterator(it.myNode->mySentinelEnd.get());
}
treeContainer::reverse_child_iterator treeContainer::tree::rend(tree_iterator it)
{
    return reverse_child_iterator(it.myNode->mySentinelStart.get());
}
treeContainer::const_reverse_child_iterator treeContainer::tree::crend(tree_iterator it) const
{
    return const_reverse_child_iterator(it.myNode->mySentinelStart.get());
}
treeContainer::deep_child_iterator treeContainer::tree::dend(tree_iterator it)
{
    return deep_child_iterator(it.myNode->mySentinelEnd.get());
}
treeContainer::const_deep_child_iterator treeContainer::tree::cdend(tree_iterator it) const
{
    return const_deep_child_iterator(it.myNode->mySentinelEnd.get());
}
treeContainer::reverse_deep_child_iterator treeContainer::tree::rdend(tree_iterator it)
{
    return reverse_deep_child_iterator(it.myNode->mySentinelStart.get());
}
treeContainer::const_reverse_deep_child_iterator treeContainer::tree::crdend(tree_iterator it) const
{
    return const_reverse_deep_child_iterator(it.myNode->mySentinelStart.get());
}
/*---------------------------------------------------------------------------------------------------------------------*/

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

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

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

//class Node
//functions

//get/set-functions
treeContainer::tree::Node* treeContainer::tree::Node::getPrev()
{
    return myPrevNode;
}
treeContainer::tree::Node* treeContainer::tree::Node::getNext()
{
    return myNextNode;
}
treeContainer::tree::Node* treeContainer::tree::Node::getFirst()
{
    return myFirstNode;
}
treeContainer::tree::Node* treeContainer::tree::Node::getLast()
{
    return myLastNode;
}
treeContainer::tree::Node *treeContainer::tree::Node::getParent()
{
    return myParentNode;
}
treeContainer::tree::Node *treeContainer::tree::Node::getStart()
{
    return mySentinelStart.get();
}
treeContainer::tree::Node *treeContainer::tree::Node::getEnd()
{
    return mySentinelEnd.get();
}
void treeContainer::tree::Node::setPrev(Node* prev)
{
    myPrevNode = prev;
}
void treeContainer::tree::Node::setNext(Node* next)
{
    myNextNode = next;
}
void treeContainer::tree::Node::setFirst(Node* first)
{
    myFirstNode = first;
}
void treeContainer::tree::Node::setLast(Node* last)
{
    myLastNode = last;
}
void treeContainer::tree::Node::setParent(tree::Node* parent)
{
    myParentNode = parent;
}

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

//append node as last child of this
treeContainer::node_iterator treeContainer::tree::Node::appendNode(std::shared_ptr<Node> node)
{
    pushNewNode(node);

    if(!myFirstNode) myFirstNode = myLastNode = node.get();
    else
    {
        linkNodes(getLast(), node.get());
        myLastNode = node.get();
    }

    checkSentinels();
    return node_iterator(node.get());
}

//insert node after this to children of parent
treeContainer::node_iterator treeContainer::tree::Node::insertAfter(std::shared_ptr<Node> node)
{
    myParentNode->pushNewNode(node);

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

    if(myParentNode->getLast() == this) myParentNode->setLast(node.get());

    return node_iterator(node.get());
}

//insert node previous to this to children of parent
treeContainer::node_iterator treeContainer::tree::Node::insertPrevious(std::shared_ptr<Node> node)
{
    myParentNode->pushNewNode(node);

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

    if(myParentNode->getFirst() == this) myParentNode->setFirst(node.get());

    return node_iterator(node.get());
}

//remove this
/* Parameter:
* 0: Append next node to previous
* 1: Remove all nodes from this to end
* 2: Remove all nodes from this to start
*/
void treeContainer::tree::Node::remove(int param)
{
    if(myFirstNode) myFirstNode->remove(1);
    if(param == 1) if(myNextNode && myNextNode != myParentNode->getEnd()) myNextNode->remove(1);
    if(param == 2) if(myPrevNode && myPrevNode != myParentNode->getStart()) myPrevNode->remove(2);

    if(myParentNode != this) //is root?
    {
        erase(mySentinelStart);
        erase(mySentinelEnd);
        mySentinelStart = nullptr;
        mySentinelEnd = nullptr;
        myParentNode->erase(this);
        extract();
    }
}

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

//extract this from all linked nodes
void treeContainer::tree::Node::extract()
{
    linkNodes(myPrevNode, myNextNode);
    if(myParentNode && myParentNode->getFirst() == this)
    {
        if(myNextNode != myParentNode->getEnd()) myParentNode->setFirst(myNextNode);
        else myParentNode->setFirst(NULL);
    }
    if(myParentNode && myParentNode->getLast() == this)
    {
        if(myPrevNode != myParentNode->getStart()) myParentNode->setLast(myPrevNode);
        else myParentNode->setLast(NULL);
    }

    myPrevNode = myNextNode = nullptr;
    myParentNode = nullptr;
}

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

//add existing node to this
std::shared_ptr<treeContainer::tree::Node> treeContainer::tree::Node::pushNewNode(std::shared_ptr<Node> node)
{
    myChildren.push_back(node);

    if(node->getParent()) node->getParent()->erase(node);

    node->extract();
    node->setParent(this);

    return node;
}

//Link Sentinels correctly
void treeContainer::tree::Node::checkSentinels()
{
    if(myFirstNode)
    {
        if(getStart()->getNext() != getFirst()) linkNodes(getStart(), getFirst());
        if(getEnd()->getPrev() != getLast()) linkNodes(getLast(), getEnd());
    }
    else linkNodes(getStart(), getEnd());
}

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

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

//class SentinalNode
//structors

treeContainer::tree::SentinelNode::SentinelNode(int value)
{
    setValue(value);
}
treeContainer::tree::SentinelNode::~SentinelNode() {}