home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c031 / 10.ddi / MFC / SRC / LIST_S.CP$ / list_s
Encoding:
Text File  |  1992-01-10  |  8.8 KB  |  411 lines
  1.  
  2.  
  3. /////////////////////////////////////////////////////////////////////////////
  4. //
  5. // Implementation of List of TYPEs
  6. //
  7. /////////////////////////////////////////////////////////////////////////////
  8.  
  9. #include "afxcoll.h"
  10. #pragma hdrstop
  11.  
  12. #include "plex.h"
  13.  
  14. #ifdef AFX_COLL_SEG
  15. #pragma code_seg(AFX_COLL_SEG)
  16. #endif
  17.  
  18.  
  19. IMPLEMENT_SERIAL(CStringList, CObject, 0);
  20.  
  21. #ifdef _DEBUG
  22. #undef THIS_FILE
  23. static char BASED_CODE THIS_FILE[] = __FILE__;
  24. #endif
  25.  
  26.  
  27. #include "elements.h"       // used for special creation
  28.  
  29.  
  30. /////////////////////////////////////////////////////////////////////////////
  31.  
  32.   
  33. CStringList::CStringList(int nBlockSize)
  34. {
  35.     ASSERT(nBlockSize > 0);
  36.  
  37.     m_nCount = 0;
  38.     m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
  39.     m_pBlocks = NULL;
  40.     m_nBlockSize = nBlockSize;
  41. }
  42.  
  43.   
  44. void CStringList::RemoveAll()
  45. {
  46.     ASSERT_VALID(this);
  47.  
  48.     // destroy elements
  49.  
  50.     register CNode* pNode;
  51.     for (pNode = m_pNodeHead; pNode != NULL; pNode = pNode->pNext)
  52.         DestructElement(&pNode->data);
  53.  
  54.  
  55.     m_nCount = 0;
  56.     m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
  57.     m_pBlocks->FreeDataChain();
  58.     m_pBlocks = NULL;
  59. }
  60.  
  61.   
  62. CStringList::~CStringList()
  63. {
  64.     RemoveAll();
  65.     ASSERT(m_nCount == 0);
  66. }
  67.  
  68. /////////////////////////////////////////////////////////////////////////////
  69. // Node helpers
  70. /*
  71.  * Implementation note: CNode's are stored in CPlex blocks and
  72.  *  chained together. Free blocks are maintained in a singly linked list
  73.  *  using the 'pNext' member of CNode with 'm_pNodeFree' as the head.
  74.  *  Used blocks are maintained in a doubly linked list using both 'pNext'
  75.  *  and 'pPrev' as links and 'm_pNodeHead' and 'm_pNodeTail'
  76.  *   as the head/tail.
  77.  *
  78.  * We never free a CPlex block unless the List is destroyed or RemoveAll()
  79.  *  is used - so the total number of CPlex blocks may grow large depending
  80.  *  on the maximum past size of the list.
  81.  */
  82.  
  83.   
  84. CStringList::CNode*
  85. CStringList::NewNode(CStringList::CNode* pPrev, CStringList::CNode* pNext)
  86. {
  87.     if (m_pNodeFree == NULL)
  88.     {
  89.         // add another block
  90.         CPlex* pNewBlock = CPlex::Create(m_pBlocks, m_nBlockSize,
  91.                  sizeof(CNode));
  92.  
  93.         // chain them into free list
  94.         CNode* pNode = (CNode*) pNewBlock->data();
  95.         // free in reverse order to make it easier to debug
  96.         pNode += m_nBlockSize - 1;
  97.         for (int i = m_nBlockSize-1; i >= 0; i--, pNode--)
  98.         {
  99.             pNode->pNext = m_pNodeFree;
  100.             m_pNodeFree = pNode;
  101.         }
  102.     }
  103.     ASSERT(m_pNodeFree != NULL); // we must have something
  104.  
  105.     register CStringList::CNode* pNode = m_pNodeFree;
  106.     m_pNodeFree = m_pNodeFree->pNext;
  107.     pNode->pPrev = pPrev;
  108.     pNode->pNext = pNext;
  109.     m_nCount++;
  110.     ASSERT(m_nCount > 0);       // make sure we don't overflow
  111.  
  112.  
  113.     ConstructElement(&pNode->data);
  114.  
  115.     return pNode;
  116. }
  117.  
  118.   
  119. void CStringList::FreeNode(CStringList::CNode* pNode)
  120. {
  121.  
  122.     DestructElement(&pNode->data);
  123.  
  124.     pNode->pNext = m_pNodeFree;
  125.     m_pNodeFree = pNode;
  126.     m_nCount--;
  127.     ASSERT(m_nCount >= 0);      // make sure we don't underflow
  128. }
  129.  
  130. /////////////////////////////////////////////////////////////////////////////
  131.  
  132.   
  133. POSITION CStringList::AddHead(const char* newElement)
  134. {
  135.     ASSERT_VALID(this);
  136.  
  137.     CNode* pNewNode = NewNode(NULL, m_pNodeHead);
  138.     pNewNode->data = newElement;
  139.     if (m_pNodeHead != NULL)
  140.         m_pNodeHead->pPrev = pNewNode;
  141.     else
  142.         m_pNodeTail = pNewNode;
  143.     m_pNodeHead = pNewNode;
  144.     return (POSITION) pNewNode;
  145. }
  146.  
  147.   
  148. POSITION CStringList::AddTail(const char* newElement)
  149. {
  150.     ASSERT_VALID(this);
  151.  
  152.     CNode* pNewNode = NewNode(m_pNodeTail, NULL);
  153.     pNewNode->data = newElement;
  154.     if (m_pNodeTail != NULL)
  155.         m_pNodeTail->pNext = pNewNode;
  156.     else
  157.         m_pNodeHead = pNewNode;
  158.     m_pNodeTail = pNewNode;
  159.     return (POSITION) pNewNode;
  160. }
  161.  
  162.   
  163. void CStringList::AddHead(CStringList* pNewList)
  164. {
  165.     ASSERT_VALID(this);
  166.  
  167.     ASSERT(pNewList != NULL);
  168.     ASSERT(pNewList->IsKindOf(RUNTIME_CLASS(CStringList)));
  169.     ASSERT_VALID(pNewList);
  170.  
  171.     // add a list of same elements to head (maintain order)
  172.     POSITION pos = pNewList->GetTailPosition();
  173.     while (pos != NULL)
  174.         AddHead(pNewList->GetPrev(pos));
  175. }
  176.  
  177.   
  178. void CStringList::AddTail(CStringList* pNewList)
  179. {
  180.     ASSERT_VALID(this);
  181.     ASSERT(pNewList != NULL);
  182.     ASSERT(pNewList->IsKindOf(RUNTIME_CLASS(CStringList)));
  183.     ASSERT_VALID(pNewList);
  184.  
  185.     // add a list of same elements
  186.     POSITION pos = pNewList->GetHeadPosition();
  187.     while (pos)
  188.         AddTail(pNewList->GetNext(pos));
  189. }
  190.  
  191.   
  192. CString CStringList::RemoveHead()
  193. {
  194.     ASSERT_VALID(this);
  195.     ASSERT(m_pNodeHead != NULL);    // don't call on empty list !!!
  196.  
  197.     CNode* pOldNode = m_pNodeHead;
  198.     ASSERT(pOldNode != NULL);
  199.     CString returnValue = pOldNode->data;
  200.  
  201.     m_pNodeHead = pOldNode->pNext;
  202.     if (m_pNodeHead != NULL)
  203.         m_pNodeHead->pPrev = NULL;
  204.     else
  205.         m_pNodeTail = NULL;
  206.     FreeNode(pOldNode);
  207.     return returnValue;
  208. }
  209.  
  210.   
  211. CString CStringList::RemoveTail()
  212. {
  213.     ASSERT_VALID(this);
  214.     ASSERT(m_pNodeTail != NULL);    // don't call on empty list !!!
  215.  
  216.     CNode* pOldNode = m_pNodeTail;
  217.     ASSERT(pOldNode != NULL);
  218.     CString returnValue = pOldNode->data;
  219.  
  220.     m_pNodeTail = pOldNode->pPrev;
  221.     if (m_pNodeTail != NULL)
  222.         m_pNodeTail->pNext = NULL;
  223.     else
  224.         m_pNodeHead = NULL;
  225.     FreeNode(pOldNode);
  226.     return returnValue;
  227. }
  228.  
  229.   
  230. POSITION CStringList::InsertBefore(POSITION position, const char* newElement)
  231. {
  232.     ASSERT_VALID(this);
  233.  
  234.     if (position == NULL)
  235.         return AddHead(newElement); // insert before nothing -> head of the list
  236.  
  237.     // Insert it before position
  238.     CNode* pOldNode = (CNode*) position;
  239.     CNode* pNewNode = NewNode(pOldNode->pPrev, pOldNode);
  240.     pNewNode->data = newElement;
  241.  
  242.     if (pOldNode->pPrev != NULL)
  243.     {
  244.         pOldNode->pPrev->pNext = pNewNode;
  245.     }
  246.     else
  247.     {
  248.         ASSERT(pOldNode == m_pNodeHead);
  249.         m_pNodeHead = pNewNode;
  250.     }
  251.     pOldNode->pPrev = pNewNode;
  252.     return (POSITION) pNewNode;
  253. }
  254.  
  255.   
  256. POSITION CStringList::InsertAfter(POSITION position, const char* newElement)
  257. {
  258.     ASSERT_VALID(this);
  259.  
  260.     if (position == NULL)
  261.         return AddTail(newElement); // insert after nothing -> tail of the list
  262.  
  263.     // Insert it before position
  264.     CNode* pOldNode = (CNode*) position;
  265.     CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext);
  266.     pNewNode->data = newElement;
  267.  
  268.     if (pOldNode->pNext != NULL)
  269.     {
  270.         pOldNode->pNext->pPrev = pNewNode;
  271.     }
  272.     else
  273.     {
  274.         ASSERT(pOldNode == m_pNodeTail);
  275.         m_pNodeTail = pNewNode;
  276.     }
  277.     pOldNode->pNext = pNewNode;
  278.     return (POSITION) pNewNode;
  279. }
  280.  
  281.   
  282. void CStringList::RemoveAt(POSITION position)
  283. {
  284.     ASSERT_VALID(this);
  285.     ASSERT(position != NULL);
  286.  
  287.     CNode* pOldNode = (CNode*) position;
  288.  
  289.     // remove pOldNode from list
  290.     if (pOldNode == m_pNodeHead)
  291.         m_pNodeHead = pOldNode->pNext;
  292.     else
  293.         pOldNode->pPrev->pNext = pOldNode->pNext;
  294.     if (pOldNode == m_pNodeTail)
  295.         m_pNodeTail = pOldNode->pPrev;
  296.     else
  297.         pOldNode->pNext->pPrev = pOldNode->pPrev;
  298.     FreeNode(pOldNode);
  299. }
  300.  
  301.  
  302. /////////////////////////////////////////////////////////////////////////////
  303. // slow operations
  304.  
  305.   
  306. POSITION CStringList::FindIndex(int nIndex) const
  307. {
  308.     ASSERT_VALID(this);
  309.     ASSERT(nIndex >= 0);
  310.  
  311.     if (nIndex >= m_nCount)
  312.         return NULL;        // went too far
  313.  
  314.     register CNode* pNode = m_pNodeHead;
  315.     while (nIndex--)
  316.         pNode = pNode->pNext;
  317.     return (POSITION) pNode;
  318. }
  319.  
  320.   
  321. POSITION CStringList::Find(const char* searchValue, POSITION startAfter) const
  322. {
  323.     ASSERT_VALID(this);
  324.  
  325.     register CNode* pNode = (CNode*) startAfter;
  326.     if (pNode == NULL)
  327.         pNode = m_pNodeHead;        // start at head
  328.     else
  329.         pNode = pNode->pNext;       // start after the one specified
  330.  
  331.     for (; pNode != NULL; pNode = pNode->pNext)
  332.         if (pNode->data == searchValue)
  333.             return (POSITION) pNode;
  334.     return NULL;
  335. }
  336.  
  337. /////////////////////////////////////////////////////////////////////////////
  338. // Serialization
  339.  
  340.  
  341.   
  342. void CStringList::Serialize(CArchive& ar)
  343. {
  344.     ASSERT_VALID(this);
  345.  
  346.     CObject::Serialize(ar);
  347.  
  348.     if (ar.IsStoring())
  349.     {
  350.         ar << (WORD) m_nCount;
  351.         for (CNode* pNode = m_pNodeHead; pNode != NULL;
  352.           pNode = pNode->pNext)
  353.             ar << pNode->data;
  354.     }
  355.     else
  356.     {
  357.         WORD nNewCount;
  358.         ar >> nNewCount;
  359.         while (nNewCount--)
  360.         {
  361.             CString newData;
  362.             ar >> newData;
  363.             AddTail(newData);
  364.         }
  365.     }
  366. }
  367.  
  368. /////////////////////////////////////////////////////////////////////////////
  369. // Diagnostics
  370.  
  371. #ifdef _DEBUG
  372.   
  373. void CStringList::Dump(CDumpContext& dc) const
  374. {
  375.     ASSERT_VALID(this);
  376.  
  377. #define MAKESTRING(x) #x
  378.     dc << "a " MAKESTRING(CStringList) " with " << m_nCount << " elements";
  379. #undef MAKESTRING
  380.     if (dc.GetDepth() > 0)
  381.     {
  382.         POSITION pos = GetHeadPosition();
  383.         dc << "\n";
  384.  
  385.         while (pos != NULL)
  386.             dc << "\n\t" << GetNext(pos);
  387.     }
  388. }
  389.  
  390.   
  391. void CStringList::AssertValid() const
  392. {
  393.     CObject::AssertValid();
  394.  
  395.     if (m_nCount == 0)
  396.     {
  397.         // empty list
  398.         ASSERT(m_pNodeHead == NULL);
  399.         ASSERT(m_pNodeTail == NULL);
  400.     }
  401.     else
  402.     {
  403.         // non-empty list
  404.         ASSERT(m_pNodeHead != NULL);
  405.         ASSERT(m_pNodeTail != NULL);
  406.     }
  407. }
  408. #endif //_DEBUG
  409.  
  410. /////////////////////////////////////////////////////////////////////////////
  411.