home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / msdn_vcb / samples / vc98 / mfc / utility / templdef / list.ctt < prev    next >
Encoding:
Text File  |  1998-03-27  |  20.5 KB  |  774 lines
  1. /////////////////////////////////////////////////////////////////////////////
  2. // class CList<TYPE, ARG_TYPE> - a list containing 'TYPE' elements
  3. // passed in parameters as ARG_TYPE
  4. //
  5. // optional definitions:
  6. //  IS_SERIAL   - enable serialization through CArchive extraction & insertion
  7. //  HAS_CREATE  - call constructors and destructors
  8. //
  9. // This is a part of the Microsoft Foundation Classes C++ library.
  10. // Copyright (C) 1994-1998 Microsoft Corporation
  11. // All rights reserved.
  12. //
  13. // This source code is only intended as a supplement to the
  14. // Microsoft Foundation Classes Reference and related
  15. // electronic documentation provided with the library.
  16. // See these sources for detailed information regarding the
  17. // Microsoft Foundation Classes product.
  18. /////////////////////////////////////////////////////////////////////////////
  19.  
  20. //$DECLARE_TEMPLATE
  21. /////////////////////////////////////////////////////////////////////////////
  22. template<class TYPE, class ARG_TYPE>
  23. class CList : public CObject
  24. {
  25. $ifdef IS_SERIAL
  26.     DECLARE_SERIAL(CList)
  27. $else
  28.     DECLARE_DYNAMIC(CList)
  29. $endif //!IS_SERIAL
  30.  
  31. protected:
  32.     struct CNode
  33.     {
  34.         CNode* pNext;
  35.         CNode* pPrev;
  36.         TYPE data;
  37.     };
  38. public:
  39.  
  40. // Construction
  41.     CList(int nBlockSize = 10);
  42.  
  43. // Attributes (head and tail)
  44.     // count of elements
  45.     int GetCount() const;
  46.     BOOL IsEmpty() const;
  47.  
  48.     // peek at head or tail
  49.     TYPE& GetHead();
  50.     TYPE GetHead() const;
  51.     TYPE& GetTail();
  52.     TYPE GetTail() const;
  53.  
  54. // Operations
  55.     // get head or tail (and remove it) - don't call on empty list!
  56.     TYPE RemoveHead();
  57.     TYPE RemoveTail();
  58.  
  59.     // add before head or after tail
  60.     POSITION AddHead(ARG_TYPE newElement);
  61.     POSITION AddTail(ARG_TYPE newElement);
  62. $ifdef INCLUDE_TYPEREF
  63.     POSITION AddHead(const TYPE& newElement);
  64.     POSITION AddTail(const TYPE& newElement);
  65. $endif
  66.  
  67.     // add another list of elements before head or after tail
  68.     void AddHead(CList* pNewList);
  69.     void AddTail(CList* pNewList);
  70.  
  71.     // remove all elements
  72.     void RemoveAll();
  73.  
  74.     // iteration
  75.     POSITION GetHeadPosition() const;
  76.     POSITION GetTailPosition() const;
  77.     TYPE& GetNext(POSITION& rPosition); // return *Position++
  78.     TYPE GetNext(POSITION& rPosition) const; // return *Position++
  79.     TYPE& GetPrev(POSITION& rPosition); // return *Position--
  80.     TYPE GetPrev(POSITION& rPosition) const; // return *Position--
  81.  
  82.     // getting/modifying an element at a given position
  83.     TYPE& GetAt(POSITION position);
  84.     TYPE GetAt(POSITION position) const;
  85.     void SetAt(POSITION pos, ARG_TYPE newElement);
  86. $ifdef INCLUDE_TYPEREF
  87.     void SetAt(POSITION pos, const TYPE& newElement);
  88. $endif
  89.     void RemoveAt(POSITION position);
  90.  
  91.     // inserting before or after a given position
  92.     POSITION InsertBefore(POSITION position, ARG_TYPE newElement);
  93.     POSITION InsertAfter(POSITION position, ARG_TYPE newElement);
  94. $ifdef INCLUDE_TYPEREF
  95.     POSITION InsertBefore(POSITION position, const TYPE& newElement);
  96.     POSITION InsertAfter(POSITION position, const TYPE& newElement);
  97. $endif
  98.  
  99.     // helper functions (note: O(n) speed)
  100.     POSITION Find(ARG_TYPE searchValue, POSITION startAfter = NULL) const;
  101.                         // defaults to starting at the HEAD
  102.                         // return NULL if not found
  103.     POSITION FindIndex(int nIndex) const;
  104.                         // get the 'nIndex'th element (may return NULL)
  105.  
  106. // Implementation
  107. protected:
  108.     CNode* m_pNodeHead;
  109.     CNode* m_pNodeTail;
  110.     int m_nCount;
  111.     CNode* m_pNodeFree;
  112.     struct CPlex* m_pBlocks;
  113.     int m_nBlockSize;
  114.  
  115.     CNode* NewNode(CNode*, CNode*);
  116.     void FreeNode(CNode*);
  117.  
  118. public:
  119.     ~CList();
  120. $ifdef IS_SERIAL
  121.     void Serialize(CArchive&);
  122. $endif //IS_SERIAL
  123. #ifdef _DEBUG
  124.     void Dump(CDumpContext&) const;
  125.     void AssertValid() const;
  126. #endif
  127.     // local typedefs for class templates
  128.     typedef TYPE BASE_TYPE;
  129.     typedef ARG_TYPE BASE_ARG_TYPE;
  130. };
  131.  
  132. //$IMPLEMENT_TEMPLATE_INLINES
  133. ////////////////////////////////////////////////////////////////////////////
  134.  
  135. template<class TYPE, class ARG_TYPE>
  136. _AFXCOLL_INLINE int CList<TYPE, ARG_TYPE>::GetCount() const
  137.     { return m_nCount; }
  138. template<class TYPE, class ARG_TYPE>
  139. _AFXCOLL_INLINE BOOL CList<TYPE, ARG_TYPE>::IsEmpty() const
  140.     { return m_nCount == 0; }
  141. template<class TYPE, class ARG_TYPE>
  142. _AFXCOLL_INLINE TYPE& CList<TYPE, ARG_TYPE>::GetHead()
  143.     { ASSERT(m_pNodeHead != NULL);
  144.         return m_pNodeHead->data; }
  145. template<class TYPE, class ARG_TYPE>
  146. _AFXCOLL_INLINE TYPE CList<TYPE, ARG_TYPE>::GetHead() const
  147.     { ASSERT(m_pNodeHead != NULL);
  148.         return m_pNodeHead->data; }
  149. template<class TYPE, class ARG_TYPE>
  150. _AFXCOLL_INLINE TYPE& CList<TYPE, ARG_TYPE>::GetTail()
  151.     { ASSERT(m_pNodeTail != NULL);
  152.         return m_pNodeTail->data; }
  153. template<class TYPE, class ARG_TYPE>
  154. _AFXCOLL_INLINE TYPE CList<TYPE, ARG_TYPE>::GetTail() const
  155.     { ASSERT(m_pNodeTail != NULL);
  156.         return m_pNodeTail->data; }
  157. template<class TYPE, class ARG_TYPE>
  158. _AFXCOLL_INLINE POSITION CList<TYPE, ARG_TYPE>::GetHeadPosition() const
  159.     { return (POSITION) m_pNodeHead; }
  160. template<class TYPE, class ARG_TYPE>
  161. _AFXCOLL_INLINE POSITION CList<TYPE, ARG_TYPE>::GetTailPosition() const
  162.     { return (POSITION) m_pNodeTail; }
  163. template<class TYPE, class ARG_TYPE>
  164. _AFXCOLL_INLINE TYPE& CList<TYPE, ARG_TYPE>::GetNext(POSITION& rPosition) // return *Position++
  165.     { CNode* pNode = (CNode*) rPosition;
  166.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  167.         rPosition = (POSITION) pNode->pNext;
  168.         return pNode->data; }
  169. template<class TYPE, class ARG_TYPE>
  170. _AFXCOLL_INLINE TYPE CList<TYPE, ARG_TYPE>::GetNext(POSITION& rPosition) const // return *Position++
  171.     { CNode* pNode = (CNode*) rPosition;
  172.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  173.         rPosition = (POSITION) pNode->pNext;
  174.         return pNode->data; }
  175. template<class TYPE, class ARG_TYPE>
  176. _AFXCOLL_INLINE TYPE& CList<TYPE, ARG_TYPE>::GetPrev(POSITION& rPosition) // return *Position--
  177.     { CNode* pNode = (CNode*) rPosition;
  178.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  179.         rPosition = (POSITION) pNode->pPrev;
  180.         return pNode->data; }
  181. template<class TYPE, class ARG_TYPE>
  182. _AFXCOLL_INLINE TYPE CList<TYPE, ARG_TYPE>::GetPrev(POSITION& rPosition) const // return *Position--
  183.     { CNode* pNode = (CNode*) rPosition;
  184.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  185.         rPosition = (POSITION) pNode->pPrev;
  186.         return pNode->data; }
  187. template<class TYPE, class ARG_TYPE>
  188. _AFXCOLL_INLINE TYPE& CList<TYPE, ARG_TYPE>::GetAt(POSITION position)
  189.     { CNode* pNode = (CNode*) position;
  190.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  191.         return pNode->data; }
  192. template<class TYPE, class ARG_TYPE>
  193. _AFXCOLL_INLINE TYPE CList<TYPE, ARG_TYPE>::GetAt(POSITION position) const
  194.     { CNode* pNode = (CNode*) position;
  195.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  196.         return pNode->data; }
  197. template<class TYPE, class ARG_TYPE>
  198. _AFXCOLL_INLINE void CList<TYPE, ARG_TYPE>::SetAt(POSITION pos, ARG_TYPE newElement)
  199.     { CNode* pNode = (CNode*) pos;
  200.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  201.         pNode->data = newElement; }
  202. $ifdef INCLUDE_TYPEREF
  203. template<class TYPE, class ARG_TYPE>
  204. _AFXCOLL_INLINE void CList<TYPE, ARG_TYPE>::SetAt(POSITION pos, const TYPE& newElement)
  205.     { CNode* pNode = (CNode*) pos;
  206.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  207.         pNode->data = newElement; }
  208. $endif
  209.  
  210. //$IMPLEMENT_TEMPLATE
  211. // This is a part of the Microsoft Foundation Classes C++ library.
  212. // Copyright (C) 1992-1997 Microsoft Corporation
  213. // All rights reserved.
  214. //
  215. // This source code is only intended as a supplement to the
  216. // Microsoft Foundation Classes Reference and related
  217. // electronic documentation provided with the library.
  218. // See these sources for detailed information regarding the
  219. // Microsoft Foundation Classes product.
  220.  
  221. /////////////////////////////////////////////////////////////////////////////
  222. //
  223. // Implementation of parameterized List
  224. //
  225. /////////////////////////////////////////////////////////////////////////////
  226.  
  227. #include "stdafx.h"
  228.  
  229. #ifdef AFX_COLL_SEG
  230. #pragma code_seg(AFX_COLL_SEG)
  231. #endif
  232.  
  233. #ifdef _DEBUG
  234. #undef THIS_FILE
  235. static char THIS_FILE[] = __FILE__;
  236. #endif
  237.  
  238. $ifdef HAS_CREATE
  239. #include "elements.h"  // used for special creation
  240. $endif
  241.  
  242. #define new DEBUG_NEW
  243.  
  244. /////////////////////////////////////////////////////////////////////////////
  245.  
  246. template<class TYPE, class ARG_TYPE>
  247. CList<TYPE, ARG_TYPE>::CList(int nBlockSize)
  248. {
  249.     ASSERT(nBlockSize > 0);
  250.  
  251.     m_nCount = 0;
  252.     m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
  253.     m_pBlocks = NULL;
  254.     m_nBlockSize = nBlockSize;
  255. }
  256.  
  257. template<class TYPE, class ARG_TYPE>
  258. void CList<TYPE, ARG_TYPE>::RemoveAll()
  259. {
  260.     ASSERT_VALID(this);
  261.  
  262.     // destroy elements
  263. $ifdef HAS_CREATE
  264.     CNode* pNode;
  265.     for (pNode = m_pNodeHead; pNode != NULL; pNode = pNode->pNext)
  266.         DestructElement(&pNode->data);
  267. $endif
  268.  
  269.     m_nCount = 0;
  270.     m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
  271.     m_pBlocks->FreeDataChain();
  272.     m_pBlocks = NULL;
  273. }
  274.  
  275. template<class TYPE, class ARG_TYPE>
  276. CList<TYPE, ARG_TYPE>::~CList()
  277. {
  278.     RemoveAll();
  279.     ASSERT(m_nCount == 0);
  280. }
  281.  
  282. /////////////////////////////////////////////////////////////////////////////
  283. // Node helpers
  284. /*
  285.  * Implementation note: CNode's are stored in CPlex blocks and
  286.  *  chained together. Free blocks are maintained in a singly linked list
  287.  *  using the 'pNext' member of CNode with 'm_pNodeFree' as the head.
  288.  *  Used blocks are maintained in a doubly linked list using both 'pNext'
  289.  *  and 'pPrev' as links and 'm_pNodeHead' and 'm_pNodeTail'
  290.  *   as the head/tail.
  291.  *
  292.  * We never free a CPlex block unless the List is destroyed or RemoveAll()
  293.  *  is used - so the total number of CPlex blocks may grow large depending
  294.  *  on the maximum past size of the list.
  295.  */
  296.  
  297. template<class TYPE, class ARG_TYPE>
  298. CList<TYPE, ARG_TYPE>::CNode*
  299. CList<TYPE, ARG_TYPE>::NewNode(CList::CNode* pPrev, CList::CNode* pNext)
  300. {
  301.     if (m_pNodeFree == NULL)
  302.     {
  303.         // add another block
  304.         CPlex* pNewBlock = CPlex::Create(m_pBlocks, m_nBlockSize,
  305.                  sizeof(CNode));
  306.  
  307.         // chain them into free list
  308.         CNode* pNode = (CNode*) pNewBlock->data();
  309.         // free in reverse order to make it easier to debug
  310.         pNode += m_nBlockSize - 1;
  311.         for (int i = m_nBlockSize-1; i >= 0; i--, pNode--)
  312.         {
  313.             pNode->pNext = m_pNodeFree;
  314.             m_pNodeFree = pNode;
  315.         }
  316.     }
  317.     ASSERT(m_pNodeFree != NULL);  // we must have something
  318.  
  319.     CList::CNode* pNode = m_pNodeFree;
  320.     m_pNodeFree = m_pNodeFree->pNext;
  321.     pNode->pPrev = pPrev;
  322.     pNode->pNext = pNext;
  323.     m_nCount++;
  324.     ASSERT(m_nCount > 0);  // make sure we don't overflow
  325.  
  326. $ifdef HAS_CREATE
  327.     ConstructElement(&pNode->data);
  328. $endif
  329. $ifdef USE_MEMSET
  330.     memset(&pNode->data, 0, sizeof(TYPE));  // zero fill
  331. $endif
  332. $ifdef USE_ASSIGN
  333.     pNode->data = 0; // start with zero
  334. $endif
  335.     return pNode;
  336. }
  337.  
  338. template<class TYPE, class ARG_TYPE>
  339. void CList<TYPE, ARG_TYPE>::FreeNode(CList::CNode* pNode)
  340. {
  341. $ifdef HAS_CREATE
  342.     DestructElement(&pNode->data);
  343. $endif
  344.     pNode->pNext = m_pNodeFree;
  345.     m_pNodeFree = pNode;
  346.     m_nCount--;
  347.     ASSERT(m_nCount >= 0);  // make sure we don't underflow
  348.  
  349.     // if no more elements, cleanup completely
  350.     if (m_nCount == 0)
  351.         RemoveAll();
  352. }
  353.  
  354. /////////////////////////////////////////////////////////////////////////////
  355.  
  356. template<class TYPE, class ARG_TYPE>
  357. POSITION CList<TYPE, ARG_TYPE>::AddHead(ARG_TYPE newElement)
  358. {
  359. $ifndef INCLUDE_TYPEREF
  360.     ASSERT_VALID(this);
  361.  
  362.     CNode* pNewNode = NewNode(NULL, m_pNodeHead);
  363.     pNewNode->data = newElement;
  364.     if (m_pNodeHead != NULL)
  365.         m_pNodeHead->pPrev = pNewNode;
  366.     else
  367.         m_pNodeTail = pNewNode;
  368.     m_pNodeHead = pNewNode;
  369.     return (POSITION) pNewNode;
  370. $else
  371.     return AddHead(TYPE(newElement));
  372. $endif
  373. }
  374.  
  375. $ifdef INCLUDE_TYPEREF
  376. template<class TYPE, class ARG_TYPE>
  377. POSITION CList<TYPE, ARG_TYPE>::AddHead(const TYPE& newElement)
  378. {
  379.     ASSERT_VALID(this);
  380.  
  381.     CNode* pNewNode = NewNode(NULL, m_pNodeHead);
  382.     pNewNode->data = newElement;
  383.     if (m_pNodeHead != NULL)
  384.         m_pNodeHead->pPrev = pNewNode;
  385.     else
  386.         m_pNodeTail = pNewNode;
  387.     m_pNodeHead = pNewNode;
  388.     return (POSITION) pNewNode;
  389. }
  390. $endif
  391.  
  392. template<class TYPE, class ARG_TYPE>
  393. POSITION CList<TYPE, ARG_TYPE>::AddTail(ARG_TYPE newElement)
  394. {
  395. $ifndef INCLUDE_TYPEREF
  396.     ASSERT_VALID(this);
  397.  
  398.     CNode* pNewNode = NewNode(m_pNodeTail, NULL);
  399.     pNewNode->data = newElement;
  400.     if (m_pNodeTail != NULL)
  401.         m_pNodeTail->pNext = pNewNode;
  402.     else
  403.         m_pNodeHead = pNewNode;
  404.     m_pNodeTail = pNewNode;
  405.     return (POSITION) pNewNode;
  406. $else
  407.     return AddTail(TYPE(newElement));
  408. $endif
  409. }
  410.  
  411. $ifdef INCLUDE_TYPEREF
  412. template<class TYPE, class ARG_TYPE>
  413. POSITION CList<TYPE, ARG_TYPE>::AddTail(const TYPE& newElement)
  414. {
  415.     ASSERT_VALID(this);
  416.  
  417.     CNode* pNewNode = NewNode(m_pNodeTail, NULL);
  418.     pNewNode->data = newElement;
  419.     if (m_pNodeTail != NULL)
  420.         m_pNodeTail->pNext = pNewNode;
  421.     else
  422.         m_pNodeHead = pNewNode;
  423.     m_pNodeTail = pNewNode;
  424.     return (POSITION) pNewNode;
  425. }
  426. $endif
  427.  
  428. template<class TYPE, class ARG_TYPE>
  429. void CList<TYPE, ARG_TYPE>::AddHead(CList* pNewList)
  430. {
  431.     ASSERT_VALID(this);
  432.  
  433.     ASSERT(pNewList != NULL);
  434.     ASSERT_KINDOF(CList, pNewList);
  435.     ASSERT_VALID(pNewList);
  436.  
  437.     // add a list of same elements to head (maintain order)
  438.     POSITION pos = pNewList->GetTailPosition();
  439.     while (pos != NULL)
  440.         AddHead(pNewList->GetPrev(pos));
  441. }
  442.  
  443. template<class TYPE, class ARG_TYPE>
  444. void CList<TYPE, ARG_TYPE>::AddTail(CList* pNewList)
  445. {
  446.     ASSERT_VALID(this);
  447.     ASSERT(pNewList != NULL);
  448.     ASSERT_KINDOF(CList, pNewList);
  449.     ASSERT_VALID(pNewList);
  450.  
  451.     // add a list of same elements
  452.     POSITION pos = pNewList->GetHeadPosition();
  453.     while (pos != NULL)
  454.         AddTail(pNewList->GetNext(pos));
  455. }
  456.  
  457. template<class TYPE, class ARG_TYPE>
  458. TYPE CList<TYPE, ARG_TYPE>::RemoveHead()
  459. {
  460.     ASSERT_VALID(this);
  461.     ASSERT(m_pNodeHead != NULL);  // don't call on empty list !!!
  462.     ASSERT(AfxIsValidAddress(m_pNodeHead, sizeof(CNode)));
  463.  
  464.     CNode* pOldNode = m_pNodeHead;
  465.     TYPE returnValue = pOldNode->data;
  466.  
  467.     m_pNodeHead = pOldNode->pNext;
  468.     if (m_pNodeHead != NULL)
  469.         m_pNodeHead->pPrev = NULL;
  470.     else
  471.         m_pNodeTail = NULL;
  472.     FreeNode(pOldNode);
  473.     return returnValue;
  474. }
  475.  
  476. template<class TYPE, class ARG_TYPE>
  477. TYPE CList<TYPE, class ARG_TYPE>::RemoveTail()
  478. {
  479.     ASSERT_VALID(this);
  480.     ASSERT(m_pNodeTail != NULL);  // don't call on empty list !!!
  481.     ASSERT(AfxIsValidAddress(m_pNodeTail, sizeof(CNode)));
  482.  
  483.     CNode* pOldNode = m_pNodeTail;
  484.     TYPE returnValue = pOldNode->data;
  485.  
  486.     m_pNodeTail = pOldNode->pPrev;
  487.     if (m_pNodeTail != NULL)
  488.         m_pNodeTail->pNext = NULL;
  489.     else
  490.         m_pNodeHead = NULL;
  491.     FreeNode(pOldNode);
  492.     return returnValue;
  493. }
  494.  
  495. template<class TYPE, class ARG_TYPE>
  496. POSITION CList<TYPE>::InsertBefore(POSITION position, ARG_TYPE newElement)
  497. {
  498. $ifndef INCLUDE_TYPEREF
  499.     ASSERT_VALID(this);
  500.  
  501.     if (position == NULL)
  502.         return AddHead(newElement); // insert before nothing -> head of the list
  503.  
  504.     // Insert it before position
  505.     CNode* pOldNode = (CNode*) position;
  506.     CNode* pNewNode = NewNode(pOldNode->pPrev, pOldNode);
  507.     pNewNode->data = newElement;
  508.  
  509.     if (pOldNode->pPrev != NULL)
  510.     {
  511.         ASSERT(AfxIsValidAddress(pOldNode->pPrev, sizeof(CNode)));
  512.         pOldNode->pPrev->pNext = pNewNode;
  513.     }
  514.     else
  515.     {
  516.         ASSERT(pOldNode == m_pNodeHead);
  517.         m_pNodeHead = pNewNode;
  518.     }
  519.     pOldNode->pPrev = pNewNode;
  520.     return (POSITION) pNewNode;
  521. $else
  522.     return InsertBefore(position, TYPE(newElement));
  523. $endif
  524. }
  525.  
  526. $ifdef INCLUDE_TYPEREF
  527. template<class TYPE, class ARG_TYPE>
  528. POSITION CList<TYPE>::InsertBefore(POSITION position, const TYPE& newElement)
  529. {
  530.     ASSERT_VALID(this);
  531.  
  532.     if (position == NULL)
  533.         return AddHead(newElement); // insert before nothing -> head of the list
  534.  
  535.     // Insert it before position
  536.     CNode* pOldNode = (CNode*) position;
  537.     CNode* pNewNode = NewNode(pOldNode->pPrev, pOldNode);
  538.     pNewNode->data = newElement;
  539.  
  540.     if (pOldNode->pPrev != NULL)
  541.     {
  542.         ASSERT(AfxIsValidAddress(pOldNode->pPrev, sizeof(CNode)));
  543.         pOldNode->pPrev->pNext = pNewNode;
  544.     }
  545.     else
  546.     {
  547.         ASSERT(pOldNode == m_pNodeHead);
  548.         m_pNodeHead = pNewNode;
  549.     }
  550.     pOldNode->pPrev = pNewNode;
  551.     return (POSITION) pNewNode;
  552. }
  553. $endif
  554.  
  555. template<class TYPE, class ARG_TYPE>
  556. POSITION CList<TYPE, ARG_TYPE>::InsertAfter(POSITION position, ARG_TYPE newElement)
  557. {
  558. $ifndef INCLUDE_TYPEREF
  559.     ASSERT_VALID(this);
  560.  
  561.     if (position == NULL)
  562.         return AddTail(newElement); // insert after nothing -> tail of the list
  563.  
  564.     // Insert it before position
  565.     CNode* pOldNode = (CNode*) position;
  566.     ASSERT(AfxIsValidAddress(pOldNode, sizeof(CNode)));
  567.     CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext);
  568.     pNewNode->data = newElement;
  569.  
  570.     if (pOldNode->pNext != NULL)
  571.     {
  572.         ASSERT(AfxIsValidAddress(pOldNode->pNext, sizeof(CNode)));
  573.         pOldNode->pNext->pPrev = pNewNode;
  574.     }
  575.     else
  576.     {
  577.         ASSERT(pOldNode == m_pNodeTail);
  578.         m_pNodeTail = pNewNode;
  579.     }
  580.     pOldNode->pNext = pNewNode;
  581.     return (POSITION) pNewNode;
  582. $else
  583.     return InsertAfter(position, TYPE(newElement));
  584. $endif
  585. }
  586.  
  587. $ifdef INCLUDE_TYPEREF
  588. template<class TYPE, class ARG_TYPE>
  589. POSITION CList<TYPE, ARG_TYPE>::InsertAfter(POSITION position, const TYPE& newElement)
  590. {
  591.     ASSERT_VALID(this);
  592.  
  593.     if (position == NULL)
  594.         return AddTail(newElement); // insert after nothing -> tail of the list
  595.  
  596.     // Insert it before position
  597.     CNode* pOldNode = (CNode*) position;
  598.     ASSERT(AfxIsValidAddress(pOldNode, sizeof(CNode)));
  599.     CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext);
  600.     pNewNode->data = newElement;
  601.  
  602.     if (pOldNode->pNext != NULL)
  603.     {
  604.         ASSERT(AfxIsValidAddress(pOldNode->pNext, sizeof(CNode)));
  605.         pOldNode->pNext->pPrev = pNewNode;
  606.     }
  607.     else
  608.     {
  609.         ASSERT(pOldNode == m_pNodeTail);
  610.         m_pNodeTail = pNewNode;
  611.     }
  612.     pOldNode->pNext = pNewNode;
  613.     return (POSITION) pNewNode;
  614. }
  615. $endif
  616.  
  617. template<class TYPE, class ARG_TYPE>
  618. void CList<TYPE, ARG_TYPE>::RemoveAt(POSITION position)
  619. {
  620.     ASSERT_VALID(this);
  621.  
  622.     CNode* pOldNode = (CNode*) position;
  623.     ASSERT(AfxIsValidAddress(pOldNode, sizeof(CNode)));
  624.  
  625.     // remove pOldNode from list
  626.     if (pOldNode == m_pNodeHead)
  627.     {
  628.         m_pNodeHead = pOldNode->pNext;
  629.     }
  630.     else
  631.     {
  632.         ASSERT(AfxIsValidAddress(pOldNode->pPrev, sizeof(CNode)));
  633.         pOldNode->pPrev->pNext = pOldNode->pNext;
  634.     }
  635.     if (pOldNode == m_pNodeTail)
  636.     {
  637.         m_pNodeTail = pOldNode->pPrev;
  638.     }
  639.     else
  640.     {
  641.         ASSERT(AfxIsValidAddress(pOldNode->pNext, sizeof(CNode)));
  642.         pOldNode->pNext->pPrev = pOldNode->pPrev;
  643.     }
  644.     FreeNode(pOldNode);
  645. }
  646.  
  647.  
  648. /////////////////////////////////////////////////////////////////////////////
  649. // slow operations
  650.  
  651. template<class TYPE, class ARG_TYPE>
  652. POSITION CList<TYPE, ARG_TYPE>::FindIndex(int nIndex) const
  653. {
  654.     ASSERT_VALID(this);
  655.  
  656.     if (nIndex >= m_nCount || nIndex < 0)
  657.         return NULL;  // went too far
  658.  
  659.     CNode* pNode = m_pNodeHead;
  660.     while (nIndex--)
  661.     {
  662.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  663.         pNode = pNode->pNext;
  664.     }
  665.     return (POSITION) pNode;
  666. }
  667.  
  668. template<class TYPE, class ARG_TYPE>
  669. POSITION CList<TYPE, ARG_TYPE>::Find(ARG_TYPE searchValue, POSITION startAfter) const
  670. {
  671.     ASSERT_VALID(this);
  672.  
  673.     CNode* pNode = (CNode*) startAfter;
  674.     if (pNode == NULL)
  675.     {
  676.         pNode = m_pNodeHead;  // start at head
  677.     }
  678.     else
  679.     {
  680.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  681.         pNode = pNode->pNext;  // start after the one specified
  682.     }
  683.  
  684.     for (; pNode != NULL; pNode = pNode->pNext)
  685.         if (pNode->data == searchValue)
  686.             return (POSITION) pNode;
  687.     return NULL;
  688. }
  689.  
  690. $ifdef IS_SERIAL
  691. /////////////////////////////////////////////////////////////////////////////
  692. // Serialization
  693.  
  694. template<class TYPE, class ARG_TYPE>
  695. void CList<TYPE, ARG_TYPE>::Serialize(CArchive& ar)
  696. {
  697.     ASSERT_VALID(this);
  698.  
  699.     CObject::Serialize(ar);
  700.  
  701.     if (ar.IsStoring())
  702.     {
  703.         ar.WriteCount(m_nCount);
  704.         for (CNode* pNode = m_pNodeHead; pNode != NULL; pNode = pNode->pNext)
  705.         {
  706.             ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  707.             ar << pNode->data;
  708.         }
  709.     }
  710.     else
  711.     {
  712.         DWORD nNewCount = ar.ReadCount();
  713.         TYPE newData;
  714.         while (nNewCount--)
  715.         {
  716.             ar >> newData;
  717.             AddTail(newData);
  718.         }
  719.     }
  720. }
  721. $endif //IS_SERIAL
  722.  
  723. /////////////////////////////////////////////////////////////////////////////
  724. // Diagnostics
  725.  
  726. #ifdef _DEBUG
  727. template<class TYPE, class ARG_TYPE>
  728. void CList<TYPE, ARG_TYPE>::Dump(CDumpContext& dc) const
  729. {
  730.     CObject::Dump(dc);
  731.  
  732.     dc << "with " << m_nCount << " elements";
  733.     if (dc.GetDepth() > 0)
  734.     {
  735.         POSITION pos = GetHeadPosition();
  736.         while (pos != NULL)
  737.             dc << "\n\t" << GetNext(pos);
  738.     }
  739.  
  740.     dc << "\n";
  741. }
  742.  
  743. template<class TYPE, class ARG_TYPE>
  744. void CList<TYPE, ARG_TYPE>::AssertValid() const
  745. {
  746.     CObject::AssertValid();
  747.  
  748.     if (m_nCount == 0)
  749.     {
  750.         // empty list
  751.         ASSERT(m_pNodeHead == NULL);
  752.         ASSERT(m_pNodeTail == NULL);
  753.     }
  754.     else
  755.     {
  756.         // non-empty list
  757.         ASSERT(AfxIsValidAddress(m_pNodeHead, sizeof(CNode)));
  758.         ASSERT(AfxIsValidAddress(m_pNodeTail, sizeof(CNode)));
  759.     }
  760. }
  761. #endif //_DEBUG
  762.  
  763. #ifdef AFX_INIT_SEG
  764. #pragma code_seg(AFX_INIT_SEG)
  765. #endif
  766.  
  767. $ifdef IS_SERIAL
  768. IMPLEMENT_SERIAL(CList, CObject, 0)
  769. $else
  770. IMPLEMENT_DYNAMIC(CList, CObject)
  771. $endif //!IS_SERIAL
  772.  
  773. /////////////////////////////////////////////////////////////////////////////
  774.