Liste template doublement chainée

Télécharger le projet
Commenter

Description

Si vous développez sous Windows et utilisez intensivement les classes MFC vous savez peut-être déjà qu?elles peuvent s?avérer lourdes et parfois même inutilisables dans certains contextes.

Un jour j?ai découvert BeOS sur les conseils d?un ami. Qu?elle ne fut pas ma surprise de découvrir une API bien plus fournie et robuste.

Voici donc une liste template doublement chaînée qui s?inspire fortement de ce qu?on peut trouver sous BeOS.

Le seul défaut qu?a Blist par rapport à la classe CList des MFC c?est de ne pas permettre d?effectuer des parcours simultanés. Cependant étant donné que cela peut s?avérer être un exercice particulièrement déconseillé ce désavantage n?en est plus un.

Source / Exemple : 


#ifndef __BLIST_H__
#define __BLIST_H__

// Revision history
// -------------------
//
// 1.0.1 Added return of insertion index for AddHead and AddTail
//       Added SetAt
// 1.0.0 First release

#pragma once

#include <assert.h>

template <class T> class BList
{
protected:
	struct sListItem
	{
		T			item;
		sListItem	*pPrevItem;
		sListItem	*pNextItem;

		sListItem(const T &newItem)
		{
			item=newItem;
			pPrevItem=NULL;
			pNextItem=NULL;
		}
	};

	sListItem	*_pFirstItem;
	sListItem	*_pLastItem;
	sListItem	*_pCurItem;
	DWORD		_dwCount;

	void		copyList(const BList<T> &list);

public:
				BList();
				BList(const BList &list);
	virtual		~BList();

	// Adds an item to the head of the list.
	//
	// [in] const T &item : item to add.
	//
	// Returns index at which item was added.
	DWORD		AddHead(const T &item);
	// Adds an item to the tail of the list.
	//
	// [in] const T &item : item to add.
	//
	// Returns index at which item was added.
	DWORD		AddTail(const T &item);
	// Removes the selected item of the list
	void		Remove();
	// Removes all items of the list.
	void		RemoveAll();

	// Selects the first item of the list.
	void		SetFirst();
	// Selects the last item of the list.
	void		SetLast();
	// Selects the previous item of the list.
	//
	// Returns TRUE if there is one, FALSE otherwise.
	BOOL		SetPrev();
	// Selects the next item of the list.
	//
	// Returns TRUE if there is one, FALSE otherwise.
	BOOL		SetNext();
	// Selects the nth item of the list.
	void		SetAt(DWORD dwIdx);
	// Finds and selects an item of the list.
	//
	// [in] const T &item : item to find.
	//
	// Returns TRUE if an item was found.
	BOOL		Find(const T &item);

	// Get the value of the currently selected item.
	//
	// Returns the value of the currently selected item.
	T			Get() const;

	// Gets a reference to the currently selected item.
	T			&GetRef();

	// Sets the value of the currently selected item.
	void		Set(const T &item);

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

	BList<T>	&operator = (const BList<T> &list);
};

template <class T> void BList<T>::copyList(const BList<T> &list)
{
	sListItem	*pListCurItem;
	T			item;

	if(!IsEmpty())
		RemoveAll();

	if(list.IsEmpty())
		return;

	pListCurItem=list._pFirstItem;
	do
	{
		item=pListCurItem->item;
		AddTail(item);
	}
	while((pListCurItem=pListCurItem->pNextItem)!=NULL);
}

template <class T> BList<T>::BList()
{
	_pFirstItem=NULL;
	_pLastItem=NULL;
	_pCurItem=NULL;
	_dwCount=0;
}

template <class T> BList<T>::BList(const BList<T> &list)
{
	_pFirstItem=NULL;
	_pLastItem=NULL;
	_pCurItem=NULL;
	_dwCount=0;

	copyList(list);
}

template <class T> BList<T>::~BList()
{
	if(!IsEmpty())
		RemoveAll();
}

template <class T> DWORD BList<T>::AddHead(const T &item)
{
	sListItem	*pNewItem=new sListItem(item);

	// first item of list
	if(_pFirstItem==NULL)
	{
		_pFirstItem=pNewItem;
		_pLastItem=pNewItem;
	}
	// add it at begin of list
	else
	{
		pNewItem->pNextItem=_pFirstItem;
		_pFirstItem->pPrevItem=pNewItem;
		_pFirstItem=pNewItem;
	}
	_dwCount++;

	return 0;
}

template <class T> DWORD BList<T>::AddTail(const T &item)
{
	sListItem	*pNewItem=new sListItem(item);

	// first item of list
	if(_pFirstItem==NULL)
	{
		_pFirstItem=pNewItem;
		_pLastItem=pNewItem;
	}
	// add it at end of list
	else
	{
		_pLastItem->pNextItem=pNewItem;
		pNewItem->pPrevItem=_pLastItem;
		_pLastItem=pNewItem;
	}
	_dwCount++;

	return _dwCount-1;
}

template <class T> void BList<T>::Remove()
{
	assert(_pCurItem!=NULL);

	sListItem	*pOldItem=_pCurItem;	

	// last item of list
	if(_pFirstItem==_pLastItem)
		_pFirstItem=_pLastItem=NULL;
	// first item of list
	else if(_pCurItem==_pFirstItem)
	{
		SetNext();

		_pCurItem->pPrevItem=NULL;
		_pFirstItem=_pCurItem;
	} 
	else
	{
		SetPrev();

		_pCurItem->pNextItem=pOldItem->pNextItem;
		if(pOldItem!=_pLastItem)
			pOldItem->pNextItem->pPrevItem=pOldItem->pPrevItem;
		else
			_pLastItem=_pCurItem;

		SetNext();
	}
	_dwCount--;

	delete pOldItem;
}

template <class T> void BList<T>::RemoveAll()
{
	assert(_pFirstItem!=NULL);
	
	for(SetFirst() ; !IsEmpty() ; )
		Remove();
}

template <class T> void BList<T>::SetFirst()
{
	assert(_pFirstItem!=NULL);

	_pCurItem=_pFirstItem;
}

template <class T> void BList<T>::SetLast()
{
	assert(_pLastItem!=NULL);

	_pCurItem=_pLastItem;
}

template <class T> BOOL BList<T>::SetPrev()
{
	assert(_pCurItem!=NULL);

	_pCurItem=_pCurItem->pPrevItem;
	return _pCurItem!=NULL;
}

template <class T> BOOL BList<T>::SetNext()
{
	assert(_pCurItem!=NULL);

	_pCurItem=_pCurItem->pNextItem;
	return _pCurItem!=NULL;
}

template <class T> void BList<T>::SetAt(DWORD dwIdx)
{
	assert(dwIdx>=0 && dwIdx<_dwCount);
	DWORD	dwCpt;

	for(dwCpt=0, SetFirst() ; dwCpt<dwIdx ; dwCpt++)
		SetNext();
}

template <class T> BOOL BList<T>::Find(const T &item)
{
	assert(_pFirstItem!=NULL);

	for(SetFirst() ; _pCurItem->item!=item ; )
	{
		if(!SetNext())
			return FALSE;
	}
	return TRUE;
}

template <class T> T BList<T>::Get() const
{
	assert(_pCurItem!=NULL);

	return _pCurItem->item;
}

template <class T> T &BList<T>::GetRef()
{
	assert(_pCurItem!=NULL);

	return _pCurItem->item;
}

template <class T> void BList<T>::Set(const T &item)
{
	assert(_pCurItem!=NULL);

	_pCurItem->item=item;
}

template <class T> BOOL BList<T>::IsEmpty() const
{
	return (_pFirstItem==NULL);
}

template <class T> DWORD BList<T>::Count() const
{
	return _dwCount;
}

template <class T> BList<T> &BList<T>::operator = (const BList<T> &list)
{
	copyList(list);

	return *this;
}

#endif

Conclusion :


Vous pouvez trouver les mises à jour sur mon site http://perso.club-internet.fr/sfeldis. Pour une explication visitez : http://perso.club-internet.fr/sfeldis/langages/c++/blist/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)