+++ /dev/null
-
-/*******************************************************************************
-
- Copyright (c) 2009, Charles McGarvey
- All rights reserved.
-
- Redistribution and use in source and binary forms, with or without
- modification, are permitted provided that the following conditions are met:
-
- * Redistributions of source code must retain the above copyright notice,
- this list of conditions and the following disclaimer.
- * Redistributions in binary form must reproduce the above copyright notice,
- this list of conditions and the following disclaimer in the documentation
- and/or other materials provided with the distribution.
-
- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
- AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
- FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
- SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
- CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
- OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-
-*******************************************************************************/
-
-#ifndef _MOOF_TREE_HH_
-#define _MOOF_TREE_HH_
-
-#include <boost/shared_ptr.hpp>
-#include <boost/weak_ptr.hpp>
-
-
-namespace Mf {
-
-
-template <typename T>
-class Tree
-{
-public:
- typedef boost::shared_ptr<Tree> Ptr;
- typedef boost::weak_ptr<Tree> WeakPtr;
-
- T node;
-
-protected:
- WeakPtr parent_;
- WeakPtr prevSibling_;
- Ptr next_;
- WeakPtr lastDescendant_;
-
- inline static void init(Ptr itself)
- {
- itself->prevSibling_ = itself;
- itself->lastDescendant_ = itself;
- }
-
- Tree() {}
-
- explicit Tree(const T& item) :
- node(item) {}
-
-public:
-
- inline void print() const
- {
- std::cout << "==================" << std::endl;
- std::cout << " Node: " << getThis() << std::endl;
- std::cout << " Parent: " << parent_.lock() << std::endl;
- std::cout << " PrevSib: " << prevSibling_.lock() << std::endl;
- std::cout << " Next: " << next_ << std::endl;
- std::cout << "LastDesc: " << lastDescendant_.lock() << std::endl;
- //std::cout << " Value: " << node << std::endl;
- std::cout << "==================" << std::endl;
- }
-
- inline static Ptr createNewNode()
- {
- Ptr newNode = Ptr(new Tree<T>());
- }
-
- inline static Ptr createNewNode(const T& item)
- {
- Ptr newNode = Ptr(new Tree<T>(item));
- init(newNode);
- return newNode;
- }
-
- inline Ptr getNext() const
- {
- return next_;
- }
-
- inline Ptr getPrevious() const
- {
- Ptr parent = getParent();
-
- if (parent)
- {
- if (parent->getNext().get() == this)
- {
- return parent;
- }
- else
- {
- return prevSibling_.lock()->getLastDescendant();
- }
- }
-
- return Ptr();
- }
-
- inline Ptr getFirstChild() const
- {
- if (next_ && next_->getParent().get() == this)
- {
- return next_;
- }
-
- return Ptr();
- }
-
- inline Ptr getLastChild() const
- {
- Ptr child = getFirstChild();
-
- if (child)
- {
- child = child->prevSibling_.lock();
- }
-
- return child;
- }
-
- inline Ptr getChild(int index) const
- {
- Ptr child = getFirstChild();
-
- for (int i = 0; child && i < index; ++i)
- {
- child = child->getNextSibling();
- }
-
- return child;
- }
-
- inline Ptr getNextSibling() const
- {
- Ptr sibling = getLastDescendant()->getNext();
-
- if (sibling && sibling->getParent() != getParent())
- {
- return Ptr();
- }
-
- return sibling;
- }
-
- inline Ptr getPreviousSibling() const
- {
- Ptr parent = getParent();
-
- if (parent && parent->getNext().get() != this)
- {
- return prevSibling_.lock();
- }
-
- return Ptr();
- }
-
- inline Ptr getParent() const
- {
- return parent_.lock();
- }
-
- inline Ptr getLastDescendant() const
- {
- return lastDescendant_.lock();
- }
-
- inline Ptr getThis() const
- {
- if (next_)
- {
- return next_->getPrevious();
- }
-
- return getLastDescendant();
- }
-
- inline bool isRoot() const
- {
- return getParent().get() == 0;
- }
-
- inline bool isLeaf() const
- {
- return getLastDescendant().get() == this;
- }
-
- inline bool isDescendantOf(Ptr ancestor) const
- {
- Ptr temp = getParent();
-
- while (temp)
- {
- if (temp.get() == this) return true;
-
- temp = temp->getParent();
- }
-
- return false;
- }
-
-
- class Iterator
- {
- Ptr current;
-
- public:
-
- };
-
-
- void addChild(Ptr subtree)
- {
- //WeakPtr parent_;
- //WeakPtr prevSibling_;
- //Ptr next_;
- //WeakPtr lastDescendant_;
-
- subtree->remove();
-
- Ptr firstChild = getFirstChild();
- Ptr lastChild = getLastChild();
- Ptr nextSibling = getNextSibling();
- Ptr lastDescendant = getLastDescendant();
- Ptr newLastDescendant = subtree->getLastDescendant();
- Ptr parent = getThis();
-
- // 1. If parent is leaf, set parent.next to subtree.
-
- if (isLeaf())
- {
- next_ = subtree;
- }
-
- // 2. Set parent.last_descendant to subtree.last_descendant.
-
- Ptr temp = parent;
- while (temp && temp->getLastDescendant() == lastDescendant)
- {
- temp->lastDescendant_ = newLastDescendant;
- temp = temp->getParent();
- }
-
- // 3. Set subtree.parent to parent.
-
- subtree->parent_ = parent;
-
- // 4. Set parent.first_child.prev_sibling to subtree.
-
- if (firstChild)
- {
- firstChild->prevSibling_ = subtree;
- }
-
- // 5. Set subtree.prev_sibling to parent.last_child.
- // 6. Set parent.last_child.last_descendant.next to subtree.
-
- if (lastChild)
- {
- subtree->prevSibling_ = lastChild;
- lastChild->getLastDescendant()->next_ = subtree;
- }
- else
- {
- subtree->prevSibling_ = subtree;
- }
-
- // 7. Set subtree.last_descendant.next to parent.next_sibling.
-
- if (nextSibling)
- {
- subtree->getLastDescendant()->next_ = nextSibling;
- }
- }
-
- void remove()
- {
- Ptr parent = getParent();
- Ptr prevSibling = getPreviousSibling();
- Ptr nextSibling = getNextSibling();
- Ptr lastDescendant = getLastDescendant();
- Ptr previous = getPrevious();
-
- Ptr newLastDescendant;
-
- // 1. Fix last descendant of each direct ancestor.
-
- if (prevSibling) newLastDescendant = prevSibling->getLastDescendant();
- else newLastDescendant = parent;
-
- Ptr temp = parent;
- while (temp && temp->getLastDescendant() == lastDescendant)
- {
- temp->lastDescendant_ = newLastDescendant;
- temp = temp->getParent();
- }
-
- // 2. Fix next of previous.
-
- if (previous)
- {
- previous->next_ = nextSibling;
- }
-
- // 3. Fix the previous sibling of next sibling.
-
- if (nextSibling)
- {
- nextSibling->prevSibling_ = prevSibling;
- }
-
- // 4. Once detached, the subtree root has no parent or siblings.
-
- parent_.reset();
- prevSibling_ = getThis();
- }
-
-};
-
-
-} // namespace Mf
-
-#endif // _MOOF_TREE_HH_
-
-/** vim: set ts=4 sw=4 tw=80: *************************************************/
-
projects / chaz / yoink / blobdiff