1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2016 The Qt Company Ltd. |
4 | ** Contact: https://www.qt.io/licensing/ |
5 | ** |
6 | ** This file is part of the QtCore module of the Qt Toolkit. |
7 | ** |
8 | ** $QT_BEGIN_LICENSE:LGPL$ |
9 | ** Commercial License Usage |
10 | ** Licensees holding valid commercial Qt licenses may use this file in |
11 | ** accordance with the commercial license agreement provided with the |
12 | ** Software or, alternatively, in accordance with the terms contained in |
13 | ** a written agreement between you and The Qt Company. For licensing terms |
14 | ** and conditions see https://www.qt.io/terms-conditions. For further |
15 | ** information use the contact form at https://www.qt.io/contact-us. |
16 | ** |
17 | ** GNU Lesser General Public License Usage |
18 | ** Alternatively, this file may be used under the terms of the GNU Lesser |
19 | ** General Public License version 3 as published by the Free Software |
20 | ** Foundation and appearing in the file LICENSE.LGPL3 included in the |
21 | ** packaging of this file. Please review the following information to |
22 | ** ensure the GNU Lesser General Public License version 3 requirements |
23 | ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. |
24 | ** |
25 | ** GNU General Public License Usage |
26 | ** Alternatively, this file may be used under the terms of the GNU |
27 | ** General Public License version 2.0 or (at your option) the GNU General |
28 | ** Public license version 3 or any later version approved by the KDE Free |
29 | ** Qt Foundation. The licenses are as published by the Free Software |
30 | ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 |
31 | ** included in the packaging of this file. Please review the following |
32 | ** information to ensure the GNU General Public License requirements will |
33 | ** be met: https://www.gnu.org/licenses/gpl-2.0.html and |
34 | ** https://www.gnu.org/licenses/gpl-3.0.html. |
35 | ** |
36 | ** $QT_END_LICENSE$ |
37 | ** |
38 | ****************************************************************************/ |
39 | |
40 | #ifndef QMAP_H |
41 | #define QMAP_H |
42 | |
43 | #include <QtCore/qiterator.h> |
44 | #include <QtCore/qlist.h> |
45 | #include <QtCore/qrefcount.h> |
46 | #include <QtCore/qpair.h> |
47 | |
48 | #ifdef Q_MAP_DEBUG |
49 | #include <QtCore/qdebug.h> |
50 | #endif |
51 | |
52 | #include <functional> |
53 | #include <initializer_list> |
54 | #include <map> |
55 | #include <new> |
56 | |
57 | QT_BEGIN_NAMESPACE |
58 | |
59 | /* |
60 | QMap uses qMapLessThanKey() to compare keys. The default |
61 | implementation uses operator<(). For pointer types, |
62 | qMapLessThanKey() uses std::less (because operator<() on |
63 | pointers can be used only between pointers in the same array). |
64 | */ |
65 | |
66 | template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2) |
67 | { |
68 | return key1 < key2; |
69 | } |
70 | |
71 | template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2) |
72 | { |
73 | return std::less<const Ptr *>()(key1, key2); |
74 | } |
75 | |
76 | struct QMapDataBase; |
77 | template <class Key, class T> struct QMapData; |
78 | |
79 | struct Q_CORE_EXPORT QMapNodeBase |
80 | { |
81 | quintptr p; |
82 | QMapNodeBase *left; |
83 | QMapNodeBase *right; |
84 | |
85 | enum Color { Red = 0, Black = 1 }; |
86 | enum { Mask = 3 }; // reserve the second bit as well |
87 | |
88 | const QMapNodeBase *nextNode() const; |
89 | QMapNodeBase *nextNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->nextNode()); } |
90 | const QMapNodeBase *previousNode() const; |
91 | QMapNodeBase *previousNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->previousNode()); } |
92 | |
93 | Color color() const { return Color(p & 1); } |
94 | void setColor(Color c) { if (c == Black) p |= Black; else p &= ~Black; } |
95 | QMapNodeBase *parent() const { return reinterpret_cast<QMapNodeBase *>(p & ~Mask); } |
96 | void setParent(QMapNodeBase *pp) { p = (p & Mask) | quintptr(pp); } |
97 | |
98 | template <typename T> |
99 | static typename std::enable_if<QTypeInfo<T>::isComplex>::type |
100 | callDestructorIfNecessary(T &t) noexcept { Q_UNUSED(t); t.~T(); } // Q_UNUSED: silence MSVC unused 't' warning |
101 | template <typename T> |
102 | static typename std::enable_if<!QTypeInfo<T>::isComplex>::type |
103 | callDestructorIfNecessary(T &) noexcept {} |
104 | }; |
105 | |
106 | template <class Key, class T> |
107 | struct QMapNode : public QMapNodeBase |
108 | { |
109 | Key key; |
110 | T value; |
111 | |
112 | inline QMapNode *leftNode() const { return static_cast<QMapNode *>(left); } |
113 | inline QMapNode *rightNode() const { return static_cast<QMapNode *>(right); } |
114 | |
115 | inline const QMapNode *nextNode() const { return reinterpret_cast<const QMapNode *>(QMapNodeBase::nextNode()); } |
116 | inline const QMapNode *previousNode() const { return static_cast<const QMapNode *>(QMapNodeBase::previousNode()); } |
117 | inline QMapNode *nextNode() { return reinterpret_cast<QMapNode *>(QMapNodeBase::nextNode()); } |
118 | inline QMapNode *previousNode() { return static_cast<QMapNode *>(QMapNodeBase::previousNode()); } |
119 | |
120 | QMapNode<Key, T> *copy(QMapData<Key, T> *d) const; |
121 | |
122 | void destroySubTree() |
123 | { |
124 | callDestructorIfNecessary(key); |
125 | callDestructorIfNecessary(value); |
126 | doDestroySubTree(std::integral_constant<bool, QTypeInfo<T>::isComplex || QTypeInfo<Key>::isComplex>()); |
127 | } |
128 | |
129 | QMapNode<Key, T> *lowerBound(const Key &key); |
130 | QMapNode<Key, T> *upperBound(const Key &key); |
131 | |
132 | private: |
133 | void doDestroySubTree(std::false_type) {} |
134 | void doDestroySubTree(std::true_type) |
135 | { |
136 | if (left) |
137 | leftNode()->destroySubTree(); |
138 | if (right) |
139 | rightNode()->destroySubTree(); |
140 | } |
141 | |
142 | QMapNode() = delete; |
143 | Q_DISABLE_COPY(QMapNode) |
144 | }; |
145 | |
146 | template <class Key, class T> |
147 | inline QMapNode<Key, T> *QMapNode<Key, T>::lowerBound(const Key &akey) |
148 | { |
149 | QMapNode<Key, T> *n = this; |
150 | QMapNode<Key, T> *lastNode = nullptr; |
151 | while (n) { |
152 | if (!qMapLessThanKey(n->key, akey)) { |
153 | lastNode = n; |
154 | n = n->leftNode(); |
155 | } else { |
156 | n = n->rightNode(); |
157 | } |
158 | } |
159 | return lastNode; |
160 | } |
161 | |
162 | template <class Key, class T> |
163 | inline QMapNode<Key, T> *QMapNode<Key, T>::upperBound(const Key &akey) |
164 | { |
165 | QMapNode<Key, T> *n = this; |
166 | QMapNode<Key, T> *lastNode = nullptr; |
167 | while (n) { |
168 | if (qMapLessThanKey(akey, n->key)) { |
169 | lastNode = n; |
170 | n = n->leftNode(); |
171 | } else { |
172 | n = n->rightNode(); |
173 | } |
174 | } |
175 | return lastNode; |
176 | } |
177 | |
178 | |
179 | |
180 | struct Q_CORE_EXPORT QMapDataBase |
181 | { |
182 | QtPrivate::RefCount ref; |
183 | int size; |
184 | QMapNodeBase ; |
185 | QMapNodeBase *mostLeftNode; |
186 | |
187 | void rotateLeft(QMapNodeBase *x); |
188 | void rotateRight(QMapNodeBase *x); |
189 | void rebalance(QMapNodeBase *x); |
190 | void freeNodeAndRebalance(QMapNodeBase *z); |
191 | void recalcMostLeftNode(); |
192 | |
193 | QMapNodeBase *createNode(int size, int alignment, QMapNodeBase *parent, bool left); |
194 | void freeTree(QMapNodeBase *root, int alignment); |
195 | |
196 | static const QMapDataBase shared_null; |
197 | |
198 | static QMapDataBase *createData(); |
199 | static void freeData(QMapDataBase *d); |
200 | }; |
201 | |
202 | template <class Key, class T> |
203 | struct QMapData : public QMapDataBase |
204 | { |
205 | typedef QMapNode<Key, T> Node; |
206 | |
207 | Node *root() const { return static_cast<Node *>(header.left); } |
208 | |
209 | // using reinterpret_cast because QMapDataBase::header is not |
210 | // actually a QMapNode. |
211 | const Node *end() const { return reinterpret_cast<const Node *>(&header); } |
212 | Node *end() { return reinterpret_cast<Node *>(&header); } |
213 | const Node *begin() const { if (root()) return static_cast<const Node*>(mostLeftNode); return end(); } |
214 | Node *begin() { if (root()) return static_cast<Node*>(mostLeftNode); return end(); } |
215 | |
216 | void deleteNode(Node *z); |
217 | Node *findNode(const Key &akey) const; |
218 | void nodeRange(const Key &akey, Node **firstNode, Node **lastNode); |
219 | |
220 | Node *createNode(const Key &k, const T &v, Node *parent = nullptr, bool left = false) |
221 | { |
222 | Node *n = static_cast<Node *>(QMapDataBase::createNode(sizeof(Node), Q_ALIGNOF(Node), |
223 | parent, left)); |
224 | QT_TRY { |
225 | new (&n->key) Key(k); |
226 | QT_TRY { |
227 | new (&n->value) T(v); |
228 | } QT_CATCH(...) { |
229 | n->key.~Key(); |
230 | QT_RETHROW; |
231 | } |
232 | } QT_CATCH(...) { |
233 | QMapDataBase::freeNodeAndRebalance(n); |
234 | QT_RETHROW; |
235 | } |
236 | return n; |
237 | } |
238 | |
239 | static QMapData *create() { |
240 | return static_cast<QMapData *>(createData()); |
241 | } |
242 | |
243 | void destroy() { |
244 | if (root()) { |
245 | root()->destroySubTree(); |
246 | freeTree(header.left, Q_ALIGNOF(Node)); |
247 | } |
248 | freeData(this); |
249 | } |
250 | }; |
251 | |
252 | template <class Key, class T> |
253 | QMapNode<Key, T> *QMapNode<Key, T>::copy(QMapData<Key, T> *d) const |
254 | { |
255 | QMapNode<Key, T> *n = d->createNode(key, value); |
256 | n->setColor(color()); |
257 | if (left) { |
258 | n->left = leftNode()->copy(d); |
259 | n->left->setParent(n); |
260 | } else { |
261 | n->left = nullptr; |
262 | } |
263 | if (right) { |
264 | n->right = rightNode()->copy(d); |
265 | n->right->setParent(n); |
266 | } else { |
267 | n->right = nullptr; |
268 | } |
269 | return n; |
270 | } |
271 | |
272 | template <class Key, class T> |
273 | void QMapData<Key, T>::deleteNode(QMapNode<Key, T> *z) |
274 | { |
275 | QMapNodeBase::callDestructorIfNecessary(z->key); |
276 | QMapNodeBase::callDestructorIfNecessary(z->value); |
277 | freeNodeAndRebalance(z); |
278 | } |
279 | |
280 | template <class Key, class T> |
281 | QMapNode<Key, T> *QMapData<Key, T>::findNode(const Key &akey) const |
282 | { |
283 | if (Node *r = root()) { |
284 | Node *lb = r->lowerBound(akey); |
285 | if (lb && !qMapLessThanKey(akey, lb->key)) |
286 | return lb; |
287 | } |
288 | return nullptr; |
289 | } |
290 | |
291 | |
292 | template <class Key, class T> |
293 | void QMapData<Key, T>::nodeRange(const Key &akey, QMapNode<Key, T> **firstNode, QMapNode<Key, T> **lastNode) |
294 | { |
295 | Node *n = root(); |
296 | Node *l = end(); |
297 | while (n) { |
298 | if (qMapLessThanKey(akey, n->key)) { |
299 | l = n; |
300 | n = n->leftNode(); |
301 | } else if (qMapLessThanKey(n->key, akey)) { |
302 | n = n->rightNode(); |
303 | } else { |
304 | *firstNode = n->leftNode() ? n->leftNode()->lowerBound(akey) : nullptr; |
305 | if (!*firstNode) |
306 | *firstNode = n; |
307 | *lastNode = n->rightNode() ? n->rightNode()->upperBound(akey) : nullptr; |
308 | if (!*lastNode) |
309 | *lastNode = l; |
310 | return; |
311 | } |
312 | } |
313 | *firstNode = *lastNode = l; |
314 | } |
315 | |
316 | |
317 | template <class Key, class T> |
318 | class QMap |
319 | { |
320 | typedef QMapNode<Key, T> Node; |
321 | |
322 | QMapData<Key, T> *d; |
323 | |
324 | public: |
325 | inline QMap() noexcept : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null))) { } |
326 | inline QMap(std::initializer_list<std::pair<Key,T> > list) |
327 | : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null))) |
328 | { |
329 | for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it) |
330 | insert(it->first, it->second); |
331 | } |
332 | QMap(const QMap<Key, T> &other); |
333 | |
334 | inline ~QMap() { if (!d->ref.deref()) d->destroy(); } |
335 | |
336 | QMap<Key, T> &operator=(const QMap<Key, T> &other); |
337 | inline QMap(QMap<Key, T> &&other) noexcept |
338 | : d(other.d) |
339 | { |
340 | other.d = static_cast<QMapData<Key, T> *>( |
341 | const_cast<QMapDataBase *>(&QMapDataBase::shared_null)); |
342 | } |
343 | |
344 | inline QMap<Key, T> &operator=(QMap<Key, T> &&other) noexcept |
345 | { QMap moved(std::move(other)); swap(moved); return *this; } |
346 | inline void swap(QMap<Key, T> &other) noexcept { qSwap(d, other.d); } |
347 | explicit QMap(const typename std::map<Key, T> &other); |
348 | std::map<Key, T> toStdMap() const; |
349 | |
350 | bool operator==(const QMap<Key, T> &other) const; |
351 | inline bool operator!=(const QMap<Key, T> &other) const { return !(*this == other); } |
352 | |
353 | inline int size() const { return d->size; } |
354 | |
355 | inline bool isEmpty() const { return d->size == 0; } |
356 | |
357 | inline void detach() { if (d->ref.isShared()) detach_helper(); } |
358 | inline bool isDetached() const { return !d->ref.isShared(); } |
359 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
360 | inline void setSharable(bool sharable) |
361 | { |
362 | if (sharable == d->ref.isSharable()) |
363 | return; |
364 | if (!sharable) |
365 | detach(); |
366 | // Don't call on shared_null |
367 | d->ref.setSharable(sharable); |
368 | } |
369 | #endif |
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> keys() const; |
384 | QList<Key> keys(const T &value) const; |
385 | QList<T> values() const; |
386 | #if QT_DEPRECATED_SINCE(5, 15) |
387 | QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key." ) QList<Key> uniqueKeys() const; |
388 | QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key." ) QList<T> values(const Key &key) const; |
389 | #endif |
390 | int count(const Key &key) const; |
391 | |
392 | |
393 | inline const Key &firstKey() const { Q_ASSERT(!isEmpty()); return constBegin().key(); } |
394 | inline const Key &lastKey() const { Q_ASSERT(!isEmpty()); return (constEnd() - 1).key(); } |
395 | |
396 | inline T &first() { Q_ASSERT(!isEmpty()); return *begin(); } |
397 | inline const T &first() const { Q_ASSERT(!isEmpty()); return *constBegin(); } |
398 | inline T &last() { Q_ASSERT(!isEmpty()); return *(end() - 1); } |
399 | inline const T &last() const { Q_ASSERT(!isEmpty()); return *(constEnd() - 1); } |
400 | |
401 | class const_iterator; |
402 | |
403 | class iterator |
404 | { |
405 | friend class const_iterator; |
406 | Node *i; |
407 | |
408 | public: |
409 | typedef std::bidirectional_iterator_tag iterator_category; |
410 | typedef qptrdiff difference_type; |
411 | typedef T value_type; |
412 | typedef T *pointer; |
413 | typedef T &reference; |
414 | |
415 | inline iterator() : i(nullptr) { } |
416 | inline iterator(Node *node) : i(node) { } |
417 | |
418 | inline const Key &key() const { return i->key; } |
419 | inline T &value() const { return i->value; } |
420 | inline T &operator*() const { return i->value; } |
421 | inline T *operator->() const { return &i->value; } |
422 | inline bool operator==(const iterator &o) const { return i == o.i; } |
423 | inline bool operator!=(const iterator &o) const { return i != o.i; } |
424 | |
425 | inline iterator &operator++() { |
426 | i = i->nextNode(); |
427 | return *this; |
428 | } |
429 | inline iterator operator++(int) { |
430 | iterator r = *this; |
431 | i = i->nextNode(); |
432 | return r; |
433 | } |
434 | inline iterator &operator--() { |
435 | i = i->previousNode(); |
436 | return *this; |
437 | } |
438 | inline iterator operator--(int) { |
439 | iterator r = *this; |
440 | i = i->previousNode(); |
441 | return r; |
442 | } |
443 | inline iterator operator+(int j) const |
444 | { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; } |
445 | inline iterator operator-(int j) const { return operator+(-j); } |
446 | inline iterator &operator+=(int j) { return *this = *this + j; } |
447 | inline iterator &operator-=(int j) { return *this = *this - j; } |
448 | friend inline iterator operator+(int j, iterator k) { return k + j; } |
449 | |
450 | #ifndef QT_STRICT_ITERATORS |
451 | public: |
452 | inline bool operator==(const const_iterator &o) const |
453 | { return i == o.i; } |
454 | inline bool operator!=(const const_iterator &o) const |
455 | { return i != o.i; } |
456 | #endif |
457 | friend class QMap<Key, T>; |
458 | friend class QMultiMap<Key, T>; |
459 | }; |
460 | friend class iterator; |
461 | |
462 | class const_iterator |
463 | { |
464 | friend class iterator; |
465 | const Node *i; |
466 | |
467 | public: |
468 | typedef std::bidirectional_iterator_tag iterator_category; |
469 | typedef qptrdiff difference_type; |
470 | typedef T value_type; |
471 | typedef const T *pointer; |
472 | typedef const T &reference; |
473 | |
474 | Q_DECL_CONSTEXPR inline const_iterator() : i(nullptr) { } |
475 | inline const_iterator(const Node *node) : i(node) { } |
476 | #ifdef QT_STRICT_ITERATORS |
477 | explicit inline const_iterator(const iterator &o) |
478 | #else |
479 | inline const_iterator(const iterator &o) |
480 | #endif |
481 | { i = o.i; } |
482 | |
483 | inline const Key &key() const { return i->key; } |
484 | inline const T &value() const { return i->value; } |
485 | inline const T &operator*() const { return i->value; } |
486 | inline const T *operator->() const { return &i->value; } |
487 | Q_DECL_CONSTEXPR inline bool operator==(const const_iterator &o) const { return i == o.i; } |
488 | Q_DECL_CONSTEXPR inline bool operator!=(const const_iterator &o) const { return i != o.i; } |
489 | |
490 | inline const_iterator &operator++() { |
491 | i = i->nextNode(); |
492 | return *this; |
493 | } |
494 | inline const_iterator operator++(int) { |
495 | const_iterator r = *this; |
496 | i = i->nextNode(); |
497 | return r; |
498 | } |
499 | inline const_iterator &operator--() { |
500 | i = i->previousNode(); |
501 | return *this; |
502 | } |
503 | inline const_iterator operator--(int) { |
504 | const_iterator r = *this; |
505 | i = i->previousNode(); |
506 | return r; |
507 | } |
508 | inline const_iterator operator+(int j) const |
509 | { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; } |
510 | inline const_iterator operator-(int j) const { return operator+(-j); } |
511 | inline const_iterator &operator+=(int j) { return *this = *this + j; } |
512 | inline const_iterator &operator-=(int j) { return *this = *this - j; } |
513 | friend inline const_iterator operator+(int j, const_iterator k) { return k + j; } |
514 | |
515 | #ifdef QT_STRICT_ITERATORS |
516 | private: |
517 | inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); } |
518 | inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); } |
519 | #endif |
520 | friend class QMap<Key, T>; |
521 | friend class QMultiMap<Key, T>; |
522 | }; |
523 | friend class const_iterator; |
524 | |
525 | class key_iterator |
526 | { |
527 | const_iterator i; |
528 | |
529 | public: |
530 | typedef typename const_iterator::iterator_category iterator_category; |
531 | typedef typename const_iterator::difference_type difference_type; |
532 | typedef Key value_type; |
533 | typedef const Key *pointer; |
534 | typedef const Key &reference; |
535 | |
536 | key_iterator() = default; |
537 | explicit key_iterator(const_iterator o) : i(o) { } |
538 | |
539 | const Key &operator*() const { return i.key(); } |
540 | const Key *operator->() const { return &i.key(); } |
541 | bool operator==(key_iterator o) const { return i == o.i; } |
542 | bool operator!=(key_iterator o) const { return i != o.i; } |
543 | |
544 | inline key_iterator &operator++() { ++i; return *this; } |
545 | inline key_iterator operator++(int) { return key_iterator(i++);} |
546 | inline key_iterator &operator--() { --i; return *this; } |
547 | inline key_iterator operator--(int) { return key_iterator(i--); } |
548 | const_iterator base() const { return i; } |
549 | }; |
550 | |
551 | typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator; |
552 | typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator; |
553 | |
554 | // STL style |
555 | inline iterator begin() { detach(); return iterator(d->begin()); } |
556 | inline const_iterator begin() const { return const_iterator(d->begin()); } |
557 | inline const_iterator constBegin() const { return const_iterator(d->begin()); } |
558 | inline const_iterator cbegin() const { return const_iterator(d->begin()); } |
559 | inline iterator end() { detach(); return iterator(d->end()); } |
560 | inline const_iterator end() const { return const_iterator(d->end()); } |
561 | inline const_iterator constEnd() const { return const_iterator(d->end()); } |
562 | inline const_iterator cend() const { return const_iterator(d->end()); } |
563 | inline key_iterator keyBegin() const { return key_iterator(begin()); } |
564 | inline key_iterator keyEnd() const { return key_iterator(end()); } |
565 | inline key_value_iterator keyValueBegin() { return key_value_iterator(begin()); } |
566 | inline key_value_iterator keyValueEnd() { return key_value_iterator(end()); } |
567 | inline const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); } |
568 | inline const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); } |
569 | inline const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); } |
570 | inline const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); } |
571 | iterator erase(iterator it); |
572 | |
573 | // more Qt |
574 | typedef iterator Iterator; |
575 | typedef const_iterator ConstIterator; |
576 | inline int count() const { return d->size; } |
577 | iterator find(const Key &key); |
578 | const_iterator find(const Key &key) const; |
579 | const_iterator constFind(const Key &key) const; |
580 | iterator lowerBound(const Key &key); |
581 | const_iterator lowerBound(const Key &key) const; |
582 | iterator upperBound(const Key &key); |
583 | const_iterator upperBound(const Key &key) const; |
584 | iterator insert(const Key &key, const T &value); |
585 | iterator insert(const_iterator pos, const Key &key, const T &value); |
586 | void insert(const QMap<Key, T> &map); |
587 | #if QT_DEPRECATED_SINCE(5, 15) |
588 | QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key." ) iterator insertMulti(const Key &key, const T &value); |
589 | QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key." ) iterator insertMulti(const_iterator pos, const Key &akey, const T &avalue); |
590 | QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key." ) QMap<Key, T> &unite(const QMap<Key, T> &other); |
591 | #endif |
592 | |
593 | // STL compatibility |
594 | typedef Key key_type; |
595 | typedef T mapped_type; |
596 | typedef qptrdiff difference_type; |
597 | typedef int size_type; |
598 | inline bool empty() const { return isEmpty(); } |
599 | QPair<iterator, iterator> equal_range(const Key &akey); |
600 | QPair<const_iterator, const_iterator> equal_range(const Key &akey) const; |
601 | |
602 | #ifdef Q_MAP_DEBUG |
603 | void dump() const; |
604 | #endif |
605 | |
606 | private: |
607 | void detach_helper(); |
608 | bool isValidIterator(const const_iterator &ci) const |
609 | { |
610 | #if defined(QT_DEBUG) && !defined(Q_MAP_NO_ITERATOR_DEBUG) |
611 | const QMapNodeBase *n = ci.i; |
612 | while (n->parent()) |
613 | n = n->parent(); |
614 | return n->left == d->root(); |
615 | #else |
616 | Q_UNUSED(ci); |
617 | return true; |
618 | #endif |
619 | } |
620 | |
621 | friend class QMultiMap<Key, T>; |
622 | }; |
623 | |
624 | template <class Key, class T> |
625 | inline QMap<Key, T>::QMap(const QMap<Key, T> &other) |
626 | { |
627 | if (other.d->ref.ref()) { |
628 | d = other.d; |
629 | } else { |
630 | d = QMapData<Key, T>::create(); |
631 | if (other.d->header.left) { |
632 | d->header.left = static_cast<Node *>(other.d->header.left)->copy(d); |
633 | d->header.left->setParent(&d->header); |
634 | d->recalcMostLeftNode(); |
635 | } |
636 | } |
637 | } |
638 | |
639 | template <class Key, class T> |
640 | Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other) |
641 | { |
642 | if (d != other.d) { |
643 | QMap<Key, T> tmp(other); |
644 | tmp.swap(*this); |
645 | } |
646 | return *this; |
647 | } |
648 | |
649 | template <class Key, class T> |
650 | Q_INLINE_TEMPLATE void QMap<Key, T>::clear() |
651 | { |
652 | *this = QMap<Key, T>(); |
653 | } |
654 | |
655 | QT_WARNING_PUSH |
656 | QT_WARNING_DISABLE_CLANG("-Wreturn-stack-address" ) |
657 | |
658 | template <class Key, class T> |
659 | Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey, const T &adefaultValue) const |
660 | { |
661 | Node *n = d->findNode(akey); |
662 | return n ? n->value : adefaultValue; |
663 | } |
664 | |
665 | QT_WARNING_POP |
666 | |
667 | template <class Key, class T> |
668 | Q_INLINE_TEMPLATE const T QMap<Key, T>::operator[](const Key &akey) const |
669 | { |
670 | return value(akey); |
671 | } |
672 | |
673 | template <class Key, class T> |
674 | Q_INLINE_TEMPLATE T &QMap<Key, T>::operator[](const Key &akey) |
675 | { |
676 | detach(); |
677 | Node *n = d->findNode(akey); |
678 | if (!n) |
679 | return *insert(akey, T()); |
680 | return n->value; |
681 | } |
682 | |
683 | template <class Key, class T> |
684 | Q_INLINE_TEMPLATE int QMap<Key, T>::count(const Key &akey) const |
685 | { |
686 | Node *firstNode; |
687 | Node *lastNode; |
688 | d->nodeRange(akey, &firstNode, &lastNode); |
689 | |
690 | const_iterator ci_first(firstNode); |
691 | const const_iterator ci_last(lastNode); |
692 | int cnt = 0; |
693 | while (ci_first != ci_last) { |
694 | ++cnt; |
695 | ++ci_first; |
696 | } |
697 | return cnt; |
698 | } |
699 | |
700 | template <class Key, class T> |
701 | Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const |
702 | { |
703 | return d->findNode(akey) != nullptr; |
704 | } |
705 | |
706 | template <class Key, class T> |
707 | Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey, const T &avalue) |
708 | { |
709 | detach(); |
710 | Node *n = d->root(); |
711 | Node *y = d->end(); |
712 | Node *lastNode = nullptr; |
713 | bool left = true; |
714 | while (n) { |
715 | y = n; |
716 | if (!qMapLessThanKey(n->key, akey)) { |
717 | lastNode = n; |
718 | left = true; |
719 | n = n->leftNode(); |
720 | } else { |
721 | left = false; |
722 | n = n->rightNode(); |
723 | } |
724 | } |
725 | if (lastNode && !qMapLessThanKey(akey, lastNode->key)) { |
726 | lastNode->value = avalue; |
727 | return iterator(lastNode); |
728 | } |
729 | Node *z = d->createNode(akey, avalue, y, left); |
730 | return iterator(z); |
731 | } |
732 | |
733 | template <class Key, class T> |
734 | typename QMap<Key, T>::iterator QMap<Key, T>::insert(const_iterator pos, const Key &akey, const T &avalue) |
735 | { |
736 | if (d->ref.isShared()) |
737 | return this->insert(akey, avalue); |
738 | |
739 | Q_ASSERT_X(isValidIterator(pos), "QMap::insert" , "The specified const_iterator argument 'it' is invalid" ); |
740 | |
741 | if (pos == constEnd()) { |
742 | // Hint is that the Node is larger than (or equal to) the largest value. |
743 | Node *n = static_cast<Node *>(pos.i->left); |
744 | if (n) { |
745 | while (n->right) |
746 | n = static_cast<Node *>(n->right); |
747 | |
748 | if (!qMapLessThanKey(n->key, akey)) |
749 | return this->insert(akey, avalue); // ignore hint |
750 | // This can be optimized by checking equal too. |
751 | // we can overwrite if previous node key is strictly smaller |
752 | // (or there is no previous node) |
753 | |
754 | Node *z = d->createNode(akey, avalue, n, false); // insert right most |
755 | return iterator(z); |
756 | } |
757 | return this->insert(akey, avalue); |
758 | } else { |
759 | // Hint indicates that the node should be less (or equal to) the hint given |
760 | // but larger than the previous value. |
761 | Node *next = const_cast<Node*>(pos.i); |
762 | if (qMapLessThanKey(next->key, akey)) |
763 | return this->insert(akey, avalue); // ignore hint |
764 | |
765 | if (pos == constBegin()) { |
766 | // There is no previous value |
767 | // Maybe overwrite left most value |
768 | if (!qMapLessThanKey(akey, next->key)) { |
769 | next->value = avalue; // overwrite current iterator |
770 | return iterator(next); |
771 | } |
772 | // insert left most. |
773 | Node *z = d->createNode(akey, avalue, begin().i, true); |
774 | return iterator(z); |
775 | } else { |
776 | Node *prev = const_cast<Node*>(pos.i->previousNode()); |
777 | if (!qMapLessThanKey(prev->key, akey)) { |
778 | return this->insert(akey, avalue); // ignore hint |
779 | } |
780 | // Hint is ok |
781 | if (!qMapLessThanKey(akey, next->key)) { |
782 | next->value = avalue; // overwrite current iterator |
783 | return iterator(next); |
784 | } |
785 | |
786 | // we need to insert (not overwrite) |
787 | if (prev->right == nullptr) { |
788 | Node *z = d->createNode(akey, avalue, prev, false); |
789 | return iterator(z); |
790 | } |
791 | if (next->left == nullptr) { |
792 | Node *z = d->createNode(akey, avalue, next, true); |
793 | return iterator(z); |
794 | } |
795 | Q_ASSERT(false); // We should have prev->right == nullptr or next->left == nullptr. |
796 | return this->insert(akey, avalue); |
797 | } |
798 | } |
799 | } |
800 | |
801 | template <class Key, class T> |
802 | Q_INLINE_TEMPLATE void QMap<Key, T>::insert(const QMap<Key, T> &map) |
803 | { |
804 | if (d == map.d) |
805 | return; |
806 | |
807 | detach(); |
808 | |
809 | Node *n = d->root(); |
810 | auto it = map.cbegin(); |
811 | const auto e = map.cend(); |
812 | while (it != e) { |
813 | // Insertion here is based on insert(Key, T) |
814 | auto parent = d->end(); |
815 | bool left = true; |
816 | Node *lastNode = nullptr; |
817 | while (n) { |
818 | parent = n; |
819 | if (!qMapLessThanKey(n->key, it.key())) { |
820 | lastNode = n; |
821 | n = n->leftNode(); |
822 | left = true; |
823 | } else { |
824 | n = n->rightNode(); |
825 | left = false; |
826 | } |
827 | } |
828 | if (lastNode && !qMapLessThanKey(it.key(), lastNode->key)) { |
829 | lastNode->value = it.value(); |
830 | n = lastNode; |
831 | } else { |
832 | n = d->createNode(it.key(), it.value(), parent, left); |
833 | } |
834 | ++it; |
835 | if (it != e) { |
836 | // Move back up the tree until we find the next branch or node which is |
837 | // relevant for the next key. |
838 | while (n != d->root() && qMapLessThanKey(n->key, it.key())) |
839 | n = static_cast<Node *>(n->parent()); |
840 | } |
841 | } |
842 | } |
843 | |
844 | |
845 | template <class Key, class T> |
846 | Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &akey) const |
847 | { |
848 | Node *n = d->findNode(akey); |
849 | return const_iterator(n ? n : d->end()); |
850 | } |
851 | |
852 | template <class Key, class T> |
853 | Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const |
854 | { |
855 | return constFind(akey); |
856 | } |
857 | |
858 | template <class Key, class T> |
859 | Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::find(const Key &akey) |
860 | { |
861 | detach(); |
862 | Node *n = d->findNode(akey); |
863 | return iterator(n ? n : d->end()); |
864 | } |
865 | |
866 | template <class Key, class T> |
867 | QPair<typename QMap<Key, T>::iterator, typename QMap<Key, T>::iterator> QMap<Key, T>::equal_range(const Key &akey) |
868 | { |
869 | detach(); |
870 | Node *firstNode, *lastNode; |
871 | d->nodeRange(akey, &firstNode, &lastNode); |
872 | return QPair<iterator, iterator>(iterator(firstNode), iterator(lastNode)); |
873 | } |
874 | |
875 | template <class Key, class T> |
876 | QPair<typename QMap<Key, T>::const_iterator, typename QMap<Key, T>::const_iterator> |
877 | QMap<Key, T>::equal_range(const Key &akey) const |
878 | { |
879 | Node *firstNode, *lastNode; |
880 | d->nodeRange(akey, &firstNode, &lastNode); |
881 | return qMakePair(const_iterator(firstNode), const_iterator(lastNode)); |
882 | } |
883 | |
884 | #ifdef Q_MAP_DEBUG |
885 | template <class Key, class T> |
886 | void QMap<Key, T>::dump() const |
887 | { |
888 | const_iterator it = begin(); |
889 | qDebug("map dump:" ); |
890 | while (it != end()) { |
891 | const QMapNodeBase *n = it.i; |
892 | int depth = 0; |
893 | while (n && n != d->root()) { |
894 | ++depth; |
895 | n = n->parent(); |
896 | } |
897 | QByteArray space(4*depth, ' '); |
898 | qDebug() << space << (it.i->color() == Node::Red ? "Red " : "Black" ) << it.i << it.i->left << it.i->right |
899 | << it.key() << it.value(); |
900 | ++it; |
901 | } |
902 | qDebug("---------" ); |
903 | } |
904 | #endif |
905 | |
906 | template <class Key, class T> |
907 | Q_OUTOFLINE_TEMPLATE int QMap<Key, T>::remove(const Key &akey) |
908 | { |
909 | detach(); |
910 | int n = 0; |
911 | while (Node *node = d->findNode(akey)) { |
912 | d->deleteNode(node); |
913 | ++n; |
914 | } |
915 | return n; |
916 | } |
917 | |
918 | template <class Key, class T> |
919 | Q_OUTOFLINE_TEMPLATE T QMap<Key, T>::take(const Key &akey) |
920 | { |
921 | detach(); |
922 | |
923 | Node *node = d->findNode(akey); |
924 | if (node) { |
925 | T t = std::move(node->value); |
926 | d->deleteNode(node); |
927 | return t; |
928 | } |
929 | return T(); |
930 | } |
931 | |
932 | template <class Key, class T> |
933 | Q_OUTOFLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::erase(iterator it) |
934 | { |
935 | if (it == iterator(d->end())) |
936 | return it; |
937 | |
938 | Q_ASSERT_X(isValidIterator(const_iterator(it)), "QMap::erase" , "The specified iterator argument 'it' is invalid" ); |
939 | |
940 | if (d->ref.isShared()) { |
941 | const_iterator oldBegin = constBegin(); |
942 | const_iterator old = const_iterator(it); |
943 | int backStepsWithSameKey = 0; |
944 | |
945 | while (old != oldBegin) { |
946 | --old; |
947 | if (qMapLessThanKey(old.key(), it.key())) |
948 | break; |
949 | ++backStepsWithSameKey; |
950 | } |
951 | |
952 | it = find(old.key()); // ensures detach |
953 | Q_ASSERT_X(it != iterator(d->end()), "QMap::erase" , "Unable to locate same key in erase after detach." ); |
954 | |
955 | while (backStepsWithSameKey > 0) { |
956 | ++it; |
957 | --backStepsWithSameKey; |
958 | } |
959 | } |
960 | |
961 | Node *n = it.i; |
962 | ++it; |
963 | d->deleteNode(n); |
964 | return it; |
965 | } |
966 | |
967 | template <class Key, class T> |
968 | Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper() |
969 | { |
970 | QMapData<Key, T> *x = QMapData<Key, T>::create(); |
971 | if (d->header.left) { |
972 | x->header.left = static_cast<Node *>(d->header.left)->copy(x); |
973 | x->header.left->setParent(&x->header); |
974 | } |
975 | if (!d->ref.deref()) |
976 | d->destroy(); |
977 | d = x; |
978 | d->recalcMostLeftNode(); |
979 | } |
980 | |
981 | template <class Key, class T> |
982 | Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys() const |
983 | { |
984 | QList<Key> res; |
985 | res.reserve(size()); |
986 | const_iterator i = begin(); |
987 | while (i != end()) { |
988 | res.append(i.key()); |
989 | ++i; |
990 | } |
991 | return res; |
992 | } |
993 | |
994 | template <class Key, class T> |
995 | Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys(const T &avalue) const |
996 | { |
997 | QList<Key> res; |
998 | const_iterator i = begin(); |
999 | while (i != end()) { |
1000 | if (i.value() == avalue) |
1001 | res.append(i.key()); |
1002 | ++i; |
1003 | } |
1004 | return res; |
1005 | } |
1006 | |
1007 | template <class Key, class T> |
1008 | Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue, const Key &defaultKey) const |
1009 | { |
1010 | const_iterator i = begin(); |
1011 | while (i != end()) { |
1012 | if (i.value() == avalue) |
1013 | return i.key(); |
1014 | ++i; |
1015 | } |
1016 | |
1017 | return defaultKey; |
1018 | } |
1019 | |
1020 | template <class Key, class T> |
1021 | Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values() const |
1022 | { |
1023 | QList<T> res; |
1024 | res.reserve(size()); |
1025 | const_iterator i = begin(); |
1026 | while (i != end()) { |
1027 | res.append(i.value()); |
1028 | ++i; |
1029 | } |
1030 | return res; |
1031 | } |
1032 | |
1033 | template <class Key, class T> |
1034 | Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::lowerBound(const Key &akey) const |
1035 | { |
1036 | Node *lb = d->root() ? d->root()->lowerBound(akey) : nullptr; |
1037 | if (!lb) |
1038 | lb = d->end(); |
1039 | return const_iterator(lb); |
1040 | } |
1041 | |
1042 | template <class Key, class T> |
1043 | Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &akey) |
1044 | { |
1045 | detach(); |
1046 | Node *lb = d->root() ? d->root()->lowerBound(akey) : nullptr; |
1047 | if (!lb) |
1048 | lb = d->end(); |
1049 | return iterator(lb); |
1050 | } |
1051 | |
1052 | template <class Key, class T> |
1053 | Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator |
1054 | QMap<Key, T>::upperBound(const Key &akey) const |
1055 | { |
1056 | Node *ub = d->root() ? d->root()->upperBound(akey) : nullptr; |
1057 | if (!ub) |
1058 | ub = d->end(); |
1059 | return const_iterator(ub); |
1060 | } |
1061 | |
1062 | template <class Key, class T> |
1063 | Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::upperBound(const Key &akey) |
1064 | { |
1065 | detach(); |
1066 | Node *ub = d->root() ? d->root()->upperBound(akey) : nullptr; |
1067 | if (!ub) |
1068 | ub = d->end(); |
1069 | return iterator(ub); |
1070 | } |
1071 | |
1072 | template <class Key, class T> |
1073 | Q_OUTOFLINE_TEMPLATE bool QMap<Key, T>::operator==(const QMap<Key, T> &other) const |
1074 | { |
1075 | if (size() != other.size()) |
1076 | return false; |
1077 | if (d == other.d) |
1078 | return true; |
1079 | |
1080 | const_iterator it1 = begin(); |
1081 | const_iterator it2 = other.begin(); |
1082 | |
1083 | while (it1 != end()) { |
1084 | if (!(it1.value() == it2.value()) || qMapLessThanKey(it1.key(), it2.key()) || qMapLessThanKey(it2.key(), it1.key())) |
1085 | return false; |
1086 | ++it2; |
1087 | ++it1; |
1088 | } |
1089 | return true; |
1090 | } |
1091 | |
1092 | template <class Key, class T> |
1093 | Q_OUTOFLINE_TEMPLATE QMap<Key, T>::QMap(const std::map<Key, T> &other) |
1094 | { |
1095 | d = QMapData<Key, T>::create(); |
1096 | typename std::map<Key,T>::const_iterator it = other.end(); |
1097 | while (it != other.begin()) { |
1098 | --it; |
1099 | d->createNode((*it).first, (*it).second, d->begin(), true); // insert on most left node. |
1100 | } |
1101 | } |
1102 | |
1103 | template <class Key, class T> |
1104 | Q_OUTOFLINE_TEMPLATE std::map<Key, T> QMap<Key, T>::toStdMap() const |
1105 | { |
1106 | std::map<Key, T> map; |
1107 | const_iterator it = end(); |
1108 | while (it != begin()) { |
1109 | --it; |
1110 | map.insert(map.begin(), std::pair<Key, T>(it.key(), it.value())); |
1111 | } |
1112 | return map; |
1113 | } |
1114 | |
1115 | template <class Key, class T> |
1116 | class QMultiMap : public QMap<Key, T> |
1117 | { |
1118 | public: |
1119 | QMultiMap() noexcept {} |
1120 | inline QMultiMap(std::initializer_list<std::pair<Key,T> > list) |
1121 | { |
1122 | for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it) |
1123 | insert(it->first, it->second); |
1124 | } |
1125 | QMultiMap(const QMap<Key, T> &other) : QMap<Key, T>(other) {} |
1126 | QMultiMap(QMap<Key, T> &&other) noexcept : QMap<Key, T>(std::move(other)) {} |
1127 | void swap(QMultiMap<Key, T> &other) noexcept { QMap<Key, T>::swap(other); } |
1128 | |
1129 | QList<Key> uniqueKeys() const; |
1130 | QList<T> values(const Key &key) const; |
1131 | |
1132 | inline typename QMap<Key, T>::iterator replace(const Key &key, const T &value) |
1133 | { return QMap<Key, T>::insert(key, value); } |
1134 | typename QMap<Key, T>::iterator insert(const Key &key, const T &value); |
1135 | //! [qmultimap-insert-pos] |
1136 | typename QMap<Key, T>::iterator insert(typename QMap<Key, T>::const_iterator pos, |
1137 | const Key &key, const T &value); |
1138 | |
1139 | //! [qmultimap-unite] |
1140 | QMultiMap &unite(const QMultiMap &other); |
1141 | inline QMultiMap &operator+=(const QMultiMap &other) |
1142 | { return unite(other); } |
1143 | inline QMultiMap operator+(const QMultiMap &other) const |
1144 | { QMultiMap result = *this; result += other; return result; } |
1145 | |
1146 | using QMap<Key, T>::contains; |
1147 | using QMap<Key, T>::remove; |
1148 | using QMap<Key, T>::count; |
1149 | using QMap<Key, T>::find; |
1150 | using QMap<Key, T>::constFind; |
1151 | using QMap<Key, T>::values; |
1152 | using QMap<Key, T>::size; |
1153 | using QMap<Key, T>::detach; |
1154 | using QMap<Key, T>::erase; |
1155 | using QMap<Key, T>::isValidIterator; |
1156 | using typename QMap<Key, T>::Node; |
1157 | |
1158 | bool contains(const Key &key, const T &value) const; |
1159 | |
1160 | int remove(const Key &key, const T &value); |
1161 | |
1162 | int count(const Key &key, const T &value) const; |
1163 | |
1164 | typename QMap<Key, T>::iterator find(const Key &key, const T &value) { |
1165 | typename QMap<Key, T>::iterator i(find(key)); |
1166 | typename QMap<Key, T>::iterator end(this->end()); |
1167 | while (i != end && !qMapLessThanKey<Key>(key, i.key())) { |
1168 | if (i.value() == value) |
1169 | return i; |
1170 | ++i; |
1171 | } |
1172 | return end; |
1173 | } |
1174 | typename QMap<Key, T>::const_iterator find(const Key &key, const T &value) const { |
1175 | typename QMap<Key, T>::const_iterator i(constFind(key)); |
1176 | typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd()); |
1177 | while (i != end && !qMapLessThanKey<Key>(key, i.key())) { |
1178 | if (i.value() == value) |
1179 | return i; |
1180 | ++i; |
1181 | } |
1182 | return end; |
1183 | } |
1184 | typename QMap<Key, T>::const_iterator constFind(const Key &key, const T &value) const |
1185 | { return find(key, value); } |
1186 | private: |
1187 | T &operator[](const Key &key); |
1188 | const T operator[](const Key &key) const; |
1189 | }; |
1190 | |
1191 | template <class Key, class T> |
1192 | Q_OUTOFLINE_TEMPLATE QList<Key> QMultiMap<Key, T>::uniqueKeys() const |
1193 | { |
1194 | QList<Key> res; |
1195 | res.reserve(size()); // May be too much, but assume short lifetime |
1196 | typename QMap<Key, T>::const_iterator i = this->begin(); |
1197 | if (i != this->end()) { |
1198 | for (;;) { |
1199 | const Key &aKey = i.key(); |
1200 | res.append(aKey); |
1201 | do { |
1202 | if (++i == this->end()) |
1203 | goto break_out_of_outer_loop; |
1204 | } while (!qMapLessThanKey(aKey, i.key())); // loop while (key == i.key()) |
1205 | } |
1206 | } |
1207 | break_out_of_outer_loop: |
1208 | return res; |
1209 | } |
1210 | |
1211 | template <class Key, class T> |
1212 | Q_OUTOFLINE_TEMPLATE QList<T> QMultiMap<Key, T>::values(const Key &akey) const |
1213 | { |
1214 | QList<T> res; |
1215 | Node *n = this->d->findNode(akey); |
1216 | if (n) { |
1217 | typename QMap<Key, T>::const_iterator it(n); |
1218 | do { |
1219 | res.append(*it); |
1220 | ++it; |
1221 | } while (it != this->constEnd() && !qMapLessThanKey<Key>(akey, it.key())); |
1222 | } |
1223 | return res; |
1224 | } |
1225 | |
1226 | template <class Key, class T> |
1227 | Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMultiMap<Key, T>::insert(const Key &akey, |
1228 | const T &avalue) |
1229 | { |
1230 | detach(); |
1231 | Node* y = this->d->end(); |
1232 | Node* x = static_cast<Node *>(this->d->root()); |
1233 | bool left = true; |
1234 | while (x != nullptr) { |
1235 | left = !qMapLessThanKey(x->key, akey); |
1236 | y = x; |
1237 | x = left ? x->leftNode() : x->rightNode(); |
1238 | } |
1239 | Node *z = this->d->createNode(akey, avalue, y, left); |
1240 | return typename QMap<Key, T>::iterator(z); |
1241 | } |
1242 | |
1243 | #ifndef Q_CLANG_QDOC |
1244 | template <class Key, class T> |
1245 | typename QMap<Key, T>::iterator QMultiMap<Key, T>::insert(typename QMap<Key, T>::const_iterator pos, |
1246 | const Key &akey, const T &avalue) |
1247 | { |
1248 | if (this->d->ref.isShared()) |
1249 | return insert(akey, avalue); |
1250 | |
1251 | Q_ASSERT_X(isValidIterator(pos), "QMap::insert" , "The specified const_iterator argument 'pos' is invalid" ); |
1252 | |
1253 | if (pos == this->constEnd()) { |
1254 | // Hint is that the Node is larger than (or equal to) the largest value. |
1255 | Node *n = static_cast<Node *>(pos.i->left); |
1256 | if (n) { |
1257 | while (n->right) |
1258 | n = static_cast<Node *>(n->right); |
1259 | |
1260 | if (!qMapLessThanKey(n->key, akey)) |
1261 | return insert(akey, avalue); // ignore hint |
1262 | Node *z = this->d->createNode(akey, avalue, n, false); // insert right most |
1263 | return typename QMap<Key, T>::iterator(z); |
1264 | } |
1265 | return insert(akey, avalue); |
1266 | } else { |
1267 | // Hint indicates that the node should be less (or equal to) the hint given |
1268 | // but larger than the previous value. |
1269 | Node *next = const_cast<Node*>(pos.i); |
1270 | if (qMapLessThanKey(next->key, akey)) |
1271 | return insert(akey, avalue); // ignore hint |
1272 | |
1273 | if (pos == this->constBegin()) { |
1274 | // There is no previous value (insert left most) |
1275 | Node *z = this->d->createNode(akey, avalue, this->begin().i, true); |
1276 | return typename QMap<Key, T>::iterator(z); |
1277 | } else { |
1278 | Node *prev = const_cast<Node*>(pos.i->previousNode()); |
1279 | if (!qMapLessThanKey(prev->key, akey)) |
1280 | return insert(akey, avalue); // ignore hint |
1281 | |
1282 | // Hint is ok - do insert |
1283 | if (prev->right == nullptr) { |
1284 | Node *z = this->d->createNode(akey, avalue, prev, false); |
1285 | return typename QMap<Key, T>::iterator(z); |
1286 | } |
1287 | if (next->left == nullptr) { |
1288 | Node *z = this->d->createNode(akey, avalue, next, true); |
1289 | return typename QMap<Key, T>::iterator(z); |
1290 | } |
1291 | Q_ASSERT(false); // We should have prev->right == nullptr or next->left == nullptr. |
1292 | return insert(akey, avalue); |
1293 | } |
1294 | } |
1295 | } |
1296 | |
1297 | template <class Key, class T> |
1298 | Q_INLINE_TEMPLATE QMultiMap<Key, T> &QMultiMap<Key, T>::unite(const QMultiMap<Key, T> &other) |
1299 | { |
1300 | QMultiMap<Key, T> copy(other); |
1301 | typename QMap<Key, T>::const_iterator it = copy.constEnd(); |
1302 | const typename QMap<Key, T>::const_iterator b = copy.constBegin(); |
1303 | while (it != b) { |
1304 | --it; |
1305 | insert(it.key(), it.value()); |
1306 | } |
1307 | return *this; |
1308 | } |
1309 | #endif // Q_CLANG_QDOC |
1310 | |
1311 | template <class Key, class T> |
1312 | Q_INLINE_TEMPLATE bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const |
1313 | { |
1314 | return constFind(key, value) != QMap<Key, T>::constEnd(); |
1315 | } |
1316 | |
1317 | template <class Key, class T> |
1318 | Q_INLINE_TEMPLATE int QMultiMap<Key, T>::remove(const Key &key, const T &value) |
1319 | { |
1320 | int n = 0; |
1321 | typename QMap<Key, T>::iterator i(find(key)); |
1322 | typename QMap<Key, T>::iterator end(QMap<Key, T>::end()); |
1323 | while (i != end && !qMapLessThanKey<Key>(key, i.key())) { |
1324 | if (i.value() == value) { |
1325 | i = erase(i); |
1326 | ++n; |
1327 | } else { |
1328 | ++i; |
1329 | } |
1330 | } |
1331 | return n; |
1332 | } |
1333 | |
1334 | template <class Key, class T> |
1335 | Q_INLINE_TEMPLATE int QMultiMap<Key, T>::count(const Key &key, const T &value) const |
1336 | { |
1337 | int n = 0; |
1338 | typename QMap<Key, T>::const_iterator i(constFind(key)); |
1339 | typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd()); |
1340 | while (i != end && !qMapLessThanKey<Key>(key, i.key())) { |
1341 | if (i.value() == value) |
1342 | ++n; |
1343 | ++i; |
1344 | } |
1345 | return n; |
1346 | } |
1347 | |
1348 | #if QT_DEPRECATED_SINCE(5, 15) |
1349 | template<class Key, class T> |
1350 | QList<Key> QMap<Key, T>::uniqueKeys() const |
1351 | { |
1352 | return static_cast<const QMultiMap<Key, T> *>(this)->uniqueKeys(); |
1353 | } |
1354 | |
1355 | template<class Key, class T> |
1356 | QList<T> QMap<Key, T>::values(const Key &key) const |
1357 | { |
1358 | return static_cast<const QMultiMap<Key, T> *>(this)->values(key); |
1359 | } |
1360 | |
1361 | template<class Key, class T> |
1362 | typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &key, const T &value) |
1363 | { |
1364 | return static_cast<QMultiMap<Key, T> *>(this)->insert(key, value); |
1365 | } |
1366 | |
1367 | template<class Key, class T> |
1368 | typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const_iterator pos, const Key &akey, const T &avalue) |
1369 | { |
1370 | return static_cast<QMultiMap<Key, T> *>(this)->insert(pos, akey, avalue); |
1371 | } |
1372 | |
1373 | template<class Key, class T> |
1374 | QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other) |
1375 | { |
1376 | return static_cast<QMultiMap<Key, T> *>(this)->unite(other); |
1377 | } |
1378 | #endif |
1379 | |
1380 | Q_DECLARE_ASSOCIATIVE_ITERATOR(Map) |
1381 | Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map) |
1382 | |
1383 | QT_END_NAMESPACE |
1384 | |
1385 | #endif // QMAP_H |
1386 | |