diff options
Diffstat (limited to 'indra/llcommon/doublelinkedlist.h')
| -rwxr-xr-x | indra/llcommon/doublelinkedlist.h | 1397 |
1 files changed, 0 insertions, 1397 deletions
diff --git a/indra/llcommon/doublelinkedlist.h b/indra/llcommon/doublelinkedlist.h deleted file mode 100755 index 0aeaa69df3..0000000000 --- a/indra/llcommon/doublelinkedlist.h +++ /dev/null @@ -1,1397 +0,0 @@ -/** - * @file doublelinkedlist.h - * @brief Provides a standard doubly linked list for fun and profit. - * - * $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_DOUBLELINKEDLIST_H -#define LL_DOUBLELINKEDLIST_H - -#include "llerror.h" -#include "llrand.h" - -// node that actually contains the data -template <class DATA_TYPE> class LLDoubleLinkedNode -{ -public: - DATA_TYPE *mDatap; - LLDoubleLinkedNode *mNextp; - LLDoubleLinkedNode *mPrevp; - - -public: - // assign the mDatap pointer - LLDoubleLinkedNode(DATA_TYPE *data); - - // destructor does not, by default, destroy associated data - // however, the mDatap must be NULL to ensure that we aren't causing memory leaks - ~LLDoubleLinkedNode(); - - // delete associated data and NULL out pointer - void deleteData(); - - // remove associated data and NULL out pointer - void removeData(); -}; - - -const U32 LLDOUBLE_LINKED_LIST_STATE_STACK_DEPTH = 4; - -template <class DATA_TYPE> class LLDoubleLinkedList -{ -private: - LLDoubleLinkedNode<DATA_TYPE> mHead; // head node - LLDoubleLinkedNode<DATA_TYPE> mTail; // tail node - LLDoubleLinkedNode<DATA_TYPE> *mQueuep; // The node in the batter's box - LLDoubleLinkedNode<DATA_TYPE> *mCurrentp; // The node we're talking about - - // The state stack allows nested exploration of the LLDoubleLinkedList - // but should be used with great care - LLDoubleLinkedNode<DATA_TYPE> *mQueuepStack[LLDOUBLE_LINKED_LIST_STATE_STACK_DEPTH]; - LLDoubleLinkedNode<DATA_TYPE> *mCurrentpStack[LLDOUBLE_LINKED_LIST_STATE_STACK_DEPTH]; - U32 mStateStackDepth; - U32 mCount; - - // mInsertBefore is a pointer to a user-set function that returns - // TRUE if "first" should be located before "second" - // NOTE: mInsertBefore() should never return TRUE when ("first" == "second") - // or never-ending loops can occur - BOOL (*mInsertBefore)(DATA_TYPE *first, DATA_TYPE *second); - -public: - LLDoubleLinkedList(); - - // destructor destroys list and nodes, but not data in nodes - ~LLDoubleLinkedList(); - - // put data into a node and stick it at the front of the list - // set mCurrentp to mQueuep - void addData(DATA_TYPE *data); - - // put data into a node and stick it at the end of the list - // set mCurrentp to mQueuep - void addDataAtEnd(DATA_TYPE *data); - - S32 getLength() const; - // search the list starting at mHead.mNextp and remove the link with mDatap == data - // set mCurrentp to mQueuep - // return TRUE if found, FALSE if not found - BOOL removeData(const DATA_TYPE *data); - - // search the list starting at mHead.mNextp and delete the link with mDatap == data - // set mCurrentp to mQueuep - // return TRUE if found, FALSE if not found - BOOL deleteData(DATA_TYPE *data); - - // remove all nodes from the list and delete the associated data - void deleteAllData(); - - // remove all nodes from the list but do not delete data - void removeAllNodes(); - - BOOL isEmpty(); - - // check to see if data is in list - // set mCurrentp and mQueuep to the target of search if found, otherwise set mCurrentp to mQueuep - // return TRUE if found, FALSE if not found - BOOL checkData(const DATA_TYPE *data); - - // NOTE: This next two funtions are only included here - // for those too familiar with the LLLinkedList template class. - // They are depreciated. resetList() is unecessary while - // getCurrentData() is identical to getNextData() and has - // a misleading name. - // - // The recommended way to loop through a list is as follows: - // - // datap = list.getFirstData(); - // while (datap) - // { - // /* do stuff */ - // datap = list.getNextData(); - // } - - // place mQueuep on mHead node - void resetList(); - - // return the data currently pointed to, - // set mCurrentp to that node and bump mQueuep down the list - // NOTE: this function is identical to getNextData() - DATA_TYPE *getCurrentData(); - - - // reset the list and return the data currently pointed to, - // set mCurrentp to that node and bump mQueuep down the list - DATA_TYPE *getFirstData(); - - - // reset the list and return the data at position n, set mCurentp - // to that node and bump mQueuep down the list - // Note: n=0 will behave like getFirstData() - DATA_TYPE *getNthData(U32 n); - - // reset the list and return the last data in it, - // set mCurrentp to that node and bump mQueuep up the list - DATA_TYPE *getLastData(); - - // return data in mQueuep, - // set mCurrentp mQueuep and bump mQueuep down the list - DATA_TYPE *getNextData(); - - // return the data in mQueuep, - // set mCurrentp to mQueuep and bump mQueuep up the list - DATA_TYPE *getPreviousData(); - - // remove the Node at mCurrentp - // set mCurrentp to mQueuep - void removeCurrentData(); - - // delete the Node at mCurrentp - // set mCurrentp to mQueuep - void deleteCurrentData(); - - // remove the Node at mCurrentp and insert it into newlist - // set mCurrentp to mQueuep - void moveCurrentData(LLDoubleLinkedList<DATA_TYPE> *newlist); - - // insert the node in front of mCurrentp - // set mCurrentp to mQueuep - void insertNode(LLDoubleLinkedNode<DATA_TYPE> *node); - - // insert the data in front of mCurrentp - // set mCurrentp to mQueuep - void insertData(DATA_TYPE *data); - - // if mCurrentp has a previous node then : - // * swaps mCurrentp with its previous - // * set mCurrentp to mQueuep - // (convenient for forward bubble-sort) - // otherwise does nothing - void swapCurrentWithPrevious(); - - // if mCurrentp has a next node then : - // * swaps mCurrentp with its next - // * set mCurrentp to mQueuep - // (convenient for backwards bubble-sort) - // otherwise does nothing - void swapCurrentWithNext(); - - // move mCurrentp to the front of the list - // set mCurrentp to mQueuep - void moveCurrentToFront(); - - // move mCurrentp to the end of the list - // set mCurrentp to mQueuep - void moveCurrentToEnd(); - - // set mInsertBefore - void setInsertBefore(BOOL (*insert_before)(DATA_TYPE *first, DATA_TYPE *second)); - - // add data in front of first node for which mInsertBefore(datap, node->mDatap) returns TRUE - // set mCurrentp to mQueuep - BOOL addDataSorted(DATA_TYPE *datap); - - // sort the list using bubble-sort - // Yes, this is a different name than the same function in LLLinkedList. - // When it comes time for a name consolidation hopefully this one will win. - BOOL bubbleSort(); - - // does a single bubble sort pass on the list - BOOL lazyBubbleSort(); - - // returns TRUE if state successfully pushed (state stack not full) - BOOL pushState(); - - // returns TRUE if state successfully popped (state stack not empty) - BOOL popState(); - - // empties the state stack - void clearStateStack(); - - // randomly move the the links in the list for debug or (Discordian) purposes - // sets mCurrentp and mQueuep to top of list - void scramble(); - -private: - // add node to beginning of list - // set mCurrentp to mQueuep - void addNode(LLDoubleLinkedNode<DATA_TYPE> *node); - - // add node to end of list - // set mCurrentp to mQueuep - void addNodeAtEnd(LLDoubleLinkedNode<DATA_TYPE> *node); -}; - -//#endif - -//////////////////////////////////////////////////////////////////////////////////////////// - -// doublelinkedlist.cpp -// LLDoubleLinkedList template class implementation file. -// Provides a standard doubly linked list for fun and profit. -// -// Copyright 2001, Linden Research, Inc. - -//#include "llerror.h" -//#include "doublelinkedlist.h" - -////////////////////////////////////////////////////////////////////////////////////////// -// LLDoubleLinkedNode -////////////////////////////////////////////////////////////////////////////////////////// - - -// assign the mDatap pointer -template <class DATA_TYPE> -LLDoubleLinkedNode<DATA_TYPE>::LLDoubleLinkedNode(DATA_TYPE *data) : - mDatap(data), mNextp(NULL), mPrevp(NULL) -{ -} - - -// destructor does not, by default, destroy associated data -// however, the mDatap must be NULL to ensure that we aren't causing memory leaks -template <class DATA_TYPE> -LLDoubleLinkedNode<DATA_TYPE>::~LLDoubleLinkedNode() -{ - if (mDatap) - { - llerror("Attempting to call LLDoubleLinkedNode destructor with a non-null mDatap!", 1); - } -} - - -// delete associated data and NULL out pointer -template <class DATA_TYPE> -void LLDoubleLinkedNode<DATA_TYPE>::deleteData() -{ - delete mDatap; - mDatap = NULL; -} - - -template <class DATA_TYPE> -void LLDoubleLinkedNode<DATA_TYPE>::removeData() -{ - mDatap = NULL; -} - - -////////////////////////////////////////////////////////////////////////////////////// -// LLDoubleLinkedList -////////////////////////////////////////////////////////////////////////////////////// - -// <------- up ------- -// -// mCurrentp -// mQueuep | -// | | -// | | -// .------. .------. .------. .------. -// | |---->| |---->| |----->| |-----> NULL -// NULL <-----| |<----| |<----| |<-----| | -// _'------' '------' '------' '------:_ -// .------. /| | | |\ .------. -// NULL <-----|mHead |/ | mQueuep \|mTail |-----> NULL -// | | mCurrentp | | -// '------' '------' -// -------- down ---------> - -template <class DATA_TYPE> -LLDoubleLinkedList<DATA_TYPE>::LLDoubleLinkedList() -: mHead(NULL), mTail(NULL), mQueuep(NULL) -{ - mCurrentp = mHead.mNextp; - mQueuep = mHead.mNextp; - mStateStackDepth = 0; - mCount = 0; - mInsertBefore = NULL; -} - - -// destructor destroys list and nodes, but not data in nodes -template <class DATA_TYPE> -LLDoubleLinkedList<DATA_TYPE>::~LLDoubleLinkedList() -{ - removeAllNodes(); -} - - -// put data into a node and stick it at the front of the list -// doesn't change mCurrentp nor mQueuep -template <class DATA_TYPE> -void LLDoubleLinkedList<DATA_TYPE>::addData(DATA_TYPE *data) -{ - // don't allow NULL to be passed to addData - if (!data) - { - llerror("NULL pointer passed to LLDoubleLinkedList::addData()", 0); - } - - // make the new node - LLDoubleLinkedNode<DATA_TYPE> *temp = new LLDoubleLinkedNode<DATA_TYPE> (data); - - // add the node to the front of the list - temp->mPrevp = NULL; - temp->mNextp = mHead.mNextp; - mHead.mNextp = temp; - - // if there's something in the list, fix its back pointer - if (temp->mNextp) - { - temp->mNextp->mPrevp = temp; - } - // otherwise, fix the tail of the list - else - { - mTail.mPrevp = temp; - } - - mCount++; -} - - -// put data into a node and stick it at the end of the list -template <class DATA_TYPE> -void LLDoubleLinkedList<DATA_TYPE>::addDataAtEnd(DATA_TYPE *data) -{ - // don't allow NULL to be passed to addData - if (!data) - { - llerror("NULL pointer passed to LLDoubleLinkedList::addData()", 0); - } - - // make the new node - LLDoubleLinkedNode<DATA_TYPE> *nodep = new LLDoubleLinkedNode<DATA_TYPE>(data); - - addNodeAtEnd(nodep); - mCount++; -} - - -// search the list starting at mHead.mNextp and remove the link with mDatap == data -// set mCurrentp to mQueuep, or NULL if mQueuep points to node with mDatap == data -// return TRUE if found, FALSE if not found -template <class DATA_TYPE> -BOOL LLDoubleLinkedList<DATA_TYPE>::removeData(const DATA_TYPE *data) -{ - BOOL b_found = FALSE; - // don't allow NULL to be passed to addData - if (!data) - { - llerror("NULL pointer passed to LLDoubleLinkedList::removeData()", 0); - } - - mCurrentp = mHead.mNextp; - - while (mCurrentp) - { - if (mCurrentp->mDatap == data) - { - b_found = TRUE; - - // if there is a next one, fix it - if (mCurrentp->mNextp) - { - mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp; - } - else // we are at end of list - { - mTail.mPrevp = mCurrentp->mPrevp; - } - - // if there is a previous one, fix it - if (mCurrentp->mPrevp) - { - mCurrentp->mPrevp->mNextp = mCurrentp->mNextp; - } - else // we are at beginning of list - { - mHead.mNextp = mCurrentp->mNextp; - } - - // remove the node - mCurrentp->removeData(); - delete mCurrentp; - mCount--; - break; - } - mCurrentp = mCurrentp->mNextp; - } - - // reset the list back to where it was - if (mCurrentp == mQueuep) - { - mCurrentp = mQueuep = NULL; - } - else - { - mCurrentp = mQueuep; - } - - return b_found; -} - - -// search the list starting at mHead.mNextp and delete the link with mDatap == data -// set mCurrentp to mQueuep, or NULL if mQueuep points to node with mDatap == data -// return TRUE if found, FALSE if not found -template <class DATA_TYPE> -BOOL LLDoubleLinkedList<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 LLDoubleLinkedList::deleteData()", 0); - } - - mCurrentp = mHead.mNextp; - - while (mCurrentp) - { - if (mCurrentp->mDatap == data) - { - b_found = TRUE; - - // if there is a next one, fix it - if (mCurrentp->mNextp) - { - mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp; - } - else // we are at end of list - { - mTail.mPrevp = mCurrentp->mPrevp; - } - - // if there is a previous one, fix it - if (mCurrentp->mPrevp) - { - mCurrentp->mPrevp->mNextp = mCurrentp->mNextp; - } - else // we are at beginning of list - { - mHead.mNextp = mCurrentp->mNextp; - } - - // remove the node - mCurrentp->deleteData(); - delete mCurrentp; - mCount--; - break; - } - mCurrentp = mCurrentp->mNextp; - } - - // reset the list back to where it was - if (mCurrentp == mQueuep) - { - mCurrentp = mQueuep = NULL; - } - else - { - mCurrentp = mQueuep; - } - - return b_found; -} - - -// remove all nodes from the list and delete the associated data -template <class DATA_TYPE> -void LLDoubleLinkedList<DATA_TYPE>::deleteAllData() -{ - mCurrentp = mHead.mNextp; - - while (mCurrentp) - { - mQueuep = mCurrentp->mNextp; - mCurrentp->deleteData(); - delete mCurrentp; - mCurrentp = mQueuep; - } - - // reset mHead and mQueuep - mHead.mNextp = NULL; - mTail.mPrevp = NULL; - mCurrentp = mHead.mNextp; - mQueuep = mHead.mNextp; - mStateStackDepth = 0; - mCount = 0; -} - - -// remove all nodes from the list but do not delete associated data -template <class DATA_TYPE> -void LLDoubleLinkedList<DATA_TYPE>::removeAllNodes() -{ - mCurrentp = mHead.mNextp; - - while (mCurrentp) - { - mQueuep = mCurrentp->mNextp; - mCurrentp->removeData(); - delete mCurrentp; - mCurrentp = mQueuep; - } - - // reset mHead and mCurrentp - mHead.mNextp = NULL; - mTail.mPrevp = NULL; - mCurrentp = mHead.mNextp; - mQueuep = mHead.mNextp; - mStateStackDepth = 0; - mCount = 0; -} - -template <class DATA_TYPE> -S32 LLDoubleLinkedList<DATA_TYPE>::getLength() const -{ -// U32 length = 0; -// for (LLDoubleLinkedNode<DATA_TYPE>* temp = mHead.mNextp; temp != NULL; temp = temp->mNextp) -// { -// length++; -// } - return mCount; -} - -// check to see if data is in list -// set mCurrentp and mQueuep to the target of search if found, otherwise set mCurrentp to mQueuep -// return TRUE if found, FALSE if not found -template <class DATA_TYPE> -BOOL LLDoubleLinkedList<DATA_TYPE>::checkData(const DATA_TYPE *data) -{ - mCurrentp = mHead.mNextp; - - while (mCurrentp) - { - if (mCurrentp->mDatap == data) - { - mQueuep = mCurrentp; - return TRUE; - } - mCurrentp = mCurrentp->mNextp; - } - - mCurrentp = mQueuep; - return FALSE; -} - -// NOTE: This next two funtions are only included here -// for those too familiar with the LLLinkedList template class. -// They are depreciated. resetList() is unecessary while -// getCurrentData() is identical to getNextData() and has -// a misleading name. -// -// The recommended way to loop through a list is as follows: -// -// datap = list.getFirstData(); -// while (datap) -// { -// /* do stuff */ -// datap = list.getNextData(); -// } - - // place mCurrentp and mQueuep on first node - template <class DATA_TYPE> - void LLDoubleLinkedList<DATA_TYPE>::resetList() - { - mCurrentp = mHead.mNextp; - mQueuep = mHead.mNextp; - mStateStackDepth = 0; - } - - - // return the data currently pointed to, - // set mCurrentp to that node and bump mQueuep down the list - template <class DATA_TYPE> - DATA_TYPE* LLDoubleLinkedList<DATA_TYPE>::getCurrentData() - { - if (mQueuep) - { - mCurrentp = mQueuep; - mQueuep = mQueuep->mNextp; - return mCurrentp->mDatap; - } - else - { - return NULL; - } - } - - -// reset the list and return the data currently pointed to, -// set mCurrentp to that node and bump mQueuep down the list -template <class DATA_TYPE> -DATA_TYPE* LLDoubleLinkedList<DATA_TYPE>::getFirstData() -{ - mQueuep = mHead.mNextp; - mCurrentp = mQueuep; - if (mQueuep) - { - mQueuep = mQueuep->mNextp; - return mCurrentp->mDatap; - } - else - { - return NULL; - } -} - - -// reset the list and return the data at position n, set mCurentp -// to that node and bump mQueuep down the list -// Note: n=0 will behave like getFirstData() -template <class DATA_TYPE> -DATA_TYPE* LLDoubleLinkedList<DATA_TYPE>::getNthData(U32 n) -{ - mCurrentp = mHead.mNextp; - - if (mCurrentp) - { - for (U32 i=0; i<n; i++) - { - mCurrentp = mCurrentp->mNextp; - if (!mCurrentp) - { - break; - } - } - } - - if (mCurrentp) - { - // bump mQueuep down the list - mQueuep = mCurrentp->mNextp; - return mCurrentp->mDatap; - } - else - { - mQueuep = NULL; - return NULL; - } -} - - -// reset the list and return the last data in it, -// set mCurrentp to that node and bump mQueuep up the list -template <class DATA_TYPE> -DATA_TYPE* LLDoubleLinkedList<DATA_TYPE>::getLastData() -{ - mQueuep = mTail.mPrevp; - mCurrentp = mQueuep; - if (mQueuep) - { - mQueuep = mQueuep->mPrevp; - return mCurrentp->mDatap; - } - else - { - return NULL; - } -} - - -// return the data in mQueuep, -// set mCurrentp to mQueuep and bump mQueuep down the list -template <class DATA_TYPE> -DATA_TYPE* LLDoubleLinkedList<DATA_TYPE>::getNextData() -{ - if (mQueuep) - { - mCurrentp = mQueuep; - mQueuep = mQueuep->mNextp; - return mCurrentp->mDatap; - } - else - { - return NULL; - } -} - - -// return the data in mQueuep, -// set mCurrentp to mQueuep and bump mQueuep up the list -template <class DATA_TYPE> -DATA_TYPE* LLDoubleLinkedList<DATA_TYPE>::getPreviousData() -{ - if (mQueuep) - { - mCurrentp = mQueuep; - mQueuep = mQueuep->mPrevp; - return mCurrentp->mDatap; - } - else - { - return NULL; - } -} - - -// remove the Node at mCurrentp -// set mCurrentp to mQueuep, or NULL if (mCurrentp == mQueuep) -template <class DATA_TYPE> -void LLDoubleLinkedList<DATA_TYPE>::removeCurrentData() -{ - if (mCurrentp) - { - // if there is a next one, fix it - if (mCurrentp->mNextp) - { - mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp; - } - else // otherwise we are at end of list - { - mTail.mPrevp = mCurrentp->mPrevp; - } - - // if there is a previous one, fix it - if (mCurrentp->mPrevp) - { - mCurrentp->mPrevp->mNextp = mCurrentp->mNextp; - } - else // otherwise we are at beginning of list - { - mHead.mNextp = mCurrentp->mNextp; - } - - // remove the node - mCurrentp->removeData(); - delete mCurrentp; - mCount--; - - // check for redundant pointing - if (mCurrentp == mQueuep) - { - mCurrentp = mQueuep = NULL; - } - else - { - mCurrentp = mQueuep; - } - } -} - - -// delete the Node at mCurrentp -// set mCurrentp to mQueuep, or NULL if (mCurrentp == mQueuep) -template <class DATA_TYPE> -void LLDoubleLinkedList<DATA_TYPE>::deleteCurrentData() -{ - if (mCurrentp) - { - // remove the node - // if there is a next one, fix it - if (mCurrentp->mNextp) - { - mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp; - } - else // otherwise we are at end of list - { - mTail.mPrevp = mCurrentp->mPrevp; - } - - // if there is a previous one, fix it - if (mCurrentp->mPrevp) - { - mCurrentp->mPrevp->mNextp = mCurrentp->mNextp; - } - else // otherwise we are at beginning of list - { - mHead.mNextp = mCurrentp->mNextp; - } - - // remove the LLDoubleLinkedNode - mCurrentp->deleteData(); - delete mCurrentp; - mCount--; - - // check for redundant pointing - if (mCurrentp == mQueuep) - { - mCurrentp = mQueuep = NULL; - } - else - { - mCurrentp = mQueuep; - } - } -} - - -// remove the Node at mCurrentp and insert it into newlist -// set mCurrentp to mQueuep, or NULL if (mCurrentp == mQueuep) -template <class DATA_TYPE> -void LLDoubleLinkedList<DATA_TYPE>::moveCurrentData(LLDoubleLinkedList<DATA_TYPE> *newlist) -{ - if (mCurrentp) - { - // remove the node - // if there is a next one, fix it - if (mCurrentp->mNextp) - { - mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp; - } - else // otherwise we are at end of list - { - mTail.mPrevp = mCurrentp->mPrevp; - } - - // if there is a previous one, fix it - if (mCurrentp->mPrevp) - { - mCurrentp->mPrevp->mNextp = mCurrentp->mNextp; - } - else // otherwise we are at beginning of list - { - mHead.mNextp = mCurrentp->mNextp; - } - - // move the node to the new list - newlist->addNode(mCurrentp); - - // check for redundant pointing - if (mCurrentp == mQueuep) - { - mCurrentp = mQueuep = NULL; - } - else - { - mCurrentp = mQueuep; - } - } -} - - -// Inserts the node previous to mCurrentp -// set mCurrentp to mQueuep -template <class DATA_TYPE> -void LLDoubleLinkedList<DATA_TYPE>::insertNode(LLDoubleLinkedNode<DATA_TYPE> *nodep) -{ - // don't allow pointer to NULL to be passed - if (!nodep) - { - llerror("NULL pointer passed to LLDoubleLinkedList::insertNode()", 0); - } - if (!nodep->mDatap) - { - llerror("NULL data pointer passed to LLDoubleLinkedList::insertNode()", 0); - } - - if (mCurrentp) - { - if (mCurrentp->mPrevp) - { - nodep->mPrevp = mCurrentp->mPrevp; - nodep->mNextp = mCurrentp; - mCurrentp->mPrevp->mNextp = nodep; - mCurrentp->mPrevp = nodep; - } - else // at beginning of list - { - nodep->mPrevp = NULL; - nodep->mNextp = mCurrentp; - mHead.mNextp = nodep; - mCurrentp->mPrevp = nodep; - } - mCurrentp = mQueuep; - } - else // add to front of list - { - addNode(nodep); - } -} - - -// insert the data in front of mCurrentp -// set mCurrentp to mQueuep -template <class DATA_TYPE> -void LLDoubleLinkedList<DATA_TYPE>::insertData(DATA_TYPE *data) -{ - if (!data) - { - llerror("NULL data pointer passed to LLDoubleLinkedList::insertNode()", 0); - } - LLDoubleLinkedNode<DATA_TYPE> *node = new LLDoubleLinkedNode<DATA_TYPE>(data); - insertNode(node); - mCount++; -} - - -// if mCurrentp has a previous node then : -// * swaps mCurrentp with its previous -// * set mCurrentp to mQueuep -// otherwise does nothing -template <class DATA_TYPE> -void LLDoubleLinkedList<DATA_TYPE>::swapCurrentWithPrevious() -{ - if (mCurrentp) - { - if (mCurrentp->mPrevp) - { - // Pull mCurrentp out of list - mCurrentp->mPrevp->mNextp = mCurrentp->mNextp; - if (mCurrentp->mNextp) - { - mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp; - } - else // mCurrentp was at end of list - { - mTail.mPrevp = mCurrentp->mPrevp; - } - - // Fix mCurrentp's pointers - mCurrentp->mNextp = mCurrentp->mPrevp; - mCurrentp->mPrevp = mCurrentp->mNextp->mPrevp; - mCurrentp->mNextp->mPrevp = mCurrentp; - - if (mCurrentp->mPrevp) - { - // Fix the backward pointer of mCurrentp's new previous - mCurrentp->mPrevp->mNextp = mCurrentp; - } - else // mCurrentp is now at beginning of list - { - mHead.mNextp = mCurrentp; - } - - // Set the list back to the way it was - mCurrentp = mQueuep; - } - } -} - - -// if mCurrentp has a next node then : -// * swaps mCurrentp with its next -// * set mCurrentp to mQueuep -// otherwise does nothing -template <class DATA_TYPE> -void LLDoubleLinkedList<DATA_TYPE>::swapCurrentWithNext() -{ - if (mCurrentp) - { - if (mCurrentp->mNextp) - { - // Pull mCurrentp out of list - mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp; - if (mCurrentp->mPrevp) - { - mCurrentp->mPrevp->mNextp = mCurrentp->mNextp; - } - else // mCurrentp was at beginning of list - { - mHead.mNextp = mCurrentp->mNextp; - } - - // Fix mCurrentp's pointers - mCurrentp->mPrevp = mCurrentp->mNextp; - mCurrentp->mNextp = mCurrentp->mPrevp->mNextp; - mCurrentp->mPrevp->mNextp = mCurrentp; - - if (mCurrentp->mNextp) - { - // Fix the back pointer of mCurrentp's new next - mCurrentp->mNextp->mPrevp = mCurrentp; - } - else // mCurrentp is now at end of list - { - mTail.mPrevp = mCurrentp; - } - - // Set the list back to the way it was - mCurrentp = mQueuep; - } - } -} - -// move mCurrentp to the front of the list -// set mCurrentp to mQueuep -template <class DATA_TYPE> -void LLDoubleLinkedList<DATA_TYPE>::moveCurrentToFront() -{ - if (mCurrentp) - { - // if there is a previous one, fix it - if (mCurrentp->mPrevp) - { - mCurrentp->mPrevp->mNextp = mCurrentp->mNextp; - } - else // otherwise we are at beginning of list - { - // check for redundant pointing - if (mCurrentp == mQueuep) - { - mCurrentp = mQueuep = NULL; - } - else - { - mCurrentp = mQueuep; - } - return; - } - - // if there is a next one, fix it - if (mCurrentp->mNextp) - { - mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp; - } - else // otherwise we are at end of list - { - mTail.mPrevp = mCurrentp->mPrevp; - } - - // add mCurrentp to beginning of list - mCurrentp->mNextp = mHead.mNextp; - mHead.mNextp->mPrevp = mCurrentp; // mHead.mNextp MUST be valid, - // or the list had only one node - // and we would have returned already - mCurrentp->mPrevp = NULL; - mHead.mNextp = mCurrentp; - - // check for redundant pointing - if (mCurrentp == mQueuep) - { - mCurrentp = mQueuep = NULL; - } - else - { - mCurrentp = mQueuep; - } - } - -} - -// move mCurrentp to the end of the list -// set mCurrentp to mQueuep -template <class DATA_TYPE> -void LLDoubleLinkedList<DATA_TYPE>::moveCurrentToEnd() -{ - if (mCurrentp) - { - // if there is a next one, fix it - if (mCurrentp->mNextp) - { - mCurrentp->mNextp->mPrevp = mCurrentp->mPrevp; - } - else // otherwise we are at end of list and we're done - { - // check for redundant pointing - if (mCurrentp == mQueuep) - { - mCurrentp = mQueuep = NULL; - } - else - { - mCurrentp = mQueuep; - } - return; - } - - // if there is a previous one, fix it - if (mCurrentp->mPrevp) - { - mCurrentp->mPrevp->mNextp = mCurrentp->mNextp; - } - else // otherwise we are at beginning of list - { - mHead.mNextp = mCurrentp->mNextp; - } - - // add mCurrentp to end of list - mCurrentp->mPrevp = mTail.mPrevp; - mTail.mPrevp->mNextp = mCurrentp; // mTail.mPrevp MUST be valid, - // or the list had only one node - // and we would have returned already - mCurrentp->mNextp = NULL; - mTail.mPrevp = mCurrentp; - - // check for redundant pointing - if (mCurrentp == mQueuep) - { - mCurrentp = mQueuep = NULL; - } - else - { - mCurrentp = mQueuep; - } - } -} - - -template <class DATA_TYPE> -void LLDoubleLinkedList<DATA_TYPE>::setInsertBefore(BOOL (*insert_before)(DATA_TYPE *first, DATA_TYPE *second) ) -{ - mInsertBefore = insert_before; -} - - -// add data in front of the first node for which mInsertBefore(datap, node->mDatap) returns TRUE -// set mCurrentp to mQueuep -template <class DATA_TYPE> -BOOL LLDoubleLinkedList<DATA_TYPE>::addDataSorted(DATA_TYPE *datap) -{ - // don't allow NULL to be passed to addData() - if (!datap) - { - llerror("NULL pointer passed to LLDoubleLinkedList::addDataSorted()", 0); - } - - // has mInsertBefore not been set? - if (!mInsertBefore) - { - addData(datap); - return FALSE; - } - - // is the list empty? - if (!mHead.mNextp) - { - addData(datap); - return TRUE; - } - - // Note: this step has been added so that the behavior of LLDoubleLinkedList - // is as rigorous as the LLLinkedList class about adding duplicate nodes. - // Duplicate nodes can cause a problem when sorting if mInsertBefore(foo, foo) - // returns TRUE. However, if mInsertBefore(foo, foo) returns FALSE, then there - // shouldn't be any reason to exclude duplicate nodes (as we do here). - if (checkData(datap)) - { - return FALSE; - } - - mCurrentp = mHead.mNextp; - while (mCurrentp) - { - // check to see if datap is already in the list - if (datap == mCurrentp->mDatap) - { - return FALSE; - } - else if (mInsertBefore(datap, mCurrentp->mDatap)) - { - insertData(datap); - return TRUE; - } - mCurrentp = mCurrentp->mNextp; - } - - addDataAtEnd(datap); - return TRUE; -} - - -// bubble-sort until sorted and return TRUE if anything was sorted -// leaves mQueuep pointing at last node that was swapped with its mNextp -// -// NOTE: if you find this function looping for really long times, then you -// probably need to check your implementation of mInsertBefore(a,b) and make -// sure it does not return TRUE when (a == b)! -template <class DATA_TYPE> -BOOL LLDoubleLinkedList<DATA_TYPE>::bubbleSort() -{ - BOOL b_swapped = FALSE; - U32 count = 0; - while (lazyBubbleSort()) - { - b_swapped = TRUE; - if (count++ > 0x7FFFFFFF) - { - llwarning("LLDoubleLinkedList::bubbleSort() : too many passes...", 1); - llwarning(" make sure the mInsertBefore(a, b) does not return TRUE for a == b", 1); - break; - } - } - return b_swapped; -} - - -// do a single bubble-sort pass and return TRUE if anything was sorted -// leaves mQueuep pointing at last node that was swapped with its mNextp -template <class DATA_TYPE> -BOOL LLDoubleLinkedList<DATA_TYPE>::lazyBubbleSort() -{ - // has mInsertBefore been set? - if (!mInsertBefore) - { - return FALSE; - } - - // is list empty? - mCurrentp = mHead.mNextp; - if (!mCurrentp) - { - return FALSE; - } - - BOOL b_swapped = FALSE; - - // the sort will exit after 0x7FFFFFFF nodes or the end of the list, whichever is first - S32 length = 0x7FFFFFFF; - S32 count = 0; - - while (mCurrentp && mCurrentp->mNextp && count<length) - { - if (mInsertBefore(mCurrentp->mNextp->mDatap, mCurrentp->mDatap)) - { - b_swapped = TRUE; - mQueuep = mCurrentp; - swapCurrentWithNext(); // sets mCurrentp to mQueuep - } - count++; - mCurrentp = mCurrentp->mNextp; - } - - return b_swapped; -} - - -template <class DATA_TYPE> -BOOL LLDoubleLinkedList<DATA_TYPE>::pushState() -{ - if (mStateStackDepth < LLDOUBLE_LINKED_LIST_STATE_STACK_DEPTH) - { - *(mQueuepStack + mStateStackDepth) = mQueuep; - *(mCurrentpStack + mStateStackDepth) = mCurrentp; - mStateStackDepth++; - return TRUE; - } - return FALSE; -} - - -template <class DATA_TYPE> -BOOL LLDoubleLinkedList<DATA_TYPE>::popState() -{ - if (mStateStackDepth > 0) - { - mStateStackDepth--; - mQueuep = *(mQueuepStack + mStateStackDepth); - mCurrentp = *(mCurrentpStack + mStateStackDepth); - return TRUE; - } - return FALSE; -} - - -template <class DATA_TYPE> -void LLDoubleLinkedList<DATA_TYPE>::clearStateStack() -{ - mStateStackDepth = 0; -} - -////////////////////////////////////////////////////////////////////////////////////////// -// private members -////////////////////////////////////////////////////////////////////////////////////////// - -// add node to beginning of list -// set mCurrentp to mQueuep -template <class DATA_TYPE> -void LLDoubleLinkedList<DATA_TYPE>::addNode(LLDoubleLinkedNode<DATA_TYPE> *nodep) -{ - // add the node to the front of the list - nodep->mPrevp = NULL; - nodep->mNextp = mHead.mNextp; - mHead.mNextp = nodep; - - // if there's something in the list, fix its back pointer - if (nodep->mNextp) - { - nodep->mNextp->mPrevp = nodep; - } - else // otherwise fix the tail node - { - mTail.mPrevp = nodep; - } - - mCurrentp = mQueuep; -} - - -// add node to end of list -// set mCurrentp to mQueuep -template <class DATA_TYPE> -void LLDoubleLinkedList<DATA_TYPE>::addNodeAtEnd(LLDoubleLinkedNode<DATA_TYPE> *node) -{ - // add the node to the end of the list - node->mNextp = NULL; - node->mPrevp = mTail.mPrevp; - mTail.mPrevp = node; - - // if there's something in the list, fix its back pointer - if (node->mPrevp) - { - node->mPrevp->mNextp = node; - } - else // otherwise fix the head node - { - mHead.mNextp = node; - } - - mCurrentp = mQueuep; -} - - -// randomly move nodes in the list for DEBUG (or Discordian) purposes -// sets mCurrentp and mQueuep to top of list -template <class DATA_TYPE> -void LLDoubleLinkedList<DATA_TYPE>::scramble() -{ - S32 random_number; - DATA_TYPE *datap = getFirstData(); - while(datap) - { - random_number = ll_rand(5); - - if (0 == random_number) - { - removeCurrentData(); - addData(datap); - } - else if (1 == random_number) - { - removeCurrentData(); - addDataAtEnd(datap); - } - else if (2 == random_number) - { - swapCurrentWithPrevious(); - } - else if (3 == random_number) - { - swapCurrentWithNext(); - } - datap = getNextData(); - } - mQueuep = mHead.mNextp; - mCurrentp = mQueuep; -} - -template <class DATA_TYPE> -BOOL LLDoubleLinkedList<DATA_TYPE>::isEmpty() -{ - return (mCount == 0); -} - - -#endif |