00001 //============================================================================= 00002 // filename: RmLinkedList.h 00003 // 00004 // ATI Research, Inc. 00005 // 3D Application Research Group 00006 // 00007 // Description: RenderMonkey's Templated LinkedList Class 00008 // 00009 //============================================================================= 00010 // (C) 2004 ATI Research, Inc. All rights reserved. 00011 //============================================================================= 00012 00013 #ifndef _RM_CORE_LINKED_LIST_H_ 00014 #define _RM_CORE_LINKED_LIST_H_ 00015 00016 #include <Core/RmTypes.h> 00017 00018 //----------------------------------------------------------------------------- 00034 //----------------------------------------------------------------------------- 00035 00036 // Necessary to remove extraneous warnings about templated usage: 00037 #pragma warning( disable : 4251 ) 00038 00039 template <class Type> 00040 class RmLinkedList 00041 { 00042 public : 00043 //-------------------------------------------------------------------------- 00049 //-------------------------------------------------------------------------- 00050 class ItemNode 00051 { 00052 public : 00053 //----------------------------------------------------------------------- 00060 //----------------------------------------------------------------------- 00061 ItemNode( RmLinkedList<Type> *pParent ) : 00062 m_pParent(pParent), 00063 m_pPrev(NULL), 00064 m_pNext(NULL) 00065 { 00066 }; // End of Constructor 00067 00068 //----------------------------------------------------------------------- 00076 //----------------------------------------------------------------------- 00077 ItemNode( RmLinkedList<Type> *pParent, Type data ) : 00078 m_pParent(pParent), 00079 m_data(data), 00080 m_pPrev(NULL), 00081 m_pNext(NULL) 00082 { 00083 }; // End of Constructor 00084 00085 //----------------------------------------------------------------------- 00090 //----------------------------------------------------------------------- 00091 ~ItemNode() 00092 { 00093 }; // End of Destructor 00094 00095 //----------------------------------------------------------------------- 00101 //----------------------------------------------------------------------- 00102 RmLinkedList<Type>* GetParent() { return m_pParent; }; 00103 00104 //----------------------------------------------------------------------- 00110 //----------------------------------------------------------------------- 00111 const RmLinkedList<Type>* GetParent() const { return m_pParent; }; 00112 00113 //----------------------------------------------------------------------- 00119 //----------------------------------------------------------------------- 00120 Type& GetData() { return m_data; }; 00121 00122 //----------------------------------------------------------------------- 00128 //----------------------------------------------------------------------- 00129 const Type& GetData() const { return m_data; }; 00130 00131 //----------------------------------------------------------------------- 00132 // Neighbor Accessors 00133 //----------------------------------------------------------------------- 00134 00135 //----------------------------------------------------------------------- 00141 //----------------------------------------------------------------------- 00142 void SetNext( ItemNode *pNext ) { m_pNext = pNext; }; 00143 00144 //----------------------------------------------------------------------- 00150 //----------------------------------------------------------------------- 00151 void SetPrev( ItemNode *pPrev ) { m_pPrev = pPrev; }; 00152 00153 //----------------------------------------------------------------------- 00159 //----------------------------------------------------------------------- 00160 ItemNode* GetNext() { return m_pNext; }; 00161 00162 //----------------------------------------------------------------------- 00168 //----------------------------------------------------------------------- 00169 const ItemNode* GetNext() const { return m_pNext; }; 00170 00171 //----------------------------------------------------------------------- 00177 //----------------------------------------------------------------------- 00178 ItemNode* GetPrev() { return m_pPrev; }; 00179 00180 //----------------------------------------------------------------------- 00186 //----------------------------------------------------------------------- 00187 const ItemNode* GetPrev() const { return m_pPrev; }; 00188 00189 //----------------------------------------------------------------------- 00197 //----------------------------------------------------------------------- 00198 void* operator new( size_t nSize ) 00199 { 00200 RM_BYTE *pBuffer = RmAllocateBuffer(nSize); 00201 return pBuffer; 00202 }; // End of operator new 00203 00204 //----------------------------------------------------------------------- 00210 //----------------------------------------------------------------------- 00211 void operator delete( void* pPtr ) 00212 { 00213 RmDeallocateBuffer((RM_BYTE*)pPtr); 00214 }; // End of delete 00215 00216 private : 00217 RmLinkedList<Type> *m_pParent; 00218 00219 Type m_data; 00220 ItemNode *m_pNext; 00221 ItemNode *m_pPrev; 00222 }; // End of ItemNode 00223 00224 //-------------------------------------------------------------------------- 00231 //-------------------------------------------------------------------------- 00232 class const_iterator 00233 { 00234 friend RmLinkedList<Type>; 00235 00236 public : 00237 //----------------------------------------------------------------------- 00242 //----------------------------------------------------------------------- 00243 const_iterator() : 00244 m_pParent(NULL), 00245 m_pItemNode(NULL) 00246 { 00247 }; // End of Constructor 00248 00249 //----------------------------------------------------------------------- 00254 //----------------------------------------------------------------------- 00255 const_iterator( const RmLinkedList<Type> *pParent, 00256 ItemNode* pItemNode ) : 00257 m_pParent(pParent), 00258 m_pItemNode(pItemNode) 00259 { 00260 }; // End of Constructor 00261 00262 //----------------------------------------------------------------------- 00267 //----------------------------------------------------------------------- 00268 ~const_iterator() {}; 00269 00270 //----------------------------------------------------------------------- 00271 // Operators 00272 //----------------------------------------------------------------------- 00273 00274 //----------------------------------------------------------------------- 00280 //----------------------------------------------------------------------- 00281 const_iterator& operator++ () 00282 { 00283 assert(m_pItemNode!=NULL); 00284 00285 m_pItemNode = m_pItemNode->GetNext(); 00286 return *this; 00287 }; // End of operator ++ 00288 00289 //----------------------------------------------------------------------- 00295 //----------------------------------------------------------------------- 00296 const_iterator operator++ ( int ) 00297 { 00298 assert(m_pItemNode!=NULL); 00299 00300 const_iterator itr(m_pParent,m_pItemNode); 00301 m_pItemNode = m_pItemNode->GetNext(); 00302 00303 return itr; 00304 }; // End of operator ++ 00305 00306 //----------------------------------------------------------------------- 00312 //----------------------------------------------------------------------- 00313 const_iterator& operator-- () 00314 { 00315 // m_pItemNode can be NULL if its end iterator 00316 // try to grab last element of list 00317 if (m_pItemNode==NULL) 00318 { 00319 m_pItemNode = m_pParent->GetTail(); 00320 } // End if 00321 else 00322 { 00323 m_pItemNode = m_pItemNode->GetPrev(); 00324 } // End else 00325 00326 return *this; 00327 }; // End of operator ++ 00328 00329 //----------------------------------------------------------------------- 00335 //----------------------------------------------------------------------- 00336 const_iterator operator-- ( int ) 00337 { 00338 assert(m_pItemNode!=NULL); 00339 00340 const_iterator itr(m_pParent,m_pItemNode); 00341 00342 // m_pItemNode can be NULL if its end iterator 00343 // try to grab last element of list 00344 if (m_pItemNode==NULL) 00345 { 00346 m_pItemNode = m_pParent->GetTail(); 00347 } // End if 00348 else 00349 { 00350 m_pItemNode = m_pItemNode->GetPrev(); 00351 } // End else 00352 00353 return itr; 00354 }; // End of operator ++ 00355 00356 //----------------------------------------------------------------------- 00362 //----------------------------------------------------------------------- 00363 const Type& operator * () const 00364 { 00365 assert(m_pItemNode!=NULL); 00366 return m_pItemNode->GetData(); 00367 }; // End of operator * 00368 00369 //----------------------------------------------------------------------- 00376 //----------------------------------------------------------------------- 00377 bool operator== ( const const_iterator &src ) 00378 { 00379 if (m_pItemNode==src.m_pItemNode) 00380 return true; 00381 00382 return false; 00383 }; // End of operator == 00384 00385 //----------------------------------------------------------------------- 00392 //----------------------------------------------------------------------- 00393 bool operator!= ( const const_iterator &src ) 00394 { 00395 if (m_pItemNode!=src.m_pItemNode) 00396 return true; 00397 00398 return false; 00399 }; // End of operator == 00400 00401 protected : 00402 const RmLinkedList<Type> *m_pParent; 00403 ItemNode *m_pItemNode; 00404 }; // End of const_iterator 00405 00406 //-------------------------------------------------------------------------- 00411 //-------------------------------------------------------------------------- 00412 class iterator : public const_iterator 00413 { 00414 friend RmLinkedList<Type>; 00415 00416 public : 00417 //----------------------------------------------------------------------- 00422 //----------------------------------------------------------------------- 00423 iterator() : const_iterator() 00424 { 00425 }; // End of Constructor 00426 00427 //----------------------------------------------------------------------- 00432 //----------------------------------------------------------------------- 00433 iterator( const RmLinkedList<Type> *pParent, 00434 ItemNode* pItemNode ) : const_iterator(pParent,pItemNode) 00435 { 00436 }; // End of Constructor 00437 00438 //----------------------------------------------------------------------- 00443 //----------------------------------------------------------------------- 00444 ~iterator() {}; 00445 00446 //----------------------------------------------------------------------- 00447 // Operators 00448 //----------------------------------------------------------------------- 00449 00450 //----------------------------------------------------------------------- 00456 //----------------------------------------------------------------------- 00457 iterator& operator++ () 00458 { 00459 assert(m_pItemNode!=NULL); 00460 00461 m_pItemNode = m_pItemNode->GetNext(); 00462 return *this; 00463 }; // End of operator ++ 00464 00465 //----------------------------------------------------------------------- 00471 //----------------------------------------------------------------------- 00472 iterator operator++ ( int ) 00473 { 00474 assert(m_pItemNode!=NULL); 00475 00476 iterator itr(m_pParent,m_pItemNode); 00477 m_pItemNode = m_pItemNode->GetNext(); 00478 00479 return itr; 00480 }; // End of operator ++ 00481 00482 //----------------------------------------------------------------------- 00488 //----------------------------------------------------------------------- 00489 iterator& operator-- () 00490 { 00491 // m_pItemNode can be NULL if its end iterator 00492 // try to grab last element of list 00493 if (m_pItemNode==NULL) 00494 { 00495 m_pItemNode = const_cast<RmLinkedList<Type>*>(m_pParent)->GetTail(); 00496 } // End if 00497 else 00498 { 00499 m_pItemNode = m_pItemNode->GetPrev(); 00500 } // End else 00501 00502 return *this; 00503 }; // End of operator ++ 00504 00505 //----------------------------------------------------------------------- 00511 //----------------------------------------------------------------------- 00512 iterator operator-- ( int ) 00513 { 00514 assert(m_pItemNode!=NULL); 00515 00516 iterator itr(m_pParent,m_pItemNode); 00517 00518 // m_pItemNode can be NULL if its end iterator 00519 // try to grab last element of list 00520 if (m_pItemNode==NULL) 00521 { 00522 m_pItemNode = m_pParent->GetTail(); 00523 } // End if 00524 else 00525 { 00526 m_pItemNode = m_pItemNode->GetPrev(); 00527 } // End else 00528 00529 00530 return itr; 00531 }; // End of operator ++ 00532 00533 //----------------------------------------------------------------------- 00539 //----------------------------------------------------------------------- 00540 Type& operator * () 00541 { 00542 assert(m_pItemNode!=NULL); 00543 return m_pItemNode->GetData(); 00544 }; // End of operator * 00545 00546 //----------------------------------------------------------------------- 00553 //----------------------------------------------------------------------- 00554 bool operator == ( const iterator &src ) 00555 { 00556 if (m_pItemNode==src.m_pItemNode) 00557 return true; 00558 00559 return false; 00560 }; // End of operator == 00561 00562 //----------------------------------------------------------------------- 00569 //----------------------------------------------------------------------- 00570 bool operator!= ( const iterator &src ) 00571 { 00572 if (m_pItemNode!=src.m_pItemNode) 00573 return true; 00574 00575 return false; 00576 }; // End of operator == 00577 }; // End of iterator 00578 00579 public : 00580 //-------------------------------------------------------------------------- 00585 //-------------------------------------------------------------------------- 00586 RmLinkedList() : 00587 m_nNumItems(0), 00588 m_pHead(NULL), 00589 m_pTail(NULL) 00590 { 00591 }; // End of Constructor 00592 00593 //-------------------------------------------------------------------------- 00600 //-------------------------------------------------------------------------- 00601 RmLinkedList( const RmLinkedList<Type> &src ) : 00602 m_nNumItems(0), 00603 m_pHead(NULL), 00604 m_pTail(NULL) 00605 { 00606 ItemNode *pNode = src.m_pHead; 00607 while (pNode!=NULL) 00608 { 00609 push_back(pNode->GetData()); 00610 pNode = pNode->GetNext(); 00611 } // End while 00612 }; // End of Constructor 00613 00614 //-------------------------------------------------------------------------- 00619 //-------------------------------------------------------------------------- 00620 ~RmLinkedList() 00621 { 00622 clear(); 00623 }; // End of Destructor 00624 00625 //-------------------------------------------------------------------------- 00626 // Information Accessors 00627 //-------------------------------------------------------------------------- 00628 00629 //-------------------------------------------------------------------------- 00635 //-------------------------------------------------------------------------- 00636 int size() const { return m_nNumItems; }; 00637 00638 //-------------------------------------------------------------------------- 00644 //-------------------------------------------------------------------------- 00645 bool empty() const { return (m_nNumItems==0); }; 00646 00647 //-------------------------------------------------------------------------- 00648 // ItemNode Accessors 00649 //-------------------------------------------------------------------------- 00650 00651 //-------------------------------------------------------------------------- 00657 //-------------------------------------------------------------------------- 00658 ItemNode* GetHead() { return m_pHead; }; 00659 00660 //-------------------------------------------------------------------------- 00666 //-------------------------------------------------------------------------- 00667 const ItemNode* GetHead() const { return m_pHead; }; 00668 00669 //-------------------------------------------------------------------------- 00675 //-------------------------------------------------------------------------- 00676 ItemNode* GetTail() { return m_pTail; }; 00677 00678 //-------------------------------------------------------------------------- 00684 //-------------------------------------------------------------------------- 00685 const ItemNode* GetTail() const { return m_pTail; }; 00686 00687 //-------------------------------------------------------------------------- 00688 // Operations 00689 //-------------------------------------------------------------------------- 00690 00691 //-------------------------------------------------------------------------- 00697 //-------------------------------------------------------------------------- 00698 bool clear() 00699 { 00700 while (m_pHead!=NULL) 00701 { 00702 removeItemNode(m_pHead); 00703 } // End while 00704 00705 return true; 00706 }; // End of clear 00707 00708 00709 //-------------------------------------------------------------------------- 00715 //-------------------------------------------------------------------------- 00716 Type& front() 00717 { 00718 assert(m_pHead!=NULL); 00719 return m_pHead->GetData(); 00720 }; // End of front 00721 00722 //-------------------------------------------------------------------------- 00728 //-------------------------------------------------------------------------- 00729 const Type& front() const 00730 { 00731 assert(m_pHead!=NULL); 00732 return m_pHead->GetData(); 00733 }; // End of front 00734 00735 //-------------------------------------------------------------------------- 00741 //-------------------------------------------------------------------------- 00742 Type& back() 00743 { 00744 assert(m_pTail!=NULL); 00745 return m_pTail->GetData(); 00746 }; // End of front 00747 00748 //-------------------------------------------------------------------------- 00754 //-------------------------------------------------------------------------- 00755 const Type& back() const 00756 { 00757 assert(m_pTail!=NULL); 00758 return m_pTail->GetData(); 00759 }; // End of front 00760 00761 //-------------------------------------------------------------------------- 00768 //-------------------------------------------------------------------------- 00769 bool push_back( Type data ) 00770 { 00771 ItemNode *pItemNode = new ItemNode(this,data); 00772 if (pItemNode==NULL) 00773 return false; 00774 00775 if (m_pHead==NULL) 00776 { 00777 m_pHead = pItemNode; 00778 m_pTail = m_pHead; 00779 } // End if 00780 else 00781 { 00782 assert(m_pTail!=NULL); 00783 00784 m_pTail->SetNext(pItemNode); 00785 pItemNode->SetPrev(m_pTail); 00786 m_pTail = pItemNode; 00787 } // End if 00788 00789 m_nNumItems++; 00790 return true; 00791 }; // End of push_back 00792 00793 //-------------------------------------------------------------------------- 00800 //-------------------------------------------------------------------------- 00801 bool push_front( Type data ) 00802 { 00803 ItemNode *pItemNode = new ItemNode(this,data); 00804 if (pItemNode==NULL) 00805 return false; 00806 00807 if (m_pHead==NULL) 00808 { 00809 m_pHead = pItemNode; 00810 m_pTail = m_pHead; 00811 } // End if 00812 else 00813 { 00814 assert(m_pHead!=NULL); 00815 00816 m_pHead->SetPrev(pItemNode); 00817 pItemNode->SetNext(m_pHead); 00818 m_pHead = pItemNode; 00819 } // End if 00820 00821 m_nNumItems++; 00822 00823 return true; 00824 }; // End of push_front 00825 00826 //-------------------------------------------------------------------------- 00832 //-------------------------------------------------------------------------- 00833 bool pop_front() 00834 { 00835 assert(m_nNumItems>0); 00836 assert(m_pHead!=NULL); 00837 00838 removeItemNode(m_pHead); 00839 return true; 00840 }; // End pof pop_front 00841 00842 //-------------------------------------------------------------------------- 00848 //-------------------------------------------------------------------------- 00849 bool pop_back() 00850 { 00851 assert(m_nNumItems>0); 00852 assert(m_pTail!=NULL); 00853 00854 removeItemNode(m_pTail); 00855 return true; 00856 }; // End pof pop_back 00857 00858 //-------------------------------------------------------------------------- 00865 //-------------------------------------------------------------------------- 00866 bool remove( Type data ) 00867 { 00868 ItemNode *pItemNode = m_pHead; 00869 while (pItemNode!=NULL) 00870 { 00871 if (pItemNode->GetData()==data) 00872 { 00873 pItemNode = removeItemNode(pItemNode); 00874 } // End if 00875 else 00876 { 00877 pItemNode = pItemNode->GetNext(); 00878 } // End else 00879 } // End while 00880 00881 return true; 00882 }; // End of remove 00883 00884 //-------------------------------------------------------------------------- 00893 //-------------------------------------------------------------------------- 00894 bool insert( iterator &where, Type data ) 00895 { 00896 if (where==end()) 00897 { 00898 return push_back(data); 00899 } // End if 00900 00901 if (where==begin()) 00902 { 00903 return push_front(data); 00904 } // End if 00905 00906 // If we are here, we are trying to insert in middle 00907 ItemNode *pNewNode = new ItemNode(this,data); 00908 if (pNewNode==NULL) 00909 return false; 00910 00911 ItemNode *pWhereNode = where.m_pItemNode; 00912 assert(pWhereNode!=NULL); 00913 00914 ItemNode *pPrev = pWhereNode->GetPrev(); 00915 assert(pPrev!=NULL); 00916 pPrev->SetNext(pNewNode); 00917 pWhereNode->SetPrev(pNewNode); 00918 00919 pNewNode->SetPrev(pPrev); 00920 pNewNode->SetNext(pWhereNode); 00921 00922 m_nNumItems++; 00923 00924 return true; 00925 }; // End of insert 00926 00927 //-------------------------------------------------------------------------- 00934 //-------------------------------------------------------------------------- 00935 void swap( iterator &itr1, iterator &itr2 ) 00936 { 00937 if( ( itr1 != end() ) 00938 && ( itr2 != end() ) ) 00939 { 00940 ItemNode *pItr1Node = itr1.m_pItemNode; 00941 ItemNode *pItr2Node = itr2.m_pItemNode; 00942 00943 if( ( NULL != pItr1Node ) 00944 && ( NULL != pItr2Node ) 00945 && ( pItr1Node != pItr2Node ) ) 00946 { 00947 //-------------------------------------------// 00948 // Get each nodes previous and next pointers // 00949 //-------------------------------------------// 00950 ItemNode *pPrevItr1Node = pItr1Node->GetPrev(); 00951 ItemNode *pNextItr1Node = pItr1Node->GetNext(); 00952 ItemNode *pPrevItr2Node = pItr2Node->GetPrev(); 00953 ItemNode *pNextItr2Node = pItr2Node->GetNext(); 00954 00955 //-------------------------------------// 00956 // Swap the previous and next pointers // 00957 //-------------------------------------// 00958 pItr1Node->SetPrev( pPrevItr2Node ); 00959 pItr1Node->SetNext( pNextItr2Node ); 00960 pItr2Node->SetPrev( pPrevItr1Node ); 00961 pItr2Node->SetNext( pNextItr1Node ); 00962 00963 //----------------------------------------------// 00964 // Add special case handling for adjacent nodes // 00965 //----------------------------------------------// 00966 if( pItr1Node->GetPrev() == pItr1Node ) 00967 { 00968 pItr1Node->SetPrev( pItr2Node ); 00969 00970 } // end if( pItr1Node->GetPrev() == pItr1Node ) 00971 00972 if( pItr1Node->GetNext() == pItr1Node ) 00973 { 00974 pItr1Node->SetNext( pItr2Node ); 00975 00976 } // end if( pItr1Node->GetNext() == pItr1Node ) 00977 00978 if( pItr2Node->GetPrev() == pItr2Node ) 00979 { 00980 pItr2Node->SetPrev( pItr1Node ); 00981 00982 } // end if( pItr2Node->GetPrev() == pItr2Node ) 00983 00984 if( pItr2Node->GetNext() == pItr2Node ) 00985 { 00986 pItr2Node->SetNext( pItr1Node ); 00987 00988 } // end if( pItr2Node->GetNext() == pItr2Node ) 00989 00990 //----------------------------------------------// 00991 // Get the updated previous and next pointers // 00992 //----------------------------------------------// 00993 pPrevItr1Node = pItr1Node->GetPrev(); 00994 pNextItr1Node = pItr1Node->GetNext(); 00995 pPrevItr2Node = pItr2Node->GetPrev(); 00996 pNextItr2Node = pItr2Node->GetNext(); 00997 00998 //----------------------------------------------------------------// 00999 // Fix the previous and next nodes pointers to the swapped nodes // 01000 //----------------------------------------------------------------// 01001 if( NULL != pPrevItr1Node ) 01002 { 01003 pPrevItr1Node->SetNext( pItr1Node ); 01004 01005 } // end if( NULL != pPrevItr1Node ) 01006 01007 if( NULL != pNextItr1Node ) 01008 { 01009 pNextItr1Node->SetPrev( pItr1Node ); 01010 01011 } // end if( NULL != pNextItr1Node ) 01012 01013 if( NULL != pPrevItr2Node ) 01014 { 01015 pPrevItr2Node->SetNext( pItr2Node ); 01016 01017 } // end if( NULL != pPrevItr2Node ) 01018 01019 if( NULL != pNextItr2Node ) 01020 { 01021 pNextItr2Node->SetPrev( pItr2Node ); 01022 01023 } // end if( NULL != pNextItr2Node ) 01024 01025 //-------------------------------// 01026 // Handle head and tail pointers // 01027 //-------------------------------// 01028 if( NULL == pItr1Node->GetPrev() ) 01029 { 01030 m_pHead = pItr1Node; 01031 01032 } // end if( NULL == pItr1Node->GetPrev() ) 01033 01034 if( NULL == pItr1Node->GetNext() ) 01035 { 01036 m_pTail = pItr1Node; 01037 01038 } // end if( NULL == pItr1Node->GetNext() ) 01039 01040 if( NULL == pItr2Node->GetPrev() ) 01041 { 01042 m_pHead = pItr2Node; 01043 01044 } // end if( NULL == pItr2Node->GetPrev() ) 01045 01046 if( NULL == pItr2Node->GetNext() ) 01047 { 01048 m_pTail = pItr2Node; 01049 01050 } // end if( NULL == pItr2Node->GetNext() ) 01051 01052 } // end if ( valid items pointers ) 01053 01054 } // end if ( valid iterators ) 01055 01056 }; // End of swap 01057 01058 //-------------------------------------------------------------------------- 01065 //-------------------------------------------------------------------------- 01066 iterator erase( iterator &itr ) 01067 { 01068 ItemNode *pNextNode = removeItemNode(itr.m_pItemNode); 01069 iterator nextItr(this,pNextNode); 01070 return nextItr; 01071 }; // End of erase 01072 01073 //-------------------------------------------------------------------------- 01074 // Iterators 01075 //-------------------------------------------------------------------------- 01076 01077 //-------------------------------------------------------------------------- 01083 //-------------------------------------------------------------------------- 01084 iterator begin() 01085 { 01086 iterator itr(this,m_pHead); 01087 return itr; 01088 }; // End of begin 01089 01090 //-------------------------------------------------------------------------- 01096 //-------------------------------------------------------------------------- 01097 const_iterator begin() const 01098 { 01099 const_iterator itr(this,m_pHead); 01100 return itr; 01101 }; // End of begin 01102 01103 //-------------------------------------------------------------------------- 01109 //-------------------------------------------------------------------------- 01110 iterator end() 01111 { 01112 iterator itr(this,NULL); 01113 return itr; 01114 }; // End of end 01115 01116 //-------------------------------------------------------------------------- 01122 //-------------------------------------------------------------------------- 01123 const_iterator end() const 01124 { 01125 const_iterator itr(this,NULL); 01126 return itr; 01127 }; // End of end 01128 01129 //-------------------------------------------------------------------------- 01130 // Indexers 01131 //-------------------------------------------------------------------------- 01132 01133 //-------------------------------------------------------------------------- 01140 //-------------------------------------------------------------------------- 01141 Type& operator[] ( int nIndex ) 01142 { 01143 assert(nIndex<m_nNumItems); 01144 int i; 01145 01146 ItemNode *pNode = m_pHead; 01147 for (i=0;i<nIndex;i++) 01148 { 01149 assert(pNode!=NULL); 01150 pNode = pNode->GetNext(); 01151 } // End for 01152 01153 assert(pNode!=NULL); 01154 return pNode->GetData(); 01155 }; // End of operator 01156 01157 //-------------------------------------------------------------------------- 01164 //-------------------------------------------------------------------------- 01165 const Type& operator[] ( int nIndex ) const 01166 { 01167 assert(nIndex<m_nNumItems); 01168 int i; 01169 01170 ItemNode *pNode = m_pHead; 01171 for (i=0;i<nIndex;i++) 01172 { 01173 assert(pNode!=NULL); 01174 pNode = pNode->GetNext(); 01175 } // End for 01176 01177 assert(pNode!=NULL); 01178 return pNode->GetData(); 01179 }; // End of operator 01180 01181 //-------------------------------------------------------------------------- 01188 //-------------------------------------------------------------------------- 01189 void operator = ( const RmLinkedList<Type> &src ) 01190 { 01191 ItemNode *pNode = src.m_pHead; 01192 while (pNode!=NULL) 01193 { 01194 push_back(pNode->GetData()); 01195 pNode = pNode->GetNext(); 01196 } // End while 01197 }; // End of operator = 01198 01199 //-------------------------------------------------------------------------- 01208 //-------------------------------------------------------------------------- 01209 iterator find( Type item ) 01210 { 01211 iterator itr = begin(); 01212 while (itr!=end()) 01213 { 01214 Type &data = (*itr); 01215 if (data==item) 01216 return itr; 01217 01218 ++itr; 01219 } // End while 01220 01221 return end(); 01222 } // End find 01223 01224 //-------------------------------------------------------------------------- 01233 //-------------------------------------------------------------------------- 01234 const_iterator find( Type item ) const 01235 { 01236 const_iterator itr = begin(); 01237 while (itr!=end()) 01238 { 01239 const Type &data = (*itr); 01240 if (data==item) 01241 return itr; 01242 01243 ++itr; 01244 } // End while 01245 01246 return end(); 01247 } // End find 01248 01249 01250 private : 01251 int m_nNumItems; 01252 ItemNode *m_pHead; 01253 ItemNode *m_pTail; 01254 01255 //-------------------------------------------------------------------------- 01262 //-------------------------------------------------------------------------- 01263 ItemNode* removeItemNode( ItemNode *pItemNode ) 01264 { 01265 assert(pItemNode!=NULL); 01266 assert(m_nNumItems>0); 01267 01268 assert(pItemNode->GetParent()==this); 01269 01270 ItemNode *pPrev = pItemNode->GetPrev(); 01271 ItemNode *pNext = pItemNode->GetNext(); 01272 01273 // Link prev to next 01274 if (pPrev!=NULL) 01275 pPrev->SetNext(pNext); 01276 01277 if (pNext!=NULL) 01278 pNext->SetPrev(pPrev); 01279 01280 // If removing start/end of node 01281 bool bHead = (m_pHead == pItemNode) ? true : false; 01282 bool bTail = (m_pTail == pItemNode) ? true : false; 01283 01284 m_nNumItems--; 01285 01286 // Now free node 01287 delete pItemNode; 01288 01289 if( bHead ) 01290 { 01291 m_pHead = pNext; 01292 01293 } // end if ( bHead ) 01294 01295 if( bTail ) 01296 { 01297 m_pTail = pPrev; 01298 01299 } // end if ( bTail ) 01300 01301 return pNext; 01302 01303 } // End of removeItemNode 01304 01305 }; // End of RmLinkedList 01306 01307 01308 #endif
1.3.6