/****************************************************************************

**

** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the QtCore module of the Qt Toolkit.

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

** This file contains pre-release code and may not be distributed.

** You may use this file in accordance with the terms and conditions

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

** Alternatively, this file may be used under the terms of the GNU Lesser

** General Public License version 2.1 as published by the Free Software

** Foundation and appearing in the file LICENSE.LGPL included in the

** packaging of this file.  Please review the following information to

** ensure the GNU Lesser General Public License version 2.1 requirements

** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

**

** In addition, as a special exception, Nokia gives you certain additional

** rights.  These rights are described in the Nokia Qt LGPL Exception

** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

**

** If you have questions regarding the use of this file, please contact

** Nokia at qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

#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>

QT_BEGIN_HEADER

QT_BEGIN_NAMESPACE

QT_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];

    QBasicAtomicInt ref;

    int topLevel;

    int size;

    uint randomBits;

    uint insertInOrder : 1;

    uint sharable : 1;

    uint strictAlignment : 1;

    uint reserved : 29;

    static QMapData *createData(); // ### Qt5 remove me

    static QMapData *createData(int alignment);

    void continueFreeData(int offset);

    Node *node_create(Node *update[], int offset); // ### Qt5 remove me

    Node *node_create(Node *update[], int offset, int alignment);

    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_SPECIALIZATION

template <class Ptr> inline bool qMapLessThanKey(Ptr *key1, Ptr *key2)

{

    Q_ASSERT(sizeof(quintptr) == sizeof(Ptr *));

    return quintptr(key1) < quintptr(key2);

}

template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)

{

    Q_ASSERT(sizeof(quintptr) == sizeof(const Ptr *));

    return quintptr(key1) < quintptr(key2);

}

#endif // QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION

template <class Key, class T>

struct QMapNode {

    Key key;

    T value;

private:

    // never access these members through this structure.

    // see below

    QMapData::Node *backward;

    QMapData::Node *forward[1];

};

template <class Key, class T>

struct QMapPayloadNode

{

    Key key;

    T value;

private:

    // QMap::e is a pointer to QMapData::Node, which matches the member

    // below. However, the memory allocation node in QMapData::node_create

    // allocates sizeof(QMapPayloNode) and incorrectly calculates the offset

    // of 'backward' below. If the alignment of QMapPayloadNode is larger

    // than the alignment of a pointer, the 'backward' member is aligned to

    // the end of this structure, not to 'value' above, and will occupy the

    // tail-padding area.

    //

    //  e.g., on a 32-bit archictecture with Key = int and

    //        sizeof(T) = alignof(T) = 8

    //   0        4        8        12       16       20       24  byte

    //   |   key  |   PAD  |      value      |backward|  PAD   |   correct layout

    //   |   key  |   PAD  |      value      |        |backward|   how it's actually used

    //   |<-----  value of QMap::payload() = 20 ----->|

    QMapData::Node *backward;

};

template <class Key, class T>

class QMap

{

    typedef QMapNode<Key, T> Node;

    typedef QMapPayloadNode<Key, T> PayloadNode;

    union {

        QMapData *d;

        QMapData::Node *e;

    };

    static inline int payload() { return sizeof(PayloadNode) - sizeof(QMapData::Node *); }

    static inline int alignment() {

#ifdef Q_ALIGNOF

        return int(qMax(sizeof(void*), Q_ALIGNOF(Node)));

#else

        return 0;

#endif

    }

    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; }

    inline bool isSharedWith(const QMap<Key, T> &other) const { return d == other.d; }

    inline void setInsertInOrder(bool ordered) { d->insertInOrder = ordered; }

    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 Key key(const T &value, const Key &defaultKey) 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

    {

        friend class const_iterator;

        QMapData::Node *i;

    public:

        typedef std::bidirectional_iterator_tag iterator_category;

        typedef qptrdiff 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 == o.i; }

        inline bool operator!=(const const_iterator &o) const

            { return i != o.i; }

    private:

        // ### Qt 5: remove

        inline operator bool() const { return false; }

    };

    friend class iterator;

    class const_iterator

    {

        friend class iterator;

        QMapData::Node *i;

    public:

        typedef std::bidirectional_iterator_tag iterator_category;

        typedef qptrdiff 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 = 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 &aKey) { remove(aKey); }

#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 &aKey, const T &aValue) { return insert(aKey, aValue); }

#endif

    QMap<Key, T> &unite(const QMap<Key, T> &other);

    // STL compatibility

    typedef Key key_type;

    typedef T mapped_type;

    typedef qptrdiff difference_type;

    typedef int size_type;

    inline bool empty() const { return isEmpty(); }

#ifdef QT_QMAP_DEBUG

    inline void dump() const { d->dump(); }

#endif

private:

    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);

};

template <class Key, class T>

Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)

{

    if (d != other.d) {

        if (!d->ref.deref())

            freeData(d);

        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(), alignment());

    QT_TRY {

        Node *concreteNode = concrete(abstractNode);

        new (&concreteNode->key) Key(akey);

        QT_TRY {

            new (&concreteNode->value) T(avalue);

        } QT_CATCH(...) {

            concreteNode->key.~Key();

            QT_RETHROW;

        }

    } QT_CATCH(...) {

        adt->node_delete(aupdate, payload(), abstractNode);

        QT_RETHROW;

    }

    // clean up the update array for further insertions

    /*

    for (int i = 0; i <= d->topLevel; ++i) {

        if ( aupdate[i]==reinterpret_cast<QMapData::Node *>(adt) || aupdate[i]->forward[i] != abstractNode)

            break;

        aupdate[i] = abstractNode;

    }

*/

    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;

    if (d->size == 0 || (node = findNode(akey)) == 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;

    if (d->size == 0 || (node = findNode(akey)) == 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)