path: root/indra/llcommon/linked_lists.h

/** 
 * @file linked_lists.h
 * @brief LLLinkedList class header amd implementation file.
 *
 * $LicenseInfo:firstyear=2001&license=viewerlgpl$
 * Second Life Viewer Source Code
 * Copyright (C) 2010, Linden Research, Inc.
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation;
 * version 2.1 of the License only.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 * 
 * Linden Research, Inc., 945 Battery Street, San Francisco, CA  94111  USA
 * $/LicenseInfo$
 */

#ifndef LL_LINKED_LISTS_H
#define LL_LINKED_LISTS_H

/** 
 * Provides a standard doubly linked list for fun and profit
 * Utilizes a neat trick off of Flipcode where the back pointer is a
 * pointer to a pointer, allowing easier transfer of nodes between lists, &c
 * And a template class, of course
 */

#include "llerror.h"


template <class DATA_TYPE> class LLLinkedList
{
public:
	friend class LLLinkNode;
	// External interface

	// basic constructor
	LLLinkedList() : mHead(NULL), mCurrentp(NULL), mInsertBefore(NULL)
	{
		mCurrentp = mHead.mNextp;
		mCurrentOperatingp = mHead.mNextp;
		mCount = 0;
	}

	// basic constructor
	LLLinkedList(BOOL	(*insert_before)(DATA_TYPE *data_new, DATA_TYPE *data_tested)) : mHead(NULL), mCurrentp(NULL), mInsertBefore(insert_before)
	{
		mCurrentp = mHead.mNextp;
		mCurrentOperatingp = mHead.mNextp;
		mCount = 0;
	}

	// destructor destroys list and nodes, but not data in nodes
	~LLLinkedList()
	{
		removeAllNodes();
	}

	// set mInsertBefore
	void setInsertBefore(BOOL (*insert_before)(DATA_TYPE *data_new, DATA_TYPE *data_tested))
	{
		mInsertBefore = insert_before;
	}

	//
	// WARNING!!!!!!!
	// addData and addDataSorted are NOT O(1) operations, but O(n) because they check
	// for existence of the data in the linked list first.  Why, I don't know - djs
	// If you don't care about dupes, use addDataNoCheck
	//

	// put data into a node and stick it at the front of the list
	inline BOOL addData(DATA_TYPE *data);

	// put data into a node and sort into list by mInsertBefore()
	// calls normal add if mInsertBefore isn't set
	inline BOOL addDataSorted(DATA_TYPE *data);

	inline BOOL addDataNoCheck(DATA_TYPE *data);

	// bubbleSortList
	// does an improved bubble sort of the list . . . works best with almost sorted data
	// does nothing if mInsertBefore isn't set
	// Nota Bene: Swaps are accomplished by swapping data pointers
	inline void bubbleSortList();

	// put data into a node and stick it at the end of the list
	inline BOOL addDataAtEnd(DATA_TYPE *data);

	// returns number of items in the list
	inline S32 getLength() const;

	inline BOOL isEmpty();

	// search the list starting at mHead.mNextp and remove the link with mDatap == data
	// leave mCurrentp and mCurrentOperatingp on the next entry
	// return TRUE if found, FALSE if not found
	inline BOOL removeData(DATA_TYPE *data);

		// search the list starting at mHead.mNextp and delete the link with mDatap == data
	// leave mCurrentp and mCurrentOperatingp on the next entry
	// return TRUE if found, FALSE if not found
	inline BOOL deleteData(DATA_TYPE *data);

	// remove all nodes from the list and delete the associated data
	inline void deleteAllData();

	// remove all nodes from the list but do not delete data
	inline void removeAllNodes();

	// check to see if data is in list
	// if TRUE then mCurrentp and mCurrentOperatingp point to data
	inline BOOL	checkData(DATA_TYPE *data);

	// place mCurrentp on first node
	inline void resetList();

	// return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp
	inline DATA_TYPE	*getCurrentData();

	// same as getCurrentData() but a more intuitive name for the operation
	inline DATA_TYPE	*getNextData();

	// reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp
	inline DATA_TYPE	*getFirstData();

	// reset the list and return the data at position n, set mCurentOperatingp to that node and bump mCurrentp
	// Note: n is zero-based
	inline DATA_TYPE	*getNthData( U32 n);

	// reset the list and return the last data in it, set mCurentOperatingp to that node and bump mCurrentp
	inline DATA_TYPE	*getLastData();

	// remove the Node at mCurentOperatingp
	// leave mCurrentp and mCurentOperatingp on the next entry
	inline void removeCurrentData();

	// remove the Node at mCurentOperatingp and add it to newlist
	// leave mCurrentp and mCurentOperatingp on the next entry
	void moveCurrentData(LLLinkedList *newlist, BOOL b_sort);

	BOOL moveData(DATA_TYPE *data, LLLinkedList *newlist, BOOL b_sort);

	// delete the Node at mCurentOperatingp
	// leave mCurrentp anf mCurentOperatingp on the next entry
	void deleteCurrentData();

private:
	// node that actually contains the data
	class LLLinkNode
	{
	public:
		// assign the mDatap pointer
		LLLinkNode(DATA_TYPE *data) : mDatap(data), mNextp(NULL), mPrevpp(NULL)
		{
		}

		// destructor does not, by default, destroy associated data
		// however, the mDatap must be NULL to ensure that we aren't causing memory leaks
		~LLLinkNode()
		{
			if (mDatap)
			{
				llerror("Attempting to call LLLinkNode destructor with a non-null mDatap!", 1);
			}
		}

		// delete associated data and NULL out pointer
		void deleteData()
		{
			delete mDatap;
			mDatap = NULL;
		}

		// NULL out pointer
		void removeData()
		{
			mDatap = NULL;
		}

		DATA_TYPE	*mDatap;
		LLLinkNode	*mNextp;
		LLLinkNode	**mPrevpp;
	};

	// add a node at the front of the list
	void addData(LLLinkNode *node)
	{
		// don't allow NULL to be passed to addData
		if (!node)
		{
			llerror("NULL pointer passed to LLLinkedList::addData", 0);
		}

		// add the node to the front of the list
		node->mPrevpp = &mHead.mNextp;
		node->mNextp = mHead.mNextp;

		// if there's something in the list, fix its back pointer
		if (node->mNextp)
		{
			node->mNextp->mPrevpp = &node->mNextp;
		}

		mHead.mNextp = node;
	}

	LLLinkNode			mHead;															// fake head node. . . makes pointer operations faster and easier
	LLLinkNode			*mCurrentp;														// mCurrentp is the Node that getCurrentData returns
	LLLinkNode			*mCurrentOperatingp;											// this is the node that the various mumbleCurrentData functions act on
	BOOL				(*mInsertBefore)(DATA_TYPE *data_new, DATA_TYPE *data_tested);	// user function set to allow sorted lists
	U32					mCount;
};

template <class DATA_TYPE>
BOOL LLLinkedList<DATA_TYPE>::addData(DATA_TYPE *data)
{
	// don't allow NULL to be passed to addData
	if (!data)
	{
		llerror("NULL pointer passed to LLLinkedList::addData", 0);
	}

	LLLinkNode *tcurr = mCurrentp;
	LLLinkNode *tcurrop = mCurrentOperatingp;

	if ( checkData(data))
	{
		mCurrentp = tcurr;
		mCurrentOperatingp = tcurrop;
		return FALSE;
	}

	// make the new node
	LLLinkNode *temp = new LLLinkNode(data);

	// add the node to the front of the list
	temp->mPrevpp = &mHead.mNextp;
	temp->mNextp = mHead.mNextp;

	// if there's something in the list, fix its back pointer
	if (temp->mNextp)
	{
		temp->mNextp->mPrevpp = &temp->mNextp;
	}

	mHead.mNextp = temp;
	mCurrentp = tcurr;
	mCurrentOperatingp = tcurrop;
	mCount++;
	return TRUE;
}


template <class DATA_TYPE>
BOOL LLLinkedList<DATA_TYPE>::addDataNoCheck(DATA_TYPE *data)
{
	// don't allow NULL to be passed to addData
	if (!data)
	{
		llerror("NULL pointer passed to LLLinkedList::addData", 0);
	}

	LLLinkNode *tcurr = mCurrentp;
	LLLinkNode *tcurrop = mCurrentOperatingp;

	// make the new node
	LLLinkNode *temp = new LLLinkNode(data);

	// add the node to the front of the list
	temp->mPrevpp = &mHead.mNextp;
	temp->mNextp = mHead.mNextp;

	// if there's something in the list, fix its back pointer
	if (temp->mNextp)
	{
		temp->mNextp->mPrevpp = &temp->mNextp;
	}

	mHead.mNextp = temp;
	mCurrentp = tcurr;
	mCurrentOperatingp = tcurrop;
	mCount++;
	return TRUE;
}


template <class DATA_TYPE>
BOOL LLLinkedList<DATA_TYPE>::addDataSorted(DATA_TYPE *data)
{
	LLLinkNode *tcurr = mCurrentp;
	LLLinkNode *tcurrop = mCurrentOperatingp;
	// don't allow NULL to be passed to addData
	if (!data)
	{
		llerror("NULL pointer passed to LLLinkedList::addDataSorted", 0);
	}

	if (checkData(data))
	{
		// restore
		mCurrentp = tcurr;
		mCurrentOperatingp = tcurrop;
		return FALSE;
	}

	// mInsertBefore not set?
	if (!mInsertBefore)
	{
		addData(data);
		// restore
		mCurrentp = tcurr;
		mCurrentOperatingp = tcurrop;
		return FALSE;
	}

	// empty list?
	if (!mHead.mNextp)
	{
		addData(data);
		// restore
		mCurrentp = tcurr;
		mCurrentOperatingp = tcurrop;
		return TRUE;
	}

	// make the new node
	LLLinkNode *temp = new LLLinkNode(data);

	// walk the list until mInsertBefore returns true 
	mCurrentp = mHead.mNextp;
	while (mCurrentp->mNextp)
	{
		if (mInsertBefore(data, mCurrentp->mDatap))
		{
			// insert before the current one
			temp->mPrevpp = mCurrentp->mPrevpp;
			temp->mNextp = mCurrentp;
			*(temp->mPrevpp) = temp;
			mCurrentp->mPrevpp = &temp->mNextp;
			// restore
			mCurrentp = tcurr;
			mCurrentOperatingp = tcurrop;
			mCount++;
			return TRUE;
		}
		else
		{
			mCurrentp = mCurrentp->mNextp;
		}
	}

	// on the last element, add before?
	if (mInsertBefore(data, mCurrentp->mDatap))
	{
		// insert before the current one
		temp->mPrevpp = mCurrentp->mPrevpp;
		temp->mNextp = mCurrentp;
		*(temp->mPrevpp) = temp;
		mCurrentp->mPrevpp = &temp->mNextp;
		// restore
		mCurrentp = tcurr;
		mCurrentOperatingp = tcurrop;
	}
	else // insert after
	{
		temp->mPrevpp = &mCurrentp->mNextp;
		temp->mNextp = NULL;
		mCurrentp->mNextp = temp;

		// restore
		mCurrentp = tcurr;
		mCurrentOperatingp = tcurrop;
	}
	mCount++;
	return TRUE;
}

template <class DATA_TYPE>
void LLLinkedList<DATA_TYPE>::bubbleSortList()
{
	// mInsertBefore not set
	if (!mInsertBefore)
	{
		return;
	}

	LLLinkNode *tcurr = mCurrentp;
	LLLinkNode *tcurrop = mCurrentOperatingp;

	BOOL		b_swapped = FALSE;
	DATA_TYPE	*temp;

	// Nota Bene: This will break if more than 0x7FFFFFFF members in list!
	S32			length = 0x7FFFFFFF;
	S32			count = 0;
	do
	{
		b_swapped = FALSE;
		mCurrentp = mHead.mNextp;
		count = 0;
		while (  (count + 1 < length)
			   &&(mCurrentp))
		{
			if (mCurrentp->mNextp)
			{
				if (!mInsertBefore(mCurrentp->mDatap, mCurrentp->mNextp->mDatap))
				{
					// swap data pointers!
					temp = mCurrentp->mDatap;
					mCurrentp->mDatap = mCurrentp->mNextp->mDatap;
					mCurrentp->mNextp->mDatap = temp;
					b_swapped = TRUE;
				}
			}
			else
			{
				break;
			}
			count++;
			mCurrentp = mCurrentp->mNextp;
		}
		length = count;
	} while (b_swapped);

	// restore
	mCurrentp = tcurr;
	mCurrentOperatingp = tcurrop;
}


template <class DATA_TYPE>
BOOL LLLinkedList<DATA_TYPE>::addDataAtEnd(DATA_TYPE *data)
{
	LLLinkNode *tcurr = mCurrentp;
	LLLinkNode *tcurrop = mCurrentOperatingp;

	// don't allow NULL to be passed to addData
	if (!data)
	{
		llerror("NULL pointer passed to LLLinkedList::addData", 0);
	}

	if (checkData(data))
	{
		mCurrentp = tcurr;
		mCurrentOperatingp = tcurrop;
		return FALSE;
	}

	// make the new node
	LLLinkNode *temp = new LLLinkNode(data);

	// add the node to the end of the list

	// if empty, add to the front and be done with it
	if (!mHead.mNextp)
	{
		temp->mPrevpp = &mHead.mNextp;
		temp->mNextp = NULL;
		mHead.mNextp = temp;
	}
	else
	{
		// otherwise, walk to the end of the list
		mCurrentp = mHead.mNextp;
		while (mCurrentp->mNextp)
		{
			mCurrentp = mCurrentp->mNextp;
		}
		temp->mPrevpp = &mCurrentp->mNextp;
		temp->mNextp = NULL;
		mCurrentp->mNextp = temp;
	}

	// restore
	mCurrentp = tcurr;
	mCurrentOperatingp = tcurrop;
	mCount++;
	return TRUE;
}


// returns number of items in the list
template <class DATA_TYPE>
S32 LLLinkedList<DATA_TYPE>::getLength() const
{
//	S32	length = 0;
//	for (LLLinkNode* temp = mHead.mNextp; temp != NULL; temp = temp->mNextp)
//	{
//		length++;
//	}
	return mCount;
}


template <class DATA_TYPE>
BOOL LLLinkedList<DATA_TYPE>::isEmpty()
{
	return (mCount == 0);
}


// search the list starting at mHead.mNextp and remove the link with mDatap == data
// leave mCurrentp and mCurrentOperatingp on the next entry
// return TRUE if found, FALSE if not found
template <class DATA_TYPE>
BOOL LLLinkedList<DATA_TYPE>::removeData(DATA_TYPE *data)
{
	BOOL b_found = FALSE;
	// don't allow NULL to be passed to addData
	if (!data)
	{
		llerror("NULL pointer passed to LLLinkedList::removeData", 0);
	}

	LLLinkNode *tcurr = mCurrentp;
	LLLinkNode *tcurrop = mCurrentOperatingp;

	mCurrentp = mHead.mNextp;
	mCurrentOperatingp = mHead.mNextp;

	while (mCurrentOperatingp)
	{
		if (mCurrentOperatingp->mDatap == data)
		{
			b_found = TRUE;

			// remove the node

			// if there is a next one, fix it
			if (mCurrentOperatingp->mNextp)
			{
				mCurrentOperatingp->mNextp->mPrevpp = mCurrentOperatingp->mPrevpp;
			}
			*(mCurrentOperatingp->mPrevpp) = mCurrentOperatingp->mNextp;

			// remove the LLLinkNode

			// if we were on the one we want to delete, bump the cached copies
			if (mCurrentOperatingp == tcurrop)
			{
				tcurrop = tcurr = mCurrentOperatingp->mNextp;
			}
			else if (mCurrentOperatingp == tcurr)
			{
				tcurrop = tcurr = mCurrentOperatingp->mNextp;
			}

			mCurrentp = mCurrentOperatingp->mNextp;

			mCurrentOperatingp->removeData();
			delete mCurrentOperatingp;
			mCurrentOperatingp = mCurrentp;
			mCount--;
			break;
		}
		mCurrentOperatingp = mCurrentOperatingp->mNextp;
	}
	// restore
	mCurrentp = tcurr;
	mCurrentOperatingp = tcurrop;
	return b_found;
}

// search the list starting at mHead.mNextp and delete the link with mDatap == data
// leave mCurrentp and mCurrentOperatingp on the next entry
// return TRUE if found, FALSE if not found
template <class DATA_TYPE>
BOOL LLLinkedList<DATA_TYPE>::deleteData(DATA_TYPE *data)
{
	BOOL b_found = FALSE;
	// don't allow NULL to be passed to addData
	if (!data)
	{
		llerror("NULL pointer passed to LLLinkedList::removeData", 0);
	}

	LLLinkNode *tcurr = mCurrentp;
	LLLinkNode *tcurrop = mCurrentOperatingp;

	mCurrentp = mHead.mNextp;
	mCurrentOperatingp = mHead.mNextp;

	while (mCurrentOperatingp)
	{
		if (mCurrentOperatingp->mDatap == data)
		{
			b_found = TRUE;

			// remove the node
			// if there is a next one, fix it
			if (mCurrentOperatingp->mNextp)
			{
				mCurrentOperatingp->mNextp->mPrevpp = mCurrentOperatingp->mPrevpp;
			}
			*(mCurrentOperatingp->mPrevpp) = mCurrentOperatingp->mNextp;

			// delete the LLLinkNode
			// if we were on the one we want to delete, bump the cached copies
			if (mCurrentOperatingp == tcurrop)
			{
				tcurrop = tcurr = mCurrentOperatingp->mNextp;
			}

			// and delete the associated data
			llassert(mCurrentOperatingp);
			mCurrentp = mCurrentOperatingp->mNextp;
			mCurrentOperatingp->deleteData();
			delete mCurrentOperatingp;
			mCurrentOperatingp = mCurrentp;
			mCount--;
			break;
		}
		mCurrentOperatingp = mCurrentOperatingp->mNextp;
	}
	// restore
	mCurrentp = tcurr;
	mCurrentOperatingp = tcurrop;
	return b_found;
}

	// remove all nodes from the list and delete the associated data
template <class DATA_TYPE>
void LLLinkedList<DATA_TYPE>::deleteAllData()
{
	LLLinkNode *temp;
	// reset mCurrentp
	mCurrentp = mHead.mNextp;

	while (mCurrentp)
	{
		temp = mCurrentp->mNextp;
		mCurrentp->deleteData();
		delete mCurrentp;
		mCurrentp = temp;
	}

	// reset mHead and mCurrentp
	mHead.mNextp = NULL;
	mCurrentp = mHead.mNextp;
	mCurrentOperatingp = mHead.mNextp;
	mCount = 0;
}

// remove all nodes from the list but do not delete data
template <class DATA_TYPE>
void LLLinkedList<DATA_TYPE>::removeAllNodes()
{
	LLLinkNode *temp;
	// reset mCurrentp
	mCurrentp = mHead.mNextp;

	while (mCurrentp)
	{
		temp = mCurrentp->mNextp;
		mCurrentp->removeData();
		delete mCurrentp;
		mCurrentp = temp;
	}

	// reset mHead and mCurrentp
	mHead.mNextp = NULL;
	mCurrentp = mHead.mNextp;
	mCurrentOperatingp = mHead.mNextp;
	mCount = 0;
}

// check to see if data is in list
// if TRUE then mCurrentp and mCurrentOperatingp point to data
template <class DATA_TYPE>
BOOL LLLinkedList<DATA_TYPE>::checkData(DATA_TYPE *data)
{
	// reset mCurrentp
	mCurrentp = mHead.mNextp;

	while (mCurrentp)
	{
		if (mCurrentp->mDatap == data)
		{
			mCurrentOperatingp = mCurrentp;
			return TRUE;
		}
		mCurrentp = mCurrentp->mNextp;
	}
	mCurrentOperatingp = mCurrentp;
	return FALSE;
}

// place mCurrentp on first node
template <class DATA_TYPE>
void LLLinkedList<DATA_TYPE>::resetList()
{
	mCurrentp = mHead.mNextp;
	mCurrentOperatingp = mHead.mNextp;
}

// return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp
template <class DATA_TYPE>
DATA_TYPE *LLLinkedList<DATA_TYPE>::getCurrentData()
{
	if (mCurrentp)
	{
		mCurrentOperatingp = mCurrentp;
		mCurrentp = mCurrentp->mNextp;
		return mCurrentOperatingp->mDatap;
	}
	else
	{
		return NULL;
	}
}

// same as getCurrentData() but a more intuitive name for the operation
template <class DATA_TYPE>
DATA_TYPE *LLLinkedList<DATA_TYPE>::getNextData()
{
	if (mCurrentp)
	{
		mCurrentOperatingp = mCurrentp;
		mCurrentp = mCurrentp->mNextp;
		return mCurrentOperatingp->mDatap;
	}
	else
	{
		return NULL;
	}
}

// reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp
template <class DATA_TYPE>
DATA_TYPE *LLLinkedList<DATA_TYPE>::getFirstData()
{
	mCurrentp = mHead.mNextp;
	mCurrentOperatingp = mHead.mNextp;
	if (mCurrentp)
	{
		mCurrentOperatingp = mCurrentp;
		mCurrentp = mCurrentp->mNextp;
		return mCurrentOperatingp->mDatap;
	}
	else
	{
		return NULL;
	}
}

// Note: n is zero-based
template <class DATA_TYPE>
DATA_TYPE	*LLLinkedList<DATA_TYPE>::getNthData( U32 n )
{
	mCurrentOperatingp = mHead.mNextp;

	// if empty, return NULL
	if (!mCurrentOperatingp)
	{
		return NULL;
	}

	for( U32 i = 0; i < n; i++ )
	{
		mCurrentOperatingp = mCurrentOperatingp->mNextp;
		if( !mCurrentOperatingp )
		{
			return NULL;
		}
	}

	mCurrentp = mCurrentOperatingp->mNextp;
	return mCurrentOperatingp->mDatap;
}


// reset the list and return the last data in it, set mCurentOperatingp to that node and bump mCurrentp
template <class DATA_TYPE>
DATA_TYPE *LLLinkedList<DATA_TYPE>::getLastData()
{
	mCurrentOperatingp = mHead.mNextp;

	// if empty, return NULL
	if (!mCurrentOperatingp)
		return NULL;

	// walk until we're pointing at the last entry
	while (mCurrentOperatingp->mNextp)
	{
		mCurrentOperatingp = mCurrentOperatingp->mNextp;
	}
	mCurrentp = mCurrentOperatingp->mNextp;
	return mCurrentOperatingp->mDatap;
}

// remove the Node at mCurentOperatingp
// leave mCurrentp and mCurentOperatingp on the next entry
// return TRUE if found, FALSE if not found
template <class DATA_TYPE>
void LLLinkedList<DATA_TYPE>::removeCurrentData()
{
	if (mCurrentOperatingp)
	{
		// remove the node
		// if there is a next one, fix it
		if (mCurrentOperatingp->mNextp)
		{
			mCurrentOperatingp->mNextp->mPrevpp = mCurrentOperatingp->mPrevpp;
		}
		*(mCurrentOperatingp->mPrevpp) = mCurrentOperatingp->mNextp;

		// remove the LLLinkNode
		mCurrentp = mCurrentOperatingp->mNextp;

		mCurrentOperatingp->removeData();
		delete mCurrentOperatingp;
		mCount--;
		mCurrentOperatingp = mCurrentp;
	}
}

// remove the Node at mCurentOperatingp and add it to newlist
// leave mCurrentp and mCurentOperatingp on the next entry
// return TRUE if found, FALSE if not found
template <class DATA_TYPE>
void LLLinkedList<DATA_TYPE>::moveCurrentData(LLLinkedList *newlist, BOOL b_sort)
{
	if (mCurrentOperatingp)
	{
		// remove the node
		// if there is a next one, fix it
		if (mCurrentOperatingp->mNextp)
		{
			mCurrentOperatingp->mNextp->mPrevpp = mCurrentOperatingp->mPrevpp;
		}
		*(mCurrentOperatingp->mPrevpp) = mCurrentOperatingp->mNextp;

		// remove the LLLinkNode
		mCurrentp = mCurrentOperatingp->mNextp;
		// move the node to the new list
		newlist->addData(mCurrentOperatingp);
		if (b_sort)
			bubbleSortList();
		mCurrentOperatingp = mCurrentp;
	}
}

template <class DATA_TYPE>
BOOL LLLinkedList<DATA_TYPE>::moveData(DATA_TYPE *data, LLLinkedList *newlist, BOOL b_sort)
{
	BOOL b_found = FALSE;
	// don't allow NULL to be passed to addData
	if (!data)
	{
		llerror("NULL pointer passed to LLLinkedList::removeData", 0);
	}

	LLLinkNode *tcurr = mCurrentp;
	LLLinkNode *tcurrop = mCurrentOperatingp;

	mCurrentp = mHead.mNextp;
	mCurrentOperatingp = mHead.mNextp;

	while (mCurrentOperatingp)
	{
		if (mCurrentOperatingp->mDatap == data)
		{
			b_found = TRUE;

			// remove the node

			// if there is a next one, fix it
			if (mCurrentOperatingp->mNextp)
			{
				mCurrentOperatingp->mNextp->mPrevpp = mCurrentOperatingp->mPrevpp;
			}
			*(mCurrentOperatingp->mPrevpp) = mCurrentOperatingp->mNextp;

			// if we were on the one we want to delete, bump the cached copies
			if (  (mCurrentOperatingp == tcurrop)
				||(mCurrentOperatingp == tcurr))
			{
				tcurrop = tcurr = mCurrentOperatingp->mNextp;
			}

			// remove the LLLinkNode
			mCurrentp = mCurrentOperatingp->mNextp;
			// move the node to the new list
			newlist->addData(mCurrentOperatingp);
			if (b_sort)
				newlist->bubbleSortList();
			mCurrentOperatingp = mCurrentp;
			break;
		}
		mCurrentOperatingp = mCurrentOperatingp->mNextp;
	}
	// restore
	mCurrentp = tcurr;
	mCurrentOperatingp = tcurrop;
	return b_found;
}

// delete the Node at mCurentOperatingp
// leave mCurrentp anf mCurentOperatingp on the next entry
// return TRUE if found, FALSE if not found
template <class DATA_TYPE>
void LLLinkedList<DATA_TYPE>::deleteCurrentData()
{
	if (mCurrentOperatingp)
	{
		// remove the node
		// if there is a next one, fix it
		if (mCurrentOperatingp->mNextp)
		{
			mCurrentOperatingp->mNextp->mPrevpp = mCurrentOperatingp->mPrevpp;
		}
		*(mCurrentOperatingp->mPrevpp) = mCurrentOperatingp->mNextp;

		// remove the LLLinkNode
		mCurrentp = mCurrentOperatingp->mNextp;

		mCurrentOperatingp->deleteData();
		if (mCurrentOperatingp->mDatap)
			llerror("This is impossible!", 0);
		delete mCurrentOperatingp;
		mCurrentOperatingp = mCurrentp;
		mCount--;
	}
}

#endif