src/corelib/tools/qmap.h

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtCore module of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:LGPL$
   9 ** GNU Lesser General Public License Usage
  10 ** This file may be used under the terms of the GNU Lesser General Public
  11 ** License version 2.1 as published by the Free Software Foundation and
  12 ** appearing in the file LICENSE.LGPL included in the packaging of this
  13 ** file. Please review the following information to ensure the GNU Lesser
  14 ** General Public License version 2.1 requirements will be met:
  15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  16 **
  17 ** In addition, as a special exception, Nokia gives you certain additional
  18 ** rights. These rights are described in the Nokia Qt LGPL Exception
  19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  20 **
  21 ** GNU General Public License Usage
  22 ** Alternatively, this file may be used under the terms of the GNU General
  23 ** Public License version 3.0 as published by the Free Software Foundation
  24 ** and appearing in the file LICENSE.GPL included in the packaging of this
  25 ** file. Please review the following information to ensure the GNU General
  26 ** Public License version 3.0 requirements will be met:
  27 ** http://www.gnu.org/copyleft/gpl.html.
  28 **
  29 ** Other Usage
  30 ** Alternatively, this file may be used in accordance with the terms and
  31 ** conditions contained in a signed written agreement between you and Nokia.
  32 **
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 #ifndef QMAP_H
  43 #define QMAP_H
  44
  45 #include <QtCore/qiterator.h>
  46 #include <QtCore/qlist.h>
  47 #include <QtCore/qrefcount.h>
  48 #include <QtCore/qpair.h>
  49
  50 #ifdef Q_MAP_DEBUG
  51 #include <QtCore/qdebug.h>
  52 #endif
  53
  54 #include <map>
  55 #include <new>
  56
  57 QT_BEGIN_HEADER
  58
  59 QT_BEGIN_NAMESPACE
  60
  61 /*
  62     QMap uses qMapLessThanKey() to compare keys. The default
  63     implementation uses operator<(). For pointer types,
  64     qMapLessThanKey() casts the pointers to integers before it
  65     compares them, because operator<() is undefined on pointers
  66     that come from different memory blocks. (In practice, this
  67     is only a problem when running a program such as
  68     BoundsChecker.)
  69 */
  70
  71 template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2)
  72 {
  73     return key1 < key2;
  74 }
  75
  76 template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)
  77 {
  78     Q_STATIC_ASSERT(sizeof(quintptr) == sizeof(const Ptr *));
  79     return quintptr(key1) < quintptr(key2);
  80 }
  81
  82 struct QMapDataBase;
  83 template <class Key, class T> struct QMapData;
  84
  85 struct Q_CORE_EXPORT QMapNodeBase
  86 {
  87     quintptr p;
  88     QMapNodeBase *left;
  89     QMapNodeBase *right;
  90
  91     enum Color { Red = 0, Black = 1 };
  92     enum { Mask = 3 }; // reserve the second bit as well
  93
  94     const QMapNodeBase *nextNode() const;
  95     QMapNodeBase *nextNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->nextNode()); }
  96     const QMapNodeBase *previousNode() const;
  97     QMapNodeBase *previousNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->previousNode()); }
  98
  99     Color color() const { return Color(p & 1); }
 100     void setColor(Color c) { if (c == Black) p |= Black; else p &= ~Black; }
 101     QMapNodeBase *parent() const { return reinterpret_cast<QMapNodeBase *>(p & ~Mask); }
 102     void setParent(QMapNodeBase *pp) { p = (p & Mask) | quintptr(pp); }
 103
 104     QMapNodeBase *minimumNode() { QMapNodeBase *n = this; while (n->left) n = n->left; return n; }
 105     QMapNodeBase *maximumNode() { QMapNodeBase *n = this; while (n->right) n = n->right; return n; }
 106     const QMapNodeBase *minimumNode() const { const QMapNodeBase *n = this; while (n->left) n = n->left; return n; }
 107     const QMapNodeBase *maximumNode() const { const QMapNodeBase *n = this; while (n->right) n = n->right; return n; }
 108 };
 109
 110 template <class Key, class T>
 111 struct QMapNode : public QMapNodeBase
 112 {
 113     Key key;
 114     T value;
 115
 116     inline QMapNode *leftNode() const { return static_cast<QMapNode *>(left); }
 117     inline QMapNode *rightNode() const { return static_cast<QMapNode *>(right); }
 118
 119     inline const QMapNode *nextNode() const { return static_cast<const QMapNode *>(QMapNodeBase::nextNode()); }
 120     inline const QMapNode *previousNode() const { return static_cast<const QMapNode *>(QMapNodeBase::previousNode()); }
 121     inline QMapNode *nextNode() { return static_cast<QMapNode *>(QMapNodeBase::nextNode()); }
 122     inline QMapNode *previousNode() { return static_cast<QMapNode *>(QMapNodeBase::previousNode()); }
 123
 124     QMapNode *minimumNode() { return static_cast<QMapNode *>(QMapNodeBase::minimumNode()); }
 125     QMapNode *maximumNode() { return static_cast<QMapNode *>(QMapNodeBase::maximumNode()); }
 126     const QMapNode *minimumNode() const { return static_cast<QMapNode *>(QMapNodeBase::minimumNode()); }
 127     const QMapNode *maximumNode() const { return static_cast<QMapNode *>(QMapNodeBase::maximumNode()); }
 128
 129     QMapNode<Key, T> *copy(QMapData<Key, T> *d) const;
 130
 131     void destroySubTree();
 132
 133     QMapNode<Key, T> *lowerBound(const Key &key);
 134     QMapNode<Key, T> *upperBound(const Key &key);
 135
 136 private:
 137     QMapNode() Q_DECL_EQ_DELETE;
 138     Q_DISABLE_COPY(QMapNode)
 139 };
 140
 141 template <class Key, class T>
 142 inline QMapNode<Key, T> *QMapNode<Key, T>::lowerBound(const Key &akey)
 143 {
 144     QMapNode<Key, T> *n = this;
 145     QMapNode<Key, T> *last = 0;
 146     while (n) {
 147         if (!qMapLessThanKey(n->key, akey)) {
 148             last = n;
 149             n = n->leftNode();
 150         } else {
 151             n = n->rightNode();
 152         }
 153     }
 154     return last;
 155 }
 156
 157 template <class Key, class T>
 158 inline QMapNode<Key, T> *QMapNode<Key, T>::upperBound(const Key &akey)
 159 {
 160     QMapNode<Key, T> *n = this;
 161     QMapNode<Key, T> *last = 0;
 162     while (n) {
 163         if (qMapLessThanKey(akey, n->key)) {
 164             last = n;
 165             n = n->leftNode();
 166         } else {
 167             n = n->rightNode();
 168         }
 169     }
 170     return last;
 171 }
 172
 173
 174
 175 struct Q_CORE_EXPORT QMapDataBase
 176 {
 177     QtPrivate::RefCount ref;
 178     int size;
 179     QMapNodeBase header;
 180
 181     void rotateLeft(QMapNodeBase *x);
 182     void rotateRight(QMapNodeBase *x);
 183     void rebalance(QMapNodeBase *x);
 184     void freeNodeAndRebalance(QMapNodeBase *z);
 185
 186     QMapNodeBase *createNode(int size, int alignment, QMapNodeBase *parent, bool left);
 187     void freeTree(QMapNodeBase *root, int alignment);
 188
 189     static const QMapDataBase shared_null;
 190
 191     static QMapDataBase *createData();
 192     static void freeData(QMapDataBase *d);
 193 };
 194
 195 template <class Key, class T>
 196 struct QMapData : public QMapDataBase
 197 {
 198     typedef QMapNode<Key, T> Node;
 199
 200     Node *root() const { return static_cast<Node *>(header.left); }
 201
 202     const Node *end() const { return static_cast<const Node *>(&header); }
 203     Node *end() { return static_cast<Node *>(&header); }
 204     const Node *begin() const { if (root()) return root()->minimumNode(); return end(); }
 205     Node *begin() { if (root()) return root()->minimumNode(); return end(); }
 206
 207     void deleteNode(Node *z);
 208     Node *findNode(const Key &akey) const;
 209     void nodeRange(const Key &akey, Node **first, Node **last);
 210
 211     Node *createNode(const Key &k, const T &v, Node *parent = 0, bool left = false)
 212     {
 213         Node *n = static_cast<Node *>(QMapDataBase::createNode(sizeof(Node), Q_ALIGNOF(Node),
 214                                       parent, left));
 215         QT_TRY {
 216             new (&n->key) Key(k);
 217             QT_TRY {
 218                 new (&n->value) T(v);
 219             } QT_CATCH(...) {
 220                 n->key.~Key();
 221                 QT_RETHROW;
 222             }
 223         } QT_CATCH(...) {
 224             QMapDataBase::freeNodeAndRebalance(n);
 225             QT_RETHROW;
 226         }
 227         return n;
 228     }
 229
 230     static QMapData *create() {
 231         return static_cast<QMapData *>(createData());
 232     }
 233
 234     void free() {
 235         if (root()) {
 236             root()->destroySubTree();
 237             freeTree(header.left, Q_ALIGNOF(Node));
 238         }
 239         freeData(this);
 240     }
 241 };
 242
 243 template <class Key, class T>
 244 QMapNode<Key, T> *QMapNode<Key, T>::copy(QMapData<Key, T> *d) const
 245 {
 246     QMapNode<Key, T> *n = d->createNode(key, value);
 247     n->setColor(color());
 248     if (left) {
 249         n->left = leftNode()->copy(d);
 250         n->left->setParent(n);
 251     } else {
 252         n->left = 0;
 253     }
 254     if (right) {
 255         n->right = rightNode()->copy(d);
 256         n->right->setParent(n);
 257     } else {
 258         n->right = 0;
 259     }
 260     return n;
 261 }
 262
 263 template <class Key, class T>
 264 void QMapNode<Key, T>::destroySubTree()
 265 {
 266     if (QTypeInfo<Key>::isComplex)
 267         key.~Key();
 268     if (QTypeInfo<T>::isComplex)
 269         value.~T();
 270     if (QTypeInfo<Key>::isComplex || QTypeInfo<T>::isComplex) {
 271         if (left)
 272             leftNode()->destroySubTree();
 273         if (right)
 274             rightNode()->destroySubTree();
 275     }
 276 }
 277
 278 template <class Key, class T>
 279 void QMapData<Key, T>::deleteNode(QMapNode<Key, T> *z)
 280 {
 281     if (QTypeInfo<Key>::isComplex)
 282         z->key.~Key();
 283     if (QTypeInfo<T>::isComplex)
 284         z->value.~T();
 285     freeNodeAndRebalance(z);
 286 }
 287
 288 template <class Key, class T>
 289 QMapNode<Key, T> *QMapData<Key, T>::findNode(const Key &akey) const
 290 {
 291     Node *lb = root()->lowerBound(akey);
 292     if (lb && !qMapLessThanKey(akey, lb->key))
 293         return lb;
 294     return 0;
 295 }
 296
 297
 298 template <class Key, class T>
 299 void QMapData<Key, T>::nodeRange(const Key &akey, QMapNode<Key, T> **first, QMapNode<Key, T> **last)
 300 {
 301     Node *n = root();
 302     Node *l = end();
 303     while (n) {
 304         if (qMapLessThanKey(akey, n->key)) {
 305             l = n;
 306             n = n->leftNode();
 307         } else if (qMapLessThanKey(n->key, akey)) {
 308             n = n->rightNode();
 309         } else {
 310             *first = n->leftNode()->lowerBound(akey);
 311             if (!*first)
 312                 *first = n;
 313             *last = n->rightNode()->upperBound(akey);
 314             if (!*last)
 315                 *last = l;
 316             return;
 317         }
 318     }
 319     *first = *last = l;
 320 }
 321
 322
 323 template <class Key, class T>
 324 class QMap
 325 {
 326     typedef QMapNode<Key, T> Node;
 327
 328     QMapData<Key, T> *d;
 329
 330 public:
 331     inline QMap() : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null))) { }
 332     QMap(const QMap<Key, T> &other);
 333
 334     inline ~QMap() { if (!d->ref.deref()) d->free(); }
 335
 336     QMap<Key, T> &operator=(const QMap<Key, T> &other);
 337 #ifdef Q_COMPILER_RVALUE_REFS
 338     inline QMap(QMap<Key, T> &&other)
 339         : d(other.d)
 340     {
 341         other.d = static_cast<QMapData<Key, T> *>(
 342                 const_cast<QMapDataBase *>(&QMapDataBase::shared_null));
 343     }
 344
 345     inline QMap<Key, T> &operator=(QMap<Key, T> &&other)
 346     { qSwap(d, other.d); return *this; }
 347 #endif
 348     inline void swap(QMap<Key, T> &other) { qSwap(d, other.d); }
 349     explicit QMap(const typename std::map<Key, T> &other);
 350     std::map<Key, T> toStdMap() const;
 351
 352     bool operator==(const QMap<Key, T> &other) const;
 353     inline bool operator!=(const QMap<Key, T> &other) const { return !(*this == other); }
 354
 355     inline int size() const { return d->size; }
 356
 357     inline bool isEmpty() const { return d->size == 0; }
 358
 359     inline void detach() { if (d->ref.isShared()) detach_helper(); }
 360     inline bool isDetached() const { return !d->ref.isShared(); }
 361     inline void setSharable(bool sharable)
 362     {
 363         if (sharable == d->ref.isSharable())
 364             return;
 365         if (!sharable)
 366             detach();
 367         // Don't call on shared_null
 368         d->ref.setSharable(sharable);
 369     }
 370     inline bool isSharedWith(const QMap<Key, T> &other) const { return d == other.d; }
 371
 372     void clear();
 373
 374     int remove(const Key &key);
 375     T take(const Key &key);
 376
 377     bool contains(const Key &key) const;
 378     const Key key(const T &value, const Key &defaultKey = Key()) const;
 379     const T value(const Key &key, const T &defaultValue = T()) const;
 380     T &operator[](const Key &key);
 381     const T operator[](const Key &key) const;
 382
 383     QList<Key> uniqueKeys() const;
 384     QList<Key> keys() const;
 385     QList<Key> keys(const T &value) const;
 386     QList<T> values() const;
 387     QList<T> values(const Key &key) const;
 388     int count(const Key &key) const;
 389
 390     class const_iterator;
 391
 392     class iterator
 393     {
 394         friend class const_iterator;
 395         Node *i;
 396
 397     public:
 398         typedef std::bidirectional_iterator_tag iterator_category;
 399         typedef qptrdiff difference_type;
 400         typedef T value_type;
 401         typedef T *pointer;
 402         typedef T &reference;
 403
 404         inline iterator() : i(0) { }
 405         inline iterator(Node *node) : i(node) { }
 406
 407         inline const Key &key() const { return i->key; }
 408         inline T &value() const { return i->value; }
 409         inline T &operator*() const { return i->value; }
 410         inline T *operator->() const { return &i->value; }
 411         inline bool operator==(const iterator &o) const { return i == o.i; }
 412         inline bool operator!=(const iterator &o) const { return i != o.i; }
 413
 414         inline iterator &operator++() {
 415             i = i->nextNode();
 416             return *this;
 417         }
 418         inline iterator operator++(int) {
 419             iterator r = *this;
 420             i = i->nextNode();
 421             return r;
 422         }
 423         inline iterator &operator--() {
 424             i = i->previousNode();
 425             return *this;
 426         }
 427         inline iterator operator--(int) {
 428             iterator r = *this;
 429             i = i->previousNode();
 430             return r;
 431         }
 432         inline iterator operator+(int j) const
 433         { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
 434         inline iterator operator-(int j) const { return operator+(-j); }
 435         inline iterator &operator+=(int j) { return *this = *this + j; }
 436         inline iterator &operator-=(int j) { return *this = *this - j; }
 437
 438 #ifdef QT_STRICT_ITERATORS
 439     private:
 440 #else
 441     public:
 442 #endif
 443         inline bool operator==(const const_iterator &o) const
 444             { return i == o.i; }
 445         inline bool operator!=(const const_iterator &o) const
 446             { return i != o.i; }
 447         friend class QMap<Key, T>;
 448     };
 449     friend class iterator;
 450
 451     class const_iterator
 452     {
 453         friend class iterator;
 454         const Node *i;
 455
 456     public:
 457         typedef std::bidirectional_iterator_tag iterator_category;
 458         typedef qptrdiff difference_type;
 459         typedef T value_type;
 460         typedef const T *pointer;
 461         typedef const T &reference;
 462
 463         inline const_iterator() : i(0) { }
 464         inline const_iterator(const Node *node) : i(node) { }
 465 #ifdef QT_STRICT_ITERATORS
 466         explicit inline const_iterator(const iterator &o)
 467 #else
 468         inline const_iterator(const iterator &o)
 469 #endif
 470         { i = o.i; }
 471
 472         inline const Key &key() const { return i->key; }
 473         inline const T &value() const { return i->value; }
 474         inline const T &operator*() const { return i->value; }
 475         inline const T *operator->() const { return &i->value; }
 476         inline bool operator==(const const_iterator &o) const { return i == o.i; }
 477         inline bool operator!=(const const_iterator &o) const { return i != o.i; }
 478
 479         inline const_iterator &operator++() {
 480             i = i->nextNode();
 481             return *this;
 482         }
 483         inline const_iterator operator++(int) {
 484             const_iterator r = *this;
 485             i = i->nextNode();
 486             return r;
 487         }
 488         inline const_iterator &operator--() {
 489             i = i->previousNode();
 490             return *this;
 491         }
 492         inline const_iterator operator--(int) {
 493             const_iterator r = *this;
 494             i = i->previousNode();
 495             return r;
 496         }
 497         inline const_iterator operator+(int j) const
 498         { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
 499         inline const_iterator operator-(int j) const { return operator+(-j); }
 500         inline const_iterator &operator+=(int j) { return *this = *this + j; }
 501         inline const_iterator &operator-=(int j) { return *this = *this - j; }
 502
 503 #ifdef QT_STRICT_ITERATORS
 504     private:
 505         inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); }
 506         inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); }
 507 #endif
 508         friend class QMap<Key, T>;
 509     };
 510     friend class const_iterator;
 511
 512     // STL style
 513     inline iterator begin() { detach(); return iterator(d->begin()); }
 514     inline const_iterator begin() const { return const_iterator(d->begin()); }
 515     inline const_iterator constBegin() const { return const_iterator(d->begin()); }
 516     inline const_iterator cbegin() const { return const_iterator(d->begin()); }
 517     inline iterator end() { detach(); return iterator(d->end()); }
 518     inline const_iterator end() const { return const_iterator(d->end()); }
 519     inline const_iterator constEnd() const { return const_iterator(d->end()); }
 520     inline const_iterator cend() const { return const_iterator(d->end()); }
 521     iterator erase(iterator it);
 522
 523     // more Qt
 524     typedef iterator Iterator;
 525     typedef const_iterator ConstIterator;
 526     inline int count() const { return d->size; }
 527     iterator find(const Key &key);
 528     const_iterator find(const Key &key) const;
 529     const_iterator constFind(const Key &key) const;
 530     iterator lowerBound(const Key &key);
 531     const_iterator lowerBound(const Key &key) const;
 532     iterator upperBound(const Key &key);
 533     const_iterator upperBound(const Key &key) const;
 534     iterator insert(const Key &key, const T &value);
 535     iterator insertMulti(const Key &key, const T &value);
 536     QMap<Key, T> &unite(const QMap<Key, T> &other);
 537
 538     // STL compatibility
 539     typedef Key key_type;
 540     typedef T mapped_type;
 541     typedef qptrdiff difference_type;
 542     typedef int size_type;
 543     inline bool empty() const { return isEmpty(); }
 544     QPair<iterator, iterator> equal_range(const Key &akey);
 545
 546 #ifdef Q_MAP_DEBUG
 547     void dump() const;
 548 #endif
 549
 550 private:
 551     void detach_helper();
 552 };
 553
 554 template <class Key, class T>
 555 inline QMap<Key, T>::QMap(const QMap<Key, T> &other)
 556 {
 557     if (other.d->ref.ref()) {
 558         d = other.d;
 559     } else {
 560         d = QMapData<Key, T>::create();
 561         if (other.d->header.left) {
 562             d->header.left = static_cast<Node *>(other.d->header.left)->copy(d);
 563             d->header.left->setParent(&d->header);
 564         }
 565     }
 566 }
 567
 568 template <class Key, class T>
 569 Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)
 570 {
 571     if (d != other.d) {
 572         QMap<Key, T> tmp(other);
 573         tmp.swap(*this);
 574     }
 575     return *this;
 576 }
 577
 578 template <class Key, class T>
 579 Q_INLINE_TEMPLATE void QMap<Key, T>::clear()
 580 {
 581     *this = QMap<Key, T>();
 582 }
 583
 584
 585 template <class Key, class T>
 586 Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey, const T &adefaultValue) const
 587 {
 588     Node *n = d->findNode(akey);
 589     return n ? n->value : adefaultValue;
 590 }
 591
 592 template <class Key, class T>
 593 Q_INLINE_TEMPLATE const T QMap<Key, T>::operator[](const Key &akey) const
 594 {
 595     return value(akey);
 596 }
 597
 598 template <class Key, class T>
 599 Q_INLINE_TEMPLATE T &QMap<Key, T>::operator[](const Key &akey)
 600 {
 601     detach();
 602     Node *n = d->findNode(akey);
 603     if (!n)
 604         return *insert(akey, T());
 605     return n->value;
 606 }
 607
 608 template <class Key, class T>
 609 Q_INLINE_TEMPLATE int QMap<Key, T>::count(const Key &akey) const
 610 {
 611     Node *firstNode;
 612     Node *lastNode;
 613     d->nodeRange(akey, &firstNode, &lastNode);
 614
 615     const_iterator first(firstNode);
 616     const const_iterator last(lastNode);
 617     int cnt = 0;
 618     while (first != last) {
 619         ++cnt;
 620         ++first;
 621     }
 622     return cnt;
 623 }
 624
 625 template <class Key, class T>
 626 Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const
 627 {
 628     return d->findNode(akey) != 0;
 629 }
 630
 631 template <class Key, class T>
 632 Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey, const T &avalue)
 633 {
 634     detach();
 635     Node *n = d->root();
 636     Node *y = d->end();
 637     Node *last = 0;
 638     bool  left = true;
 639     while (n) {
 640         y = n;
 641         if (!qMapLessThanKey(n->key, akey)) {
 642             last = n;
 643             left = true;
 644             n = n->leftNode();
 645         } else {
 646             left = false;
 647             n = n->rightNode();
 648         }
 649     }
 650     if (last && !qMapLessThanKey(akey, last->key)) {
 651         last->value = avalue;
 652         return iterator(last);
 653     }
 654     Node *z = d->createNode(akey, avalue, y, left);
 655     return iterator(z);
 656 }
 657
 658 template <class Key, class T>
 659 Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &akey,
 660                                                                             const T &avalue)
 661 {
 662     detach();
 663     Node* y = d->end();
 664     Node* x = static_cast<Node *>(d->root());
 665     bool left = true;
 666     while (x != 0) {
 667         left = !qMapLessThanKey(x->key, akey);
 668         y = x;
 669         x = left ? x->leftNode() : x->rightNode();
 670     }
 671     Node *z = d->createNode(akey, avalue, y, left);
 672     return iterator(z);
 673 }
 674
 675 template <class Key, class T>
 676 Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &akey) const
 677 {
 678     Node *n = d->findNode(akey);
 679     return const_iterator(n ? n : d->end());
 680 }
 681
 682 template <class Key, class T>
 683 Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const
 684 {
 685     return constFind(akey);
 686 }
 687
 688 template <class Key, class T>
 689 Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::find(const Key &akey)
 690 {
 691     detach();
 692     Node *n = d->findNode(akey);
 693     return iterator(n ? n : d->end());
 694 }
 695
 696 template <class Key, class T>
 697 Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other)
 698 {
 699     QMap<Key, T> copy(other);
 700     const_iterator it = copy.constEnd();
 701     const const_iterator b = copy.constBegin();
 702     while (it != b) {
 703         --it;
 704         insertMulti(it.key(), it.value());
 705     }
 706     return *this;
 707 }
 708
 709 template <class Key, class T>
 710 QPair<typename QMap<Key, T>::iterator, typename QMap<Key, T>::iterator> QMap<Key, T>::equal_range(const Key &akey)
 711 {
 712     detach();
 713     Node *first, *last;
 714     d->nodeRange(akey, &first, &last);
 715     return QPair<iterator, iterator>(iterator(first), iterator(last));
 716 }
 717
 718 #ifdef Q_MAP_DEBUG
 719 template <class Key, class T>
 720 void QMap<Key, T>::dump() const
 721 {
 722     const_iterator it = begin();
 723     qDebug() << "map dump:";
 724     while (it != end()) {
 725         const QMapNodeBase *n = it.i;
 726         int depth = 0;
 727         while (n && n != d->root()) {
 728             ++depth;
 729             n = n->parent();
 730         }
 731         QByteArray space(4*depth, ' ');
 732         qDebug() << space << (it.i->color() == Node::Red ? "Red  " : "Black") << it.i << it.i->left << it.i->right
 733                  << it.key() << it.value();
 734         ++it;
 735     }
 736     qDebug() << "---------";
 737 }
 738 #endif
 739
 740 template <class Key, class T>
 741 Q_OUTOFLINE_TEMPLATE int QMap<Key, T>::remove(const Key &akey)
 742 {
 743     detach();
 744     int n = 0;
 745     while (Node *node = d->findNode(akey)) {
 746         d->deleteNode(node);
 747         ++n;
 748     }
 749     return n;
 750 }
 751
 752 template <class Key, class T>
 753 Q_OUTOFLINE_TEMPLATE T QMap<Key, T>::take(const Key &akey)
 754 {
 755     detach();
 756
 757     Node *node = d->findNode(akey);
 758     if (node) {
 759         T t = node->value;
 760         d->deleteNode(node);
 761         return t;
 762     }
 763     return T();
 764 }
 765
 766 template <class Key, class T>
 767 Q_OUTOFLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::erase(iterator it)
 768 {
 769     if (it == iterator(d->end()))
 770         return it;
 771
 772     Node *n = it.i;
 773     ++it;
 774     d->deleteNode(n);
 775     return it;
 776 }
 777
 778 template <class Key, class T>
 779 Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper()
 780 {
 781     QMapData<Key, T> *x = QMapData<Key, T>::create();
 782     if (d->header.left) {
 783         x->header.left = static_cast<Node *>(d->header.left)->copy(x);
 784         x->header.left->setParent(&x->header);
 785     }
 786     if (!d->ref.deref())
 787         d->free();
 788     d = x;
 789 }
 790
 791 template <class Key, class T>
 792 Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::uniqueKeys() const
 793 {
 794     QList<Key> res;
 795     res.reserve(size()); // May be too much, but assume short lifetime
 796     const_iterator i = begin();
 797     if (i != end()) {
 798         for (;;) {
 799             const Key &aKey = i.key();
 800             res.append(aKey);
 801             do {
 802                 if (++i == end())
 803                     goto break_out_of_outer_loop;
 804             } while (!qMapLessThanKey(aKey, i.key()));   // loop while (key == i.key())
 805         }
 806     }
 807 break_out_of_outer_loop:
 808     return res;
 809 }
 810
 811 template <class Key, class T>
 812 Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys() const
 813 {
 814     QList<Key> res;
 815     res.reserve(size());
 816     const_iterator i = begin();
 817     while (i != end()) {
 818         res.append(i.key());
 819         ++i;
 820     }
 821     return res;
 822 }
 823
 824 template <class Key, class T>
 825 Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys(const T &avalue) const
 826 {
 827     QList<Key> res;
 828     const_iterator i = begin();
 829     while (i != end()) {
 830         if (i.value() == avalue)
 831             res.append(i.key());
 832         ++i;
 833     }
 834     return res;
 835 }
 836
 837 template <class Key, class T>
 838 Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue, const Key &defaultKey) const
 839 {
 840     const_iterator i = begin();
 841     while (i != end()) {
 842         if (i.value() == avalue)
 843             return i.key();
 844         ++i;
 845     }
 846
 847     return defaultKey;
 848 }
 849
 850 template <class Key, class T>
 851 Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values() const
 852 {
 853     QList<T> res;
 854     res.reserve(size());
 855     const_iterator i = begin();
 856     while (i != end()) {
 857         res.append(i.value());
 858         ++i;
 859     }
 860     return res;
 861 }
 862
 863 template <class Key, class T>
 864 Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values(const Key &akey) const
 865 {
 866     QList<T> res;
 867     Node *n = d->findNode(akey);
 868     if (n) {
 869         const_iterator it(n);
 870         do {
 871             res.append(*it);
 872             ++it;
 873         } while (it != constEnd() && !qMapLessThanKey<Key>(akey, it.key()));
 874     }
 875     return res;
 876 }
 877
 878 template <class Key, class T>
 879 Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::lowerBound(const Key &akey) const
 880 {
 881     Node *lb = d->root()->lowerBound(akey);
 882     if (!lb)
 883         lb = d->end();
 884     return const_iterator(lb);
 885 }
 886
 887 template <class Key, class T>
 888 Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &akey)
 889 {
 890     detach();
 891     Node *lb = d->root()->lowerBound(akey);
 892     if (!lb)
 893         lb = d->end();
 894     return iterator(lb);
 895 }
 896
 897 template <class Key, class T>
 898 Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
 899 QMap<Key, T>::upperBound(const Key &akey) const
 900 {
 901     Node *ub = d->root()->upperBound(akey);
 902     if (!ub)
 903         ub = d->end();
 904     return const_iterator(ub);
 905 }
 906
 907 template <class Key, class T>
 908 Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::upperBound(const Key &akey)
 909 {
 910     detach();
 911     Node *ub = d->root()->upperBound(akey);
 912     if (!ub)
 913         ub = d->end();
 914     return iterator(ub);
 915 }
 916
 917 template <class Key, class T>
 918 Q_OUTOFLINE_TEMPLATE bool QMap<Key, T>::operator==(const QMap<Key, T> &other) const
 919 {
 920     if (size() != other.size())
 921         return false;
 922     if (d == other.d)
 923         return true;
 924
 925     const_iterator it1 = begin();
 926     const_iterator it2 = other.begin();
 927
 928     while (it1 != end()) {
 929         if (!(it1.value() == it2.value()) || qMapLessThanKey(it1.key(), it2.key()) || qMapLessThanKey(it2.key(), it1.key()))
 930             return false;
 931         ++it2;
 932         ++it1;
 933     }
 934     return true;
 935 }
 936
 937 template <class Key, class T>
 938 Q_OUTOFLINE_TEMPLATE QMap<Key, T>::QMap(const std::map<Key, T> &other)
 939 {
 940     d = QMapData<Key, T>::create();
 941     typename std::map<Key,T>::const_iterator it = other.end();
 942     while (it != other.begin()) {
 943         --it;
 944         insert((*it).first, (*it).second);
 945     }
 946 }
 947
 948 template <class Key, class T>
 949 Q_OUTOFLINE_TEMPLATE std::map<Key, T> QMap<Key, T>::toStdMap() const
 950 {
 951     std::map<Key, T> map;
 952     const_iterator it = end();
 953     while (it != begin()) {
 954         --it;
 955         map.insert(std::pair<Key, T>(it.key(), it.value()));
 956     }
 957     return map;
 958 }
 959
 960 template <class Key, class T>
 961 class QMultiMap : public QMap<Key, T>
 962 {
 963 public:
 964     QMultiMap() {}
 965     QMultiMap(const QMap<Key, T> &other) : QMap<Key, T>(other) {}
 966     inline void swap(QMultiMap<Key, T> &other) { QMap<Key, T>::swap(other); }
 967
 968     inline typename QMap<Key, T>::iterator replace(const Key &key, const T &value)
 969     { return QMap<Key, T>::insert(key, value); }
 970     inline typename QMap<Key, T>::iterator insert(const Key &key, const T &value)
 971     { return QMap<Key, T>::insertMulti(key, value); }
 972
 973     inline QMultiMap &operator+=(const QMultiMap &other)
 974     { this->unite(other); return *this; }
 975     inline QMultiMap operator+(const QMultiMap &other) const
 976     { QMultiMap result = *this; result += other; return result; }
 977
 978 #if !defined(Q_NO_USING_KEYWORD) && !defined(Q_CC_RVCT)
 979     // RVCT compiler doesn't handle using-keyword right when used functions are overloaded in child class
 980     using QMap<Key, T>::contains;
 981     using QMap<Key, T>::remove;
 982     using QMap<Key, T>::count;
 983     using QMap<Key, T>::find;
 984     using QMap<Key, T>::constFind;
 985 #else
 986     inline bool contains(const Key &key) const
 987     { return QMap<Key, T>::contains(key); }
 988     inline int remove(const Key &key)
 989     { return QMap<Key, T>::remove(key); }
 990     inline int count(const Key &key) const
 991     { return QMap<Key, T>::count(key); }
 992     inline int count() const
 993     { return QMap<Key, T>::count(); }
 994     inline typename QMap<Key, T>::iterator find(const Key &key)
 995     { return QMap<Key, T>::find(key); }
 996     inline typename QMap<Key, T>::const_iterator find(const Key &key) const
 997     { return QMap<Key, T>::find(key); }
 998     inline typename QMap<Key, T>::const_iterator constFind(const Key &key) const
 999     { return QMap<Key, T>::constFind(key); }
1000 #endif
1001
1002     bool contains(const Key &key, const T &value) const;
1003
1004     int remove(const Key &key, const T &value);
1005
1006     int count(const Key &key, const T &value) const;
1007
1008     typename QMap<Key, T>::iterator find(const Key &key, const T &value) {
1009         typename QMap<Key, T>::iterator i(find(key));
1010         typename QMap<Key, T>::iterator end(this->end());
1011         while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1012             if (i.value() == value)
1013                 return i;
1014             ++i;
1015         }
1016         return end;
1017     }
1018     typename QMap<Key, T>::const_iterator find(const Key &key, const T &value) const {
1019         typename QMap<Key, T>::const_iterator i(constFind(key));
1020         typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
1021         while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1022             if (i.value() == value)
1023                 return i;
1024             ++i;
1025         }
1026         return end;
1027     }
1028     typename QMap<Key, T>::const_iterator constFind(const Key &key, const T &value) const
1029         { return find(key, value); }
1030 private:
1031     T &operator[](const Key &key);
1032     const T operator[](const Key &key) const;
1033 };
1034
1035 template <class Key, class T>
1036 Q_INLINE_TEMPLATE bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const
1037 {
1038     return constFind(key, value) != QMap<Key, T>::constEnd();
1039 }
1040
1041 template <class Key, class T>
1042 Q_INLINE_TEMPLATE int QMultiMap<Key, T>::remove(const Key &key, const T &value)
1043 {
1044     int n = 0;
1045     typename QMap<Key, T>::iterator i(find(key));
1046     typename QMap<Key, T>::iterator end(QMap<Key, T>::end());
1047     while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1048         if (i.value() == value) {
1049             i = this->erase(i);
1050             ++n;
1051         } else {
1052             ++i;
1053         }
1054     }
1055     return n;
1056 }
1057
1058 template <class Key, class T>
1059 Q_INLINE_TEMPLATE int QMultiMap<Key, T>::count(const Key &key, const T &value) const
1060 {
1061     int n = 0;
1062     typename QMap<Key, T>::const_iterator i(constFind(key));
1063     typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
1064     while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1065         if (i.value() == value)
1066             ++n;
1067         ++i;
1068     }
1069     return n;
1070 }
1071
1072 Q_DECLARE_ASSOCIATIVE_ITERATOR(Map)
1073 Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map)
1074
1075 QT_END_NAMESPACE
1076
1077 QT_END_HEADER
1078
1079 #endif // QMAP_H