Changeset c48e80 in git for factory/templates


Ignore:
Timestamp:
Oct 28, 2009, 3:45:57 PM (14 years ago)
Author:
Hans Schönemann <hannes@…>
Branches:
(u'spielwiese', '5b153614cbc72bfa198d75b1e9e33dab2645d9fe')
Children:
f5d2963eec6952b42517b3865c98f0a7ddedae43
Parents:
cc051cf43fa6076737b5f7a6d4dc074ad8db1fbe
Message:
*lee: new gcd


git-svn-id: file:///usr/local/Singular/svn/trunk@12214 2c84dea3-7e68-4137-9b89-c4e89433aadc
Location:
factory/templates
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • factory/templates/ftmpl_list.cc

    rcc051cf rc48e80  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: ftmpl_list.cc,v 1.9 2006-05-15 09:03:07 Singular Exp $ */
     2/* $Id: ftmpl_list.cc,v 1.10 2009-10-28 14:42:23 Singular Exp $ */
    33
    44#include <factoryconf.h>
     
    4747ListItem<T>& ListItem<T>::operator=( const ListItem<T>& i )
    4848{
    49     if ( this != &i ) {
    50         next = i.next;
    51         prev = i.prev;
    52         item = i.item;
     49    if ( this != &i )
     50    {
     51        next = i.next;
     52        prev = i.prev;
     53        item = i.item;
    5354    }
    5455    return *this;
     
    8182{
    8283    if ( item )
    83         os << *item;
     84        os << *item;
    8485    else
    85         os << "(no item)";
     86        os << "(no item)";
    8687}
    8788#endif /* NOSTREAMIO */
     
    101102{
    102103    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;
     104    if ( cur )
     105    {
     106        first = new ListItem<T>( *(cur->item), 0, 0 );
     107        last = first;
     108        cur = cur->prev;
     109        while ( cur )
     110        {
     111            first = new ListItem<T>( *(cur->item), first, 0 );
     112            first->next->prev = first;
     113            cur = cur->prev;
     114        }
     115        _length = l._length;
     116    }
     117    else
     118    {
     119        first = last = 0;
     120        _length = 0;
    117121    }
    118122}
     
    131135{
    132136    ListItem<T> *dummy;
    133     while ( first ) {
    134         dummy = first;
    135         first = first->next;
    136         delete dummy;
     137    while ( first )
     138    {
     139        dummy = first;
     140        first = first->next;
     141        delete dummy;
    137142    }
    138143}
     
    142147List<T>& List<T>::operator=( const List<T>& l )
    143148{
    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;
     149    if ( this != &l )
     150    {
     151        ListItem<T> *dummy;
     152        while ( first )
     153        {
     154            dummy = first;
     155            first = first->next;
     156            delete dummy;
     157        }
     158        ListItem<T>* cur = l.last;
     159        if ( cur )
     160        {
     161            first = new ListItem<T>( *(cur->item), 0, 0 );
     162            last = first;
     163            cur = cur->prev;
     164            while ( cur )
     165            {
     166                first = new ListItem<T>( *(cur->item), first, 0 );
     167                first->next->prev = first;
     168                cur = cur->prev;
     169            }
     170            _length = l._length;
     171        }
     172        else
     173        {
     174            first = last = 0;
     175            _length = 0;
     176        }
     177        _length = l._length;
    168178    }
    169179    return *this;
     
    176186    first = new ListItem<T>( t, first, 0 );
    177187    if ( last )
    178         first->next->prev = first;
     188        first->next->prev = first;
    179189    last = ( last ) ? last : first;
    180190    _length++;
     
    186196{
    187197    if ( ! first || cmpf( *first->item, t ) > 0 )
    188         insert( t );
     198        insert( t );
    189199    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         }
     200        append( t );
     201    else
     202    {
     203        ListItem<T> * cursor = first;
     204        int c;
     205        while ( (c = cmpf( *cursor->item, t )) < 0 )
     206            cursor = cursor->next;
     207        if ( c == 0 )
     208            *cursor->item = t;
     209        else
     210        {
     211            cursor = cursor->prev;
     212            cursor->next = new ListItem<T>( t, cursor->next, cursor );
     213            cursor->next->next->prev = cursor->next;
     214            _length++;
     215        }
    204216    }
    205217}
     
    210222{
    211223    if ( ! first || cmpf( *first->item, t ) > 0 )
    212         insert( t );
     224        insert( t );
    213225    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         }
     226        append( t );
     227    else
     228    {
     229        ListItem<T> * cursor = first;
     230        int c;
     231        while ( (c = cmpf( *cursor->item, t )) < 0 )
     232            cursor = cursor->next;
     233        if ( c == 0 )
     234            insf( *cursor->item, t );
     235        else
     236        {
     237            cursor = cursor->prev;
     238            cursor->next = new ListItem<T>( t, cursor->next, cursor );
     239            cursor->next->next->prev = cursor->next;
     240            _length++;
     241        }
    228242    }
    229243}
     
    235249    last = new ListItem<T>( t, 0, last );
    236250    if ( first )
    237         last->prev->next = last;
     251        last->prev->next = last;
    238252    first = ( first ) ? first : last;
    239253    _length++;
     
    264278void List<T>::removeFirst()
    265279{
    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         }
     280    if ( first )
     281    {
     282        _length--;
     283        if ( first == last )
     284        {
     285            delete first;
     286            first = last = 0;
     287        }
     288        else
     289        {
     290            ListItem<T> *dummy = first;
     291            first->next->prev = 0;
     292            first = first->next;
     293            delete dummy;
     294        }
    278295    }
    279296}
     
    291308void List<T>::removeLast()
    292309{
    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         }
     310    if ( last )
     311    {
     312        _length--;
     313        if ( first == last )
     314        {
     315            delete last;
     316            first = last = 0;
     317        }
     318        else
     319        {
     320            ListItem<T> *dummy = last;
     321            last->prev->next = 0;
     322            last = last->prev;
     323            delete dummy;
     324        }
    305325    }
    306326}
     
    310330void List<T>::sort( int (*swapit) ( const T&, const T& ) )
    311331{
    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);
     332    if ( first != last )
     333    {
     334        int swap;
     335        do
     336        {
     337            swap = 0;
     338            ListItem<T> *cur = first;
     339            while ( cur->next )
     340            {
     341                if ( swapit( *(cur->item), *(cur->next->item) ) )
     342                {
     343                    T* dummy = cur->item;
     344                    cur->item = cur->next->item;
     345                    cur->next->item = dummy;
     346                    swap = 1;
     347                }
     348                cur = cur->next;
     349            }
     350        } while (swap);
    327351    }
    328352}
     
    335359    ListItem<T> *cur = first;
    336360    os << "( ";
    337     while ( cur ) {
    338         cur->print( os );
    339         if ( (cur = cur->getNext()) )
    340             os << ", ";
     361    while ( cur )
     362    {
     363        cur->print( os );
     364        if ( (cur = cur->getNext()) )
     365            os << ", ";
    341366    }
    342367    os << " )";
     
    376401ListIterator<T>& ListIterator<T>::operator= ( const ListIterator<T> & I )
    377402{
    378     if ( this != &I ) {
    379         theList = I.theList;
    380         current = I.current;
     403    if ( this != &I )
     404    {
     405        theList = I.theList;
     406        current = I.current;
    381407    }
    382408    return *this;
     
    412438{
    413439    if ( current )
    414         current = current->next;
     440        current = current->next;
    415441}
    416442
     
    420446{
    421447    if ( current )
    422         current = current->prev;
     448        current = current->prev;
    423449}
    424450
     
    428454{
    429455    if ( current )
    430         current = current->next;
     456        current = current->next;
    431457}
    432458
     
    436462{
    437463    if ( current )
    438         current = current->prev;
     464        current = current->prev;
    439465}
    440466
     
    457483void ListIterator<T>::insert ( const T & t )
    458484{
    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         }
     485    if ( current )
     486    {
     487        if ( ! current->prev )
     488            theList->insert( t );
     489        else
     490        {
     491            current->prev = new ListItem<T>( t, current, current->prev );
     492            current->prev->prev->next = current->prev;
     493            theList->_length++;
     494        }
    467495    }
    468496}
     
    472500void ListIterator<T>::append ( const T & t )
    473501{
    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         }
     502    if ( current )
     503    {
     504        if ( ! current->next )
     505            theList->append( t );
     506        else
     507        {
     508            current->next = new ListItem<T>( t, current->next, current );
     509            current->next->next->prev = current->next;
     510            theList->_length++;
     511        }
    482512    }
    483513}
     
    487517void ListIterator<T>::remove ( int moveright )
    488518{
    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         }
     519    if ( current )
     520    {
     521        ListItem <T>*dummynext = current->next, *dummyprev = current->prev;
     522        if ( current->prev )
     523        {
     524            current->prev->next = current->next;
     525            if ( current->next )
     526                current->next->prev = current->prev;
     527            else
     528                theList->last = current->prev;
     529            delete current;
     530            current = ( moveright ) ? dummynext : dummyprev;
     531        }
     532        else
     533        {
     534            if ( current->next )
     535                current->next->prev = 0;
     536            theList->first = current->next;
     537            delete current;
     538            current = ( moveright ) ? dummynext : dummyprev;
     539        }
    507540    }
    508541}
     
    525558    bool iselt;
    526559
    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 );
     560    for ( i = F; i.hasItem(); i++ )
     561    {
     562        f = i.getItem();
     563        iselt = false;
     564        j = G;
     565        while ( ( ! iselt ) && j.hasItem() )
     566        {
     567            iselt =  f == j.getItem();
     568            j++;
     569        }
     570        if ( ! iselt )
     571            L.append( f );
    537572    }
    538573    return L;
     
    546581
    547582    for ( i = F; i.hasItem(); ++i )
    548         L.insert( i.getItem(), cmpf, insf );
     583        L.insert( i.getItem(), cmpf, insf );
    549584    return L;
    550585}
     
    557592    T f;
    558593    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 );
     594    for ( i = F; i.hasItem(); ++i )
     595    {
     596        f = i.getItem();
     597        found = 0;
     598        for ( j = G; j.hasItem() && (!found); ++j )
     599            found = f == j.getItem();
     600        if ( ! found )
     601            L.append( f );
    566602    }
    567603    return L;
     
    574610    T p = 1;
    575611    for ( i = F; i.hasItem(); i++ )
    576         p = p * i.getItem();
     612        p = p * i.getItem();
    577613    return p;
    578614}
     615
     616template <class T>
     617bool find (const List<T> & F, const T& t)
     618{
     619  if (F.length() == 0) return false;
     620  ListIterator<T> J= F;
     621  while (J.hasItem())
     622  {
     623    if (J.getItem() == t)
     624      return true;
     625    J++;
     626  }
     627  return false;
     628}
  • factory/templates/ftmpl_list.h

    rcc051cf rc48e80  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: ftmpl_list.h,v 1.10 2006-05-15 09:03:07 Singular Exp $ */
     2/* $Id: ftmpl_list.h,v 1.11 2009-10-28 14:42:23 Singular Exp $ */
    33
    44#ifndef INCL_LIST_H
     
    124124T prod ( const List<T>& );
    125125
     126template <class T>
     127bool find (const List<T>&, const T& t);
     128
    126129#endif /* ! INCL_LIST_H */
Note: See TracChangeset for help on using the changeset viewer.