1/****************************************************************************
2**
3** Copyright (C) 2020 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 QFLATMAP_P_H
41#define QFLATMAP_P_H
42
43//
44// W A R N I N G
45// -------------
46//
47// This file is not part of the Qt API. It exists for the convenience
48// of a number of Qt sources files. This header file may change from
49// version to version without notice, or even be removed.
50//
51// We mean it.
52//
53
54#include "qlist.h"
55
56#include <algorithm>
57#include <functional>
58#include <initializer_list>
59#include <iterator>
60#include <numeric>
61#include <type_traits>
62#include <utility>
63#include <vector>
64
65QT_BEGIN_NAMESPACE
66
67/*
68 QFlatMap provides an associative container backed by sorted sequential
69 containers. By default, QList is used.
70
71 Keys and values are stored in two separate containers. This provides improved
72 cache locality for key iteration and makes keys() and values() fast
73 operations.
74
75 One can customize the underlying container type by passing the KeyContainer
76 and MappedContainer template arguments:
77 QFlatMap<float, int, std::less<float>, std::vector<float>, std::vector<int>>
78*/
79
80namespace Qt {
81
82struct OrderedUniqueRange_t {};
83constexpr OrderedUniqueRange_t OrderedUniqueRange = {};
84
85} // namespace Qt
86
87template <class Key, class T, class Compare>
88class QFlatMapValueCompare : protected Compare
89{
90public:
91 QFlatMapValueCompare() = default;
92 QFlatMapValueCompare(const Compare &key_compare)
93 : Compare(key_compare)
94 {
95 }
96
97 using value_type = std::pair<const Key, T>;
98 static constexpr bool is_comparator_noexcept = noexcept(
99 std::declval<Compare>()(std::declval<Key>(), std::declval<Key>()));
100
101 bool operator()(const value_type &lhs, const value_type &rhs) const
102 noexcept(is_comparator_noexcept)
103 {
104 return Compare::operator()(lhs.first, rhs.first);
105 }
106};
107
108template<class Key, class T, class Compare = std::less<Key>, class KeyContainer = QList<Key>,
109 class MappedContainer = QList<T>>
110class QFlatMap : private QFlatMapValueCompare<Key, T, Compare>
111{
112 using full_map_t = QFlatMap<Key, T, Compare, KeyContainer, MappedContainer>;
113
114 template <class U>
115 class mock_pointer
116 {
117 U ref;
118 public:
119 mock_pointer(U r)
120 : ref(r)
121 {
122 }
123
124 U *operator->()
125 {
126 return &ref;
127 }
128 };
129
130public:
131 using key_type = Key;
132 using mapped_type = T;
133 using value_compare = QFlatMapValueCompare<Key, T, Compare>;
134 using value_type = typename value_compare::value_type;
135 using key_container_type = KeyContainer;
136 using mapped_container_type = MappedContainer;
137 using size_type = typename key_container_type::size_type;
138 using key_compare = Compare;
139
140 struct containers
141 {
142 key_container_type keys;
143 mapped_container_type values;
144 };
145
146 class iterator
147 {
148 public:
149 using difference_type = ptrdiff_t;
150 using value_type = std::pair<const Key, T>;
151 using reference = std::pair<const Key &, T &>;
152 using pointer = mock_pointer<reference>;
153 using iterator_category = std::random_access_iterator_tag;
154
155 iterator() = default;
156
157 iterator(containers *ac, size_type ai)
158 : c(ac), i(ai)
159 {
160 }
161
162 reference operator*()
163 {
164 return { c->keys[i], c->values[i] };
165 }
166
167 pointer operator->()
168 {
169 return { operator*() };
170 }
171
172 bool operator==(const iterator &o) const
173 {
174 return c == o.c && i == o.i;
175 }
176
177 bool operator!=(const iterator &o) const
178 {
179 return !operator==(o);
180 }
181
182 iterator &operator++()
183 {
184 ++i;
185 return *this;
186 }
187
188 iterator operator++(int)
189 {
190
191 iterator r = *this;
192 i++;
193 return r;
194 }
195
196 iterator &operator--()
197 {
198 --i;
199 return *this;
200 }
201
202 iterator operator--(int)
203 {
204 iterator r = *this;
205 i--;
206 return r;
207 }
208
209 iterator &operator+=(size_type n)
210 {
211 i += n;
212 return *this;
213 }
214
215 friend iterator operator+(size_type n, const iterator a)
216 {
217 iterator ret = a;
218 return ret += n;
219 }
220
221 friend iterator operator+(const iterator a, size_type n)
222 {
223 return n + a;
224 }
225
226 iterator &operator-=(size_type n)
227 {
228 i -= n;
229 return *this;
230 }
231
232 friend iterator operator-(const iterator a, size_type n)
233 {
234 iterator ret = a;
235 return ret -= n;
236 }
237
238 friend difference_type operator-(const iterator b, const iterator a)
239 {
240 return b.i - a.i;
241 }
242
243 reference operator[](size_type n)
244 {
245 size_type k = i + n;
246 return { c->keys[k], c->values[k] };
247 }
248
249 bool operator<(const iterator &other) const
250 {
251 return i < other.i;
252 }
253
254 bool operator>(const iterator &other) const
255 {
256 return i > other.i;
257 }
258
259 bool operator<=(const iterator &other) const
260 {
261 return i <= other.i;
262 }
263
264 bool operator>=(const iterator &other) const
265 {
266 return i >= other.i;
267 }
268
269 const Key &key() const { return c->keys[i]; }
270 T &value() { return c->values[i]; }
271
272 private:
273 containers *c = nullptr;
274 size_type i = 0;
275 friend full_map_t;
276 };
277
278 class const_iterator
279 {
280 public:
281 using difference_type = ptrdiff_t;
282 using value_type = std::pair<const Key, const T>;
283 using reference = std::pair<const Key &, const T &>;
284 using pointer = mock_pointer<reference>;
285 using iterator_category = std::random_access_iterator_tag;
286
287 const_iterator() = default;
288
289 const_iterator(const containers *ac, size_type ai)
290 : c(ac), i(ai)
291 {
292 }
293
294 const_iterator(iterator o)
295 : c(o.c), i(o.i)
296 {
297 }
298
299 reference operator*()
300 {
301 return { c->keys[i], c->values[i] };
302 }
303
304 pointer operator->()
305 {
306 return { operator*() };
307 }
308
309 bool operator==(const const_iterator &o) const
310 {
311 return c == o.c && i == o.i;
312 }
313
314 bool operator!=(const const_iterator &o) const
315 {
316 return !operator==(o);
317 }
318
319 const_iterator &operator++()
320 {
321 ++i;
322 return *this;
323 }
324
325 const_iterator operator++(int)
326 {
327
328 const_iterator r = *this;
329 i++;
330 return r;
331 }
332
333 const_iterator &operator--()
334 {
335 --i;
336 return *this;
337 }
338
339 const_iterator operator--(int)
340 {
341 const_iterator r = *this;
342 i--;
343 return r;
344 }
345
346 const_iterator &operator+=(size_type n)
347 {
348 i += n;
349 return *this;
350 }
351
352 friend const_iterator operator+(size_type n, const const_iterator a)
353 {
354 const_iterator ret = a;
355 return ret += n;
356 }
357
358 friend const_iterator operator+(const const_iterator a, size_type n)
359 {
360 return n + a;
361 }
362
363 const_iterator &operator-=(size_type n)
364 {
365 i -= n;
366 return *this;
367 }
368
369 friend const_iterator operator-(const const_iterator a, size_type n)
370 {
371 const_iterator ret = a;
372 return ret -= n;
373 }
374
375 friend difference_type operator-(const const_iterator b, const const_iterator a)
376 {
377 return b.i - a.i;
378 }
379
380 reference operator[](size_type n)
381 {
382 size_type k = i + n;
383 return { c->keys[k], c->values[k] };
384 }
385
386 bool operator<(const const_iterator &other) const
387 {
388 return i < other.i;
389 }
390
391 bool operator>(const const_iterator &other) const
392 {
393 return i > other.i;
394 }
395
396 bool operator<=(const const_iterator &other) const
397 {
398 return i <= other.i;
399 }
400
401 bool operator>=(const const_iterator &other) const
402 {
403 return i >= other.i;
404 }
405
406 const Key &key() const { return c->keys[i]; }
407 const T &value() { return c->values[i]; }
408
409 private:
410 const containers *c = nullptr;
411 size_type i = 0;
412 friend full_map_t;
413 };
414
415private:
416 template <class, class = void>
417 struct is_marked_transparent_type : std::false_type { };
418
419 template <class X>
420 struct is_marked_transparent_type<X, typename X::is_transparent> : std::true_type { };
421
422 template <class X>
423 using is_marked_transparent = typename std::enable_if<
424 is_marked_transparent_type<X>::value>::type *;
425
426 template <typename It>
427 using is_compatible_iterator = typename std::enable_if<
428 std::is_same<value_type, typename std::iterator_traits<It>::value_type>::value>::type *;
429
430public:
431 QFlatMap() = default;
432
433 explicit QFlatMap(const key_container_type &keys, const mapped_container_type &values)
434 : c{keys, values}
435 {
436 ensureOrderedUnique();
437 }
438
439 explicit QFlatMap(key_container_type &&keys, const mapped_container_type &values)
440 {
441 c.keys = std::move(keys);
442 c.values = values;
443 ensureOrderedUnique();
444 }
445
446 explicit QFlatMap(const key_container_type &keys, mapped_container_type &&values)
447 {
448 c.keys = keys;
449 c.values = std::move(values);
450 ensureOrderedUnique();
451 }
452
453 explicit QFlatMap(key_container_type &&keys, mapped_container_type &&values)
454 {
455 c.keys = std::move(keys);
456 c.values = std::move(values);
457 ensureOrderedUnique();
458 }
459
460 explicit QFlatMap(std::initializer_list<value_type> lst)
461 : QFlatMap(lst.begin(), lst.end())
462 {
463 }
464
465 template <class InputIt, is_compatible_iterator<InputIt> = nullptr>
466 explicit QFlatMap(InputIt first, InputIt last)
467 {
468 initWithRange(first, last);
469 ensureOrderedUnique();
470 }
471
472 explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys,
473 const mapped_container_type &values)
474 {
475 c.keys = keys;
476 c.values = values;
477 }
478
479 explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys,
480 const mapped_container_type &values)
481 {
482 c.keys = std::move(keys);
483 c.values = values;
484 }
485
486 explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys,
487 mapped_container_type &&values)
488 {
489 c.keys = keys;
490 c.values = std::move(values);
491 }
492
493 explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys,
494 mapped_container_type &&values)
495 {
496 c.keys = std::move(keys);
497 c.values = std::move(values);
498 }
499
500 explicit QFlatMap(Qt::OrderedUniqueRange_t, std::initializer_list<value_type> lst)
501 : QFlatMap(lst.begin(), lst.end())
502 {
503 }
504
505 template <class InputIt, is_compatible_iterator<InputIt> = nullptr>
506 explicit QFlatMap(Qt::OrderedUniqueRange_t, InputIt first, InputIt last)
507 {
508 initWithRange(first, last);
509 }
510
511 explicit QFlatMap(const Compare &compare)
512 : value_compare(compare)
513 {
514 }
515
516 explicit QFlatMap(const key_container_type &keys, const mapped_container_type &values,
517 const Compare &compare)
518 : value_compare(compare), c{keys, values}
519 {
520 ensureOrderedUnique();
521 }
522
523 explicit QFlatMap(key_container_type &&keys, const mapped_container_type &values,
524 const Compare &compare)
525 : value_compare(compare), c{std::move(keys), values}
526 {
527 ensureOrderedUnique();
528 }
529
530 explicit QFlatMap(const key_container_type &keys, mapped_container_type &&values,
531 const Compare &compare)
532 : value_compare(compare), c{keys, std::move(values)}
533 {
534 ensureOrderedUnique();
535 }
536
537 explicit QFlatMap(key_container_type &&keys, mapped_container_type &&values,
538 const Compare &compare)
539 : value_compare(compare), c{std::move(keys), std::move(values)}
540 {
541 ensureOrderedUnique();
542 }
543
544 explicit QFlatMap(std::initializer_list<value_type> lst, const Compare &compare)
545 : QFlatMap(lst.begin(), lst.end(), compare)
546 {
547 }
548
549 template <class InputIt, is_compatible_iterator<InputIt> = nullptr>
550 explicit QFlatMap(InputIt first, InputIt last, const Compare &compare)
551 : value_compare(compare)
552 {
553 initWithRange(first, last);
554 ensureOrderedUnique();
555 }
556
557 explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys,
558 const mapped_container_type &values, const Compare &compare)
559 : value_compare(compare), c{keys, values}
560 {
561 }
562
563 explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys,
564 const mapped_container_type &values, const Compare &compare)
565 : value_compare(compare), c{std::move(keys), values}
566 {
567 }
568
569 explicit QFlatMap(Qt::OrderedUniqueRange_t, const key_container_type &keys,
570 mapped_container_type &&values, const Compare &compare)
571 : value_compare(compare), c{keys, std::move(values)}
572 {
573 }
574
575 explicit QFlatMap(Qt::OrderedUniqueRange_t, key_container_type &&keys,
576 mapped_container_type &&values, const Compare &compare)
577 : value_compare(compare), c{std::move(keys), std::move(values)}
578 {
579 }
580
581 explicit QFlatMap(Qt::OrderedUniqueRange_t, std::initializer_list<value_type> lst,
582 const Compare &compare)
583 : QFlatMap(Qt::OrderedUniqueRange, lst.begin(), lst.end(), compare)
584 {
585 }
586
587 template <class InputIt, is_compatible_iterator<InputIt> = nullptr>
588 explicit QFlatMap(Qt::OrderedUniqueRange_t, InputIt first, InputIt last, const Compare &compare)
589 : value_compare(compare)
590 {
591 initWithRange(first, last);
592 }
593
594 size_type count() const noexcept { return c.keys.size(); }
595 size_type size() const noexcept { return c.keys.size(); }
596 size_type capacity() const noexcept { return c.keys.capacity(); }
597 bool isEmpty() const noexcept { return c.keys.empty(); }
598 bool empty() const noexcept { return c.keys.empty(); }
599 containers extract() && { return std::move(c); }
600 const key_container_type &keys() const noexcept { return c.keys; }
601 const mapped_container_type &values() const noexcept { return c.values; }
602
603 void reserve(size_type s)
604 {
605 c.keys.reserve(s);
606 c.values.reserve(s);
607 }
608
609 void clear()
610 {
611 c.keys.clear();
612 c.values.clear();
613 }
614
615 bool remove(const Key &key)
616 {
617 auto it = binary_find(key);
618 if (it != end()) {
619 c.keys.erase(toKeysIterator(it));
620 c.values.erase(toValuesIterator(it));
621 return true;
622 }
623 return false;
624 }
625
626 iterator erase(iterator it)
627 {
628 c.values.erase(toValuesIterator(it));
629 return fromKeysIterator(c.keys.erase(toKeysIterator(it)));
630 }
631
632 T take(const Key &key)
633 {
634 auto it = binary_find(key);
635 if (it != end()) {
636 T result = std::move(it.value());
637 erase(it);
638 return result;
639 }
640 return {};
641 }
642
643 bool contains(const Key &key) const
644 {
645 return binary_find(key) != end();
646 }
647
648 T value(const Key &key, const T &defaultValue) const
649 {
650 auto it = binary_find(key);
651 return it == end() ? defaultValue : it.value();
652 }
653
654 T value(const Key &key) const
655 {
656 auto it = binary_find(key);
657 return it == end() ? T() : it.value();
658 }
659
660 T &operator[](const Key &key)
661 {
662 auto it = lower_bound(key);
663 if (it == end() || key_compare::operator()(key, it.key())) {
664 c.keys.insert(toKeysIterator(it), key);
665 return *c.values.insert(toValuesIterator(it), T());
666 }
667 return it.value();
668 }
669
670 T &operator[](Key &&key)
671 {
672 auto it = lower_bound(key);
673 if (it == end() || key_compare::operator()(key, it.key())) {
674 c.keys.insert(toKeysIterator(it), key);
675 return *c.values.insert(toValuesIterator(it), T());
676 }
677 return it.value();
678 }
679
680 T operator[](const Key &key) const
681 {
682 return value(key);
683 }
684
685 std::pair<iterator, bool> insert(const Key &key, const T &value)
686 {
687 auto it = lower_bound(key);
688 if (it == end() || key_compare::operator()(key, it.key())) {
689 c.values.insert(toValuesIterator(it), value);
690 auto k = c.keys.insert(toKeysIterator(it), key);
691 return { fromKeysIterator(k), true };
692 } else {
693 it.value() = value;
694 return {it, false};
695 }
696 }
697
698 std::pair<iterator, bool> insert(Key &&key, const T &value)
699 {
700 auto it = lower_bound(key);
701 if (it == end() || key_compare::operator()(key, it.key())) {
702 c.values.insert(toValuesIterator(it), value);
703 return { c.keys.insert(it, std::move(key)), true };
704 } else {
705 *toValuesIterator(it) = value;
706 return {it, false};
707 }
708 }
709
710 std::pair<iterator, bool> insert(const Key &key, T &&value)
711 {
712 auto it = lower_bound(key);
713 if (it == end() || key_compare::operator()(key, it.key())) {
714 c.values.insert(toValuesIterator(it), std::move(value));
715 return { c.keys.insert(it, key), true };
716 } else {
717 *toValuesIterator(it) = std::move(value);
718 return {it, false};
719 }
720 }
721
722 std::pair<iterator, bool> insert(Key &&key, T &&value)
723 {
724 auto it = lower_bound(key);
725 if (it == end() || key_compare::operator()(key, it.key())) {
726 c.values.insert(toValuesIterator(it), std::move(value));
727 return { fromKeysIterator(c.keys.insert(toKeysIterator(it), std::move(key))), true };
728 } else {
729 *toValuesIterator(it) = std::move(value);
730 return {it, false};
731 }
732 }
733
734 template <class InputIt, is_compatible_iterator<InputIt> = nullptr>
735 void insert(InputIt first, InputIt last)
736 {
737 insertRange(first, last);
738 }
739
740 // ### Merge with the templated version above
741 // once we can use std::disjunction in is_compatible_iterator.
742 void insert(const value_type *first, const value_type *last)
743 {
744 insertRange(first, last);
745 }
746
747 template <class InputIt, is_compatible_iterator<InputIt> = nullptr>
748 void insert(Qt::OrderedUniqueRange_t, InputIt first, InputIt last)
749 {
750 insertOrderedUniqueRange(first, last);
751 }
752
753 // ### Merge with the templated version above
754 // once we can use std::disjunction in is_compatible_iterator.
755 void insert(Qt::OrderedUniqueRange_t, const value_type *first, const value_type *last)
756 {
757 insertOrderedUniqueRange(first, last);
758 }
759
760 iterator begin() { return { &c, 0 }; }
761 const_iterator begin() const { return { &c, 0 }; }
762 const_iterator cbegin() const { return begin(); }
763 const_iterator constBegin() const { return cbegin(); }
764 iterator end() { return { &c, c.keys.size() }; }
765 const_iterator end() const { return { &c, c.keys.size() }; }
766 const_iterator cend() const { return end(); }
767 const_iterator constEnd() const { return cend(); }
768 std::reverse_iterator<iterator> rbegin() { return std::reverse_iterator<iterator>(end()); }
769 std::reverse_iterator<const_iterator> rbegin() const
770 {
771 return std::reverse_iterator<const_iterator>(end());
772 }
773 std::reverse_iterator<const_iterator> crbegin() const { return rbegin(); }
774 std::reverse_iterator<iterator> rend() {
775 return std::reverse_iterator<iterator>(begin());
776 }
777 std::reverse_iterator<const_iterator> rend() const
778 {
779 return std::reverse_iterator<const_iterator>(begin());
780 }
781 std::reverse_iterator<const_iterator> crend() const { return rend(); }
782
783 iterator lower_bound(const Key &key)
784 {
785 auto cit = const_cast<const full_map_t *>(this)->lower_bound(key);
786 return { &c, cit.i };
787 }
788
789 template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr>
790 iterator lower_bound(const X &key)
791 {
792 auto cit = const_cast<const full_map_t *>(this)->lower_bound(key);
793 return { &c, cit.i };
794 }
795
796 const_iterator lower_bound(const Key &key) const
797 {
798 return fromKeysIterator(std::lower_bound(c.keys.begin(), c.keys.end(), key, key_comp()));
799 }
800
801 template <class X, class Y = Compare, is_marked_transparent<Y> = nullptr>
802 const_iterator lower_bound(const X &key) const
803 {
804 return fromKeysIterator(std::lower_bound(c.keys.begin(), c.keys.end(), key, key_comp()));
805 }
806
807 iterator find(const key_type &k)
808 {
809 return binary_find(k);
810 }
811
812 const_iterator find(const key_type &k) const
813 {
814 return binary_find(k);
815 }
816
817 key_compare key_comp() const noexcept
818 {
819 return static_cast<key_compare>(*this);
820 }
821
822 value_compare value_comp() const noexcept
823 {
824 return static_cast<value_compare>(*this);
825 }
826
827private:
828 template <class InputIt, is_compatible_iterator<InputIt> = nullptr>
829 void initWithRange(InputIt first, InputIt last)
830 {
831 QtPrivate::reserveIfForwardIterator(this, first, last);
832 while (first != last) {
833 c.keys.push_back(first->first);
834 c.values.push_back(first->second);
835 ++first;
836 }
837 }
838
839 iterator fromKeysIterator(typename key_container_type::iterator kit)
840 {
841 return { &c, static_cast<size_type>(std::distance(c.keys.begin(), kit)) };
842 }
843
844 const_iterator fromKeysIterator(typename key_container_type::const_iterator kit) const
845 {
846 return { &c, static_cast<size_type>(std::distance(c.keys.begin(), kit)) };
847 }
848
849 typename key_container_type::iterator toKeysIterator(iterator it)
850 {
851 return c.keys.begin() + it.i;
852 }
853
854 typename mapped_container_type::iterator toValuesIterator(iterator it)
855 {
856 return c.values.begin() + it.i;
857 }
858
859 template <class InputIt>
860 void insertRange(InputIt first, InputIt last)
861 {
862 size_type i = c.keys.size();
863 c.keys.resize(i + std::distance(first, last));
864 c.values.resize(c.keys.size());
865 for (; first != last; ++first, ++i) {
866 c.keys[i] = first->first;
867 c.values[i] = first->second;
868 }
869 ensureOrderedUnique();
870 }
871
872 class IndexedKeyComparator
873 {
874 public:
875 IndexedKeyComparator(const full_map_t *am)
876 : m(am)
877 {
878 }
879
880 bool operator()(size_type i, size_type k) const
881 {
882 return m->key_comp()(m->c.keys[i], m->c.keys[k]);
883 }
884
885 private:
886 const full_map_t *m;
887 };
888
889 template <class InputIt>
890 void insertOrderedUniqueRange(InputIt first, InputIt last)
891 {
892 const size_type s = c.keys.size();
893 c.keys.resize(s + std::distance(first, last));
894 c.values.resize(c.keys.size());
895 for (size_type i = s; first != last; ++first, ++i) {
896 c.keys[i] = first->first;
897 c.values[i] = first->second;
898 }
899
900 std::vector<size_type> p(size_t(c.keys.size()));
901 std::iota(p.begin(), p.end(), 0);
902 std::inplace_merge(p.begin(), p.begin() + s, p.end(), IndexedKeyComparator(this));
903 applyPermutation(p);
904 makeUnique();
905 }
906
907 iterator binary_find(const Key &key)
908 {
909 return { &c, const_cast<const full_map_t *>(this)->binary_find(key).i };
910 }
911
912 const_iterator binary_find(const Key &key) const
913 {
914 auto it = lower_bound(key);
915 if (it != end()) {
916 if (!key_compare::operator()(key, it.key()))
917 return it;
918 it = end();
919 }
920 return it;
921 }
922
923 void ensureOrderedUnique()
924 {
925 std::vector<size_type> p(size_t(c.keys.size()));
926 std::iota(p.begin(), p.end(), 0);
927 std::stable_sort(p.begin(), p.end(), IndexedKeyComparator(this));
928 applyPermutation(p);
929 makeUnique();
930 }
931
932 void applyPermutation(const std::vector<size_type> &p)
933 {
934 const size_type s = c.keys.size();
935 std::vector<bool> done(s);
936 for (size_type i = 0; i < s; ++i) {
937 if (done[i])
938 continue;
939 done[i] = true;
940 size_type j = i;
941 size_type k = p[i];
942 while (i != k) {
943 qSwap(c.keys[j], c.keys[k]);
944 qSwap(c.values[j], c.values[k]);
945 done[k] = true;
946 j = k;
947 k = p[j];
948 }
949 }
950 }
951
952 void makeUnique()
953 {
954 if (c.keys.size() < 2)
955 return;
956 auto k = std::end(c.keys) - 1;
957 auto i = k - 1;
958 for (;;) {
959 if (key_compare::operator()(*i, *k) || key_compare::operator()(*k, *i)) {
960 if (i == std::begin(c.keys))
961 break;
962 --i;
963 --k;
964 } else {
965 c.values.erase(std::begin(c.values) + std::distance(std::begin(c.keys), i));
966 i = c.keys.erase(i);
967 if (i == std::begin(c.keys))
968 break;
969 k = i + 1;
970 }
971 }
972 c.keys.shrink_to_fit();
973 c.values.shrink_to_fit();
974 }
975
976 containers c;
977};
978
979QT_END_NAMESPACE
980
981#endif // QFLATMAP_P_H
982