CLAM-Development  1.4.0
List.hxx
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2001-2004 MUSIC TECHNOLOGY GROUP (MTG)
3  * UNIVERSITAT POMPEU FABRA
4  *
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19  *
20  */
21 
22 #ifndef _List_
23 #define _List_
24 
25 #include "DataTypes.hxx"
26 #include "Err.hxx"
27 #include "Assert.hxx"
28 #include "Component.hxx"
29 #include "TypeInfo.hxx"
30 
31 #include "XMLAdapter.hxx"
32 #include "XMLComponentAdapter.hxx"
33 
34 namespace CLAM {
35 
36 template <class T2> void StoreMemberOn(T2 &item, Storage & storage);
37 
38 template <class T> class List:public Component
39 {
40 
41  class Node
42  {
43  friend class List<T>;
44  private:
45  T mValue;
46  Node *mpNext,*mpPrevious;
47  public:
48  Node(const T& value)
49  {
50  mpNext=mpPrevious=0;
51  mValue=value;
52  }
53  const T& Value(void) const{ return mValue; }
54  T& Value(void) { return mValue; }
55  Node *Next(void) { return mpNext; }
56  Node *Previous(void) { return mpPrevious; }
57  };
58 
59 
60 
61 public:
62  const char * GetClassName() const {return 0;}
63 
64  List()
65  {
66  mpFirst = mpLast = mpCurrent = 0;
67  mCurrentIndex = 0;
68  mSize = 0;
69 
70  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
71 
72  }
73 
74  List & operator = (const List& src)
75  {
76  int i;
77  if (mSize>0)
78  {
79  DoLast();
80  while(mpCurrent)
81  {
82  DeleteElem(mSize-1);
83  }
84 
85  }
86  for(i=0;i<src.Size();i++)
87  {
88  AddElem(src[i]);
89  }
90  return *this;
91  }
92 
93  List(const List& src)
94  {
95  mpFirst = mpLast = mpCurrent = 0;
96  mCurrentIndex = 0;
97  mSize = 0;
98  *this=src;
99  }
100 
102  {
103  mpCurrent = mpFirst;
104  while (mpCurrent)
105  {
106  Node* next = mpCurrent->mpNext;
107  delete mpCurrent;
108  mpCurrent = next;
109  }
110  }
111 
112  void AddElem(const T& value);
113  void InsertElem(const T& value,TIndex i);
114  void InsertElem(const T& value);
115  void DeleteElem(TIndex i);
116  void DeleteElem();
117  void Extract(T& value,TIndex i);
118  void Extract(T& value);
119  TSize Size() const
120  {
121  return mSize;
122  }
123  bool IsEmpty() const
124  {
125  return mSize==0;
126  }
127  const T& operator [] (TIndex i) const;
128  T& operator [] (TIndex i);
129  const T& Current() const
130  {
131  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
132  CLAM_ASSERT(mpCurrent,"Trying to access non-exixting current pointer");
133  return mpCurrent->Value();
134  }
135  const T& First() const
136  {
137  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
138  CLAM_ASSERT(mSize>=0,"Trying to access empty list");
139  return mpFirst->Value();
140  }
141  const T& Last() const
142  {
143  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
144  CLAM_ASSERT(mSize>=0,"Trying to access empty list");
145  return mpLast->Value();
146  }
147  T& Current()
148  {
149  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
150  CLAM_ASSERT(mpCurrent,"Trying to access non-exixting current pointer");
151  return mpCurrent->Value();
152  }
153  T& First()
154  {
155  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
156  CLAM_ASSERT(mSize>=0,"Trying to access empty list");
157  return mpFirst->Value();
158  }
159  T& Last()
160  {
161  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
162  CLAM_ASSERT(mSize>=0,"Trying to access empty list");
163  return mpLast->Value();
164  }
165  void DoFirst()
166  {
167  mpCurrent=mpFirst;
168  mCurrentIndex=0;
169  }
170  void DoLast()
171  {
172  mpCurrent=mpLast;
173  mCurrentIndex=mSize-1;
174  }
175  void DoNext()
176  {
177  CLAM_ASSERT(mCurrentIndex<mSize-1,"Current element is already last one");
178  mpCurrent=mpCurrent->mpNext;
179  mCurrentIndex++;
180  }
181  void DoPrevious()
182  {
183  CLAM_ASSERT(mCurrentIndex>0,"Current element is already first one");
184  mpCurrent=mpCurrent->mpPrevious;
185  mCurrentIndex--;
186  }
187 
188  bool IsLast()
189  {
190  return (mpCurrent==mpLast);
191  }
192 
193  bool Done(void)
194  {
195  return mCurrentIndex==mSize;
196  }
197 
198  bool IsFirst()
199  {
200  return (mpCurrent==mpFirst);
201  }
202 
203  int CurrentIndex() const{return mCurrentIndex;}
204  bool FulfillsInvariant (void) const;
205 
206 private:
207 
208  Node* GetNodeAt(TIndex i);
209  void LinkNode(Node* pA,Node* pB);
210  void AddNode(Node* pA);
211  void InsertNode(Node* pA);
212  void InsertNode(Node* pWhere, Node* pWhat);
213  void DeleteNode();
214  void DeleteNode(Node* pNode);
215 
216  Node *mpFirst,*mpLast;
217  mutable Node* mpCurrent;
218  mutable TIndex mCurrentIndex;
219  TSize mSize;
220 
221 
222 public:
223 
224  void StoreOn(Storage & storage) const
225  {
226 
227  if(mSize<=0) return;
228  // TODO: think if it's the best way to check if there is data.
229  typedef typename TypeInfo<T>::StorableAsLeaf IsStorableAsLeaf;
230  for (int i=0; i<mSize; i++)
231  {
233  (IsStorableAsLeaf*)0,
234  &(*this)[i],
235  storage
236  );
237  }
238  }
239 
240  void LoadFrom(Storage & storage)
241  {
242  typedef typename TypeInfo<T>::StorableAsLeaf IsStorableAsLeaf;
243  do AddElem(T());
244  while (LoadMemberFrom( (IsStorableAsLeaf *)0, &(Last()), storage));
245  DoLast();
246  DeleteNode();
247  }
248 private:
249  void StoreMemberOn(StaticTrue* asLeave, const void * item, Storage & storage) const {
250  XMLAdapter<T> adapter(*(T*)item);
251  storage.Store(adapter);
252  }
253  void StoreMemberOn(StaticFalse* asLeave, const Component * item, Storage & storage) const {
254  const char* className = item->GetClassName();
255  const char* label = className? className : "Element";
256  XMLComponentAdapter adapter(*item, label, true);
257  storage.Store(adapter);
258  }
259  bool StoreMemberOn(StaticFalse* asLeave, const void * item, Storage & storage) const {
260  CLAM_ASSERT(false, "Trying to Store an object that is not neither a streamable nor a Component");
261  return false;
262  }
263  bool LoadMemberFrom(StaticTrue* asLeave, void * item, Storage & storage) {
264  XMLAdapter<T> adapter(*(T*)item);
265  return storage.Load(adapter);
266  }
267  bool LoadMemberFrom(StaticFalse* asLeave, Component * item, Storage & storage) {
268  const char* className = item->GetClassName();
269  const char* label = className? className : "Element";
270  XMLComponentAdapter adapter(*item, label, true);
271  return storage.Load(adapter);
272  }
273  bool LoadMemberFrom(StaticFalse* asLeave, void * item, Storage & storage) {
274  CLAM_ASSERT(false, "Trying to Load an object that is not neither a streamable nor a Component");
275  return false;
276  }
277 };
278 
279 
280 
281 
282 template <class T> inline void List<T>::AddElem(const T& value)
283 {
284  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
285 
286  AddNode(new Node(value));
287  mCurrentIndex=mSize-1;
288  mpCurrent=mpLast;
289 
290  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
291 
292 }
293 
294 template <class T> inline void List<T>::DeleteElem(TIndex i)
295 {
296  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
297  CLAM_ASSERT(i<mSize,"Trying to access non-existing element");
298  mCurrentIndex=i;
299  mpCurrent=GetNodeAt(i);
300  DeleteNode(mpCurrent);
301 
302  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
303 
304 }
305 
306 template <class T> inline void List<T>::DeleteNode()
307 {
308  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
309 
310  DeleteNode(mpCurrent);
311 
312  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
313 
314 }
315 
316 template <class T> inline void List<T>::DeleteNode(Node* pNode)
317 {
318  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
319 
320  if(pNode!=mpFirst)
321  {
322  mpCurrent=pNode->Previous();
323  mCurrentIndex--;
324  }
325  else
326  {
327  mpCurrent=pNode->Next();
328  mCurrentIndex=0;
329  }
330  if(pNode!=mpLast&&pNode!=mpFirst)
331  {
332  pNode->mpPrevious->mpNext=pNode->Next();
333  pNode->mpNext->mpPrevious=pNode->Previous();
334  }
335  else
336  {
337  if(pNode==mpFirst)
338  {
339  mpFirst=pNode->mpNext;
340  if(mpFirst)
341  mpFirst->mpPrevious=0;;
342  }
343  if(pNode==mpLast)
344  {
345  mpLast=pNode->mpPrevious;
346  if(mpLast)
347  mpLast->mpNext=0;
348  }
349  }
350  delete pNode;
351  pNode=0;
352  mSize--;
353  if(mSize==0) mCurrentIndex=-1;
354 
355  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
356 
357 }
358 
359 template <class T> inline void List<T>::InsertElem(const T& value,TIndex i)
360 {
361  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
362  CLAM_ASSERT(i<=mSize,"Trying to insert out of bounds");
363 
364  InsertNode(GetNodeAt(i), new Node(value));
365 
366  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
367 
368 }
369 
370 
371 template <class T> inline void List<T>::InsertNode(Node* pNewNode)
372 {
373  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
374 
375  InsertNode(mpCurrent,pNewNode);
376 
377  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
378 
379 }
380 
381 template <class T> inline void List<T>::InsertNode(Node* pWhere,Node* pNewNode)
382 {
383  CLAM_ASSERT(pNewNode,"Not a valid Nodeent to insert");
384  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
385 
386  if(pWhere!=mpFirst) pWhere->mpPrevious->mpNext=pNewNode;
387  pNewNode->mpPrevious=pWhere->mpPrevious;
388  pWhere->mpPrevious=pNewNode;
389  pNewNode->mpNext=pWhere;
390  mpCurrent=pNewNode;
391  if(pWhere==mpFirst) mpFirst=pNewNode;
392  mSize++;
393 
394  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
395 
396 }
397 
398 template <class T> inline void List<T>::Extract(T& value,TIndex i)
399 {
400  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
401  CLAM_ASSERT(i<mSize,"Trying to access non-existing element");
402 
403  value=(*this)[i];
404  DeleteElem(i);
405 
406  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
407 
408 }
409 
410 template <class T> inline void List<T>::Extract(T& value)
411 {
412  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
413 
414  Extract(value,mCurrentIndex);
415 
416  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
417 
418 }
419 
420 template <class T> inline void List<T>::LinkNode(Node* pA,Node* pB)
421 {
422  pA->mpNext = pB;
423  pB->mpPrevious = pA;
424 }
425 
426 template <class T> inline void List<T>::AddNode(Node* pNode)
427 {
428  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
429 
430  if (mpLast) LinkNode(mpLast,pNode);
431  else mpFirst = mpCurrent = pNode;
432  mpLast = pNode;
433  mpCurrent=mpLast;
434  mSize++;
435  mCurrentIndex=mSize-1;
436 
437  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
438 
439 }
440 
441 
442 
443 
444 template <class T> inline const T& List<T>::operator [] (TIndex i) const{
445  /* this function is optimized, by starting searching from the current
446  index, or from the beginning or the end, when that's closer.
447  */
448  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
449 
450  if (i<=0)
451  {
452  mCurrentIndex=0;
453  mpCurrent=mpFirst;
454  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
455 
456  return ((Node*)mpFirst)->mValue;
457  }
458  if (i>=mSize-1)
459  {
460  mCurrentIndex=mSize-1;
461  mpCurrent=mpLast;
462  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
463 
464  return ((Node*)mpLast)->mValue;
465  }
466  if (mCurrentIndex<i) {
467  if (i<((mCurrentIndex+mSize)>>1)) {
468  do {
469  mCurrentIndex++;
470  mpCurrent = mpCurrent->Next();
471  } while (mCurrentIndex<i);
472  } else {
473  mCurrentIndex = mSize-1;
474  mpCurrent = mpLast;
475  while (mCurrentIndex>i) {
476  mCurrentIndex--;
477  mpCurrent = mpCurrent->Previous();
478  }
479  }
480  }else if (mCurrentIndex>i)
481  {
482  if (i>(mCurrentIndex>>1)) {
483  do {
484  mCurrentIndex--;
485  mpCurrent = mpCurrent->Previous();
486  } while (mCurrentIndex>i);
487  } else {
488  mCurrentIndex=0;
489  mpCurrent = mpFirst;
490  while (mCurrentIndex<i) {
491  mCurrentIndex++;
492  mpCurrent = mpCurrent->Next();
493  }
494  }
495  }
496  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
497 
498  return ((Node*)mpCurrent)->mValue;
499 }
500 
501 template <class T> inline T& List<T>::operator [] (TIndex i) {
502  /* this function is optimized, by starting searching from the current
503  index, or from the beginning or the end, when that's closer.
504  */
505  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
506 
507  if (i<=0)
508  {
509  mCurrentIndex=0;
510  mpCurrent=mpFirst;
511  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
512 
513  return ((Node*)mpFirst)->mValue;
514  }
515  if (i>=mSize-1)
516  {
517  mCurrentIndex=mSize-1;
518  mpCurrent=mpLast;
519  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
520 
521  return ((Node*)mpLast)->mValue;
522  }
523  if (mCurrentIndex<i) {
524  if (i<((mCurrentIndex+mSize)>>1)) {
525  do {
526  mCurrentIndex++;
527  mpCurrent = mpCurrent->Next();
528  } while (mCurrentIndex<i);
529  } else {
530  mCurrentIndex = mSize-1;
531  mpCurrent = mpLast;
532  while (mCurrentIndex>i) {
533  mCurrentIndex--;
534  mpCurrent = mpCurrent->Previous();
535  }
536  }
537  }else if (mCurrentIndex>i)
538  {
539  if (i>(mCurrentIndex>>1)) {
540  do {
541  mCurrentIndex--;
542  mpCurrent = mpCurrent->Previous();
543  } while (mCurrentIndex>i);
544  } else {
545  mCurrentIndex=0;
546  mpCurrent = mpFirst;
547  while (mCurrentIndex<i) {
548  mCurrentIndex++;
549  mpCurrent = mpCurrent->Next();
550  }
551  }
552  }
553  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
554 
555  return ((Node*)mpCurrent)->mValue;
556 }
557 
558 template <class T> inline typename List<T>::Node* List<T>::GetNodeAt(TIndex i){
559  /* this function is optimized, by starting searching from the current
560  index, or from the beginning or the end, when that's closer.
561  */
562  if (i<=0)
563  {
564  mpCurrent=mpFirst;
565  mCurrentIndex=0;
566  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
567 
568  return mpFirst;
569  }
570  if (i>=mSize-1)
571  {
572  mpCurrent=mpLast;
573  mCurrentIndex=mSize-1;
574  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
575 
576  return mpLast;
577  }
578  if (mCurrentIndex<i) {
579  if (i<((mCurrentIndex+mSize)>>1)) {
580  do {
581  mCurrentIndex++;
582  mpCurrent = mpCurrent->Next();
583  } while (mCurrentIndex<i);
584  } else {
585  mCurrentIndex = mSize-1;
586  mpCurrent = mpLast;
587  while (mCurrentIndex>i) {
588  mCurrentIndex--;
589  mpCurrent = mpCurrent->Previous();
590  }
591  }
592  }else if (mCurrentIndex>i)
593  {
594  if (i>(mCurrentIndex>>1)) {
595  do {
596  mCurrentIndex--;
597  mpCurrent = mpCurrent->Previous();
598  } while (mCurrentIndex>i);
599  } else {
600  mCurrentIndex=0;
601  mpCurrent = mpFirst;
602  while (mCurrentIndex<i) {
603  mCurrentIndex++;
604  mpCurrent = mpCurrent->Next();
605  }
606  }
607  }
608  CLAM_DEBUG_ASSERT(FulfillsInvariant(),"List does not fulfill invariant");
609 
610  return mpCurrent;
611 }
612 
613 template <class T> inline bool List<T>::FulfillsInvariant(void) const
614 {
615  int i;
616  if(mSize>0)
617  {
618  if (mpFirst->mpPrevious || mpLast->mpNext ||
619  mSize<0 || (mCurrentIndex<0) || (mpCurrent==0)
620  )
621  {
622  return false;
623  }
624  Node* pTmp=mpCurrent;
625  for(i=mCurrentIndex;i>=0;i--)
626  {
627  CLAM_ASSERT(pTmp->mpPrevious || i==0, "Current pointer not consistent");
628  pTmp=pTmp->mpPrevious;
629  }
630  }
631  return true;
632 }
633 
634 };
635 
636 #endif
637