File: UTILS\U_LISTS.CPP
1 //#############################################################################
2 // //
3 // U_LISTS.CPP //
4 // Subsystem: Utilities - verkettete Listen //
5 // Deklaration: U_LISTS.H //
6 //---------------------------------------------------------------------------//
7 // Autoren: Thomas Kullmann, Günther Reinecker //
8 // Stand: 02.04.2004 //
9 // //
10 //#############################################################################
11
12 #include "utils\u_lists.h" // SCHNITTSTELLE für diese Datei
13
14 //#############################################################################
15 // TLnkContainer
16 //#############################################################################
17
18 TLnkContainer::TLnkContainer(void *const aData, TLnkList &aList) : m_Data(aData), m_List(aList), m_Prev(0), m_Next(0) {
19 }
20 //-----------------------------------------------------------------------------
21
22 bool TLnkContainer::IsElementOf(const TLnkList *const aList) const {
23 return ( &m_List==aList );
24 }
25
26 //#############################################################################
27 // TLnkList
28 //#############################################################################
29
30 TLnkList::TLnkList(const bool aFailIfNull, const bool aFailIfExists, const bool aAutoDelete, const bool aCheckOnDel) : m_FailIfNull(aFailIfNull), m_FailIfExists(aFailIfExists), m_AutoDelete(aAutoDelete), m_CheckOnDel(aCheckOnDel), m_First(0), m_Last(0) {
31 }
32 //-----------------------------------------------------------------------------
33
34 TLnkList::~TLnkList() {
35 Clear();
36 }
37 //-----------------------------------------------------------------------------
38
39 TLnkContainer *TLnkList::Find(void *aData, TLnkContainer *aStart) {
40 TLnkContainer *result= 0;
41 if ( !aStart ) result= m_First; // am Anfang anfangen
42 else if ( !aStart->IsElementOf(this) ) return aStart->m_List.Find(aData, aStart); // nicht Element dieser Liste
43 else result= aStart; // ab angegebenem Container
44
45 while ( result ) {
46 if ( result->m_Data==aData ) return result; // gefunden
47 else result= result->m_Next;
48 }
49 return 0; // nicht gefunden
50 }
51 //-----------------------------------------------------------------------------
52
53 void *TLnkList::GetAt(TLnkContainer &aContainer) const {
54 if ( !aContainer.IsElementOf(this) ) return aContainer.m_List.GetAt(aContainer);
55 return aContainer.m_Data; // ggf. 0
56 }
57 //-----------------------------------------------------------------------------
58
59 bool TLnkList::Insert(void *const aData) {
60 if ( m_FailIfNull && !aData ) return false; // Null-Elemente nicht aufnehmen
61 if ( m_FailIfExists && Find(aData) ) return false; // ist schon in der Liste
62
63 TLnkContainer *toAdd= new TLnkContainer(aData, *this);
64 // mit Folgeelement verlinken
65 if ( m_First ) m_First->m_Prev= toAdd;
66 toAdd->m_Next= m_First; // ggf. 0
67 m_First= toAdd;
68 if ( !m_Last ) m_Last= toAdd; // die Liste war leer
69 return true;
70 }
71 //-----------------------------------------------------------------------------
72
73 bool TLnkList::Append(void *const aData) {
74 if ( m_FailIfNull && !aData ) return false; // Null-Elemente nicht aufnehmen
75 if ( m_FailIfExists && Find(aData) ) return false; // ist schon in der Liste
76
77 TLnkContainer *toAdd= new TLnkContainer(aData, *this);
78 // mit Vorgänger verlinken
79 if ( m_Last ) m_Last->m_Next= toAdd;
80 toAdd->m_Prev= m_Last; // ggf. 0
81 m_Last= toAdd;
82 if ( !m_First ) m_First= toAdd; // die Liste war leer
83 return true;
84 }
85 //-----------------------------------------------------------------------------
86
87 bool TLnkList::InsBefore(TLnkContainer *aContainer, void *const aData) {
88 if ( !aContainer ) return Insert(aData); // am Anfang einfügen
89 if ( !aContainer->IsElementOf(this) ) return aContainer->m_List.InsBefore(aContainer, aData); // nicht Element dieser Liste
90
91 if ( m_FailIfNull && !aData ) return false; // Null-Elemente nicht aufnehmen
92 if ( m_FailIfExists && Find(aData) ) return false; // ist schon in der Liste
93
94 TLnkContainer *prev= aContainer->m_Prev; // ggf. 0
95 TLnkContainer *toAdd= new TLnkContainer(aData, *this);
96 // mit Vorgänger verlinken
97 if ( prev ) prev->m_Next= toAdd;
98 else m_First= toAdd; // kein Vorgänger: wir sind die ersten
99 toAdd->m_Prev= prev; // ggf. 0
100 // mit Folgeelement verlinken
101 toAdd->m_Next= aContainer;
102 aContainer->m_Prev= toAdd;
103 return true;
104 }
105 //-----------------------------------------------------------------------------
106
107 bool TLnkList::AddAfter(TLnkContainer *aContainer, void *const aData) {
108 if ( !aContainer ) return Append(aData); // am Ende einfügen
109 if ( !aContainer->IsElementOf(this) ) return aContainer->m_List.AddAfter(aContainer, aData); // nicht Element dieser Liste
110
111 if ( m_FailIfNull && !aData ) return false; // Null-Elemente nicht aufnehmen
112 if ( m_FailIfExists && Find(aData) ) return false; // ist schon in der Liste
113
114 TLnkContainer *next= aContainer->m_Next; // ggf. 0
115 TLnkContainer *toAdd= new TLnkContainer(aData, *this);
116 // mit Vorgänger verlinken
117 aContainer->m_Next= toAdd;
118 toAdd->m_Prev= aContainer;
119 // mit Folgeelement verlinken
120 if ( next ) next->m_Prev= toAdd;
121 else m_Last= toAdd; // kein Folgeelement: wir sind die letzten
122 toAdd->m_Next= next; // ggf. 0
123 return true;
124 }
125 //-----------------------------------------------------------------------------
126
127 void *TLnkList::Remove(TLnkContainer &aContainer) {
128 if ( !aContainer.IsElementOf(this) ) return aContainer.m_List.Remove(aContainer); // nicht Element dieser Liste
129
130 TLnkContainer *p= aContainer.m_Prev; // ggf. 0
131 TLnkContainer *n= aContainer.m_Next; // ggf. 0
132 // Verlinkung entfernen
133 if ( p ) p->m_Next= n;
134 else m_First= n; // kein Vorgänger: wir waren die ersten; ggf. 0
135 if ( n ) n->m_Prev= p;
136 else m_Last= p; // kein Nachfolger: wie waren die letzten; ggf. 0
137
138 // Container freigeben
139 TLnkContainer *toDel= &aContainer;
140 void *result= toDel->m_Data;
141 _FREEOBJ(toDel);
142
143 // Element nicht automatisch freigeben
144 if ( m_AutoDelete && result ) { // Element automatisch freigeben
145 if ( !m_CheckOnDel || m_FailIfExists || !Find(result) ) { // <result> ist einzigartig in der Liste
146 FreeData(result); // einzigartiges Element freigeben
147 result= 0;
148 }
149 }
150 return result;
151 }
152 //-----------------------------------------------------------------------------
153
154 void TLnkList::Clear() {
155 if ( m_First ) CutList(*m_First); // alle Elemente entfernen
156 }
157 //-----------------------------------------------------------------------------
158
159 void TLnkList::CutList(TLnkContainer &aContainer) {
160 if ( !aContainer.IsElementOf(this) ) { // nicht Element dieser Liste
161 aContainer.m_List.CutList(aContainer);
162 return;
163 }
164
165 TLnkContainer *act= &aContainer;
166 // Vorgänger ist neues Listenende
167 TLnkContainer *p= act->m_Prev; // ggf. 0
168 if ( p ) p->m_Next= 0;
169 else m_First= 0; // kein Vorgänger: wir waren die ersten
170 m_Last= p; // ggf. 0
171
172 // dieses und Folgeelemente entfernen
173 while ( act ) {
174 TLnkContainer *toDel= act;
175 act= act->m_Next; // weitersetzen, vor _FREEOBJ
176
177 // Container freigeben
178 void *result= toDel->m_Data;
179 _FREEOBJ(toDel);
180
181 if ( m_AutoDelete && result ) { // Element automatisch freigeben
182 if ( m_CheckOnDel && !m_FailIfExists ) { // alle weiteren Vorkommen, die weiter hinten folgen, entfernen
183 // alle nachfolgenden Container entfernen, die auch <result> beinhalten
184 TLnkContainer *next= 0;
185 if ( act ) next= Find(result, act); // nur suchen, wenn Folgeelement existiert
186 while ( next ) {
187 TLnkContainer *temp= next;
188 next= Find(result, next->m_Next); // erst weitersuchen, dann freigeben
189
190 // Verlinkung aktualisierien, <m_First> und <m_Last> wurden oben schon gesetzt - dürfen nicht mehr gesetzt werden
191 TLnkContainer *p= temp->m_Prev;
192 TLnkContainer *n= temp->m_Next;
193 if ( p ) p->m_Next= n;
194 if ( n ) n->m_Prev= p;
195
196 // Container freigeben
197 _FREEOBJ(temp);
198 }
199 }
200 // wenn <result> noch in der Liste ist, die am Ende von CutList übrig bleibt: <result> NICHT freigeben
201 if ( !m_CheckOnDel || m_FailIfExists || !Find(result) ) { // <result> ist einzigartig in der Liste
202 FreeData(result); // einzigartiges Element freigeben
203 result= 0;
204 }
205 }
206 }
207 }
208 //-----------------------------------------------------------------------------
209
210 void TLnkList::FreeData(void *aData) const {
211 _FREEOBJ(aData);
212 }
213
214 //##############################################################################
215 // TIndList
216 //##############################################################################
217
218 TIndList::TIndList(const bool aFailIfNull, const bool aFailIfExists, const bool aAutoDelete, const bool aCheckOnDel, const TIndex &aTemp) : TLnkList(aFailIfNull, aFailIfExists, aAutoDelete, aCheckOnDel) {
219 m_Count= 0;
220 DoInvalidAccelerator();
221 }
222 //-----------------------------------------------------------------------------
223
224 void TIndList::DoInvalidAccelerator() {
225 m_AccelIndex= 0;
226 m_AccelContainer= 0;
227 }
228 //-----------------------------------------------------------------------------
229
230 TLnkContainer *TIndList::FindForward(TIndex aIndex, const TIndex aActIdx, TLnkContainer *aActContainer) const {
231 TLnkContainer *result= aActContainer;
232 while ( (aIndex>aActIdx) && (result) ) {
233 result= result->m_Next;
234 aIndex--;
235 }
236 return result;
237 }
238 //-----------------------------------------------------------------------------
239
240 TLnkContainer *TIndList::FindBackward(TIndex aIndex, const TIndex aActIdx, TLnkContainer *aActContainer) const {
241 TLnkContainer *result= aActContainer;
242 while ( (aIndex<aActIdx) && (result) ) {
243 result= result->m_Prev;
244 aIndex++;
245 }
246 return result;
247 }
248 //-----------------------------------------------------------------------------
249
250 TLnkContainer *TIndList::FindIdx(TIndex aIndex, bool aAdoptAccelerator) const {
251 if ( GetCount()==0 ) { // Liste ist leer
252 TraceErr("INDEX!!! Die Liste ist leer!\nDie angeforderte Operation ist nicht durchführbar.");
253 return 0;
254 }
255 if ( aIndex > GetCount()-1 ) { // Index ist zu groß
256 TraceErr("INDEX!!! Der angegebene Index ueberschreitet das Listenende!\nDas letzte Element wird fuer die angeforderte Operation verwendet.");
257 aIndex= GetCount()-1;
258 }
259
260 TLnkContainer *result= 0;
261 if ( m_AccelContainer && aIndex<m_AccelIndex && m_AccelIndex-aIndex<aIndex-0 ) // angeforderter Index liegt vor dem zuletzt benutzten Container und dieser ist besser als am Anfang anzufangen
262 result= FindBackward(aIndex, m_AccelIndex, m_AccelContainer);
263 else if ( m_AccelContainer && m_AccelIndex<=aIndex && aIndex-m_AccelIndex<GetCount()-aIndex ) // angeforderter Index liegt nach dem zuletzt benutzten Container und dieser ist besser als am Ende anzufangen
264 result= FindForward(aIndex, m_AccelIndex, m_AccelContainer);
265 else if ( aIndex<GetCount()/2 || GetCount()==0 ) // am Anfang anfangen und vorwärts suchen
266 result= FindForward(aIndex, 0, m_First);
267 else // bei Ende anfangen und rückwärts suchen
268 result= FindBackward(aIndex, GetCount()-1, m_Last);
269
270 if ( aAdoptAccelerator && result ) {
271 static_cast<TIndex>(m_AccelIndex)= aIndex;
272 const_cast<TLnkContainer*>(m_AccelContainer)= result;
273 }
274 return result;
275 }
276 //-----------------------------------------------------------------------------
277
278 void *TIndList::GetAt(TIndex aIndex, bool &aValid) const {
279 TLnkContainer *temp= FindIdx(aIndex);
280 aValid= (temp!=0);
281 if ( temp ) return TLnkList::GetAt(*temp);
282 else return 0; // leere oder fehlerhafte Liste
283 }
284 //-----------------------------------------------------------------------------
285
286 void *TIndList::GetAt(TIndex aIndex) const {
287 bool bValid= false;
288 return GetAt(aIndex, bValid);
289 }
290 //-----------------------------------------------------------------------------
291
292 void *TIndList::operator[] (TIndex aIndex) const {
293 return GetAt(aIndex);
294 }
295 //-----------------------------------------------------------------------------
296
297 bool TIndList::Insert(void *const aData) {
298 bool result= TLnkList::Insert(aData);
299 if ( result ) {
300 DoInvalidAccelerator();
301 m_Count++;
302 }
303 return result;
304 }
305 //-----------------------------------------------------------------------------
306
307 bool TIndList::Append(void *const aData) {
308 bool result= TLnkList::Append(aData);
309 if ( result ) m_Count++;
310 return result;
311 }
312 //-----------------------------------------------------------------------------
313
314 bool TIndList::InsBefore(TIndex aIndex, void *const aData) {
315 bool result= false;
316 if ( GetCount()==0 ) { // Liste ist leer
317 TraceErr("INDEX!!! Die Liste ist leer!\nDas Element wird am Listenende eingefuegt.");
318 result= TLnkList::Append(aData);
319 } else {
320 TLnkContainer *temp= FindIdx(aIndex, false);
321 result= ( temp && TLnkList::InsBefore(temp, aData) );
322 if ( result && aIndex<=m_AccelIndex ) DoInvalidAccelerator();
323 }
324 if ( result ) m_Count++;
325 return result;
326 }
327 //-----------------------------------------------------------------------------
328
329 bool TIndList::AddAfter(TIndex aIndex, void *const aData) {
330 bool result= false;
331 if ( GetCount()==0 ) { // Liste ist leer
332 TraceErr("INDEX!!! Die Liste ist leer!\nDas Element wird am Listenende eingefuegt.");
333 result= TLnkList::Append(aData);
334 } else {
335 TLnkContainer *temp= FindIdx(aIndex);
336 result= ( temp && TLnkList::AddAfter(temp, aData) );
337 if ( result && aIndex<m_AccelIndex ) DoInvalidAccelerator();
338 }
339 if ( result ) m_Count++;
340 return result;
341 }
342 //-----------------------------------------------------------------------------
343
344 void *TIndList::Remove(TIndex aIndex) {
345 TLnkContainer *temp= FindIdx(aIndex, false);
346 if ( temp ) {
347 if ( aIndex<=m_AccelIndex ) DoInvalidAccelerator();
348 void *result= TLnkList::Remove(*temp); // entfernt <*temp> in jedem Fall; Rückgabewert aber ggf. 0
349 m_Count--;
350 return result;
351 } else return 0; // leere oder fehlerhafte Liste
352 }
353 //-----------------------------------------------------------------------------
354
355 void *TIndList::RemoveData(void *aData) {
356 TLnkContainer *temp= m_First;
357 TIndex idx= 0;
358 while ( temp ) {
359 if ( temp->m_Data==aData ) return Remove(idx); // gefunden
360 temp= temp->m_Next;
361 idx++;
362 }
363 return 0; // leere Liste oder <aData> nicht gefunden
364 }
365 //-----------------------------------------------------------------------------
366
367 void TIndList::Clear() {
368 DoInvalidAccelerator();
369 TLnkList::Clear();
370 m_Count= 0;
371 }
372 //-----------------------------------------------------------------------------
373
374 void TIndList::CutList(TIndex aCount) {
375 if ( GetCount()==0 ) {
376 TraceErr("INDEX!!! Die Liste ist leer!\nDie angeforderte Operation ist nicht durchführbar."); // Liste ist leer
377 return;
378 } else if ( aCount > GetCount()-1 ) {
379 TraceErr("INDEX!!! Der angegebene Index ueberschreitet das Listenende!\nDie angeforderte Operation ist nicht durchführbar."); // Index ist zu groß
380 return;
381 }
382
383 TLnkContainer *temp= FindIdx(aCount, false);
384 if ( temp ) {
385 TLnkList::CutList(*temp); // entfernt <temp> und Folgeelemente
386 m_Count= aCount;
387 if ( aCount<=m_AccelIndex ) DoInvalidAccelerator();
388 }
389 }
390 //-----------------------------------------------------------------------------
391
392 TIndex TIndList::GetCount() const {
393 return m_Count;
394 }
395
396 //##############################################################################
397 // TIdxContainer
398 //##############################################################################
399
400 TIdxContainer::TIdxContainer(const TIndex &aSize) : m_Data(0), m_Size(0), m_Prev(0), m_Next(0) {
401 static_cast<TIndex>(m_Size)= max(1, aSize); // mind. ein Element sollte enthalten sein
402 m_Data= new void*[m_Size];
403 for (TIndex idx= 0; idx<GetSize(); idx++) m_Data[idx]= 0;
404 }
405 //-----------------------------------------------------------------------------
406
407 TIdxContainer::~TIdxContainer() {
408 _FREELIST(m_Data);
409 }
410 //-----------------------------------------------------------------------------
411
412 TIndex TIdxContainer::GetSize() const {
413 return m_Size;
414 }
415 //-----------------------------------------------------------------------------
416
417 void *TIdxContainer::ShiftRight(TIndex aStartIdx) {
418 if ( aStartIdx>=GetSize() ) {
419 TraceErr("INDEX!!! Der Index ist zu groß!\nDie gesamte Liste wird nach hinten geshiftet."); // Index zu groß
420 aStartIdx= 0; // vom Anfang der Liste
421 }
422 void *result= m_Data[ GetSize()-1 ];
423 for (TIndex idx= GetSize()-1; idx>aStartIdx; idx--) m_Data[idx]= m_Data[idx-1];
424 m_Data[aStartIdx]= 0; // nun leer
425 return result;
426 }
427 //-----------------------------------------------------------------------------
428
429 void *TIdxContainer::ShiftLeft(TIndex aStartIdx) {
430 if ( aStartIdx>=GetSize() ) {
431 TraceErr("INDEX!!! Der Index ist zu groß!\nDie gesamte Liste wird nach vorn geshiftet."); // Index zu groß
432 aStartIdx= GetSize()-1; // bis zum Ende der Liste
433 }
434 void *result= m_Data[ aStartIdx ];
435 for (TIndex idx= aStartIdx+1; idx<GetSize()-1; idx++) m_Data[idx-1]= m_Data[idx];
436 m_Data[GetSize()-1]= 0; // nun leer
437 return result;
438 }
439
440 //##############################################################################
441 // TIdxList
442 //##############################################################################
443
444 TIdxList::TIdxList(const bool aFailIfNull, const bool aFailIfExists, const bool aAutoDelete, const bool aCheckOnDel, const TIndex &aSize) : m_FailIfNull(aFailIfNull), m_FailIfExists(aFailIfExists), m_AutoDelete(aAutoDelete), m_CheckOnDel(aCheckOnDel), m_Size(aSize), m_First(0), m_Last(0), m_Count(0), m_Used(0) {
445 }
446 //-----------------------------------------------------------------------------
447
448 TIdxList::~TIdxList() {
449 Clear();
450 }
451 //-----------------------------------------------------------------------------
452
453 TIdxContainer *TIdxList::FindIdx(TIndex &aIndex) const {
454 if ( GetCount()>0 && aIndex>GetCount()-1 ) {
455 TraceErr("INDEX!!! Der Index ist zu groß!\nDas letzte Element wird verwendet."); // Index zu groß
456 aIndex= GetCount()-1;
457 } else if ( !m_First ) TraceErr("INDEX!!! Die Liste ist leer!\nDie angeforderte Operation ist nicht durchführbar."); // Liste ist leer
458
459 TIdxContainer *result= 0;
460 if ( aIndex<GetCount()/2 || GetCount()==0 ) { // am Anfang anfangen und vorwärts suchen
461 result= m_First;
462 while ( result && aIndex>=result->GetSize() ) {
463 aIndex-= result->GetSize();
464 result= result->m_Next;
465 }
466 return result;
467 } else { // bei Ende anfangen und rückwärts suchen
468 result= m_Last;
469 TIndex index= GetCount();
470 while ( result ) {
471 if ( !result->m_Next ) index-= m_Used; // Container ist u.U. noch nicht voll
472 else index-= result->GetSize();
473 if ( index<=aIndex ) { // gefunden
474 aIndex-= index;
475 return result;
476 }
477 result= result->m_Prev;
478 }
479 // nicht gefunden
480 aIndex= 0;
481 return 0;
482 }
483 }
484 //-----------------------------------------------------------------------------
485
486 TIdxContainer *TIdxList::Find(void *aData, TIndex &aIndex) const {
487 aIndex= 0;
488 TIdxContainer *result= m_First;
489 while ( result ) {
490 TIndex last= result->GetSize();
491 if ( !result->m_Next ) last= m_Used; // das letzte Element mit einbeziehen
492 for (TIndex idx= 0; idx<last; idx++) {
493 if ( result->m_Data[idx]==aData ) return result; // gefunden
494 aIndex++;
495 }
496 result= result->m_Next;
497 }
498 aIndex= 0;
499 return 0;
500 }
501 //-----------------------------------------------------------------------------
502
503 void *TIdxList::GetAt(TIndex aIndex, bool &aValid) const {
504 TIdxContainer *temp= FindIdx(aIndex); // sucht den Container und verändert <aIndex>
505 aValid= (temp!=0);
506 if ( temp ) return temp->m_Data[aIndex];
507 else return 0; // leere Liste
508 }
509 //-----------------------------------------------------------------------------
510
511 void *TIdxList::GetAt(TIndex aIndex) const {
512 bool bValid= false;
513 return GetAt(aIndex, bValid);
514 }
515 //-----------------------------------------------------------------------------
516
517 void *TIdxList::operator[] (TIndex aIndex) const {
518 return GetAt(aIndex);
519 }
520 //-----------------------------------------------------------------------------
521
522 bool TIdxList::Insert(void *const aData) {
523 if ( !m_First ) return Append(aData); // Liste ist leer: Vor den Überprüfungen Append aufrufen - führt auch diese Überprüfungen aus
524 else return InsBefore(0, aData); // gibt bei <m_First>==0 eine Fehlermeldung aus
525 }
526 //-----------------------------------------------------------------------------
527
528 bool TIdxList::Append(void *const aData) {
529 TIndex i;
530 if ( m_FailIfNull && !aData ) return false; // Null-Elemente nicht aufnehmen
531 if ( m_FailIfExists && Find(aData, i) ) return false; // ist schon in der Liste
532
533 if ( !m_Last ) { // Liste ist leer
534 TIdxContainer *toAdd= m_Last= new TIdxContainer(m_Size);
535 m_Used= 1;
536 toAdd->m_Data[m_Used-1]= aData;
537 // mit Vorgänger verlinken
538 m_First= m_Last= toAdd;
539 m_Count= 1;
540 return true;
541 }
542
543 if ( m_Used>=m_Last->GetSize() ) { // dieser (letzte) Container ist voll: einen neuen anhängen
544 TIdxContainer *toAdd= new TIdxContainer(m_Size);
545 m_Used= 1;
546 toAdd->m_Data[m_Used-1]= aData;
547 // mit Vorgänger verlinken
548 m_Last->m_Next= toAdd;
549 toAdd->m_Prev= m_Last;
550 m_Last= toAdd;
551 } else { // ansonsten ist im letzten Container noch genug Platz
552 m_Used++;
553 m_Last->m_Data[m_Used-1]= aData;
554 }
555 m_Count++;
556 return true;
557 }
558 //-----------------------------------------------------------------------------
559
560 bool TIdxList::InsBefore(TIndex aIndex, void *const aData) {
561 if ( !m_First ) { // Liste ist leer
562 TraceErr("INDEX!!! Die Liste ist leer!\nDas Element wird am Listenende eingefuegt.");
563 return Append(aData);
564 }
565 TIndex i;
566 if ( m_FailIfNull && !aData ) return false; // Null-Elemente nicht aufnehmen
567 if ( m_FailIfExists && Find(aData, i) ) return false; // ist schon in der Liste
568
569 void *shifted= aData; // als Element, das beim shiften frei wird
570 TIdxContainer *act= FindIdx(aIndex); // sucht den Container und verändert <aIndex>
571 while ( act ) {
572 void *temp= act->ShiftRight(aIndex);
573 act->m_Data[aIndex]= shifted;
574 shifted= temp;
575 aIndex= 0; // nun sofort nur noch am Anfang einfügen
576 if ( !act->m_Next ) { // wir haben den letzten Container erreicht
577 if ( m_Used>=act->GetSize() ) { // dieser (letzte) Container ist voll: einen neuen anhängen
578 TIdxContainer *toAdd= new TIdxContainer(m_Size);
579 m_Used= 1;
580 toAdd->m_Data[m_Used-1]= shifted;
581 // mit Vorgänger verlinken
582 m_Last->m_Next= toAdd;
583 toAdd->m_Prev= m_Last;
584 m_Last= toAdd;
585 } else m_Used++; // ansonsten ist im letzten Container noch genug Platz
586 break; // fertig
587 } else act= act->m_Next; // im nächsten Container weitermachen
588 }
589 m_Count++;
590 return true;
591 }
592 //-----------------------------------------------------------------------------
593
594 bool TIdxList::AddAfter(TIndex aIndex, void *const aData) {
595 if ( m_First && aIndex>=GetCount()-1 ) return Append(aData); // das einzige, was InsBefore nicht kann; bei <m_First>==0 auch InsBefore aufrufen, wegen der Fehlermeldung
596 else return InsBefore(aIndex+1, aData); // einfach VOR dem nachfolgenden Element einfügen
597 }
598 //-----------------------------------------------------------------------------
599
600 void *TIdxList::Remove(TIndex aIndex) {
601 void *result= 0; // falls Liste leer
602 TIdxContainer *act= FindIdx(aIndex); // sucht den Container und verändert <aIndex>
603 if ( act ) {
604 // alle nachfolgenden Elemente eins nach vorn kopieren
605 result= act->ShiftLeft(aIndex);
606 while ( act->m_Next ) {
607 void *shifted= act->m_Next->ShiftLeft(0);
608 act->m_Data[ act->GetSize()-1 ]= shifted;
609 }
610 m_Used--;
611 if ( m_Used==0 ) { // letzter Container ist nun leer: diesen entfernen und m_Used auf Größe des nun letzten Containers (if one)
612 act= m_Last->m_Prev; // ggf. 0
613 _FREEOBJ(m_Last); // Container freigeben
614 if ( act ) {
615 m_Last= act; // neues letztes Element
616 m_Last->m_Next= 0; // ohne Nachfolger
617 m_Used= m_Last->GetSize();
618 } else m_First= m_Last= 0; // Liste ist nun leer
619 }
620 m_Count--;
621
622 if ( m_AutoDelete && result ) { // Element automatisch freigeben
623 TIndex temp;
624 if ( !m_CheckOnDel || m_FailIfExists || !Find(result, temp) ) { // <result> ist einzigartig in der Liste
625 FreeData(result);
626 result= 0;
627 }
628 }
629 }
630 return result;
631 }
632 //-----------------------------------------------------------------------------
633
634 void TIdxList::CutList(const TIndex &aCount) {
635 if ( GetCount()==0 ) {
636 TraceErr("INDEX!!! Die Liste ist leer!\nDie angeforderte Operation ist nicht durchführbar."); // Liste ist leer
637 return;
638 } else if ( aCount>GetCount()-1 ) {
639 TraceErr("INDEX!!! Der angegebene Index ueberschreitet das Listenende!\nDie angeforderte Operation ist nicht durchführbar."); // Index ist zu groß
640 return;
641 }
642
643 // dieses und alle nachfolgenden Elemente entfernen
644 TIndex aIndex= aCount;
645 TIdxContainer *act= FindIdx(aIndex); // sucht den Container und verändert <aIndex>
646 if ( !act ) return;
647
648 // Liste vor dem Element abschneiden
649 TIdxContainer *next= act->m_Next;
650 TIndex used= m_Used;
651 if ( aIndex==0 ) { // <act> wird komplett geleert; d.h. sein Vorgänger wird neuer, letzter Container
652 m_Last= act->m_Prev; // ggf. 0
653 if ( !m_Last ) { // Liste ist nun leer
654 m_First= 0;
655 m_Used= 0;
656 } else m_Used= m_Last->GetSize(); // den neue letzten Container komplett benutzen (der ist voll)
657 } else {
658 m_Last= act;
659 m_Used= aIndex;
660 }
661 if ( m_Last ) m_Last->m_Next= 0;
662 m_Count= aCount;
663 // Elemente freigeben
664 while ( act ) {
665 TIndex last= act->GetSize();
666 if ( !next ) last= used; // das letzte Element mit einbeziehen
667 for (TIndex idx= aIndex; idx<last; idx++) {
668 void *result= act->m_Data[idx];
669 act->m_Data[idx]= 0;
670
671 if ( m_AutoDelete && result ) { // Element automatisch freigeben
672 if ( m_CheckOnDel && !m_FailIfExists ) { // alle weiteren Vorkommen, die weiter hinten folgen, entfernen
673 // bis zum Ende des aktuellen Containers
674 for (TIndex idx2= idx+1; idx2<last; idx2++) if ( act->m_Data[idx2]==result ) act->m_Data[idx2]= 0;
675 TIdxContainer *act2= next;
676 // alle weiteren Container
677 while ( act2 ) {
678 TIndex last2= act2->GetSize();
679 if ( !act2->m_Next ) last2= used; // das letzte Element mit einbeziehen
680 for (idx2= 0; idx2<last2; idx2++) if ( act2->m_Data[idx2]==result ) act2->m_Data[idx2]= 0;
681 act2= act2->m_Next;
682 }
683 }
684 TIndex temp;
685 if ( !m_CheckOnDel || m_FailIfExists || !Find(result, temp) ) { // <result> ist einzigartig in der Liste
686 FreeData(result);
687 result= 0;
688 }
689 }
690 }
691 if ( aIndex==0 ) _FREEOBJ(act); // Container komplett entfernen
692 aIndex= 0; // nächsten Container komplett
693 act= next; // bei dem über FindIdx gefundenen Container ist m_Next==0, um das neue Listenende zu kennzeichnen, deshalb <next> verwenden
694 if ( act ) next= act->m_Next;
695 else next= 0;
696 }
697 }
698 //-----------------------------------------------------------------------------
699
700 void TIdxList::Clear() {
701 if ( GetCount() ) CutList(0);
702 m_Count= 0;
703 }
704 //-----------------------------------------------------------------------------
705
706 TIndex TIdxList::GetCount() const {
707 return m_Count;
708 }
709 //-----------------------------------------------------------------------------
710
711 void TIdxList::FreeData(void *aData) const { // überschreiben, wenn in der Liste nur Objekte eines bestimmten Typs enthalten sind (dann <aData> auf diesen Typ casten und freigeben)
712 _FREEOBJ(aData);
713 }
714
715 //##############################################################################
716 // TIntList
717 //##############################################################################
718
719 TIntList::TIntList(const TIndex &aCount, const int &aDefaultValue, const TIndex &aSize) : TBaseList(true, false, true, false, aSize), m_DefaultValue(aDefaultValue) {
720 SetCount(aCount);
721 }
722 //-----------------------------------------------------------------------------
723
724 TIntList::TIntList(const TIntList &aList) : TBaseList(aList.m_FailIfNull, aList.m_FailIfExists, aList.m_AutoDelete, aList.m_CheckOnDel, aList.m_Size), m_DefaultValue(aList.m_DefaultValue) {
725 if ( &aList==this ) return; // Selbstzuweisung
726
727 Clear();
728 bool bValid= false;
729 for (TIndex i=0; i<aList.GetCount(); i++) Append( aList.GetAt(i, bValid) );
730 }
731 //-----------------------------------------------------------------------------
732
733 TIntList &TIntList::operator= (const TIntList &aList) {
734 if ( &aList==this ) return *this; // Selbstzuweisung
735
736 m_DefaultValue= aList.m_DefaultValue;
737 Clear();
738 bool bValid= false;
739 for (TIndex i=0; i<aList.GetCount(); i++) Append( aList.GetAt(i, bValid) );
740 return *this;
741 }
742 //-----------------------------------------------------------------------------
743
744 int TIntList::GetAt(const TIndex &aIndex, bool &aValid) const {
745 int *temp= (int*)TBaseList::GetAt(aIndex, aValid);
746 if ( aValid && temp ) return *temp;
747 else return m_DefaultValue;
748 }
749 //-----------------------------------------------------------------------------
750
751 int TIntList::GetAt(const TIndex &aIndex) const {
752 bool bValid= false;
753 return GetAt(aIndex, bValid);
754 }
755 //-----------------------------------------------------------------------------
756
757 int &TIntList::operator[] (const TIndex &aIndex) {
758 bool bValid= false;
759 int *temp= (int*)TBaseList::GetAt(aIndex, bValid);
760 if ( !bValid || !temp ) { // <m_DefaultValue> kopieren, sonst kann <m_DefaultValue> beim Schreibzugriff geändert werden
761 temp= new int;
762 *temp= m_DefaultValue;
763 }
764 return *temp;
765 }
766 //-----------------------------------------------------------------------------
767
768 bool TIntList::SetAt(const TIndex &aIndex, const int &aValue) {
769 if ( GetCount()>0 && aIndex<GetCount() ) {
770 int *temp= (int*)TBaseList::GetAt(aIndex);
771 if ( temp ) {
772 *temp= aValue;
773 return true;
774 }
775 }
776 if ( GetCount()==0 ) TraceErr("INDEX!!! Die Liste ist leer!\nDie angeforderte Operation ist nicht durchführbar."); // Liste ist leer
777 else if ( aIndex > GetCount()-1 ) TraceErr("INDEX!!! Der angegebene Index ueberschreitet das Listenende!\nDie angeforderte Operation ist nicht durchführbar."); // Index ist zu groß
778 return false;
779 }
780 //-----------------------------------------------------------------------------
781
782 bool TIntList::Insert(const int &aValue) {
783 int *temp= new int;
784 *temp= aValue;
785 bool result= TBaseList::Insert(temp);
786 if ( !result ) FreeData(temp);
787 return result;
788 }
789 //-----------------------------------------------------------------------------
790
791 bool TIntList::Append(const int &aValue) {
792 int *temp= new int;
793 *temp= aValue;
794 bool result= TBaseList::Append(temp);
795 if ( !result ) FreeData(temp);
796 return result;
797 }
798 //-----------------------------------------------------------------------------
799
800 bool TIntList::InsBefore(const TIndex &aIndex, const int &aValue) {
801 int *temp= new int;
802 *temp= aValue;
803 bool result= TBaseList::InsBefore(aIndex, temp);
804 if ( !result ) FreeData(temp);
805 return result;
806 }
807 //-----------------------------------------------------------------------------
808
809 bool TIntList::AddAfter(const TIndex &aIndex, const int &aValue) {
810 int *temp= new int;
811 *temp= aValue;
812 bool result= TBaseList::AddAfter(aIndex, temp);
813 if ( !result ) FreeData(temp);
814 return result;
815 }
816 //-----------------------------------------------------------------------------
817
818 void TIntList::SetCount(const TIndex &aCount, const int &aDefaultValue) {
819 // Liste verkürzen
820 if ( GetCount()>aCount ) TBaseList::CutList(aCount); // CutList verringert GetCount()
821 // Liste verlängern
822 else while ( GetCount()<aCount && Append(aDefaultValue) ) /* Append erhöht GetCount() */;
823 }
824 //-----------------------------------------------------------------------------
825
826 void TIntList::SetCount(const TIndex &aCount) {
827 SetCount(aCount, m_DefaultValue);
828 }
829
830 //##############################################################################
831 // TFloatList
832 //##############################################################################
833
834 TFloatList::TFloatList(const TIndex &aCount, const float &aDefaultValue, const TIndex &aSize) : TBaseList(true, false, true, false, aSize), m_DefaultValue(aDefaultValue) {
835 SetCount(aCount);
836 }
837 //-----------------------------------------------------------------------------
838
839 TFloatList::TFloatList(const TFloatList &aList) : TBaseList(aList.m_FailIfNull, aList.m_FailIfExists, aList.m_AutoDelete, aList.m_CheckOnDel, aList.m_Size), m_DefaultValue(aList.m_DefaultValue) {
840 if ( &aList==this ) return; // Selbstzuweisung
841
842 Clear();
843 bool bValid= false;
844 for (TIndex i=0; i<aList.GetCount(); i++) Append( aList.GetAt(i, bValid) );
845 }
846 //-----------------------------------------------------------------------------
847
848 TFloatList &TFloatList::operator= (const TFloatList &aList) {
849 if ( &aList==this ) return *this; // Selbstzuweisung
850
851 m_DefaultValue= aList.m_DefaultValue;
852 Clear();
853 bool bValid= false;
854 for (TIndex i=0; i<aList.GetCount(); i++) Append( aList.GetAt(i, bValid) );
855 return *this;
856 }
857
858 //-----------------------------------------------------------------------------
859
860 float TFloatList::GetAt(const TIndex &aIndex, bool &aValid) const {
861 float *temp= (float*)TBaseList::GetAt(aIndex, aValid);
862 if ( aValid && temp ) return *temp;
863 else return m_DefaultValue;
864 }
865 //-----------------------------------------------------------------------------
866
867 float TFloatList::GetAt(const TIndex &aIndex) const {
868 bool bValid= false;
869 return GetAt(aIndex, bValid);
870 }
871 //-----------------------------------------------------------------------------
872
873 float &TFloatList::operator[] (const TIndex &aIndex) {
874 bool bValid= false;
875 float *temp= (float*)TBaseList::GetAt(aIndex, bValid);
876 if ( !bValid || !temp ) {
877 temp= new float;
878 *temp= m_DefaultValue;
879 }
880 return *temp;
881 }
882 //-----------------------------------------------------------------------------
883
884 bool TFloatList::SetAt(const TIndex &aIndex, const float &aValue) {
885 if ( GetCount()>0 && aIndex<GetCount() ) {
886 float *temp= (float*)TBaseList::GetAt(aIndex);
887 if ( temp ) {
888 *temp= aValue;
889 return true;
890 }
891 }
892 if ( GetCount()==0 ) TraceErr("INDEX!!! Die Liste ist leer!\nDie angeforderte Operation ist nicht durchführbar."); // Liste ist leer
893 else if ( aIndex > GetCount()-1 ) TraceErr("INDEX!!! Der angegebene Index ueberschreitet das Listenende!\nDie angeforderte Operation ist nicht durchführbar."); // Index ist zu groß
894 return false;
895 }
896 //-----------------------------------------------------------------------------
897
898 bool TFloatList::Insert(const float &aValue) {
899 float *temp= new float;
900 *temp= aValue;
901 bool result= TBaseList::Insert(temp);
902 if ( !result ) FreeData(temp);
903 return result;
904 }
905 //-----------------------------------------------------------------------------
906
907 bool TFloatList::Append(const float &aValue) {
908 float *temp= new float;
909 *temp= aValue;
910 bool result= TBaseList::Append(temp);
911 if ( !result ) FreeData(temp);
912 return result;
913 }
914 //-----------------------------------------------------------------------------
915
916 bool TFloatList::InsBefore(const TIndex &aIndex, const float &aValue) {
917 float *temp= new float;
918 *temp= aValue;
919 bool result= TBaseList::InsBefore(aIndex, temp);
920 if ( !result ) FreeData(temp);
921 return result;
922 }
923 //-----------------------------------------------------------------------------
924
925 bool TFloatList::AddAfter(const TIndex &aIndex, const float &aValue) {
926 float *temp= new float;
927 *temp= aValue;
928 bool result= TBaseList::AddAfter(aIndex, temp);
929 if ( !result ) FreeData(temp);
930 return result;
931 }
932 //-----------------------------------------------------------------------------
933
934 void TFloatList::SetCount(const TIndex &aCount, const float &aDefaultValue) {
935 // Liste verkürzen
936 if ( GetCount()>aCount ) TBaseList::CutList(aCount); // CutList verringert GetCount()
937 // Liste verlängern
938 else while ( GetCount()<aCount && Append(aDefaultValue) ) /* Append erhöht GetCount() */;
939 }
940 //-----------------------------------------------------------------------------
941
942 void TFloatList::SetCount(const TIndex &aCount) {
943 SetCount(aCount, m_DefaultValue);
944 }
945
946 //##############################################################################
947 // TPoint
948 //##############################################################################
949
950 TPoint::TPoint() : m_Pt(0) {
951 m_Pt= new float[s_Size];
952 for (TIndex i= 0; i<s_Size; i++) m_Pt[i]= 0.0;
953 Valid= FALSE;
954 }
955 //-----------------------------------------------------------------------------
956
957 TPoint::~TPoint() {
958 _FREELIST(m_Pt);
959 }
960 //-----------------------------------------------------------------------------
961
962 TPoint::TPoint(const TPoint &aPoint) : m_Pt(0) {
963 if ( &aPoint==this ) return; // Selbstzuweisung
964
965 m_Pt= new float[s_Size];
966 for (TIndex i= 0; i<s_Size; i++) m_Pt[i]= aPoint.m_Pt[i];
967 Valid= aPoint.Valid;
968 }
969 //-----------------------------------------------------------------------------
970
971 TPoint &TPoint::operator= (const TPoint &aPoint) {
972 if ( &aPoint==this ) return *this; // Selbstzuweisung
973
974 for (TIndex i= 0; i<s_Size; i++) m_Pt[i]= aPoint.m_Pt[i];
975 Valid= aPoint.Valid;
976 return *this;
977 }
978 //-----------------------------------------------------------------------------
979
980 float TPoint::GetAt(const TIndex &aIndex, bool &aValid) const {
981 aValid= false;
982 if ( aIndex>=s_Size ) { // Index ist zu groß
983 TraceErr("INDEX!!! Der angegebene Index ueberschreitet das Listenende!\nDas letzte Element wird fuer die angeforderte Operation verwendet.");
984 aValid= false;
985 } else aValid= true;
986 return m_Pt[ min(aIndex, s_Size-1) ];
987 }
988 //-----------------------------------------------------------------------------
989
990 float TPoint::GetAt(const TIndex &aIndex) const {
991 bool temp;
992 return GetAt(aIndex, temp);
993 }
994 //-----------------------------------------------------------------------------
995
996 float &TPoint::operator[] (const TIndex &aIndex) {
997 if ( aIndex>=s_Size ) TraceErr("INDEX!!! Der angegebene Index ueberschreitet das Listenende!\nDas letzte Element wird fuer die angeforderte Operation verwendet."); // Index ist zu groß
998 return m_Pt[ min(aIndex, s_Size-1) ];
999 }
1000 //-----------------------------------------------------------------------------
1001
1002 bool TPoint::SetAt(const TIndex &aIndex, const float &aValue) {
1003 if ( aIndex<s_Size ) {
1004 m_Pt[ aIndex ]= aValue;
1005 return true;
1006 } else {
1007 TraceErr("INDEX!!! Der angegebene Index ueberschreitet das Listenende!\nDie angeforderte Operation ist nicht durchführbar."); // Index ist zu groß
1008 return false;
1009 }
1010 }
1011
1012 //##############################################################################
1013 // TPointList
1014 //##############################################################################
1015
1016 TPointList::TPointList(const TIndex &aCount, const TIndex &aSize) : TBaseList(true, false, true, false, aSize) {
1017 SetCount(aCount);
1018 }
1019 //-----------------------------------------------------------------------------
1020
1021 TPointList::~TPointList() {
1022 Clear(); // sonst wird nicht TPointList::FreeData verwendet
1023 }
1024 //-----------------------------------------------------------------------------
1025
1026 TPointList::TPointList(const TPointList &aList) : TBaseList(aList.m_FailIfNull, aList.m_FailIfExists, aList.m_AutoDelete, aList.m_CheckOnDel, aList.m_Size), m_DefaultValue(aList.m_DefaultValue) {
1027 if ( &aList==this ) return; // Selbstzuweisung
1028
1029 Clear();
1030 bool bValid= false;
1031 for (TIndex i=0; i<aList.GetCount(); i++) Append( aList.GetAt(i, bValid) );
1032 }
1033 //-----------------------------------------------------------------------------
1034
1035 TPointList &TPointList::operator= (const TPointList &aList) {
1036 if ( &aList==this ) return *this; // Selbstzuweisung
1037
1038 m_DefaultValue= aList.m_DefaultValue;
1039 Clear();
1040 bool bValid= false;
1041 for (TIndex i=0; i<aList.GetCount(); i++) Append( aList.GetAt(i, bValid) );
1042 return *this;
1043 }
1044
1045 //-----------------------------------------------------------------------------
1046
1047 TPoint &TPointList::GetAt(const TIndex &aIndex, bool &aValid) const {
1048 TPoint *temp= (TPoint*)TBaseList::GetAt(aIndex, aValid);
1049 if ( !aValid && temp ) {
1050 FreeData(temp);
1051 temp= 0;
1052 }
1053 if ( !aValid || !temp ) temp= new TPoint(m_DefaultValue);
1054 return *temp;
1055 }
1056 //-----------------------------------------------------------------------------
1057
1058 TPoint &TPointList::GetAt(const TIndex &aIndex) const {
1059 bool bValid= false;
1060 return GetAt(aIndex, bValid);
1061 }
1062 //-----------------------------------------------------------------------------
1063
1064 TPoint &TPointList::operator[] (const TIndex &aIndex) const {
1065 return GetAt(aIndex);
1066 }
1067 //-----------------------------------------------------------------------------
1068
1069 bool TPointList::Insert(const TPoint &aValue) {
1070 TPoint *temp= new TPoint(aValue);
1071 bool result= TBaseList::Insert(temp);
1072 if ( !result ) FreeData(temp);
1073 return result;
1074 }
1075 //-----------------------------------------------------------------------------
1076
1077 bool TPointList::Append(const TPoint &aValue) {
1078 TPoint *temp= new TPoint(aValue);
1079 bool result= TBaseList::Append(temp);
1080 if ( !result ) FreeData(temp);
1081 return result;
1082 }
1083 //-----------------------------------------------------------------------------
1084
1085 bool TPointList::InsBefore(const TIndex &aIndex, const TPoint &aValue) {
1086 TPoint *temp= new TPoint(aValue);
1087 bool result= TBaseList::InsBefore(aIndex, temp);
1088 if ( !result ) FreeData(temp);
1089 return result;
1090 }
1091 //-----------------------------------------------------------------------------
1092
1093 bool TPointList::AddAfter(const TIndex &aIndex, const TPoint &aValue) {
1094 TPoint *temp= new TPoint(aValue);
1095 bool result= TBaseList::AddAfter(aIndex, temp);
1096 if ( !result ) FreeData(temp);
1097 return result;
1098 }
1099 //-----------------------------------------------------------------------------
1100
1101 void TPointList::SetCount(const TIndex &aCount, const TPoint &aDefaultValue) {
1102 // Liste verkürzen
1103 if ( GetCount()>aCount ) TBaseList::CutList(aCount); // CutList verringert GetCount()
1104 // Liste verlängern
1105 else while ( GetCount()<aCount && Append(aDefaultValue) ) /* Append erhöht GetCount() */;
1106 }
1107 //-----------------------------------------------------------------------------
1108
1109 void TPointList::SetCount(const TIndex &aCount) {
1110 SetCount(aCount, m_DefaultValue);
1111 }
1112 //-----------------------------------------------------------------------------
1113
1114 void TPointList::FreeData(void *aData) const {
1115 TPoint *cast= (TPoint*)aData;
1116 _FREEOBJ(cast); // sonst wird TPoint::~TPoint() nicht gerufen
1117 }
1118