/** 
 * @file llskipmap.h
 * @brief Associative container based on the skiplist algorithm.
 *
 * $LicenseInfo:firstyear=2003&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_LLSKIPMAP_H
#define LL_LLSKIPMAP_H

#include "llerror.h"

template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH = 8> 
class LLSkipMap
{
public:
	// basic constructor
	LLSkipMap();

	// basic constructor including sorter
	LLSkipMap(BOOL	(*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second), 
			   BOOL	(*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second));

	~LLSkipMap();

	void setInsertFirst(BOOL (*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second));
	void setEquals(BOOL (*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second));

	DATA_TYPE &addData(const INDEX_TYPE &index, DATA_TYPE datap);
	DATA_TYPE &addData(const INDEX_TYPE &index);
	DATA_TYPE &getData(const INDEX_TYPE &index);
	DATA_TYPE &operator[](const INDEX_TYPE &index);

	// If index present, returns data.
	// If index not present, adds <index,NULL> and returns NULL.
	DATA_TYPE &getData(const INDEX_TYPE &index, BOOL &b_new_entry);

	// Returns TRUE if data present in map.
	BOOL checkData(const INDEX_TYPE &index);

	// Returns TRUE if key is present in map. This is useful if you
	// are potentially storing NULL pointers in the map
	BOOL checkKey(const INDEX_TYPE &index);

	// If there, returns the data.
	// If not, returns NULL.
	// Never adds entries to the map.
	DATA_TYPE getIfThere(const INDEX_TYPE &index);

	INDEX_TYPE reverseLookup(const DATA_TYPE datap);

	// returns number of items in the list
	S32 getLength(); // WARNING!  getLength is O(n), not O(1)!

	BOOL removeData(const INDEX_TYPE &index);

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

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

	// return the data currently pointed to
	DATA_TYPE	getCurrentDataWithoutIncrement();

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

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

	INDEX_TYPE	getNextKey();

	// return the key currently pointed to
	INDEX_TYPE	getCurrentKeyWithoutIncrement();

	// The internal iterator is at the end of the list.
	BOOL		notDone() const;

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

	void deleteCurrentData();

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

	INDEX_TYPE	getFirstKey();

	class LLSkipMapNode
	{
	public:
		LLSkipMapNode()
		{
			S32 i;
			for (i = 0; i < BINARY_DEPTH; i++)
			{
				mForward[i] = NULL;
			}

			U8  *zero = (U8 *)&mIndex;

			for (i = 0; i < (S32)sizeof(INDEX_TYPE); i++)
			{
				*(zero + i) = 0;
			}

			zero = (U8 *)&mData;

			for (i = 0; i < (S32)sizeof(DATA_TYPE); i++)
			{
				*(zero + i) = 0;
			}
		}

		LLSkipMapNode(const INDEX_TYPE &index)
		:	mIndex(index)
		{

			S32 i;
			for (i = 0; i < BINARY_DEPTH; i++)
			{
				mForward[i] = NULL;
			}

			U8 *zero = (U8 *)&mData;

			for (i = 0; i < (S32)sizeof(DATA_TYPE); i++)
			{
				*(zero + i) = 0;
			}
		}

		LLSkipMapNode(const INDEX_TYPE &index, DATA_TYPE datap)
		:	mIndex(index)
		{

			S32 i;
			for (i = 0; i < BINARY_DEPTH; i++)
			{
				mForward[i] = NULL;
			}

			mData = datap;
		}

		~LLSkipMapNode()
		{
		}


		INDEX_TYPE					mIndex;
		DATA_TYPE					mData;
		LLSkipMapNode				*mForward[BINARY_DEPTH];

	private:
		// Disallow copying of LLSkipMapNodes by not implementing these methods.
		LLSkipMapNode(const LLSkipMapNode &);
		LLSkipMapNode &operator=(const LLSkipMapNode &rhs);
	};

	static BOOL	defaultEquals(const INDEX_TYPE &first, const INDEX_TYPE &second)
	{
		return first == second;
	}

private:
	// don't generate implicit copy constructor or copy assignment
	LLSkipMap(const LLSkipMap &);
	LLSkipMap &operator=(const LLSkipMap &);

private:
	LLSkipMapNode				mHead;
	LLSkipMapNode				*mUpdate[BINARY_DEPTH];
	LLSkipMapNode				*mCurrentp;
	LLSkipMapNode				*mCurrentOperatingp;
	S32							mLevel;
	BOOL						(*mInsertFirst)(const INDEX_TYPE &first, const INDEX_TYPE &second);
	BOOL						(*mEquals)(const INDEX_TYPE &first, const INDEX_TYPE &second);
	S32							mNumberOfSteps;
};

//////////////////////////////////////////////////
//
// LLSkipMap implementation
//

template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::LLSkipMap()
	:	mInsertFirst(NULL),
		mEquals(defaultEquals)
{
	llstatic_assert(BINARY_DEPTH >= 2, "Skipmaps must have binary depth of at least 2");

	S32 i;
	for (i = 0; i < BINARY_DEPTH; i++)
	{
		mUpdate[i] = NULL;
	}
	mLevel = 1;
	mCurrentp = *(mHead.mForward);
	mCurrentOperatingp = *(mHead.mForward);
}

template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::LLSkipMap(BOOL	(*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second), 
			   BOOL	(*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second)) 
	:	mInsertFirst(insert_first),
		mEquals(equals)
{
	llstatic_assert(BINARY_DEPTH >= 2, "Skipmaps must have binary depth of at least 2");

	mLevel = 1;
	S32 i;
	for (i = 0; i < BINARY_DEPTH; i++)
	{
		mHead.mForward[i] = NULL;
		mUpdate[i] = NULL;
	}
	mCurrentp = *(mHead.mForward);
	mCurrentOperatingp = *(mHead.mForward);
}

template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::~LLSkipMap()
{
	removeAllData();
}

template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::setInsertFirst(BOOL (*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second))
{
	mInsertFirst = insert_first;
}

template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::setEquals(BOOL (*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second))
{
	mEquals = equals;
}

template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::addData(const INDEX_TYPE &index, DATA_TYPE datap)
{
	S32			level;
	LLSkipMapNode	*current = &mHead;
	LLSkipMapNode	*temp;

	// find the pointer one in front of the one we want
	if (mInsertFirst)
	{
		for (level = mLevel - 1; level >= 0; level--)
		{
			temp = *(current->mForward + level);
			while (  (temp)
				   &&(mInsertFirst(temp->mIndex, index)))
			{
				current = temp;
				temp = *(current->mForward + level);
			}
			*(mUpdate + level) = current;
		}
	}
	else
	{
		for (level = mLevel - 1; level >= 0; level--)
		{
			temp = *(current->mForward + level);
			while (  (temp)
				   &&(temp->mIndex < index))
			{
				current = temp;
				temp = *(current->mForward + level);
			}
			*(mUpdate + level) = current;
		}
	}
	
	// we're now just in front of where we want to be . . . take one step forward
	current = *current->mForward;

	// replace the existing data if a node is already there
	if (  (current)
		&&(mEquals(current->mIndex, index)))
	{
		current->mData = datap;
		return current->mData;
	}

	// now add the new node
	S32 newlevel;
	for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++)
	{
		if (rand() & 1)
		{
			break;
		}
	}

	LLSkipMapNode *snode = new LLSkipMapNode(index, datap);

	if (newlevel > mLevel)
	{
		mHead.mForward[mLevel] = NULL;
		mUpdate[mLevel] = &mHead;
		mLevel = newlevel;
	}

	for (level = 0; level < newlevel; level++)
	{
		snode->mForward[level] = mUpdate[level]->mForward[level];
		mUpdate[level]->mForward[level] = snode;
	}
	return snode->mData;
}

template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::addData(const INDEX_TYPE &index)
{
	S32			level;
	LLSkipMapNode	*current = &mHead;
	LLSkipMapNode	*temp;

	// find the pointer one in front of the one we want
	if (mInsertFirst)
	{
		for (level = mLevel - 1; level >= 0; level--)
		{
			temp = *(current->mForward + level);
			while (  (temp)
				   &&(mInsertFirst(temp->mIndex, index)))
			{
				current = temp;
				temp = *(current->mForward + level);
			}
			*(mUpdate + level) = current;
		}
	}
	else
	{
		for (level = mLevel - 1; level >= 0; level--)
		{
			temp = *(current->mForward + level);
			while (  (temp)
				   &&(temp->mIndex < index))
			{
				current = temp;
				temp = *(current->mForward + level);
			}
			*(mUpdate + level) = current;
		}
	}
	
	// we're now just in front of where we want to be . . . take one step forward
	current = *current->mForward;

	// now add the new node
	S32 newlevel;
	for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++)
	{
		if (rand() & 1)
			break;
	}

	LLSkipMapNode *snode = new LLSkipMapNode(index);

	if (newlevel > mLevel)
	{
		mHead.mForward[mLevel] = NULL;
		mUpdate[mLevel] = &mHead;
		mLevel = newlevel;
	}

	for (level = 0; level < newlevel; level++)
	{
		snode->mForward[level] = mUpdate[level]->mForward[level];
		mUpdate[level]->mForward[level] = snode;
	}
	return snode->mData;
}

template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getData(const INDEX_TYPE &index)
{
	S32			level;
	LLSkipMapNode	*current = &mHead;
	LLSkipMapNode	*temp;

	mNumberOfSteps = 0;

	// find the pointer one in front of the one we want
	if (mInsertFirst)
	{
		for (level = mLevel - 1; level >= 0; level--)
		{
			temp = *(current->mForward + level);
			while (  (temp)
				   &&(mInsertFirst(temp->mIndex, index)))
			{
				current = temp;
				temp = *(current->mForward + level);
				mNumberOfSteps++;
			}
			*(mUpdate + level) = current;
		}
	}
	else
	{
		for (level = mLevel - 1; level >= 0; level--)
		{
			temp = *(current->mForward + level);
			while (  (temp)
				   &&(temp->mIndex < index))
			{
				current = temp;
				temp = *(current->mForward + level);
				mNumberOfSteps++;
			}
			*(mUpdate + level) = current;
		}
	}
	
	// we're now just in front of where we want to be . . . take one step forward
	current = *current->mForward;
	mNumberOfSteps++;

	if (  (current)
		&&(mEquals(current->mIndex, index)))
	{
		
		return current->mData;
	}
	
	// now add the new node
	S32 newlevel;
	for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++)
	{
		if (rand() & 1)
			break;
	}

	LLSkipMapNode *snode = new LLSkipMapNode(index);

	if (newlevel > mLevel)
	{
		mHead.mForward[mLevel] = NULL;
		mUpdate[mLevel] = &mHead;
		mLevel = newlevel;
	}

	for (level = 0; level < newlevel; level++)
	{
		snode->mForward[level] = mUpdate[level]->mForward[level];
		mUpdate[level]->mForward[level] = snode;
	}
	
	return snode->mData;
}

template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::operator[](const INDEX_TYPE &index)
{
	
	return getData(index);
}

// If index present, returns data.
// If index not present, adds <index,NULL> and returns NULL.
template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline DATA_TYPE &LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getData(const INDEX_TYPE &index, BOOL &b_new_entry)
{
	S32			level;
	LLSkipMapNode	*current = &mHead;
	LLSkipMapNode	*temp;

	mNumberOfSteps = 0;

	// find the pointer one in front of the one we want
	if (mInsertFirst)
	{
		for (level = mLevel - 1; level >= 0; level--)
		{
			temp = *(current->mForward + level);
			while (  (temp)
				   &&(mInsertFirst(temp->mIndex, index)))
			{
				current = temp;
				temp = *(current->mForward + level);
				mNumberOfSteps++;
			}
			*(mUpdate + level) = current;
		}
	}
	else
	{
		for (level = mLevel - 1; level >= 0; level--)
		{
			temp = *(current->mForward + level);
			while (  (temp)
				   &&(temp->mIndex < index))
			{
				current = temp;
				temp = *(current->mForward + level);
				mNumberOfSteps++;
			}
			*(mUpdate + level) = current;
		}
	}
	
	// we're now just in front of where we want to be . . . take one step forward
	mNumberOfSteps++;
	current = *current->mForward;

	if (  (current)
		&&(mEquals(current->mIndex, index)))
	{
		
		return current->mData;
	}
	b_new_entry = TRUE;
	addData(index);
	
	return current->mData;
}

// Returns TRUE if data present in map.
template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline BOOL LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::checkData(const INDEX_TYPE &index)
{
	S32			level;
	LLSkipMapNode	*current = &mHead;
	LLSkipMapNode	*temp;

	// find the pointer one in front of the one we want
	if (mInsertFirst)
	{
		for (level = mLevel - 1; level >= 0; level--)
		{
			temp = *(current->mForward + level);
			while (  (temp)
				   &&(mInsertFirst(temp->mIndex, index)))
			{
				current = temp;
				temp = *(current->mForward + level);
			}
			*(mUpdate + level) = current;
		}
	}
	else
	{
		for (level = mLevel - 1; level >= 0; level--)
		{
			temp = *(current->mForward + level);
			while (  (temp)
				   &&(temp->mIndex < index))
			{
				current = temp;
				temp = *(current->mForward + level);
			}
			*(mUpdate + level) = current;
		}
	}
	
	// we're now just in front of where we want to be . . . take one step forward
	current = *current->mForward;

	if (current)
	{
		// Gets rid of some compiler ambiguity for the LLPointer<> templated class.
		if (current->mData)
		{
			return mEquals(current->mIndex, index);
		}
	}

	return FALSE;
}

// Returns TRUE if key is present in map. This is useful if you
// are potentially storing NULL pointers in the map
template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline BOOL LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::checkKey(const INDEX_TYPE &index)
{
	S32			level;
	LLSkipMapNode	*current = &mHead;
	LLSkipMapNode	*temp;

	// find the pointer one in front of the one we want
	if (mInsertFirst)
	{
		for (level = mLevel - 1; level >= 0; level--)
		{
			temp = *(current->mForward + level);
			while (  (temp)
				   &&(mInsertFirst(temp->mIndex, index)))
			{
				current = temp;
				temp = *(current->mForward + level);
			}
			*(mUpdate + level) = current;
		}
	}
	else
	{
		for (level = mLevel - 1; level >= 0; level--)
		{
			temp = *(current->mForward + level);
			while (  (temp)
				   &&(temp->mIndex < index))
			{
				current = temp;
				temp = *(current->mForward + level);
			}
			*(mUpdate + level) = current;
		}
	}
	
	// we're now just in front of where we want to be . . . take one step forward
	current = *current->mForward;

	if (current)
	{
		return mEquals(current->mIndex, index);
	}

	return FALSE;
}

// If there, returns the data.
// If not, returns NULL.
// Never adds entries to the map.
template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getIfThere(const INDEX_TYPE &index)
{
	S32			level;
	LLSkipMapNode	*current = &mHead;
	LLSkipMapNode	*temp;

	mNumberOfSteps = 0;

	// find the pointer one in front of the one we want
	if (mInsertFirst)
	{
		for (level = mLevel - 1; level >= 0; level--)
		{
			temp = *(current->mForward + level);
			while (  (temp)
				   &&(mInsertFirst(temp->mIndex, index)))
			{
				current = temp;
				temp = *(current->mForward + level);
				mNumberOfSteps++;
			}
			*(mUpdate + level) = current;
		}
	}
	else
	{
		for (level = mLevel - 1; level >= 0; level--)
		{
			temp = *(current->mForward + level);
			while (  (temp)
				   &&(temp->mIndex < index))
			{
				current = temp;
				temp = *(current->mForward + level);
				mNumberOfSteps++;
			}
			*(mUpdate + level) = current;
		}
	}
	
	// we're now just in front of where we want to be . . . take one step forward
	mNumberOfSteps++;
	current = *current->mForward;

	if (current)
	{
		if (mEquals(current->mIndex, index))
		{
			return current->mData;
		}
	}

	// Avoid Linux compiler warning on returning NULL.
	return DATA_TYPE();
}

template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline INDEX_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::reverseLookup(const DATA_TYPE datap)
{
	LLSkipMapNode	*current = &mHead;

	while (current)
	{
		if (datap == current->mData)
		{
			
			return current->mIndex;
		}
		current = *current->mForward;
	}

	// not found! return NULL
	return INDEX_TYPE();
}

// returns number of items in the list
template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline S32 LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getLength()
{
	U32	length = 0;
	for (LLSkipMapNode* temp = *(mHead.mForward); temp != NULL; temp = temp->mForward[0])
	{
		length++;
	}
	
	return length;
}

template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline BOOL LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::removeData(const INDEX_TYPE &index)
{
	S32			level;
	LLSkipMapNode	*current = &mHead;
	LLSkipMapNode	*temp;

	// find the pointer one in front of the one we want
	if (mInsertFirst)
	{
		for (level = mLevel - 1; level >= 0; level--)
		{
			temp = *(current->mForward + level);
			while (  (temp)
				   &&(mInsertFirst(temp->mIndex, index)))
			{
				current = temp;
				temp = *(current->mForward + level);
			}
			*(mUpdate + level) = current;
		}
	}
	else
	{
		for (level = mLevel - 1; level >= 0; level--)
		{
			temp = *(current->mForward + level);
			while (  (temp)
				   &&(temp->mIndex < index))
			{
				current = temp;
				temp = *(current->mForward + level);
			}
			*(mUpdate + level) = current;
		}
	}
	
	// we're now just in front of where we want to be . . . take one step forward
	current = *current->mForward;

	if (!current)
	{
		// empty list or beyond the end!
		
		return FALSE;
	}

	// is this the one we want?
	if (!mEquals(current->mIndex, index))
	{
		// nope!
		
		return FALSE;
	}
	else
	{
		// do we need to fix current or currentop?
		if (current == mCurrentp)
		{
			mCurrentp = *current->mForward;
		}

		if (current == mCurrentOperatingp)
		{
			mCurrentOperatingp = *current->mForward;
		}
		// yes it is!  change pointers as required
		for (level = 0; level < mLevel; level++)
		{
			if (*((*(mUpdate + level))->mForward + level) != current)
			{
				// cool, we've fixed all the pointers!
				break;
			}
			*((*(mUpdate + level))->mForward + level) = *(current->mForward + level);
		}

		delete current;

		// clean up mHead
		while (  (mLevel > 1)
			   &&(!*(mHead.mForward + mLevel - 1)))
		{
			mLevel--;
		}
	}
	
	return TRUE;
}


// remove all nodes from the list but do not delete data
template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::removeAllData()
{
	LLSkipMapNode *temp;
	// reset mCurrentp
	mCurrentp = *(mHead.mForward);

	while (mCurrentp)
	{
		temp = mCurrentp->mForward[0];
		delete mCurrentp;
		mCurrentp = temp;
	}

	S32 i;
	for (i = 0; i < BINARY_DEPTH; i++)
	{
		mHead.mForward[i] = NULL;
		mUpdate[i] = NULL;
	}

	mCurrentp = *(mHead.mForward);
	mCurrentOperatingp = *(mHead.mForward);
}


// place mCurrentp on first node
template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::resetList()
{
	mCurrentp = *(mHead.mForward);
	mCurrentOperatingp = *(mHead.mForward);
}


// return the data currently pointed to
template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getCurrentDataWithoutIncrement()
{
	if (mCurrentOperatingp)
	{
		return mCurrentOperatingp->mData;
	}
	else
	{
		return DATA_TYPE();
	}
}

// return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp
template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getCurrentData()
{
	if (mCurrentp)
	{
		mCurrentOperatingp = mCurrentp;
		mCurrentp = mCurrentp->mForward[0];
		return mCurrentOperatingp->mData;
	}
	else
	{
		// Basic types, like int, have default constructors that initialize
		// them to zero.  g++ 2.95 supports this.  "int()" is zero.
		// This also is nice for LLUUID()
		return DATA_TYPE();
	}
}

// same as getCurrentData() but a more intuitive name for the operation
template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getNextData()
{
	if (mCurrentp)
	{
		mCurrentOperatingp = mCurrentp;
		mCurrentp = mCurrentp->mForward[0];
		return mCurrentOperatingp->mData;
	}
	else
	{
		// Basic types, like int, have default constructors that initialize
		// them to zero.  g++ 2.95 supports this.  "int()" is zero.
		// This also is nice for LLUUID()
		return DATA_TYPE();
	}
}

template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline INDEX_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getNextKey()
{
	if (mCurrentp)
	{
		mCurrentOperatingp = mCurrentp;
		mCurrentp = mCurrentp->mForward[0];
		return mCurrentOperatingp->mIndex;
	}
	else
	{
		return mHead.mIndex;
	}
}

// return the key currently pointed to
template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline INDEX_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getCurrentKeyWithoutIncrement()
{
	if (mCurrentOperatingp)
	{
		return mCurrentOperatingp->mIndex;
	}
	else
	{
		// See comment for getNextData()
		return INDEX_TYPE();
	}
}

template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline BOOL LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::notDone() const
{
	if (mCurrentOperatingp)
	{
		return TRUE;
	}
	else
	{
		return FALSE;
	}
}


// remove the Node at mCurentOperatingp
// leave mCurrentp and mCurentOperatingp on the next entry
template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::removeCurrentData()
{
	if (mCurrentOperatingp)
	{
		removeData(mCurrentOperatingp->mIndex);
	}
}

template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline void LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::deleteCurrentData()
{
	if (mCurrentOperatingp)
	{
		deleteData(mCurrentOperatingp->mIndex);
	}
}

// reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp
template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline DATA_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getFirstData()
{
	mCurrentp = *(mHead.mForward);
	mCurrentOperatingp = *(mHead.mForward);
	if (mCurrentp)
	{
		mCurrentOperatingp = mCurrentp;
		mCurrentp = mCurrentp->mForward[0];
		return mCurrentOperatingp->mData;
	}
	else
	{
		// See comment for getNextData()
		return DATA_TYPE();
	}
}

template <class INDEX_TYPE, class DATA_TYPE, S32 BINARY_DEPTH>
inline INDEX_TYPE LLSkipMap<INDEX_TYPE, DATA_TYPE, BINARY_DEPTH>::getFirstKey()
{
	mCurrentp = *(mHead.mForward);
	mCurrentOperatingp = *(mHead.mForward);
	if (mCurrentp)
	{
		mCurrentOperatingp = mCurrentp;
		mCurrentp = mCurrentp->mForward[0];
		return mCurrentOperatingp->mIndex;
	}
	else
	{
		return mHead.mIndex;
	}
}

#endif