class Tree
{
public:
- typedef boost::shared_ptr<Tree> Ptr;
- typedef boost::weak_ptr<Tree> WeakPtr;
+ typedef boost::shared_ptr<Tree> Ptr;
+ typedef boost::weak_ptr<Tree> WeakPtr;
-private:
+ 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:
- T data;
+ 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;
+ }
- Tree() {}
- Tree(const T& item) :
- data(item) {}
+ inline static Ptr createNewNode()
+ {
+ Ptr newNode = Ptr(new Tree<T>());
+ }
- inline Ptr next() const
+ 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 prev() const
+ inline Ptr getPrevious() const
{
- Ptr parent = parent_.lock();
+ Ptr parent = getParent();
if (parent)
{
- if (parent->next_.get() == this)
+ if (parent->getNext().get() == this)
{
return parent;
}
else
{
- return prevSibling_.lock()->lastDescendant_.lock();
+ return prevSibling_.lock()->getLastDescendant();
}
}
return Ptr();
}
- inline Ptr firstChild() const
+ inline Ptr getFirstChild() const
{
- if (next_ && next_->parent_.lock().get() == this)
+ if (next_ && next_->getParent().get() == this)
{
return next_;
}
return Ptr();
}
- inline Ptr lastChild() const
+ inline Ptr getLastChild() const
{
- Ptr child = firstChild();
+ Ptr child = getFirstChild();
if (child)
{
return child;
}
- inline Ptr nextSibling() const
+ 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 = lastDescendant_.lock()->next_;
+ Ptr sibling = getLastDescendant()->getNext();
- if (sibling && sibling->parent_.lock() != parent_.lock())
+ if (sibling && sibling->getParent() != getParent())
{
return Ptr();
}
return sibling;
}
- inline Ptr prevSibling() const
+ inline Ptr getPreviousSibling() const
{
- Ptr parent = parent_.lock();
+ Ptr parent = getParent();
- if (parent && parent->next_.get() != this)
+ 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
{
};
- void insert()
+ 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();
}
};
projects / chaz / yoink / blobdiff