source: git/factory/templates/ftmpl_list.cc @ fb1675

spielwiese
Last change on this file since fb1675 was fb1675, checked in by Hans Schoenemann <hannes@…>, 7 years ago
use include ".." for singular related .h, p8
  • Property mode set to 100644
File size: 13.3 KB
Line 
1/* emacs edit mode for this file is -*- C++ -*- */
2
3#include "factory/templates/ftmpl_list.h"
4
5template <class T>
6ListItem<T>::ListItem( const ListItem<T>& i )
7{
8    next = i.next;
9    prev = i.prev;
10    item = i.item;
11}
12
13
14template <class T>
15ListItem<T>::ListItem( const T& t, ListItem<T>* n, ListItem<T>* p )
16{
17    next = n;
18    prev = p;
19    item = new T( t );
20}
21
22
23template <class T>
24ListItem<T>::ListItem( T* t, ListItem<T>* n, ListItem<T>* p )
25{
26    next = n;
27    prev = p;
28    item = t;
29}
30
31
32template <class T>
33ListItem<T>::~ListItem()
34{
35    delete item;
36}
37
38
39template <class T>
40ListItem<T>& ListItem<T>::operator=( const ListItem<T>& i )
41{
42    if ( this != &i )
43    {
44        next = i.next;
45        prev = i.prev;
46        item = i.item;
47    }
48    return *this;
49}
50
51
52template <class T>
53ListItem<T>* ListItem<T>::getNext()
54{
55    return next;
56}
57
58
59template <class T>
60ListItem<T>* ListItem<T>::getPrev()
61{
62    return prev;
63}
64
65
66template <class T>
67T& ListItem<T>::getItem()
68{
69    return *item;
70}
71
72#ifndef NOSTREAMIO
73template <class T>
74void ListItem<T>::print( OSTREAM & os )
75{
76    if ( item )
77        os << *item;
78    else
79        os << "(no item)";
80}
81#endif /* NOSTREAMIO */
82
83
84
85template <class T>
86List<T>::List()
87{
88    first = last = 0;
89    _length = 0;
90}
91
92
93template <class T>
94List<T>::List( const List<T>& l )
95{
96    ListItem<T>* cur = l.last;
97    if ( cur )
98    {
99        first = new ListItem<T>( *(cur->item), 0, 0 );
100        last = first;
101        cur = cur->prev;
102        while ( cur )
103        {
104            first = new ListItem<T>( *(cur->item), first, 0 );
105            first->next->prev = first;
106            cur = cur->prev;
107        }
108        _length = l._length;
109    }
110    else
111    {
112        first = last = 0;
113        _length = 0;
114    }
115}
116
117
118template <class T>
119List<T>::List( const T& t )
120{
121    first = last = new ListItem<T>( t, 0, 0 );
122    _length = 1;
123}
124
125
126template <class T>
127List<T>::~List()
128{
129    ListItem<T> *dummy;
130    while ( first )
131    {
132        dummy = first;
133        first = first->next;
134        delete dummy;
135    }
136}
137
138
139template <class T>
140List<T>& List<T>::operator=( const List<T>& l )
141{
142    if ( this != &l )
143    {
144        ListItem<T> *dummy;
145        while ( first )
146        {
147            dummy = first;
148            first = first->next;
149            delete dummy;
150        }
151        ListItem<T>* cur = l.last;
152        if ( cur )
153        {
154            first = new ListItem<T>( *(cur->item), 0, 0 );
155            last = first;
156            cur = cur->prev;
157            while ( cur )
158            {
159                first = new ListItem<T>( *(cur->item), first, 0 );
160                first->next->prev = first;
161                cur = cur->prev;
162            }
163            _length = l._length;
164        }
165        else
166        {
167            first = last = 0;
168            _length = 0;
169        }
170        _length = l._length;
171    }
172    return *this;
173}
174
175template <class T>
176int operator== ( const List<T>& l1, const List<T>& l2 )
177{
178    if (l1.length() != l2.length())
179      return 0;
180    ListIterator<T> iter2= l2;
181    for (ListIterator<T> iter1= l1; iter1.hasItem(); iter1++)
182    {
183      if (!(iter1.getItem() == iter2.getItem()))
184        return 0;
185      iter2++;
186    }
187
188    return 1;
189}
190
191
192template <class T>
193void List<T>::insert ( const T& t )
194{
195    first = new ListItem<T>( t, first, 0 );
196    if ( last )
197        first->next->prev = first;
198    last = ( last ) ? last : first;
199    _length++;
200}
201
202
203template <class T>
204void List<T>::insert ( const T& t, int (*cmpf)( const T&, const T& ) )
205{
206    if ( ! first || cmpf( *first->item, t ) > 0 )
207        insert( t );
208    else if ( cmpf( *last->item, t ) < 0 )
209        append( t );
210    else
211    {
212        ListItem<T> * cursor = first;
213        int c;
214        while ( (c = cmpf( *cursor->item, t )) < 0 )
215            cursor = cursor->next;
216        if ( c == 0 )
217            *cursor->item = t;
218        else
219        {
220            cursor = cursor->prev;
221            cursor->next = new ListItem<T>( t, cursor->next, cursor );
222            cursor->next->next->prev = cursor->next;
223            _length++;
224        }
225    }
226}
227
228
229template <class T>
230void List<T>::insert ( const T& t, int (*cmpf)( const T&, const T& ), void (*insf)( T&, const T& ) )
231{
232    if ( ! first || cmpf( *first->item, t ) > 0 )
233        insert( t );
234    else if ( cmpf( *last->item, t ) < 0 )
235        append( t );
236    else
237    {
238        ListItem<T> * cursor = first;
239        int c;
240        while ( (c = cmpf( *cursor->item, t )) < 0 )
241            cursor = cursor->next;
242        if ( c == 0 )
243            insf( *cursor->item, t );
244        else
245        {
246            cursor = cursor->prev;
247            cursor->next = new ListItem<T>( t, cursor->next, cursor );
248            cursor->next->next->prev = cursor->next;
249            _length++;
250        }
251    }
252}
253
254
255template <class T>
256void List<T>::append ( const T& t )
257{
258    last = new ListItem<T>( t, 0, last );
259    if ( first )
260        last->prev->next = last;
261    first = ( first ) ? first : last;
262    _length++;
263}
264
265
266template <class T>
267int List<T>::isEmpty() const
268{
269    return ( first == 0 );
270}
271
272template <class T>
273int List<T>::length() const
274{
275    return _length;
276}
277
278template <class T>
279T List<T>::getFirst() const
280{
281    ASSERT( first, "List: no item available" );
282    return first->getItem();
283}
284
285
286template <class T>
287void List<T>::removeFirst()
288{
289    if ( first )
290    {
291        _length--;
292        if ( first == last )
293        {
294            delete first;
295            first = last = 0;
296        }
297        else
298        {
299            ListItem<T> *dummy = first;
300            first->next->prev = 0;
301            first = first->next;
302            delete dummy;
303        }
304    }
305}
306
307
308template <class T>
309T List<T>::getLast() const
310{
311    ASSERT( first, "List: no item available" );
312    return last->getItem();
313}
314
315
316template <class T>
317void List<T>::removeLast()
318{
319    if ( last )
320    {
321        _length--;
322        if ( first == last )
323        {
324            delete last;
325            first = last = 0;
326        }
327        else
328        {
329            ListItem<T> *dummy = last;
330            last->prev->next = 0;
331            last = last->prev;
332            delete dummy;
333        }
334    }
335}
336
337
338template <class T>
339void List<T>::sort( int (*swapit) ( const T&, const T& ) )
340{
341    if ( first != last )
342    {
343        int swap;
344        do
345        {
346            swap = 0;
347            ListItem<T> *cur = first;
348            while ( cur->next )
349            {
350                if ( swapit( *(cur->item), *(cur->next->item) ) )
351                {
352                    T* dummy = cur->item;
353                    cur->item = cur->next->item;
354                    cur->next->item = dummy;
355                    swap = 1;
356                }
357                cur = cur->next;
358            }
359        } while (swap);
360    }
361}
362
363
364#ifndef NOSTREAMIO
365template <class T>
366void List<T>::print ( OSTREAM & os ) const
367{
368    ListItem<T> *cur = first;
369    os << "( ";
370    while ( cur )
371    {
372        cur->print( os );
373        if ( (cur = cur->getNext()) )
374            os << ", ";
375    }
376    os << " )";
377}
378#endif /* NOSTREAMIO */
379
380
381template <class T>
382ListIterator<T>::ListIterator()
383{
384    theList = 0;
385    current = 0;
386}
387
388
389template <class T>
390ListIterator<T>::ListIterator ( const ListIterator<T> & i )
391{
392    theList = i.theList;
393    current = i.current;
394}
395
396
397template <class T>
398ListIterator<T>::ListIterator ( const List<T> & l )
399{
400    theList = (List<T>*)&l;
401    current = l.first;
402}
403
404
405template <class T>
406ListIterator<T>::~ListIterator() { }
407
408
409template <class T>
410ListIterator<T>& ListIterator<T>::operator= ( const ListIterator<T> & I )
411{
412    if ( this != &I )
413    {
414        theList = I.theList;
415        current = I.current;
416    }
417    return *this;
418}
419
420
421template <class T>
422ListIterator<T>& ListIterator<T>::operator= ( const List<T> & l )
423{
424    theList = (List<T>*)&l;
425    current = l.first;
426    return *this;
427}
428
429
430template <class T>
431T& ListIterator<T>::getItem () const
432{
433    ASSERT( current, "ListIterator: no item available" );
434    return current->getItem();
435}
436
437
438template <class T>
439int ListIterator<T>::hasItem ()
440{
441    return current != 0;
442}
443
444
445template <class T>
446void ListIterator<T>::operator++ ()
447{
448    if ( current )
449        current = current->next;
450}
451
452
453template <class T>
454void ListIterator<T>::operator-- ()
455{
456    if ( current )
457        current = current->prev;
458}
459
460
461template <class T>
462void ListIterator<T>::operator++ ( int )
463{
464    if ( current )
465        current = current->next;
466}
467
468
469template <class T>
470void ListIterator<T>::operator-- ( int )
471{
472    if ( current )
473        current = current->prev;
474}
475
476
477template <class T>
478void ListIterator<T>::firstItem ()
479{
480    current = theList->first;
481}
482
483
484template <class T>
485void ListIterator<T>::lastItem ()
486{
487    current = theList->last;
488}
489
490
491template <class T>
492void ListIterator<T>::insert ( const T & t )
493{
494    if ( current )
495    {
496        if ( ! current->prev )
497            theList->insert( t );
498        else
499        {
500            current->prev = new ListItem<T>( t, current, current->prev );
501            current->prev->prev->next = current->prev;
502            theList->_length++;
503        }
504    }
505}
506
507
508template <class T>
509void ListIterator<T>::append ( const T & t )
510{
511    if ( current )
512    {
513        if ( ! current->next )
514            theList->append( t );
515        else
516        {
517            current->next = new ListItem<T>( t, current->next, current );
518            current->next->next->prev = current->next;
519            theList->_length++;
520        }
521    }
522}
523
524
525template <class T>
526void ListIterator<T>::remove ( int moveright )
527{
528    if ( current )
529    {
530        ListItem <T>*dummynext = current->next, *dummyprev = current->prev;
531        if ( current->prev )
532        {
533            current->prev->next = current->next;
534            if ( current->next )
535                current->next->prev = current->prev;
536            else
537                theList->last = current->prev;
538            delete current;
539            current = ( moveright ) ? dummynext : dummyprev;
540        }
541        else
542        {
543            if ( current->next )
544                current->next->prev = 0;
545            theList->first = current->next;
546            delete current;
547            current = ( moveright ) ? dummynext : dummyprev;
548        }
549        theList->_length--;
550    }
551}
552
553#ifndef NOSTREAMIO
554template <class T>
555OSTREAM& operator<<( OSTREAM & os, const List<T> & l )
556{
557    l.print( os );
558    return os;
559}
560#endif /* NOSTREAMIO */
561
562template <class T>
563List<T> Union ( const List<T> & F, const List<T> & G )
564{
565    List<T> L = G;
566    ListIterator<T> i, j;
567    T f;
568    bool iselt;
569
570    for ( i = F; i.hasItem(); i++ )
571    {
572        f = i.getItem();
573        iselt = false;
574        j = G;
575        while ( ( ! iselt ) && j.hasItem() )
576        {
577            iselt =  f == j.getItem();
578            j++;
579        }
580        if ( ! iselt )
581            L.append( f );
582    }
583    return L;
584}
585
586template <class T>
587List<T> Union ( const List<T> & F, const List<T> & G, int (*cmpf)( const T&, const T& ), void (*insf)( T&, const T& ) )
588{
589    List<T> L = G;
590    ListIterator<T> i;
591
592    for ( i = F; i.hasItem(); ++i )
593        L.insert( i.getItem(), cmpf, insf );
594    return L;
595}
596
597template <class T>
598List<T> Union ( const List<T> & F, const List<T> & G, int (*ecmpf)( const T&, const T& ))
599{
600    List<T> L = G;
601    ListIterator<T> i, j;
602    T f;
603    bool iselt;
604
605    for ( i = F; i.hasItem(); i++ )
606    {
607        f = i.getItem();
608        iselt = false;
609        j = G;
610        while ( ( ! iselt ) && j.hasItem() )
611        {
612            iselt =  ecmpf (f, j.getItem());
613            j++;
614        }
615        if ( ! iselt )
616            L.append( f );
617    }
618    return L;
619}
620
621template <class T>
622List<T> Difference ( const List<T> & F, const List<T> & G )
623{
624    List<T> L;
625    ListIterator<T> i, j;
626    T f;
627    int found;
628    for ( i = F; i.hasItem(); ++i )
629    {
630        f = i.getItem();
631        found = 0;
632        for ( j = G; j.hasItem() && (!found); ++j )
633            found = f == j.getItem();
634        if ( ! found )
635            L.append( f );
636    }
637    return L;
638}
639
640template <class T>
641List<T> Difference ( const List<T> & F, const List<T> & G, int (*ecmpf)( const T&, const T& ))
642{
643    List<T> L;
644    ListIterator<T> i, j;
645    T f;
646    int found;
647    for ( i = F; i.hasItem(); ++i )
648    {
649        f = i.getItem();
650        found = 0;
651        for ( j = G; j.hasItem() && (!found); ++j )
652            found = ecmpf (f, j.getItem());
653        if ( ! found )
654            L.append( f );
655    }
656    return L;
657}
658
659template <class T>
660List<T> Difference ( const List<T> & F, const T & G, int (*ecmpf)( const T&, const T& ))
661{
662    List<T> L;
663    ListIterator<T> i;
664    int found;
665    for ( i = F; i.hasItem(); ++i )
666    {
667        found = ecmpf (G, i.getItem());
668        if ( ! found )
669            L.append( i.getItem() );
670    }
671    return L;
672}
673
674template <class T>
675List<T> Difference ( const List<T> & F, const T & G)
676{
677    List<T> L;
678    ListIterator<T> i;
679    int found;
680    for ( i = F; i.hasItem(); ++i )
681    {
682        found = G == i.getItem();
683        if ( ! found )
684            L.append( i.getItem() );
685    }
686    return L;
687}
688
689template <class T>
690T prod ( const List<T> & F )
691{
692    ListIterator<T> i;
693    T p = 1;
694    for ( i = F; i.hasItem(); i++ )
695        p = p * i.getItem();
696    return p;
697}
698
699template <class T>
700bool find (const List<T> & F, const T& t)
701{
702  if (F.length() == 0) return false;
703  ListIterator<T> J= F;
704  while (J.hasItem())
705  {
706    if (J.getItem() == t)
707      return true;
708    J++;
709  }
710  return false;
711}
712
713template <class T>
714bool find (const List<T> & F, const T& t, int (*ecmpf)( const T&, const T& ))
715{
716  if (F.length() == 0) return false;
717  ListIterator<T> J= F;
718  while (J.hasItem())
719  {
720    if (ecmpf (J.getItem(), t))
721      return true;
722    J++;
723  }
724  return false;
725}
726
Note: See TracBrowser for help on using the repository browser.