source: git/factory/templates/ftmpl_list.cc @ 9d3636

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