/* -*- mode: C++; tab-width: 4; c-basic-offset: 4; -*- */

/* AbiSource Program Utilities
 * 
 * Copyright (C) 2003 Francis James Franklin <fjf@alinameridon.com>
 * Copyright (C) 2003 AbiSource, Inc.
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  
 * 02111-1307, USA.
 */
 
#include <cstdlib>
#include <cstring>

#include "ut_assert.h"
#include "ut_debugmsg.h"
#include "ut_exception.h"

#include "ut_Tree.h"

/* ************************************************************************************************************************
 * UT_Node
 * ************************************************************************************************************************
 */

UT_Node::UT_Node (NodeType nt) :
	m_type(nt),
	m_parent(0)
{
	// 
}

/* ************************************************************************************************************************
 * UT_Text_Node
 * ************************************************************************************************************************
 */

UT_Text_Node::UT_Text_Node (NodeType nt, const char * text) :
	UT_Node(nt),
	m_text(text)
{
	UT_ASSERT(nt != nt_element);
}

UT_Text_Node::UT_Text_Node (const char * text) :
	UT_Node(nt_text),
	m_text(text)
{
	// 
}

UT_Text_Node::~UT_Text_Node ()
{
	// 
}

bool UT_Text_Node::write (UT_UTF8String & cache, Writer & writer) const
{
	if (!writer.treeNodeWrite (this)) // whether the current node should be written at all
		return true;
	return text().byteLength () ? writer.treeNodeWrite (m_text) : true;
}

/* ************************************************************************************************************************
 * UT_CDATA_Node
 * ************************************************************************************************************************
 */

UT_CDATA_Node::UT_CDATA_Node (const char * text) :
	UT_Text_Node(nt_cdata,text)
{
	// 
}

bool UT_CDATA_Node::write (UT_UTF8String & cache, Writer & writer) const
{
	if (!writer.treeNodeWrite (this)) // whether the current node should be written at all
		return true;

	if (!text().byteLength ())
		return true;

	cache = "<![CDATA[";
	if (!writer.treeNodeWrite (cache))
		return false;

	if (!UT_Text_Node::write (cache, writer))
		return false;

	cache = "]]>";
	return writer.treeNodeWrite (cache);
}

/* ************************************************************************************************************************
 * UT_PI_Node
 * ************************************************************************************************************************
 */

UT_PI_Node::UT_PI_Node (const char * pi_target, const char * text) :
	UT_Text_Node(nt_pi,text),
	m_target(pi_target)
{
	// 
}

bool UT_PI_Node::write (UT_UTF8String & cache, Writer & writer) const
{
	if (!writer.treeNodeWrite (this)) // whether the current node should be written at all
		return true;

	if (!target().byteLength ())
		{
			UT_DEBUGMSG(("ut_Tree: Processing Instruction has no target!"));
			return false;
		}
	if (!text().byteLength ())
		return true;

	cache  = "<?";
	cache += target ();
	cache += " ";
	if (!writer.treeNodeWrite (cache))
		return false;

	if (!UT_Text_Node::write (cache, writer))
		return false;

	cache = "?>";
	return writer.treeNodeWrite (cache);
}

/* ************************************************************************************************************************
 * UT_Comment_Node
 * ************************************************************************************************************************
 */

UT_Comment_Node::UT_Comment_Node (const char * text) :
	UT_Text_Node(nt_comment,text)
{
	// 
}

bool UT_Comment_Node::write (UT_UTF8String & cache, Writer & writer) const
{
	if (!writer.treeNodeWrite (this)) // whether the current node should be written at all
		return true;

	if (!text().byteLength ())
		return true;

	cache = "<!--";
	if (!writer.treeNodeWrite (cache))
		return false;

	if (!UT_Text_Node::write (cache, writer))
		return false;

	cache = "-->";
	return writer.treeNodeWrite (cache);
}

/* ************************************************************************************************************************
 * UT_Default_Node
 * ************************************************************************************************************************
 */

UT_Default_Node::UT_Default_Node (const char * text) :
	UT_Text_Node(nt_default,text)
{
	// 
}

/* ************************************************************************************************************************
 * UT_Element
 * ************************************************************************************************************************
 */

const char * UT_Element::GBID = "UT_Element";

const char * UT_Element::GenericBaseID () const
{
	return UT_Element::GBID;
}

UT_Element::UT_Element (const char * element_tag, const char * element_id) :
	UT_Node(nt_element),
	m_tree(0),
	m_ElementTag(element_tag),
	m_ElementID(element_id),
	m_sibling_number(0),
	m_node(0),
	m_node_count(0),
	m_node_max(0),
	m_children(0),
	m_Attrs(0),
	m_Props(0),
	m_ref_count(0)
{
	// 
}

UT_Element::~UT_Element ()
{
	if (m_tree)
		{
			UT_DEBUGMSG(("ut_Tree: shouldn't need to deregister inside the destructor - what's wrong?\n"));
			m_tree->deregister (this);
		}

	while (m_node_count)
		deleteNode (m_node_count - 1);

	if (m_node) free (m_node);

	if (m_Attrs) delete m_Attrs;
	// if (m_Props) delete m_Props;
}

/* change the element's ID;
 * fails if the new element_id is already registered with the element's tree (if any)
 */
bool UT_Element::ElementID (const UT_UTF8String & element_id)
{
	if (m_ElementID == element_id)
		{
			return true;
		}
	if (tree () == 0)
		{
			m_ElementID = element_id;
			return true;
		}
	if (m_tree->reregister (this, element_id))
		{
			m_ElementID = element_id;
			return true;
		}
	return false;
}

/* adding/changing attributes
 */
bool UT_Element::insAttr (const char ** atts)
{
	if (!m_Attrs)
		{
			UT_TRY
				{
					m_Attrs = new UT_UTF8Hash;
				}
			UT_CATCH(...)
				{
					m_Attrs = 0;
				}
			if (!m_Attrs) return false;
		}
	return m_Attrs->ins (atts);
}

bool UT_Element::insAttr (const char * name, const char * value)
{
	if (!m_Attrs)
		{
			UT_TRY
				{
					m_Attrs = new UT_UTF8Hash;
				}
			UT_CATCH(...)
				{
					m_Attrs = 0;
				}
			if (!m_Attrs) return false;
		}
	return m_Attrs->ins (name, value);
}

void UT_Element::delAttr (const char * name)
{
	if (m_Attrs)
		m_Attrs->del (name);
}

const UT_Element::UT_Element * UT_Element::child (UT_uint32 index) const
{
	if (index >= m_children) return 0;

	UT_Element * element = 0;
	UT_uint32 sn = 0;

	for (UT_uint32 n = 0; n < m_node_count; n++)
		{
			UT_Node * node = m_node[n];
			if (node->type () == nt_element)
				if (sn++ == index)
					{
						element = static_cast<UT_Element *>(node);
						break;
					}
		}
	return element;
}

bool UT_Element::insertNode (UT_Node * node, UT_uint32 index, bool delete_if_fail)
{
	if (node == 0)
		return false;
	if (node->parent ())
		{
			UT_DEBUGMSG(("ut_Tree: you can't add this node here, it belongs to another element!\n"));
			return false; // don't delete the node!
		}
	if (!acceptNode (node, index))
		{
			UT_DEBUGMSG(("ut_Tree: this node is not permitted in this position!\n"));
			if (delete_if_fail) delete m_node;
			return false;
		}

	if ((index > m_node_count) || !grow ())
		{
			UT_DEBUGMSG(("ut_Tree: node out of range (or range out of nodes, perhaps)!\n"));
			if (delete_if_fail) delete m_node;
			return false;
		}
	if (node->type () == nt_element)
		{
			UT_Element * element = static_cast<UT_Element *>(node);
			if (tree ())
				{
					if (element->tree () == 0)
						{
							map (element); // TODO: check success/failure
						}
					else if (element->tree () != tree ())
						{
							UT_DEBUGMSG(("ut_Tree: this element belongs to a different tree!\n"));
							return false; // don't delete the node!
						}
					else if (element == tree()->root ())
						{
							UT_DEBUGMSG(("ut_Tree: huh? I'm not going to make my own root element a child of myself!\n"));
							return false; // don't delete the node!
						}
				}
			else if (element->tree ())
				{
					UT_DEBUGMSG(("ut_Tree: this element belongs to a different tree!\n"));
					return false; // don't delete the node!
				}

			/* NOTE: if ((tree () == 0) && (element->tree () == 0)) then disable element ID validation
			 */
		}

	if (index < m_node_count)
		memmove (m_node + index + 1, m_node + index, (m_node_count - index) * sizeof (UT_Node *));

	m_node[index] = node;
	m_node_count++;

	node->parent (this);

	if (node->type () == nt_element)
		relabelChildren ();

	return true;
}

bool UT_Element::deleteNode (UT_uint32 index)
{
	UT_Node * node = detachNode (index);
	if (node) delete node;
	return (node != 0);
}

UT_Node * UT_Element::detachNode (UT_uint32 index)
{
	if (index >= m_node_count) return 0;

	UT_Node * node = m_node[index];
	m_node_count--;

	if (index < m_node_count)
		memmove (m_node + index, m_node + index + 1, (m_node_count - index) * sizeof (UT_Node *));

	node->parent (0);

	if (node->type () == nt_element)
		{
			relabelChildren ();

			UT_Element * element = static_cast<UT_Element *>(node);
			element->relabel (0);
			element->deregister ();
		}
	return node;
}

/* this is called by insertNode() to check whether the supplied node is permitted
 * at the suggested index; UT_Element default implementation returns true always
 */
bool UT_Element::acceptNode (const UT_Node * node, UT_uint32 index) const
{
	return true;
}

bool UT_Element::shiftNode (UT_uint32 src_index, UT_Element * dest, UT_uint32 dest_index)
{
	if (!dest || (src_index >= m_node_count))
		return false;
	if (dest->tree () != tree ()) // hmm... can't shift to a different tree
		return false;

	UT_Node * node = m_node[src_index];

	if (dest == this) // copy within self... simple swap, then
		{
			if (dest_index >= m_node_count)
				return false;

			m_node[ src_index] = m_node[dest_index];
			m_node[dest_index] =   node;

			if ((node->type () == nt_element) || (m_node[src_index]->type () == nt_element))
				relabelChildren ();

			return true;
		}

	if (node->type () == nt_element)
		if (dest->descendsFrom (static_cast<UT_Element *>(node)))
			return false; // hmm... can't shift an element to a descendent of itself

	node->parent (0);

	if (!dest->insertNode (node, dest_index, false)) // erk! can't move it!
		{
			node->parent (this);
			return false;
		}

	m_node_count--;

	if (src_index < m_node_count)
		memmove (m_node + src_index, m_node + src_index + 1, (m_node_count - src_index) * sizeof (UT_Node *));

	if (node->type () == nt_element)
		relabelChildren ();

	return true;
}

bool UT_Element::map (UT_Tree * Tree, UT_Element * element)
{
	if (Tree == 0)
		{
			UT_ASSERT(Tree);
			return false;
		}

	UT_UTF8Hash map_Abi;
	UT_UTF8Hash map_Named;

	if (!element->setUniqueID (Tree, map_Abi, map_Named))
		{
			UT_DEBUGMSG(("ut_Tree: failed to map element & children for tree!\n"));
			return false;
		}
	element->remap_IDREFs (map_Abi, map_Named);

	if (!element->enregister (Tree))
		{
			UT_DEBUGMSG(("ut_Tree: failed to register element with tree!\n"));
			return false;
		}
	return true;
}

bool UT_Element::setUniqueID (UT_Tree * Tree, UT_UTF8Hash & map_Abi, UT_UTF8Hash & map_Named)
{
	if (m_tree)
		{
			UT_DEBUGMSG(("ut_Tree: this element belongs to a tree!\n"));
			UT_ASSERT(m_tree == 0);
			return false;
		}

	bool okay = true;

	/* problems arise if the same ID is used multiple times
	 */
	if (UT_ID_Generator::isInternal (m_ElementID))
		{
			UT_UTF8String old_EID(m_ElementID);

			m_ElementID = Tree->uniqueEID ();

			if (map_Abi[old_EID])
				{
					UT_DEBUGMSG(("ut_Tree: (warning) this new branch has overlapping IDs!\n"));
				}
			else
				{
					okay = map_Abi.ins (old_EID, m_ElementID);
				}
		}
	else if (m_ElementID.byteLength ())
		{
			UT_UTF8String old_EID(m_ElementID);

			while (Tree->lookupEID (m_ElementID) || map_Named[m_ElementID])
				{
					/* ID already in use; figure out a new one:
					 */
					m_ElementID = old_EID + (Tree->uniqueEID () + 3);
				}
			if (map_Named[old_EID])
				{
					UT_DEBUGMSG(("ut_Tree: (warning) this new branch has overlapping IDs!\n"));
				}
			else
				{
					okay = map_Named.ins (old_EID, m_ElementID);
				}
		}
	else
		{
			m_ElementID = Tree->uniqueEID ();
		}
	if (!okay)
		{
			UT_DEBUGMSG(("ut_Tree: unknown error while mapping element ID\n"));
			return false;
		}

	for (UT_uint32 n = 0; n < m_node_count; n++)
		{
			UT_Node * node = m_node[n];
			if (node->type () == nt_element)
				{
					UT_Element * element = static_cast<UT_Element *>(node);
					if (!element->setUniqueID (Tree, map_Abi, map_Named))
						{
							okay = false;
							break;
						}
				}
		}
	return okay;
}

void UT_Element::remap_IDREFs (UT_UTF8Hash & map_Abi, UT_UTF8Hash & map_Named)
{
	// empty implementation
}

bool UT_Element::enregister (UT_Tree * Tree)
{
	if (m_tree)
		{
			UT_DEBUGMSG(("ut_Tree: this element already belongs to a tree!\n"));
			return false;
		}
	if (!Tree->enregister (this))
		{
			UT_DEBUGMSG(("ut_Tree: failed to register element with new tree!\n"));
			return false;
		}
	m_tree = Tree;

	bool okay = true;

	for (UT_uint32 n = 0; n < m_node_count; n++)
		{
			UT_Node * node = m_node[n];
			if (node->type () == nt_element)
				{
					UT_Element * element = static_cast<UT_Element *>(node);
					if (!element->enregister (m_tree))
						{
							okay = false;
							break;
						}
				}
		}
	return okay;
}

void UT_Element::deregister ()
{
	if (!m_tree) return;

	m_tree->deregister (this);
	m_tree = 0;

	for (UT_uint32 n = 0; n < m_node_count; n++)
		{
			UT_Node * node = m_node[n];
			if (node->type () == nt_element)
				{
					UT_Element * element = static_cast<UT_Element *>(node);
					element->deregister ();
				}
		}
}

/* used by UT_Tree for deregistering root elements
 */
void UT_Element::deregister (UT_Element * element)
{
	if (element == 0)
		{
			UT_ASSERT(element);
			return;
		}
	if (element->tree () == 0)
		{
			UT_DEBUGMSG(("ut_Tree: element not registered with a tree!\n"));
			return;
		}
	if (element->parent ())
		{
			UT_DEBUGMSG(("ut_Tree: element not a root element! not deregistering...\n"));
			return;
		}
	if (element->tree()->root () == element)
		{
			UT_DEBUGMSG(("ut_Tree: element is root of tree! not deregistering...\n"));
			return;
		}
	element->deregister ();
}

bool UT_Element::descendsFrom (const UT_Element * element) const
{
	if (element == this)
		return true;
	return parent () ? parent()->descendsFrom (element) : false;
}

void UT_Element::relabelChildren ()
{
	m_children = 0;

	for (UT_uint32 n = 0; n < m_node_count; n++)
		{
			UT_Node * node = m_node[n];
			if (node->type () == nt_element)
				{
					UT_Element * element = static_cast<UT_Element *>(node);
					element->relabel (m_children++);
				}
		}
}

bool UT_Element::write (UT_UTF8String & cache, Writer & writer) const
{
	bool descend = true;

	if (!writer.treeNodeWrite (this, descend)) // whether the current node should be written at all
		{
			bool okay = true;

			if (descend)
				for (UT_uint32 n = 0; n < m_node_count; n++)
					if (!m_node[n]->write (cache, writer))
						{
							okay = false;
							break;
						}
			if (okay)
				writer.treeAscending (this);
			return okay;
		}

	if (!ElementTag().byteLength ())
		{
			UT_DEBUGMSG(("ut_Tree: element has no tag!"));
			return false;
		}

	cache  = "<";
	cache += ElementTag ();

	if (m_Attrs)
		if (m_Attrs->count ())
			{
				const UT_UTF8String * name  = 0;
				const UT_UTF8String * value = 0;

				UT_uint32 count = m_Attrs->count ();

				bool okay = true;

				for (UT_uint32 index = 0; index < count; index++)
					{
						m_Attrs->pair (index, name, value);

						if (name->byteLength () == 0)
							{
								UT_DEBUGMSG(("ut_Tree: attribute has no name! skipping...\n")); // [ or worse? ]
								continue;
							}

						cache += " ";
						cache += *name;
						cache += "=\"";

						if (value->byteLength () > 128) // watch out for things like data-URLs
							{
								if (!writer.treeNodeWrite (cache))
									{
										okay = false;
										break;
									}
								if (!writer.treeNodeWrite (*value))
									{
										okay = false;
										break;
									}
								cache = "\"";
								continue;
							}
						cache += *value;
						cache += "\"";
					}
				if (!okay) return false;
			}

	if (nodes ())
		{
			cache += ">";

			if (!writer.treeNodeWrite (cache))
				return false;

			bool okay = true;

			for (UT_uint32 n = 0; n < m_node_count; n++)
				if (!m_node[n]->write (cache, writer))
					{
						okay = false;
						break;
					}
			if (!okay) return false;

			cache  = "</";
			cache += ElementTag ();
			cache += ">";
		}
	else
		{
			cache = " />";
		}

	/* this is called *before* the end-tag is written
	 */
	writer.treeAscending (this);

	return writer.treeNodeWrite (cache);
}

bool UT_Element::grow ()
{
	if (m_node_count < m_node_max) return true;

	if (m_node == 0)
		{
			m_node = reinterpret_cast<UT_Node **>(malloc (8 * sizeof (UT_Node *)));
			if (m_node == 0) return false;
		}
	else
		{
			UT_Node ** more = reinterpret_cast<UT_Node **>(realloc (m_node, (m_node_max + 8) * sizeof (UT_Node *)));
			if (more == 0) return false;
			m_node = more;
		}
	m_node_max += 8;

	return true;
}

/* ************************************************************************************************************************
 * UT_ElementHash
 * ************************************************************************************************************************
 */

UT_ElementHash::UT_ElementHash (UT_uint32 increment) :
	UT_GenericUTF8Hash(increment)
{
	// 
}

UT_ElementHash::~UT_ElementHash ()
{
	clear ();
}

/* for easy sequential access of map members:
 */
bool UT_ElementHash::pair (UT_uint32 index, const UT_UTF8String *& element_id, const UT_Element *& element) const
{
	const UT_GenericBase * generic_value = 0;

	bool found = UT_GenericUTF8Hash::pair (index, element_id, generic_value);

	element = static_cast<const UT_Element *>(generic_value);
	return found;
}

/* returns false if no element with ID
 */
bool UT_ElementHash::del (const UT_UTF8String & element_id)
{
	UT_GenericBase * generic_value = 0;

	bool found = UT_GenericUTF8Hash::del (element_id, generic_value); // retrieve so not deleted

	return found;
}

/* ************************************************************************************************************************
 * UT_ID_Generator
 * ************************************************************************************************************************
 */

/* true if element_id matches "Abi_??????"
 */
bool UT_ID_Generator::isInternal (const UT_UTF8String & element_id)
{
	if (element_id.byteLength () == 10)
		return (strncmp (element_id.utf8_str (), "Abi_", 4) == 0);

	return false;
}

UT_ID_Generator::UT_ID_Generator () :
	i1(-1),
	i2(0),
	i3(0),
	i4(0),
	i5(0),
	i6(0)
{
	strcpy (buffer, "Abi_000000");
}

static const char * s_62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

const char * UT_ID_Generator::next ()
{
	if (++i1 < 62)
		{
			buffer[9] = s_62[i1];
			return buffer;
		}
	i1 = 0;
	buffer[9] = '0';

	if (++i2 < 62)
		{
			buffer[8] = s_62[i2];
			return buffer;
		}
	i2 = 0;
	buffer[8] = '0';

	if (++i3 < 62)
		{
			buffer[7] = s_62[i3];
			return buffer;
		}
	i3 = 0;
	buffer[7] = '0';

	if (++i4 < 62)
		{
			buffer[6] = s_62[i4];
			return buffer;
		}
	i4 = 0;
	buffer[6] = '0';

	if (++i5 < 62)
		{
			buffer[5] = s_62[i5];
			return buffer;
		}
	i5 = 0;
	buffer[5] = '0';

	if (++i6 < 62)
		{
			buffer[4] = s_62[i6];
			return buffer;
		}
	i6 = 0;
	buffer[4] = '0';

	return buffer;
}

/* ************************************************************************************************************************
 * UT_ElementFactory
 * ************************************************************************************************************************
 */

UT_Element * UT_ElementFactory::createElement (const char * element_tag, const char * element_id) const
{
	UT_Element * element = 0;

	UT_TRY
		{
			element = new UT_Element(element_tag,element_id);
		}
	UT_CATCH(...)
		{
			element = 0;
		}
	return element;
}

/* ************************************************************************************************************************
 * UT_Tree
 * ************************************************************************************************************************
 */

UT_Tree::UT_Tree () :
	m_parser(0),
	m_factory(0),
	m_current(0),
	m_cdata(false),
	m_valid(true),
	m_ElementID_Abi(256),
	m_ElementID_Named(32),
	m_root(0),
	m_node(0),
	m_node_count(0),
	m_node_max(0)
{
	// 
}

UT_Tree::~UT_Tree ()
{
	if (m_ElementID_Abi.count () || m_ElementID_Named.count ())
		{
			UT_DEBUGMSG(("ut_Tree: (warning) tree deleted while elements still registered!\n"));
			// UT_ASSERT((m_ElementID_Abi.count () == 0) && (m_ElementID_Named.count () == 0));
		}

	while (m_node_count)
		deleteNode (m_node_count - 1);

	if (m_node) free (m_node);
}

const UT_Element * UT_Tree::lookupEID (const UT_UTF8String & element_id)
{
	return UT_ID_Generator::isInternal (element_id) ? m_ElementID_Abi[element_id] : m_ElementID_Named[element_id];
}

bool UT_Tree::insertNode (UT_Node * node, UT_uint32 index, bool delete_if_fail)
{
	if (node == 0)
		return false;
	if (node->parent ())
		{
			UT_DEBUGMSG(("ut_Tree: you can't add this node here, it belongs to an element!\n"));
			return false; // don't delete the node!
		}

	bool valid_type = true;

	switch (node->type ())
		{
		case UT_Node::nt_text:
		case UT_Node::nt_cdata:
			valid_type = false;
			break;
		default:
			break;
		}
	if (!valid_type)
		{
			UT_DEBUGMSG(("ut_Tree: node not of valid type for tree-level insertion!\n"));
			if (delete_if_fail) delete m_node;
			return false;
		}

	if ((index > m_node_count) || !grow ())
		{
			UT_DEBUGMSG(("ut_Tree: node out of range (or range out of nodes, perhaps)!\n"));
			if (delete_if_fail) delete m_node;
			return false;
		}
	if (node->type () == UT_Node::nt_element)
		{
			if (m_root)
				{
					UT_DEBUGMSG(("ut_Tree: tree already has a root element!\n"));
					if (delete_if_fail) delete m_node;
					return false;
				}

			UT_Element * element = static_cast<UT_Element *>(node);
			if (element->tree ())
				{
					UT_DEBUGMSG(("ut_Tree: this element already belongs to a tree!\n"));
					return false; // don't delete the node!
				}
			UT_Element::map (this, element); // TODO: check success/failure

			m_root = element;
		}

	if (index < m_node_count)
		memmove (m_node + index + 1, m_node + index, (m_node_count - index) * sizeof (UT_Node *));

	m_node[index] = node;
	m_node_count++;

	return true;
}

bool UT_Tree::deleteNode (UT_uint32 index)
{
	UT_Node * node = detachNode (index);
	if (node) delete node;
	return (node != 0);
}

UT_Node * UT_Tree::detachNode (UT_uint32 index)
{
	if (index >= m_node_count) return 0;

	UT_Node * node = m_node[index];
	m_node_count--;

	if (index < m_node_count)
		memmove (m_node + index, m_node + index + 1, (m_node_count - index) * sizeof (UT_Node *));

	if (node->type () == UT_Node::nt_element)
		{
			m_root = 0; // necessary first step

			UT_Element * element = static_cast<UT_Element *>(node);
			UT_Element::deregister (element);
		}
	return node;
}

bool UT_Tree::grow ()
{
	if (m_node_count < m_node_max) return true;

	if (m_node == 0)
		{
			m_node = reinterpret_cast<UT_Node **>(malloc (8 * sizeof (UT_Node *)));
			if (m_node == 0) return false;
		}
	else
		{
			UT_Node ** more = reinterpret_cast<UT_Node **>(realloc (m_node, (m_node_max + 8) * sizeof (UT_Node *)));
			if (more == 0) return false;
			m_node = more;
		}
	m_node_max += 8;

	return true;
}

bool UT_Tree::write (UT_Node::Writer & writer) const
{
	if (!m_root)
		{
			UT_DEBUGMSG(("ut_Tree: attempt to write empty tree!\n"));
			UT_ASSERT(m_root);
			return false;
		}

	UT_UTF8String cache;

	return m_root->write (cache, writer);
}

/* fails if an element with the same ID has already been registered
 */
bool UT_Tree::enregister (const UT_Element * element)
{
	if (element == 0)
		{
			UT_ASSERT(element);
			return false;
		}
	if (element->tree ())
		{
			UT_DEBUGMSG(("ut_Tree: this element is already registered with a tree!\n"));
			return false;
		}
	if (lookupEID (element->ElementID ()))
		{
			UT_DEBUGMSG(("ut_Tree: an element with this ID has already been registered with this tree!\n"));
			return false;
		}

	bool okay;

	if (UT_ID_Generator::isInternal (element->ElementID ()))
		{
			okay = m_ElementID_Abi.ins (element->ElementID (), element);
		}
	else
		{
			okay = m_ElementID_Named.ins (element->ElementID (), element);
		}
	return okay;
}

/* fails if element has registered parent or is root element
 */
bool UT_Tree::deregister (const UT_Element * element)
{
	if (element == 0)
		{
			UT_ASSERT(element);
			return false;
		}
	if (element->tree () != this)
		{
			UT_DEBUGMSG(("ut_Tree: this element isn't registered with this tree!\n"));
			return false;
		}
	if (element == root ())
		{
			UT_DEBUGMSG(("ut_Tree: can't deregister root element!\n"));
			return false;
		}
	if (element->parent ())
		if (element->parent()->tree ())
			{
				UT_DEBUGMSG(("ut_Tree: can't deregister an element which still has a registered parent!\n"));
				return false;
			}

	const UT_Element * e = lookupEID (element->ElementID ());
	if (!e || (e != element))
		{
			UT_DEBUGMSG(("ut_Tree: this element isn't registered with this tree!\n"));
			return false;
		}

	bool okay;

	if (UT_ID_Generator::isInternal (element->ElementID ()))
		{
			okay = m_ElementID_Abi.del (element->ElementID ());
		}
	else
		{
			okay = m_ElementID_Named.del (element->ElementID ());
		}
	return okay;
}

/* attempts to deregister element, but this may fail silently; registers element with new ID
 * if reregistration succeeds, the element should change its ID to new_EID
 */
bool UT_Tree::reregister (const UT_Element * element, const UT_UTF8String & new_EID)
{
	if (element == 0)
		{
			UT_ASSERT(element);
			return false;
		}
	if (element->tree () != this)
		{
			UT_DEBUGMSG(("ut_Tree: this element is not registered with this tree!\n"));
			return false;
		}
	if (lookupEID (new_EID))
		{
			/* NOTE: this also catches the case of (element->ElementID () == new_EID)
			 */
			UT_DEBUGMSG(("ut_Tree: an element with this ID has already been registered with this tree!\n"));
			return false;
		}

	bool okay;

	if (UT_ID_Generator::isInternal (new_EID))
		{
			okay = m_ElementID_Abi.ins (new_EID, element);
		}
	else
		{
			okay = m_ElementID_Named.ins (new_EID, element);
		}
	if (!okay) return false;

	const UT_Element * e = lookupEID (element->ElementID ());
	if (!e || (e != element))
		{
			UT_DEBUGMSG(("ut_Tree: (warning) this element isn't registered with this tree!\n"));
		}
	else if (UT_ID_Generator::isInternal (element->ElementID ()))
		{
			m_ElementID_Abi.del (element->ElementID ());
		}
	else
		{
			m_ElementID_Named.del (element->ElementID ());
		}
	return true;
}

bool UT_Tree::parse (const char * buffer, UT_uint32 length, const UT_ElementFactory * factory, bool bIsBuffer)
{
	if (bIsBuffer)
		{
			UT_ASSERT(buffer && length);
			if ((buffer == 0) || (length == 0))
				return false;
		}
	else
		{
			UT_ASSERT( buffer);
			if ( buffer == 0)
				return false;
			UT_ASSERT(*buffer);
			if (*buffer == 0)
				return false;
		}

	if (nodes ())
		{
			UT_DEBUGMSG(("ut_Tree: this tree isn't empty; please start with a fresh tree when building with XML parser!\n"));
			UT_ASSERT(nodes () == 0);
			return false;
		}

	UT_XML parser;
	parser.setExpertListener (this);
	m_parser = &parser;

	UT_ElementFactory defaultFactory;
	if (factory)
		m_factory = factory;
	else
		m_factory = &defaultFactory;

	m_current = 0;
	m_cdata = false;
	m_valid = true;

	bool okay;
	if (bIsBuffer)
		okay = (UT_OK == parser.parse (buffer, length));
	else
		okay = (UT_OK == parser.parse (buffer)); // buffer is filename

	if (okay)
		okay = m_valid;

	m_parser = 0;
	m_factory = 0;
	m_current = 0;
	m_cdata = false;
	m_valid = true;

	// TODO: other initialization of tree?

	return okay;
}

/* implementation of UT_XML::ExpertListener
 */

void UT_Tree::StartElement (const XML_Char * name, const XML_Char ** atts)
{
	if (!m_parser) return;
	if (!m_current && m_root)
		{
			UT_DEBUGMSG(("ut_Tree: huh? 2nd root element?\n"));
			m_parser->stop ();
			m_valid = false;
			return;
		}
	UT_Element * element = m_factory->createElement (reinterpret_cast<const char *>(name), "");
	if (element == 0)
		{
			UT_DEBUGMSG(("ut_Tree: failed to create new element!\n"));
			m_parser->stop ();
			m_valid = false;
			return;
		}
	if (!element->insAttr (reinterpret_cast<const char **>(atts)))
		{
			UT_DEBUGMSG(("ut_Tree: failed to add attributes to new element!\n"));
			m_parser->stop ();
			m_valid = false;
			return;
		}
	if (m_current)
		{
			if (!m_current->appendNode (element))
				{
					UT_DEBUGMSG(("ut_Tree: failed to add new element to tree!\n"));
					m_parser->stop ();
					m_valid = false;
					return;
				}
		}
	else
		{
			if (!appendNode (element))
				{
					UT_DEBUGMSG(("ut_Tree: failed to add root element to tree!\n"));
					m_parser->stop ();
					m_valid = false;
					return;
				}
		}
	m_current = element;
}

void UT_Tree::EndElement (const XML_Char * name)
{
	if (!m_parser) return;
	if (!m_current)
		{
			UT_DEBUGMSG(("ut_Tree: huh? element end-tag while not in an element?\n"));
			m_parser->stop ();
			m_valid = false;
			return;
		}
	m_current = const_cast<UT_Element *>(m_current->parent ());
}

void UT_Tree::CharData (const XML_Char * buffer, int length)
{
	if (!m_parser) return;
	if ((buffer == 0) || (length == 0))
		{
			UT_ASSERT(buffer && length);
			return;
		}
	if (!m_root)
		{
			UT_DEBUGMSG(("ut_Tree: huh? character data outside of root element?\n"));
			m_parser->stop ();
			m_valid = false;
			return;
		}

	UT_Text_Node * node = 0;

	if (m_cdata)
		{
			UT_TRY
				{
					node = new UT_CDATA_Node(buffer);
				}
			UT_CATCH(...)
				{
					node = 0;
				}
			if (node == 0)
				{
					UT_DEBUGMSG(("ut_Tree: failed to create CDATA node!\n"));
				}
		}
	else
		{
			UT_TRY
				{
					node = new UT_Text_Node(buffer);
				}
			UT_CATCH(...)
				{
					node = 0;
				}
			if (node == 0)
				{
					UT_DEBUGMSG(("ut_Tree: failed to create character data node!\n"));
				}
		}
	if (node == 0)
		{
			m_parser->stop ();
			m_valid = false;
			return;
		}
	if (!m_current->appendNode (node))
		{
			UT_DEBUGMSG(("ut_Tree: failed to add character data (or CDATA) node to tree!\n"));
			m_parser->stop ();
			m_valid = false;
			return;
		}
}

void UT_Tree::ProcessingInstruction (const XML_Char * target, const XML_Char * data)
{
	if (!m_parser) return;

	UT_PI_Node * node = 0;

	UT_TRY
		{
			node = new UT_PI_Node(target,data);
		}
	UT_CATCH(...)
		{
			node = 0;
		}
	if (node == 0)
		{
			UT_DEBUGMSG(("ut_Tree: failed to create processing instruction node!\n"));
			m_parser->stop ();
			m_valid = false;
			return;
		}
	if (m_current)
		{
			if (!m_current->appendNode (node))
				{
					UT_DEBUGMSG(("ut_Tree: failed to add PI node to tree!\n"));
					m_parser->stop ();
					m_valid = false;
					return;
				}
		}
	else
		{
			if (!appendNode (node))
				{
					UT_DEBUGMSG(("ut_Tree: failed to add PI node to tree!\n"));
					m_parser->stop ();
					m_valid = false;
					return;
				}
		}
}

void UT_Tree::Comment (const XML_Char * data)
{
	if (!m_parser) return;

	UT_Comment_Node * node = 0;

	UT_TRY
		{
			node = new UT_Comment_Node(data);
		}
	UT_CATCH(...)
		{
			node = 0;
		}
	if (node == 0)
		{
			UT_DEBUGMSG(("ut_Tree: failed to create comment node!\n"));
			m_parser->stop ();
			m_valid = false;
			return;
		}
	if (m_current)
		{
			if (!m_current->appendNode (node))
				{
					UT_DEBUGMSG(("ut_Tree: failed to add comment to tree!\n"));
					m_parser->stop ();
					m_valid = false;
					return;
				}
		}
	else
		{
			if (!appendNode (node))
				{
					UT_DEBUGMSG(("ut_Tree: failed to add comment to tree!\n"));
					m_parser->stop ();
					m_valid = false;
					return;
				}
		}
}

void UT_Tree::StartCdataSection ()
{
	if (!m_parser) return;
	m_cdata = true;
}

void UT_Tree::EndCdataSection ()
{
	if (!m_parser) return;
	m_cdata = false;
}

void UT_Tree::Default (const XML_Char * buffer, int length)
{
	if (!m_parser) return;

	UT_Default_Node * node = 0;

	UT_TRY
		{
			node = new UT_Default_Node(buffer);
		}
	UT_CATCH(...)
		{
			node = 0;
		}
	if (node == 0)
		{
			UT_DEBUGMSG(("ut_Tree: failed to create default node!\n"));
			m_parser->stop ();
			m_valid = false;
			return;
		}
	if (m_current)
		{
			UT_DEBUGMSG(("ut_Tree: (warning) adding default node inside tree!\n"));

			if (!m_current->appendNode (node))
				{
					UT_DEBUGMSG(("ut_Tree: failed to add default node to tree!\n"));
					m_parser->stop ();
					m_valid = false;
					return;
				}
		}
	else
		{
			if (!appendNode (node))
				{
					UT_DEBUGMSG(("ut_Tree: failed to add default node to tree!\n"));
					m_parser->stop ();
					m_valid = false;
					return;
				}
		}
}