home *** CD-ROM | disk | FTP | other *** search
/ QBasic & Borland Pascal & C / Delphi5.iso / C / BC_502 / MFCINC.PAK / AFXTEMPL.H < prev    next >
Encoding:
C/C++ Source or Header  |  1997-05-06  |  42.8 KB  |  1,647 lines
  1. // This is a part of the Microsoft Foundation Classes C++ library.
  2. // Copyright (C) 1992-1995 Microsoft Corporation
  3. // All rights reserved.
  4. //
  5. // This source code is only intended as a supplement to the
  6. // Microsoft Foundation Classes Reference and related
  7. // electronic documentation provided with the library.
  8. // See these sources for detailed information regarding the
  9. // Microsoft Foundation Classes product.
  10.  
  11. #ifndef __AFXTEMPL_H__
  12. #define __AFXTEMPL_H__
  13.  
  14. #ifndef __AFXPLEX_H__
  15.     #include <afxplex_.h>
  16. #endif
  17.  
  18. #ifdef _AFX_MINREBUILD
  19. #pragma component(minrebuild, off)
  20. #endif
  21. #ifndef _AFX_FULLTYPEINFO
  22. #pragma component(mintypeinfo, on)
  23. #endif
  24.  
  25. #ifdef _AFX_PACKING
  26. #pragma pack(push, _AFX_PACKING)
  27. #endif
  28.  
  29. #ifdef _DEBUG
  30. static char _szAfxTempl[] = "afxtempl.h";
  31. #undef THIS_FILE
  32. #define THIS_FILE _szAfxTempl
  33. #endif
  34.  
  35. #ifndef ALL_WARNINGS
  36. #pragma warning(disable: 4114)
  37. #endif
  38.  
  39. /////////////////////////////////////////////////////////////////////////////
  40. // global helpers (can be overridden)
  41.  
  42. #ifdef new
  43. #undef new
  44. #define _REDEF_NEW
  45. #endif
  46.  
  47. #ifndef _INC_NEW
  48.     #include <new.h>
  49. #endif
  50.  
  51. #if defined(__BORLANDC__) && !defined(__oaidl_h__)
  52. #include <oaidl.h>
  53. #endif
  54.  
  55. template<class TYPE>
  56. inline void AFXAPI ConstructElements(TYPE* pElements, int nCount)
  57. {
  58.     ASSERT(nCount == 0 ||
  59.         AfxIsValidAddress(pElements, nCount * sizeof(TYPE)));
  60.  
  61.     // first do bit-wise zero initialization
  62.     memset((void*)pElements, 0, nCount * sizeof(TYPE));
  63.  
  64.     // then call the constructor(s)
  65.     for (; nCount--; pElements++)
  66.         ::new((void*)pElements) TYPE;
  67. }
  68.  
  69. template<class TYPE>
  70. inline void AFXAPI DestructElements(TYPE* pElements, int nCount)
  71. {
  72.     ASSERT(nCount == 0 ||
  73.         AfxIsValidAddress(pElements, nCount * sizeof(TYPE)));
  74.  
  75.     // call the destructor(s)
  76.     for (; nCount--; pElements++)
  77.         pElements->~TYPE();
  78. }
  79.  
  80. template<class TYPE>
  81. inline void AFXAPI CopyElements(TYPE* pDest, const TYPE* pSrc, int nCount)
  82. {
  83.     ASSERT(nCount == 0 ||
  84.         AfxIsValidAddress(pDest, nCount * sizeof(TYPE)));
  85.     ASSERT(nCount == 0 ||
  86.         AfxIsValidAddress(pSrc, nCount * sizeof(TYPE)));
  87.  
  88.     // default is bit-wise copy
  89.     memcpy(pDest, pSrc, nCount * sizeof(TYPE));
  90. }
  91.  
  92. template<class TYPE>
  93. void AFXAPI SerializeElements(CArchive& ar, TYPE* pElements, int nCount)
  94. {
  95.     ASSERT(nCount == 0 ||
  96.         AfxIsValidAddress(pElements, nCount * sizeof(TYPE)));
  97.  
  98.     // default is bit-wise read/write
  99.     if (ar.IsStoring())
  100.         ar.Write((void*)pElements, nCount * sizeof(TYPE));
  101.     else
  102.         ar.Read((void*)pElements, nCount * sizeof(TYPE));
  103. }
  104.  
  105. #ifdef _DEBUG
  106. template<class TYPE>
  107. void AFXAPI DumpElements(CDumpContext& dc, const TYPE* pElements, int nCount)
  108. {
  109.     ASSERT(nCount == 0 ||
  110.         AfxIsValidAddress(pElements, nCount * sizeof(TYPE)));
  111.     &dc; // not used
  112.     pElements;  // not used
  113.     nCount; // not used
  114.  
  115.     // default does nothing
  116. }
  117. #endif
  118.  
  119. template<class TYPE, class ARG_TYPE>
  120. BOOL AFXAPI CompareElements(const TYPE* pElement1, const ARG_TYPE* pElement2)
  121. {
  122.     ASSERT(AfxIsValidAddress(pElement1, sizeof(TYPE)));
  123.     ASSERT(AfxIsValidAddress(pElement2, sizeof(ARG_TYPE)));
  124.  
  125.     return *pElement1 == *pElement2;
  126. }
  127.  
  128. template<class ARG_KEY>
  129. inline UINT AFXAPI HashKey(ARG_KEY key)
  130. {
  131.     // default identity hash - works for most primitive values
  132. #ifdef __BORLANDC__
  133.     return (*((UINT*)(void*) &key)) >> 4;
  134. #else
  135.     return ((UINT)(void*)(DWORD)key) >> 4;
  136. #endif
  137. }
  138.  
  139.  
  140. // special versions for CString
  141. void AFXAPI ConstructElements(CString* pElements, int nCount);
  142. void AFXAPI DestructElements(CString* pElements, int nCount);
  143. void AFXAPI CopyElements(CString* pDest, const CString* pSrc, int nCount);
  144. void AFXAPI SerializeElements(CArchive& ar, CString* pElements, int nCount);
  145. UINT AFXAPI HashKey(LPCTSTR key);
  146.  
  147. // forward declarations
  148. class COleVariant;
  149. struct tagVARIANT;
  150.  
  151. // special versions for COleVariant
  152. void AFXAPI ConstructElements(COleVariant* pElements, int nCount);
  153. void AFXAPI DestructElements(COleVariant* pElements, int nCount);
  154. void AFXAPI CopyElements(COleVariant* pDest, const COleVariant* pSrc, int nCount);
  155. void AFXAPI SerializeElements(CArchive& ar, COleVariant* pElements, int nCount);
  156. void AFXAPI DumpElements(CDumpContext& dc, COleVariant* pElements, int nCount);
  157.  
  158. #ifdef __BORLANDC__
  159. inline UINT AFXAPI HashKey(const struct tagVARIANT& var)
  160. {
  161.     switch (var.vt)
  162.     {
  163.     case VT_EMPTY:
  164.     case VT_NULL:
  165.         return 0;
  166.     case VT_I2:
  167.         return HashKey((DWORD)var.iVal);
  168.     case VT_I4:
  169.         return HashKey((DWORD)var.lVal);
  170.     case VT_R4:
  171.         return (UINT)(var.fltVal / 16);
  172.     case VT_R8:
  173.     case VT_CY:
  174.         return (UINT)(var.dblVal / 16);
  175.     case VT_BOOL:
  176.         return HashKey((DWORD)V_BOOL(&var));
  177.     case VT_ERROR:
  178.         return HashKey((DWORD)var.scode);
  179.     case VT_DATE:
  180.         return (UINT)(var.date / 16);
  181.     case VT_BSTR:
  182.         return HashKey(var.bstrVal);
  183.     case VT_DISPATCH:
  184.     case VT_UNKNOWN:
  185.         return HashKey((DWORD)var.punkVal);
  186.  
  187.     default:
  188.         // No support for VT_BYREF & VT_ARRAY
  189.         ASSERT(FALSE);
  190.  
  191.         // Fall through
  192.     }
  193.  
  194.     return 0;
  195. }
  196. #else    // __BORLANDC__
  197. UINT AFXAPI HashKey(const struct tagVARIANT& var);
  198. #endif   // __BORLANDC__
  199.  
  200. #define new DEBUG_NEW
  201.  
  202. /////////////////////////////////////////////////////////////////////////////
  203. // CArray<TYPE, ARG_TYPE>
  204.  
  205. template<class TYPE, class ARG_TYPE>
  206. class CArray : public CObject
  207. {
  208. public:
  209. // Construction
  210.     CArray();
  211.  
  212. // Attributes
  213.     int GetSize() const;
  214.     int GetUpperBound() const;
  215.     void SetSize(int nNewSize, int nGrowBy = -1);
  216.  
  217. // Operations
  218.     // Clean up
  219.     void FreeExtra();
  220.     void RemoveAll();
  221.  
  222.     // Accessing elements
  223.     TYPE GetAt(int nIndex) const;
  224.     void SetAt(int nIndex, ARG_TYPE newElement);
  225.     TYPE& ElementAt(int nIndex);
  226.  
  227.     // Direct Access to the element data (may return NULL)
  228.     const TYPE* GetData() const;
  229.     TYPE* GetData();
  230.  
  231.     // Potentially growing the array
  232.     void SetAtGrow(int nIndex, ARG_TYPE newElement);
  233.     int Add(ARG_TYPE newElement);
  234.     int Append(const CArray& src);
  235.     void Copy(const CArray& src);
  236.  
  237.     // overloaded operator helpers
  238.     TYPE operator[](int nIndex) const;
  239.     TYPE& operator[](int nIndex);
  240.  
  241.     // Operations that move elements around
  242.     void InsertAt(int nIndex, ARG_TYPE newElement, int nCount = 1);
  243.     void RemoveAt(int nIndex, int nCount = 1);
  244.     void InsertAt(int nStartIndex, CArray* pNewArray);
  245.  
  246. // Implementation
  247. protected:
  248.     TYPE* m_pData;   // the actual array of data
  249.     int m_nSize;     // # of elements (upperBound - 1)
  250.     int m_nMaxSize;  // max allocated
  251.     int m_nGrowBy;   // grow amount
  252.  
  253. public:
  254.     ~CArray();
  255.     void Serialize(CArchive&);
  256. #ifdef _DEBUG
  257.     void Dump(CDumpContext&) const;
  258.     void AssertValid() const;
  259. #endif
  260. };
  261.  
  262. /////////////////////////////////////////////////////////////////////////////
  263. // CArray<TYPE, ARG_TYPE> inline functions
  264.  
  265. template<class TYPE, class ARG_TYPE>
  266. inline int CArray<TYPE, ARG_TYPE>::GetSize() const
  267.     { return m_nSize; }
  268. template<class TYPE, class ARG_TYPE>
  269. inline int CArray<TYPE, ARG_TYPE>::GetUpperBound() const
  270.     { return m_nSize-1; }
  271. template<class TYPE, class ARG_TYPE>
  272. inline void CArray<TYPE, ARG_TYPE>::RemoveAll()
  273.     { SetSize(0, -1); }
  274. template<class TYPE, class ARG_TYPE>
  275. inline TYPE CArray<TYPE, ARG_TYPE>::GetAt(int nIndex) const
  276.     { ASSERT(nIndex >= 0 && nIndex < m_nSize);
  277.         return m_pData[nIndex]; }
  278. template<class TYPE, class ARG_TYPE>
  279. inline void CArray<TYPE, ARG_TYPE>::SetAt(int nIndex, ARG_TYPE newElement)
  280.     { ASSERT(nIndex >= 0 && nIndex < m_nSize);
  281.         m_pData[nIndex] = newElement; }
  282. template<class TYPE, class ARG_TYPE>
  283. inline TYPE& CArray<TYPE, ARG_TYPE>::ElementAt(int nIndex)
  284.     { ASSERT(nIndex >= 0 && nIndex < m_nSize);
  285.         return m_pData[nIndex]; }
  286. template<class TYPE, class ARG_TYPE>
  287. inline const TYPE* CArray<TYPE, ARG_TYPE>::GetData() const
  288.     { return (const TYPE*)m_pData; }
  289. template<class TYPE, class ARG_TYPE>
  290. inline TYPE* CArray<TYPE, ARG_TYPE>::GetData()
  291.     { return (TYPE*)m_pData; }
  292. template<class TYPE, class ARG_TYPE>
  293. inline int CArray<TYPE, ARG_TYPE>::Add(ARG_TYPE newElement)
  294.     { int nIndex = m_nSize;
  295.         SetAtGrow(nIndex, newElement);
  296.         return nIndex; }
  297. template<class TYPE, class ARG_TYPE>
  298. inline TYPE CArray<TYPE, ARG_TYPE>::operator[](int nIndex) const
  299.     { return GetAt(nIndex); }
  300. template<class TYPE, class ARG_TYPE>
  301. inline TYPE& CArray<TYPE, ARG_TYPE>::operator[](int nIndex)
  302.     { return ElementAt(nIndex); }
  303.  
  304. /////////////////////////////////////////////////////////////////////////////
  305. // CArray<TYPE, ARG_TYPE> out-of-line functions
  306.  
  307. template<class TYPE, class ARG_TYPE>
  308. CArray<TYPE, ARG_TYPE>::CArray()
  309. {
  310.     m_pData = NULL;
  311.     m_nSize = m_nMaxSize = m_nGrowBy = 0;
  312. }
  313.  
  314. template<class TYPE, class ARG_TYPE>
  315. CArray<TYPE, ARG_TYPE>::~CArray()
  316. {
  317.     ASSERT_VALID(this);
  318.  
  319.     if (m_pData != NULL)
  320.     {
  321.         DestructElements(m_pData, m_nSize);
  322.         delete[] (BYTE*)m_pData;
  323.     }
  324. }
  325.  
  326. template<class TYPE, class ARG_TYPE>
  327. void CArray<TYPE, ARG_TYPE>::SetSize(int nNewSize, int nGrowBy)
  328. {
  329.     ASSERT_VALID(this);
  330.     ASSERT(nNewSize >= 0);
  331.  
  332.     if (nGrowBy != -1)
  333.         m_nGrowBy = nGrowBy;  // set new size
  334.  
  335.     if (nNewSize == 0)
  336.     {
  337.         // shrink to nothing
  338.         if (m_pData != NULL)
  339.         {
  340.             DestructElements(m_pData, m_nSize);
  341.             delete[] (BYTE*)m_pData;
  342.             m_pData = NULL;
  343.         }
  344.         m_nSize = m_nMaxSize = 0;
  345.     }
  346.     else if (m_pData == NULL)
  347.     {
  348.         // create one with exact size
  349. #ifdef SIZE_T_MAX
  350.         ASSERT(nNewSize <= SIZE_T_MAX/sizeof(TYPE));    // no overflow
  351. #endif
  352.         m_pData = (TYPE*) new BYTE[nNewSize * sizeof(TYPE)];
  353.         ConstructElements(m_pData, nNewSize);
  354.         m_nSize = m_nMaxSize = nNewSize;
  355.     }
  356.     else if (nNewSize <= m_nMaxSize)
  357.     {
  358.         // it fits
  359.         if (nNewSize > m_nSize)
  360.         {
  361.             // initialize the new elements
  362.             ConstructElements(&m_pData[m_nSize], nNewSize-m_nSize);
  363.         }
  364.         else if (m_nSize > nNewSize)
  365.         {
  366.             // destroy the old elements
  367.             DestructElements(&m_pData[nNewSize], m_nSize-nNewSize);
  368.         }
  369.         m_nSize = nNewSize;
  370.     }
  371.     else
  372.     {
  373.         // otherwise, grow array
  374.         int nGrowBy = m_nGrowBy;
  375.         if (nGrowBy == 0)
  376.         {
  377.             // heuristically determine growth when nGrowBy == 0
  378.             //  (this avoids heap fragmentation in many situations)
  379.             nGrowBy = m_nSize / 8;
  380.             nGrowBy = (nGrowBy < 4) ? 4 : ((nGrowBy > 1024) ? 1024 : nGrowBy);
  381.         }
  382.         int nNewMax;
  383.         if (nNewSize < m_nMaxSize + nGrowBy)
  384.             nNewMax = m_nMaxSize + nGrowBy;  // granularity
  385.         else
  386.             nNewMax = nNewSize;  // no slush
  387.  
  388.         ASSERT(nNewMax >= m_nMaxSize);  // no wrap around
  389. #ifdef SIZE_T_MAX
  390.         ASSERT(nNewMax <= SIZE_T_MAX/sizeof(TYPE)); // no overflow
  391. #endif
  392.         TYPE* pNewData = (TYPE*) new BYTE[nNewMax * sizeof(TYPE)];
  393.  
  394.         // copy new data from old
  395.         memcpy(pNewData, m_pData, m_nSize * sizeof(TYPE));
  396.  
  397.         // construct remaining elements
  398.         ASSERT(nNewSize > m_nSize);
  399.         ConstructElements(&pNewData[m_nSize], nNewSize-m_nSize);
  400.  
  401.         // get rid of old stuff (note: no destructors called)
  402.         delete[] (BYTE*)m_pData;
  403.         m_pData = pNewData;
  404.         m_nSize = nNewSize;
  405.         m_nMaxSize = nNewMax;
  406.     }
  407. }
  408.  
  409. template<class TYPE, class ARG_TYPE>
  410. int CArray<TYPE, ARG_TYPE>::Append(const CArray& src)
  411. {
  412.     ASSERT_VALID(this);
  413.     ASSERT(this != &src);   // cannot append to itself
  414.  
  415.     int nOldSize = m_nSize;
  416.     SetSize(m_nSize + src.m_nSize);
  417.     CopyElements(m_pData + nOldSize, src.m_pData, src.m_nSize);
  418.     return nOldSize;
  419. }
  420.  
  421. template<class TYPE, class ARG_TYPE>
  422. void CArray<TYPE, ARG_TYPE>::Copy(const CArray& src)
  423. {
  424.     ASSERT_VALID(this);
  425.     ASSERT(this != &src);   // cannot append to itself
  426.  
  427.     SetSize(src.m_nSize);
  428.     CopyElements(m_pData, src.m_pData, src.m_nSize);
  429. }
  430.  
  431. template<class TYPE, class ARG_TYPE>
  432. void CArray<TYPE, ARG_TYPE>::FreeExtra()
  433. {
  434.     ASSERT_VALID(this);
  435.  
  436.     if (m_nSize != m_nMaxSize)
  437.     {
  438.         // shrink to desired size
  439. #ifdef SIZE_T_MAX
  440.         ASSERT(m_nSize <= SIZE_T_MAX/sizeof(TYPE)); // no overflow
  441. #endif
  442.         TYPE* pNewData = NULL;
  443.         if (m_nSize != 0)
  444.         {
  445.             pNewData = (TYPE*) new BYTE[m_nSize * sizeof(TYPE)];
  446.             // copy new data from old
  447.             memcpy(pNewData, m_pData, m_nSize * sizeof(TYPE));
  448.         }
  449.  
  450.         // get rid of old stuff (note: no destructors called)
  451.         delete[] (BYTE*)m_pData;
  452.         m_pData = pNewData;
  453.         m_nMaxSize = m_nSize;
  454.     }
  455. }
  456.  
  457. template<class TYPE, class ARG_TYPE>
  458. void CArray<TYPE, ARG_TYPE>::SetAtGrow(int nIndex, ARG_TYPE newElement)
  459. {
  460.     ASSERT_VALID(this);
  461.     ASSERT(nIndex >= 0);
  462.  
  463.     if (nIndex >= m_nSize)
  464.         SetSize(nIndex+1, -1);
  465.     m_pData[nIndex] = newElement;
  466. }
  467.  
  468. template<class TYPE, class ARG_TYPE>
  469. void CArray<TYPE, ARG_TYPE>::InsertAt(int nIndex, ARG_TYPE newElement, int nCount /*=1*/)
  470. {
  471.     ASSERT_VALID(this);
  472.     ASSERT(nIndex >= 0);    // will expand to meet need
  473.     ASSERT(nCount > 0);     // zero or negative size not allowed
  474.  
  475.     if (nIndex >= m_nSize)
  476.     {
  477.         // adding after the end of the array
  478.         SetSize(nIndex + nCount, -1);   // grow so nIndex is valid
  479.     }
  480.     else
  481.     {
  482.         // inserting in the middle of the array
  483.         int nOldSize = m_nSize;
  484.         SetSize(m_nSize + nCount, -1);  // grow it to new size
  485.         // shift old data up to fill gap
  486.         memmove(&m_pData[nIndex+nCount], &m_pData[nIndex],
  487.             (nOldSize-nIndex) * sizeof(TYPE));
  488.  
  489.         // re-init slots we copied from
  490.         ConstructElements(&m_pData[nIndex], nCount);
  491.     }
  492.  
  493.     // insert new value in the gap
  494.     ASSERT(nIndex + nCount <= m_nSize);
  495.     while (nCount--)
  496.         m_pData[nIndex++] = newElement;
  497. }
  498.  
  499. template<class TYPE, class ARG_TYPE>
  500. void CArray<TYPE, ARG_TYPE>::RemoveAt(int nIndex, int nCount)
  501. {
  502.     ASSERT_VALID(this);
  503.     ASSERT(nIndex >= 0);
  504.     ASSERT(nCount >= 0);
  505.     ASSERT(nIndex + nCount <= m_nSize);
  506.  
  507.     // just remove a range
  508.     int nMoveCount = m_nSize - (nIndex + nCount);
  509.     DestructElements(&m_pData[nIndex], nCount);
  510.     if (nMoveCount)
  511.         memcpy(&m_pData[nIndex], &m_pData[nIndex + nCount],
  512.             nMoveCount * sizeof(TYPE));
  513.     m_nSize -= nCount;
  514. }
  515.  
  516. template<class TYPE, class ARG_TYPE>
  517. void CArray<TYPE, ARG_TYPE>::InsertAt(int nStartIndex, CArray* pNewArray)
  518. {
  519.     ASSERT_VALID(this);
  520.     ASSERT(pNewArray != NULL);
  521.     ASSERT_VALID(pNewArray);
  522.     ASSERT(nStartIndex >= 0);
  523.  
  524.     if (pNewArray->GetSize() > 0)
  525.     {
  526.         InsertAt(nStartIndex, pNewArray->GetAt(0), pNewArray->GetSize());
  527.         for (int i = 0; i < pNewArray->GetSize(); i++)
  528.             SetAt(nStartIndex + i, pNewArray->GetAt(i));
  529.     }
  530. }
  531.  
  532. template<class TYPE, class ARG_TYPE>
  533. void CArray<TYPE, ARG_TYPE>::Serialize(CArchive& ar)
  534. {
  535.     ASSERT_VALID(this);
  536.  
  537.     CObject::Serialize(ar);
  538.     if (ar.IsStoring())
  539.     {
  540.         ar.WriteCount(m_nSize);
  541.     }
  542.     else
  543.     {
  544.         DWORD nOldSize = ar.ReadCount();
  545.         SetSize(nOldSize, -1);
  546.     }
  547.     SerializeElements(ar, m_pData, m_nSize);
  548. }
  549.  
  550. #ifdef _DEBUG
  551. template<class TYPE, class ARG_TYPE>
  552. void CArray<TYPE, ARG_TYPE>::Dump(CDumpContext& dc) const
  553. {
  554.     CObject::Dump(dc);
  555.  
  556.     dc << "with " << m_nSize << " elements";
  557.     if (dc.GetDepth() > 0)
  558.     {
  559.         dc << "\n";
  560.         DumpElements(dc, m_pData, m_nSize);
  561.     }
  562.  
  563.     dc << "\n";
  564. }
  565.  
  566. template<class TYPE, class ARG_TYPE>
  567. void CArray<TYPE, ARG_TYPE>::AssertValid() const
  568. {
  569.     CObject::AssertValid();
  570.  
  571.     if (m_pData == NULL)
  572.     {
  573.         ASSERT(m_nSize == 0);
  574.         ASSERT(m_nMaxSize == 0);
  575.     }
  576.     else
  577.     {
  578.         ASSERT(m_nSize >= 0);
  579.         ASSERT(m_nMaxSize >= 0);
  580.         ASSERT(m_nSize <= m_nMaxSize);
  581.         ASSERT(AfxIsValidAddress(m_pData, m_nMaxSize * sizeof(TYPE)));
  582.     }
  583. }
  584. #endif //_DEBUG
  585.  
  586. /////////////////////////////////////////////////////////////////////////////
  587. // CList<TYPE, ARG_TYPE>
  588.  
  589. template<class TYPE, class ARG_TYPE>
  590. class CList : public CObject
  591. {
  592. protected:
  593.     struct CNode
  594.     {
  595.         CNode* pNext;
  596.         CNode* pPrev;
  597.         TYPE data;
  598.     };
  599. public:
  600. // Construction
  601.     CList(int nBlockSize = 10);
  602.  
  603. // Attributes (head and tail)
  604.     // count of elements
  605.     int GetCount() const;
  606.     BOOL IsEmpty() const;
  607.  
  608.     // peek at head or tail
  609.     TYPE& GetHead();
  610.     TYPE GetHead() const;
  611.     TYPE& GetTail();
  612.     TYPE GetTail() const;
  613.  
  614. // Operations
  615.     // get head or tail (and remove it) - don't call on empty list !
  616.     TYPE RemoveHead();
  617.     TYPE RemoveTail();
  618.  
  619.     // add before head or after tail
  620.     POSITION AddHead(ARG_TYPE newElement);
  621.     POSITION AddTail(ARG_TYPE newElement);
  622.  
  623.     // add another list of elements before head or after tail
  624.     void AddHead(CList* pNewList);
  625.     void AddTail(CList* pNewList);
  626.  
  627.     // remove all elements
  628.     void RemoveAll();
  629.  
  630.     // iteration
  631.     POSITION GetHeadPosition() const;
  632.     POSITION GetTailPosition() const;
  633.     TYPE& GetNext(POSITION& rPosition); // return *Position++
  634.     TYPE GetNext(POSITION& rPosition) const; // return *Position++
  635.     TYPE& GetPrev(POSITION& rPosition); // return *Position--
  636.     TYPE GetPrev(POSITION& rPosition) const; // return *Position--
  637.  
  638.     // getting/modifying an element at a given position
  639.     TYPE& GetAt(POSITION position);
  640.     TYPE GetAt(POSITION position) const;
  641.     void SetAt(POSITION pos, ARG_TYPE newElement);
  642.     void RemoveAt(POSITION position);
  643.  
  644.     // inserting before or after a given position
  645.     POSITION InsertBefore(POSITION position, ARG_TYPE newElement);
  646.     POSITION InsertAfter(POSITION position, ARG_TYPE newElement);
  647.  
  648.     // helper functions (note: O(n) speed)
  649.     POSITION Find(ARG_TYPE searchValue, POSITION startAfter = NULL) const;
  650.         // defaults to starting at the HEAD, return NULL if not found
  651.     POSITION FindIndex(int nIndex) const;
  652.         // get the 'nIndex'th element (may return NULL)
  653.  
  654. // Implementation
  655. protected:
  656.     CNode* m_pNodeHead;
  657.     CNode* m_pNodeTail;
  658.     int m_nCount;
  659.     CNode* m_pNodeFree;
  660.     struct CPlex* m_pBlocks;
  661.     int m_nBlockSize;
  662.  
  663.     CNode* NewNode(CNode*, CNode*);
  664.     void FreeNode(CNode*);
  665.  
  666. public:
  667.     ~CList();
  668.     void Serialize(CArchive&);
  669. #ifdef _DEBUG
  670.     void Dump(CDumpContext&) const;
  671.     void AssertValid() const;
  672. #endif
  673. };
  674.  
  675. /////////////////////////////////////////////////////////////////////////////
  676. // CList<TYPE, ARG_TYPE> inline functions
  677.  
  678. template<class TYPE, class ARG_TYPE>
  679. inline int CList<TYPE, ARG_TYPE>::GetCount() const
  680.     { return m_nCount; }
  681. template<class TYPE, class ARG_TYPE>
  682. inline BOOL CList<TYPE, ARG_TYPE>::IsEmpty() const
  683.     { return m_nCount == 0; }
  684. template<class TYPE, class ARG_TYPE>
  685. inline TYPE& CList<TYPE, ARG_TYPE>::GetHead()
  686.     { ASSERT(m_pNodeHead != NULL);
  687.         return m_pNodeHead->data; }
  688. template<class TYPE, class ARG_TYPE>
  689. inline TYPE CList<TYPE, ARG_TYPE>::GetHead() const
  690.     { ASSERT(m_pNodeHead != NULL);
  691.         return m_pNodeHead->data; }
  692. template<class TYPE, class ARG_TYPE>
  693. inline TYPE& CList<TYPE, ARG_TYPE>::GetTail()
  694.     { ASSERT(m_pNodeTail != NULL);
  695.         return m_pNodeTail->data; }
  696. template<class TYPE, class ARG_TYPE>
  697. inline TYPE CList<TYPE, ARG_TYPE>::GetTail() const
  698.     { ASSERT(m_pNodeTail != NULL);
  699.         return m_pNodeTail->data; }
  700. template<class TYPE, class ARG_TYPE>
  701. inline POSITION CList<TYPE, ARG_TYPE>::GetHeadPosition() const
  702.     { return (POSITION) m_pNodeHead; }
  703. template<class TYPE, class ARG_TYPE>
  704. inline POSITION CList<TYPE, ARG_TYPE>::GetTailPosition() const
  705.     { return (POSITION) m_pNodeTail; }
  706. template<class TYPE, class ARG_TYPE>
  707. inline TYPE& CList<TYPE, ARG_TYPE>::GetNext(POSITION& rPosition) // return *Position++
  708.     { CNode* pNode = (CNode*) rPosition;
  709.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  710.         rPosition = (POSITION) pNode->pNext;
  711.         return pNode->data; }
  712. template<class TYPE, class ARG_TYPE>
  713. inline TYPE CList<TYPE, ARG_TYPE>::GetNext(POSITION& rPosition) const // return *Position++
  714.     { CNode* pNode = (CNode*) rPosition;
  715.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  716.         rPosition = (POSITION) pNode->pNext;
  717.         return pNode->data; }
  718. template<class TYPE, class ARG_TYPE>
  719. inline TYPE& CList<TYPE, ARG_TYPE>::GetPrev(POSITION& rPosition) // return *Position--
  720.     { CNode* pNode = (CNode*) rPosition;
  721.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  722.         rPosition = (POSITION) pNode->pPrev;
  723.         return pNode->data; }
  724. template<class TYPE, class ARG_TYPE>
  725. inline TYPE CList<TYPE, ARG_TYPE>::GetPrev(POSITION& rPosition) const // return *Position--
  726.     { CNode* pNode = (CNode*) rPosition;
  727.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  728.         rPosition = (POSITION) pNode->pPrev;
  729.         return pNode->data; }
  730. template<class TYPE, class ARG_TYPE>
  731. inline TYPE& CList<TYPE, ARG_TYPE>::GetAt(POSITION position)
  732.     { CNode* pNode = (CNode*) position;
  733.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  734.         return pNode->data; }
  735. template<class TYPE, class ARG_TYPE>
  736. inline TYPE CList<TYPE, ARG_TYPE>::GetAt(POSITION position) const
  737.     { CNode* pNode = (CNode*) position;
  738.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  739.         return pNode->data; }
  740. template<class TYPE, class ARG_TYPE>
  741. inline void CList<TYPE, ARG_TYPE>::SetAt(POSITION pos, ARG_TYPE newElement)
  742.     { CNode* pNode = (CNode*) pos;
  743.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  744.         pNode->data = newElement; }
  745.  
  746. template<class TYPE, class ARG_TYPE>
  747. CList<TYPE, ARG_TYPE>::CList(int nBlockSize)
  748. {
  749.     ASSERT(nBlockSize > 0);
  750.  
  751.     m_nCount = 0;
  752.     m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
  753.     m_pBlocks = NULL;
  754.     m_nBlockSize = nBlockSize;
  755. }
  756.  
  757. template<class TYPE, class ARG_TYPE>
  758. void CList<TYPE, ARG_TYPE>::RemoveAll()
  759. {
  760.     ASSERT_VALID(this);
  761.  
  762.     // destroy elements
  763.     CNode* pNode;
  764.     for (pNode = m_pNodeHead; pNode != NULL; pNode = pNode->pNext)
  765.         DestructElements(&pNode->data, 1);
  766.  
  767.     m_nCount = 0;
  768.     m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
  769.     m_pBlocks->FreeDataChain();
  770.     m_pBlocks = NULL;
  771. }
  772.  
  773. template<class TYPE, class ARG_TYPE>
  774. CList<TYPE, ARG_TYPE>::~CList()
  775. {
  776.     RemoveAll();
  777.     ASSERT(m_nCount == 0);
  778. }
  779.  
  780. /////////////////////////////////////////////////////////////////////////////
  781. // Node helpers
  782. //
  783. // Implementation note: CNode's are stored in CPlex blocks and
  784. //  chained together. Free blocks are maintained in a singly linked list
  785. //  using the 'pNext' member of CNode with 'm_pNodeFree' as the head.
  786. //  Used blocks are maintained in a doubly linked list using both 'pNext'
  787. //  and 'pPrev' as links and 'm_pNodeHead' and 'm_pNodeTail'
  788. //   as the head/tail.
  789. //
  790. // We never free a CPlex block unless the List is destroyed or RemoveAll()
  791. //  is used - so the total number of CPlex blocks may grow large depending
  792. //  on the maximum past size of the list.
  793. //
  794.  
  795. template<class TYPE, class ARG_TYPE>
  796. CList<TYPE, ARG_TYPE>::CNode*
  797. CList<TYPE, ARG_TYPE>::NewNode(CList::CNode* pPrev, CList::CNode* pNext)
  798. {
  799.     if (m_pNodeFree == NULL)
  800.     {
  801.         // add another block
  802.         CPlex* pNewBlock = CPlex::Create(m_pBlocks, m_nBlockSize,
  803.                  sizeof(CNode));
  804.  
  805.         // chain them into free list
  806.         CNode* pNode = (CNode*) pNewBlock->data();
  807.         // free in reverse order to make it easier to debug
  808.         pNode += m_nBlockSize - 1;
  809.         for (int i = m_nBlockSize-1; i >= 0; i--, pNode--)
  810.         {
  811.             pNode->pNext = m_pNodeFree;
  812.             m_pNodeFree = pNode;
  813.         }
  814.     }
  815.     ASSERT(m_pNodeFree != NULL);  // we must have something
  816.  
  817.     CList::CNode* pNode = m_pNodeFree;
  818.     m_pNodeFree = m_pNodeFree->pNext;
  819.     pNode->pPrev = pPrev;
  820.     pNode->pNext = pNext;
  821.     m_nCount++;
  822.     ASSERT(m_nCount > 0);  // make sure we don't overflow
  823.  
  824.     ConstructElements(&pNode->data, 1);
  825.     return pNode;
  826. }
  827.  
  828. template<class TYPE, class ARG_TYPE>
  829. void CList<TYPE, ARG_TYPE>::FreeNode(CList::CNode* pNode)
  830. {
  831.     DestructElements(&pNode->data, 1);
  832.     pNode->pNext = m_pNodeFree;
  833.     m_pNodeFree = pNode;
  834.     m_nCount--;
  835.     ASSERT(m_nCount >= 0);  // make sure we don't underflow
  836.  
  837.     // if no more elements, cleanup completely
  838.     if (m_nCount == 0)
  839.         RemoveAll();
  840. }
  841.  
  842. template<class TYPE, class ARG_TYPE>
  843. POSITION CList<TYPE, ARG_TYPE>::AddHead(ARG_TYPE newElement)
  844. {
  845.     ASSERT_VALID(this);
  846.  
  847.     CNode* pNewNode = NewNode(NULL, m_pNodeHead);
  848.     pNewNode->data = newElement;
  849.     if (m_pNodeHead != NULL)
  850.         m_pNodeHead->pPrev = pNewNode;
  851.     else
  852.         m_pNodeTail = pNewNode;
  853.     m_pNodeHead = pNewNode;
  854.     return (POSITION) pNewNode;
  855. }
  856.  
  857. template<class TYPE, class ARG_TYPE>
  858. POSITION CList<TYPE, ARG_TYPE>::AddTail(ARG_TYPE newElement)
  859. {
  860.     ASSERT_VALID(this);
  861.  
  862.     CNode* pNewNode = NewNode(m_pNodeTail, NULL);
  863.     pNewNode->data = newElement;
  864.     if (m_pNodeTail != NULL)
  865.         m_pNodeTail->pNext = pNewNode;
  866.     else
  867.         m_pNodeHead = pNewNode;
  868.     m_pNodeTail = pNewNode;
  869.     return (POSITION) pNewNode;
  870. }
  871.  
  872. template<class TYPE, class ARG_TYPE>
  873. void CList<TYPE, ARG_TYPE>::AddHead(CList* pNewList)
  874. {
  875.     ASSERT_VALID(this);
  876.  
  877.     ASSERT(pNewList != NULL);
  878.     ASSERT_VALID(pNewList);
  879.  
  880.     // add a list of same elements to head (maintain order)
  881.     POSITION pos = pNewList->GetTailPosition();
  882.     while (pos != NULL)
  883.         AddHead(pNewList->GetPrev(pos));
  884. }
  885.  
  886. template<class TYPE, class ARG_TYPE>
  887. void CList<TYPE, ARG_TYPE>::AddTail(CList* pNewList)
  888. {
  889.     ASSERT_VALID(this);
  890.     ASSERT(pNewList != NULL);
  891.     ASSERT_VALID(pNewList);
  892.  
  893.     // add a list of same elements
  894.     POSITION pos = pNewList->GetHeadPosition();
  895.     while (pos != NULL)
  896.         AddTail(pNewList->GetNext(pos));
  897. }
  898.  
  899. template<class TYPE, class ARG_TYPE>
  900. TYPE CList<TYPE, ARG_TYPE>::RemoveHead()
  901. {
  902.     ASSERT_VALID(this);
  903.     ASSERT(m_pNodeHead != NULL);  // don't call on empty list !!!
  904.     ASSERT(AfxIsValidAddress(m_pNodeHead, sizeof(CNode)));
  905.  
  906.     CNode* pOldNode = m_pNodeHead;
  907.     TYPE returnValue = pOldNode->data;
  908.  
  909.     m_pNodeHead = pOldNode->pNext;
  910.     if (m_pNodeHead != NULL)
  911.         m_pNodeHead->pPrev = NULL;
  912.     else
  913.         m_pNodeTail = NULL;
  914.     FreeNode(pOldNode);
  915.     return returnValue;
  916. }
  917.  
  918. template<class TYPE, class ARG_TYPE>
  919. TYPE CList<TYPE, ARG_TYPE>::RemoveTail()
  920. {
  921.     ASSERT_VALID(this);
  922.     ASSERT(m_pNodeTail != NULL);  // don't call on empty list !!!
  923.     ASSERT(AfxIsValidAddress(m_pNodeTail, sizeof(CNode)));
  924.  
  925.     CNode* pOldNode = m_pNodeTail;
  926.     TYPE returnValue = pOldNode->data;
  927.  
  928.     m_pNodeTail = pOldNode->pPrev;
  929.     if (m_pNodeTail != NULL)
  930.         m_pNodeTail->pNext = NULL;
  931.     else
  932.         m_pNodeHead = NULL;
  933.     FreeNode(pOldNode);
  934.     return returnValue;
  935. }
  936.  
  937. template<class TYPE, class ARG_TYPE>
  938. POSITION CList<TYPE, ARG_TYPE>::InsertBefore(POSITION position, ARG_TYPE newElement)
  939. {
  940.     ASSERT_VALID(this);
  941.  
  942.     if (position == NULL)
  943.         return AddHead(newElement); // insert before nothing -> head of the list
  944.  
  945.     // Insert it before position
  946.     CNode* pOldNode = (CNode*) position;
  947.     CNode* pNewNode = NewNode(pOldNode->pPrev, pOldNode);
  948.     pNewNode->data = newElement;
  949.  
  950.     if (pOldNode->pPrev != NULL)
  951.     {
  952.         ASSERT(AfxIsValidAddress(pOldNode->pPrev, sizeof(CNode)));
  953.         pOldNode->pPrev->pNext = pNewNode;
  954.     }
  955.     else
  956.     {
  957.         ASSERT(pOldNode == m_pNodeHead);
  958.         m_pNodeHead = pNewNode;
  959.     }
  960.     pOldNode->pPrev = pNewNode;
  961.     return (POSITION) pNewNode;
  962. }
  963.  
  964. template<class TYPE, class ARG_TYPE>
  965. POSITION CList<TYPE, ARG_TYPE>::InsertAfter(POSITION position, ARG_TYPE newElement)
  966. {
  967.     ASSERT_VALID(this);
  968.  
  969.     if (position == NULL)
  970.         return AddTail(newElement); // insert after nothing -> tail of the list
  971.  
  972.     // Insert it before position
  973.     CNode* pOldNode = (CNode*) position;
  974.     ASSERT(AfxIsValidAddress(pOldNode, sizeof(CNode)));
  975.     CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext);
  976.     pNewNode->data = newElement;
  977.  
  978.     if (pOldNode->pNext != NULL)
  979.     {
  980.         ASSERT(AfxIsValidAddress(pOldNode->pNext, sizeof(CNode)));
  981.         pOldNode->pNext->pPrev = pNewNode;
  982.     }
  983.     else
  984.     {
  985.         ASSERT(pOldNode == m_pNodeTail);
  986.         m_pNodeTail = pNewNode;
  987.     }
  988.     pOldNode->pNext = pNewNode;
  989.     return (POSITION) pNewNode;
  990. }
  991.  
  992. template<class TYPE, class ARG_TYPE>
  993. void CList<TYPE, ARG_TYPE>::RemoveAt(POSITION position)
  994. {
  995.     ASSERT_VALID(this);
  996.  
  997.     CNode* pOldNode = (CNode*) position;
  998.     ASSERT(AfxIsValidAddress(pOldNode, sizeof(CNode)));
  999.  
  1000.     // remove pOldNode from list
  1001.     if (pOldNode == m_pNodeHead)
  1002.     {
  1003.         m_pNodeHead = pOldNode->pNext;
  1004.     }
  1005.     else
  1006.     {
  1007.         ASSERT(AfxIsValidAddress(pOldNode->pPrev, sizeof(CNode)));
  1008.         pOldNode->pPrev->pNext = pOldNode->pNext;
  1009.     }
  1010.     if (pOldNode == m_pNodeTail)
  1011.     {
  1012.         m_pNodeTail = pOldNode->pPrev;
  1013.     }
  1014.     else
  1015.     {
  1016.         ASSERT(AfxIsValidAddress(pOldNode->pNext, sizeof(CNode)));
  1017.         pOldNode->pNext->pPrev = pOldNode->pPrev;
  1018.     }
  1019.     FreeNode(pOldNode);
  1020. }
  1021.  
  1022. template<class TYPE, class ARG_TYPE>
  1023. POSITION CList<TYPE, ARG_TYPE>::FindIndex(int nIndex) const
  1024. {
  1025.     ASSERT_VALID(this);
  1026.     ASSERT(nIndex >= 0);
  1027.  
  1028.     if (nIndex >= m_nCount)
  1029.         return NULL;  // went too far
  1030.  
  1031.     CNode* pNode = m_pNodeHead;
  1032.     while (nIndex--)
  1033.     {
  1034.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  1035.         pNode = pNode->pNext;
  1036.     }
  1037.     return (POSITION) pNode;
  1038. }
  1039.  
  1040. template<class TYPE, class ARG_TYPE>
  1041. POSITION CList<TYPE, ARG_TYPE>::Find(ARG_TYPE searchValue, POSITION startAfter) const
  1042. {
  1043.     ASSERT_VALID(this);
  1044.  
  1045.     CNode* pNode = (CNode*) startAfter;
  1046.     if (pNode == NULL)
  1047.     {
  1048.         pNode = m_pNodeHead;  // start at head
  1049.     }
  1050.     else
  1051.     {
  1052.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  1053.         pNode = pNode->pNext;  // start after the one specified
  1054.     }
  1055.  
  1056.     for (; pNode != NULL; pNode = pNode->pNext)
  1057.         if (CompareElements(&pNode->data, &searchValue))
  1058.             return (POSITION)pNode;
  1059.     return NULL;
  1060. }
  1061.  
  1062. template<class TYPE, class ARG_TYPE>
  1063. void CList<TYPE, ARG_TYPE>::Serialize(CArchive& ar)
  1064. {
  1065.     ASSERT_VALID(this);
  1066.  
  1067.     CObject::Serialize(ar);
  1068.  
  1069.     if (ar.IsStoring())
  1070.     {
  1071.         ar.WriteCount(m_nCount);
  1072.         for (CNode* pNode = m_pNodeHead; pNode != NULL; pNode = pNode->pNext)
  1073.         {
  1074.             ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  1075.             SerializeElements(ar, &pNode->data, 1);
  1076.         }
  1077.     }
  1078.     else
  1079.     {
  1080.         DWORD nNewCount = ar.ReadCount();
  1081.         TYPE newData;
  1082.         while (nNewCount--)
  1083.         {
  1084.             SerializeElements(ar, &newData, 1);
  1085.             AddTail(newData);
  1086.         }
  1087.     }
  1088. }
  1089.  
  1090. #ifdef _DEBUG
  1091. template<class TYPE, class ARG_TYPE>
  1092. void CList<TYPE, ARG_TYPE>::Dump(CDumpContext& dc) const
  1093. {
  1094.     CObject::Dump(dc);
  1095.  
  1096.     dc << "with " << m_nCount << " elements";
  1097.     if (dc.GetDepth() > 0)
  1098.     {
  1099.         POSITION pos = GetHeadPosition();
  1100.         while (pos != NULL)
  1101.         {
  1102.             dc << "\n";
  1103.             DumpElements(dc, &((CList*)this)->GetNext(pos), 1);
  1104.         }
  1105.     }
  1106.  
  1107.     dc << "\n";
  1108. }
  1109.  
  1110. template<class TYPE, class ARG_TYPE>
  1111. void CList<TYPE, ARG_TYPE>::AssertValid() const
  1112. {
  1113.     CObject::AssertValid();
  1114.  
  1115.     if (m_nCount == 0)
  1116.     {
  1117.         // empty list
  1118.         ASSERT(m_pNodeHead == NULL);
  1119.         ASSERT(m_pNodeTail == NULL);
  1120.     }
  1121.     else
  1122.     {
  1123.         // non-empty list
  1124.         ASSERT(AfxIsValidAddress(m_pNodeHead, sizeof(CNode)));
  1125.         ASSERT(AfxIsValidAddress(m_pNodeTail, sizeof(CNode)));
  1126.     }
  1127. }
  1128. #endif //_DEBUG
  1129.  
  1130. /////////////////////////////////////////////////////////////////////////////
  1131. // CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>
  1132.  
  1133. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1134. class CMap : public CObject
  1135. {
  1136. protected:
  1137.     // Association
  1138.     struct CAssoc
  1139.     {
  1140.         CAssoc* pNext;
  1141.         UINT nHashValue;  // needed for efficient iteration
  1142.         KEY key;
  1143.         VALUE value;
  1144.     };
  1145. public:
  1146. // Construction
  1147.     CMap(int nBlockSize = 10);
  1148.  
  1149. // Attributes
  1150.     // number of elements
  1151.     int GetCount() const;
  1152.     BOOL IsEmpty() const;
  1153.  
  1154.     // Lookup
  1155.     BOOL Lookup(ARG_KEY key, VALUE& rValue) const;
  1156.  
  1157. // Operations
  1158.     // Lookup and add if not there
  1159.     VALUE& operator[](ARG_KEY key);
  1160.  
  1161.     // add a new (key, value) pair
  1162.     void SetAt(ARG_KEY key, ARG_VALUE newValue);
  1163.  
  1164.     // removing existing (key, ?) pair
  1165.     BOOL RemoveKey(ARG_KEY key);
  1166.     void RemoveAll();
  1167.  
  1168.     // iterating all (key, value) pairs
  1169.     POSITION GetStartPosition() const;
  1170.     void GetNextAssoc(POSITION& rNextPosition, KEY& rKey, VALUE& rValue) const;
  1171.  
  1172.     // advanced features for derived classes
  1173.     UINT GetHashTableSize() const;
  1174.     void InitHashTable(UINT hashSize, BOOL bAllocNow = TRUE);
  1175.  
  1176. // Implementation
  1177. protected:
  1178.     CAssoc** m_pHashTable;
  1179.     UINT m_nHashTableSize;
  1180.     int m_nCount;
  1181.     CAssoc* m_pFreeList;
  1182.     struct CPlex* m_pBlocks;
  1183.     int m_nBlockSize;
  1184.  
  1185.     CAssoc* NewAssoc();
  1186.     void FreeAssoc(CAssoc*);
  1187.     CAssoc* GetAssocAt(ARG_KEY, UINT&) const;
  1188.  
  1189. public:
  1190.     ~CMap();
  1191.     void Serialize(CArchive&);
  1192. #ifdef _DEBUG
  1193.     void Dump(CDumpContext&) const;
  1194.     void AssertValid() const;
  1195. #endif
  1196. };
  1197.  
  1198. /////////////////////////////////////////////////////////////////////////////
  1199. // CMap<KEY, ARG_KEY, VALUE, ARG_VALUE> inline functions
  1200.  
  1201. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1202. inline int CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetCount() const
  1203.     { return m_nCount; }
  1204. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1205. inline BOOL CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::IsEmpty() const
  1206.     { return m_nCount == 0; }
  1207. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1208. inline void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::SetAt(ARG_KEY key, ARG_VALUE newValue)
  1209.     { (*this)[key] = newValue; }
  1210. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1211. inline POSITION CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetStartPosition() const
  1212.     { return (m_nCount == 0) ? NULL : BEFORE_START_POSITION; }
  1213. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1214. inline UINT CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetHashTableSize() const
  1215.     { return m_nHashTableSize; }
  1216.  
  1217. /////////////////////////////////////////////////////////////////////////////
  1218. // CMap<KEY, ARG_KEY, VALUE, ARG_VALUE> out-of-line functions
  1219.  
  1220. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1221. CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CMap(int nBlockSize)
  1222. {
  1223.     ASSERT(nBlockSize > 0);
  1224.  
  1225.     m_pHashTable = NULL;
  1226.     m_nHashTableSize = 17;  // default size
  1227.     m_nCount = 0;
  1228.     m_pFreeList = NULL;
  1229.     m_pBlocks = NULL;
  1230.     m_nBlockSize = nBlockSize;
  1231. }
  1232.  
  1233. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1234. void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::InitHashTable(
  1235.     UINT nHashSize, BOOL bAllocNow)
  1236. //
  1237. // Used to force allocation of a hash table or to override the default
  1238. //   hash table size of (which is fairly small)
  1239. {
  1240.     ASSERT_VALID(this);
  1241.     ASSERT(m_nCount == 0);
  1242.     ASSERT(nHashSize > 0);
  1243.  
  1244.     if (m_pHashTable != NULL)
  1245.     {
  1246.         // free hash table
  1247.         delete[] m_pHashTable;
  1248.         m_pHashTable = NULL;
  1249.     }
  1250.  
  1251.     if (bAllocNow)
  1252.     {
  1253.         m_pHashTable = new CAssoc* [nHashSize];
  1254.         memset(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize);
  1255.     }
  1256.     m_nHashTableSize = nHashSize;
  1257. }
  1258.  
  1259. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1260. void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::RemoveAll()
  1261. {
  1262.     ASSERT_VALID(this);
  1263.  
  1264.     if (m_pHashTable != NULL)
  1265.     {
  1266.         // destroy elements (values and keys)
  1267.         for (UINT nHash = 0; nHash < m_nHashTableSize; nHash++)
  1268.         {
  1269.             CAssoc* pAssoc;
  1270.             for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;
  1271.               pAssoc = pAssoc->pNext)
  1272.             {
  1273.                 DestructElements(&pAssoc->value, 1);
  1274.                 DestructElements(&pAssoc->key, 1);
  1275.             }
  1276.         }
  1277.     }
  1278.  
  1279.     // free hash table
  1280.     delete[] m_pHashTable;
  1281.     m_pHashTable = NULL;
  1282.  
  1283.     m_nCount = 0;
  1284.     m_pFreeList = NULL;
  1285.     m_pBlocks->FreeDataChain();
  1286.     m_pBlocks = NULL;
  1287. }
  1288.  
  1289. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1290. CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::~CMap()
  1291. {
  1292.     RemoveAll();
  1293.     ASSERT(m_nCount == 0);
  1294. }
  1295.  
  1296. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1297. CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CAssoc*
  1298. CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::NewAssoc()
  1299. {
  1300.     if (m_pFreeList == NULL)
  1301.     {
  1302.         // add another block
  1303.         CPlex* newBlock = CPlex::Create(m_pBlocks, m_nBlockSize, sizeof(CMap::CAssoc));
  1304.         // chain them into free list
  1305.         CMap::CAssoc* pAssoc = (CMap::CAssoc*) newBlock->data();
  1306.         // free in reverse order to make it easier to debug
  1307.         pAssoc += m_nBlockSize - 1;
  1308.         for (int i = m_nBlockSize-1; i >= 0; i--, pAssoc--)
  1309.         {
  1310.             pAssoc->pNext = m_pFreeList;
  1311.             m_pFreeList = pAssoc;
  1312.         }
  1313.     }
  1314.     ASSERT(m_pFreeList != NULL);  // we must have something
  1315.  
  1316.     CMap::CAssoc* pAssoc = m_pFreeList;
  1317.     m_pFreeList = m_pFreeList->pNext;
  1318.     m_nCount++;
  1319.     ASSERT(m_nCount > 0);  // make sure we don't overflow
  1320.     ConstructElements(&pAssoc->key, 1);
  1321.     ConstructElements(&pAssoc->value, 1);   // special construct values
  1322.     return pAssoc;
  1323. }
  1324.  
  1325. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1326. void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::FreeAssoc(CMap::CAssoc* pAssoc)
  1327. {
  1328.     DestructElements(&pAssoc->value, 1);
  1329.     DestructElements(&pAssoc->key, 1);
  1330.     pAssoc->pNext = m_pFreeList;
  1331.     m_pFreeList = pAssoc;
  1332.     m_nCount--;
  1333.     ASSERT(m_nCount >= 0);  // make sure we don't underflow
  1334.  
  1335.     // if no more elements, cleanup completely
  1336.     if (m_nCount == 0)
  1337.         RemoveAll();
  1338. }
  1339.  
  1340. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1341. CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CAssoc*
  1342. CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetAssocAt(ARG_KEY key, UINT& nHash) const
  1343. // find association (or return NULL)
  1344. {
  1345.     nHash = HashKey(key) % m_nHashTableSize;
  1346.  
  1347.     if (m_pHashTable == NULL)
  1348.         return NULL;
  1349.  
  1350.     // see if it exists
  1351.     CAssoc* pAssoc;
  1352.     for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext)
  1353.     {
  1354.         if (CompareElements(&pAssoc->key, &key))
  1355.             return pAssoc;
  1356.     }
  1357.     return NULL;
  1358. }
  1359.  
  1360. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1361. BOOL CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::Lookup(ARG_KEY key, VALUE& rValue) const
  1362. {
  1363.     ASSERT_VALID(this);
  1364.  
  1365.     UINT nHash;
  1366.     CAssoc* pAssoc = GetAssocAt(key, nHash);
  1367.     if (pAssoc == NULL)
  1368.         return FALSE;  // not in map
  1369.  
  1370.     rValue = pAssoc->value;
  1371.     return TRUE;
  1372. }
  1373.  
  1374. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1375. VALUE& CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::operator[](ARG_KEY key)
  1376. {
  1377.     ASSERT_VALID(this);
  1378.  
  1379.     UINT nHash;
  1380.     CAssoc* pAssoc;
  1381.     if ((pAssoc = GetAssocAt(key, nHash)) == NULL)
  1382.     {
  1383.         if (m_pHashTable == NULL)
  1384.             InitHashTable(m_nHashTableSize);
  1385.  
  1386.         // it doesn't exist, add a new Association
  1387.         pAssoc = NewAssoc();
  1388.         pAssoc->nHashValue = nHash;
  1389.         pAssoc->key = key;
  1390.         // 'pAssoc->value' is a constructed object, nothing more
  1391.  
  1392.         // put into hash table
  1393.         pAssoc->pNext = m_pHashTable[nHash];
  1394.         m_pHashTable[nHash] = pAssoc;
  1395.     }
  1396.     return pAssoc->value;  // return new reference
  1397. }
  1398.  
  1399. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1400. BOOL CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::RemoveKey(ARG_KEY key)
  1401. // remove key - return TRUE if removed
  1402. {
  1403.     ASSERT_VALID(this);
  1404.  
  1405.     if (m_pHashTable == NULL)
  1406.         return FALSE;  // nothing in the table
  1407.  
  1408.     CAssoc** ppAssocPrev;
  1409.     ppAssocPrev = &m_pHashTable[HashKey(key) % m_nHashTableSize];
  1410.  
  1411.     CAssoc* pAssoc;
  1412.     for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext)
  1413.     {
  1414.         if (CompareElements(&pAssoc->key, &key))
  1415.         {
  1416.             // remove it
  1417.             *ppAssocPrev = pAssoc->pNext;  // remove from list
  1418.             FreeAssoc(pAssoc);
  1419.             return TRUE;
  1420.         }
  1421.         ppAssocPrev = &pAssoc->pNext;
  1422.     }
  1423.     return FALSE;  // not found
  1424. }
  1425.  
  1426. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1427. void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetNextAssoc(POSITION& rNextPosition,
  1428.     KEY& rKey, VALUE& rValue) const
  1429. {
  1430.     ASSERT_VALID(this);
  1431.     ASSERT(m_pHashTable != NULL);  // never call on empty map
  1432.  
  1433.     CAssoc* pAssocRet = (CAssoc*)rNextPosition;
  1434.     ASSERT(pAssocRet != NULL);
  1435.  
  1436.     if (pAssocRet == (CAssoc*) BEFORE_START_POSITION)
  1437.     {
  1438.         // find the first association
  1439.         for (UINT nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
  1440.             if ((pAssocRet = m_pHashTable[nBucket]) != NULL)
  1441.                 break;
  1442.         ASSERT(pAssocRet != NULL);  // must find something
  1443.     }
  1444.  
  1445.     // find next association
  1446.     ASSERT(AfxIsValidAddress(pAssocRet, sizeof(CAssoc)));
  1447.     CAssoc* pAssocNext;
  1448.     if ((pAssocNext = pAssocRet->pNext) == NULL)
  1449.     {
  1450.         // go to next bucket
  1451.         for (UINT nBucket = pAssocRet->nHashValue + 1;
  1452.           nBucket < m_nHashTableSize; nBucket++)
  1453.             if ((pAssocNext = m_pHashTable[nBucket]) != NULL)
  1454.                 break;
  1455.     }
  1456.  
  1457.     rNextPosition = (POSITION) pAssocNext;
  1458.  
  1459.     // fill in return data
  1460.     rKey = pAssocRet->key;
  1461.     rValue = pAssocRet->value;
  1462. }
  1463.  
  1464. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1465. void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::Serialize(CArchive& ar)
  1466. {
  1467.     ASSERT_VALID(this);
  1468.  
  1469.     CObject::Serialize(ar);
  1470.  
  1471.     if (ar.IsStoring())
  1472.     {
  1473.         ar.WriteCount(m_nCount);
  1474.         if (m_nCount == 0)
  1475.             return;  // nothing more to do
  1476.  
  1477.         ASSERT(m_pHashTable != NULL);
  1478.         for (UINT nHash = 0; nHash < m_nHashTableSize; nHash++)
  1479.         {
  1480.             CAssoc* pAssoc;
  1481.             for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;
  1482.               pAssoc = pAssoc->pNext)
  1483.             {
  1484.                 SerializeElements(ar, &pAssoc->key, 1);
  1485.                 SerializeElements(ar, &pAssoc->value, 1);
  1486.             }
  1487.         }
  1488.     }
  1489.     else
  1490.     {
  1491.         DWORD nNewCount = ar.ReadCount();
  1492.         KEY newKey;
  1493.         VALUE newValue;
  1494.         while (nNewCount--)
  1495.         {
  1496.             SerializeElements(ar, &newKey, 1);
  1497.             SerializeElements(ar, &newValue, 1);
  1498.             SetAt(newKey, newValue);
  1499.         }
  1500.     }
  1501. }
  1502.  
  1503. #ifdef _DEBUG
  1504. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1505. void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::Dump(CDumpContext& dc) const
  1506. {
  1507.     CObject::Dump(dc);
  1508.  
  1509.     dc << "with " << m_nCount << " elements";
  1510.     if (dc.GetDepth() > 0)
  1511.     {
  1512.         // Dump in format "[key] -> value"
  1513.         KEY key;
  1514.         VALUE val;
  1515.  
  1516.         POSITION pos = GetStartPosition();
  1517.         while (pos != NULL)
  1518.         {
  1519.             GetNextAssoc(pos, key, val);
  1520.             dc << "\n\t[";
  1521.             DumpElements(dc, &key, 1);
  1522.             dc << "] = ";
  1523.             DumpElements(dc, &val, 1);
  1524.         }
  1525.     }
  1526.  
  1527.     dc << "\n";
  1528. }
  1529.  
  1530. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1531. void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::AssertValid() const
  1532. {
  1533.     CObject::AssertValid();
  1534.  
  1535.     ASSERT(m_nHashTableSize > 0);
  1536.     ASSERT(m_nCount == 0 || m_pHashTable != NULL);
  1537.         // non-empty map should have hash table
  1538. }
  1539. #endif //_DEBUG
  1540.  
  1541. /////////////////////////////////////////////////////////////////////////////
  1542. // CTypedPtrArray<BASE_CLASS, TYPE>
  1543.  
  1544. template<class BASE_CLASS, class TYPE>
  1545. class CTypedPtrArray : public BASE_CLASS
  1546. {
  1547. public:
  1548.     // Accessing elements
  1549.     TYPE GetAt(int nIndex) const
  1550.         { return (TYPE)BASE_CLASS::GetAt(nIndex); }
  1551.     TYPE& ElementAt(int nIndex)
  1552.         { return (TYPE&)BASE_CLASS::ElementAt(nIndex); }
  1553.  
  1554.     // overloaded operator helpers
  1555.     TYPE operator[](int nIndex) const
  1556.         { return (TYPE)BASE_CLASS::operator[](nIndex); }
  1557.     TYPE& operator[](int nIndex)
  1558.         { return (TYPE&)BASE_CLASS::operator[](nIndex); }
  1559. };
  1560.  
  1561. /////////////////////////////////////////////////////////////////////////////
  1562. // CTypedPtrList<BASE_CLASS, TYPE>
  1563.  
  1564. template<class BASE_CLASS, class TYPE>
  1565. class CTypedPtrList : public BASE_CLASS
  1566. {
  1567. public:
  1568.     // peek at head or tail
  1569.     TYPE& GetHead()
  1570.         { return (TYPE&)BASE_CLASS::GetHead(); }
  1571.     TYPE GetHead() const
  1572.         { return (TYPE)BASE_CLASS::GetHead(); }
  1573.     TYPE& GetTail()
  1574.         { return (TYPE&)BASE_CLASS::GetTail(); }
  1575.     TYPE GetTail() const
  1576.         { return (TYPE)BASE_CLASS::GetTail(); }
  1577.  
  1578.     // get head or tail (and remove it) - don't call on empty list!
  1579.     TYPE RemoveHead()
  1580.         { return (TYPE)BASE_CLASS::RemoveHead(); }
  1581.     TYPE RemoveTail()
  1582.         { return (TYPE)BASE_CLASS::RemoveTail(); }
  1583.  
  1584.     // iteration
  1585.     TYPE& GetNext(POSITION& rPosition)
  1586.         { return (TYPE&)BASE_CLASS::GetNext(rPosition); }
  1587.     TYPE GetNext(POSITION& rPosition) const
  1588.         { return (TYPE)BASE_CLASS::GetNext(rPosition); }
  1589.     TYPE& GetPrev(POSITION& rPosition)
  1590.         { return (TYPE&)BASE_CLASS::GetPrev(rPosition); }
  1591.     TYPE GetPrev(POSITION& rPosition) const
  1592.         { return (TYPE)BASE_CLASS::GetPrev(rPosition); }
  1593.  
  1594.     // getting/modifying an element at a given position
  1595.     TYPE& GetAt(POSITION position)
  1596.         { return (TYPE&)BASE_CLASS::GetAt(position); }
  1597.     TYPE GetAt(POSITION position) const
  1598.         { return (TYPE)BASE_CLASS::GetAt(position); }
  1599. };
  1600.  
  1601. /////////////////////////////////////////////////////////////////////////////
  1602. // CTypedPtrMap<BASE_CLASS, KEY, VALUE>
  1603.  
  1604. template<class BASE_CLASS, class KEY, class VALUE>
  1605. class CTypedPtrMap : public BASE_CLASS
  1606. {
  1607. public:
  1608.     // Lookup
  1609.     BOOL Lookup(BASE_CLASS::BASE_ARG_KEY key, VALUE& rValue) const
  1610.         { return BASE_CLASS::Lookup(key, (BASE_CLASS::BASE_VALUE&)rValue); }
  1611.  
  1612.     // Lookup and add if not there
  1613.     VALUE& operator[](BASE_CLASS::BASE_ARG_KEY key)
  1614.         { return (VALUE&)BASE_CLASS::operator[](key); }
  1615.  
  1616.     // iteration
  1617.     void GetNextAssoc(POSITION& rPosition, KEY& rKey, VALUE& rValue) const
  1618.         { BASE_CLASS::GetNextAssoc(rPosition, (BASE_CLASS::BASE_KEY&)rKey,
  1619.             (BASE_CLASS::BASE_VALUE&)rValue); }
  1620. };
  1621.  
  1622. /////////////////////////////////////////////////////////////////////////////
  1623.  
  1624. #undef THIS_FILE
  1625. #define THIS_FILE __FILE__
  1626.  
  1627. #undef new
  1628. #ifdef _REDEF_NEW
  1629. #define new DEBUG_NEW
  1630. #undef _REDEF_NEW
  1631. #endif
  1632.  
  1633. #ifdef _AFX_PACKING
  1634. #pragma pack(pop)
  1635. #endif
  1636.  
  1637. #ifdef _AFX_MINREBUILD
  1638. #pragma component(minrebuild, on)
  1639. #endif
  1640. #ifndef _AFX_FULLTYPEINFO
  1641. #pragma component(mintypeinfo, off)
  1642. #endif
  1643.  
  1644. #endif //__AFXTEMPL_H__
  1645.  
  1646. /////////////////////////////////////////////////////////////////////////////
  1647.