home *** CD-ROM | disk | FTP | other *** search
/ Windows Game Programming for Dummies (2nd Edition) / WinGamProgFD.iso / pc / DirectX SDK / DXSDK / samples / Multimedia / DirectInput / DIConfig / collections.h < prev    next >
Encoding:
C/C++ Source or Header  |  2001-10-08  |  33.6 KB  |  1,241 lines
  1. //-----------------------------------------------------------------------------
  2. // File: collections.h
  3. //
  4. // Desc: Contains all container templates used by the UI.
  5. //
  6. // Copyright (C) 1999-2001 Microsoft Corporation. All Rights Reserved.
  7. //-----------------------------------------------------------------------------
  8.  
  9. #ifndef __COLLECTIONS_H__
  10. #define __COLLECTIONS_H__
  11.  
  12.  
  13. // fake out afx
  14.  
  15. #define BEFORE_START_POSITION ((POSITION)-1L)
  16.  
  17. BOOL AfxIsValidAddress( const void* lp, UINT nBytes, BOOL bReadWrite = TRUE ); 
  18.  
  19. #define ASSERT assert
  20. #define AFX_INLINE inline
  21. #define AFXAPI
  22. #define ASSERT_VALID(p) assert(p != NULL)
  23.  
  24. typedef void *POSITION;
  25.  
  26. #pragma warning( disable : 4291 )
  27. inline void *__cdecl operator new(size_t, void *_P)
  28.     { return (_P); }
  29.  
  30. // afx template stuff without mfc dependencies!  :D
  31.  
  32. template<class ARG_KEY>
  33. AFX_INLINE UINT AFXAPI HashKey(ARG_KEY key)
  34. {
  35.     // default identity hash - works for most primitive values
  36.     return ((UINT)(DWORD)key) >> 4;
  37. }
  38.  
  39. template<class TYPE>
  40. AFX_INLINE void AFXAPI ConstructElements(TYPE* pElements, int nCount)
  41. {
  42.     ASSERT(nCount == 0 ||
  43.         AfxIsValidAddress(pElements, nCount * sizeof(TYPE)));
  44.  
  45.     // first do bit-wise zero initialization
  46.     memset((void*)pElements, 0, nCount * sizeof(TYPE));
  47.  
  48.     // then call the constructor(s)
  49.     for (; nCount--; pElements++)
  50.         ::new((void*)pElements) TYPE;
  51. }
  52.  
  53. template<class TYPE>
  54. AFX_INLINE void AFXAPI DestructElements(TYPE* pElements, int nCount)
  55. {
  56.     ASSERT(nCount == 0 ||
  57.         AfxIsValidAddress(pElements, nCount * sizeof(TYPE)));
  58.  
  59.     // call the destructor(s)
  60.     for (; nCount--; pElements++)
  61.         pElements->~TYPE();
  62. }
  63.  
  64. template<class TYPE>
  65. AFX_INLINE void AFXAPI CopyElements(TYPE* pDest, const TYPE* pSrc, int nCount)
  66. {
  67.     ASSERT(nCount == 0 ||
  68.         AfxIsValidAddress(pDest, nCount * sizeof(TYPE)));
  69.     ASSERT(nCount == 0 ||
  70.         AfxIsValidAddress(pSrc, nCount * sizeof(TYPE)));
  71.  
  72.     // default is element-copy using assignment
  73.     while (nCount--)
  74.         *pDest++ = *pSrc++;
  75. }
  76.  
  77. template<class TYPE, class ARG_TYPE>
  78. BOOL AFXAPI CompareElements(const TYPE* pElement1, const ARG_TYPE* pElement2)
  79. {
  80.     ASSERT(AfxIsValidAddress(pElement1, sizeof(TYPE), FALSE));
  81.     ASSERT(AfxIsValidAddress(pElement2, sizeof(ARG_TYPE), FALSE));
  82.  
  83.     return *pElement1 == *pElement2;
  84. }
  85.  
  86.  
  87. /////////////////////////////////////////////////////////////////////////////
  88. // CArray<TYPE, ARG_TYPE>
  89.  
  90. template<class TYPE, class ARG_TYPE>
  91. class CArray
  92. {
  93. public:
  94. // Construction
  95.     CArray();
  96.  
  97. // Attributes
  98.     int GetSize() const;
  99.     int GetUpperBound() const;
  100.     void SetSize(int nNewSize, int nGrowBy = -1);
  101.  
  102.     // Operations
  103.  
  104.     // Clean up
  105.     void FreeExtra();
  106.     void RemoveAll();
  107.  
  108.     // Accessing elements
  109.     TYPE GetAt(int nIndex) const;
  110.     void SetAt(int nIndex, ARG_TYPE newElement);
  111.     TYPE& ElementAt(int nIndex);
  112.  
  113.     // Direct Access to the element data (may return NULL)
  114.     const TYPE* GetData() const;
  115.     TYPE* GetData();
  116.  
  117.     // Potentially growing the array
  118.     void SetAtGrow(int nIndex, ARG_TYPE newElement);
  119.     int Add(ARG_TYPE newElement);
  120.     int Append(const CArray& src);
  121.     void Copy(const CArray& src);
  122.  
  123.     // overloaded operator helpers
  124.     TYPE operator[](int nIndex) const;
  125.     TYPE& operator[](int nIndex);
  126.  
  127.     // Operations that move elements around
  128.     void InsertAt(int nIndex, ARG_TYPE newElement, int nCount = 1);
  129.     void RemoveAt(int nIndex, int nCount = 1);
  130.     void InsertAt(int nStartIndex, CArray* pNewArray);
  131.  
  132. // Implementation
  133. protected:
  134.     TYPE* m_pData;   // the actual array of data
  135.     int m_nSize;     // # of elements (upperBound - 1)
  136.     int m_nMaxSize;  // max allocated
  137.     int m_nGrowBy;   // grow amount
  138.  
  139. public:
  140.     ~CArray();
  141. };
  142.  
  143. /////////////////////////////////////////////////////////////////////////////
  144. // CArray<TYPE, ARG_TYPE> inline functions
  145.  
  146. template<class TYPE, class ARG_TYPE>
  147. AFX_INLINE int CArray<TYPE, ARG_TYPE>::GetSize() const
  148.     { return m_nSize; }
  149. template<class TYPE, class ARG_TYPE>
  150. AFX_INLINE int CArray<TYPE, ARG_TYPE>::GetUpperBound() const
  151.     { return m_nSize-1; }
  152. template<class TYPE, class ARG_TYPE>
  153. AFX_INLINE void CArray<TYPE, ARG_TYPE>::RemoveAll()
  154.     { SetSize(0, -1); }
  155. template<class TYPE, class ARG_TYPE>
  156. AFX_INLINE TYPE CArray<TYPE, ARG_TYPE>::GetAt(int nIndex) const
  157.     { ASSERT(nIndex >= 0 && nIndex < m_nSize);
  158.         return m_pData[nIndex]; }
  159. template<class TYPE, class ARG_TYPE>
  160. AFX_INLINE void CArray<TYPE, ARG_TYPE>::SetAt(int nIndex, ARG_TYPE newElement)
  161.     { ASSERT(nIndex >= 0 && nIndex < m_nSize);
  162.         m_pData[nIndex] = newElement; }
  163. template<class TYPE, class ARG_TYPE>
  164. AFX_INLINE TYPE& CArray<TYPE, ARG_TYPE>::ElementAt(int nIndex)
  165.     { ASSERT(nIndex >= 0 && nIndex < m_nSize);
  166.         return m_pData[nIndex]; }
  167. template<class TYPE, class ARG_TYPE>
  168. AFX_INLINE const TYPE* CArray<TYPE, ARG_TYPE>::GetData() const
  169.     { return (const TYPE*)m_pData; }
  170. template<class TYPE, class ARG_TYPE>
  171. AFX_INLINE TYPE* CArray<TYPE, ARG_TYPE>::GetData()
  172.     { return (TYPE*)m_pData; }
  173. template<class TYPE, class ARG_TYPE>
  174. AFX_INLINE int CArray<TYPE, ARG_TYPE>::Add(ARG_TYPE newElement)
  175.     { int nIndex = m_nSize;
  176.         SetAtGrow(nIndex, newElement);
  177.         return nIndex; }
  178. template<class TYPE, class ARG_TYPE>
  179. AFX_INLINE TYPE CArray<TYPE, ARG_TYPE>::operator[](int nIndex) const
  180.     { return GetAt(nIndex); }
  181. template<class TYPE, class ARG_TYPE>
  182. AFX_INLINE TYPE& CArray<TYPE, ARG_TYPE>::operator[](int nIndex)
  183.     { return ElementAt(nIndex); }
  184.  
  185. /////////////////////////////////////////////////////////////////////////////
  186. // CArray<TYPE, ARG_TYPE> out-of-line functions
  187.  
  188. template<class TYPE, class ARG_TYPE>
  189. CArray<TYPE, ARG_TYPE>::CArray()
  190. {
  191.     m_pData = NULL;
  192.     m_nSize = m_nMaxSize = m_nGrowBy = 0;
  193. }
  194.  
  195. template<class TYPE, class ARG_TYPE>
  196. CArray<TYPE, ARG_TYPE>::~CArray()
  197. {
  198.     ASSERT_VALID(this);
  199.  
  200.     if (m_pData != NULL)
  201.     {
  202.         DestructElements<TYPE>(m_pData, m_nSize);
  203.         delete[] (BYTE*)m_pData;
  204.     }
  205. }
  206.  
  207. template<class TYPE, class ARG_TYPE>
  208. void CArray<TYPE, ARG_TYPE>::SetSize(int nNewSize, int nGrowBy)
  209. {
  210.     ASSERT_VALID(this);
  211.     ASSERT(nNewSize >= 0);
  212.  
  213.     if (nGrowBy != -1)
  214.         m_nGrowBy = nGrowBy;  // set new size
  215.  
  216.     if (nNewSize == 0)
  217.     {
  218.         // shrink to nothing
  219.         if (m_pData != NULL)
  220.         {
  221.             DestructElements<TYPE>(m_pData, m_nSize);
  222.             delete[] (BYTE*)m_pData;
  223.             m_pData = NULL;
  224.         }
  225.         m_nSize = m_nMaxSize = 0;
  226.     }
  227.     else if (m_pData == NULL)
  228.     {
  229.         // create one with exact size
  230. #ifdef SIZE_T_MAX
  231.         ASSERT(nNewSize <= SIZE_T_MAX/sizeof(TYPE));    // no overflow
  232. #endif
  233.         m_pData = (TYPE*) new BYTE[nNewSize * sizeof(TYPE)];
  234.         ConstructElements<TYPE>(m_pData, nNewSize);
  235.         m_nSize = m_nMaxSize = nNewSize;
  236.     }
  237.     else if (nNewSize <= m_nMaxSize)
  238.     {
  239.         // it fits
  240.         if (nNewSize > m_nSize)
  241.         {
  242.             // initialize the new elements
  243.             ConstructElements<TYPE>(&m_pData[m_nSize], nNewSize-m_nSize);
  244.         }
  245.         else if (m_nSize > nNewSize)
  246.         {
  247.             // destroy the old elements
  248.             DestructElements<TYPE>(&m_pData[nNewSize], m_nSize-nNewSize);
  249.         }
  250.         m_nSize = nNewSize;
  251.     }
  252.     else
  253.     {
  254.         // otherwise, grow array
  255.         int nGrowBy = m_nGrowBy;
  256.         if (nGrowBy == 0)
  257.         {
  258.             // heuristically determine growth when nGrowBy == 0
  259.             //  (this avoids heap fragmentation in many situations)
  260.             nGrowBy = m_nSize / 8;
  261.             nGrowBy = (nGrowBy < 4) ? 4 : ((nGrowBy > 1024) ? 1024 : nGrowBy);
  262.         }
  263.         int nNewMax;
  264.         if (nNewSize < m_nMaxSize + nGrowBy)
  265.             nNewMax = m_nMaxSize + nGrowBy;  // granularity
  266.         else
  267.             nNewMax = nNewSize;  // no slush
  268.  
  269.         ASSERT(nNewMax >= m_nMaxSize);  // no wrap around
  270. #ifdef SIZE_T_MAX
  271.         ASSERT(nNewMax <= SIZE_T_MAX/sizeof(TYPE)); // no overflow
  272. #endif
  273.         TYPE* pNewData = (TYPE*) new BYTE[nNewMax * sizeof(TYPE)];
  274.  
  275.         // copy new data from old
  276.         memcpy(pNewData, m_pData, m_nSize * sizeof(TYPE));
  277.  
  278.         // construct remaining elements
  279.         ASSERT(nNewSize > m_nSize);
  280.         ConstructElements<TYPE>(&pNewData[m_nSize], nNewSize-m_nSize);
  281.  
  282.         // get rid of old stuff (note: no destructors called)
  283.         delete[] (BYTE*)m_pData;
  284.         m_pData = pNewData;
  285.         m_nSize = nNewSize;
  286.         m_nMaxSize = nNewMax;
  287.     }
  288. }
  289.  
  290. template<class TYPE, class ARG_TYPE>
  291. int CArray<TYPE, ARG_TYPE>::Append(const CArray& src)
  292. {
  293.     ASSERT_VALID(this);
  294.     ASSERT(this != &src);   // cannot append to itself
  295.  
  296.     int nOldSize = m_nSize;
  297.     SetSize(m_nSize + src.m_nSize);
  298.     CopyElements<TYPE>(m_pData + nOldSize, src.m_pData, src.m_nSize);
  299.     return nOldSize;
  300. }
  301.  
  302. template<class TYPE, class ARG_TYPE>
  303. void CArray<TYPE, ARG_TYPE>::Copy(const CArray& src)
  304. {
  305.     ASSERT_VALID(this);
  306.     ASSERT(this != &src);   // cannot append to itself
  307.  
  308.     SetSize(src.m_nSize);
  309.     CopyElements<TYPE>(m_pData, src.m_pData, src.m_nSize);
  310. }
  311.  
  312. template<class TYPE, class ARG_TYPE>
  313. void CArray<TYPE, ARG_TYPE>::FreeExtra()
  314. {
  315.     ASSERT_VALID(this);
  316.  
  317.     if (m_nSize != m_nMaxSize)
  318.     {
  319.         // shrink to desired size
  320. #ifdef SIZE_T_MAX
  321.         ASSERT(m_nSize <= SIZE_T_MAX/sizeof(TYPE)); // no overflow
  322. #endif
  323.         TYPE* pNewData = NULL;
  324.         if (m_nSize != 0)
  325.         {
  326.             pNewData = (TYPE*) new BYTE[m_nSize * sizeof(TYPE)];
  327.             // copy new data from old
  328.             memcpy(pNewData, m_pData, m_nSize * sizeof(TYPE));
  329.         }
  330.  
  331.         // get rid of old stuff (note: no destructors called)
  332.         delete[] (BYTE*)m_pData;
  333.         m_pData = pNewData;
  334.         m_nMaxSize = m_nSize;
  335.     }
  336. }
  337.  
  338. template<class TYPE, class ARG_TYPE>
  339. void CArray<TYPE, ARG_TYPE>::SetAtGrow(int nIndex, ARG_TYPE newElement)
  340. {
  341.     ASSERT_VALID(this);
  342.     ASSERT(nIndex >= 0);
  343.  
  344.     if (nIndex >= m_nSize)
  345.         SetSize(nIndex+1, -1);
  346.     m_pData[nIndex] = newElement;
  347. }
  348.  
  349. template<class TYPE, class ARG_TYPE>
  350. void CArray<TYPE, ARG_TYPE>::InsertAt(int nIndex, ARG_TYPE newElement, int nCount /*=1*/)
  351. {
  352.     ASSERT_VALID(this);
  353.     ASSERT(nIndex >= 0);    // will expand to meet need
  354.     ASSERT(nCount > 0);     // zero or negative size not allowed
  355.  
  356.     if (nIndex >= m_nSize)
  357.     {
  358.         // adding after the end of the array
  359.         SetSize(nIndex + nCount, -1);   // grow so nIndex is valid
  360.     }
  361.     else
  362.     {
  363.         // inserting in the middle of the array
  364.         int nOldSize = m_nSize;
  365.         SetSize(m_nSize + nCount, -1);  // grow it to new size
  366.         // destroy intial data before copying over it
  367.         DestructElements<TYPE>(&m_pData[nOldSize], nCount);
  368.         // shift old data up to fill gap
  369.         memmove(&m_pData[nIndex+nCount], &m_pData[nIndex],
  370.             (nOldSize-nIndex) * sizeof(TYPE));
  371.  
  372.         // re-init slots we copied from
  373.         ConstructElements<TYPE>(&m_pData[nIndex], nCount);
  374.     }
  375.  
  376.     // insert new value in the gap
  377.     ASSERT(nIndex + nCount <= m_nSize);
  378.     while (nCount--)
  379.         m_pData[nIndex++] = newElement;
  380. }
  381.  
  382. template<class TYPE, class ARG_TYPE>
  383. void CArray<TYPE, ARG_TYPE>::RemoveAt(int nIndex, int nCount)
  384. {
  385.     ASSERT_VALID(this);
  386.     ASSERT(nIndex >= 0);
  387.     ASSERT(nCount >= 0);
  388.     ASSERT(nIndex + nCount <= m_nSize);
  389.  
  390.     // just remove a range
  391.     int nMoveCount = m_nSize - (nIndex + nCount);
  392.     DestructElements<TYPE>(&m_pData[nIndex], nCount);
  393.     if (nMoveCount)
  394.         memmove(&m_pData[nIndex], &m_pData[nIndex + nCount],
  395.             nMoveCount * sizeof(TYPE));
  396.     m_nSize -= nCount;
  397. }
  398.  
  399. template<class TYPE, class ARG_TYPE>
  400. void CArray<TYPE, ARG_TYPE>::InsertAt(int nStartIndex, CArray* pNewArray)
  401. {
  402.     ASSERT_VALID(this);
  403.     ASSERT(pNewArray != NULL);
  404.     ASSERT_VALID(pNewArray);
  405.     ASSERT(nStartIndex >= 0);
  406.  
  407.     if (pNewArray->GetSize() > 0)
  408.     {
  409.         InsertAt(nStartIndex, pNewArray->GetAt(0), pNewArray->GetSize());
  410.         for (int i = 0; i < pNewArray->GetSize(); i++)
  411.             SetAt(nStartIndex + i, pNewArray->GetAt(i));
  412.     }
  413. }
  414.  
  415. /////////////////////////////////////////////////////////////////////////////
  416. // CPlex
  417.  
  418. struct CPlex     // warning variable length structure
  419. {
  420.     CPlex* pNext;
  421.     DWORD dwReserved[1];    // align on 8 byte boundary
  422.  
  423.     // BYTE data[maxNum*elementSize];
  424.  
  425.     void* data() { return this+1; }
  426.  
  427.     static CPlex* PASCAL Create(CPlex*& head, UINT nMax, UINT cbElement);
  428.     // like 'calloc' but no zero fill
  429.     // may throw memory exceptions
  430.  
  431.     void FreeDataChain();       // free this one and links
  432. };
  433.  
  434. /////////////////////////////////////////////////////////////////////////////
  435. // CList<TYPE, ARG_TYPE>
  436.  
  437. template<class TYPE, class ARG_TYPE>
  438. class CList
  439. {
  440. protected:
  441.     struct CNode
  442.     {
  443.         CNode* pNext;
  444.         CNode* pPrev;
  445.         TYPE data;
  446.     };
  447. public:
  448. // Construction
  449.     CList(int nBlockSize = 10);
  450.  
  451. // Attributes (head and tail)
  452.     // count of elements
  453.     int GetCount() const;
  454.     BOOL IsEmpty() const;
  455.  
  456.     // peek at head or tail
  457.     TYPE& GetHead();
  458.     TYPE GetHead() const;
  459.     TYPE& GetTail();
  460.     TYPE GetTail() const;
  461.  
  462. // Operations
  463.     // get head or tail (and remove it) - don't call on empty list !
  464.     TYPE RemoveHead();
  465.     TYPE RemoveTail();
  466.  
  467.     // add before head or after tail
  468.     POSITION AddHead(ARG_TYPE newElement);
  469.     POSITION AddTail(ARG_TYPE newElement);
  470.  
  471.     // add another list of elements before head or after tail
  472.     void AddHead(CList* pNewList);
  473.     void AddTail(CList* pNewList);
  474.  
  475.     // remove all elements
  476.     void RemoveAll();
  477.  
  478.     // iteration
  479.     POSITION GetHeadPosition() const;
  480.     POSITION GetTailPosition() const;
  481.     TYPE& GetNext(POSITION& rPosition); // return *Position++
  482.     TYPE GetNext(POSITION& rPosition) const; // return *Position++
  483.     TYPE& GetPrev(POSITION& rPosition); // return *Position--
  484.     TYPE GetPrev(POSITION& rPosition) const; // return *Position--
  485.  
  486.     // getting/modifying an element at a given position
  487.     TYPE& GetAt(POSITION position);
  488.     TYPE GetAt(POSITION position) const;
  489.     void SetAt(POSITION pos, ARG_TYPE newElement);
  490.     void RemoveAt(POSITION position);
  491.  
  492.     // inserting before or after a given position
  493.     POSITION InsertBefore(POSITION position, ARG_TYPE newElement);
  494.     POSITION InsertAfter(POSITION position, ARG_TYPE newElement);
  495.  
  496.     // helper functions (note: O(n) speed)
  497.     POSITION Find(ARG_TYPE searchValue, POSITION startAfter = NULL) const;
  498.         // defaults to starting at the HEAD, return NULL if not found
  499.     POSITION FindIndex(int nIndex) const;
  500.         // get the 'nIndex'th element (may return NULL)
  501.  
  502. // Implementation
  503. protected:
  504.     CNode* m_pNodeHead;
  505.     CNode* m_pNodeTail;
  506.     int m_nCount;
  507.     CNode* m_pNodeFree;
  508.     struct CPlex* m_pBlocks;
  509.     int m_nBlockSize;
  510.  
  511.     CNode* NewNode(CNode*, CNode*);
  512.     void FreeNode(CNode*);
  513.  
  514. public:
  515.     ~CList();
  516. };
  517.  
  518. /////////////////////////////////////////////////////////////////////////////
  519. // CList<TYPE, ARG_TYPE> inline functions
  520.  
  521. template<class TYPE, class ARG_TYPE>
  522. AFX_INLINE int CList<TYPE, ARG_TYPE>::GetCount() const
  523.     { return m_nCount; }
  524. template<class TYPE, class ARG_TYPE>
  525. AFX_INLINE BOOL CList<TYPE, ARG_TYPE>::IsEmpty() const
  526.     { return m_nCount == 0; }
  527. template<class TYPE, class ARG_TYPE>
  528. AFX_INLINE TYPE& CList<TYPE, ARG_TYPE>::GetHead()
  529.     { ASSERT(m_pNodeHead != NULL);
  530.         return m_pNodeHead->data; }
  531. template<class TYPE, class ARG_TYPE>
  532. AFX_INLINE TYPE CList<TYPE, ARG_TYPE>::GetHead() const
  533.     { ASSERT(m_pNodeHead != NULL);
  534.         return m_pNodeHead->data; }
  535. template<class TYPE, class ARG_TYPE>
  536. AFX_INLINE TYPE& CList<TYPE, ARG_TYPE>::GetTail()
  537.     { ASSERT(m_pNodeTail != NULL);
  538.         return m_pNodeTail->data; }
  539. template<class TYPE, class ARG_TYPE>
  540. AFX_INLINE TYPE CList<TYPE, ARG_TYPE>::GetTail() const
  541.     { ASSERT(m_pNodeTail != NULL);
  542.         return m_pNodeTail->data; }
  543. template<class TYPE, class ARG_TYPE>
  544. AFX_INLINE POSITION CList<TYPE, ARG_TYPE>::GetHeadPosition() const
  545.     { return (POSITION) m_pNodeHead; }
  546. template<class TYPE, class ARG_TYPE>
  547. AFX_INLINE POSITION CList<TYPE, ARG_TYPE>::GetTailPosition() const
  548.     { return (POSITION) m_pNodeTail; }
  549. template<class TYPE, class ARG_TYPE>
  550. AFX_INLINE TYPE& CList<TYPE, ARG_TYPE>::GetNext(POSITION& rPosition) // return *Position++
  551.     { CNode* pNode = (CNode*) rPosition;
  552.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  553.         rPosition = (POSITION) pNode->pNext;
  554.         return pNode->data; }
  555. template<class TYPE, class ARG_TYPE>
  556. AFX_INLINE TYPE CList<TYPE, ARG_TYPE>::GetNext(POSITION& rPosition) const // return *Position++
  557.     { CNode* pNode = (CNode*) rPosition;
  558.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  559.         rPosition = (POSITION) pNode->pNext;
  560.         return pNode->data; }
  561. template<class TYPE, class ARG_TYPE>
  562. AFX_INLINE TYPE& CList<TYPE, ARG_TYPE>::GetPrev(POSITION& rPosition) // return *Position--
  563.     { CNode* pNode = (CNode*) rPosition;
  564.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  565.         rPosition = (POSITION) pNode->pPrev;
  566.         return pNode->data; }
  567. template<class TYPE, class ARG_TYPE>
  568. AFX_INLINE TYPE CList<TYPE, ARG_TYPE>::GetPrev(POSITION& rPosition) const // return *Position--
  569.     { CNode* pNode = (CNode*) rPosition;
  570.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  571.         rPosition = (POSITION) pNode->pPrev;
  572.         return pNode->data; }
  573. template<class TYPE, class ARG_TYPE>
  574. AFX_INLINE TYPE& CList<TYPE, ARG_TYPE>::GetAt(POSITION position)
  575.     { CNode* pNode = (CNode*) position;
  576.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  577.         return pNode->data; }
  578. template<class TYPE, class ARG_TYPE>
  579. AFX_INLINE TYPE CList<TYPE, ARG_TYPE>::GetAt(POSITION position) const
  580.     { CNode* pNode = (CNode*) position;
  581.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  582.         return pNode->data; }
  583. template<class TYPE, class ARG_TYPE>
  584. AFX_INLINE void CList<TYPE, ARG_TYPE>::SetAt(POSITION pos, ARG_TYPE newElement)
  585.     { CNode* pNode = (CNode*) pos;
  586.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  587.         pNode->data = newElement; }
  588.  
  589. template<class TYPE, class ARG_TYPE>
  590. CList<TYPE, ARG_TYPE>::CList(int nBlockSize)
  591. {
  592.     ASSERT(nBlockSize > 0);
  593.  
  594.     m_nCount = 0;
  595.     m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
  596.     m_pBlocks = NULL;
  597.     m_nBlockSize = nBlockSize;
  598. }
  599.  
  600. template<class TYPE, class ARG_TYPE>
  601. void CList<TYPE, ARG_TYPE>::RemoveAll()
  602. {
  603.     ASSERT_VALID(this);
  604.  
  605.     // destroy elements
  606.     CNode* pNode;
  607.     for (pNode = m_pNodeHead; pNode != NULL; pNode = pNode->pNext)
  608.         DestructElements<TYPE>(&pNode->data, 1);
  609.  
  610.     m_nCount = 0;
  611.     m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
  612.     m_pBlocks->FreeDataChain();
  613.     m_pBlocks = NULL;
  614. }
  615.  
  616. template<class TYPE, class ARG_TYPE>
  617. CList<TYPE, ARG_TYPE>::~CList()
  618. {
  619.     RemoveAll();
  620.     ASSERT(m_nCount == 0);
  621. }
  622.  
  623. /////////////////////////////////////////////////////////////////////////////
  624. // Node helpers
  625. //
  626. // Implementation note: CNode's are stored in CPlex blocks and
  627. //  chained together. Free blocks are maintained in a singly linked list
  628. //  using the 'pNext' member of CNode with 'm_pNodeFree' as the head.
  629. //  Used blocks are maintained in a doubly linked list using both 'pNext'
  630. //  and 'pPrev' as links and 'm_pNodeHead' and 'm_pNodeTail'
  631. //   as the head/tail.
  632. //
  633. // We never free a CPlex block unless the List is destroyed or RemoveAll()
  634. //  is used - so the total number of CPlex blocks may grow large depending
  635. //  on the maximum past size of the list.
  636. //
  637.  
  638. template<class TYPE, class ARG_TYPE>
  639. CList<TYPE, ARG_TYPE>::CNode*
  640. CList<TYPE, ARG_TYPE>::NewNode(CList::CNode* pPrev, CList::CNode* pNext)
  641. {
  642.     if (m_pNodeFree == NULL)
  643.     {
  644.         // add another block
  645.         CPlex* pNewBlock = CPlex::Create(m_pBlocks, m_nBlockSize,
  646.                  sizeof(CNode));
  647.  
  648.         // chain them into free list
  649.         CNode* pNode = (CNode*) pNewBlock->data();
  650.         // free in reverse order to make it easier to debug
  651.         pNode += m_nBlockSize - 1;
  652.         for (int i = m_nBlockSize-1; i >= 0; i--, pNode--)
  653.         {
  654.             pNode->pNext = m_pNodeFree;
  655.             m_pNodeFree = pNode;
  656.         }
  657.     }
  658.     ASSERT(m_pNodeFree != NULL);  // we must have something
  659.  
  660.     CList::CNode* pNode = m_pNodeFree;
  661.     m_pNodeFree = m_pNodeFree->pNext;
  662.     pNode->pPrev = pPrev;
  663.     pNode->pNext = pNext;
  664.     m_nCount++;
  665.     ASSERT(m_nCount > 0);  // make sure we don't overflow
  666.  
  667.     ConstructElements<TYPE>(&pNode->data, 1);
  668.     return pNode;
  669. }
  670.  
  671. template<class TYPE, class ARG_TYPE>
  672. void CList<TYPE, ARG_TYPE>::FreeNode(CList::CNode* pNode)
  673. {
  674.     DestructElements<TYPE>(&pNode->data, 1);
  675.     pNode->pNext = m_pNodeFree;
  676.     m_pNodeFree = pNode;
  677.     m_nCount--;
  678.     ASSERT(m_nCount >= 0);  // make sure we don't underflow
  679.  
  680.     // if no more elements, cleanup completely
  681.     if (m_nCount == 0)
  682.         RemoveAll();
  683. }
  684.  
  685. template<class TYPE, class ARG_TYPE>
  686. POSITION CList<TYPE, ARG_TYPE>::AddHead(ARG_TYPE newElement)
  687. {
  688.     ASSERT_VALID(this);
  689.  
  690.     CNode* pNewNode = NewNode(NULL, m_pNodeHead);
  691.     pNewNode->data = newElement;
  692.     if (m_pNodeHead != NULL)
  693.         m_pNodeHead->pPrev = pNewNode;
  694.     else
  695.         m_pNodeTail = pNewNode;
  696.     m_pNodeHead = pNewNode;
  697.     return (POSITION) pNewNode;
  698. }
  699.  
  700. template<class TYPE, class ARG_TYPE>
  701. POSITION CList<TYPE, ARG_TYPE>::AddTail(ARG_TYPE newElement)
  702. {
  703.     ASSERT_VALID(this);
  704.  
  705.     CNode* pNewNode = NewNode(m_pNodeTail, NULL);
  706.     pNewNode->data = newElement;
  707.     if (m_pNodeTail != NULL)
  708.         m_pNodeTail->pNext = pNewNode;
  709.     else
  710.         m_pNodeHead = pNewNode;
  711.     m_pNodeTail = pNewNode;
  712.     return (POSITION) pNewNode;
  713. }
  714.  
  715. template<class TYPE, class ARG_TYPE>
  716. void CList<TYPE, ARG_TYPE>::AddHead(CList* pNewList)
  717. {
  718.     ASSERT_VALID(this);
  719.  
  720.     ASSERT(pNewList != NULL);
  721.     ASSERT_VALID(pNewList);
  722.  
  723.     // add a list of same elements to head (maintain order)
  724.     POSITION pos = pNewList->GetTailPosition();
  725.     while (pos != NULL)
  726.         AddHead(pNewList->GetPrev(pos));
  727. }
  728.  
  729. template<class TYPE, class ARG_TYPE>
  730. void CList<TYPE, ARG_TYPE>::AddTail(CList* pNewList)
  731. {
  732.     ASSERT_VALID(this);
  733.     ASSERT(pNewList != NULL);
  734.     ASSERT_VALID(pNewList);
  735.  
  736.     // add a list of same elements
  737.     POSITION pos = pNewList->GetHeadPosition();
  738.     while (pos != NULL)
  739.         AddTail(pNewList->GetNext(pos));
  740. }
  741.  
  742. template<class TYPE, class ARG_TYPE>
  743. TYPE CList<TYPE, ARG_TYPE>::RemoveHead()
  744. {
  745.     ASSERT_VALID(this);
  746.     ASSERT(m_pNodeHead != NULL);  // don't call on empty list !!!
  747.     ASSERT(AfxIsValidAddress(m_pNodeHead, sizeof(CNode)));
  748.  
  749.     CNode* pOldNode = m_pNodeHead;
  750.     TYPE returnValue = pOldNode->data;
  751.  
  752.     m_pNodeHead = pOldNode->pNext;
  753.     if (m_pNodeHead != NULL)
  754.         m_pNodeHead->pPrev = NULL;
  755.     else
  756.         m_pNodeTail = NULL;
  757.     FreeNode(pOldNode);
  758.     return returnValue;
  759. }
  760.  
  761. template<class TYPE, class ARG_TYPE>
  762. TYPE CList<TYPE, ARG_TYPE>::RemoveTail()
  763. {
  764.     ASSERT_VALID(this);
  765.     ASSERT(m_pNodeTail != NULL);  // don't call on empty list !!!
  766.     ASSERT(AfxIsValidAddress(m_pNodeTail, sizeof(CNode)));
  767.  
  768.     CNode* pOldNode = m_pNodeTail;
  769.     TYPE returnValue = pOldNode->data;
  770.  
  771.     m_pNodeTail = pOldNode->pPrev;
  772.     if (m_pNodeTail != NULL)
  773.         m_pNodeTail->pNext = NULL;
  774.     else
  775.         m_pNodeHead = NULL;
  776.     FreeNode(pOldNode);
  777.     return returnValue;
  778. }
  779.  
  780. template<class TYPE, class ARG_TYPE>
  781. POSITION CList<TYPE, ARG_TYPE>::InsertBefore(POSITION position, ARG_TYPE newElement)
  782. {
  783.     ASSERT_VALID(this);
  784.  
  785.     if (position == NULL)
  786.         return AddHead(newElement); // insert before nothing -> head of the list
  787.  
  788.     // Insert it before position
  789.     CNode* pOldNode = (CNode*) position;
  790.     CNode* pNewNode = NewNode(pOldNode->pPrev, pOldNode);
  791.     pNewNode->data = newElement;
  792.  
  793.     if (pOldNode->pPrev != NULL)
  794.     {
  795.         ASSERT(AfxIsValidAddress(pOldNode->pPrev, sizeof(CNode)));
  796.         pOldNode->pPrev->pNext = pNewNode;
  797.     }
  798.     else
  799.     {
  800.         ASSERT(pOldNode == m_pNodeHead);
  801.         m_pNodeHead = pNewNode;
  802.     }
  803.     pOldNode->pPrev = pNewNode;
  804.     return (POSITION) pNewNode;
  805. }
  806.  
  807. template<class TYPE, class ARG_TYPE>
  808. POSITION CList<TYPE, ARG_TYPE>::InsertAfter(POSITION position, ARG_TYPE newElement)
  809. {
  810.     ASSERT_VALID(this);
  811.  
  812.     if (position == NULL)
  813.         return AddTail(newElement); // insert after nothing -> tail of the list
  814.  
  815.     // Insert it before position
  816.     CNode* pOldNode = (CNode*) position;
  817.     ASSERT(AfxIsValidAddress(pOldNode, sizeof(CNode)));
  818.     CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext);
  819.     pNewNode->data = newElement;
  820.  
  821.     if (pOldNode->pNext != NULL)
  822.     {
  823.         ASSERT(AfxIsValidAddress(pOldNode->pNext, sizeof(CNode)));
  824.         pOldNode->pNext->pPrev = pNewNode;
  825.     }
  826.     else
  827.     {
  828.         ASSERT(pOldNode == m_pNodeTail);
  829.         m_pNodeTail = pNewNode;
  830.     }
  831.     pOldNode->pNext = pNewNode;
  832.     return (POSITION) pNewNode;
  833. }
  834.  
  835. template<class TYPE, class ARG_TYPE>
  836. void CList<TYPE, ARG_TYPE>::RemoveAt(POSITION position)
  837. {
  838.     ASSERT_VALID(this);
  839.  
  840.     CNode* pOldNode = (CNode*) position;
  841.     ASSERT(AfxIsValidAddress(pOldNode, sizeof(CNode)));
  842.  
  843.     // remove pOldNode from list
  844.     if (pOldNode == m_pNodeHead)
  845.     {
  846.         m_pNodeHead = pOldNode->pNext;
  847.     }
  848.     else
  849.     {
  850.         ASSERT(AfxIsValidAddress(pOldNode->pPrev, sizeof(CNode)));
  851.         pOldNode->pPrev->pNext = pOldNode->pNext;
  852.     }
  853.     if (pOldNode == m_pNodeTail)
  854.     {
  855.         m_pNodeTail = pOldNode->pPrev;
  856.     }
  857.     else
  858.     {
  859.         ASSERT(AfxIsValidAddress(pOldNode->pNext, sizeof(CNode)));
  860.         pOldNode->pNext->pPrev = pOldNode->pPrev;
  861.     }
  862.     FreeNode(pOldNode);
  863. }
  864.  
  865. template<class TYPE, class ARG_TYPE>
  866. POSITION CList<TYPE, ARG_TYPE>::FindIndex(int nIndex) const
  867. {
  868.     ASSERT_VALID(this);
  869.  
  870.     if (nIndex >= m_nCount || nIndex < 0)
  871.         return NULL;  // went too far
  872.  
  873.     CNode* pNode = m_pNodeHead;
  874.     while (nIndex--)
  875.     {
  876.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  877.         pNode = pNode->pNext;
  878.     }
  879.     return (POSITION) pNode;
  880. }
  881.  
  882. template<class TYPE, class ARG_TYPE>
  883. POSITION CList<TYPE, ARG_TYPE>::Find(ARG_TYPE searchValue, POSITION startAfter) const
  884. {
  885.     ASSERT_VALID(this);
  886.  
  887.     CNode* pNode = (CNode*) startAfter;
  888.     if (pNode == NULL)
  889.     {
  890.         pNode = m_pNodeHead;  // start at head
  891.     }
  892.     else
  893.     {
  894.         ASSERT(AfxIsValidAddress(pNode, sizeof(CNode)));
  895.         pNode = pNode->pNext;  // start after the one specified
  896.     }
  897.  
  898.     for (; pNode != NULL; pNode = pNode->pNext)
  899.         if (CompareElements<TYPE>(&pNode->data, &searchValue))
  900.             return (POSITION)pNode;
  901.     return NULL;
  902. }
  903.  
  904. /////////////////////////////////////////////////////////////////////////////
  905. // CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>
  906.  
  907. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  908. class CMap
  909. {
  910. protected:
  911.     // Association
  912.     struct CAssoc
  913.     {
  914.         CAssoc* pNext;
  915.         UINT nHashValue;  // needed for efficient iteration
  916.         KEY key;
  917.         VALUE value;
  918.     };
  919. public:
  920. // Construction
  921.     CMap(int nBlockSize = 10);
  922.  
  923. // Attributes
  924.     // number of elements
  925.     int GetCount() const;
  926.     BOOL IsEmpty() const;
  927.  
  928.     // Lookup
  929.     BOOL Lookup(ARG_KEY key, VALUE& rValue) const;
  930.  
  931. // Operations
  932.     // Lookup and add if not there
  933.     VALUE& operator[](ARG_KEY key);
  934.  
  935.     // add a new (key, value) pair
  936.     void SetAt(ARG_KEY key, ARG_VALUE newValue);
  937.  
  938.     // removing existing (key, ?) pair
  939.     BOOL RemoveKey(ARG_KEY key);
  940.     void RemoveAll();
  941.  
  942.     // iterating all (key, value) pairs
  943.     POSITION GetStartPosition() const;
  944.     void GetNextAssoc(POSITION& rNextPosition, KEY& rKey, VALUE& rValue) const;
  945.  
  946.     // advanced features for derived classes
  947.     UINT GetHashTableSize() const;
  948.     void InitHashTable(UINT hashSize, BOOL bAllocNow = TRUE);
  949.  
  950. // Implementation
  951. protected:
  952.     CAssoc** m_pHashTable;
  953.     UINT m_nHashTableSize;
  954.     int m_nCount;
  955.     CAssoc* m_pFreeList;
  956.     struct CPlex* m_pBlocks;
  957.     int m_nBlockSize;
  958.  
  959.     CAssoc* NewAssoc();
  960.     void FreeAssoc(CAssoc*);
  961.     CAssoc* GetAssocAt(ARG_KEY, UINT&) const;
  962.  
  963. public:
  964.     ~CMap();
  965. };
  966.  
  967. /////////////////////////////////////////////////////////////////////////////
  968. // CMap<KEY, ARG_KEY, VALUE, ARG_VALUE> inline functions
  969.  
  970. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  971. AFX_INLINE int CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetCount() const
  972.     { return m_nCount; }
  973. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  974. AFX_INLINE BOOL CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::IsEmpty() const
  975.     { return m_nCount == 0; }
  976. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  977. AFX_INLINE void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::SetAt(ARG_KEY key, ARG_VALUE newValue)
  978.     { (*this)[key] = newValue; }
  979. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  980. AFX_INLINE POSITION CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetStartPosition() const
  981.     { return (m_nCount == 0) ? NULL : BEFORE_START_POSITION; }
  982. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  983. AFX_INLINE UINT CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetHashTableSize() const
  984.     { return m_nHashTableSize; }
  985.  
  986. /////////////////////////////////////////////////////////////////////////////
  987. // CMap<KEY, ARG_KEY, VALUE, ARG_VALUE> out-of-line functions
  988.  
  989. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  990. CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CMap(int nBlockSize)
  991. {
  992.     ASSERT(nBlockSize > 0);
  993.  
  994.     m_pHashTable = NULL;
  995.     m_nHashTableSize = 17;  // default size
  996.     m_nCount = 0;
  997.     m_pFreeList = NULL;
  998.     m_pBlocks = NULL;
  999.     m_nBlockSize = nBlockSize;
  1000. }
  1001.  
  1002. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1003. void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::InitHashTable(
  1004.     UINT nHashSize, BOOL bAllocNow)
  1005. //
  1006. // Used to force allocation of a hash table or to override the default
  1007. //   hash table size of (which is fairly small)
  1008. {
  1009.     ASSERT_VALID(this);
  1010.     ASSERT(m_nCount == 0);
  1011.     ASSERT(nHashSize > 0);
  1012.  
  1013.     if (m_pHashTable != NULL)
  1014.     {
  1015.         // free hash table
  1016.         delete[] m_pHashTable;
  1017.         m_pHashTable = NULL;
  1018.     }
  1019.  
  1020.     if (bAllocNow)
  1021.     {
  1022.         m_pHashTable = new CAssoc* [nHashSize];
  1023.         memset(m_pHashTable, 0, sizeof(CAssoc*) * nHashSize);
  1024.     }
  1025.     m_nHashTableSize = nHashSize;
  1026. }
  1027.  
  1028. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1029. void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::RemoveAll()
  1030. {
  1031.     ASSERT_VALID(this);
  1032.  
  1033.     if (m_pHashTable != NULL)
  1034.     {
  1035.         // destroy elements (values and keys)
  1036.         for (UINT nHash = 0; nHash < m_nHashTableSize; nHash++)
  1037.         {
  1038.             CAssoc* pAssoc;
  1039.             for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;
  1040.               pAssoc = pAssoc->pNext)
  1041.             {
  1042.                 DestructElements<VALUE>(&pAssoc->value, 1);
  1043.                 DestructElements<KEY>(&pAssoc->key, 1);
  1044.             }
  1045.         }
  1046.     }
  1047.  
  1048.     // free hash table
  1049.     delete[] m_pHashTable;
  1050.     m_pHashTable = NULL;
  1051.  
  1052.     m_nCount = 0;
  1053.     m_pFreeList = NULL;
  1054.     m_pBlocks->FreeDataChain();
  1055.     m_pBlocks = NULL;
  1056. }
  1057.  
  1058. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1059. CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::~CMap()
  1060. {
  1061.     RemoveAll();
  1062.     ASSERT(m_nCount == 0);
  1063. }
  1064.  
  1065. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1066. CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CAssoc*
  1067. CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::NewAssoc()
  1068. {
  1069.     if (m_pFreeList == NULL)
  1070.     {
  1071.         // add another block
  1072.         CPlex* newBlock = CPlex::Create(m_pBlocks, m_nBlockSize, sizeof(CMap::CAssoc));
  1073.         // chain them into free list
  1074.         CMap::CAssoc* pAssoc = (CMap::CAssoc*) newBlock->data();
  1075.         // free in reverse order to make it easier to debug
  1076.         pAssoc += m_nBlockSize - 1;
  1077.         for (int i = m_nBlockSize-1; i >= 0; i--, pAssoc--)
  1078.         {
  1079.             pAssoc->pNext = m_pFreeList;
  1080.             m_pFreeList = pAssoc;
  1081.         }
  1082.     }
  1083.     ASSERT(m_pFreeList != NULL);  // we must have something
  1084.  
  1085.     CMap::CAssoc* pAssoc = m_pFreeList;
  1086.     m_pFreeList = m_pFreeList->pNext;
  1087.     m_nCount++;
  1088.     ASSERT(m_nCount > 0);  // make sure we don't overflow
  1089.     ConstructElements<KEY>(&pAssoc->key, 1);
  1090.     ConstructElements<VALUE>(&pAssoc->value, 1);   // special construct values
  1091.     return pAssoc;
  1092. }
  1093.  
  1094. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1095. void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::FreeAssoc(CMap::CAssoc* pAssoc)
  1096. {
  1097.     DestructElements<VALUE>(&pAssoc->value, 1);
  1098.     DestructElements<KEY>(&pAssoc->key, 1);
  1099.     pAssoc->pNext = m_pFreeList;
  1100.     m_pFreeList = pAssoc;
  1101.     m_nCount--;
  1102.     ASSERT(m_nCount >= 0);  // make sure we don't underflow
  1103.  
  1104.     // if no more elements, cleanup completely
  1105.     if (m_nCount == 0)
  1106.         RemoveAll();
  1107. }
  1108.  
  1109. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1110. CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::CAssoc*
  1111. CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetAssocAt(ARG_KEY key, UINT& nHash) const
  1112. // find association (or return NULL)
  1113. {
  1114.     nHash = HashKey<ARG_KEY>(key) % m_nHashTableSize;
  1115.  
  1116.     if (m_pHashTable == NULL)
  1117.         return NULL;
  1118.  
  1119.     // see if it exists
  1120.     CAssoc* pAssoc;
  1121.     for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL; pAssoc = pAssoc->pNext)
  1122.     {
  1123.         if (CompareElements(&pAssoc->key, &key))
  1124.             return pAssoc;
  1125.     }
  1126.     return NULL;
  1127. }
  1128.  
  1129. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1130. BOOL CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::Lookup(ARG_KEY key, VALUE& rValue) const
  1131. {
  1132.     ASSERT_VALID(this);
  1133.  
  1134.     UINT nHash;
  1135.     CAssoc* pAssoc = GetAssocAt(key, nHash);
  1136.     if (pAssoc == NULL)
  1137.         return FALSE;  // not in map
  1138.  
  1139.     rValue = pAssoc->value;
  1140.     return TRUE;
  1141. }
  1142.  
  1143. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1144. VALUE& CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::operator[](ARG_KEY key)
  1145. {
  1146.     ASSERT_VALID(this);
  1147.  
  1148.     UINT nHash;
  1149.     CAssoc* pAssoc;
  1150.     if ((pAssoc = GetAssocAt(key, nHash)) == NULL)
  1151.     {
  1152.         if (m_pHashTable == NULL)
  1153.             InitHashTable(m_nHashTableSize);
  1154.  
  1155.         // it doesn't exist, add a new Association
  1156.         pAssoc = NewAssoc();
  1157.         pAssoc->nHashValue = nHash;
  1158.         pAssoc->key = key;
  1159.         // 'pAssoc->value' is a constructed object, nothing more
  1160.  
  1161.         // put into hash table
  1162.         pAssoc->pNext = m_pHashTable[nHash];
  1163.         m_pHashTable[nHash] = pAssoc;
  1164.     }
  1165.     return pAssoc->value;  // return new reference
  1166. }
  1167.  
  1168. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1169. BOOL CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::RemoveKey(ARG_KEY key)
  1170. // remove key - return TRUE if removed
  1171. {
  1172.     ASSERT_VALID(this);
  1173.  
  1174.     if (m_pHashTable == NULL)
  1175.         return FALSE;  // nothing in the table
  1176.  
  1177.     CAssoc** ppAssocPrev;
  1178.     ppAssocPrev = &m_pHashTable[HashKey<ARG_KEY>(key) % m_nHashTableSize];
  1179.  
  1180.     CAssoc* pAssoc;
  1181.     for (pAssoc = *ppAssocPrev; pAssoc != NULL; pAssoc = pAssoc->pNext)
  1182.     {
  1183.         if (CompareElements(&pAssoc->key, &key))
  1184.         {
  1185.             // remove it
  1186.             *ppAssocPrev = pAssoc->pNext;  // remove from list
  1187.             FreeAssoc(pAssoc);
  1188.             return TRUE;
  1189.         }
  1190.         ppAssocPrev = &pAssoc->pNext;
  1191.     }
  1192.     return FALSE;  // not found
  1193. }
  1194.  
  1195. template<class KEY, class ARG_KEY, class VALUE, class ARG_VALUE>
  1196. void CMap<KEY, ARG_KEY, VALUE, ARG_VALUE>::GetNextAssoc(POSITION& rNextPosition,
  1197.     KEY& rKey, VALUE& rValue) const
  1198. {
  1199.     ASSERT_VALID(this);
  1200.     ASSERT(m_pHashTable != NULL);  // never call on empty map
  1201.  
  1202.     CAssoc* pAssocRet = (CAssoc*)rNextPosition;
  1203.     ASSERT(pAssocRet != NULL);
  1204.  
  1205.     if (pAssocRet == (CAssoc*) BEFORE_START_POSITION)
  1206.     {
  1207.         // find the first association
  1208.         for (UINT nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
  1209.             if ((pAssocRet = m_pHashTable[nBucket]) != NULL)
  1210.                 break;
  1211.         ASSERT(pAssocRet != NULL);  // must find something
  1212.     }
  1213.  
  1214.     // find next association
  1215.     ASSERT(AfxIsValidAddress(pAssocRet, sizeof(CAssoc)));
  1216.     CAssoc* pAssocNext;
  1217.     if ((pAssocNext = pAssocRet->pNext) == NULL)
  1218.     {
  1219.         // go to next bucket
  1220.         for (UINT nBucket = pAssocRet->nHashValue + 1;
  1221.              nBucket < m_nHashTableSize; nBucket++)
  1222.             if ((pAssocNext = m_pHashTable[nBucket]) != NULL)
  1223.                 break;
  1224.     }
  1225.  
  1226.     rNextPosition = (POSITION) pAssocNext;
  1227.  
  1228.     // fill in return data
  1229.     rKey = pAssocRet->key;
  1230.     rValue = pAssocRet->value;
  1231. }
  1232.  
  1233.  
  1234. #undef ASSERT
  1235. #undef AFX_INLINE
  1236. #undef AFXAPI
  1237. #undef ASSERT_VALID
  1238.  
  1239.  
  1240. #endif //__COLLECTIONS_H__
  1241.