qsortedlist.h

Go to the documentation of this file.

/********************************************************************************
*                                                                               *
*                         An always sorted qptrlist                             *
*                                                                               *
*********************************************************************************
* Copyright (C) 2001,2002,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 QSORTEDLIST_H
#define QSORTEDLIST_H

#include <qptrlist.h>
namespace FX {
template<class type, class allocator=FX::aligned_allocator<type *, 0> > class QSortedListIterator;
template<class type, class allocator=FX::aligned_allocator<type *, 0> > class QSortedList;
template<class type, class allocator> class QSortedList : private QPtrList<type, allocator>
{
    bool findInternal(QSortedListIterator<type, allocator> *itout, int *idx, const type *d) const;
    QSortedListIterator<type, allocator> findRefInternal(const type *d) const;
public:
    explicit QSortedList(bool wantAutoDel=false) : QPtrList<type>(wantAutoDel) {}
    QSortedList(const QSortedList<type, allocator> &o) : QPtrList<type>(o) {}
    ~QSortedList()              { clear(); }
    QSortedList<type, allocator> &operator=(const QSortedList<type, allocator> &l)
            { return (QSortedList<type, allocator>&)QPtrList<type>::operator=(l); }
    FXADDMOVEBASECLASS(QSortedList, QPtrList<type>)
    bool operator==( const QSortedList<type, allocator> &list ) const
    { return QPtrList<type>::operator==( list ); }

    using QPtrList<type>::autoDelete;
    using QPtrList<type>::setAutoDelete;
    using QPtrList<type>::count;
    using QPtrList<type>::isEmpty;
    using QPtrList<type>::removeByIter;
    using QPtrList<type>::removeFirst;
    using QPtrList<type>::removeLast;
    using QPtrList<type>::takeByIter;
    using QPtrList<type>::takeFirst;
    using QPtrList<type>::takeLast;
    using QPtrList<type>::clear;
    using QPtrList<type>::contains;
    using QPtrList<type>::containsRef;
    using QPtrList<type>::at;
    using QPtrList<type>::getFirst;
    using QPtrList<type>::getLast;
    using QPtrList<type>::first;
    using QPtrList<type>::last;
    virtual int compareItems(type *a, type *b) const;
    bool remove(const type *d);
    bool removeRef(const type *d);
    bool take(const type *d);
    bool takeRef(const type *d);
    int find(const type *d) const { int idx; if(findInternal(0, &idx, d)) return idx; else return -1; }
    QSortedListIterator<type, allocator> findIter(const type *d) const;
    type *findP(const type *d) const;
    int findClosest(const type *d) const { int idx; findInternal(0, &idx, d); return idx; }
    QSortedListIterator<type, allocator> findClosestIter(const type *d) const;
    type *findClosestP(const type *d) const;
    bool insert(const type *d);
    void merge(QSortedList<type, allocator> &list, bool exclusive=false);
};

template<class type, class allocator> inline int QSortedList<type, allocator>::compareItems(type *a, type *b) const
{
    if(*a==*b) return 0;
    return (*a<*b) ? -1 : 1;
    //if(*((QSortedListItem<type> *) s1)==*((QSortedListItem<type> *) s2)) return 0;
    //return (*((QSortedListItem<type> *) s1)<*((QSortedListItem<type> *) s2) ? -1 : 1 );
}
template<> inline int QSortedList<void>::compareItems(void *a, void *b) const
{
    if(a==b) return 0;
    return (a<b) ? -1 : 1;
}

template<class type, class allocator> class QSortedListIterator : public QPtrListIterator<type, allocator>
{
public:
    QSortedListIterator() { }
    QSortedListIterator(const QSortedList<type, allocator> &l)
        : QPtrListIterator<type, allocator>((const QPtrList<type, allocator> &) l) {}
    QSortedListIterator<type, allocator> &makeDead()
    {
        return static_cast<QSortedListIterator<type, allocator> &>(QPtrListIterator<type, allocator>::makeDead());
    }
};

template<class type, class allocator> inline QSortedListIterator<type, allocator> QSortedList<type, allocator>::findRefInternal(const type *d) const
{
    QSortedListIterator<type, allocator> it;
    if(!findInternal(&it, 0, d)) return it.makeDead();
    QSortedListIterator<type, allocator> it1(it), it2(it);
    type *a;
    // Step backwards while comparitor is equal
    for(--it; (a=it.current()) && !compareItems(const_cast<type *>(d), a); it1=it, --it);
    for(it=it1; (a=it.current()); ++it)
    {
        if(a==d) return it;
        if(it==it2) break;
    }
    // Step forwards while comparitor is equal
    for(; (a=it.current()) && !compareItems(const_cast<type *>(d), a); ++it)
    {
        if(a==d) return it;
    }
    return it.makeDead();
}

template<class type, class allocator> inline bool QSortedList<type, allocator>::remove(const type *d)
{
    QSortedListIterator<type, allocator> it;
    if(!findInternal(&it, 0, d)) return false;
    return QPtrList<type>::removeByIter(it);
}

template<class type, class allocator> inline bool QSortedList<type, allocator>::removeRef(const type *d)
{
    QSortedListIterator<type, allocator> it(findRefInternal(d));
    if(!it.current()) return false;
    return QPtrList<type>::removeByIter(it);
}

template<class type, class allocator> inline bool QSortedList<type, allocator>::take(const type *d)
{
    QSortedListIterator<type, allocator> it;
    if(!findInternal(&it, 0, d)) return false;
    return QPtrList<type>::takeByIter(it);
}

template<class type, class allocator> inline bool QSortedList<type, allocator>::takeRef(const type *d)
{
    QSortedListIterator<type, allocator> it(findRefInternal(d));
    if(!it.current()) return false;
    return QPtrList<type>::takeByIter(it);
}

template<class type, class allocator> inline QSortedListIterator<type, allocator> QSortedList<type, allocator>::findIter(const type *d) const
{
    QSortedListIterator<type, allocator> it;
    if(!findInternal(&it, 0, d))
        it.makeDead();
    return it;
}

template<class type, class allocator> inline type *QSortedList<type, allocator>::findP(const type *d) const
{
    QSortedListIterator<type, allocator> it;
    if(!findInternal(&it, 0, d)) return 0;
    return it.current();
}

template<class type, class allocator> inline QSortedListIterator<type, allocator> QSortedList<type, allocator>::findClosestIter(const type *d) const
{
    QSortedListIterator<type, allocator> it;
    findInternal(&it, 0, d);
    return it;
}

template<class type, class allocator> inline type *QSortedList<type, allocator>::findClosestP(const type *d) const
{
    QSortedListIterator<type, allocator> it;
    findInternal(&it, 0, d);
    return it.current();
}

template<class type, class allocator> inline bool QSortedList<type, allocator>::insert(const type *d)
{
    QSortedListIterator<type, allocator> it;
    findInternal(&it, 0, d);
    return QPtrList<type>::insertAtIter(it, d);
}

template<class type, class allocator> inline bool QSortedList<type, allocator>::findInternal(QSortedListIterator<type, allocator> *itout, int *idx, const type *d) const
{
    int n=0;
    QSortedListIterator<type, allocator> it(*this); it.toFirst();
    int lbound=0, ubound=count()-1, c;
    //if(lbound<0) lbound=0;
    while(lbound<=ubound)
    {
        int result;
        const type *testpoint;
        c=(lbound+ubound)/2;
        if(c-n>0) { testpoint=it+=(c-n); n=c; }
        else if(c-n<0) { testpoint=it-=(n-c); n=c; }
        else testpoint=it.current();
        // Unfortunate that I have to do this, but compareItems() should really be const
        QSortedList<type, allocator> *t=const_cast<QSortedList<type, allocator> *>(this);
        result=t->compareItems(const_cast<type *>(d), const_cast<type *>(testpoint));
        if(result<0)
            ubound=c-1;
        else if(result>0)
            lbound=c+1;
        else
        {
            if(itout) *itout=it;
            if(idx) *idx=n;
            return true;
        }
    }
    if(itout)
    {
        if(lbound!=n) it+=(lbound-n);
        *itout=it;
    }
    if(idx) *idx=lbound;
    return false;
}

template<class type, class allocator> inline void QSortedList<type, allocator>::merge(QSortedList<type, allocator> &list, bool exclusive)
{
    QSortedListIterator<type, allocator> it;
    type *ne;
    for(QSortedListIterator<type, allocator> nit(list); (ne=nit.current());)
    {
        QSortedListIterator<type, allocator> nit2(nit); ++nit;
        if(findInternal(&it, 0, ne) && exclusive)
            QPtrList<type>::removeByIter(nit2);
        else
        {   // Might as well splice as it avoids malloc
            std::list<type *, allocator>::splice(it.int_getIterator(), static_cast<std::list<type *, allocator> &>(list), nit2.int_getIterator());
            //QPtrList<type>::insertAtIter(it, ne);
            //list.takeByIter(nit2);
        }
    }
}

template<class type, class allocator> FXStream &operator<<(FXStream &s, const QSortedList<type, allocator> &i)
{
    FXuint mysize=i.count();
    s << mysize;
    for(QSortedListIterator<type, allocator> it(i); it.current(); ++it)
    {
        s << *it.current();
    }
    return s;
}
template<class type, class allocator> FXStream &operator>>(FXStream &s, QSortedList<type, allocator> &i)
{
    QPtrList<type, allocator> &ii=(QPtrList<type, allocator> &) i;
    FXuint mysize;
    s >> mysize;
    i.clear();
    for(FXuint n=0; n<mysize; n++)
    {
        type *item;
        FXERRHM(item=new type);
        s >> *item;
        ii.append(item);
    }
    return s;
}


} // namespace

#endif

---

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