~ivantis/armagetronad/sty+ct+ivantis

/*

 

*************************************************************************

 

ArmageTron -- Just another Tron Lightcycle Game in 3D.

Copyright (C) 2000  Manuel Moos (manuel@moosnet.de)

 

**************************************************************************

 

This program is free software; you can redistribute it and/or

modify it under the terms of the GNU General Public License

as published by the Free Software Foundation; either version 2

of the License, or (at your option) any later version.

 

This program is distributed in the hope that it will be useful,

but WITHOUT ANY WARRANTY; without even the implied warranty of

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

GNU General Public License for more details.

 

You should have received a copy of the GNU General Public License

along with this program; if not, write to the Free Software

Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

  

***************************************************************************

 

*/

 

#include "tLinkedList.h"

 

void tListItemBase::Remove(){

    if (anchor){

        *anchor      = next;

        if (next)

            next->anchor = anchor;

        anchor       = NULL;

        next         = NULL;

    }

}

 

void  tListItemBase::Insert(tListItemBase *&a){

    if (anchor)

        Remove();

    anchor = &a;

    next   =  a;

    a      =  this;

    if (next)

        next->anchor = &next;

}

 

int  tListItemBase::Len(){

    int ret=0;

    tListItemBase* x=this;

    while (x){

        ret++;

        x = x->next;

    }

    return ret;

}

 

void tListItemBase::Sort( Comparator* compare )

{

    // early return statements: empty list or single element in list

    if ( !this || !next )

    {

        return;

    }

 

    tListItemBase* middle = this;

    {

        // locate the middle of the list

        tListItemBase* run = *anchor;

        while ( run )

        {

            middle = middle->next;

            run          = run->next;

            if ( run )

            {

                run = run->next;

            }

        }

    }

 

    // split the list in the middle

    *middle->anchor = NULL;

    middle->anchor = &middle;

 

    // retrieve the anchor of the first half list

    tListItemBase*& first = *anchor;

 

    // sort the two half lists

    first->Sort( compare );

    middle->Sort( compare );

 

    // merge the lists

    {

        tListItemBase** run = &first;

        while ( middle )

        {

            // find the correct place for middle

            while ( *run && compare( *run, middle ) > 0 )

                run = &(*run)->next;

 

            // remove middle from the second list; care needs to be taken because middle->remove() would modify middle.

            tListItemBase* insert = middle;

            insert->Remove();

 

            // insert it into the first list

            insert->Insert( *run );

            run = &insert->next;

        }

    }

 

    // done!

}