xsec/utils/XSECXPathNodeList.cpp - santuario-cpp - Git at Google

 /**
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements. See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership. The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License. You may obtain a copy of the License at
  *
  * http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing,
  * software distributed under the License is distributed on an
  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  * KIND, either express or implied. See the License for the
  * specific language governing permissions and limitations
  * under the License.
  */

 /*
  * XSEC
  *
  * XSECXPathNodeList := A structure to hold node lists from XPath
  * evaluations
  *
  * $Id$
  *
  */

 // XSEC

 #include <xsec/utils/XSECXPathNodeList.hpp>
 #include <xsec/framework/XSECError.hpp>

 #include <string.h>

 XERCES_CPP_NAMESPACE_USE

 // --------------------------------------------------------------------------------
 //           Constructors and Destructors.
 // --------------------------------------------------------------------------------

 XSECXPathNodeList::XSECXPathNodeList(unsigned int initialSize) {

 	m_num = 0;
 	mp_tree = NULL;

 }

 XSECXPathNodeList::XSECXPathNodeList(const XSECXPathNodeList &other) {

 	m_num = other.m_num;
 	mp_tree = copy_tree(other.mp_tree);
 	mp_current = NULL;

 }

 XSECXPathNodeList::~XSECXPathNodeList() {

 	// Delete all the elements in the node list
 	delete_tree(mp_tree);

 }

 XSECXPathNodeList & XSECXPathNodeList::operator= (const XSECXPathNodeList & toCopy) {

 	// For now simply delete the old list and set with the new
 	// Large overhead as we call other functions, but simplest way to
 	// implement for now

 	mp_tree = copy_tree(toCopy.mp_tree);
 	m_num = toCopy.m_num;
 	mp_current = NULL;
 	return *this;

 }

 // --------------------------------------------------------------------------------
 //           Utility Functions.
 // --------------------------------------------------------------------------------

 XSECXPathNodeList::btn * XSECXPathNodeList::findNodeIndex(const DOMNode *n) const {

 	btn * t = mp_tree;

 	while (t != NULL && t->v != n) {

 		if (n > t->v)
 			t = t->r;
 		else
 			t = t->l;
 	}

 	return t;

 }

 void XSECXPathNodeList::delete_tree(btn * t) {

 	if (t == NULL)
 		return;

 	btn * parent, * n;

 	n = t;
 	while (n != NULL) {

 		if (n->l)
 			n = n->l;
 		else if (n->r)
 			n = n->r;

 		else {
 			parent = n->p;
 			if (parent != NULL) {
 				if (parent->l == n)
 					parent->l = NULL;
 				else
 					parent->r = NULL;
 			}
 			// Delete this node
 			delete n;
 			n = parent;
 		}
 	}

 }

 XSECXPathNodeList::btn * XSECXPathNodeList::copy_tree(btn * t) const {

 	if (t == NULL)
 		return NULL;

 	btn * n, *c, *cp, *ret;
     c = cp = NULL;

 	n = t;
 	bool create = true;
 	ret = NULL;
 	while (n != NULL) {

 		if (create) {
 			XSECnew(c, btn);
 			c->l = NULL;
 			c->r = NULL;
 			c->v = n->v;

 			// R we at top?
 			if (ret == NULL) {
 				ret = c;
 				c->p = NULL;
 				cp = NULL;
 			}

 			else {
 				c->p = cp;
 				if (cp != NULL) {
 					if (n->p->l == n)
 						cp->l = c;
 					else
 						cp->r = c;
 				}
 			}
 		}

 		// Go down!
 		if (c->l == NULL && n->l != NULL) {
 			cp = c;
 			n = n->l;
 			create = true;
 		}
 		else if (c->r == NULL && n->r != NULL) {
 			cp = c;
 			n = n->r;
 			create = true;
 		}
 		else {

 			// Go Back Up!
 			n = n->p;
 			c = cp;
 			if (cp != NULL)
 				cp = cp->p;
 			create = false;
 		}
 	}

 	return ret;
 }


 // --------------------------------------------------------------------------------
 //           Adding and Deleting Nodes.
 // --------------------------------------------------------------------------------

 long XSECXPathNodeList::balance_count(btn * t) const {

 	if (t == NULL)
 		return 0;

 	long r = (t->r == NULL ? 0 : t->r->h);
 	long l = (t->l == NULL ? 0 : t->l->h);

 	return r - l;

 }

 long XSECXPathNodeList::calc_height(btn * t) {

 	if (t == NULL)
 		return 0;
 	if (t->l == NULL) {
 		if (t->r == NULL)
 			return 1;
 		return t->r->h + 1;
 	}
 	else {
 		if (t->r == NULL)
 			return t->l->h + 1;
 	}

 	return ((t->l->h > t->r->h ? t->l->h : t->r->h) + 1);
 }

 void XSECXPathNodeList::rotate_right(btn * t) {

 	// Rotate me right!
 	btn * lc = t->l;

 	// First - are we at the root?
 	if (t == mp_tree) {
 		lc->p = NULL;
 		mp_tree = lc;
 	}
 	else {
 		if (t->p->l == t) {
 			t->p->l = lc;
 		}
 		else {
 			t->p->r = lc;
 		}

 		lc->p = t->p;
 	}

 	// Do the rotate
 	t->l = lc->r;
 	if (t->l)
 		t->l->p = t;
 	lc->r = t;
 	t->p = lc;

 	// Recalculate heights
 	lc = t;
 	while (lc != NULL) {
 		lc->h = calc_height(lc);
 		lc = lc->p;
 	}

 }


 void XSECXPathNodeList::rotate_left(btn * t) {

 	// Rotate me left!
 	btn * rc = t->r;

 	// First - are we at the root?
 	if (t == mp_tree) {
 		rc->p = NULL;
 		mp_tree = rc;
 	}
 	else {
 		if (t->p->r == t) {
 			t->p->r = rc;
 		}
 		else {
 			t->p->l = rc;
 		}

 		rc->p = t->p;
 	}

 	// Do the rotate
 	t->r = rc->l;
 	if (t->r)
 		t->r->p = t;
 	rc->l = t;
 	t->p = rc;

 	// Recalculate heights
 	rc = t;
 	while (rc != NULL) {
 		rc->h = calc_height(rc);
 		rc = rc->p;
 	}

 }

 void XSECXPathNodeList::addNode(const DOMNode *n) {

 	btn * v;

 	if (m_num == 0) {
 		XSECnew(mp_tree, btn);
 		mp_tree->l = mp_tree->r = NULL;
 		mp_tree->v = n;
 		mp_tree->p = NULL;
 		mp_tree->h = 1;
 		m_num = 1;
 		return;
 	}

 	// Find the node
 	btn * t = mp_tree;
 	btn * last = NULL;

 	while (t != NULL && t->v != n) {
 		last = t;
 		if (n > t->v)
 			t = t->r;
 		else
 			t = t->l;
 	}

 	if (t != NULL)
 		// Node already exists in tree!
 		return;

 	// Work out the insertion.
 	XSECnew(v, btn);
 	v->v = n;
 	v->r = v->l = NULL;
 	v->h = 1;
 	v->p = last;

 	// Determine on which leg to place the new value
 	if (n > last->v)
 		last->r = v;
 	else
 		last->l = v;

 	// Recalculate heights
 	t = last;
 	long newh;
 	while (t != NULL) {
 		newh = calc_height(t);
 		if (newh > t->h) {
 			t->h = newh;
 			t = t->p;
 		}
 		else
 			// If the height is the same here, then nothing will have changed above
 			t = NULL;
 	}

 	// Rebalance!

 	t = last;
 	while (t != NULL) {
 		long bal = balance_count(t);
 		long balrc = balance_count(t->r);
 		long ballc = balance_count(t->l);

 		// Case 1 - Balance is OK
 		if (bal <= 1 && bal >= -1) {
 			// Do nothing!
 		}

 		// Case 2a - Balance is -2 and LC = -1
 		else if (bal == -2 && ballc == -1) {

 			// Rotate current node right
 			rotate_right(t);
 		}
 		// Or balance is +2 and RC = +1
 		else if (bal == 2 && balrc  == 1) {

 			// Rotate current node left
 			rotate_left(t);
 		}
 		// Case 2b = Balance is -2 and LC = +1
 		else if (bal == -2 && ballc == 1) {

 			// Double Right rotation
 			rotate_left(t->l);
 			rotate_right(t);
 		}

 		else {
 			rotate_right(t->r);
 			rotate_left(t);

 		}

 		t = t->p;

 	}

 }

 void XSECXPathNodeList::removeNode(const DOMNode *n) {

 	btn * t, * last;
     last = NULL;
 	btn * i = findNodeIndex(n);

 	if (i == NULL)
 		// Not found!
 		return;

 	// Delete from tree
 	if (i == mp_tree) {
 		// Bugger - we are at the top of the tree

 		// OK - No children?
 		if (i->l == NULL && i->r == NULL) {
 			// WooHoo!  Easy!
 			delete mp_tree;
 			mp_tree = NULL;
 		}

 		// One Child?
 		if (i->l != NULL && i->r == NULL) {

 			// WooHoo! Easy!
 			mp_tree = i->l;
 			mp_tree->p = NULL;
 			delete i;
 		}
 		if (i->r != NULL && i->l == NULL) {

 			// WooHoo! Easy!
 			mp_tree = i->r;
 			mp_tree->p = NULL;
 			delete i;
 		}

 		// Oh dear = we have two children and now some heartache
 		if (i->r->l == NULL && i->r->r == NULL) {

 			// No subtree on right hand side.
 			mp_tree = mp_tree->l;
 			mp_tree->p = NULL;
 			t = mp_tree->r;
 			last = mp_tree;
 			while (t != NULL) {
 				last = t;
 				if (i->r->v < t->v)
 					t = t->l;
 				else
 					t = t->r;
 			}

 			if (i->r->v < last->v) {
 				last->l = i->r;
 				i->r->p = last;
 			}
 			else {
 				last->r = i->r;
 				i->r->p = last;
 			}
 		}

 		else {

 			// Need to find the "in-order" successor
 			t = i->r;

 			while (t != NULL) {
 				last = t;
 				t=t->l;
 			}

 			if (last == i->r) {
 				// can't have been a left hand leg on the next node!)
 				last->l = i->l;
 				if (last->l != NULL)
 					last->l->p = last;

 				mp_tree = last;
 				last->p = NULL;

 				delete i;
 			}
 			else {

 				// OK - Last is now the next biggest node, and it doesn;t
 				// have anything on it's left (otherwise there would be something smaller)

 				last->p->l = last->r;
 				last->r->p = last->p;
 				last->l = i->l;
 				last->r = i->r;
 				if (last->r != NULL)
 					last->r->p = last;
 				if (last->l != NULL)
 					last->l->p = last;

 				mp_tree = last;
 				last->p = NULL;

 				delete i;

 			}
 		}
 	}

 	else {

 		/* i != mp_tree */
 		// OK - No children?
 		if (i->l == NULL && i->r == NULL) {
 			// WooHoo!  Easy!
 			if (i->p->l == i)
 				i->p->l = NULL;
 			else
 				i->p->r = NULL;

 			delete i;
 		}

 		// One Child?
 		if (i->l != NULL && i->r == NULL) {

 			// WooHoo! Easy!
 			if (i->p->l == i) {
 				i->p->l = i->l;
 				i->l->p = i->p;
 			}
 			else {
 				i->p->r = i->l;
 				i->r->p = i->p;
 			}
 			delete i;
 		}
 		if (i->r != NULL && i->l == NULL) {

 			// WooHoo! Easy!
 			if (i->p->l == i) {
 				i->p->l = i->r;
 				i->r->p = i->p;
 			}
 			else {
 				i->p->r = i->r;
 				i->r->p = i->p;
 			}
 			delete i;
 		}

 		// Oh dear = we have two children and now some heartache
 		if (i->r->l == NULL && i->r->r == NULL) {

 			// No subtree on right hand side.
 			if (i->p->l == i) {
 				// Was left hand child
 				i->p->l = i->l;
 				i->l->p = i->p;
 				t = i->l;

 				// Find insertion point for dangling node
 				while (t != NULL) {
 					last = t;
 					t = t->r;
 				}

 				last->r = i->r;
 				i->r->p = last;
 			}
 			else {
 				// Was right hand child
 				i->p->r = i->l;
 				i->l->p = i->p;
 				t = i->l;

 				// Find insertion point for dangling node
 				while (t != NULL) {
 					last = t;
 					t = t->r;
 				}

 				last->r = i->r;
 				i->r->p = last;
 			}


 		}

 		else {

 			// Subtree - so need to find the "in-order" successor
 			t = i->r;

 			while (t != NULL) {
 				last = t;
 				t=t->l;
 			}

 			// OK - Last is now the next biggest node, and it doesn;t
 			// have anything on it's left (otherwise there would be something smaller)

 			last->p->l = last->r;
 			last->r->p = last->p;
 			last->l = i->l;
 			last->r = i->r;
 			if (last->r != NULL)
 				last->r->p = last;
 			if (last->l != NULL)
 				last->l->p = last;

 			mp_tree = last;
 			last->p = NULL;

 			delete i;

 		}
 	}

 	m_num--;
 }

 void XSECXPathNodeList::clear() {

 	m_num = 0;
 	delete_tree(mp_tree);
 	mp_tree = NULL;

 }

 // --------------------------------------------------------------------------------
 //           Information functions.
 // --------------------------------------------------------------------------------


 bool XSECXPathNodeList::hasNode(const DOMNode *n) const {

 	btn * i = findNodeIndex(n);

 	return (i != NULL);

 }

 const DOMNode *XSECXPathNodeList::getFirstNode(void) const {


 	if (mp_tree == NULL)
 		return NULL;

 	// Find the smallest node
 	mp_current = mp_tree;
 	while (mp_current->l != NULL)
 		mp_current = mp_current->l;

 	return mp_current->v;

 }

 const DOMNode *XSECXPathNodeList::getNextNode(void) const {

 	if (mp_current == NULL)
 		return NULL;

 	btn * t = mp_current;

 	if (t->r != NULL) {
 		// Find next biggest node
 		t = t->r;
 		while (t->l != NULL)
 			t = t->l;
 		mp_current = t;
 	}
 	else {
 		// Go backwards!
 		t = mp_current->p;
 		while (t != NULL && t->r == mp_current) {
 			mp_current = t;
 			t = t->p;
 		}

 		if (t == NULL) {
 			mp_current = NULL;
 			return NULL;
 		}
 		mp_current = t;
 	}

 	return t->v;

 }

 // --------------------------------------------------------------------------------
 //           Intersect with another list
 // --------------------------------------------------------------------------------

 void XSECXPathNodeList::intersect(const XSECXPathNodeList &toIntersect) {

 	// Create a new list
 	XSECXPathNodeList ret;

 	const DOMNode * n = getFirstNode();
 	while (n != NULL) {

 		if (toIntersect.hasNode(n))
 			ret.addNode(n);

 		n = getNextNode();

 	}

 	// Swap lists
 	btn * t = mp_tree;
 	mp_tree = ret.mp_tree;
 	ret.mp_tree = t;
 	m_num = ret.m_num;

 	return;

 }
	/**
	* Licensed to the Apache Software Foundation (ASF) under one
	* or more contributor license agreements. See the NOTICE file
	* distributed with this work for additional information
	* regarding copyright ownership. The ASF licenses this file
	* to you under the Apache License, Version 2.0 (the
	* "License"); you may not use this file except in compliance
	* with the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing,
	* software distributed under the License is distributed on an
	* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
	* KIND, either express or implied. See the License for the
	* specific language governing permissions and limitations
	* under the License.
	*/

	/*
	* XSEC
	*
	* XSECXPathNodeList := A structure to hold node lists from XPath
	* evaluations
	*
	* $Id$
	*
	*/

	// XSEC

	#include <xsec/utils/XSECXPathNodeList.hpp>
	#include <xsec/framework/XSECError.hpp>

	#include <string.h>

	XERCES_CPP_NAMESPACE_USE

	// --------------------------------------------------------------------------------
	// Constructors and Destructors.
	// --------------------------------------------------------------------------------

	XSECXPathNodeList::XSECXPathNodeList(unsigned int initialSize) {

	m_num = 0;
	mp_tree = NULL;

	}

	XSECXPathNodeList::XSECXPathNodeList(const XSECXPathNodeList &other) {

	m_num = other.m_num;
	mp_tree = copy_tree(other.mp_tree);
	mp_current = NULL;

	}

	XSECXPathNodeList::~XSECXPathNodeList() {

	// Delete all the elements in the node list
	delete_tree(mp_tree);

	}

	XSECXPathNodeList & XSECXPathNodeList::operator= (const XSECXPathNodeList & toCopy) {

	// For now simply delete the old list and set with the new
	// Large overhead as we call other functions, but simplest way to
	// implement for now

	mp_tree = copy_tree(toCopy.mp_tree);
	m_num = toCopy.m_num;
	mp_current = NULL;
	return *this;

	}

	// --------------------------------------------------------------------------------
	// Utility Functions.
	// --------------------------------------------------------------------------------

	XSECXPathNodeList::btn * XSECXPathNodeList::findNodeIndex(const DOMNode *n) const {

	btn * t = mp_tree;

	while (t != NULL && t->v != n) {

	if (n > t->v)
	t = t->r;
	else
	t = t->l;
	}

	return t;

	}

	void XSECXPathNodeList::delete_tree(btn * t) {

	if (t == NULL)
	return;

	btn * parent, * n;

	n = t;
	while (n != NULL) {

	if (n->l)
	n = n->l;
	else if (n->r)
	n = n->r;

	else {
	parent = n->p;
	if (parent != NULL) {
	if (parent->l == n)
	parent->l = NULL;
	else
	parent->r = NULL;
	}
	// Delete this node
	delete n;
	n = parent;
	}
	}

	}

	XSECXPathNodeList::btn * XSECXPathNodeList::copy_tree(btn * t) const {

	if (t == NULL)
	return NULL;

	btn * n, c, cp, *ret;
	c = cp = NULL;

	n = t;
	bool create = true;
	ret = NULL;
	while (n != NULL) {

	if (create) {
	XSECnew(c, btn);
	c->l = NULL;
	c->r = NULL;
	c->v = n->v;

	// R we at top?
	if (ret == NULL) {
	ret = c;
	c->p = NULL;
	cp = NULL;
	}

	else {
	c->p = cp;
	if (cp != NULL) {
	if (n->p->l == n)
	cp->l = c;
	else
	cp->r = c;
	}
	}
	}

	// Go down!
	if (c->l == NULL && n->l != NULL) {
	cp = c;
	n = n->l;
	create = true;
	}
	else if (c->r == NULL && n->r != NULL) {
	cp = c;
	n = n->r;
	create = true;
	}
	else {

	// Go Back Up!
	n = n->p;
	c = cp;
	if (cp != NULL)
	cp = cp->p;
	create = false;
	}
	}

	return ret;
	}


	// --------------------------------------------------------------------------------
	// Adding and Deleting Nodes.
	// --------------------------------------------------------------------------------

	long XSECXPathNodeList::balance_count(btn * t) const {

	if (t == NULL)
	return 0;

	long r = (t->r == NULL ? 0 : t->r->h);
	long l = (t->l == NULL ? 0 : t->l->h);

	return r - l;

	}

	long XSECXPathNodeList::calc_height(btn * t) {

	if (t == NULL)
	return 0;
	if (t->l == NULL) {
	if (t->r == NULL)
	return 1;
	return t->r->h + 1;
	}
	else {
	if (t->r == NULL)
	return t->l->h + 1;
	}

	return ((t->l->h > t->r->h ? t->l->h : t->r->h) + 1);
	}

	void XSECXPathNodeList::rotate_right(btn * t) {

	// Rotate me right!
	btn * lc = t->l;

	// First - are we at the root?
	if (t == mp_tree) {
	lc->p = NULL;
	mp_tree = lc;
	}
	else {
	if (t->p->l == t) {
	t->p->l = lc;
	}
	else {
	t->p->r = lc;
	}

	lc->p = t->p;
	}

	// Do the rotate
	t->l = lc->r;
	if (t->l)
	t->l->p = t;
	lc->r = t;
	t->p = lc;

	// Recalculate heights
	lc = t;
	while (lc != NULL) {
	lc->h = calc_height(lc);
	lc = lc->p;
	}

	}


	void XSECXPathNodeList::rotate_left(btn * t) {

	// Rotate me left!
	btn * rc = t->r;

	// First - are we at the root?
	if (t == mp_tree) {
	rc->p = NULL;
	mp_tree = rc;
	}
	else {
	if (t->p->r == t) {
	t->p->r = rc;
	}
	else {
	t->p->l = rc;
	}

	rc->p = t->p;
	}

	// Do the rotate
	t->r = rc->l;
	if (t->r)
	t->r->p = t;
	rc->l = t;
	t->p = rc;

	// Recalculate heights
	rc = t;
	while (rc != NULL) {
	rc->h = calc_height(rc);
	rc = rc->p;
	}

	}

	void XSECXPathNodeList::addNode(const DOMNode *n) {

	btn * v;

	if (m_num == 0) {
	XSECnew(mp_tree, btn);
	mp_tree->l = mp_tree->r = NULL;
	mp_tree->v = n;
	mp_tree->p = NULL;
	mp_tree->h = 1;
	m_num = 1;
	return;
	}

	// Find the node
	btn * t = mp_tree;
	btn * last = NULL;

	while (t != NULL && t->v != n) {
	last = t;
	if (n > t->v)
	t = t->r;
	else
	t = t->l;
	}

	if (t != NULL)
	// Node already exists in tree!
	return;

	// Work out the insertion.
	XSECnew(v, btn);
	v->v = n;
	v->r = v->l = NULL;
	v->h = 1;
	v->p = last;

	// Determine on which leg to place the new value
	if (n > last->v)
	last->r = v;
	else
	last->l = v;

	// Recalculate heights
	t = last;
	long newh;
	while (t != NULL) {
	newh = calc_height(t);
	if (newh > t->h) {
	t->h = newh;
	t = t->p;
	}
	else
	// If the height is the same here, then nothing will have changed above
	t = NULL;
	}

	// Rebalance!

	t = last;
	while (t != NULL) {
	long bal = balance_count(t);
	long balrc = balance_count(t->r);
	long ballc = balance_count(t->l);

	// Case 1 - Balance is OK
	if (bal <= 1 && bal >= -1) {
	// Do nothing!
	}

	// Case 2a - Balance is -2 and LC = -1
	else if (bal == -2 && ballc == -1) {

	// Rotate current node right
	rotate_right(t);
	}
	// Or balance is +2 and RC = +1
	else if (bal == 2 && balrc == 1) {

	// Rotate current node left
	rotate_left(t);
	}
	// Case 2b = Balance is -2 and LC = +1
	else if (bal == -2 && ballc == 1) {

	// Double Right rotation
	rotate_left(t->l);
	rotate_right(t);
	}

	else {
	rotate_right(t->r);
	rotate_left(t);

	}

	t = t->p;

	}

	}

	void XSECXPathNodeList::removeNode(const DOMNode *n) {

	btn * t, * last;
	last = NULL;
	btn * i = findNodeIndex(n);

	if (i == NULL)
	// Not found!
	return;

	// Delete from tree
	if (i == mp_tree) {
	// Bugger - we are at the top of the tree

	// OK - No children?
	if (i->l == NULL && i->r == NULL) {
	// WooHoo! Easy!
	delete mp_tree;
	mp_tree = NULL;
	}

	// One Child?
	if (i->l != NULL && i->r == NULL) {

	// WooHoo! Easy!
	mp_tree = i->l;
	mp_tree->p = NULL;
	delete i;
	}
	if (i->r != NULL && i->l == NULL) {

	// WooHoo! Easy!
	mp_tree = i->r;
	mp_tree->p = NULL;
	delete i;
	}

	// Oh dear = we have two children and now some heartache
	if (i->r->l == NULL && i->r->r == NULL) {

	// No subtree on right hand side.
	mp_tree = mp_tree->l;
	mp_tree->p = NULL;
	t = mp_tree->r;
	last = mp_tree;
	while (t != NULL) {
	last = t;
	if (i->r->v < t->v)
	t = t->l;
	else
	t = t->r;
	}

	if (i->r->v < last->v) {
	last->l = i->r;
	i->r->p = last;
	}
	else {
	last->r = i->r;
	i->r->p = last;
	}
	}

	else {

	// Need to find the "in-order" successor
	t = i->r;

	while (t != NULL) {
	last = t;
	t=t->l;
	}

	if (last == i->r) {
	// can't have been a left hand leg on the next node!)
	last->l = i->l;
	if (last->l != NULL)
	last->l->p = last;

	mp_tree = last;
	last->p = NULL;

	delete i;
	}
	else {

	// OK - Last is now the next biggest node, and it doesn;t
	// have anything on it's left (otherwise there would be something smaller)

	last->p->l = last->r;
	last->r->p = last->p;
	last->l = i->l;
	last->r = i->r;
	if (last->r != NULL)
	last->r->p = last;
	if (last->l != NULL)
	last->l->p = last;

	mp_tree = last;
	last->p = NULL;

	delete i;

	}
	}
	}

	else {

	/* i != mp_tree */
	// OK - No children?
	if (i->l == NULL && i->r == NULL) {
	// WooHoo! Easy!
	if (i->p->l == i)
	i->p->l = NULL;
	else
	i->p->r = NULL;

	delete i;
	}

	// One Child?
	if (i->l != NULL && i->r == NULL) {

	// WooHoo! Easy!
	if (i->p->l == i) {
	i->p->l = i->l;
	i->l->p = i->p;
	}
	else {
	i->p->r = i->l;
	i->r->p = i->p;
	}
	delete i;
	}
	if (i->r != NULL && i->l == NULL) {

	// WooHoo! Easy!
	if (i->p->l == i) {
	i->p->l = i->r;
	i->r->p = i->p;
	}
	else {
	i->p->r = i->r;
	i->r->p = i->p;
	}
	delete i;
	}

	// Oh dear = we have two children and now some heartache
	if (i->r->l == NULL && i->r->r == NULL) {

	// No subtree on right hand side.
	if (i->p->l == i) {
	// Was left hand child
	i->p->l = i->l;
	i->l->p = i->p;
	t = i->l;

	// Find insertion point for dangling node
	while (t != NULL) {
	last = t;
	t = t->r;
	}

	last->r = i->r;
	i->r->p = last;
	}
	else {
	// Was right hand child
	i->p->r = i->l;
	i->l->p = i->p;
	t = i->l;

	// Find insertion point for dangling node
	while (t != NULL) {
	last = t;
	t = t->r;
	}

	last->r = i->r;
	i->r->p = last;
	}


	}

	else {

	// Subtree - so need to find the "in-order" successor
	t = i->r;

	while (t != NULL) {
	last = t;
	t=t->l;
	}

	// OK - Last is now the next biggest node, and it doesn;t
	// have anything on it's left (otherwise there would be something smaller)

	last->p->l = last->r;
	last->r->p = last->p;
	last->l = i->l;
	last->r = i->r;
	if (last->r != NULL)
	last->r->p = last;
	if (last->l != NULL)
	last->l->p = last;

	mp_tree = last;
	last->p = NULL;

	delete i;

	}
	}

	m_num--;
	}

	void XSECXPathNodeList::clear() {

	m_num = 0;
	delete_tree(mp_tree);
	mp_tree = NULL;

	}

	// --------------------------------------------------------------------------------
	// Information functions.
	// --------------------------------------------------------------------------------


	bool XSECXPathNodeList::hasNode(const DOMNode *n) const {

	btn * i = findNodeIndex(n);

	return (i != NULL);

	}

	const DOMNode *XSECXPathNodeList::getFirstNode(void) const {


	if (mp_tree == NULL)
	return NULL;

	// Find the smallest node
	mp_current = mp_tree;
	while (mp_current->l != NULL)
	mp_current = mp_current->l;

	return mp_current->v;

	}

	const DOMNode *XSECXPathNodeList::getNextNode(void) const {

	if (mp_current == NULL)
	return NULL;

	btn * t = mp_current;

	if (t->r != NULL) {
	// Find next biggest node
	t = t->r;
	while (t->l != NULL)
	t = t->l;
	mp_current = t;
	}
	else {
	// Go backwards!
	t = mp_current->p;
	while (t != NULL && t->r == mp_current) {
	mp_current = t;
	t = t->p;
	}

	if (t == NULL) {
	mp_current = NULL;
	return NULL;
	}
	mp_current = t;
	}

	return t->v;

	}

	// --------------------------------------------------------------------------------
	// Intersect with another list
	// --------------------------------------------------------------------------------

	void XSECXPathNodeList::intersect(const XSECXPathNodeList &toIntersect) {

	// Create a new list
	XSECXPathNodeList ret;

	const DOMNode * n = getFirstNode();
	while (n != NULL) {

	if (toIntersect.hasNode(n))
	ret.addNode(n);

	n = getNextNode();

	}

	// Swap lists
	btn * t = mp_tree;
	mp_tree = ret.mp_tree;
	ret.mp_tree = t;
	m_num = ret.m_num;

	return;

	}