/******************************************************************************** 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 QMAP_H#define QMAP_H#include <QtCore/qatomic.h>#include <QtCore/qiterator.h>#include <QtCore/qlist.h>#ifndef QT_NO_STL#include <map>#endif#include <new>#undef QT_MAP_DEBUGQT_BEGIN_HEADERQT_MODULE(Core)struct Q_CORE_EXPORT QMapData{    struct Node {        Node *backward;        Node *forward[1];    };    enum { LastLevel = 11, Sparseness = 3 };    QMapData *backward;    QMapData *forward[QMapData::LastLevel + 1];    QBasicAtomic ref;    int topLevel;    int size;    uint randomBits;    uint insertInOrder : 1;    uint sharable : 1;    static QMapData *createData();    void continueFreeData(int offset);    Node *node_create(Node *update[], int offset);    void node_delete(Node *update[], int offset, Node *node);#ifdef QT_QMAP_DEBUG    uint adjust_ptr(Node *node);    void dump();#endif    static QMapData shared_null;};/*    QMap uses qMapLessThanKey() to compare keys. The default    implementation uses operator<(). For pointer types,    qMapLessThanKey() casts the pointers to integers before it    compares them, because operator<() is undefined on pointers    that come from different memory blocks. (In practice, this    is only a problem when running a program such as    BoundsChecker.)*/template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2){    return key1 < key2;}#ifndef QT_NO_PARTIAL_TEMPLATE_SPECIALIZATIONtemplate <class Ptr> inline bool qMapLessThanKey(Ptr *key1, Ptr *key2){    Q_ASSERT(sizeof(ulong) == sizeof(Ptr *));    return reinterpret_cast<ulong>(key1) < reinterpret_cast<ulong>(key2);}template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2){    Q_ASSERT(sizeof(ulong) == sizeof(const Ptr *));    return reinterpret_cast<ulong>(key1) < reinterpret_cast<ulong>(key2);}#endif // QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION#if !defined(QT_NO_DATASTREAM)class QDataStream;template <class Key, class T> class QMap;template <class aKey, class aT>QDataStream &operator>>(QDataStream &in, QMap<aKey, aT> &map);#endiftemplate <class Key, class T>class QMap{    struct Node {        Key key;        T value;        QMapData::Node *backward;        QMapData::Node *forward[1];    };    union {        QMapData *d;        QMapData::Node *e;    };    struct PayloadNode    {        Key key;        T value;        QMapData::Node *backward;    };    static inline int payload() { return sizeof(PayloadNode) - sizeof(QMapData::Node *); }    static inline Node *concrete(QMapData::Node *node) {        return reinterpret_cast<Node *>(reinterpret_cast<char *>(node) - payload());    }public:    inline QMap() : d(&QMapData::shared_null) { d->ref.ref(); }    inline QMap(const QMap<Key, T> &other) : d(other.d)    { d->ref.ref(); if (!d->sharable) detach(); }    inline ~QMap() { if (!d) return; if (!d->ref.deref()) freeData(d); }    QMap<Key, T> &operator=(const QMap<Key, T> &other);#ifndef QT_NO_STL    explicit QMap(const typename std::map<Key, T> &other);    std::map<Key, T> toStdMap() const;#endif    bool operator==(const QMap<Key, T> &other) const;    inline bool operator!=(const QMap<Key, T> &other) const { return !(*this == other); }    inline int size() const { return d->size; }    inline bool isEmpty() const { return d->size == 0; }    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; }    void clear();    int remove(const Key &key);    T take(const Key &key);    bool contains(const Key &key) const;    const Key key(const T &value) const;    const T value(const Key &key) const;    const T value(const Key &key, const T &defaultValue) const;    T &operator[](const Key &key);    const T operator[](const Key &key) const;    QList<Key> uniqueKeys() const;    QList<Key> keys() const;    QList<Key> keys(const T &value) const;    QList<T> values() const;    QList<T> values(const Key &key) const;    int count(const Key &key) const;    class const_iterator;    class iterator    {        QMapData::Node *i;    public:        typedef std::bidirectional_iterator_tag iterator_category;        typedef ptrdiff_t difference_type;        typedef T value_type;        typedef T *pointer;        typedef T &reference;        // ### Qt 5: get rid of 'operator Node *'        inline operator QMapData::Node *() const { return i; }        inline iterator() : i(0) { }        inline iterator(QMapData::Node *node) : i(node) { }        inline const Key &key() const { return concrete(i)->key; }        inline T &value() const { return concrete(i)->value; }#ifdef QT3_SUPPORT        inline QT3_SUPPORT T &data() const { return concrete(i)->value; }#endif        inline T &operator*() const { return concrete(i)->value; }        inline T *operator->() const { return &concrete(i)->value; }        inline bool operator==(const iterator &o) const { return i == o.i; }        inline bool operator!=(const iterator &o) const { return i != o.i; }        inline iterator &operator++() {            i = i->forward[0];            return *this;        }        inline iterator operator++(int) {            iterator r = *this;            i = i->forward[0];            return r;        }        inline iterator &operator--() {            i = i->backward;            return *this;        }        inline iterator operator--(int) {            iterator r = *this;            i = i->backward;            return r;        }        inline iterator operator+(int j) const        { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }        inline iterator operator-(int j) const { return operator+(-j); }        inline iterator &operator+=(int j) { return *this = *this + j; }        inline iterator &operator-=(int j) { return *this = *this - j; }        // ### Qt 5: not sure this is necessary anymore#ifdef QT_STRICT_ITERATORS    private:#else    public:#endif        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; }    private:        // ### Qt 5: remove        inline operator bool() const { return false; }    };    friend class iterator;    class const_iterator    {        QMapData::Node *i;    public:        typedef std::bidirectional_iterator_tag iterator_category;        typedef ptrdiff_t difference_type;        typedef T value_type;        typedef const T *pointer;        typedef const T &reference;        // ### Qt 5: get rid of 'operator Node *'        inline operator QMapData::Node *() const { return i; }        inline const_iterator() : i(0) { }        inline const_iterator(QMapData::Node *node) : i(node) { }#ifdef QT_STRICT_ITERATORS        explicit inline const_iterator(const iterator &o)#else        inline const_iterator(const iterator &o)#endif        { i = reinterpret_cast<const const_iterator &>(o).i; }        inline const Key &key() const { return concrete(i)->key; }        inline const T &value() const { return concrete(i)->value; }#ifdef QT3_SUPPORT        inline QT3_SUPPORT const T &data() const { return concrete(i)->value; }#endif        inline const T &operator*() const { return concrete(i)->value; }        inline const T *operator->() const { return &concrete(i)->value; }        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 const_iterator &operator++() {            i = i->forward[0];            return *this;        }        inline const_iterator operator++(int) {            const_iterator r = *this;            i = i->forward[0];            return r;        }        inline const_iterator &operator--() {            i = i->backward;            return *this;        }        inline const_iterator operator--(int) {            const_iterator r = *this;            i = i->backward;            return r;        }        inline const_iterator operator+(int j) const        { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }        inline const_iterator operator-(int j) const { return operator+(-j); }        inline const_iterator &operator+=(int j) { return *this = *this + j; }        inline const_iterator &operator-=(int j) { return *this = *this - j; }        // ### Qt 5: not sure this is necessary anymore#ifdef QT_STRICT_ITERATORS    private:        inline bool operator==(const iterator &o) { return operator==(const_iterator(o)); }        inline bool operator!=(const iterator &o) { return operator!=(const_iterator(o)); }#endif    private:        // ### Qt 5: remove        inline operator bool() const { return false; }    };    friend class const_iterator;    // STL style    inline iterator begin() { detach(); return iterator(e->forward[0]); }    inline const_iterator begin() const { return const_iterator(e->forward[0]); }    inline const_iterator constBegin() const { return const_iterator(e->forward[0]); }    inline iterator end() {        detach();        return iterator(e);    }    inline const_iterator end() const { return const_iterator(e); }    inline const_iterator constEnd() const { return const_iterator(e); }    iterator erase(iterator it);#ifdef QT3_SUPPORT    inline QT3_SUPPORT iterator remove(iterator it) { return erase(it); }    inline QT3_SUPPORT void erase(const Key &key) { remove(key); }#endif    // more Qt    typedef iterator Iterator;    typedef const_iterator ConstIterator;    inline int count() const { return d->size; }    iterator find(const Key &key);    const_iterator find(const Key &key) const;    const_iterator constFind(const Key &key) const;    iterator lowerBound(const Key &key);    const_iterator lowerBound(const Key &key) const;    iterator upperBound(const Key &key);    const_iterator upperBound(const Key &key) const;    iterator insert(const Key &key, const T &value);#ifdef QT3_SUPPORT    QT3_SUPPORT iterator insert(const Key &key, const T &value, bool overwrite);#endif    iterator insertMulti(const Key &key, const T &value);#ifdef QT3_SUPPORT    inline QT3_SUPPORT iterator replace(const Key &key, const T &value) { return insert(key, value); }#endif    QMap<Key, T> &unite(const QMap<Key, T> &other);    // STL compatibility    typedef Key key_type;    typedef T mapped_type;    typedef ptrdiff_t difference_type;    typedef int size_type;    inline bool empty() const { return isEmpty(); }#ifdef QT_QMAP_DEBUG    inline void dump() const { d->dump(); }#endifprivate:    void detach_helper();    void freeData(QMapData *d);    QMapData::Node *findNode(const Key &key) const;    QMapData::Node *mutableFindNode(QMapData::Node *update[], const Key &key) const;    QMapData::Node *node_create(QMapData *d, QMapData::Node *update[], const Key &key,                                const T &value);#if !defined(QT_NO_DATASTREAM)#if !defined(Q_CC_BOR)#if defined Q_CC_MSVC && _MSC_VER < 1300    friend QDataStream &operator>> (QDataStream &in, QMap &map);#else    template <class aKey, class aT>    friend QDataStream &operator>> (QDataStream &in, QMap<aKey, aT> &map);#endif#endif#endif};template <class Key, class T>Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other){    if (d != other.d) {        QMapData *x = other.d;        x->ref.ref();        x = qAtomicSetPtr(&d, x);        if (!x->ref.deref())            freeData(x);        if (!d->sharable)            detach_helper();    }    return *this;}template <class Key, class T>Q_INLINE_TEMPLATE void QMap<Key, T>::clear(){    *this = QMap<Key, T>();}template <class Key, class T>Q_INLINE_TEMPLATE typename QMapData::Node *QMap<Key, T>::node_create(QMapData *adt, QMapData::Node *aupdate[], const Key &akey, const T &avalue){    QMapData::Node *abstractNode = adt->node_create(aupdate, payload());    Node *concreteNode = concrete(abstractNode);    new (&concreteNode->key) Key(akey);    new (&concreteNode->value) T(avalue);    return abstractNode;}template <class Key, class T>Q_INLINE_TEMPLATE QMapData::Node *QMap<Key, T>::findNode(const Key &akey) const{    QMapData::Node *cur = e;    QMapData::Node *next = e;    for (int i = d->topLevel; i >= 0; i--) {        while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))            cur = next;    }    if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {        return next;    } else {        return e;    }}template <class Key, class T>Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey) const{    QMapData::Node *node = findNode(akey);    if (node == e) {        return T();    } else {        return concrete(node)->value;    }}template <class Key, class T>Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey, const T &adefaultValue) const{    QMapData::Node *node = findNode(akey);    if (node == e) {        return adefaultValue;    } else {        return concrete(node)->value;    }}template <class Key, class T>Q_INLINE_TEMPLATE const T QMap<Key, T>::operator[](const Key &akey) const{    return value(akey);}template <class Key, class T>Q_INLINE_TEMPLATE T &QMap<Key, T>::operator[](const Key &akey)