/******************************************************************************** Copyright (C) 1992-2006 Trolltech ASA. All rights reserved.**** This file is part of the QtCore module of the Qt Toolkit.**** This file may be used under the terms of the GNU General Public** License version 2.0 as published by the Free Software Foundation** and appearing in the file LICENSE.GPL included in the packaging of** this file.  Please review the following information to ensure GNU** General Public Licensing requirements will be met:** http://www.trolltech.com/products/qt/opensource.html**** If you are unsure which license is appropriate for your use, please** review the following information:** http://www.trolltech.com/products/qt/licensing.html or contact the** sales department at sales@trolltech.com.**** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.******************************************************************************/#ifndef QLIST_H#define QLIST_H#include <QtCore/qiterator.h>#include <QtCore/qatomic.h>#include <QtCore/qalgorithms.h>#ifndef QT_NO_STL#include <iterator>#include <list>#endif#include <new>QT_BEGIN_HEADERQT_MODULE(Core)template <typename T> class QVector;template <typename T> class QSet;struct Q_CORE_EXPORT QListData {    struct Data {        QBasicAtomic ref;        int alloc, begin, end;        uint sharable : 1;        void *array[1];    };    enum { DataHeaderSize = sizeof(Data) - sizeof(void *) };    Data *detach();    void realloc(int alloc);    static Data shared_null;    Data *d;    void **erase(void **xi);    void **append();    void **append(const QListData &l);    void **prepend();    void **insert(int i);    void remove(int i);    void remove(int i, int n);    void move(int from, int to);    inline int size() const { return d->end - d->begin; }    inline bool isEmpty() const { return d->end  == d->begin; }    inline void **at(int i) const { return d->array + d->begin + i; }    inline void **begin() const { return d->array + d->begin; }    inline void **end() const { return d->array + d->end; }};template <typename T>class QList{    struct Node { void *v;#if defined(Q_CC_BOR)        Q_INLINE_TEMPLATE T &t();#else        Q_INLINE_TEMPLATE T &t()        { return *reinterpret_cast<T*>(QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic                                       ? v : this); }#endif    };    union { QListData p; QListData::Data *d; };public:    inline QList() : d(&QListData::shared_null) { d->ref.ref(); }    inline QList(const QList<T> &l) : d(l.d) { d->ref.ref(); if (!d->sharable) detach_helper(); }    ~QList();    QList<T> &operator=(const QList<T> &l);    bool operator==(const QList<T> &l) const;    inline bool operator!=(const QList<T> &l) const { return !(*this == l); }    inline int size() const { return p.size(); }    inline void detach() { if (d->ref != 1) detach_helper(); }    inline bool isDetached() const { return d->ref == 1; }    inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }    inline bool isEmpty() const { return p.isEmpty(); }    void clear();    const T &at(int i) const;    const T &operator[](int i) const;    T &operator[](int i);    void append(const T &t);    void prepend(const T &t);    void insert(int i, const T &t);    void replace(int i, const T &t);    void removeAt(int i);    int removeAll(const T &t);    T takeAt(int i);    T takeFirst();    T takeLast();    void move(int from, int to);    void swap(int i, int j);    int indexOf(const T &t, int from = 0) const;    int lastIndexOf(const T &t, int from = -1) const;    QBool contains(const T &t) const;    int count(const T &t) const;    class const_iterator;    class iterator {    public:        Node *i;        typedef std::random_access_iterator_tag  iterator_category;        typedef ptrdiff_t  difference_type;        typedef T value_type;        typedef T *pointer;        typedef T &reference;        inline iterator() : i(0) {}        inline iterator(Node *n) : i(n) {}        inline iterator(const iterator &o): i(o.i){}        inline T &operator*() const { return i->t(); }        inline T *operator->() const { return &i->t(); }        inline T &operator[](int j) const { return i[j].t(); }        inline bool operator==(const iterator &o) const { return i == o.i; }        inline bool operator!=(const iterator &o) const { return i != o.i; }        inline bool operator<(const iterator& other) const { return i < other.i; }        inline bool operator<=(const iterator& other) const { return i <= other.i; }        inline bool operator>(const iterator& other) const { return i > other.i; }        inline bool operator>=(const iterator& other) const { return i >= other.i; }#ifndef QT_STRICT_ITERATORS        inline bool operator==(const const_iterator &o) const            { return i == reinterpret_cast<const iterator &>(o).i; }        inline bool operator!=(const const_iterator &o) const            { return i != reinterpret_cast<const iterator &>(o).i; }        inline bool operator<(const const_iterator& other) const            { return i < reinterpret_cast<const iterator &>(other).i; }        inline bool operator<=(const const_iterator& other) const            { return i <= reinterpret_cast<const iterator &>(other).i; }        inline bool operator>(const const_iterator& other) const            { return i > reinterpret_cast<const iterator &>(other).i; }        inline bool operator>=(const const_iterator& other) const            { return i >= reinterpret_cast<const iterator &>(other).i; }#endif        inline iterator &operator++() { ++i; return *this; }        inline iterator operator++(int) { Node *n = i; ++i; return n; }        inline iterator &operator--() { i--; return *this; }        inline iterator operator--(int) { Node *n = i; i--; return n; }        inline iterator &operator+=(int j) { i+=j; return *this; }        inline iterator &operator-=(int j) { i-=j; return *this; }        inline iterator operator+(int j) const { return iterator(i+j); }        inline iterator operator-(int j) const { return iterator(i-j); }        inline int operator-(iterator j) const { return i - j.i; }    };    friend class iterator;    class const_iterator {    public:        Node *i;        typedef std::random_access_iterator_tag  iterator_category;        typedef ptrdiff_t difference_type;        typedef T value_type;        typedef const T *pointer;        typedef const T &reference;        inline const_iterator() : i(0) {}        inline const_iterator(Node *n) : i(n) {}        inline const_iterator(const const_iterator &o): i(o.i) {}#ifdef QT_STRICT_ITERATORS        inline explicit const_iterator(const iterator &o): i(o.i) {}#else        inline const_iterator(const iterator &o): i(o.i) {}#endif        inline const T &operator*() const { return i->t(); }        inline const T *operator->() const { return &i->t(); }        inline const T &operator[](int j) const { return i[j].t(); }        inline bool operator==(const const_iterator &o) const { return i == o.i; }        inline bool operator!=(const const_iterator &o) const { return i != o.i; }        inline bool operator<(const const_iterator& other) const { return i < other.i; }        inline bool operator<=(const const_iterator& other) const { return i <= other.i; }        inline bool operator>(const const_iterator& other) const { return i > other.i; }        inline bool operator>=(const const_iterator& other) const { return i >= other.i; }        inline const_iterator &operator++() { ++i; return *this; }        inline const_iterator operator++(int) { Node *n = i; ++i; return n; }        inline const_iterator &operator--() { i--; return *this; }        inline const_iterator operator--(int) { Node *n = i; i--; return n; }        inline const_iterator &operator+=(int j) { i+=j; return *this; }        inline const_iterator &operator-=(int j) { i-=j; return *this; }        inline const_iterator operator+(int j) const { return const_iterator(i+j); }        inline const_iterator operator-(int j) const { return const_iterator(i-j); }        inline int operator-(const_iterator j) const { return i - j.i; }    };    friend class const_iterator;    // stl style    inline iterator begin() { detach(); return reinterpret_cast<Node *>(p.begin()); }    inline const_iterator begin() const { return reinterpret_cast<Node *>(p.begin()); }    inline const_iterator constBegin() const { return reinterpret_cast<Node *>(p.begin()); }    inline iterator end() { detach(); return reinterpret_cast<Node *>(p.end()); }    inline const_iterator end() const { return reinterpret_cast<Node *>(p.end()); }    inline const_iterator constEnd() const { return reinterpret_cast<Node *>(p.end()); }    iterator insert(iterator before, const T &t);    iterator erase(iterator pos);    iterator erase(iterator first, iterator last);    // more Qt    typedef iterator Iterator;    typedef const_iterator ConstIterator;    inline int count() const { return p.size(); }    inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }    inline const T& first() const { Q_ASSERT(!isEmpty()); return *begin(); }    T& last() { Q_ASSERT(!isEmpty()); return *(--end()); }    const T& last() const { Q_ASSERT(!isEmpty()); return *(--end()); }    inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(begin()); }    inline void removeLast() { Q_ASSERT(!isEmpty()); erase(--end()); }    QList<T> mid(int pos, int length = -1) const;    T value(int i) const;    T value(int i, const T &defaultValue) const;    // stl compatibility    inline void push_back(const T &t) { append(t); }    inline void push_front(const T &t) { prepend(t); }    inline T& front() { return first(); }    inline const T& front() const { return first(); }    inline T& back() { return last(); }    inline const T& back() const { return last(); }    inline void pop_front() { removeFirst(); }    inline void pop_back() { removeLast(); }    inline bool empty() const { return isEmpty(); }    typedef int size_type;    typedef T value_type;    typedef value_type *pointer;    typedef const value_type *const_pointer;    typedef value_type &reference;    typedef const value_type &const_reference;    typedef ptrdiff_t difference_type;#ifdef QT3_SUPPORT    inline QT3_SUPPORT iterator remove(iterator pos) { return erase(pos); }    inline QT3_SUPPORT int remove(const T &t) { return removeAll(t); }    inline QT3_SUPPORT int findIndex(const T& t) const { return indexOf(t); }    inline QT3_SUPPORT iterator find(const T& t)    { int i = indexOf(t); return (i == -1 ? end() : (begin()+i)); }    inline QT3_SUPPORT const_iterator find (const T& t) const    { int i = indexOf(t); return (i == -1 ? end() : (begin()+i)); }    inline QT3_SUPPORT iterator find(iterator from, const T& t)    { int i = indexOf(t, from - begin()); return i == -1 ? end() : begin()+i; }    inline QT3_SUPPORT const_iterator find(const_iterator from, const T& t) const    { int i = indexOf(t, from - begin()); return i == -1 ? end() : begin()+i; }#endif    // comfort    QList<T> &operator+=(const QList<T> &l);    inline QList<T> operator+(const QList<T> &l) const    { QList n = *this; n += l; return n; }    inline QList<T> &operator+=(const T &t)    { append(t); return *this; }    inline QList<T> &operator<< (const T &t)    { append(t); return *this; }    inline QList<T> &operator<<(const QList<T> &l)    { *this += l; return *this; }    QVector<T> toVector() const;    QSet<T> toSet() const;    static QList<T> fromVector(const QVector<T> &vector);    static QList<T> fromSet(const QSet<T> &set);#ifndef QT_NO_STL    static inline QList<T> fromStdList(const std::list<T> &list)    { QList<T> tmp; qCopy(list.begin(), list.end(), std::back_inserter(tmp)); return tmp; }    inline std::list<T> toStdList() const    { std::list<T> tmp; qCopy(constBegin(), constEnd(), std::back_inserter(tmp)); return tmp; }#endifprivate:    void detach_helper();    void free(QListData::Data *d);    void node_construct(Node *n, const T &t);    void node_destruct(Node *n);    void node_copy(Node *from, Node *to, Node *src);    void node_destruct(Node *from, Node *to);};#if defined(Q_CC_BOR)template <typename T>Q_INLINE_TEMPLATE T &QList<T>::Node::t(){ return QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic ? *(T*)v:*(T*)this; }#endiftemplate <typename T>Q_INLINE_TEMPLATE void QList<T>::node_construct(Node *n, const T &t){    if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) n->v = new T(t);    else if (QTypeInfo<T>::isComplex) new (n) T(t);    else *reinterpret_cast<T*>(n) = t;}template <typename T>Q_INLINE_TEMPLATE void QList<T>::node_destruct(Node *n){    if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) delete reinterpret_cast<T*>(n->v);    else if (QTypeInfo<T>::isComplex) reinterpret_cast<T*>(n)->~T();}