home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / msdn_vcb / samples / vc98 / sdk / dbmsg / oledb / tablecopy / list.h < prev    next >
Encoding:
C/C++ Source or Header  |  1998-03-12  |  13.6 KB  |  495 lines
  1. //-----------------------------------------------------------------------------
  2. // Microsoft OLE DB TABLECOPY Sample
  3. // Copyright (C) 1995-1998 Microsoft Corporation
  4. //
  5. // @doc
  6. //
  7. // @module LIST.H
  8. //
  9. //-----------------------------------------------------------------------------
  10. #ifndef _LIST_H_
  11. #define _LIST_H_
  12.             
  13. /////////////////////////////////////////////////////////////////////////////
  14. // Includes
  15. //
  16. /////////////////////////////////////////////////////////////////////////////
  17.  
  18.  
  19. /////////////////////////////////////////////////////////////////////////////
  20. // Defines
  21. //
  22. /////////////////////////////////////////////////////////////////////////////
  23. typedef void* LISTPOS;
  24.  
  25.  
  26. /////////////////////////////////////////////////////////////////////////////
  27. // CNode
  28. //
  29. /////////////////////////////////////////////////////////////////////////////
  30. template <class TYPE> class CNode
  31. {
  32. public:
  33.     // constructors
  34.     CNode(TYPE val, CNode* pPrevNode, CNode* pNextNode);
  35.  
  36.     // members
  37.     TYPE     m_data;       // element data
  38.     CNode*   m_pNextNode;  // next CNode
  39.     CNode*   m_pPrevNode;  // prev CNode
  40. };
  41.  
  42.  
  43. /////////////////////////////////////////////////////////////////////////////
  44. // CNode::CNode
  45. //
  46. /////////////////////////////////////////////////////////////////////////////
  47. template <class TYPE> CNode<TYPE>::CNode(TYPE data, CNode* pPrevNode, CNode* pNextNode)
  48. {
  49.     //Constructor
  50.     m_data = data;
  51.     m_pPrevNode = pPrevNode;
  52.     m_pNextNode = pNextNode;
  53. }
  54.  
  55.  
  56.  
  57. /////////////////////////////////////////////////////////////////////////////
  58. // CList
  59. //
  60. /////////////////////////////////////////////////////////////////////////////
  61. template <class TYPE> class CList
  62. {
  63. public:
  64.  
  65.     //constructors
  66.     CList();
  67.     virtual ~CList();
  68.  
  69.     //members
  70.     
  71.     //list modifying operations
  72.     virtual LISTPOS    AddHead(TYPE element);        // Add to Head
  73.     virtual LISTPOS    AddTail(TYPE element);        // Add to Tail
  74.  
  75.     virtual LISTPOS    InsertBefore(LISTPOS position, TYPE element);    // Add before position
  76.     virtual LISTPOS    InsertAfter(LISTPOS position, TYPE element);    // Add after position
  77.  
  78.     virtual TYPE    RemoveHead();                // Remove from Head
  79.     virtual TYPE    RemoveTail();                // Remove from Tail
  80.     virtual TYPE    RemoveAt(LISTPOS position); // RemoveAt position
  81.     virtual void    RemoveAll();                // Remove all elements
  82.  
  83.     //Seeking methods
  84.     virtual LISTPOS    Find(TYPE element);            // Find element
  85.  
  86.     //Peek methods
  87.     virtual LISTPOS    GetHeadPosition();            // Head Position
  88.     virtual LISTPOS    GetTailPosition();            // Tail Position
  89.  
  90.     virtual TYPE        GetHead();                    // Head element
  91.     virtual TYPE        GetTail();                    // Tail element
  92.     virtual TYPE        GetNext(LISTPOS& position); // Next element
  93.     virtual TYPE        GetPrev(LISTPOS& position); // Prev element
  94.  
  95.     //Data methods
  96.     virtual TYPE        GetAt(LISTPOS position) const;            //Get element value
  97.     virtual TYPE        SetAt(LISTPOS position, TYPE element);    //Set element value
  98.  
  99.     //Array-like methods
  100.     virtual LISTPOS    FindIndex(ULONG iIndex);    //Index element
  101.  
  102.     //informational methods
  103.     virtual BOOL        IsEmpty();                    // IsEmpty
  104.     virtual ULONG        GetCount();                    // Elements in the list
  105.  
  106. private:
  107.     //data
  108.     CNode<TYPE>*        m_pHeadNode;                // Head of CList
  109.     CNode<TYPE>*        m_pTailNode;                // Tail of CList
  110.  
  111.     ULONG                m_ulElements;                // Elements in the list
  112. };
  113.  
  114.  
  115. /////////////////////////////////////////////////////////////////////////////
  116. // CList::CList
  117. //
  118. /////////////////////////////////////////////////////////////////////////////
  119. template <class TYPE> CList<TYPE>::CList()
  120. {
  121.     //constructor
  122.     m_pHeadNode = NULL;
  123.     m_pTailNode = NULL;
  124.     m_ulElements = 0;
  125. }
  126.  
  127. /////////////////////////////////////////////////////////////////////////////
  128. // CList::~CList
  129. //
  130. /////////////////////////////////////////////////////////////////////////////
  131. template <class TYPE> CList<TYPE>::~CList() 
  132. {
  133.     //Remove all elements
  134.     RemoveAll();
  135. }
  136.  
  137.  
  138. /////////////////////////////////////////////////////////////////////////////
  139. // CList::AddHead
  140. //
  141. /////////////////////////////////////////////////////////////////////////////
  142. template <class TYPE> LISTPOS CList<TYPE>::AddHead(TYPE element) 
  143. {
  144.     //Add to the Head of the CList, (stack)
  145.     CNode<TYPE>* pHeadNode = new CNode<TYPE>(element, NULL, m_pHeadNode);
  146.     ASSERT(pHeadNode);
  147.  
  148.     //If there was a list hook the head->prev to the new head
  149.     if(m_pHeadNode) 
  150.       m_pHeadNode->m_pPrevNode = pHeadNode;
  151.  
  152.     //If there isn't a tail element, hook it to the head
  153.     if(!m_pTailNode)
  154.       m_pTailNode = pHeadNode;
  155.  
  156.     m_pHeadNode = pHeadNode;
  157.     m_ulElements++;
  158.     return m_pHeadNode;
  159. }
  160.  
  161.  
  162. /////////////////////////////////////////////////////////////////////////////
  163. // CList::AddTail
  164. //
  165. /////////////////////////////////////////////////////////////////////////////
  166. template <class TYPE> LISTPOS CList<TYPE>::AddTail(TYPE element) 
  167. {
  168.     //Add to the m_pTailNode of the CList
  169.     CNode<TYPE>* pTailNode = new CNode<TYPE>(element, m_pTailNode, 0);
  170.     ASSERT(pTailNode);
  171.  
  172.     //if previously empty
  173.     if(!m_pHeadNode)
  174.         m_pHeadNode = pTailNode;
  175.     else
  176.         m_pTailNode->m_pNextNode = pTailNode;
  177.  
  178.     m_pTailNode = pTailNode;
  179.     m_ulElements++;
  180.     return m_pTailNode;
  181. }
  182.  
  183.  
  184.  
  185. /////////////////////////////////////////////////////////////////////////////
  186. // CList::GetHeadPosition
  187. //
  188. /////////////////////////////////////////////////////////////////////////////
  189. template <class TYPE> inline LISTPOS CList<TYPE>::GetHeadPosition() 
  190. {
  191.     //return Head element Position
  192.     return m_pHeadNode;
  193. }
  194.  
  195. /////////////////////////////////////////////////////////////////////////////
  196. // CList::GetTailPosition
  197. //
  198. /////////////////////////////////////////////////////////////////////////////
  199. template <class TYPE> inline LISTPOS CList<TYPE>::GetTailPosition() 
  200. {
  201.     //return Tail element Position
  202.     return m_pTailNode;
  203. }
  204.  
  205. /////////////////////////////////////////////////////////////////////////////
  206. // CList::GetHead
  207. //
  208. /////////////////////////////////////////////////////////////////////////////
  209. template <class TYPE> inline TYPE CList<TYPE>::GetHead() 
  210. {
  211.     //return Head element value
  212.     ASSERT(m_pHeadNode);
  213.     return m_pHeadNode->m_data;
  214. }
  215.  
  216. /////////////////////////////////////////////////////////////////////////////
  217. // CList::AddTail
  218. //
  219. /////////////////////////////////////////////////////////////////////////////
  220. template <class TYPE> inline TYPE CList<TYPE>::GetTail() 
  221. {
  222.     // return Tail element value
  223.     ASSERT(m_pTailNode);
  224.     return m_pTailNode->m_data;
  225. }
  226.  
  227.  
  228. /////////////////////////////////////////////////////////////////////////////
  229. // CList::GetNext
  230. //
  231. /////////////////////////////////////////////////////////////////////////////
  232. template <class TYPE> inline TYPE CList<TYPE>::GetNext(LISTPOS& position) 
  233. {
  234.     ASSERT(position);
  235.  
  236.     //Set position to the next element
  237.     CNode<TYPE>* pNode = (CNode<TYPE>*)position;
  238.     position = pNode->m_pNextNode;
  239.  
  240.     //return the current element
  241.     return pNode->m_data;
  242. }
  243.  
  244.  
  245. /////////////////////////////////////////////////////////////////////////////
  246. // CList::GetPrev
  247. //
  248. /////////////////////////////////////////////////////////////////////////////
  249. template <class TYPE> inline TYPE CList<TYPE>::GetPrev(LISTPOS& position) 
  250. {
  251.     ASSERT(position);
  252.     
  253.     //Set position to the next element
  254.     CNode<TYPE>* pNode = (CNode<TYPE>*)position;
  255.     position = pNode->m_pPrevNode;
  256.     
  257.     //return the current element
  258.     return pNode->m_data;
  259. }
  260.  
  261.  
  262. /////////////////////////////////////////////////////////////////////////////
  263. // CList::GetAt
  264. //
  265. /////////////////////////////////////////////////////////////////////////////
  266. template <class TYPE> inline TYPE CList<TYPE>::GetAt(LISTPOS position) const
  267. {
  268.     ASSERT(position);
  269.     return ((CNode<TYPE>*)position)->m_data;
  270. }
  271.  
  272. /////////////////////////////////////////////////////////////////////////////
  273. // CList::SetAt
  274. //
  275. /////////////////////////////////////////////////////////////////////////////
  276. template <class TYPE> inline TYPE CList<TYPE>::SetAt(LISTPOS position, TYPE element)
  277. {
  278.     ASSERT(position);
  279.  
  280.     //Save the old data
  281.     CNode<TYPE>* pNode = (CNode<TYPE>*)position;
  282.     TYPE oldData = pNode->m_data;
  283.  
  284.     //Store new data
  285.     pNode->m_data = element;
  286.  
  287.     //return olddata
  288.     return oldData;
  289. }
  290.  
  291.  
  292. /////////////////////////////////////////////////////////////////////////////
  293. // CList::Find
  294. //
  295. /////////////////////////////////////////////////////////////////////////////
  296. template <class TYPE> LISTPOS CList<TYPE>::Find(TYPE element) 
  297. {
  298.     //return pointer to found element
  299.     for(CNode<TYPE>* p = m_pHeadNode; p; p = p->m_pNextNode)
  300.       if(p->m_data == element)
  301.         return p;   // return position to found CNode
  302.  
  303.     return NULL;  // return NULL if not found
  304. }
  305.  
  306.  
  307. /////////////////////////////////////////////////////////////////////////////
  308. // CList::IsEmpty
  309. //
  310. /////////////////////////////////////////////////////////////////////////////
  311. template <class TYPE> inline BOOL CList<TYPE>::IsEmpty() 
  312. {
  313.     // returns TRUE if Empty
  314.     return m_ulElements == 0;
  315. }
  316.  
  317.  
  318.  
  319. /////////////////////////////////////////////////////////////////////////////
  320. // CList::RemoveHead
  321. //
  322. /////////////////////////////////////////////////////////////////////////////
  323. template <class TYPE> TYPE CList<TYPE>::RemoveHead() 
  324. {
  325.     //Remove and return from the Head of the List
  326.     ASSERT(m_pHeadNode);
  327.  
  328.     CNode<TYPE>* pHeadNode = m_pHeadNode;    // pointer to the Removed node
  329.     TYPE element = GetHead();                //make a copy, before deleteing
  330.  
  331.     m_pHeadNode = pHeadNode->m_pNextNode;        // reroute Head to exclude the first element
  332.     if(m_pHeadNode)
  333.         m_pHeadNode->m_pPrevNode = NULL;
  334.     else
  335.         m_pTailNode = NULL;
  336.  
  337.     m_ulElements--;
  338.     delete pHeadNode;                        // delete head
  339.     return element;
  340. }
  341.  
  342.  
  343. /////////////////////////////////////////////////////////////////////////////
  344. // CList::RemoveTail
  345. //
  346. /////////////////////////////////////////////////////////////////////////////
  347. template <class TYPE> TYPE CList<TYPE>::RemoveTail() 
  348. {
  349.     //Remove and return from the m_pTailNode of the CList
  350.     ASSERT(m_pTailNode);
  351.  
  352.     CNode<TYPE>* pTailNode = m_pTailNode->m_pPrevNode;
  353.     TYPE element = GetTail();  //make a copy before deleteing
  354.  
  355.     m_pTailNode = pTailNode;
  356.     if(m_pTailNode)
  357.         m_pTailNode->m_pNextNode = NULL;
  358.     else
  359.         m_pHeadNode = NULL;
  360.  
  361.     m_ulElements--;
  362.     delete m_pTailNode;
  363.     return element;
  364. }
  365.  
  366.  
  367. /////////////////////////////////////////////////////////////////////////////
  368. // CList::RemoveAt
  369. //
  370. /////////////////////////////////////////////////////////////////////////////
  371. template <class TYPE> TYPE CList<TYPE>::RemoveAt(LISTPOS position)
  372. {
  373.     //Remove CList[position]
  374.     ASSERT(position);
  375.  
  376.     CNode<TYPE>* pNode = (CNode<TYPE>*)position;
  377.     TYPE oldData = pNode->m_data;
  378.  
  379.     // If removing the head
  380.     if (pNode == m_pHeadNode)
  381.         m_pHeadNode = pNode->m_pNextNode;
  382.     else
  383.         pNode->m_pPrevNode->m_pNextNode = pNode->m_pNextNode;
  384.     
  385.     //If removing the tail
  386.     if (pNode == m_pTailNode)
  387.         m_pTailNode = pNode->m_pPrevNode;
  388.     else
  389.         pNode->m_pNextNode->m_pPrevNode = pNode->m_pPrevNode;
  390.  
  391.     m_ulElements--;
  392.     delete pNode;
  393.     return oldData;
  394. }
  395.  
  396.  
  397. /////////////////////////////////////////////////////////////////////////////
  398. // CList::RemoveAll
  399. //
  400. /////////////////////////////////////////////////////////////////////////////
  401. template <class TYPE> void CList<TYPE>::RemoveAll() 
  402. {
  403.     // Remove all items from the CList
  404.     for(CNode<TYPE>* p = m_pHeadNode; p; p = p->m_pNextNode)     
  405.         delete p;
  406.  
  407.     m_pHeadNode   = NULL;
  408.     m_pTailNode   = NULL;
  409.     m_ulElements    = 0;
  410. }
  411.  
  412.  
  413. /////////////////////////////////////////////////////////////////////////////
  414. // CList::GetCount
  415. //
  416. /////////////////////////////////////////////////////////////////////////////
  417. template <class TYPE> inline ULONG CList<TYPE>::GetCount() 
  418. {
  419.     // return the Length
  420.     return m_ulElements;
  421. }
  422.  
  423.                    
  424. /////////////////////////////////////////////////////////////////////////////
  425. // CList::InsertBefore
  426. //
  427. /////////////////////////////////////////////////////////////////////////////
  428. template <class TYPE> LISTPOS CList<TYPE>::InsertBefore(LISTPOS position, TYPE element)
  429. {
  430.     //insert before the position
  431.     if(position == m_pHeadNode)    // Add before Head
  432.       return AddHead(element);
  433.  
  434.     CNode<TYPE>* pOldNode = (CNode<TYPE>*)position;
  435.  
  436.     //otherwise a little more difficult
  437.     CNode<TYPE>* pNewNode = new CNode<TYPE>(element, pOldNode->m_pPrevNode, pOldNode);
  438.     
  439.     //Create the new node
  440.     pNewNode->m_pNextNode = new CNode<TYPE>(element, pOldNode->m_pPrevNode, pOldNode->m_pNextNode);
  441.  
  442.     //Hook up before after nodes to it
  443.     pOldNode->m_pPrevNode->m_pNextNode = pNewNode;
  444.     pOldNode->m_pPrevNode = pNewNode;
  445.  
  446.     m_ulElements++;
  447.     return pNewNode;
  448. }
  449.  
  450.  
  451.  
  452. /////////////////////////////////////////////////////////////////////////////
  453. // CList::InsertAfter
  454. //
  455. /////////////////////////////////////////////////////////////////////////////
  456. template <class TYPE> LISTPOS CList<TYPE>::InsertAfter(LISTPOS position, TYPE element)
  457. {
  458.     //insert after the position
  459.     if(position == m_pTailNode)     // Add after the m_pTailNode
  460.       return AddTail(element);
  461.     
  462.     CNode<TYPE>* pOldNode = (CNode<TYPE>*)position;
  463.  
  464.     //other wise a little more difficult
  465.     CNode<TYPE>* pNewNode = new CNode<TYPE>(element, pOldNode, pOldNode->m_pNextNode);
  466.     
  467.     //Hook up before after nodes to it
  468.     pOldNode->m_pNextNode->m_pPrevNode = pNewNode;
  469.     pOldNode->m_pNextNode = pNewNode;
  470.  
  471.     m_ulElements++;
  472.     return pNewNode;
  473. }
  474.  
  475.  
  476. /////////////////////////////////////////////////////////////////////////////
  477. // CList::FindIndex
  478. //
  479. /////////////////////////////////////////////////////////////////////////////
  480. template <class TYPE> LISTPOS CList<TYPE>::FindIndex(ULONG iIndex)
  481. {
  482.     ASSERT(iIndex>=0 && iIndex<m_ulElements);
  483.  
  484.     CNode<TYPE>* pNode = m_pHeadNode;
  485.  
  486.     //Find the specified index
  487.     while(iIndex--)
  488.         pNode = pNode->m_pNextNode;
  489.  
  490.     return (LISTPOS)pNode;
  491. }
  492.  
  493. #endif //_LIST_H_
  494.  
  495.