Template de skip-list.

Soyez le premier à donner votre avis sur cette source.

Vue 5 227 fois - Téléchargée 98 fois

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.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

cs_tibur
Messages postés
101
Date d'inscription
samedi 9 février 2002
Statut
Membre
Dernière intervention
5 mai 2009
-
C'est dommage que cette source soit si mal notée : j'aime beaucoup cette structure.
Pour ce qui est des {BOOL,TRUE,FALSE}, c'est vrai que je prefere les {bool,true,false} (surtout pour du C++) ...
Tib
phenix13
Messages postés
4
Date d'inscription
jeudi 28 novembre 2002
Statut
Membre
Dernière intervention
5 décembre 2002
-
J'utilise DWORD et BOOL car je programme principalement avec Visual C++ sous Windows et que j'utilise les MFC. J'utilise ces types pour ne pas mixer différentes conventions d'écriture qui rendrait la relecture un peu difficile. Quand a ceux qui ne connaissent pas les types en question DWORD est un unsigned long et BOOL un int qui peut être aisément remplacé par le type bool.
cs_Kaid
Messages postés
950
Date d'inscription
mardi 2 octobre 2001
Statut
Membre
Dernière intervention
8 juillet 2006
-
Pourquoi utiliser les types BOOL et DWORD définis par Windows ?

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.