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