Liste template doublement chainée

0/5 (5 avis)

Vue 4 319 fois - Téléchargée 114 fois

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.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

trinitacs
Messages postés
249
Date d'inscription
mardi 16 juillet 2002
Statut
Membre
Dernière intervention
7 août 2003
1 -
Kaid << "Mais au fait, un héritage entre quelques classes ? "
Kaid >> En parlant d'héritage je pensais qu'il aurait pu faire une classe au lieu de la struct et ensuite faire un héritage ou un friend ou autre, bref. Enfin je n'avais jamais pensé à mélanger struct et classe dans un même code sources.
phenix13
Messages postés
4
Date d'inscription
jeudi 28 novembre 2002
Statut
Membre
Dernière intervention
5 décembre 2002
-
trinitacs: En fait j'ai mis une structure car je n'avais pas besoins de la sophistication d'une classe vu que la seule chose que j'utilise c'est le constructeur pour mettre les valeurs par défaut. Et de fait elle est déclarée protégée car elle est utilisée uniquement en interne et représente comme le dis Kaid un maillon du chainage.
cs_Kaid
Messages postés
949
Date d'inscription
mardi 2 octobre 2001
Statut
Membre
Dernière intervention
8 juillet 2006
-
trinitacs: la structure dans la classe sert à représenter un maillon du chainage. Il y a bien sur une relation entre la liste et les maillons mais tu ne peux absolument pas faire un héritage. Mais au fait, un héritage entre quelques classes ?
trinitacs
Messages postés
249
Date d'inscription
mardi 16 juillet 2002
Statut
Membre
Dernière intervention
7 août 2003
1 -
Avant ça j'avais jamais pensé à mettre une struct dans une classe. Pk t'as pas fait un héritage à la place? Il doit sûrement y avoir une bonne solution car j'ai du mal à lire quand il y a des template (je ne les utilise pas assez souvent, mais je devrais pour la réutilisation) de plus je en connais rien à BeOS. C'est juste par curiosité.
cs_tavernier
Messages postés
47
Date d'inscription
mardi 1 octobre 2002
Statut
Membre
Dernière intervention
3 juin 2003
-
Vous auriez au moins pu mettre les commentaires en français

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.