X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Fyoink;a=blobdiff_plain;f=src%2FMoof%2FTree.hh;fp=src%2FMoof%2FTree.hh;h=0000000000000000000000000000000000000000;hp=b3f6a97c22dadf125c1efd79efaaef48883ad2a4;hb=329a48e4c4c2f5f2904b913938fc53154c48b825;hpb=72d4af22710317acffab861421c4364b1780b6fe diff --git a/src/Moof/Tree.hh b/src/Moof/Tree.hh deleted file mode 100644 index b3f6a97..0000000 --- a/src/Moof/Tree.hh +++ /dev/null @@ -1,341 +0,0 @@ - -/******************************************************************************* - - 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 -#include - - -namespace Mf { - - -template -class Tree -{ -public: - typedef boost::shared_ptr Ptr; - typedef boost::weak_ptr 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()); - } - - inline static Ptr createNewNode(const T& item) - { - Ptr newNode = Ptr(new Tree(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: *************************************************/ -