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