Template de skip-list.

Télécharger le projet
Commenter

Description

Une liste chaînée de type SkipList. C'est une structure de données mise au point par Bill Pugh (http://www.cs.umd.edu/users/pugh/) Mon implémentation en C++ est basée sur ses travaux.

Pour l'utiliser c'est tout simple il suffit d'inclure BSkipList.h.

Source / Exemple : 


#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

Conclusion :


Pour les mises à jour et explication visitez mon site http://perso.club-internet.fr/sfeldis. Pour une explication voir http://perso.club-internet.fr/sfeldis/langages/c++/bskiplist/mainFrame.html.
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (phenix13)