Implement node moving functions.

The operations itself are O(1) since they just rearrange pointers.
However, the validation step is O(logN) due to a sanity check to prevent recursive trees.

git-svn-id: https://pugixml.googlecode.com/svn/trunk@1002 99668b35-9821-0410-8761-19e4c4f06640

2 files changed, 90 insertions, 14 deletions

diff --git a/src/pugixml.cpp b/src/pugixml.cpp
index b6559e7..cc19c8a 100644
--- a/src/pugixml.cpp
+++ b/src/pugixml.cpp
@@ -621,6 +621,8 @@ PUGI__NS_BEGIN
 			node->first_child = child;
 			child->prev_sibling_c = child;
 		}
+
+		child->next_sibling = 0;
 	}
 
 	inline void prepend_node(xml_node_struct* child, xml_node_struct* node)
@@ -641,38 +643,38 @@ PUGI__NS_BEGIN
 		node->first_child = child;
 	}
 
-	inline void insert_node_before(xml_node_struct* child, xml_node_struct* node)
+	inline void insert_node_after(xml_node_struct* child, xml_node_struct* node)
 	{
 		xml_node_struct* parent = node->parent;
 
 		child->parent = parent;
 
-		if (node->prev_sibling_c->next_sibling)
-			node->prev_sibling_c->next_sibling = child;
+		if (node->next_sibling)
+			node->next_sibling->prev_sibling_c = child;
 		else
-			parent->first_child = child;
+			parent->first_child->prev_sibling_c = child;
 
-		child->prev_sibling_c = node->prev_sibling_c;
-		child->next_sibling = node;
+		child->next_sibling = node->next_sibling;
+		child->prev_sibling_c = node;
 
-		node->prev_sibling_c = child;
+		node->next_sibling = child;
 	}
 
-	inline void insert_node_after(xml_node_struct* child, xml_node_struct* node)
+	inline void insert_node_before(xml_node_struct* child, xml_node_struct* node)
 	{
 		xml_node_struct* parent = node->parent;
 
 		child->parent = parent;
 
-		if (node->next_sibling)
-			node->next_sibling->prev_sibling_c = child;
+		if (node->prev_sibling_c->next_sibling)
+			node->prev_sibling_c->next_sibling = child;
 		else
-			parent->first_child->prev_sibling_c = child;
+			parent->first_child = child;
 
-		child->next_sibling = node->next_sibling;
-		child->prev_sibling_c = node;
+		child->prev_sibling_c = node->prev_sibling_c;
+		child->next_sibling = node;
 
-		node->next_sibling = child;
+		node->prev_sibling_c = child;
 	}
 
 	inline void remove_node(xml_node_struct* node)
@@ -3428,6 +3430,30 @@ PUGI__NS_BEGIN
 		return true;
 	}
 
+	PUGI__FN bool allow_move(const xml_node& parent, const xml_node& child)
+	{
+		// check that child can be a child of parent
+		if (!allow_insert_child(parent.type(), child.type()))
+			return false;
+
+		// check that node is not moved between documents
+		if (parent.root() != child.root())
+			return false;
+
+		// check that new parent is not in the child subtree
+		xml_node cur = parent;
+
+		while (cur)
+		{
+			if (cur == child)
+				return false;
+
+			cur = cur.parent();
+		}
+
+		return true;
+	}
+
 	PUGI__FN void recursive_copy_skip(xml_node& dest, const xml_node& source, const xml_node& skip)
 	{
 		assert(dest.type() == source.type());
@@ -4823,6 +4849,50 @@ namespace pugi
 		return result;
 	}
 
+	PUGI__FN xml_node xml_node::append_move(const xml_node& moved)
+	{
+		if (!impl::allow_move(*this, moved)) return xml_node();
+
+		impl::remove_node(moved._root);
+		impl::append_node(moved._root, _root);
+
+		return moved;
+	}
+
+	PUGI__FN xml_node xml_node::prepend_move(const xml_node& moved)
+	{
+		if (!impl::allow_move(*this, moved)) return xml_node();
+
+		impl::remove_node(moved._root);
+		impl::prepend_node(moved._root, _root);
+
+		return moved;
+	}
+
+	PUGI__FN xml_node xml_node::insert_move_after(const xml_node& moved, const xml_node& node)
+	{
+		if (!impl::allow_move(*this, moved)) return xml_node();
+		if (!node._root || node._root->parent != _root) return xml_node();
+		if (moved._root == node._root) return xml_node();
+
+		impl::remove_node(moved._root);
+		impl::insert_node_after(moved._root, node._root);
+
+		return moved;
+	}
+
+	PUGI__FN xml_node xml_node::insert_move_before(const xml_node& moved, const xml_node& node)
+	{
+		if (!impl::allow_move(*this, moved)) return xml_node();
+		if (!node._root || node._root->parent != _root) return xml_node();
+		if (moved._root == node._root) return xml_node();
+
+		impl::remove_node(moved._root);
+		impl::insert_node_before(moved._root, node._root);
+
+		return moved;
+	}
+
 	PUGI__FN bool xml_node::remove_attribute(const char_t* name_)
 	{
 		return remove_attribute(attribute(name_));
diff --git a/src/pugixml.hpp b/src/pugixml.hpp
index c15e5a1..69b2cb2 100644
--- a/src/pugixml.hpp
+++ b/src/pugixml.hpp
@@ -501,6 +501,12 @@ namespace pugi
 		xml_node insert_copy_after(const xml_node& proto, const xml_node& node);
 		xml_node insert_copy_before(const xml_node& proto, const xml_node& node);
 
+		// Move the specified node to become a child of this node. Returns moved node, or empty node on errors.
+		xml_node append_move(const xml_node& moved);
+		xml_node prepend_move(const xml_node& moved);
+		xml_node insert_move_after(const xml_node& moved, const xml_node& node);
+		xml_node insert_move_before(const xml_node& moved, const xml_node& node);
+
 		// Remove specified attribute
 		bool remove_attribute(const xml_attribute& a);
 		bool remove_attribute(const char_t* name);