/*******************************************************************************
Tree Container Library: Generic container library to store data in tree-like structures.
Copyright (c) 2006  Mitchel Haas

This software is provided 'as-is', without any express or implied warranty. 
In no event will the author be held liable for any damages arising from 
the use of this software.

Permission is granted to anyone to use this software for any purpose, 
including commercial applications, and to alter it and redistribute it freely, 
subject to the following restrictions:

1.	The origin of this software must not be misrepresented; 
you must not claim that you wrote the original software. 
If you use this software in a product, an acknowledgment in the product 
documentation would be appreciated but is not required.

2.	Altered source versions must be plainly marked as such, 
and must not be misrepresented as being the original software.

3.	The above copyright notice and this permission notice may not be removed 
or altered from any source distribution.

For complete documentation on this library, see http://www.datasoftsolutions.net
Email questions, comments or suggestions to mhaas@datasoftsolutions.net
*******************************************************************************/
#include <algorithm>

// copy constructor
template<typename stored_type, typename node_compare_type, typename node_order_compare_type>
tcl::unique_tree<stored_type, node_compare_type, node_order_compare_type>::unique_tree( const tree_type& rhs ) 
	: associative_tree_type(rhs), pOrphans(0), allowing_orphans(false)
{
	allowing_orphans = rhs.allowing_orphans;  // copy orphan flag

	if (rhs.pOrphans) { // orphans present?
		basic_tree_type::allocate_tree_type(pOrphans, tree_type());
		typename associative_tree_type::const_iterator it = rhs.pOrphans->begin();
		const typename associative_tree_type::const_iterator it_end = rhs.pOrphans->end();
		for ( ; it != it_end; ++it ) { // copy orphans
			pOrphans->insert(*it.node());
		}
	} else 
		pOrphans = 0;

	typename associative_tree_type::const_iterator it = rhs.begin();
	const typename associative_tree_type::const_iterator it_end = rhs.end();
	for ( ; it != it_end; ++it ) { // do deep copy by inserting children (and descendants)
		insert(*it.node());
	}
}

// assignment operator
template<typename stored_type, typename node_compare_type, typename node_order_compare_type>
tcl::unique_tree<stored_type, node_compare_type, node_order_compare_type>& 
tcl::unique_tree<stored_type, node_compare_type, node_order_compare_type>::operator = (const tree_type& rhs)
{
	if (!associative_tree_type::is_root()) // can assign only to root node
		return *this;

	if ( this == &rhs )  // check for self assignment
		return *this;

	clear();
	basic_tree_type::operator =(rhs); // base class operation

	allowing_orphans = rhs.allowing_orphans;

	if (rhs.pOrphans) { // orphans present?
		basic_tree_type::allocate_tree_type(pOrphans, tree_type());  // yes.  copy them
		typename associative_tree_type::const_iterator it = rhs.pOrphans->begin();
		const typename associative_tree_type::const_iterator it_end = rhs.pOrphans->end();
		for ( ; it != it_end; ++it ) {
			pOrphans->insert(*it.node());
		}
	} else 
		pOrphans = 0;

	typename associative_tree_type::const_iterator it = rhs.begin();
	const typename associative_tree_type::const_iterator it_end = rhs.end();
	for ( ; it != it_end; ++it ) {  // copy all children (and descendants)
		insert(*it.node());
	}

	return *this;
}


// set(const tree_type&)
template<typename stored_type, typename node_compare_type, typename node_order_compare_type>
void tcl::unique_tree<stored_type, node_compare_type, node_order_compare_type>::set(const tree_type& tree_obj)
{
	if ( !check_for_duplicate(*tree_obj.get(), this)) { // duplicate node exist in tree?
		// no.  OK to set this node
		basic_tree_type::set(*tree_obj.get());

		typename associative_tree_type::const_iterator it = tree_obj.begin(), it_end = tree_obj.end();
		for ( ; it != it_end; ++it ) { // insert any children
			insert(*it.node());
		}

		if ( tree_obj.pOrphans && allow_orphans() ) { // copy orphans if any present
			get_root()->pOrphans->set(*tree_obj.pOrphans );
		}  

	}
}


// insert(const stored_type&)
template<typename stored_type, typename node_compare_type, typename node_order_compare_type>
typename tcl::unique_tree<stored_type, node_compare_type, node_order_compare_type>::child_iterator 
tcl::unique_tree<stored_type, node_compare_type, node_order_compare_type>::insert(const stored_type& value) 
{ 
	const tree_type* const pRoot = get_root();
	if ( allow_orphans() && pRoot->pOrphans ) { // orphans present?
		// yes.  check orphans for child
		typename associative_tree_type::iterator oit = pRoot->pOrphans->find_deep(value);
		if ( oit != pRoot->pOrphans->end() ) { 
			// child is an orphan.  update orphan with new data
			oit.node()->set(stored_type(value));
			tree_type orphan;
			orphan.set(*oit.node());
			pRoot->pOrphans->erase(*oit);
			return insert(orphan);
		} 
	} 
	
	// stored obj doesn't already exist in an orphan
	if ( !check_for_duplicate(value, this)) { // check for duplication
		const typename associative_tree_type::iterator it = associative_tree_type::insert(value, this);
		ordered_children.insert(it.node());  // no duplicate exists.  insert new node
		inform_grandparents(it.node(), this );
		return it;
	} else
		return associative_tree_type::end(); // duplicate node exists.  don't insert

}

// insert(const tree_type&)
template<typename stored_type, typename node_compare_type, typename node_order_compare_type>
typename tcl::unique_tree<stored_type, node_compare_type, node_order_compare_type>::child_iterator 
tcl::unique_tree<stored_type, node_compare_type, node_order_compare_type>::insert(const tree_type& tree_obj )
{
	if ( tree_obj.pOrphans && allow_orphans() ) { // have orphans?
		get_root()->pOrphans->insert(*tree_obj.pOrphans ); // yes.  copy orphans
	}  

	// insert current node
	typename associative_tree_type::iterator base_it = insert(*tree_obj.get());

	if ( base_it == associative_tree_type::end() ) { // insert successful?
		// no.  but, the node may have existed here previously.  check if so
		base_it = associative_tree_type::find(*tree_obj.get()); 
	}

	if ( base_it != associative_tree_type::end() ) {  // node exist?
		typename associative_tree_type::const_iterator it = tree_obj.begin();
		const typename associative_tree_type::const_iterator it_end = tree_obj.end();

		// call this function recursively to insert children and descendants
		for ( ; it != it_end; ++it )
			base_it.node()->insert(*it.node());
	}
	return base_it;
}

// insert(const stored_type&, const stored_type&)
template<typename stored_type, typename node_compare_type, typename node_order_compare_type>
typename tcl::unique_tree<stored_type, node_compare_type, node_order_compare_type>::child_iterator 
tcl::unique_tree<stored_type, node_compare_type, node_order_compare_type>::insert( const stored_type& parent_obj, const stored_type& value)
{
	if ( !(parent_obj < *this->get()) && !(*this->get() < parent_obj) ) { // is this node the parent?	
		return insert(value);  // yes.  insert the node here.
	}

	// find parent node
	typename associative_tree_type::iterator it, it_parent = find_deep(parent_obj);

	const tree_type* const pRoot = get_root();
	if ( it_parent != associative_tree_type::end() ) {
		// found parent node, 
		if ( allow_orphans() && pRoot->pOrphans ) {
			// orphans present.  check orphans for child
			typename associative_tree_type::iterator oit = pRoot->pOrphans->find_deep(value);
			if ( oit != pRoot->pOrphans->end() ) {
				// child is an orphan.  update orphan with new data
				oit.node()->set(stored_type(value));
				tree_type orphan;
				orphan.set(*oit.node());
				pRoot->pOrphans->erase(*oit);
				it = it_parent.node()->insert(orphan);
			} else
				it = it_parent.node()->insert(value); // child not an orphan. inset child node in parent 
		} else {
			it = it_parent.node()->insert(value); // no orphans.  insert child node in parent
		}
		if ( it == it_parent.node()->end() ) // was node inserted successfully?
			return associative_tree_type::end(); // no.  return proper end()
	} else if (allow_orphans() ) { 
		// parent not found.  do we have orphans?
		if ( !pRoot->pOrphans ) {
			basic_tree_type::allocate_tree_type(pRoot->pOrphans, tree_type());  // no, instanciate them
		}

		typename associative_tree_type::iterator oit = pRoot->pOrphans->find_deep(parent_obj);

		// orphans contain parent?
		if ( oit == pRoot->pOrphans->end() ) {
			// no.  create parent in orphans
			oit = pRoot->pOrphans->insert(parent_obj);
			pRoot->pOrphans->ordered_children.clear();  // orphans need no ordered children
		} 

		typename associative_tree_type::iterator child_oit = pRoot->pOrphans->find_deep(value);
		if ( child_oit != pRoot->pOrphans->end() ) {
			// child is an orphan.  update orphan with new data
			child_oit.node()->set(stored_type(value));
			tree_type orphan;
			orphan.set(*child_oit.node());
			pRoot->pOrphans->erase(*child_oit);
			it = oit.node()->insert(orphan);
			oit.node()->ordered_children.clear();