Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifndef TREECONTAINER_H
- #define TREECONTAINER_H
- /* API & Description:
- *
- * This Container provides the abillity to store values of any type.
- * The structure of the Container is a tree. Each node of the tree stores a value of type T and can have N children.
- * It provides different kinds of iterators to navigate through the tree. Access to the stored value of a node is only possible with an iterator.
- *
- *
- * Class Descriptions:
- * tree:
- * The main class. It provides the functions to modify the tree like creating new nodes, removing them or move them to another position.
- * It also provides the tree_iterator, a wrapper to wrap different kinds of iterators with different increment and decrement behaviour.
- *
- * Iterators:
- * Different types of Iterators to navigate through the tree and get access to the values of the node or alter the values.
- * The only public iterator is the wrapper tree_iterator. tree_iterator provides the functions to navigate through the tree and
- * getting access to stored values of the nodes. tree_iterator wraps different kinds of iterators with different increment an decrement behaviour.
- *
- * Iterator types:
- * node_iterator: iterates through all nodes of the tree.
- * const_node_iterator: const version of node_iterator
- *
- * reverse_node_iterator: iterates reverse through all nodes of the tree.
- * const_reverse_node_iterator: const version of reverse_node_iterator
- *
- * child_iterator: iterates through all childnodes of a node. Ignores the chilren of the children.
- * const_child_iterator: const version of child_iterator
- *
- * reverse_child_iterator: iterates reverse through all childnodes of a node. Ignores the chilren of the children.
- * const_reverse_child_iterator: const version of reverse_child_iterator
- *
- *
- *
- * API:
- *
- * tree:
- *
- * Public methods:
- * template<typename T> node_iterator find(const T& value); Find the first node with the value in the tree
- * template<typename T> tree_iterator find(const tree_iterator& start, Find the first node in range. If end of tree is reached the search is continued
- * const tree_iterator& end, const T& value); at the beginning of the tree.
- *
- * void clear(); Remove all nodes from the tree
- * void clear(const tree_iterator& it); Remove all nodes from the children of the node
- *
- * template<typename T> tree_iterator createNode(const tree_iterator& parent, const T& value); Create a new Node with value and type of value T and
- * append it to the parent
- *
- * void move(const tree_iterator& parent, const tree_iterator& node); Move an existing node to the end of the children of a node
- * void insertAfter(const tree_iterator& pos, const tree_iterator& node); Append an existing node to the parent of a node at position after node
- * void insertPrevious(const tree_iterator& pos, const tree_iterator& node); Append an existing node to the parent of a node at position previous to node
- * void swap(const tree_iterator& it_1, const tree_iterator& it_2); Swap two Nodes
- *
- * tree_iterator remove(const tree_iterator& node); Remove the node from tree
- * tree_iterator remove(const tree_iterator& first, Remove all children in range
- * const tree_iterator& last);
- *
- * int getDepth(const tree_iterator& node); Returns the depth of the node. The Childnodes of Root have depth = 0;
- *
- *
- * tree_iterator begin(); Returns a tree_iterator of type node_iterator to the beginning of the tree
- * tree_iterator cbegin() const; Returns a tree_iterator of type const_node_iterator to the beginning of the tree
- *
- * tree_iterator rbegin(); Returns a tree_iterator of type reverse_node_iterator to the reverse beginning of the tree
- * tree_iterator crbegin() const; Returns a tree_iterator of type const_reverse_node_iterator to the reverse beginning of the tree
- *
- * tree_iterator begin(const tree_iterator& parent); Returns a tree_iterator of type child_iterator to the beginning of the children of the node
- * tree_iterator cbegin(const tree_iterator& parent) const; Returns a tree_iterator of type const_child_iterator to the beginning of the children of the node
- *
- * tree_iterator rbegin(const tree_iterator& parent); Returns a tree_iterator of type reverse_child_iterator to the reverse beginning of the children of the node
- * tree_iterator crbegin(const tree_iterator& parent) const; Returns a tree_iterator of type const_reverse_child_iterator to the reverse beginning of the children of the node
- *
- * tree_iterator end(); Returns a tree_iterator of type node_iterator to the end of the tree
- * tree_iterator cend() const; Returns a tree_iterator of type const_node_iterator to the end of the tree
- *
- * tree_iterator rend(); Returns a tree_iterator of type reverse_node_iterator to the reverse end of the tree
- * tree_iterator crend() const; Returns a tree_iterator of type const_reverse_node_iterator to the reverse end of the tree
- *
- * tree_iterator end(const tree_iterator& parent); Returns a tree_iterator of type child_iterator to the end of the children
- * tree_iterator cend(const tree_iterator& parent) const; Returns a tree_iterator of type const_child_iterator to the end of the children
- *
- * tree_iterator rend(const tree_iterator& parent); Returns a tree_iterator of type reverse_child_iterator to the reverse end of the children
- * tree_iterator crend(const tree_iterator& parent) const; Returns a tree_iterator of type const_reverse_child_iterator to the reverse end of the children
- *
- *
- * tree_iterator node_iterator(const tree_iterator& pos); Returns a tree_iterator of type node_iterator to the position
- * tree_iterator const_node_iterator(const tree_iterator& pos); Returns a tree_iterator of type const_node_iterator to the position
- * tree_iterator reverse_node_iterator(const tree_iterator& pos); Returns a tree_iterator of type reverse_node_iterator to the position
- * tree_iterator const_reverse_node_iterator(const tree_iterator& pos); Returns a tree_iterator of type const_reverse_node_iterator to the position
- * tree_iterator child_iterator(const tree_iterator& pos); Returns a tree_iterator of type child_iterator to the position
- * tree_iterator const_child_iterator(const tree_iterator& pos); Returns a tree_iterator of type const_child_iterator to the position
- * tree_iterator reverse_child_iterator(const tree_iterator& pos); Returns a tree_iterator of type reverse_child_iterator to the position
- * tree_iterator const_reverse_child_iterator(const tree_iterator& pos);Returns a tree_iterator of type const_reverse_child_iterator to the position
- *
- *
- *
- * tree-iterator:
- *
- * Public methods:
- * tree_iterator(const tree_iterator& it): Constructor, initialize the tree_iterator with an other tree_iterator
- *
- * operator =(const tree_iterator& rhs): Assign an iterator to the tree_iterator
- * bool operator ==(const tree_iterator& rhs): Compare if the passed iterator and this pointing to the same node
- * bool operator !=(const tree_iterator& rhs): Compare if the passed iterator and this are not pointing to the same node
- * tree_iterator& operator ++(): Pre-increment operator. Behaviour depends on wrapped iterator
- * const tree_iterator operator ++(int junk): Post-increment operator. Behaviour depends on wrapped iterator
- * tree_iterator& operator --(): Pre-decrement operator. Behaviour depends on wrapped iterator
- * const tree_iterator operator --(int junk): Post-decrement operator. Behaviour depends on wrapped iterator
- *
- * void Next(): Set the iterator to the next sibling.
- * void Prev(): Set the iterator to the previous sibling
- * void First(): Set the iterator to the first child
- * void Last(): Set the iterator to the last child
- * void Parent(): Set the iterator to the parent
- *
- * bool hasChildren(): Returns true, if the node the iterator is pointing to has children
- *
- * template<typename T> void setValue(T value): Assign a value to node the iterator is pointing to
- * template<typename T> T getValue(): Get the value of the node the iterator is pointing to
- * std::type_index getValueType(): get the type of the value of the node the iterator is pointing to
- *
- */
- #include <map>
- #include <vector>
- #include <typeinfo>
- #include <typeindex>
- #include <memory>
- namespace treeContainer {
- class tree{
- private:
- class _Node;
- public:
- class tree_iterator;
- //structors
- public:
- tree();
- ~tree();
- //functions
- public:
- /* Description: find first node with value in tree
- * Parameters: "value" of type T
- * Return: node_iterator to first node with value of type T. If no node match, end() is returned */
- template<typename T> tree_iterator find(const T& value);
- /* Description: find first node with value in range
- * Parameters: tree_iterator "pos", "value" of type T
- * Return: node_iterator to first node with value of type T. If no node match, end() is returned */
- template<typename T> tree_iterator find(const tree_iterator& start, const tree_iterator& end, const T& value);
- /* Description: Remove all nodes from tree
- * Parameters: None
- * Return: None */
- void clear();
- /* Description: Remove all childnodes from node
- * Parameters: tree_iterator "it"
- * Return: None */
- void clear(const tree_iterator& node);
- /* Description: Create new node with value of type T and append it to childnodes of parent
- * CAUTION: Use the end()-method to append the node to Root
- * Parameters: tree_iterator "it", "value" of type T
- * Return: node_iterator to created node */
- template<typename T> tree_iterator createNode(const tree_iterator& parent, const T& value);
- /* Description: Append existing node to childnodes of the new parent
- * Parameters: new parent: tree_iterator "parent", moved node: tree_iterator "node"
- * Return: None */
- void move(const tree_iterator& parent, const tree_iterator& node);
- /* Description: Append existing node to childnodes of parent of node at position after node
- * Parameters: tree_iterator "pos", tree_iterator "node"
- * Return: None */
- void insertAfter(const tree_iterator& pos, const tree_iterator& node);
- /* Description: Append existing node to childnodes of parent of node at position previous to node
- * Parameters: tree_iterator "pos", tree_iterator "node"
- * Return: None */
- void insertPrevious(const tree_iterator& pos, const tree_iterator& node);
- /* Description: swap nodes of "it_1" and "it_2"
- * Parameters: tree_iterator "it_1", tree_iterator "it_2"
- * Return: None */
- void swap(const tree_iterator& it_1, const tree_iterator& it_2);
- /* Description: delete node.
- * Parameters: tree_iterator pos
- * Return: node_iterator to previous or in case first is the first children to the parent node */
- tree_iterator remove(const tree_iterator& pos);
- /* Description: delete nodes. All nodes from first to last will be deleted
- * Parameters: tree_iterator first, tree_iterator last
- * Return: node_iterator to previous or in case first is the first children to the parent node */
- tree_iterator remove(const tree_iterator& first, const tree_iterator& last);
- /* Description: get depth of node in tree, children of Root has Deep = 0
- * Parameters: tree_iterator "node"
- * Return: depth of type int */
- int getDepth(const tree_iterator& node);
- //Functions iterating
- /* Description: returns iterator to beginning of tree/childnodes
- * CAUTION: use the function which belongs to the used iterator to ensure correctly iterating
- * Parameters: node_iterators: None, child_iterators: tree_iterator to parent
- * Return: tree_iterator to the beginning of tree/childnodes */
- /* Description: returns (const_)node_iterator to beginning of tree for const an non-const node_iterators
- * In case the tree is empty it returns an node_iterator to root, als to the first child */
- tree_iterator begin();
- tree_iterator cbegin() const;
- /* Description: returns (const_)reverse_tree_iterator to reverse beginning of tree for const an non-const reverse_node_iterators */
- tree_iterator rbegin();
- tree_iterator crbegin() const;
- /* Description: returns (const_)child_iterator to beginning of childnodes of node for const an non-const child_node_iterators */
- tree_iterator begin(const tree_iterator& parent);
- tree_iterator cbegin(const tree_iterator& parent) const;
- /* Description: returns (const_)reverse_child_iterator to reverse beginning of childnodes of node for const an non-const reverse_child_node_iterators */
- tree_iterator rbegin(const tree_iterator& parent);
- tree_iterator crbegin(const tree_iterator& parent) const;
- /* Description: returns iterator to end of tree/childnodes
- * CAUTION: use the function which belongs to the used iterator to ensure correctly iterating
- * Parameters: node_iterators: None, child_iterators: tree_iterator "child"
- * Return: iterator to the end of tree/childnodes */
- /* Description: returns (const_)node_iterator to end of tree for const an non-const node_iterators */
- tree_iterator end();
- tree_iterator cend() const;
- /* Description: returns (const_)reverse_node_iterator to reverse end of tree for const an non-const reverse_node_iterators */
- tree_iterator rend();
- tree_iterator crend() const;
- /* Description: returns (const_)child_iterator to end of childnodes of node for const an non-const child_node_iterators */
- tree_iterator end(const tree_iterator& parent);
- tree_iterator cend(const tree_iterator& parent) const;
- /* Description: returns (const_)reverse_child_iterator to reverse end of childnodes of node for const an non-const reverse_child_node_iterators */
- tree_iterator rend(const tree_iterator& parent);
- tree_iterator crend(const tree_iterator& parent) const;
- //Functions get Iterator of type
- /*Description: Returns a tree_iterator which wraps an iterator of called type pointing to the node of the passed tree_iterator */
- tree_iterator node_iterator(const tree_iterator& pos);
- tree_iterator const_node_iterator(const tree_iterator& pos);
- tree_iterator reverse_node_iterator(const tree_iterator& pos);
- tree_iterator const_reverse_node_iterator(const tree_iterator& pos);
- tree_iterator child_iterator(const tree_iterator& pos);
- tree_iterator const_child_iterator(const tree_iterator& pos);
- tree_iterator reverse_child_iterator(const tree_iterator& pos);
- tree_iterator const_reverse_child_iterator(const tree_iterator& pos);
- //Classes
- //Iterators:
- private:
- class _iterator_impl
- {
- friend class tree;
- public:
- virtual ~_iterator_impl() {}
- /*Description: Compare if the nodes the passed iterator and this are pointing to are the same */
- bool equal(const tree_iterator& rhs, _Node* node)
- {
- return node == rhs._node;
- }
- /*Description: Compare if the nodes the passed iterator and this are pointing to are not the same */
- bool unequal(const tree_iterator& rhs, _Node* node)
- {
- return !(node == rhs._node);
- }
- /*Description: Set the iterator to the next sibling.
- * If the next sibling is the end of the children of the parent, the iterator is set to the parent */
- _Node* Next(_Node* node)
- {
- if(node->NextNode) node = node->NextNode;
- else node = Parent(node);
- return node;
- }
- /*Description: Set the iterator to the previous sibling.
- * If the previous sibling is the start of the children of the parent, the iterator is set to the parent */
- _Node* Prev(_Node* node)
- {
- if(node->PrevNode) node = node->PrevNode;
- else node = Parent(node);
- return node;
- }
- /*Description: Set the iterator to the first child of the node.
- * If the node has no children, the iterator is not set to an other node */
- _Node* First(_Node* node)
- {
- if(node->FirstNode) node = node->FirstNode;
- return node;
- }
- /*Description: Set the iterator to the last child of the node.
- * If the node has no children, the iterator is not set to an other node */
- _Node* Last(_Node* node)
- {
- if(node->LastNode) node = node->LastNode;
- return node;
- }
- /*Description: Set the iterator to the parent of the node */
- _Node* Parent(_Node* node)
- {
- return node->ParentNode;
- }
- /*Description: Assigns a new value to the node */
- template<typename T> void setValue(_Node* node, T value)
- {
- node->setValue(value);
- }
- /*Description: Get the value of the node */
- template<typename T> T getValue(_Node* node)
- {
- return node->getValue<T>();
- }
- /*Description: Get the type of the value of the node. Returns as type_index*/
- std::type_index getValueType(_Node* node)
- {
- return node->getValueType();
- }
- /*Description: Returns true, if the node has one or more children, else false */
- bool hasChildren(_Node* node)
- {
- if(node->FirstNode) return true;
- else return false;
- }
- virtual _Node* pre_increment(_Node* node) = 0;
- virtual _Node* pre_decrement(_Node* node) = 0;
- protected:
- /*Description: Internal method. Set the iterator to the next node. If the actual node has children the iterator is set to the first child
- At the end of the children getNext() is called to get the next node which is not a sentinel Node*/
- _Node* increment(_Node* node)
- {
- if(node->FirstNode) node = node->FirstNode;
- else
- {
- while(!node->NextNode) node = node->ParentNode;
- node = node->NextNode;
- }
- return node;
- }
- /*Description: Internal method. Set the iterator to the previus node. If the actual node has children the iterator is set to the last child
- At the Start of the children getPrev() is called to get the previus node which is not a sentinel node*/
- _Node* decrement(_Node* node)
- {
- if(node->PrevNode)
- {
- node = node->PrevNode;
- while(node->LastNode) node = node->LastNode;
- }
- else node = node->ParentNode;
- return node;
- }
- };
- class _node_iterator_impl : public _iterator_impl
- {
- public:
- _node_iterator_impl() {}
- ~_node_iterator_impl() {}
- /*Description: Increment an decrement operators. Behaviour depends on type of the iterator */
- _Node* pre_increment(_Node* node)
- {
- return increment(node);
- }
- _Node* pre_decrement(_Node* node)
- {
- return decrement(node);
- }
- };
- class _const_node_iterator_impl : public _iterator_impl
- {
- public:
- _const_node_iterator_impl() {}
- ~_const_node_iterator_impl() {}
- /*Description: Increment an decrement operators. Behaviour depends on type of the iterator */
- _Node* pre_increment(_Node* node)
- {
- return increment(node);
- }
- _Node* pre_decrement(_Node* node)
- {
- return decrement(node);
- }
- };
- class _reverse_node_iterator_impl : public _iterator_impl
- {
- public:
- _reverse_node_iterator_impl() {}
- ~_reverse_node_iterator_impl() {}
- /*Description: Increment an decrement operators. Behaviour depends on type of the iterator */
- _Node* pre_increment(_Node* node)
- {
- return decrement(node);
- }
- _Node* pre_decrement(_Node* node)
- {
- return increment(node);
- }
- };
- class _const_reverse_node_iterator_impl : public _iterator_impl
- {
- public:
- _const_reverse_node_iterator_impl() {}
- ~_const_reverse_node_iterator_impl() {}
- /*Description: Increment an decrement operators. Behaviour depends on type of the iterator */
- _Node* pre_increment(_Node* node)
- {
- return decrement(node);
- }
- _Node* pre_decrement(_Node* node)
- {
- return increment(node);
- }
- };
- class _child_iterator_impl : public _iterator_impl
- {
- public:
- _child_iterator_impl() {}
- ~_child_iterator_impl() {}
- /*Description: Increment an decrement operators. Behaviour depends on type of the iterator */
- _Node* pre_increment(_Node* node)
- {
- if(node->NextNode) node = node->NextNode;
- else node = increment(node);
- return node;
- }
- _Node* pre_decrement(_Node* node)
- {
- if(node->PrevNode) node = node->PrevNode;
- else node = decrement(node);
- return node;
- }
- };
- class _const_child_iterator_impl : public _iterator_impl
- {
- public:
- _const_child_iterator_impl() {}
- ~_const_child_iterator_impl() {}
- /*Description: Increment an decrement operators. Behaviour depends on type of the iterator */
- _Node* pre_increment(_Node* node)
- {
- if(node->NextNode) node = node->NextNode;
- else node = increment(node);
- return node;
- }
- _Node* pre_decrement(_Node* node)
- {
- if(node->PrevNode) node = node->PrevNode;
- else node = decrement(node);
- return node;
- }
- };
- class _reverse_child_iterator_impl : public _iterator_impl
- {
- public:
- _reverse_child_iterator_impl() {}
- ~_reverse_child_iterator_impl() {}
- /*Description: Increment an decrement operators. Behaviour depends on type of the iterator */
- _Node* pre_increment(_Node* node)
- {
- if(node->PrevNode) node = node->PrevNode;
- else node = decrement(node);
- return node;
- }
- _Node* pre_decrement(_Node* node)
- {
- if(node->NextNode) node = node->NextNode;
- else node = increment(node);
- return node;
- }
- };
- class _const_reverse_child_iterator_impl : public _iterator_impl
- {
- public:
- _const_reverse_child_iterator_impl() {}
- ~_const_reverse_child_iterator_impl() {}
- /*Description: Increment an decrement operators. Behaviour depends on type of the iterator */
- _Node* pre_increment(_Node* node)
- {
- if(node->PrevNode) node = node->PrevNode;
- else node = decrement(node);
- return node;
- }
- _Node* pre_decrement(_Node* node)
- {
- if(node->NextNode) node = node->NextNode;
- else node = increment(node);
- return node;
- }
- };
- public:
- class tree_iterator
- {
- friend class tree;
- private:
- tree_iterator(const std::shared_ptr<_iterator_impl>& it, _Node* node) : iterator(it), _node(node) {}
- public:
- tree_iterator(const tree_iterator& it) : iterator(it.iterator), _node(it._node) {}
- ~tree_iterator() {}
- /*Description: Set the iterator to the next sibling.
- * If the next sibling is the end of the children of the parent, the iterator is set to the parent */
- void Next() { _node = iterator->Next(_node); }
- /*Description: Set the iterator to the previous sibling.
- * If the previous sibling is the start of the children of the parent, the iterator is set to the parent */
- void Prev() { _node = iterator->Prev(_node); }
- /*Description: Set the iterator to the first child of the node.
- * If the node has no children, the iterator is not set to an other node */
- void First() { _node = iterator->First(_node); }
- /*Description: Set the iterator to the last child of the node.
- * If the node has no children, the iterator is not set to an other node */
- void Last() { _node = iterator->Last(_node); }
- /*Description: Set the iterator to the parent of the node */
- void Parent() { _node = iterator->Parent(_node); }
- /*Description: Returns true, if the node has one or more children, else false */
- bool hasChildren() { return iterator->hasChildren(_node); }
- /*Description: Assigns a new value to the node */
- template<typename T> void setValue(T value) { iterator->setValue<T>(_node, value); }
- /*Description: Get the value of the node */
- template<typename T> T getValue() { return iterator->getValue<T>(_node); }
- /*Description: Get the type of the value of the node. Returns as type_index*/
- std::type_index getValueType() { return iterator->getValueType(_node); }
- /*Description: Assign an iterator to this */
- void operator =(const tree_iterator& rhs) { iterator = rhs.iterator; _node = rhs._node; }
- /*Description: Compare if the nodes the passed iterator and this are pointing to are the same */
- bool operator ==(const tree_iterator& rhs) { return iterator->equal(rhs, _node); }
- /*Description: Compare if the nodes the passed iterator and this are pointing to are not the same */
- bool operator !=(const tree_iterator& rhs) { return iterator->unequal(rhs, _node); }
- /*Description: pre-increment operator. Behaviour depends on wrappes iterator. */
- tree_iterator& operator ++()
- {
- _node = iterator->pre_increment(_node);
- return *this;
- }
- /*Description: post-increment operator. Behaviour depends on wrappes iterator. */
- const tree_iterator operator ++(int)
- {
- tree_iterator ret(*this);
- _node = iterator->pre_increment(_node);
- return ret;
- }
- /*Description: pre-decrement operator. Behaviour depends on wrappes iterator. */
- tree_iterator& operator --()
- {
- _node = iterator->pre_decrement(_node);
- return *this;
- }
- /*Description: post-decrement operator. Behaviour depends on wrappes iterator. */
- const tree_iterator operator --(int)
- {
- tree_iterator ret(*this);
- _node = iterator->pre_decrement(_node);
- return ret;
- }
- private:
- std::shared_ptr<_iterator_impl> iterator;
- _Node* _node;
- };
- //Node
- private:
- class _Node{
- /* Description:
- * This class provides the Nodes and the methods of the Nodes. */
- /* ---------------------------------------------------------------------------------------------------------
- *
- * CAUTION: The following class descriptions contain the descriptions of internal class _Node.
- * The descriptions provide more information about how the tree works in detail.
- *
- * Node:
- * Description:
- * The nodes of the tree, can be nodes and leafs.
- * Providing the storage for values of any kind.
- * Each node have to have a stored value.
- * Users should not be able to access this class to ensure correct linking between the nodes in the tree.
- *
- * Linking between the Nodes:
- * CAUTION: The parent of Root is Root
- *
- *
- * Parent (Node)
- * |
- * Parent
- * |
- * Siblings (Node)---Prev---(Node)---Next---(Node)
- * ______/ / \ \_______
- * / / \ \
- * Start First Last End
- * / / \ \
- * Children: (Sentinal-Start) (Node) ... (Node) (Sentinel-End)
- *
- *
- * Public methods:
- *
- * void extract(); Extract the Node. Deletes the links to relatives, ensure the siblings are correctly linked and
- * ensure the first/last-link of the parent is correct if necessary.
- * Does NOT delete the node from the children of the parent
- *
- * void erase(_Node* node); Erase the node from the childred of the parent. Make sure to call extract() after calling erase() to ensure correct linking
- *
- * std::shared_ptr<_Node> getPtr(); Returns a shared_ptr of this
- *
- * _Node* appendNode(const std::shared_ptr<_Node>& node); Internal function to append a node to children of this
- * _Node* insertAfter(const std::shared_ptr<_Node>& node); Internal function to append node to parent of this at position after this
- * _Node* insertPrevious(const std::shared_ptr<_Node>& node); Internal function to append node to parent of this at position previous to this
- *
- * void remove(); Internal function to remove this node.
- *
- * template<typename T> void setValue(T value); Set the stored value of type T
- * template<typename T> T getValue(); Get the stored value of type T
- * std::type_index getValueType(); Get the value type of the stored value
- *
- * Members:
- * std::shared_ptr<placeholder> Value = nullptr; Pointer to the stored value of this node
- *
- * Node* ParentNode = nullptr; Pointer to the parent node. If node is Root, it points to itself
- * Node* PrevNode = nullptr; Pointer to the previous siblings node
- * Node* NextNode = nullptr; Pointer to the next siblings node
- * Node* FirstNode = nullptr; Pointer to the first child node. Is NULL if no children exist.
- * Node* LastNode = nullptr; Pointer to the last child node. Is NULL if no children exist.
- * std::vector<std::shared_ptr<Node>> Children; Vector of Pointers of the owned children
- *
- * classes:
- * - placeholder Abstract class to provide an abstract type for storing values of any type
- * - holder Template class, provides the storage for values of any type
- *
- * ---------------------------------------------------------------------------------------------------------
- */
- friend class tree;
- private:
- class placeholder{
- /* Description:
- * Abstract class for providing an abstract type for any type of value */
- public:
- virtual ~placeholder() {}
- //Description: virtual function to get access to type of stored value
- virtual std::type_index getType() = 0;
- };
- template<typename T>
- class holder : public placeholder{
- /* Description:
- * Template class to provide the abillity to store values of any type, inherits from placeholder*/
- public:
- holder(T value) : Value(value) {}
- /* Description: Returns the type_index of the value which is stored
- * Parameters: None
- * Return: std::type_index */
- std::type_index getType();
- T Value;
- };
- private:
- //Members
- std::unique_ptr<placeholder> Value;
- _Node* ParentNode = nullptr;
- _Node* PrevNode = nullptr;
- _Node* NextNode = nullptr;
- _Node* FirstNode = nullptr;
- _Node* LastNode = nullptr;
- std::vector<std::shared_ptr<_Node>> Children;
- public:
- //structors
- _Node();
- template<typename T> _Node(T value);
- ~_Node();
- public:
- //Public Methods
- /* Description: Extract this node. See class description for details
- * Parameters: None
- * Return: None */
- void extract();
- /* Description: Erase node from children of this. If node is not a sentinel call extract() after erase() to ensure correct linking,
- * Parameters: None
- * Return: None */
- void erase(_Node* node);
- /* Description: Get the shared_ptr of this. The shared_ptr is get from the parent node.
- * Parameters: None
- * Return: shared_ptr of this */
- std::shared_ptr<_Node> getPtr();
- /* Description: Append a node to the children of this
- * Parameters: shared_ptr to appending node
- * Return: Pointer to appended node */
- _Node* appendNode(const std::shared_ptr<_Node>& node);
- /* Description: Append a node to the children of parent of this at position after this
- * Parameters: shared_ptr to appending node
- * Return: Pointer to appended node */
- _Node* insertAfter(const std::shared_ptr<_Node>& node);
- /* Description: Append a node to the children of parent of this at position previous to this
- * Parameters: shared_ptr to appending node
- * Return: Pointer to appended node */
- _Node* insertPrevious(const std::shared_ptr<_Node>& node);
- /* Description: Remove this node
- * Parameters: None
- * Return: None */
- void remove();
- /* Description: Template function to set the stored value of this node
- * Parameters: value with type T
- * Return: None */
- template<typename T> void setValue(T value);
- /* Description: Get the stored value of this node of type T
- * Parameters: None
- * Return: value of type T */
- template<typename T> T getValue();
- /* Description: Get the type of the stored value
- * Parameters: None
- * Return: type of the stored value as type_index */
- std::type_index getValueType();
- /* Description: Operator to set the stored value of this node
- * Parameters: value of type T
- * Return: None */
- template<typename T> void operator =(T value) { setValue(value); }
- private:
- //Helper functions
- /* Description: push new node to the list of children of this
- * Parameters: shared_ptr to the new child
- * Return: shared_ptr of the new child */
- void pushNewNode(const std::shared_ptr<_Node>& node);
- /* Description: Link to nodes as siblings. First is linked as the previous node of second and second is linked as the next of first.
- * Pointer can be NULL
- * Parameters: first: raw pointer to previous node, second: raw pointer to next node
- * Return: None */
- void linkNodes(_Node* first, _Node* second);
- }; //end class Node
- //Member
- private:
- std::shared_ptr<_Node> Root;
- std::shared_ptr<_iterator_impl> _node_iterator;
- std::shared_ptr<_iterator_impl> _const_node_iterator;
- std::shared_ptr<_iterator_impl> _reverse_node_iterator;
- std::shared_ptr<_iterator_impl> _const_reverse_node_iterator;
- std::shared_ptr<_iterator_impl> _child_iterator;
- std::shared_ptr<_iterator_impl> _const_child_iterator;
- std::shared_ptr<_iterator_impl> _reverse_child_iterator;
- std::shared_ptr<_iterator_impl> _const_reverse_child_iterator;
- }; //end class tree
- } // end namespace treeContainer
- /*--------------------------------------------------------------------------------------------------------------------------------------*/
- //Functions
- //Find value in tree
- template<typename T> treeContainer::tree::tree_iterator treeContainer::tree::find(const T& value)
- {
- return find(tree_iterator(_node_iterator, Root.get()), tree_iterator(_node_iterator, Root.get()), value);
- }
- //Find values in children of passed node
- template<typename T> treeContainer::tree::tree_iterator treeContainer::tree::find(const tree_iterator& start, const tree_iterator& end, const T& value)
- {
- tree_iterator ret(_node_iterator, start._node);
- bool found = false;
- ++ret;
- while(!found && ret != end){
- if(ret._node->getValueType() == typeid(T) && ret._node->getValue<T>() == value) found = true;
- else ++ret;
- }
- if(!found) ret._node = Root.get();
- return tree_iterator(ret);
- }
- //create a new node with value of type T and append it to the children of passed node
- template<typename T> treeContainer::tree::tree_iterator treeContainer::tree::createNode(const tree_iterator& parent, const T& value)
- {
- tree_iterator ret(_node_iterator, Root.get());
- if(parent._node == Root.get()) ret._node = Root->appendNode(std::make_shared<_Node>(value));
- else ret._node = parent._node->appendNode(std::make_shared<_Node>(value));
- return tree_iterator(ret);
- }
- /*--------------------------------------------------------------------------------------------------------------------------------------*/
- //class TreeNode
- //structors
- template<typename T> treeContainer::tree::_Node::_Node(T value)
- {
- setValue(value);
- }
- //functions
- //Store passed value of type T an store it in newly created holder
- template<typename T> void treeContainer::tree::_Node::setValue(T value)
- {
- Value = std::unique_ptr<placeholder>(new holder<T>(value));
- }
- //Returns the stored value of type T
- template<typename T> T treeContainer::tree::_Node::getValue()
- {
- return ((holder<T>*)Value.get())->Value;
- }
- //Returns the type of stored value as type_index
- template<typename T>
- std::type_index treeContainer::tree::_Node::holder<T>::getType()
- {
- return std::type_index(typeid(Value));
- }
- #endif // TREECONTAINER_H
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement