TEMPLATE DE SKIP-LIST.

#ifndef __BSKIPLIST_H__
#define __BSKIPLIST_H__

// Revision history
// -------------------
//
// 1.0.2 Remove : count was not decremented after item deletion
// 1.0.1 Remove : bad reorganisation corrected
// 1.0.0 First release

#pragma once

#include <wtypes.h>
#include <assert.h>

template <class K, class V> class BSkipList
{
protected:
	struct	sSkipListItem
	{
		K				_key;			// key for search purpose
		V				_value;			// value of the item
		sSkipListItem	**_pNextItem;	// next item

				sSkipListItem()		{}
		virtual	~sSkipListItem()	{ delete [] _pNextItem; }
	};

	sSkipListItem	*_pCurItem;
	sSkipListItem	*_pFirstItem;	// first item
	int				_nLevel;		// current level of list
	int				_nMaxLevel;

	DWORD			_nCount;

	void			init(int nMaxLevel);

	void			*add(const K &key, const V &value);

	void			copyList(const BSkipList<K,V> &list);

public:
					BSkipList(int nMaxLevel=10);
					BSkipList(const BSkipList<K,V> &list);
	virtual			~BSkipList();

	// Adds an item to the the list.
	//
	// [in] const K &key : key to add.
	// [in] const V &value : value to add.
	//
	// Returns TRUE if added, FALSE if there was a duplicate.
	BOOL			Add(const K &key, const V &value);

	// Removes an item by key.
	//
	// [in] const K &key : key to remove.
	//
	// Returns TRUE if removed, FALSE if the item wasn't found.	
	BOOL			Remove(const K &key);
	// Removes all items of the list.
	void			RemoveAll();

	// Selects the first item of the list.
	void			SetFirst();
	// Selects the next item of the list.
	//
	// Returns TRUE if there is one, FALSE otherwise.
	BOOL			SetNext();

	// Finds and selects an item of the list.
	//
	// [in] const K &key : key to find.
	//
	// Returns TRUE if an item was found.
	BOOL			Find(const K &key);

	// Gets the key from the current item.
	//
	// Returns key.
	K				GetKey();
	// Gets the value from the current item.
	//
	// Returns value.
	V				GetValue();

	// Returns TRUE if the list is empty, FALSE otherwise.
	BOOL			IsEmpty() const;
	// Returns the item count of the list.
	DWORD			Count() const;

	BSkipList<K,V>	&operator = (const BSkipList<K,V> &list);
};

template <class K, class V> void BSkipList<K,V>::init(int nMaxLevel)
{
	int	cpt;

	_nMaxLevel=nMaxLevel;
	_pFirstItem=new sSkipListItem;
	_pFirstItem->_pNextItem=new sSkipListItem *[_nMaxLevel+1];

	for(cpt=0 ; cpt<=_nMaxLevel ; cpt++)
		_pFirstItem->_pNextItem[cpt]=_pFirstItem;
	_nLevel=0;

	_pCurItem=NULL;
	_nCount=0;
}

template <class K, class V> void *BSkipList<K,V>::add(const K &key, const V &value)
{
	int				cpt,nNewLevel;
	sSkipListItem	**pUpdateArray=new sSkipListItem *[_nMaxLevel+1];
	sSkipListItem	*pCurItem;

	// find where to insert item
	for(pCurItem=_pFirstItem, cpt=_nLevel ; cpt>=0 ; cpt--)
	{
		while(pCurItem->_pNextItem[cpt]!=_pFirstItem && pCurItem->_pNextItem[cpt]->_key<key)
			pCurItem=pCurItem->_pNextItem[cpt];
		pUpdateArray[cpt]=pCurItem;
	}
	pCurItem=pCurItem->_pNextItem[0];

	// this item is already in list
	if(pCurItem!=_pFirstItem && pCurItem->_key==key)
	{
		delete [] pUpdateArray;
		return NULL;
	}

	// get new list level
	for(nNewLevel=0 ; rand()<RAND_MAX/2 && nNewLevel<_nMaxLevel ; nNewLevel++)
	{}
	if(nNewLevel>_nLevel)
	{
		for(cpt=_nLevel+1 ; cpt<=nNewLevel ; cpt++)
			pUpdateArray[cpt]=_pFirstItem;
		_nLevel=nNewLevel;
	}

	// create new item
	pCurItem=new sSkipListItem;
	pCurItem->_pNextItem=new sSkipListItem *[nNewLevel+1];
	pCurItem->_key=key;
	pCurItem->_value=value;

	// update next items pointers
	for(cpt=0 ; cpt<=nNewLevel ; cpt++)
	{
		pCurItem->_pNextItem[cpt]=pUpdateArray[cpt]->_pNextItem[cpt];
		pUpdateArray[cpt]->_pNextItem[cpt]=pCurItem;
	}

	delete [] pUpdateArray;

	_nCount++;

	return pCurItem;
}

template <class K, class V> void BSkipList<K,V>::copyList(const BSkipList<K,V> &list)
{
	if(!IsEmpty())
		RemoveAll();

	// max level is not the same, reallocate if needed
	if(_nMaxLevel!=list._nMaxLevel && _pFirstItem!=NULL)
	{
		delete _pFirstItem;
		_pFirstItem=NULL;
	}
	if(_pFirstItem==NULL)
		init(list._nMaxLevel);

	if(list.IsEmpty())
		return;

	sSkipListItem	*pFirstItem=list._pFirstItem;
	sSkipListItem	*pCurItem=pFirstItem->_pNextItem[0];
	sSkipListItem	*pAddedItem;

	for( ; pCurItem!=pFirstItem ; pCurItem=pCurItem->_pNextItem[0])
	{
		pAddedItem=(sSkipListItem *)add(pCurItem->_key,pCurItem->_value);
		if(list._pCurItem==pCurItem)
			_pCurItem=pAddedItem;
	}
}

template <class K, class V> BSkipList<K,V>::BSkipList(int nMaxLevel)
{
	init(nMaxLevel);
}

template <class K, class V> BSkipList<K,V>::BSkipList(const BSkipList<K,V> &list)
{
	_pCurItem=NULL;
	_pFirstItem=NULL;
	_nLevel=0;
	_nMaxLevel=0;
	_nCount=0;

	copyList(list);
}

template <class K, class V> BSkipList<K,V>::~BSkipList()
{
	RemoveAll();
	delete _pFirstItem;
}

template <class K, class V> BOOL BSkipList<K,V>::Add(const K &key, const V &value)
{
	return add(key,value)!=NULL;
}

template <class K, class V> BOOL BSkipList<K,V>::Remove(const K &key)
{
	int				cpt;
	sSkipListItem	**pUpdateArray=new sSkipListItem *[_nMaxLevel+1];
	sSkipListItem	*pCurItem;

	// search item to remove
	for(pCurItem=_pFirstItem, cpt=_nLevel ; cpt>=0 ; cpt--)
	{
		while(pCurItem->_pNextItem[cpt]!=_pFirstItem && pCurItem->_pNextItem[cpt]->_key<key)
			pCurItem=pCurItem->_pNextItem[cpt];
		pUpdateArray[cpt]=pCurItem;
	}
	pCurItem=pCurItem->_pNextItem[0];

	// reorder liste without this item
	if(pCurItem->_key==key)
	{
		for(cpt=0 ; cpt<=_nLevel ; cpt++)
		{
			if(pUpdateArray[cpt]->_pNextItem[cpt]==pCurItem)
				pUpdateArray[cpt]->_pNextItem[cpt]=pCurItem->_pNextItem[cpt];

		}
		delete pCurItem;
		_nCount--;
	}

	// correct list level
	while(_nLevel>0 && _pFirstItem->_pNextItem[_nLevel]!=NULL)
		_nLevel--;

	delete [] pUpdateArray;

	return TRUE;
}

template <class K, class V> void BSkipList<K,V>::RemoveAll()
{
	sSkipListItem	*pNextItem,*pCurItem;
	int				cpt;

	if(IsEmpty())
		return;

	// remove all
	for(pCurItem=_pFirstItem->_pNextItem[0] ; pCurItem!=_pFirstItem ; pCurItem=pNextItem)
	{
		pNextItem=pCurItem->_pNextItem[0];
		delete [] pCurItem;
	}

	// reinit of list
	for(cpt=0 ; cpt<=_nMaxLevel ; cpt++)
		_pFirstItem->_pNextItem[cpt]=_pFirstItem;
	_nLevel=0;
	_nCount=0;
	_pCurItem=NULL;
}

template <class K, class V> void BSkipList<K,V>::SetFirst()
{
	assert(_nCount);

	_pCurItem=_pFirstItem->_pNextItem[0];
}

template <class K, class V> BOOL BSkipList<K,V>::SetNext()
{
	assert(_pCurItem!=NULL);

	_pCurItem=_pCurItem->_pNextItem[0];

	if(_pCurItem!=_pFirstItem)
		return TRUE;
	_pCurItem=NULL;
	return FALSE;
}

template <class K, class V> BOOL BSkipList<K,V>::Find(const K &key)
{
	int				cpt;
	sSkipListItem	*pCurItem;

	// search item
	for(pCurItem=_pFirstItem, cpt=_nLevel ; cpt>=0 ; cpt--)
	{
		while(pCurItem->_pNextItem[cpt]!=_pFirstItem && pCurItem->_pNextItem[cpt]->_key<key)
			pCurItem=pCurItem->_pNextItem[cpt];
	}
	pCurItem=pCurItem->_pNextItem[0];

	// this item is not in list
	if(pCurItem==_pFirstItem || pCurItem->_key!=key)
		return FALSE;

	_pCurItem=pCurItem;

	return TRUE;
}

template <class K, class V> K BSkipList<K,V>::GetKey()
{
	assert(_pCurItem!=NULL);

	return _pCurItem->_key;
}

template <class K, class V> V BSkipList<K,V>::GetValue()
{
	assert(_pCurItem!=NULL);

	return _pCurItem->_value;
}

template <class K, class V> BOOL BSkipList<K,V>::IsEmpty() const
{
	return _nCount==0;
}

template <class K, class V> DWORD BSkipList<K,V>::Count() const
{
	return _nCount;
}

template <class K, class V> BSkipList<K,V> &BSkipList<K,V>::operator = (const BSkipList<K,V> &list)
{
	copyList(list);

	return *this;
}

#endif