/******************************************************************************** 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 QVECTOR_H#define QVECTOR_H#include <QtCore/qiterator.h>#include <QtCore/qatomic.h>#include <QtCore/qalgorithms.h>#include <QtCore/qlist.h>#ifndef QT_NO_STL#include <iterator>#include <vector>#endif#include <stdlib.h>#include <string.h>QT_BEGIN_HEADERQT_MODULE(Core)struct Q_CORE_EXPORT QVectorData{    QBasicAtomic ref;    int alloc;    int size;    uint sharable : 1;    static QVectorData shared_null;    static QVectorData *malloc(int sizeofTypedData, int size, int sizeofT, QVectorData *init);    static int grow(int sizeofTypedData, int size, int sizeofT, bool excessive);};template <typename T>struct QVectorTypedData{    QBasicAtomic ref;    int alloc;    int size;    uint sharable : 1;    T array[1];};template <typename T>class QVector{    typedef QVectorTypedData<T> Data;    union { QVectorData *p; QVectorTypedData<T> *d; };public:    inline QVector() : p(&QVectorData::shared_null) { d->ref.ref(); }    explicit QVector(int size);    QVector(int size, const T &t);    inline QVector(const QVector<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); }    inline ~QVector() { if (!d) return; if (!d->ref.deref()) free(d); }    QVector<T> &operator=(const QVector<T> &v);    bool operator==(const QVector<T> &v) const;    inline bool operator!=(const QVector<T> &v) const { return !(*this == v); }    inline int size() const { return d->size; }    inline bool isEmpty() const { return d->size == 0; }    void resize(int size);    inline int capacity() const { return d->alloc; }    void reserve(int size);    inline void squeeze() { realloc(d->size, d->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 T *data() { detach(); return d->array; }    inline const T *data() const { return d->array; }    inline const T *constData() const { return d->array; }    void clear();    const T &at(int i) const;    T &operator[](int i);    const T &operator[](int i) const;    void append(const T &t);    void prepend(const T &t);    void insert(int i, const T &t);    void insert(int i, int n, const T &t);    void replace(int i, const T &t);    void remove(int i);    void remove(int i, int n);    QVector<T> &fill(const T &t, int size = -1);    int indexOf(const T &t, int from = 0) const;    int lastIndexOf(const T &t, int from = -1) const;    bool contains(const T &t) const;    int count(const T &t) const;#ifdef QT_STRICT_ITERATORS    class iterator {    public:        T *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(T *n) : i(n) {}        inline iterator(const iterator &o): i(o.i){}        inline T &operator*() const { return *i; }        inline T *operator->() const { return i; }        inline T &operator[](int j) const { return *(i + j); }        inline bool operator==(const iterator &o) const { qDebug("1"); 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; }        inline iterator &operator++() { ++i; return *this; }        inline iterator operator++(int) { T *n = i; ++i; return n; }        inline iterator &operator--() { i--; return *this; }        inline iterator operator--(int) { T *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:        T *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(T *n) : i(n) {}        inline const_iterator(const const_iterator &o): i(o.i) {}        inline explicit const_iterator(const iterator &o): i(o.i) {}        inline const T &operator*() const { return *i; }        inline const T *operator->() const { return i; }        inline const T &operator[](int j) const { return *(i + j); }        inline bool operator==(const const_iterator &o) const { qDebug("3"); 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) { T *n = i; ++i; return n; }        inline const_iterator &operator--() { i--; return *this; }        inline const_iterator operator--(int) { T *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;#else    // STL-style    typedef T* iterator;    typedef const T* const_iterator;#endif    inline iterator begin() { detach(); return d->array; }    inline const_iterator begin() const { return d->array; }    inline const_iterator constBegin() const { return d->array; }    inline iterator end() { detach(); return d->array + d->size; }    inline const_iterator end() const { return d->array + d->size; }    inline const_iterator constEnd() const { return d->array + d->size; }    iterator insert(iterator before, int n, const T &x);    inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); }    iterator erase(iterator begin, iterator end);    inline iterator erase(iterator pos) { return erase(pos, pos+1); }    // more Qt    inline int count() const { return d->size; }    inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }    inline const T &first() const { Q_ASSERT(!isEmpty()); return *begin(); }    inline T& last() { Q_ASSERT(!isEmpty()); return *(end()-1); }    inline const T &last() const { Q_ASSERT(!isEmpty()); return *(end()-1); }    QVector<T> mid(int pos, int length = -1) const;    T value(int i) const;    T value(int i, const T &defaultValue) const;    // STL compatibility    typedef T value_type;    typedef value_type* pointer;    typedef const value_type* const_pointer;    typedef value_type& reference;    typedef const value_type& const_reference;#ifndef QT_NO_STL    typedef ptrdiff_t difference_type;#else    typedef int difference_type;#endif    typedef iterator Iterator;    typedef const_iterator ConstIterator;    typedef int size_type;    inline void push_back(const T &t) { append(t); }    inline void push_front(const T &t) { prepend(t); }    void pop_back() { Q_ASSERT(!isEmpty()); erase(end()-1); }    void pop_front() { Q_ASSERT(!isEmpty()); erase(begin()); }    inline bool empty() const    { return d->size == 0; }    inline T& front() { return first(); }    inline const_reference front() const { return first(); }    inline reference back() { return last(); }    inline const_reference back() const { return last(); }    // comfort    QVector<T> &operator+=(const QVector<T> &l);    inline QVector<T> operator+(const QVector<T> &l) const    { QVector n = *this; n += l; return n; }    inline QVector<T> &operator+=(const T &t)    { append(t); return *this; }    inline QVector<T> &operator<< (const T &t)    { append(t); return *this; }    inline QVector<T> &operator<<(const QVector<T> &l)    { *this += l; return *this; }    QList<T> toList() const;    static QVector<T> fromList(const QList<T> &list);#ifndef QT_NO_STL    static inline QVector<T> fromStdVector(const std::vector<T> &vector)    { QVector<T> tmp; qCopy(vector.begin(), vector.end(), std::back_inserter(tmp)); return tmp; }    inline std::vector<T> toStdVector() const    { std::vector<T> tmp; qCopy(constBegin(), constEnd(), std::back_inserter(tmp)); return tmp; }#endifprivate:    void detach_helper();    QVectorData *malloc(int alloc);    void realloc(int size, int alloc);    void free(Data *d);};template <typename T>void QVector<T>::detach_helper(){ realloc(d->size, d->alloc); }template <typename T>void QVector<T>::reserve(int asize){ if (asize > d->alloc) realloc(d->size, asize); }template <typename T>void QVector<T>::resize(int asize){ realloc(asize, (asize > d->alloc || (asize < d->size && asize < (d->alloc >> 1))) ?          QVectorData::grow(sizeof(Data), asize, sizeof(T), QTypeInfo<T>::isStatic)          : d->alloc); }template <typename T>inline void QVector<T>::clear(){ *this = QVector<T>(); }template <typename T>inline const T &QVector<T>::at(int i) const{ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::at", "index out of range");  return d->array[i]; }template <typename T>inline const T &QVector<T>::operator[](int i) const{ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range");  return d->array[i]; }template <typename T>inline T &QVector<T>::operator[](int i){ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range");  return data()[i]; }template <typename T>inline void QVector<T>::insert(int i, const T &t){ Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert", "index out of range");  insert(begin() + i, 1, t); }template <typename T>inline void QVector<T>::insert(int i, int n, const T &t){ Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert", "index out of range");  insert(begin() + i, n, t); }template <typename T>inline void QVector<T>::remove(int i, int n){ Q_ASSERT_X(i >= 0 && n >= 0 && i + n <= d->size, "QVector<T>::remove", "index out of range");  erase(begin() + i, begin() + i + n); }template <typename T>inline void QVector<T>::remove(int i){ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::remove", "index out of range");  erase(begin() + i, begin() + i + 1); }template <typename T>inline void QVector<T>::prepend(const T &t){ insert(begin(), 1, t); }template <typename T>inline void QVector<T>::replace(int i, const T &t){    Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::replace", "index out of range");    const T copy(t);    data()[i] = copy;}template <typename T>QVector<T> &QVector<T>::operator=(const QVector<T> &v){    typename QVector::Data *x = v.d;    x->ref.ref();    x = qAtomicSetPtr(&d, x);    if (!x->ref.deref())        free(x);    if (!d->sharable)        detach_helper();    return *this;}template <typename T>inline QVectorData *QVector<T>::malloc(int aalloc){    return static_cast<QVectorData *>(qMalloc(sizeof(Data) + (aalloc - 1) * sizeof(T)));}template <typename T>QVector<T>::QVector(int asize){    p = malloc(asize);    d->ref.init(1);    d->alloc = d->size = asize;    d->sharable = true;    if (QTypeInfo<T>::isComplex) {        T* b = d->array;        T* i = d->array + d->size;        while (i != b)            new (--i) T;    } else {        qMemSet(d->array, 0, asize * sizeof(T));    }}template <typename T>QVector<T>::QVector(int asize, const T &t){    p = malloc(asize);    d->ref.init(1);