From d98a1ef902527ca2351ec6bf18872a4226953487 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?M=C3=A5rten=20Nordheim?= <marten.nordheim@qt.io>
Date: Wed, 6 Nov 2019 18:04:45 +0100
Subject: Add QMap::insert(const QMap &map)

As opposed to unite(), this inserts one map into the other
without duplicating elements.

Task-number: QTBUG-35544
Change-Id: Ie8ab350b29148851a3176cef1007e8a4ca82c273
Reviewed-by: Lars Knoll <lars.knoll@qt.io>
---
 src/corelib/tools/qmap.h | 44 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 44 insertions(+)

(limited to 'src/corelib/tools/qmap.h')

diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h
index 18c681581f..fa736e8413 100644
--- a/src/corelib/tools/qmap.h
+++ b/src/corelib/tools/qmap.h
@@ -578,6 +578,7 @@ public:
     const_iterator upperBound(const Key &key) const;
     iterator insert(const Key &key, const T &value);
     iterator insert(const_iterator pos, const Key &key, const T &value);
+    void insert(const QMap<Key, T> &map);
     iterator insertMulti(const Key &key, const T &value);
     iterator insertMulti(const_iterator pos, const Key &akey, const T &avalue);
     QMap<Key, T> &unite(const QMap<Key, T> &other);
@@ -788,6 +789,49 @@ typename QMap<Key, T>::iterator QMap<Key, T>::insert(const_iterator pos, const K
     }
 }
 
+template <class Key, class T>
+Q_INLINE_TEMPLATE void QMap<Key, T>::insert(const QMap<Key, T> &map)
+{
+    if (d == map.d)
+        return;
+
+    detach();
+
+    Node *n = d->root();
+    auto it = map.cbegin();
+    const auto e = map.cend();
+    while (it != e) {
+        // Insertion here is based on insert(Key, T)
+        auto parent = d->end();
+        bool left = true;
+        Node *lastNode = nullptr;
+        while (n) {
+            parent = n;
+            if (!qMapLessThanKey(n->key, it.key())) {
+                lastNode = n;
+                n = n->leftNode();
+                left = true;
+            } else {
+                n = n->rightNode();
+                left = false;
+            }
+        }
+        if (lastNode && !qMapLessThanKey(it.key(), lastNode->key)) {
+            lastNode->value = it.value();
+            n = lastNode;
+        } else {
+            n = d->createNode(it.key(), it.value(), parent, left);
+        }
+        ++it;
+        if (it != e) {
+            // Move back up the tree until we find the next branch or node which is
+            // relevant for the next key.
+            while (n != d->root() && qMapLessThanKey(n->key, it.key()))
+                n = static_cast<Node *>(n->parent());
+        }
+    }
+}
+
 template <class Key, class T>
 Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &akey,
                                                                             const T &avalue)
-- 
cgit v1.2.3