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

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