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(const tree_iterator& it)
{
    if(it.myNode->getFirst()) it.myNode->getFirst()->remove(1);
}

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

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

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

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

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

//Remove node
treeContainer::node_iterator treeContainer::tree::remove(const tree_iterator& node)
{
    node_iterator ret = node.myNode->getPrev();
    node.myNode->remove(0);

    return ret;
}

//Remove all childnodes from it to End
treeContainer::node_iterator treeContainer::tree::removeToEnd(const tree_iterator& pos)
{
    node_iterator ret = pos.myNode->getPrev();
    pos.myNode->remove(1);

    return ret;
}

//Remove all childnodes from it to Start
treeContainer::node_iterator treeContainer::tree::removeToStart(const tree_iterator& pos)
{
    node_iterator ret = pos.myNode->getNext();
    pos.myNode->remove(2);

    return ret;
}

//Returns depth of Node
int treeContainer::tree::getDepth(const tree_iterator& node)
{
    int deep = 0;
    Node* tmp = node.myNode;
    while (tmp->getParent() != tmp)
    {
        deep++;
        tmp = tmp->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
{
    if(myRoot->getFirst()) return const_node_iterator(myRoot->getFirst());
    else return const_node_iterator(myRoot->getEnd());
}
treeContainer::reverse_node_iterator treeContainer::tree::rbegin()
{
    if(myRoot->getLast()) return reverse_node_iterator(myRoot->getLast());
    else return reverse_node_iterator(myRoot->getStart());
}
treeContainer::const_reverse_node_iterator treeContainer::tree::crbegin() const
{
    if(myRoot->getLast()) return const_reverse_node_iterator(myRoot->getLast());
    else return const_reverse_node_iterator(myRoot->getStart());
}
treeContainer::child_iterator treeContainer::tree::begin(const tree_iterator& parent)
{
    return child_iterator(parent);
}
treeContainer::const_child_iterator treeContainer::tree::cbegin(const tree_iterator& parent) const
{
    return const_child_iterator(parent);
}
treeContainer::reverse_child_iterator treeContainer::tree::rbegin(const tree_iterator& parent)
{
    return reverse_child_iterator(parent);
}
treeContainer::const_reverse_child_iterator treeContainer::tree::crbegin(const tree_iterator& parent) const
{
    return const_reverse_child_iterator(parent);
}
treeContainer::deep_child_iterator treeContainer::tree::dbegin(const tree_iterator& parent)
{
    return deep_child_iterator(parent);
}
treeContainer::const_deep_child_iterator treeContainer::tree::cdbegin(const tree_iterator& parent) const
{
    return const_deep_child_iterator(parent);
}
treeContainer::reverse_deep_child_iterator treeContainer::tree::rdbegin(const tree_iterator& parent)
{
    return reverse_deep_child_iterator(parent);
}
treeContainer::const_reverse_deep_child_iterator treeContainer::tree::crdbegin(const tree_iterator& parent) const
{
    return const_reverse_deep_child_iterator(parent);
}
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(const tree_iterator& parent)
{
    return child_iterator(parent.myNode->mySentinelEnd.get());
}
treeContainer::const_child_iterator treeContainer::tree::cend(const tree_iterator& parent) const
{
    return const_child_iterator(parent.myNode->mySentinelEnd.get());
}
treeContainer::reverse_child_iterator treeContainer::tree::rend(const tree_iterator& parent)
{
    return reverse_child_iterator(parent.myNode->mySentinelStart.get());
}
treeContainer::const_reverse_child_iterator treeContainer::tree::crend(const tree_iterator& parent) const
{
    return const_reverse_child_iterator(parent.myNode->mySentinelStart.get());
}
treeContainer::deep_child_iterator treeContainer::tree::dend(const tree_iterator& parent)
{
    return deep_child_iterator(parent.myNode->mySentinelEnd.get());
}
treeContainer::const_deep_child_iterator treeContainer::tree::cdend(const tree_iterator& parent) const
{
    return const_deep_child_iterator(parent.myNode->mySentinelEnd.get());
}
treeContainer::reverse_deep_child_iterator treeContainer::tree::rdend(const tree_iterator& parent)
{
    return reverse_deep_child_iterator(parent.myNode->mySentinelStart.get());
}
treeContainer::const_reverse_deep_child_iterator treeContainer::tree::crdend(const tree_iterator& parent) const
{
    return const_reverse_deep_child_iterator(parent.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.get());
        erase(mySentinelEnd.get());
        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;
        }
    }
}

//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.get());

    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() {}