void XSECXPathNodeList::removeNode()

in xsec/utils/XSECXPathNodeList.cpp [402:620]

• 146 lines of code
• 36 McCabe index (conditional complexity)

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--;
}