CLAM-Development
1.1
|
00001 /* 00002 * Copyright (c) 2001-2004 MUSIC TECHNOLOGY GROUP (MTG) 00003 * UNIVERSITAT POMPEU FABRA 00004 * 00005 * 00006 * This program is free software; you can redistribute it and/or modify 00007 * it under the terms of the GNU General Public License as published by 00008 * the Free Software Foundation; either version 2 of the License, or 00009 * (at your option) any later version. 00010 * 00011 * This program is distributed in the hope that it will be useful, 00012 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 * GNU General Public License for more details. 00015 * 00016 * You should have received a copy of the GNU General Public License 00017 * along with this program; if not, write to the Free Software 00018 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 00019 * 00020 */ 00021 00022 #ifndef _List_ 00023 #define _List_ 00024 00025 #include "DataTypes.hxx" 00026 #include "Err.hxx" 00027 #include "Assert.hxx" 00028 #include "Component.hxx" 00029 #include "TypeInfo.hxx" 00030 00031 #include "XMLAdapter.hxx" 00032 #include "XMLComponentAdapter.hxx" 00033 00034 namespace CLAM { 00035 00036 template <class T2> void StoreMemberOn(T2 &item, Storage & storage); 00037 00038 template <class T> class List:public Component 00039 { 00040 00041 class Node 00042 { 00043 friend class List<T>; 00044 private: 00045 T mValue; 00046 Node *mpNext,*mpPrevious; 00047 public: 00048 Node(const T& value) 00049 { 00050 mpNext=mpPrevious=0; 00051 mValue=value; 00052 } 00053 const T& Value(void) const{ return mValue; } 00054 T& Value(void) { return mValue; } 00055 Node *Next(void) { return mpNext; } 00056 Node *Previous(void) { return mpPrevious; } 00057 }; 00058 00059 00060 00061 public: 00062 const char * GetClassName() const {return 0;} 00063 00064 List() 00065 { 00066 mpFirst = mpLast = mpCurrent = 0; 00067 mCurrentIndex = 0; 00068 mSize = 0; 00069 00070 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00071 00072 } 00073 00074 List & operator = (const List& src) 00075 { 00076 int i; 00077 if (mSize>0) 00078 { 00079 DoLast(); 00080 while(mpCurrent) 00081 { 00082 DeleteElem(mSize-1); 00083 } 00084 00085 } 00086 for(i=0;i<src.Size();i++) 00087 { 00088 AddElem(src[i]); 00089 } 00090 return *this; 00091 } 00092 00093 List(const List& src) 00094 { 00095 mpFirst = mpLast = mpCurrent = 0; 00096 mCurrentIndex = 0; 00097 mSize = 0; 00098 *this=src; 00099 } 00100 00101 ~List() 00102 { 00103 mpCurrent = mpFirst; 00104 while (mpCurrent) 00105 { 00106 Node* next = mpCurrent->mpNext; 00107 delete mpCurrent; 00108 mpCurrent = next; 00109 } 00110 } 00111 00112 void AddElem(const T& value); 00113 void InsertElem(const T& value,TIndex i); 00114 void InsertElem(const T& value); 00115 void DeleteElem(TIndex i); 00116 void DeleteElem(); 00117 void Extract(T& value,TIndex i); 00118 void Extract(T& value); 00119 TSize Size() const 00120 { 00121 return mSize; 00122 } 00123 bool IsEmpty() const 00124 { 00125 return mSize==0; 00126 } 00127 const T& operator [] (TIndex i) const; 00128 T& operator [] (TIndex i); 00129 const T& Current() const 00130 { 00131 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00132 CLAM_ASSERT(mpCurrent,"Trying to access non-exixting current pointer"); 00133 return mpCurrent->Value(); 00134 } 00135 const T& First() const 00136 { 00137 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00138 CLAM_ASSERT(mSize>=0,"Trying to access empty list"); 00139 return mpFirst->Value(); 00140 } 00141 const T& Last() const 00142 { 00143 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00144 CLAM_ASSERT(mSize>=0,"Trying to access empty list"); 00145 return mpLast->Value(); 00146 } 00147 T& Current() 00148 { 00149 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00150 CLAM_ASSERT(mpCurrent,"Trying to access non-exixting current pointer"); 00151 return mpCurrent->Value(); 00152 } 00153 T& First() 00154 { 00155 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00156 CLAM_ASSERT(mSize>=0,"Trying to access empty list"); 00157 return mpFirst->Value(); 00158 } 00159 T& Last() 00160 { 00161 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00162 CLAM_ASSERT(mSize>=0,"Trying to access empty list"); 00163 return mpLast->Value(); 00164 } 00165 void DoFirst() 00166 { 00167 mpCurrent=mpFirst; 00168 mCurrentIndex=0; 00169 } 00170 void DoLast() 00171 { 00172 mpCurrent=mpLast; 00173 mCurrentIndex=mSize-1; 00174 } 00175 void DoNext() 00176 { 00177 CLAM_ASSERT(mCurrentIndex<mSize-1,"Current element is already last one"); 00178 mpCurrent=mpCurrent->mpNext; 00179 mCurrentIndex++; 00180 } 00181 void DoPrevious() 00182 { 00183 CLAM_ASSERT(mCurrentIndex>0,"Current element is already first one"); 00184 mpCurrent=mpCurrent->mpPrevious; 00185 mCurrentIndex--; 00186 } 00187 00188 bool IsLast() 00189 { 00190 return (mpCurrent==mpLast); 00191 } 00192 00193 bool Done(void) 00194 { 00195 return mCurrentIndex==mSize; 00196 } 00197 00198 bool IsFirst() 00199 { 00200 return (mpCurrent==mpFirst); 00201 } 00202 00203 int CurrentIndex() const{return mCurrentIndex;} 00204 bool FulfillsInvariant (void) const; 00205 00206 private: 00207 00208 Node* GetNodeAt(TIndex i); 00209 void LinkNode(Node* pA,Node* pB); 00210 void AddNode(Node* pA); 00211 void InsertNode(Node* pA); 00212 void InsertNode(Node* pWhere, Node* pWhat); 00213 void DeleteNode(); 00214 void DeleteNode(Node* pNode); 00215 00216 Node *mpFirst,*mpLast; 00217 mutable Node* mpCurrent; 00218 mutable TIndex mCurrentIndex; 00219 TSize mSize; 00220 00221 00222 public: 00223 00224 void StoreOn(Storage & storage) const 00225 { 00226 00227 if(mSize<=0) return; 00228 // TODO: think if it's the best way to check if there is data. 00229 typedef typename TypeInfo<T>::StorableAsLeaf IsStorableAsLeaf; 00230 for (int i=0; i<mSize; i++) 00231 { 00232 StoreMemberOn( 00233 (IsStorableAsLeaf*)0, 00234 &(*this)[i], 00235 storage 00236 ); 00237 } 00238 } 00239 00240 void LoadFrom(Storage & storage) 00241 { 00242 typedef typename TypeInfo<T>::StorableAsLeaf IsStorableAsLeaf; 00243 do AddElem(T()); 00244 while (LoadMemberFrom( (IsStorableAsLeaf *)0, &(Last()), storage)); 00245 DoLast(); 00246 DeleteNode(); 00247 } 00248 private: 00249 void StoreMemberOn(StaticTrue* asLeave, const void * item, Storage & storage) const { 00250 XMLAdapter<T> adapter(*(T*)item); 00251 storage.Store(adapter); 00252 } 00253 void StoreMemberOn(StaticFalse* asLeave, const Component * item, Storage & storage) const { 00254 const char* className = item->GetClassName(); 00255 const char* label = className? className : "Element"; 00256 XMLComponentAdapter adapter(*item, label, true); 00257 storage.Store(adapter); 00258 } 00259 bool StoreMemberOn(StaticFalse* asLeave, const void * item, Storage & storage) const { 00260 CLAM_ASSERT(false, "Trying to Store an object that is not neither a streamable nor a Component"); 00261 return false; 00262 } 00263 bool LoadMemberFrom(StaticTrue* asLeave, void * item, Storage & storage) { 00264 XMLAdapter<T> adapter(*(T*)item); 00265 return storage.Load(adapter); 00266 } 00267 bool LoadMemberFrom(StaticFalse* asLeave, Component * item, Storage & storage) { 00268 const char* className = item->GetClassName(); 00269 const char* label = className? className : "Element"; 00270 XMLComponentAdapter adapter(*item, label, true); 00271 return storage.Load(adapter); 00272 } 00273 bool LoadMemberFrom(StaticFalse* asLeave, void * item, Storage & storage) { 00274 CLAM_ASSERT(false, "Trying to Load an object that is not neither a streamable nor a Component"); 00275 return false; 00276 } 00277 }; 00278 00279 00280 00281 00282 template <class T> inline void List<T>::AddElem(const T& value) 00283 { 00284 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00285 00286 AddNode(new Node(value)); 00287 mCurrentIndex=mSize-1; 00288 mpCurrent=mpLast; 00289 00290 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00291 00292 } 00293 00294 template <class T> inline void List<T>::DeleteElem(TIndex i) 00295 { 00296 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00297 CLAM_ASSERT(i<mSize,"Trying to access non-existing element"); 00298 mCurrentIndex=i; 00299 mpCurrent=GetNodeAt(i); 00300 DeleteNode(mpCurrent); 00301 00302 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00303 00304 } 00305 00306 template <class T> inline void List<T>::DeleteNode() 00307 { 00308 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00309 00310 DeleteNode(mpCurrent); 00311 00312 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00313 00314 } 00315 00316 template <class T> inline void List<T>::DeleteNode(Node* pNode) 00317 { 00318 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00319 00320 if(pNode!=mpFirst) 00321 { 00322 mpCurrent=pNode->Previous(); 00323 mCurrentIndex--; 00324 } 00325 else 00326 { 00327 mpCurrent=pNode->Next(); 00328 mCurrentIndex=0; 00329 } 00330 if(pNode!=mpLast&&pNode!=mpFirst) 00331 { 00332 pNode->mpPrevious->mpNext=pNode->Next(); 00333 pNode->mpNext->mpPrevious=pNode->Previous(); 00334 } 00335 else 00336 { 00337 if(pNode==mpFirst) 00338 { 00339 mpFirst=pNode->mpNext; 00340 if(mpFirst) 00341 mpFirst->mpPrevious=0;; 00342 } 00343 if(pNode==mpLast) 00344 { 00345 mpLast=pNode->mpPrevious; 00346 if(mpLast) 00347 mpLast->mpNext=0; 00348 } 00349 } 00350 delete pNode; 00351 pNode=0; 00352 mSize--; 00353 if(mSize==0) mCurrentIndex=-1; 00354 00355 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00356 00357 } 00358 00359 template <class T> inline void List<T>::InsertElem(const T& value,TIndex i) 00360 { 00361 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00362 CLAM_ASSERT(i<=mSize,"Trying to insert out of bounds"); 00363 00364 InsertNode(GetNodeAt(i), new Node(value)); 00365 00366 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00367 00368 } 00369 00370 00371 template <class T> inline void List<T>::InsertNode(Node* pNewNode) 00372 { 00373 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00374 00375 InsertNode(mpCurrent,pNewNode); 00376 00377 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00378 00379 } 00380 00381 template <class T> inline void List<T>::InsertNode(Node* pWhere,Node* pNewNode) 00382 { 00383 CLAM_ASSERT(pNewNode,"Not a valid Nodeent to insert"); 00384 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00385 00386 if(pWhere!=mpFirst) pWhere->mpPrevious->mpNext=pNewNode; 00387 pNewNode->mpPrevious=pWhere->mpPrevious; 00388 pWhere->mpPrevious=pNewNode; 00389 pNewNode->mpNext=pWhere; 00390 mpCurrent=pNewNode; 00391 if(pWhere==mpFirst) mpFirst=pNewNode; 00392 mSize++; 00393 00394 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00395 00396 } 00397 00398 template <class T> inline void List<T>::Extract(T& value,TIndex i) 00399 { 00400 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00401 CLAM_ASSERT(i<mSize,"Trying to access non-existing element"); 00402 00403 value=(*this)[i]; 00404 DeleteElem(i); 00405 00406 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00407 00408 } 00409 00410 template <class T> inline void List<T>::Extract(T& value) 00411 { 00412 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00413 00414 Extract(value,mCurrentIndex); 00415 00416 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00417 00418 } 00419 00420 template <class T> inline void List<T>::LinkNode(Node* pA,Node* pB) 00421 { 00422 pA->mpNext = pB; 00423 pB->mpPrevious = pA; 00424 } 00425 00426 template <class T> inline void List<T>::AddNode(Node* pNode) 00427 { 00428 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00429 00430 if (mpLast) LinkNode(mpLast,pNode); 00431 else mpFirst = mpCurrent = pNode; 00432 mpLast = pNode; 00433 mpCurrent=mpLast; 00434 mSize++; 00435 mCurrentIndex=mSize-1; 00436 00437 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00438 00439 } 00440 00441 00442 00443 00444 template <class T> inline const T& List<T>::operator [] (TIndex i) const{ 00445 /* this function is optimized, by starting searching from the current 00446 index, or from the beginning or the end, when that's closer. 00447 */ 00448 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00449 00450 if (i<=0) 00451 { 00452 mCurrentIndex=0; 00453 mpCurrent=mpFirst; 00454 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00455 00456 return ((Node*)mpFirst)->mValue; 00457 } 00458 if (i>=mSize-1) 00459 { 00460 mCurrentIndex=mSize-1; 00461 mpCurrent=mpLast; 00462 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00463 00464 return ((Node*)mpLast)->mValue; 00465 } 00466 if (mCurrentIndex<i) { 00467 if (i<((mCurrentIndex+mSize)>>1)) { 00468 do { 00469 mCurrentIndex++; 00470 mpCurrent = mpCurrent->Next(); 00471 } while (mCurrentIndex<i); 00472 } else { 00473 mCurrentIndex = mSize-1; 00474 mpCurrent = mpLast; 00475 while (mCurrentIndex>i) { 00476 mCurrentIndex--; 00477 mpCurrent = mpCurrent->Previous(); 00478 } 00479 } 00480 }else if (mCurrentIndex>i) 00481 { 00482 if (i>(mCurrentIndex>>1)) { 00483 do { 00484 mCurrentIndex--; 00485 mpCurrent = mpCurrent->Previous(); 00486 } while (mCurrentIndex>i); 00487 } else { 00488 mCurrentIndex=0; 00489 mpCurrent = mpFirst; 00490 while (mCurrentIndex<i) { 00491 mCurrentIndex++; 00492 mpCurrent = mpCurrent->Next(); 00493 } 00494 } 00495 } 00496 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00497 00498 return ((Node*)mpCurrent)->mValue; 00499 } 00500 00501 template <class T> inline T& List<T>::operator [] (TIndex i) { 00502 /* this function is optimized, by starting searching from the current 00503 index, or from the beginning or the end, when that's closer. 00504 */ 00505 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00506 00507 if (i<=0) 00508 { 00509 mCurrentIndex=0; 00510 mpCurrent=mpFirst; 00511 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00512 00513 return ((Node*)mpFirst)->mValue; 00514 } 00515 if (i>=mSize-1) 00516 { 00517 mCurrentIndex=mSize-1; 00518 mpCurrent=mpLast; 00519 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00520 00521 return ((Node*)mpLast)->mValue; 00522 } 00523 if (mCurrentIndex<i) { 00524 if (i<((mCurrentIndex+mSize)>>1)) { 00525 do { 00526 mCurrentIndex++; 00527 mpCurrent = mpCurrent->Next(); 00528 } while (mCurrentIndex<i); 00529 } else { 00530 mCurrentIndex = mSize-1; 00531 mpCurrent = mpLast; 00532 while (mCurrentIndex>i) { 00533 mCurrentIndex--; 00534 mpCurrent = mpCurrent->Previous(); 00535 } 00536 } 00537 }else if (mCurrentIndex>i) 00538 { 00539 if (i>(mCurrentIndex>>1)) { 00540 do { 00541 mCurrentIndex--; 00542 mpCurrent = mpCurrent->Previous(); 00543 } while (mCurrentIndex>i); 00544 } else { 00545 mCurrentIndex=0; 00546 mpCurrent = mpFirst; 00547 while (mCurrentIndex<i) { 00548 mCurrentIndex++; 00549 mpCurrent = mpCurrent->Next(); 00550 } 00551 } 00552 } 00553 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00554 00555 return ((Node*)mpCurrent)->mValue; 00556 } 00557 00558 template <class T> inline typename List<T>::Node* List<T>::GetNodeAt(TIndex i){ 00559 /* this function is optimized, by starting searching from the current 00560 index, or from the beginning or the end, when that's closer. 00561 */ 00562 if (i<=0) 00563 { 00564 mpCurrent=mpFirst; 00565 mCurrentIndex=0; 00566 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00567 00568 return mpFirst; 00569 } 00570 if (i>=mSize-1) 00571 { 00572 mpCurrent=mpLast; 00573 mCurrentIndex=mSize-1; 00574 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00575 00576 return mpLast; 00577 } 00578 if (mCurrentIndex<i) { 00579 if (i<((mCurrentIndex+mSize)>>1)) { 00580 do { 00581 mCurrentIndex++; 00582 mpCurrent = mpCurrent->Next(); 00583 } while (mCurrentIndex<i); 00584 } else { 00585 mCurrentIndex = mSize-1; 00586 mpCurrent = mpLast; 00587 while (mCurrentIndex>i) { 00588 mCurrentIndex--; 00589 mpCurrent = mpCurrent->Previous(); 00590 } 00591 } 00592 }else if (mCurrentIndex>i) 00593 { 00594 if (i>(mCurrentIndex>>1)) { 00595 do { 00596 mCurrentIndex--; 00597 mpCurrent = mpCurrent->Previous(); 00598 } while (mCurrentIndex>i); 00599 } else { 00600 mCurrentIndex=0; 00601 mpCurrent = mpFirst; 00602 while (mCurrentIndex<i) { 00603 mCurrentIndex++; 00604 mpCurrent = mpCurrent->Next(); 00605 } 00606 } 00607 } 00608 CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant"); 00609 00610 return mpCurrent; 00611 } 00612 00613 template <class T> inline bool List<T>::FulfillsInvariant(void) const 00614 { 00615 int i; 00616 if(mSize>0) 00617 { 00618 if (mpFirst->mpPrevious || mpLast->mpNext || 00619 mSize<0 || (mCurrentIndex<0) || (mpCurrent==0) 00620 ) 00621 { 00622 return false; 00623 } 00624 Node* pTmp=mpCurrent; 00625 for(i=mCurrentIndex;i>=0;i--) 00626 { 00627 CLAM_ASSERT(pTmp->mpPrevious || i==0, "Current pointer not consistent"); 00628 pTmp=pTmp->mpPrevious; 00629 } 00630 } 00631 return true; 00632 } 00633 00634 }; 00635 00636 #endif 00637