unique_tree.inl

C++ STL 中没有树形容器是最大的遗憾！ 还好高手总是能及时出现

		} else {
			it = oit.node()->insert(value); // child not an orphan.  insert child in parent orphan
			oit.node()->ordered_children.clear();
		}

		if ( it == oit.node()->end() ) // was child inserted as orphan?
			return associative_tree_type::end();  // no.  return proper end()
	} else {
		return associative_tree_type::end(); // couldn't find parent, and orphans not allowed
	}

	return it;
}


// find_deep(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>::find_deep(const stored_type& value) 
{
	tree_type tree_node(value);  // create seach node
	const typename std::set<tree_type*, deref_key_compare>::iterator desc_it = descendents.find(&tree_node);
	if (desc_it == descendents.end()) // node found in descendants?
		return associative_tree_type::end();  // no.  node not a descendant of this node

	// node is some type of descendant.  check if it's an immediate child
	typename associative_tree_type::iterator it = associative_tree_type::find(value);
	if ( it != associative_tree_type::end() )
		return it;

	// node not an immediate child.  
	it = associative_tree_type::begin();
	const typename associative_tree_type::iterator it_end = associative_tree_type::end();
	for ( ; it != it_end; ++it ) {  // iterate over children and call this fcn recursively
		const typename associative_tree_type::iterator grandchild_it = it.node()->find_deep(value);
		if ( grandchild_it != it.node()->end() ) 
			return grandchild_it;  // found it
	}

	return associative_tree_type::end();
}

// find_deep(const stored_type&) const
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>::const_child_iterator 
tcl::unique_tree<stored_type, node_compare_type, node_order_compare_type>::find_deep(const stored_type& value) const
{
	typename associative_tree_type::const_iterator it_end = associative_tree_type::end();
	tree_type tree_node(value);  // create seach node
	typename std::set<tree_type*, deref_key_compare>::const_iterator desc_it = descendents.find(&tree_node);
	if (desc_it == descendents.end())  // node found in descendants?
		return it_end;  // no.  node not a descendant of this node

	// node is some type of descendant.  check if it's an immediate child
	typename associative_tree_type::const_iterator it = associative_tree_type::find(value);
	if ( it != it_end )
		return it;

	// node not an immediate child.  
	it = associative_tree_type::begin();
	for ( ; it != it_end; ++it ) { // iterate over children and call this fcn recursively
		typename associative_tree_type::const_iterator grandchild_it = it.node()->find_deep(value);
		typename associative_tree_type::const_iterator grandchild_it_end = it.node()->end();
		if ( grandchild_it != grandchild_it_end )
			return grandchild_it;  // found it
	}

	return it_end;
}


// clear()
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>::clear()
{
	// create descendant remove set
	std::set<tree_type*, deref_key_compare> remove_set;
	remove_set.swap(descendents);  // get a copy of the descendants, and clear them

	tree_type* pParent = basic_tree_type::parent();
	while ( pParent != 0 ) {  // climb up to the root node
		std::set<tree_type*, deref_key_compare> dest_set;  // create a difference set
		std::set_difference( pParent->descendents.begin(), pParent->descendents.end(),
			remove_set.begin(), remove_set.end(), std::inserter(dest_set, dest_set.begin()), deref_key_compare() );
		pParent->descendents.swap(dest_set);  // and remove the deleted descendants
		pParent = pParent->parent();
	}

	associative_tree_type::clear(); // call base class operation
	ordered_children.clear();
	descendents.clear();

	if ( pOrphans ) { // if this is the root, clear orphans also
		pOrphans->clear();
	}
}


// inform_grandparents(tree_type*, 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>::inform_grandparents( tree_type* new_child, tree_type* pParent  )
{
	if ( pParent) {  // traverse to root, adding new child to descendants to every node
		pParent->descendents.insert(new_child);
		inform_grandparents(new_child, pParent->parent());
	}
}

// find_ordered(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>::ordered_iterator 
tcl::unique_tree<stored_type, node_compare_type, node_order_compare_type>::find_ordered(const stored_type& value) 
{
	tree_type tree_node(value);  // search node
	return ordered_iterator(ordered_children.find(&tree_node));
}

// find_ordered(const stored_type&) const 
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>::const_ordered_iterator 
tcl::unique_tree<stored_type, node_compare_type, node_order_compare_type>::find_ordered(const stored_type& value) const
{
	tree_type tree_node(value);  // search node
	return const_ordered_iterator(ordered_children.find(&tree_node));
}

// erase(const stored_type&)
template<typename stored_type, typename node_compare_type, typename node_order_compare_type>
bool tcl::unique_tree<stored_type, node_compare_type, node_order_compare_type>::
erase(const stored_type& value)
{
	const typename associative_tree_type::iterator it = find_deep(value);  // see if node is a descendant
	if ( it != associative_tree_type::end() ) {
		tree_type* const pParent = it.node()->parent();  // it is.  get it's parent
		tree_type* pAncestor = pParent;

		while ( pAncestor ) {  // update all ancestors of removed child
			pAncestor->descendents.erase(it.node());
			pAncestor = pAncestor->parent();
		}

		tree_type* const pNode = it.node();
		pParent->ordered_children.erase(pNode);
		dynamic_cast<associative_tree_type*>(pParent)->erase(*pNode->get()); // erase node

		return true;
	}

	return false;
}

// erase(iterator)
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>::erase(typename associative_tree<stored_type, unique_tree<stored_type, node_compare_type, node_order_compare_type>,  std::set<unique_tree<stored_type, node_compare_type, node_order_compare_type>*, unique_tree_deref_less<stored_type, node_compare_type, node_order_compare_type> > >::iterator it) 
{
	tree_type* pAncestor = this;

	while (pAncestor) { // update all ancestors of removed child
		pAncestor->descendents.erase(it.node());
		pAncestor = pAncestor->parent();
	}

	tree_type* pNode = it.node();
	ordered_children.erase(pNode);

	associative_tree_type::erase(*pNode->get()); 
}

// erase(iterator, iterator)
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>::erase(typename associative_tree<stored_type, unique_tree<stored_type, node_compare_type, node_order_compare_type>,  std::set<unique_tree<stored_type, node_compare_type, node_order_compare_type>*, unique_tree_deref_less<stored_type, node_compare_type, node_order_compare_type> > >::iterator it_beg, typename associative_tree<stored_type, unique_tree<stored_type, node_compare_type, node_order_compare_type>,  std::set<unique_tree<stored_type, node_compare_type, node_order_compare_type>*, unique_tree_deref_less<stored_type, node_compare_type, node_order_compare_type> > >::iterator it_end) 
{
	while (it_beg != it_end) {
		erase(it_beg++);
	}
}

// check_for_duplicate()
template<typename stored_type, typename node_compare_type, typename node_order_compare_type>
bool tcl::unique_tree<stored_type, node_compare_type, node_order_compare_type>::check_for_duplicate(const stored_type& value, const tree_type* pParent) const
{
	while ( pParent && !pParent->is_root() ) {  // find root node
		pParent = pParent->parent();
	}

	// check if node is root
	if (!(value < *pParent->get()) && !(*pParent->get() < value))
		return true;

	typename associative_tree_type::const_iterator it = pParent->find_deep(value);  // check if node is descendant of root
	typename associative_tree_type::const_iterator it_end = pParent->end();

	return ( it != it_end );  
}

// get_root()
template<typename stored_type, typename node_compare_type, typename node_order_compare_type>
const tcl::unique_tree<stored_type, node_compare_type, node_order_compare_type>*
tcl::unique_tree<stored_type, node_compare_type, node_order_compare_type>::get_root() const
{
	const tree_type* pParent = this;

	while ( pParent->parent() ) {  // traverse up to root
		pParent = pParent->parent();
	}

	return pParent;
}

// swap
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>::swap(tree_type& rhs)
{
	tree_type temp(*this);

	clear();
	*this = rhs;

	rhs.clear();
	rhs = temp;
}