xsec/utils/XSECXPathNodeList.cpp

/**
 * 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;

}