qvaluelist.h

Go to the documentation of this file.

/********************************************************************************
*                                                                               *
*                   Q t   V a l u e   L i s t   T h u n k                       *
*                                                                               *
*********************************************************************************
* Copyright (C) 2003 by Niall Douglas.   All Rights Reserved.                   *
*       NOTE THAT I DO NOT PERMIT ANY OF MY CODE TO BE PROMOTED TO THE GPL      *
*********************************************************************************
* This code is free software; you can redistribute it and/or modify it under    *
* the terms of the GNU Library General Public License v2.1 as published by the  *
* Free Software Foundation EXCEPT that clause 3 does not apply ie; you may not  *
* "upgrade" this code to the GPL without my prior written permission.           *
* Please consult the file "License_Addendum2.txt" accompanying this file.       *
*                                                                               *
* This code 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.                          *
*********************************************************************************
* $Id:                                                                          *
********************************************************************************/

#ifndef QVALUELIST_H
#define QVALUELIST_H

#if _MSC_VER==1200
#pragma warning(disable: 4786)
#endif

#include <list>
#undef Unsorted
#include "fxdefs.h"
#include "FXException.h"
#include "FXPolicies.h"
#include "FXStream.h"

namespace FX {

typedef FXuint uint;

template<class type> class QValueList : public std::list<type>
{
public:
    QValueList() : std::list<type>() { }
    QValueList(const std::list<type> &l) : std::list<type>(l) { }
    FXADDMOVEBASECLASS(QValueList, std::list<type>)
    void remove(const type &d) { std::list<type>::remove(d); }
    uint removeAllOf(const type &d)
    {
        uint count=0;
        for(typename std::list<type>::iterator it=std::list<type>::begin(); it!=std::list<type>::end(); ++it)
        {
            if(*it==d) count++;
        }
        for(uint n=0; n<count; n++)
            std::list<type>::remove(d);
        return count;
    }
    bool isEmpty() const { return std::list<type>::empty(); }
    typename std::list<type>::iterator append(const type &d) { FXEXCEPTION_STL1 { std::list<type>::push_back(d); } FXEXCEPTION_STL2; return --std::list<type>::end(); }
    typename std::list<type>::iterator append(const QValueList &l)
    {
        FXEXCEPTION_STL1 {
            for(typename std::list<type>::const_iterator it=l.begin(); it!=l.end(); ++it)
            {
                std::list<type>::push_back(*it);
            }
        } FXEXCEPTION_STL2;
        return --std::list<type>::end();
    }
    typename std::list<type>::iterator prepend(const type &d) { FXEXCEPTION_STL1 { std::list<type>::push_front(d); } FXEXCEPTION_STL2; return std::list<type>::begin(); }
    typename std::list<type>::iterator remove(typename std::list<type>::iterator it) { typename std::list<type>::iterator itafter=it; ++itafter; std::list<type>::erase(it); return itafter; }
    typename std::list<type>::iterator at(typename std::list<type>::size_type i) { typename std::list<type>::iterator it; for(it=std::list<type>::begin(); i; --i, ++it); return it; }
    typename std::list<type>::const_iterator at(typename std::list<type>::size_type i) const { typename std::list<type>::const_iterator it; for(it=std::list<type>::begin(); i; --i, ++it); return it; }
    type &operator[](typename std::list<type>::size_type i) { return *at(i); }
    const type &operator[](typename std::list<type>::size_type i) const { return *at(i); }
    typename std::list<type>::iterator find(const type &d)
    {
        typename std::list<type>::iterator it;
        for(it=std::list<type>::begin(); it!=std::list<type>::end(); ++it)
            if(*it==d) return it;
        return it;
    }
    typename std::list<type>::const_iterator find(const type &d) const
    {
        typename std::list<type>::const_iterator it;
        for(it=std::list<type>::begin(); it!=std::list<type>::end(); ++it)
            if(*it==d) return it;
        return it;
    }
    typename std::list<type>::iterator find(typename std::list<type>::iterator it, const type &d)
    {
        for(; it!=std::list<type>::end(); ++it)
            if(*it==d) return it;
        return it;
    }
    typename std::list<type>::const_iterator find(typename std::list<type>::const_iterator it, const type &d) const
    {
        for(; it!=std::list<type>::end(); ++it)
            if(*it==d) return it;
        return it;
    }
    int findIndex(const type &d) const
    {
        int idx=0;
        for(typename std::list<type>::const_iterator it=std::list<type>::begin(); it!=std::list<type>::end(); ++it, ++idx)
            if(*it==d) return idx;
        return -1;
    }
    typename std::list<type>::size_type contains(const type &d) const
    {
        typename std::list<type>::size_type count=0;
        for(typename std::list<type>::const_iterator it=std::list<type>::begin(); it!=std::list<type>::end(); ++it)
            if(*it==d) count++;
        return count;
    }
    typename std::list<type>::size_type count() const { return std::list<type>::size(); }
    QValueList<type> &operator+=(const type &d) { std::list<type>::push_back(d); return *this; }

};

// Unfortunately GCC doesn't like templated typedefs (at last one area MSVC wins!)
//template<class type> typedef typename std::list<type>::iterator QValueListIterator;
//template<class type> typedef typename std::list<type>::const_iterator QValueListConstIterator;

template<class type> class QValueListIterator : public std::list<type>::iterator
{
public:
    QValueListIterator() : std::list<type>::iterator() { }
    QValueListIterator(const QValueListIterator &o) : std::list<type>::iterator(o) { }
};
template<class type> class QValueListConstIterator : public std::list<type>::const_iterator
{
public:
    QValueListConstIterator() : std::list<type>::const_iterator() { }
    QValueListConstIterator(const QValueListConstIterator &o) : std::list<type>::const_iterator(o) { }
};

template<class type> FXStream &operator<<(FXStream &s, const QValueList<type> &i)
{
    FXuint mysize=(FXuint) i.count();
    s << mysize;
    for(typename QValueList<type>::const_iterator it=i.begin(); it!=i.end(); ++it)
    {
        s << *it;
    }
    return s;
}
template<class type> FXStream &operator>>(FXStream &s, QValueList<type> &i)
{
    FXuint mysize;
    s >> mysize;
    i.clear();
    for(FXuint n=0; n<mysize; n++)
    {
        type item;
        s >> item;
        i.append(item);
    }
    return s;
}

enum QVLQSortType
{
    QVLQSortDefault=0,      
    QVLQSortInsertion=1,    
    QVLQSortMerge=2,        
    QVLQSortQuick=4,        

    QVLQSortStable=256      
};
template<class type,
    template<class> class movePolicy=Pol::itMove,
    template<class> class swapPolicy=Pol::itSwap,
    template<class> class comparePolicy=Pol::itCompare>
class QValueListQSort : public movePolicy<type>, public swapPolicy<type>, public comparePolicy<type>
{
    static const int insertionCutOff=12, mergeCutOff=12; //40000;
public:
    typedef QValueList<type> list;
    typedef typename list::iterator iterator;
protected:
    typedef std::pair<int, iterator> intit;
    mutable list &mylist;
    int sorttype;
public:
    QValueListQSort(QValueList<type> &list, int _sorttype=QVLQSortDefault)
        : mylist(list), sorttype(_sorttype) { }
    void run(int _sorttype=QVLQSortDefault)
    {
        if(mylist.empty()) return;
        if(QVLQSortDefault!=sorttype) sorttype=_sorttype;
        if(!sorttype) sorttype=QVLQSortInsertion|QVLQSortMerge|QVLQSortQuick;
        int s=(int) mylist.size();
        if(s>mergeCutOff && (sorttype & QVLQSortQuick) && !(sorttype & QVLQSortStable))
        {
            intit l=std::make_pair(0, mylist.begin());
            intit u=std::make_pair(s, mylist.end());
            qsort(l, u);
        }
        //else if(s>insertionCutOff && (sorttype & QVLQSortMerge))
        //{
        //  msort();
        //}
        else
        {
            iterator l=mylist.begin(), u=mylist.end();
            isort(l, u);
        }
    }
private:
    void isort(iterator &lb, iterator &ub)
    {   // Niall's bastard iterator based insertion sort
        for(iterator it=lb;;)
        {
            iterator prev=it;
            if(++it==ub) break;
            if(comparePolicy<type>::compare(mylist, it, prev))
            {
                bool found=false;
                iterator find=lb;
                for(; find!=ub; ++find)
                {
                    if(find!=it && comparePolicy<type>::compare(mylist, it, find))
                    {
                        bool atStart=(find==lb);
                        move(mylist, find, it);
                        if(atStart) lb=it;
                        found=true;
                        break;
                    }
                }
                if(!found) movePolicy<type>::move(mylist, find, it);
            }
        }
    }
    inline void merge(int len, intit &_lb, intit &_m, intit &_ub)
    {
        bool updlb=true, updm=true, updub=true;
        iterator lb=_lb.second, m=_m.second, ub=_ub.second;
        while(true)
        {
            // To be completed
        }
    }
    void msort(intit &_lb, intit &_ub)
    {
        int len=(_ub.first-_lb.first);
        if(len<=2) return;
        int mididx=len>>1;
        iterator it=_lb.second;
        int idx;
        for(idx=_lb.first; idx<mididx; ++it, ++idx);
        intit m=std::make_pair(idx, it);
        msort(_lb, m);
        msort(m, _ub);
        merge(len, _lb, m, _ub);
    }
    inline intit partition(intit &_lb, intit &_ub)
    {
        bool updlb=true;
        int lbidx=_lb.first, ubidx=_ub.first;
        iterator lb(_lb.second), ub(_ub.second);
        while(true)
        {
            while(lbidx<ubidx && comparePolicy<type>::compare(mylist, _lb.second, (--ubidx, --ub)));
            while(lbidx<ubidx && comparePolicy<type>::compare(mylist, (updlb=false, ++lbidx, ++lb), _lb.second));
            if(lbidx>=ubidx) break;
            swapPolicy<type>::swap(mylist, lb, ub);
            if(updlb) _lb.second=lb;
        }
        if(_lb.second!=ub)
        {
            swapPolicy<type>::swap(mylist, _lb.second, ub);
        }
        return std::make_pair(ubidx, ub);
    }
    void qsort(intit &_lb, intit &_ub)
    {
        bool updlb=true, updub=true;
        intit lb(_lb), ub(_ub);
        while(lb.first<ub.first)
        {
            if(ub.first-lb.first<=insertionCutOff)
            {
                isort(lb.second, ub.second);
                if(updlb) _lb.second=lb.second;
                if(updub) _ub.second=ub.second;
                return;
            }
            intit i=partition(lb, ub);
            if(updlb) _lb.second=lb.second;
            if(updub) _ub.second=ub.second;
            int r1=i.first-lb.first, r2=ub.first-i.first-1;
            if(r1<=r2)
            {
                if(r1>0)
                {
                    qsort(lb, i);
                    if(updlb) _lb.second=lb.second;
                }
                lb.first=i.first+1; lb.second=++i.second; updlb=false;
            }
            else
            {
                ++i.first; ++i.second;
                if(r2>0)
                {
                    qsort(i, ub);
                    if(updub) _ub.second=ub.second;
                }
                ub.first=i.first-1; ub.second=--i.second; updub=false;
            }
        }
    }
};

} // namespace

#endif

---

(C) 2002-2009 Niall Douglas. Some parts (C) to assorted authors.