home *** CD-ROM | disk | FTP | other *** search
/ Programming Languages Suite / ProgLangD.iso / C++-7 / DISK8 / MFC / SAMPLES / TEMPLDEF / LIST.CT$ / list
Encoding:
Text File  |  1992-01-12  |  15.3 KB  |  569 lines
  1. /////////////////////////////////////////////////////////////////////////////
  2. // class CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE> - a list containing 'TYPE' elements
  3. // passed in parameters as ARG_TYPE
  4. //
  5. // This is a part of the Microsoft Foundation Classes C++ library.
  6. // Copyright (C) 1992 Microsoft Corporation
  7. // All rights reserved.
  8. //
  9. // This source code is only intended as a supplement to the
  10. // Microsoft Foundation Classes Reference and Microsoft
  11. // QuickHelp documentation provided with the library.
  12. // See these sources for detailed information regarding the
  13. // Microsoft Foundation Classes product.
  14. /////////////////////////////////////////////////////////////////////////////
  15.  
  16. //$DECLARE_TEMPLATE
  17.  
  18. /////////////////////////////////////////////////////////////////////////////
  19.  
  20. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  21. class CList : public CObject
  22. {
  23. #if IS_SERIAL
  24.     DECLARE_SERIAL(CList)
  25. #else
  26.     DECLARE_DYNAMIC(CList)
  27. #endif //!IS_SERIAL
  28.  
  29. protected:
  30.     struct CNode
  31.     {
  32.         CNode*  pNext;
  33.         CNode*  pPrev;
  34.         TYPE    data;
  35.     };
  36. public:
  37.  
  38. // Construction
  39.     CList(int nBlockSize=10);
  40.  
  41. // Attributes (head and tail)
  42.     // count of elements
  43.     int     GetCount() const
  44.                 { return m_nCount; }
  45.     BOOL    IsEmpty() const
  46.                 { return m_nCount == 0; }
  47.  
  48.     // peek at head or tail
  49.     TYPE&   GetHead()
  50.                 { ASSERT(m_pNodeHead != NULL);
  51.                     return m_pNodeHead->data; }
  52.     TYPE    GetHead() const
  53.                 { ASSERT(m_pNodeHead != NULL);
  54.                     return m_pNodeHead->data; }
  55.     TYPE&   GetTail()
  56.                 { ASSERT(m_pNodeTail != NULL);
  57.                     return m_pNodeTail->data; }
  58.     TYPE    GetTail() const
  59.                 { ASSERT(m_pNodeTail != NULL);
  60.                     return m_pNodeTail->data; }
  61.  
  62. // Operations
  63.     // get head or tail (and remove it) - don't call on empty list !
  64.     TYPE    RemoveHead();
  65.     TYPE    RemoveTail();
  66.  
  67.     // add before head or after tail
  68.     POSITION AddHead(ARG_TYPE newElement);
  69.     POSITION AddTail(ARG_TYPE newElement);
  70.  
  71.     // add another list of elements before head or after tail
  72.     void    AddHead(CList* pNewList);
  73.     void    AddTail(CList* pNewList);
  74.  
  75.     // remove all elements
  76.     void    RemoveAll();
  77.  
  78.     // iteration
  79.     POSITION GetHeadPosition() const
  80.                 { return (POSITION) m_pNodeHead; }
  81.     POSITION GetTailPosition() const
  82.                 { return (POSITION) m_pNodeTail; }
  83.     TYPE&   GetNext(POSITION& rPosition) // return *Position++
  84.                 { CNode* pNode = (CNode*) rPosition;
  85.                     ASSERT(pNode != NULL);
  86.                     rPosition = (POSITION) pNode->pNext;
  87.                     return pNode->data; }
  88.     TYPE    GetNext(POSITION& rPosition) const // return *Position++
  89.                 { CNode* pNode = (CNode*) rPosition;
  90.                     ASSERT(pNode != NULL);
  91.                     rPosition = (POSITION) pNode->pNext;
  92.                     return pNode->data; }
  93.     TYPE&   GetPrev(POSITION& rPosition) // return *Position--
  94.                 { CNode* pNode = (CNode*) rPosition;
  95.                     ASSERT(pNode != NULL);
  96.                     rPosition = (POSITION) pNode->pPrev;
  97.                     return pNode->data; }
  98.     TYPE    GetPrev(POSITION& rPosition) const // return *Position--
  99.                 { CNode* pNode = (CNode*) rPosition;
  100.                     ASSERT(pNode != NULL);
  101.                     rPosition = (POSITION) pNode->pPrev;
  102.                     return pNode->data; }
  103.  
  104.     // getting/modifying an element at a given position
  105.     TYPE&   GetAt(POSITION position)
  106.                 { CNode* pNode = (CNode*) position;
  107.                     ASSERT(pNode != NULL);
  108.                     return pNode->data; }
  109.     TYPE    GetAt(POSITION position) const
  110.                 { CNode* pNode = (CNode*) position;
  111.                     ASSERT(pNode != NULL);
  112.                     return pNode->data; }
  113.     void    SetAt(POSITION pos, ARG_TYPE newElement)
  114.                 { CNode* pNode = (CNode*) pos;
  115.                     ASSERT(pNode != NULL);
  116.                     pNode->data = newElement; }
  117.     void    RemoveAt(POSITION position);
  118.  
  119.     // inserting before or after a given position
  120.     POSITION InsertBefore(POSITION position, ARG_TYPE newElement);
  121.     POSITION InsertAfter(POSITION position, ARG_TYPE newElement);
  122.  
  123.     // helper functions (note: O(n) speed)
  124.     POSITION Find(ARG_TYPE searchValue, POSITION startAfter = NULL) const;
  125.                         // defaults to starting at the HEAD
  126.                         // return NULL if not found
  127.     POSITION FindIndex(int nIndex) const;
  128.                         // get the 'nIndex'th element (may return NULL)
  129.  
  130. // Implementation
  131. protected:
  132.     CNode*  m_pNodeHead;
  133.     CNode*  m_pNodeTail;
  134.     int     m_nCount;
  135.     CNode*  m_pNodeFree;
  136.     struct CPlex* m_pBlocks;
  137.     int     m_nBlockSize;
  138.  
  139.     CNode*  NewNode(CNode*, CNode*);
  140.     void    FreeNode(CNode*);
  141.  
  142. public:
  143.     ~CList();
  144. #if IS_SERIAL
  145.     void    Serialize(CArchive&);
  146. #endif //IS_SERIAL
  147. #ifdef _DEBUG
  148.     void    Dump(CDumpContext&) const;
  149.     void    AssertValid() const;
  150. #endif
  151. };
  152.  
  153. //$IMPLEMENT_TEMPLATE
  154.  
  155. /////////////////////////////////////////////////////////////////////////////
  156. //
  157. // Implementation of List of TYPEs
  158. //
  159. /////////////////////////////////////////////////////////////////////////////
  160.  
  161. #include "afxcoll.h"
  162. #pragma hdrstop
  163.  
  164. #include "plex.h"
  165.  
  166. #ifdef AFX_COLL_SEG
  167. #pragma code_seg(AFX_COLL_SEG)
  168. #endif
  169.  
  170. #if IS_SERIAL
  171. IMPLEMENT_SERIAL(CList, CObject, 0);
  172. #else
  173. IMPLEMENT_DYNAMIC(CList, CObject);
  174. #endif //!IS_SERIAL
  175.  
  176. #ifdef _DEBUG
  177. #undef THIS_FILE
  178. static char BASED_CODE THIS_FILE[] = __FILE__;
  179. #endif
  180.  
  181. #if HAS_CREATE
  182. #include "elements.h"       // used for special creation
  183. #endif
  184.  
  185. /////////////////////////////////////////////////////////////////////////////
  186.  
  187. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  188. CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::CList(int nBlockSize)
  189. {
  190.     ASSERT(nBlockSize > 0);
  191.  
  192.     m_nCount = 0;
  193.     m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
  194.     m_pBlocks = NULL;
  195.     m_nBlockSize = nBlockSize;
  196. }
  197.  
  198. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  199. void CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::RemoveAll()
  200. {
  201.     ASSERT_VALID(this);
  202.  
  203.     // destroy elements
  204. #if HAS_CREATE
  205.     register CNode* pNode;
  206.     for (pNode = m_pNodeHead; pNode != NULL; pNode = pNode->pNext)
  207.         DestructElement(&pNode->data);
  208. #endif
  209.  
  210.     m_nCount = 0;
  211.     m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
  212.     m_pBlocks->FreeDataChain();
  213.     m_pBlocks = NULL;
  214. }
  215.  
  216. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  217. CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::~CList()
  218. {
  219.     RemoveAll();
  220.     ASSERT(m_nCount == 0);
  221. }
  222.  
  223. /////////////////////////////////////////////////////////////////////////////
  224. // Node helpers
  225. /*
  226.  * Implementation note: CNode's are stored in CPlex blocks and
  227.  *  chained together. Free blocks are maintained in a singly linked list
  228.  *  using the 'pNext' member of CNode with 'm_pNodeFree' as the head.
  229.  *  Used blocks are maintained in a doubly linked list using both 'pNext'
  230.  *  and 'pPrev' as links and 'm_pNodeHead' and 'm_pNodeTail'
  231.  *   as the head/tail.
  232.  *
  233.  * We never free a CPlex block unless the List is destroyed or RemoveAll()
  234.  *  is used - so the total number of CPlex blocks may grow large depending
  235.  *  on the maximum past size of the list.
  236.  */
  237.  
  238. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  239. CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::CNode*
  240. CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::NewNode(CList::CNode* pPrev, CList::CNode* pNext)
  241. {
  242.     if (m_pNodeFree == NULL)
  243.     {
  244.         // add another block
  245.         CPlex* pNewBlock = CPlex::Create(m_pBlocks, m_nBlockSize,
  246.                  sizeof(CNode));
  247.  
  248.         // chain them into free list
  249.         CNode* pNode = (CNode*) pNewBlock->data();
  250.         // free in reverse order to make it easier to debug
  251.         pNode += m_nBlockSize - 1;
  252.         for (int i = m_nBlockSize-1; i >= 0; i--, pNode--)
  253.         {
  254.             pNode->pNext = m_pNodeFree;
  255.             m_pNodeFree = pNode;
  256.         }
  257.     }
  258.     ASSERT(m_pNodeFree != NULL); // we must have something
  259.  
  260.     register CList::CNode* pNode = m_pNodeFree;
  261.     m_pNodeFree = m_pNodeFree->pNext;
  262.     pNode->pPrev = pPrev;
  263.     pNode->pNext = pNext;
  264.     m_nCount++;
  265.     ASSERT(m_nCount > 0);       // make sure we don't overflow
  266.  
  267. #if HAS_CREATE
  268.     ConstructElement(&pNode->data);
  269. #else
  270.     memset(&pNode->data, 0, sizeof(TYPE));          // zero fill
  271. #endif
  272.     return pNode;
  273. }
  274.  
  275. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  276. void CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::FreeNode(CList::CNode* pNode)
  277. {
  278. #if HAS_CREATE
  279.     DestructElement(&pNode->data);
  280. #endif
  281.     pNode->pNext = m_pNodeFree;
  282.     m_pNodeFree = pNode;
  283.     m_nCount--;
  284.     ASSERT(m_nCount >= 0);      // make sure we don't underflow
  285. }
  286.  
  287. /////////////////////////////////////////////////////////////////////////////
  288.  
  289. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  290. POSITION CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::AddHead(ARG_TYPE newElement)
  291. {
  292.     ASSERT_VALID(this);
  293.  
  294.     CNode* pNewNode = NewNode(NULL, m_pNodeHead);
  295.     pNewNode->data = newElement;
  296.     if (m_pNodeHead != NULL)
  297.         m_pNodeHead->pPrev = pNewNode;
  298.     else
  299.         m_pNodeTail = pNewNode;
  300.     m_pNodeHead = pNewNode;
  301.     return (POSITION) pNewNode;
  302. }
  303.  
  304. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  305. POSITION CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::AddTail(ARG_TYPE newElement)
  306. {
  307.     ASSERT_VALID(this);
  308.  
  309.     CNode* pNewNode = NewNode(m_pNodeTail, NULL);
  310.     pNewNode->data = newElement;
  311.     if (m_pNodeTail != NULL)
  312.         m_pNodeTail->pNext = pNewNode;
  313.     else
  314.         m_pNodeHead = pNewNode;
  315.     m_pNodeTail = pNewNode;
  316.     return (POSITION) pNewNode;
  317. }
  318.  
  319. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  320. void CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::AddHead(CList* pNewList)
  321. {
  322.     ASSERT_VALID(this);
  323.  
  324.     ASSERT(pNewList != NULL);
  325.     ASSERT(pNewList->IsKindOf(RUNTIME_CLASS(CList)));
  326.     ASSERT_VALID(pNewList);
  327.  
  328.     // add a list of same elements to head (maintain order)
  329.     POSITION pos = pNewList->GetTailPosition();
  330.     while (pos != NULL)
  331.         AddHead(pNewList->GetPrev(pos));
  332. }
  333.  
  334. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  335. void CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::AddTail(CList* pNewList)
  336. {
  337.     ASSERT_VALID(this);
  338.     ASSERT(pNewList != NULL);
  339.     ASSERT(pNewList->IsKindOf(RUNTIME_CLASS(CList)));
  340.     ASSERT_VALID(pNewList);
  341.  
  342.     // add a list of same elements
  343.     POSITION pos = pNewList->GetHeadPosition();
  344.     while (pos)
  345.         AddTail(pNewList->GetNext(pos));
  346. }
  347.  
  348. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  349. TYPE CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::RemoveHead()
  350. {
  351.     ASSERT_VALID(this);
  352.     ASSERT(m_pNodeHead != NULL);    // don't call on empty list !!!
  353.  
  354.     CNode* pOldNode = m_pNodeHead;
  355.     ASSERT(pOldNode != NULL);
  356.     TYPE returnValue = pOldNode->data;
  357.  
  358.     m_pNodeHead = pOldNode->pNext;
  359.     if (m_pNodeHead != NULL)
  360.         m_pNodeHead->pPrev = NULL;
  361.     else
  362.         m_pNodeTail = NULL;
  363.     FreeNode(pOldNode);
  364.     return returnValue;
  365. }
  366.  
  367. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  368. TYPE CList<TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>::RemoveTail()
  369. {
  370.     ASSERT_VALID(this);
  371.     ASSERT(m_pNodeTail != NULL);    // don't call on empty list !!!
  372.  
  373.     CNode* pOldNode = m_pNodeTail;
  374.     ASSERT(pOldNode != NULL);
  375.     TYPE returnValue = pOldNode->data;
  376.  
  377.     m_pNodeTail = pOldNode->pPrev;
  378.     if (m_pNodeTail != NULL)
  379.         m_pNodeTail->pNext = NULL;
  380.     else
  381.         m_pNodeHead = NULL;
  382.     FreeNode(pOldNode);
  383.     return returnValue;
  384. }
  385.  
  386. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  387. POSITION CList<TYPE>::InsertBefore(POSITION position, ARG_TYPE newElement)
  388. {
  389.     ASSERT_VALID(this);
  390.  
  391.     if (position == NULL)
  392.         return AddHead(newElement); // insert before nothing -> head of the list
  393.  
  394.     // Insert it before position
  395.     CNode* pOldNode = (CNode*) position;
  396.     CNode* pNewNode = NewNode(pOldNode->pPrev, pOldNode);
  397.     pNewNode->data = newElement;
  398.  
  399.     if (pOldNode->pPrev != NULL)
  400.     {
  401.         pOldNode->pPrev->pNext = pNewNode;
  402.     }
  403.     else
  404.     {
  405.         ASSERT(pOldNode == m_pNodeHead);
  406.         m_pNodeHead = pNewNode;
  407.     }
  408.     pOldNode->pPrev = pNewNode;
  409.     return (POSITION) pNewNode;
  410. }
  411.  
  412. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  413. POSITION CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::InsertAfter(POSITION position, ARG_TYPE newElement)
  414. {
  415.     ASSERT_VALID(this);
  416.  
  417.     if (position == NULL)
  418.         return AddTail(newElement); // insert after nothing -> tail of the list
  419.  
  420.     // Insert it before position
  421.     CNode* pOldNode = (CNode*) position;
  422.     CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext);
  423.     pNewNode->data = newElement;
  424.  
  425.     if (pOldNode->pNext != NULL)
  426.     {
  427.         pOldNode->pNext->pPrev = pNewNode;
  428.     }
  429.     else
  430.     {
  431.         ASSERT(pOldNode == m_pNodeTail);
  432.         m_pNodeTail = pNewNode;
  433.     }
  434.     pOldNode->pNext = pNewNode;
  435.     return (POSITION) pNewNode;
  436. }
  437.  
  438. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  439. void CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::RemoveAt(POSITION position)
  440. {
  441.     ASSERT_VALID(this);
  442.     ASSERT(position != NULL);
  443.  
  444.     CNode* pOldNode = (CNode*) position;
  445.  
  446.     // remove pOldNode from list
  447.     if (pOldNode == m_pNodeHead)
  448.         m_pNodeHead = pOldNode->pNext;
  449.     else
  450.         pOldNode->pPrev->pNext = pOldNode->pNext;
  451.     if (pOldNode == m_pNodeTail)
  452.         m_pNodeTail = pOldNode->pPrev;
  453.     else
  454.         pOldNode->pNext->pPrev = pOldNode->pPrev;
  455.     FreeNode(pOldNode);
  456. }
  457.  
  458.  
  459. /////////////////////////////////////////////////////////////////////////////
  460. // slow operations
  461.  
  462. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  463. POSITION CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::FindIndex(int nIndex) const
  464. {
  465.     ASSERT_VALID(this);
  466.     ASSERT(nIndex >= 0);
  467.  
  468.     if (nIndex >= m_nCount)
  469.         return NULL;        // went too far
  470.  
  471.     register CNode* pNode = m_pNodeHead;
  472.     while (nIndex--)
  473.         pNode = pNode->pNext;
  474.     return (POSITION) pNode;
  475. }
  476.  
  477. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  478. POSITION CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::Find(ARG_TYPE searchValue, POSITION startAfter) const
  479. {
  480.     ASSERT_VALID(this);
  481.  
  482.     register CNode* pNode = (CNode*) startAfter;
  483.     if (pNode == NULL)
  484.         pNode = m_pNodeHead;        // start at head
  485.     else
  486.         pNode = pNode->pNext;       // start after the one specified
  487.  
  488.     for (; pNode != NULL; pNode = pNode->pNext)
  489.         if (pNode->data == searchValue)
  490.             return (POSITION) pNode;
  491.     return NULL;
  492. }
  493.  
  494. /////////////////////////////////////////////////////////////////////////////
  495. // Serialization
  496.  
  497. #if IS_SERIAL
  498. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  499. void CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::Serialize(CArchive& ar)
  500. {
  501.     ASSERT_VALID(this);
  502.  
  503.     CObject::Serialize(ar);
  504.  
  505.     if (ar.IsStoring())
  506.     {
  507.         ar << (WORD) m_nCount;
  508.         for (CNode* pNode = m_pNodeHead; pNode != NULL;
  509.           pNode = pNode->pNext)
  510.             ar << pNode->data;
  511.     }
  512.     else
  513.     {
  514.         WORD nNewCount;
  515.         ar >> nNewCount;
  516.         while (nNewCount--)
  517.         {
  518.             TYPE newData;
  519.             ar >> newData;
  520.             AddTail(newData);
  521.         }
  522.     }
  523. }
  524. #endif //IS_SERIAL
  525.  
  526. /////////////////////////////////////////////////////////////////////////////
  527. // Diagnostics
  528.  
  529. #ifdef _DEBUG
  530. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  531. void CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::Dump(CDumpContext& dc) const
  532. {
  533.     ASSERT_VALID(this);
  534.  
  535. #define MAKESTRING(x) #x
  536.     dc << "a " MAKESTRING(CList) " with " << m_nCount << " elements";
  537. #undef MAKESTRING
  538.     if (dc.GetDepth() > 0)
  539.     {
  540.         POSITION pos = GetHeadPosition();
  541.         dc << "\n";
  542.  
  543.         while (pos != NULL)
  544.             dc << "\n\t" << GetNext(pos);
  545.     }
  546. }
  547.  
  548. template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
  549. void CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::AssertValid() const
  550. {
  551.     CObject::AssertValid();
  552.  
  553.     if (m_nCount == 0)
  554.     {
  555.         // empty list
  556.         ASSERT(m_pNodeHead == NULL);
  557.         ASSERT(m_pNodeTail == NULL);
  558.     }
  559.     else
  560.     {
  561.         // non-empty list
  562.         ASSERT(m_pNodeHead != NULL);
  563.         ASSERT(m_pNodeTail != NULL);
  564.     }
  565. }
  566. #endif //_DEBUG
  567.  
  568. /////////////////////////////////////////////////////////////////////////////
  569.