LIST.H

//----------------------------------------------------------------------------- 
// Microsoft OLE DB TABLECOPY Sample 
// Copyright (C) 1996 By Microsoft Corporation. 
// 
// @doc 
// 
// @module LIST.H 
// 
//----------------------------------------------------------------------------- 
#ifndef _LIST_H_ 
#define _LIST_H_ 
 
 
///////////////////////////////////////////////////////////////////////////// 
// Includes 
// 
///////////////////////////////////////////////////////////////////////////// 
#include "winmain.h" 
 
 
///////////////////////////////////////////////////////////////////////////// 
// Defines 
// 
///////////////////////////////////////////////////////////////////////////// 
#define POSITION CNode<TYPE>* 
 
 
///////////////////////////////////////////////////////////////////////////// 
// CNode 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> class CNode 
{ 
public: 
// constructors 
CNode(TYPE val, CNode* pPrevNode, CNode* pNextNode); 
 
// members 
TYPE     m_data;       // element data 
CNode*   m_pNextNode;  // next CNode 
CNode*   m_pPrevNode;  // prev CNode 
}; 
 
 
///////////////////////////////////////////////////////////////////////////// 
// CNode::CNode 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> CNode<TYPE>::CNode(TYPE data, CNode<TYPE>* pPrevNode, CNode<TYPE>* pNextNode) 
{ 
  //Constructor 
  m_data = data; 
  m_pPrevNode = pPrevNode; 
  m_pNextNode = pNextNode; 
} 
 
 
 
///////////////////////////////////////////////////////////////////////////// 
// CList 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> class CList 
{ 
  public: 
 
//constructors 
CList(); 
virtual ~CList(); 
 
//members 
 
//list modifying operations 
virtual POSITIONAddHead(TYPE element);// Add to Head 
virtual POSITIONAddTail(TYPE element);// Add to Tail 
 
virtual POSITIONInsertBefore(POSITION position, TYPE newdata);// Add before position 
virtual POSITIONInsertAfter(POSITION position, TYPE newdata);// Add after m_pItr 
 
virtual TYPERemoveHead();// Remove from Head 
virtual TYPERemoveTail();// Remove from Tail 
virtual voidRemoveAt(POSITION position);// RemoveAt position 
virtual voidRemoveAll();// Remove all elements 
 
//Seeking operations 
virtual POSITIONFind(TYPE element);        // Find element 
 
//Peek operations 
virtual TYPEGetHead();// Head element 
virtual TYPEGetTail();// Tail element 
virtual TYPEGetNext(POSITION position);// Next element 
virtual TYPEGetPrev(POSITION position);// Prev element 
 
//informational operations 
virtual BOOLIsEmpty();// IsEmpty 
virtual ULONGGetCount();// m_ulLengthgth of CList 
 
//data 
CNode<TYPE>*  m_pHeadNode;// Head of CList 
CNode<TYPE>*  m_pTailNode;// Tail of CList 
 
ULONGm_ulLength;// m_ulLengthgth of CList 
}; 
 
 
///////////////////////////////////////////////////////////////////////////// 
// CList::CList 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> CList<TYPE>::CList() 
{ 
//constructor 
m_pHeadNode = NULL; 
m_pTailNode = NULL; 
m_ulLength = 0; 
} 
 
///////////////////////////////////////////////////////////////////////////// 
// CList::~CList 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> CList<TYPE>::~CList()  
{ 
//Remove all elements 
RemoveAll(); 
} 
 
 
///////////////////////////////////////////////////////////////////////////// 
// CList::AddHead 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> POSITION CList<TYPE>::AddHead(TYPE element)  
{ 
//Add to the Head of the CList, (stack) 
CNode<TYPE>* pHeadNode = new CNode<TYPE>(element, NULL, m_pHeadNode); 
ASSERT(pHeadNode); 
 
//If there was a list hook the head->prev to the new head 
if(m_pHeadNode)  
  m_pHeadNode->m_pPrevNode = pHeadNode; 
 
//If there isn't a tail element, hook it to the head 
if(!m_pTailNode) 
  m_pTailNode = pHeadNode; 
 
m_pHeadNode = pHeadNode; 
m_ulLength++; 
return m_pHeadNode; 
} 
 
 
///////////////////////////////////////////////////////////////////////////// 
// CList::AddTail 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> POSITION CList<TYPE>::AddTail(TYPE element)  
{ 
//Add to the m_pTailNode of the CList 
CNode<TYPE>* pTailNode = new CNode<TYPE>(element, m_pTailNode, 0); 
ASSERT(pTailNode); 
 
//if previously empty 
if(!m_pHeadNode) 
m_pHeadNode = pTailNode; 
else 
m_pTailNode->m_pNextNode = pTailNode; 
 
m_pTailNode = pTailNode; 
m_ulLength++; 
return m_pTailNode; 
} 
 
 
 
///////////////////////////////////////////////////////////////////////////// 
// CList::GetHead 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> inline TYPE CList<TYPE>::GetHead()  
{ 
//return Head element value 
ASSERT(m_pHeadNode); 
return m_pHeadNode->m_data; 
} 
 
///////////////////////////////////////////////////////////////////////////// 
// CList::AddTail 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> inline TYPE CList<TYPE>::GetTail()  
{ 
// return Tail element value 
ASSERT(m_pTailNode); 
return m_pTailNode->m_data; 
} 
 
 
///////////////////////////////////////////////////////////////////////////// 
// CList::GetNext 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> inline TYPE CList<TYPE>::GetNext(POSITION position)  
{ 
ASSERT(position); 
 
// return the next element 
return position->m_pNextNode->m_data; 
} 
 
 
///////////////////////////////////////////////////////////////////////////// 
// CList::GetPrev 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> inline TYPE CList<TYPE>::GetPrev(POSITION position)  
{ 
ASSERT(position); 
 
// return the prev element 
return position->m_pPrevNode->m_data; 
} 
 
 
///////////////////////////////////////////////////////////////////////////// 
// CList::Find 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> POSITION CList<TYPE>::Find(TYPE element)  
{ 
//return pointer to found element 
for(CNode<TYPE>* p = m_pHeadNode; p; p = p->m_pNextNode) 
  if(p->m_data == element) 
return p;   // return position to found CNode 
 
return NULL;  // return NULL if not found 
} 
 
 
///////////////////////////////////////////////////////////////////////////// 
// CList::IsEmpty 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> inline BOOL CList<TYPE>::IsEmpty()  
{ 
// returns TRUE if Empty 
return m_ulLength == 0; 
} 
 
 
 
///////////////////////////////////////////////////////////////////////////// 
// CList::RemoveHead 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> TYPE CList<TYPE>::RemoveHead()  
{ 
//Remove and return from the Head of the List 
ASSERT(m_pHeadNode); 
 
CNode<TYPE>* pHeadNode = m_pHeadNode;// pointer to the Removed node 
TYPE element = GetHead();//make a copy, before deleteing 
 
m_pHeadNode = pHeadNode->m_pNextNode;// reroute Head to exclude the first element 
if(m_pHeadNode) 
m_pHeadNode->m_pPrevNode = NULL; 
else 
m_pTailNode = NULL; 
 
m_ulLength--; 
delete pHeadNode;// delete head 
return element; 
} 
 
 
///////////////////////////////////////////////////////////////////////////// 
// CList::RemoveTail 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> TYPE CList<TYPE>::RemoveTail()  
{ 
//Remove and return from the m_pTailNode of the CList 
ASSERT(m_pTailNode); 
 
CNode<TYPE>* pTailNode = m_pTailNode->m_pPrevNode; 
TYPE element = GetTail();  //make a copy before deleteing 
 
m_pTailNode = pTailNode; 
if(m_pTailNode) 
m_pTailNode->m_pNextNode = NULL; 
else 
m_pHeadNode = NULL; 
 
m_ulLength--; 
delete m_pTailNode; 
return element; 
} 
 
 
///////////////////////////////////////////////////////////////////////////// 
// CList::RemoveAt 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> void CList<TYPE>::RemoveAt(POSITION position) 
{ 
//Remove CList[position] 
ASSERT(position); 
 
CNode<TYPE>* pNode = position; 
 
// If removing the head 
if (pNode == m_pHeadNode) 
m_pHeadNode = pNode->m_pNextNode; 
else 
pNode->m_pPrevNode->m_pNextNode = pNode->m_pNextNode; 
 
//If removing the tail 
if (pNode == m_pTailNode) 
m_pTailNode = pNode->m_pPrevNode; 
else 
pNode->m_pNextNode->m_pPrevNode = pNode->m_pPrevNode; 
 
m_ulLength--; 
delete pNode; 
} 
 
 
///////////////////////////////////////////////////////////////////////////// 
// CList::RemoveAll 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> void CList<TYPE>::RemoveAll()  
{ 
// Remove all items from the CList 
for (CNode<TYPE>* p = m_pHeadNode; p; p = p->m_pNextNode)  
delete p; 
 
m_pHeadNode   = NULL; 
m_pTailNode   = NULL; 
m_ulLength    = 0; 
} 
 
 
///////////////////////////////////////////////////////////////////////////// 
// CList::GetCount 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> inline ULONG CList<TYPE>::GetCount()  
{ 
// return the Length 
return m_ulLength; 
} 
 
 
///////////////////////////////////////////////////////////////////////////// 
// CList::InsertBefore 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> POSITION CList<TYPE>::InsertBefore(POSITION position, TYPE element) 
{ 
//insert before the position 
if(position == m_pHeadNode)    // Add before Head 
  return AddHead(element); 
 
//otherwise a little more difficult 
CNode<TYPE>* pNode = new CNode<TYPE>(element, position->m_pPrevNode, position); 
 
//Create the new node 
pNode->m_pNextNode = new CNode<TYPE>(element, position->m_pPrevNode, position->m_pNextNode); 
 
//Hook up before after nodes to it 
position->m_pPrevNode->m_pNextNode = pNode; 
position->m_pPrevNode = pNode; 
 
m_ulLength++; 
return pNode; 
} 
 
 
 
///////////////////////////////////////////////////////////////////////////// 
// CList::InsertAfter 
// 
///////////////////////////////////////////////////////////////////////////// 
template <class TYPE> POSITION CList<TYPE>::InsertAfter(POSITION position, TYPE element) 
{ 
//insert after the position 
if(position == m_pTailNode)     // Add after the m_pTailNode 
  return AddTail(element); 
 
//other wise a little more difficult 
CNode<TYPE>* pNode = new CNode<TYPE>(element, position, position->m_pNextNode); 
 
//Hook up before after nodes to it 
position->m_pNextNode->m_pPrevNode = pNode; 
position->m_pNextNode = pNode; 
 
m_ulLength++; 
return pNode; 
} 
 
 
 
#endif //_LIST_H_