utlist.h

vc6.0完整版

#ifndef __UTLIST_H__
#define __UTLIST_H__
/******************************************************************************
Microsoft D.T.C. (Distributed Transaction Coordinator)

Copyright 1995 Microsoft Corporation.  All Rights Reserved.

@doc

@module UTList.h  |

	Contains list ADT. 

@devnote None
-------------------------------------------------------------------------------
	@rev 1 | 12th Apr,95 | GaganC | Added StaticList & StaticListIterator	
	@rev 0 | 24th Jan,95 | GaganC | Created
*******************************************************************************/


typedef enum {
				EXCEPT_MEMORY=0,
			 	EXCEPT_UNKNOWN,
			 	EXCEPT_LOCKFAILED,
				EXCEPT_TROUBLE
			 }	EXCEPT;  


//---------- Forward Declarations -------------------------------------------
template <class T> class UTLink;
template <class T> class UTList;
template <class T> class UTListIterator;
template <class T> class UTStaticList;
template <class T> class UTStaticListIterator;

//-----**************************************************************-----
// @class template class
//		The UTIterator is an ABSTRACT BASE CLASS for ALL iterators. This
//		class defines the basic operation that all iterators must support
//		regardless of what type of collection it operates upon.
//
//-----**************************************************************-----
template <class T> class UTIterator
{
// @access Public members

public:

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// initialize iterator
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Initializes the iterator to the first position
	virtual BOOL	Init	(void) =0;

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// operators
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Retrieves the current element (pointed to by iterator)
	virtual T		operator()	(void) const =0;
	// @cmember Checks to see if iterator is in a valid position
	virtual BOOL	operator !	(void) const =0;
	// @cmember Moves the iterator forward
	virtual BOOL	operator ++ (int dummy) =0;
	// @cmember Assigns the current element a new value
	virtual void	operator =	(T	newValue) =0;
};

//-----**************************************************************-----
// @class Template class
//		The UTLink class is the backbone of a linked list. It holds the
//		actual data of type T (which is the list's data type) and points
//		to the next and previous elements in the list.
//		The class is entirely private to hide all functions and data from
//		everyone but it's friends - which are the UTList and UTListIterator.
//
// @tcarg class | T | data type to store in the link
//-----**************************************************************-----
template <class T> class UTLink
{
// @access Public members
public:

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// constructors/destructor
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Constructor
	UTLink (void);
	// @cmember Constructor
	UTLink (const T& LinkValue,UTLink< T > * Prev = NULL,UTLink< T > * Next = NULL);
	// @cmember Copy Constructor
	UTLink (const UTLink< T >&	CopyLink);
	// @cmember Destructor
	virtual ~UTLink (void);

	void Init (const T& LinkValue,UTLink< T > * Prev = NULL,UTLink< T > * Next = NULL);

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// operators
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Assignment operator
	virtual UTLink< T >& operator =	(const UTLink< T >&	AssignLink);

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// action protocol
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Adds a new element before this object
	UTLink< T > * AddBefore	(const T& newValue);
	// @cmember Adds a new element after this object
	UTLink< T > * AddAfter	(const T& newValue);

	// @cmember Remove this link from the specified list
	void		RemoveFromList (UTStaticList < T > * pStaticList);

public:
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// friends
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	friend class UTList< T >;
	friend class UTStaticList < T >;
	friend class UTListIterator< T >;
	friend class UTStaticListIterator <T>;

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// data members
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Value held in the link of type T
	T				m_Value;
	// @cmember Pointer to next link (in list)
	UTLink< T > *	m_pNextLink;
	// @cmember Pointer to previous link (in list)
	UTLink< T > *	m_pPrevLink;
};

//-----**************************************************************-----
// @class Template class
//		The UTList class consists of a pointer to the first and last
//		links along with a count of the number of elements in the list.
//		The Add method simply appends to the end of the list.
//		To add elements to a specific location in the list other than
//		the first or last positions, use the UTListIterator methods.
//		To create an ordered list, a user could inherit from the UTList
//		class and override Add to add elements in the correct order.
//		Of course, you would want to do something about the other
//		methods of adding members to the list.
//
// @tcarg class | T | data type to store in the list
//-----**************************************************************-----

template <class T> class UTList
{
// @access Public members
public:

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// constructors/destructor
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Consructor
	UTList	(void);
	// @cmember Copy Constructor
	UTList	(const UTList< T >& CopyList);
	// @cmember Destructor
	virtual ~UTList (void);

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// operators
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Assignment operator
	virtual UTList< T >&		operator =	(const UTList< T >& AssignList);

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// action protocol
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Add new value to the list
	virtual void			Add			(const T& newValue);
	// @cmember Insert new value at the front of the list
	virtual void			InsertFirst (const T& newValue);
	// @cmember Insert new value at the end of the list
	virtual void			InsertLast	(const T& newValue);
	// @cmember Remove all elements from the list
	virtual void			RemoveAll	(void);
	// @cmember Remove first element from the list
	virtual BOOL			RemoveFirst (T* pType);
	// @cmember Remove last element from the list
	virtual BOOL			RemoveLast	(T* pType);
	// @cmember Duplicate contents of entire list
	virtual UTList< T > *	Duplicate	(void);

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// state protocol
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Retrieve the first value via the out parameter
	virtual BOOL	FirstElement(T* pType) const;
	// @cmember Retrieve the last value via the out parameter
	virtual BOOL	LastElement (T* pType) const;
	// @cmember Does the list include this value?
	virtual BOOL	Includes	(const T& value);
	// @cmember Is the list empty?
	virtual BOOL	IsEmpty		(void) const;
	// @cmember Return the count of elements in the list
	virtual ULONG	GetCount	(void) const;

	virtual void	Init (void);
// @access Protected members
protected:

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// friends
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	friend class UTListIterator< T >;

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// data members
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Count of elements in the list
	ULONG			m_ulCount;
	// @cmember Pointer to the first link in the list
	UTLink< T > *	m_pFirstLink;
	// @cmember Pointer to the last link in the list
	UTLink< T > *	m_pLastLink;
};

//-----**************************************************************-----
// @class Template class
//		The UTStaticList class. This is similar to the UTList class except 
//		that it in this the links are all static. Links are provided, to
//		the various methods, they are never created or destroyed as they
//		have been preallocated.
//
// @tcarg class | T | data type to store in the list
//-----**************************************************************-----
template <class T> class UTStaticList
{
// @access Public members
public:

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// constructors/destructor
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Consructor
	UTStaticList	(void);
	// @cmember Copy Constructor
//	UTStaticList	(const UTStaticList< T >& CopyList);
	// @cmember Destructor
	virtual ~UTStaticList (void);

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// operators
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Assignment operator
//	virtual UTStaticList< T >&		operator =	(const UTStaticList< T >& AssignList);

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// action protocol
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Add new link to the list
	virtual void			Add			(UTLink <T> * pLink);
	// @cmember Insert new link at the front of the list
	virtual void			InsertFirst (UTLink <T> * pLink);
	// @cmember Insert new link at the end of the list
	virtual void			InsertLast	(UTLink <T> * pLink);
	// @cmember Remove all elements from the list
	virtual void			RemoveAll	(void);
	// @cmember Remove first element from the list
	virtual BOOL			RemoveFirst (UTLink <T> ** ppLink);
	// @cmember Remove last element from the list
	virtual BOOL			RemoveLast	(UTLink <T> ** ppLink);
	// @cmember Duplicate contents of entire list
//	virtual UTStaticList< T > *	Duplicate	(void);

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// state protocol
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Retrieve the first link via the out parameter
	virtual BOOL	FirstElement(UTLink <T> ** ppLink);
	// @cmember Retrieve the last link via the out parameter
	virtual BOOL	LastElement (UTLink <T> ** ppLink);
	// @cmember Does the list include this value?
//	virtual BOOL	Includes	(const UTLink <T> * pLink);
	// @cmember Is the list empty?
	virtual BOOL	IsEmpty		(void) const;
	// @cmember Return the count of elements in the list
	virtual ULONG	GetCount	(void) const;


	virtual void	Init (void);

// @access Protected members
public:

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// friends
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	friend class UTStaticListIterator <T>;

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// data members
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Count of elements in the list
	ULONG			m_ulCount;
	// @cmember Pointer to the first link in the list
	UTLink< T > *	m_pFirstLink;
	// @cmember Pointer to the last link in the list
	UTLink< T > *	m_pLastLink;
}; //End class UTStaticList





//-----**************************************************************-----
// @class Template class
//		The UTListIterator class implements the operations that an
//		iterator must support and includes some additional operations
//		that are useful in the context of a linked list.
//		Use AddBefore & AddAfter to add elements to a list based on the
//		iterator's current position within the list.
//
// @tcarg class | T | data type stored in list and type for iterator
// @base public | UTIterator
//-----**************************************************************-----
template <class T> class UTListIterator : public UTIterator< T >
{
// @access Public members
public:

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// constructors/destructor
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Constructor
	UTListIterator (UTList< T >&	List);
	// @cmember Copy constructor
	UTListIterator (const UTListIterator< T >&	CopyListItr);
	// @cmember Destructor
	virtual ~UTListIterator(void);

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// iterator protocol
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Initialize the iterator to the first link in list
	virtual BOOL	Init		(void);
	// @cmember Retrieve the value from the current link
	virtual T		operator () (void) const;
	// @cmember Does the iterator point to a valid link
	virtual BOOL	operator !	(void) const;
	// @cmember Move the iterator to the next link
	virtual BOOL	operator ++ (int dummy);
	// @cmember Assign the current link a new value
	virtual void	operator =	(T newValue);

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// additional protocol for list iterator
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Assignment operator
	virtual UTListIterator< T >& operator =	(const UTListIterator< T >& AssignListItr);
	// @cmember Move the iterator to the previous link
	virtual BOOL	operator --		(int dummy);
	// @cmember Remove the current link from the list
	virtual BOOL	RemoveCurrent	(T* pType);
	// @cmember Insert a new value before the iterator
	virtual void	InsertBefore	(const T& newValue);
	// @cmember Insert a new value after the iterator
	virtual void	InsertAfter		(const T& newValue);
	// @cmember Set the iterator at the first element of this value
	virtual BOOL	SetPosAt		(const T& value);

// @access Protected members
public:

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// data members
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Position of iterator in list
	UTLink< T > *	m_pCurrentLink;
	// @cmember One position before the current position
	UTLink< T > *	m_pPreviousLink;
	// @cmember List that is being iterated upon
	UTList< T >&		m_List;
};

//-----**************************************************************-----
// @class Template class
//		The UTStaticListIterator class implements the operations that an
//		iterator must support and includes some additional operations
//		that are useful in the context of a static linked list.
//		Use AddBefore & AddAfter to add elements to a list based on the
//		iterator's current position within the list.
//
// @tcarg class | T | data type stored in list and type for iterator
// @base public | UTIterator
//-----**************************************************************-----
template <class T> class UTStaticListIterator : public UTIterator< T >
{
// @access Public members
public:

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// constructors/destructor
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Constructor
	UTStaticListIterator (UTStaticList< T >&	StaticList);
	// @cmember Copy constructor
//	UTStaticListIterator (const UTStaticListIterator< T >&	CopyListItr);
	// @cmember Destructor
	virtual ~UTStaticListIterator(void);

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// iterator protocol
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// @cmember Initialize the iterator to the first link in list
	virtual BOOL	Init		(void);
	// @cmember Retrieve the value from the current link
	virtual T		operator () (void) const;
	// @cmember Does the iterator point to a valid link
	virtual BOOL	operator !	(void) const;
	// @cmember Move the iterator to the next link
	virtual BOOL	operator ++ (int dummy);
	// @cmember Assign the current link a new value
	virtual void	operator =	(T newValue);

	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	// additional protocol for list iterator
	//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~