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=b3f6a97c22dadf125c1efd79efaaef48883ad2a4;hp=2b5fdb8baf769bcebba4460bdd67e3e4e7d40e01;hb=72d4af22710317acffab861421c4364b1780b6fe;hpb=493ddb59a8620b49dfa0ff62ce93395ebfd02e86

diff --git a/src/Moof/Tree.hh b/src/Moof/Tree.hh
index 2b5fdb8..b3f6a97 100644
--- a/src/Moof/Tree.hh
+++ b/src/Moof/Tree.hh
@@ -40,50 +40,81 @@ template <typename T>
 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_;
 		}
@@ -91,9 +122,9 @@ public:
 		return Ptr();
 	}
 
-	inline Ptr lastChild() const
+	inline Ptr getLastChild() const
 	{
-		Ptr child = firstChild();
+		Ptr child = getFirstChild();
 
 		if (child)
 		{
@@ -103,11 +134,23 @@ public:
 		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();
 		}
@@ -115,11 +158,11 @@ public:
 		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();
 		}
@@ -127,6 +170,50 @@ public:
 		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
 	{
@@ -137,12 +224,110 @@ public:
 	};
 
 
-	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();
 	}
 
 };