source: git/factory/templates/ftmpl_list.cc @ 362fc67

jengelh-datetimespielwiese
Last change on this file since 362fc67 was 362fc67, checked in by Martin Lee <martinlee84@…>, 11 years ago
chg: remove $Id$
  • Property mode set to 100644
File size: 11.1 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
175
176template <class T>
177void List<T>::insert ( const T& t )
178{
179    first = new ListItem<T>( t, first, 0 );
180    if ( last )
181        first->next->prev = first;
182    last = ( last ) ? last : first;
183    _length++;
184}
185
186
187template <class T>
188void List<T>::insert ( const T& t, int (*cmpf)( const T&, const T& ) )
189{
190    if ( ! first || cmpf( *first->item, t ) > 0 )
191        insert( t );
192    else if ( cmpf( *last->item, t ) < 0 )
193        append( t );
194    else
195    {
196        ListItem<T> * cursor = first;
197        int c;
198        while ( (c = cmpf( *cursor->item, t )) < 0 )
199            cursor = cursor->next;
200        if ( c == 0 )
201            *cursor->item = t;
202        else
203        {
204            cursor = cursor->prev;
205            cursor->next = new ListItem<T>( t, cursor->next, cursor );
206            cursor->next->next->prev = cursor->next;
207            _length++;
208        }
209    }
210}
211
212
213template <class T>
214void List<T>::insert ( const T& t, int (*cmpf)( const T&, const T& ), void (*insf)( T&, const T& ) )
215{
216    if ( ! first || cmpf( *first->item, t ) > 0 )
217        insert( t );
218    else if ( cmpf( *last->item, t ) < 0 )
219        append( t );
220    else
221    {
222        ListItem<T> * cursor = first;
223        int c;
224        while ( (c = cmpf( *cursor->item, t )) < 0 )
225            cursor = cursor->next;
226        if ( c == 0 )
227            insf( *cursor->item, t );
228        else
229        {
230            cursor = cursor->prev;
231            cursor->next = new ListItem<T>( t, cursor->next, cursor );
232            cursor->next->next->prev = cursor->next;
233            _length++;
234        }
235    }
236}
237
238
239template <class T>
240void List<T>::append ( const T& t )
241{
242    last = new ListItem<T>( t, 0, last );
243    if ( first )
244        last->prev->next = last;
245    first = ( first ) ? first : last;
246    _length++;
247}
248
249
250template <class T>
251int List<T>::isEmpty() const
252{
253    return ( first == 0 );
254}
255
256template <class T>
257int List<T>::length() const
258{
259    return _length;
260}
261
262template <class T>
263T List<T>::getFirst() const
264{
265    ASSERT( first, "List: no item available" );
266    return first->getItem();
267}
268
269
270template <class T>
271void List<T>::removeFirst()
272{
273    if ( first )
274    {
275        _length--;
276        if ( first == last )
277        {
278            delete first;
279            first = last = 0;
280        }
281        else
282        {
283            ListItem<T> *dummy = first;
284            first->next->prev = 0;
285            first = first->next;
286            delete dummy;
287        }
288    }
289}
290
291
292template <class T>
293T List<T>::getLast() const
294{
295    ASSERT( first, "List: no item available" );
296    return last->getItem();
297}
298
299
300template <class T>
301void List<T>::removeLast()
302{
303    if ( last )
304    {
305        _length--;
306        if ( first == last )
307        {
308            delete last;
309            first = last = 0;
310        }
311        else
312        {
313            ListItem<T> *dummy = last;
314            last->prev->next = 0;
315            last = last->prev;
316            delete dummy;
317        }
318    }
319}
320
321
322template <class T>
323void List<T>::sort( int (*swapit) ( const T&, const T& ) )
324{
325    if ( first != last )
326    {
327        int swap;
328        do
329        {
330            swap = 0;
331            ListItem<T> *cur = first;
332            while ( cur->next )
333            {
334                if ( swapit( *(cur->item), *(cur->next->item) ) )
335                {
336                    T* dummy = cur->item;
337                    cur->item = cur->next->item;
338                    cur->next->item = dummy;
339                    swap = 1;
340                }
341                cur = cur->next;
342            }
343        } while (swap);
344    }
345}
346
347
348#ifndef NOSTREAMIO
349template <class T>
350void List<T>::print ( OSTREAM & os ) const
351{
352    ListItem<T> *cur = first;
353    os << "( ";
354    while ( cur )
355    {
356        cur->print( os );
357        if ( (cur = cur->getNext()) )
358            os << ", ";
359    }
360    os << " )";
361}
362#endif /* NOSTREAMIO */
363
364
365template <class T>
366ListIterator<T>::ListIterator()
367{
368    theList = 0;
369    current = 0;
370}
371
372
373template <class T>
374ListIterator<T>::ListIterator ( const ListIterator<T> & i )
375{
376    theList = i.theList;
377    current = i.current;
378}
379
380
381template <class T>
382ListIterator<T>::ListIterator ( const List<T> & l )
383{
384    theList = (List<T>*)&l;
385    current = l.first;
386}
387
388
389template <class T>
390ListIterator<T>::~ListIterator() { }
391
392
393template <class T>
394ListIterator<T>& ListIterator<T>::operator= ( const ListIterator<T> & I )
395{
396    if ( this != &I )
397    {
398        theList = I.theList;
399        current = I.current;
400    }
401    return *this;
402}
403
404
405template <class T>
406ListIterator<T>& ListIterator<T>::operator= ( const List<T> & l )
407{
408    theList = (List<T>*)&l;
409    current = l.first;
410    return *this;
411}
412
413
414template <class T>
415T& ListIterator<T>::getItem () const
416{
417    ASSERT( current, "ListIterator: no item available" );
418    return current->getItem();
419}
420
421
422template <class T>
423int ListIterator<T>::hasItem ()
424{
425    return current != 0;
426}
427
428
429template <class T>
430void ListIterator<T>::operator++ ()
431{
432    if ( current )
433        current = current->next;
434}
435
436
437template <class T>
438void ListIterator<T>::operator-- ()
439{
440    if ( current )
441        current = current->prev;
442}
443
444
445template <class T>
446void ListIterator<T>::operator++ ( int )
447{
448    if ( current )
449        current = current->next;
450}
451
452
453template <class T>
454void ListIterator<T>::operator-- ( int )
455{
456    if ( current )
457        current = current->prev;
458}
459
460
461template <class T>
462void ListIterator<T>::firstItem ()
463{
464    current = theList->first;
465}
466
467
468template <class T>
469void ListIterator<T>::lastItem ()
470{
471    current = theList->last;
472}
473
474
475template <class T>
476void ListIterator<T>::insert ( const T & t )
477{
478    if ( current )
479    {
480        if ( ! current->prev )
481            theList->insert( t );
482        else
483        {
484            current->prev = new ListItem<T>( t, current, current->prev );
485            current->prev->prev->next = current->prev;
486            theList->_length++;
487        }
488    }
489}
490
491
492template <class T>
493void ListIterator<T>::append ( const T & t )
494{
495    if ( current )
496    {
497        if ( ! current->next )
498            theList->append( t );
499        else
500        {
501            current->next = new ListItem<T>( t, current->next, current );
502            current->next->next->prev = current->next;
503            theList->_length++;
504        }
505    }
506}
507
508
509template <class T>
510void ListIterator<T>::remove ( int moveright )
511{
512    if ( current )
513    {
514        ListItem <T>*dummynext = current->next, *dummyprev = current->prev;
515        if ( current->prev )
516        {
517            current->prev->next = current->next;
518            if ( current->next )
519                current->next->prev = current->prev;
520            else
521                theList->last = current->prev;
522            delete current;
523            current = ( moveright ) ? dummynext : dummyprev;
524        }
525        else
526        {
527            if ( current->next )
528                current->next->prev = 0;
529            theList->first = current->next;
530            delete current;
531            current = ( moveright ) ? dummynext : dummyprev;
532        }
533        theList->_length--;
534    }
535}
536
537#ifndef NOSTREAMIO
538template <class T>
539OSTREAM& operator<<( OSTREAM & os, const List<T> & l )
540{
541    l.print( os );
542    return os;
543}
544#endif /* NOSTREAMIO */
545
546template <class T>
547List<T> Union ( const List<T> & F, const List<T> & G )
548{
549    List<T> L = G;
550    ListIterator<T> i, j;
551    T f;
552    bool iselt;
553
554    for ( i = F; i.hasItem(); i++ )
555    {
556        f = i.getItem();
557        iselt = false;
558        j = G;
559        while ( ( ! iselt ) && j.hasItem() )
560        {
561            iselt =  f == j.getItem();
562            j++;
563        }
564        if ( ! iselt )
565            L.append( f );
566    }
567    return L;
568}
569
570template <class T>
571List<T> Union ( const List<T> & F, const List<T> & G, int (*cmpf)( const T&, const T& ), void (*insf)( T&, const T& ) )
572{
573    List<T> L = G;
574    ListIterator<T> i;
575
576    for ( i = F; i.hasItem(); ++i )
577        L.insert( i.getItem(), cmpf, insf );
578    return L;
579}
580
581template <class T>
582List<T> Difference ( const List<T> & F, const List<T> & G )
583{
584    List<T> L;
585    ListIterator<T> i, j;
586    T f;
587    int found;
588    for ( i = F; i.hasItem(); ++i )
589    {
590        f = i.getItem();
591        found = 0;
592        for ( j = G; j.hasItem() && (!found); ++j )
593            found = f == j.getItem();
594        if ( ! found )
595            L.append( f );
596    }
597    return L;
598}
599
600template <class T>
601T prod ( const List<T> & F )
602{
603    ListIterator<T> i;
604    T p = 1;
605    for ( i = F; i.hasItem(); i++ )
606        p = p * i.getItem();
607    return p;
608}
609
610template <class T>
611bool find (const List<T> & F, const T& t)
612{
613  if (F.length() == 0) return false;
614  ListIterator<T> J= F;
615  while (J.hasItem())
616  {
617    if (J.getItem() == t)
618      return true;
619    J++;
620  }
621  return false;
622}
Note: See TracBrowser for help on using the repository browser.