1*635a8641SAndroid Build Coastguard Worker // Copyright 2017 The Chromium Authors. All rights reserved.
2*635a8641SAndroid Build Coastguard Worker // Use of this source code is governed by a BSD-style license that can be
3*635a8641SAndroid Build Coastguard Worker // found in the LICENSE file.
4*635a8641SAndroid Build Coastguard Worker
5*635a8641SAndroid Build Coastguard Worker #ifndef BASE_CONTAINERS_FLAT_TREE_H_
6*635a8641SAndroid Build Coastguard Worker #define BASE_CONTAINERS_FLAT_TREE_H_
7*635a8641SAndroid Build Coastguard Worker
8*635a8641SAndroid Build Coastguard Worker #include <algorithm>
9*635a8641SAndroid Build Coastguard Worker #include <iterator>
10*635a8641SAndroid Build Coastguard Worker #include <type_traits>
11*635a8641SAndroid Build Coastguard Worker #include <vector>
12*635a8641SAndroid Build Coastguard Worker
13*635a8641SAndroid Build Coastguard Worker #include "base/template_util.h"
14*635a8641SAndroid Build Coastguard Worker
15*635a8641SAndroid Build Coastguard Worker namespace base {
16*635a8641SAndroid Build Coastguard Worker
17*635a8641SAndroid Build Coastguard Worker enum FlatContainerDupes {
18*635a8641SAndroid Build Coastguard Worker KEEP_FIRST_OF_DUPES,
19*635a8641SAndroid Build Coastguard Worker KEEP_LAST_OF_DUPES,
20*635a8641SAndroid Build Coastguard Worker };
21*635a8641SAndroid Build Coastguard Worker
22*635a8641SAndroid Build Coastguard Worker namespace internal {
23*635a8641SAndroid Build Coastguard Worker
24*635a8641SAndroid Build Coastguard Worker // This is a convenience method returning true if Iterator is at least a
25*635a8641SAndroid Build Coastguard Worker // ForwardIterator and thus supports multiple passes over a range.
26*635a8641SAndroid Build Coastguard Worker template <class Iterator>
is_multipass()27*635a8641SAndroid Build Coastguard Worker constexpr bool is_multipass() {
28*635a8641SAndroid Build Coastguard Worker return std::is_base_of<
29*635a8641SAndroid Build Coastguard Worker std::forward_iterator_tag,
30*635a8641SAndroid Build Coastguard Worker typename std::iterator_traits<Iterator>::iterator_category>::value;
31*635a8641SAndroid Build Coastguard Worker }
32*635a8641SAndroid Build Coastguard Worker
33*635a8641SAndroid Build Coastguard Worker // This algorithm is like unique() from the standard library except it
34*635a8641SAndroid Build Coastguard Worker // selects only the last of consecutive values instead of the first.
35*635a8641SAndroid Build Coastguard Worker template <class Iterator, class BinaryPredicate>
LastUnique(Iterator first,Iterator last,BinaryPredicate compare)36*635a8641SAndroid Build Coastguard Worker Iterator LastUnique(Iterator first, Iterator last, BinaryPredicate compare) {
37*635a8641SAndroid Build Coastguard Worker Iterator replacable = std::adjacent_find(first, last, compare);
38*635a8641SAndroid Build Coastguard Worker
39*635a8641SAndroid Build Coastguard Worker // No duplicate elements found.
40*635a8641SAndroid Build Coastguard Worker if (replacable == last)
41*635a8641SAndroid Build Coastguard Worker return last;
42*635a8641SAndroid Build Coastguard Worker
43*635a8641SAndroid Build Coastguard Worker first = std::next(replacable);
44*635a8641SAndroid Build Coastguard Worker
45*635a8641SAndroid Build Coastguard Worker // Last element is a duplicate but all others are unique.
46*635a8641SAndroid Build Coastguard Worker if (first == last)
47*635a8641SAndroid Build Coastguard Worker return replacable;
48*635a8641SAndroid Build Coastguard Worker
49*635a8641SAndroid Build Coastguard Worker // This loop is based on std::adjacent_find but std::adjacent_find doesn't
50*635a8641SAndroid Build Coastguard Worker // quite cut it.
51*635a8641SAndroid Build Coastguard Worker for (Iterator next = std::next(first); next != last; ++next, ++first) {
52*635a8641SAndroid Build Coastguard Worker if (!compare(*first, *next))
53*635a8641SAndroid Build Coastguard Worker *replacable++ = std::move(*first);
54*635a8641SAndroid Build Coastguard Worker }
55*635a8641SAndroid Build Coastguard Worker
56*635a8641SAndroid Build Coastguard Worker // Last element should be copied unconditionally.
57*635a8641SAndroid Build Coastguard Worker *replacable++ = std::move(*first);
58*635a8641SAndroid Build Coastguard Worker return replacable;
59*635a8641SAndroid Build Coastguard Worker }
60*635a8641SAndroid Build Coastguard Worker
61*635a8641SAndroid Build Coastguard Worker // Uses SFINAE to detect whether type has is_transparent member.
62*635a8641SAndroid Build Coastguard Worker template <typename T, typename = void>
63*635a8641SAndroid Build Coastguard Worker struct IsTransparentCompare : std::false_type {};
64*635a8641SAndroid Build Coastguard Worker template <typename T>
65*635a8641SAndroid Build Coastguard Worker struct IsTransparentCompare<T, void_t<typename T::is_transparent>>
66*635a8641SAndroid Build Coastguard Worker : std::true_type {};
67*635a8641SAndroid Build Coastguard Worker
68*635a8641SAndroid Build Coastguard Worker // Implementation -------------------------------------------------------------
69*635a8641SAndroid Build Coastguard Worker
70*635a8641SAndroid Build Coastguard Worker // Implementation of a sorted vector for backing flat_set and flat_map. Do not
71*635a8641SAndroid Build Coastguard Worker // use directly.
72*635a8641SAndroid Build Coastguard Worker //
73*635a8641SAndroid Build Coastguard Worker // The use of "value" in this is like std::map uses, meaning it's the thing
74*635a8641SAndroid Build Coastguard Worker // contained (in the case of map it's a <Kay, Mapped> pair). The Key is how
75*635a8641SAndroid Build Coastguard Worker // things are looked up. In the case of a set, Key == Value. In the case of
76*635a8641SAndroid Build Coastguard Worker // a map, the Key is a component of a Value.
77*635a8641SAndroid Build Coastguard Worker //
78*635a8641SAndroid Build Coastguard Worker // The helper class GetKeyFromValue provides the means to extract a key from a
79*635a8641SAndroid Build Coastguard Worker // value for comparison purposes. It should implement:
80*635a8641SAndroid Build Coastguard Worker // const Key& operator()(const Value&).
81*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
82*635a8641SAndroid Build Coastguard Worker class flat_tree {
83*635a8641SAndroid Build Coastguard Worker private:
84*635a8641SAndroid Build Coastguard Worker using underlying_type = std::vector<Value>;
85*635a8641SAndroid Build Coastguard Worker
86*635a8641SAndroid Build Coastguard Worker public:
87*635a8641SAndroid Build Coastguard Worker // --------------------------------------------------------------------------
88*635a8641SAndroid Build Coastguard Worker // Types.
89*635a8641SAndroid Build Coastguard Worker //
90*635a8641SAndroid Build Coastguard Worker using key_type = Key;
91*635a8641SAndroid Build Coastguard Worker using key_compare = KeyCompare;
92*635a8641SAndroid Build Coastguard Worker using value_type = Value;
93*635a8641SAndroid Build Coastguard Worker
94*635a8641SAndroid Build Coastguard Worker // Wraps the templated key comparison to compare values.
95*635a8641SAndroid Build Coastguard Worker class value_compare : public key_compare {
96*635a8641SAndroid Build Coastguard Worker public:
97*635a8641SAndroid Build Coastguard Worker value_compare() = default;
98*635a8641SAndroid Build Coastguard Worker
99*635a8641SAndroid Build Coastguard Worker template <class Cmp>
100*635a8641SAndroid Build Coastguard Worker explicit value_compare(Cmp&& compare_arg)
101*635a8641SAndroid Build Coastguard Worker : KeyCompare(std::forward<Cmp>(compare_arg)) {}
102*635a8641SAndroid Build Coastguard Worker
103*635a8641SAndroid Build Coastguard Worker bool operator()(const value_type& left, const value_type& right) const {
104*635a8641SAndroid Build Coastguard Worker GetKeyFromValue extractor;
105*635a8641SAndroid Build Coastguard Worker return key_compare::operator()(extractor(left), extractor(right));
106*635a8641SAndroid Build Coastguard Worker }
107*635a8641SAndroid Build Coastguard Worker };
108*635a8641SAndroid Build Coastguard Worker
109*635a8641SAndroid Build Coastguard Worker using pointer = typename underlying_type::pointer;
110*635a8641SAndroid Build Coastguard Worker using const_pointer = typename underlying_type::const_pointer;
111*635a8641SAndroid Build Coastguard Worker using reference = typename underlying_type::reference;
112*635a8641SAndroid Build Coastguard Worker using const_reference = typename underlying_type::const_reference;
113*635a8641SAndroid Build Coastguard Worker using size_type = typename underlying_type::size_type;
114*635a8641SAndroid Build Coastguard Worker using difference_type = typename underlying_type::difference_type;
115*635a8641SAndroid Build Coastguard Worker using iterator = typename underlying_type::iterator;
116*635a8641SAndroid Build Coastguard Worker using const_iterator = typename underlying_type::const_iterator;
117*635a8641SAndroid Build Coastguard Worker using reverse_iterator = typename underlying_type::reverse_iterator;
118*635a8641SAndroid Build Coastguard Worker using const_reverse_iterator =
119*635a8641SAndroid Build Coastguard Worker typename underlying_type::const_reverse_iterator;
120*635a8641SAndroid Build Coastguard Worker
121*635a8641SAndroid Build Coastguard Worker // --------------------------------------------------------------------------
122*635a8641SAndroid Build Coastguard Worker // Lifetime.
123*635a8641SAndroid Build Coastguard Worker //
124*635a8641SAndroid Build Coastguard Worker // Constructors that take range guarantee O(N * log^2(N)) + O(N) complexity
125*635a8641SAndroid Build Coastguard Worker // and take O(N * log(N)) + O(N) if extra memory is available (N is a range
126*635a8641SAndroid Build Coastguard Worker // length).
127*635a8641SAndroid Build Coastguard Worker //
128*635a8641SAndroid Build Coastguard Worker // Assume that move constructors invalidate iterators and references.
129*635a8641SAndroid Build Coastguard Worker //
130*635a8641SAndroid Build Coastguard Worker // The constructors that take ranges, lists, and vectors do not require that
131*635a8641SAndroid Build Coastguard Worker // the input be sorted.
132*635a8641SAndroid Build Coastguard Worker
133*635a8641SAndroid Build Coastguard Worker flat_tree();
134*635a8641SAndroid Build Coastguard Worker explicit flat_tree(const key_compare& comp);
135*635a8641SAndroid Build Coastguard Worker
136*635a8641SAndroid Build Coastguard Worker template <class InputIterator>
137*635a8641SAndroid Build Coastguard Worker flat_tree(InputIterator first,
138*635a8641SAndroid Build Coastguard Worker InputIterator last,
139*635a8641SAndroid Build Coastguard Worker FlatContainerDupes dupe_handling = KEEP_FIRST_OF_DUPES,
140*635a8641SAndroid Build Coastguard Worker const key_compare& comp = key_compare());
141*635a8641SAndroid Build Coastguard Worker
142*635a8641SAndroid Build Coastguard Worker flat_tree(const flat_tree&);
143*635a8641SAndroid Build Coastguard Worker flat_tree(flat_tree&&) noexcept = default;
144*635a8641SAndroid Build Coastguard Worker
145*635a8641SAndroid Build Coastguard Worker flat_tree(std::vector<value_type> items,
146*635a8641SAndroid Build Coastguard Worker FlatContainerDupes dupe_handling = KEEP_FIRST_OF_DUPES,
147*635a8641SAndroid Build Coastguard Worker const key_compare& comp = key_compare());
148*635a8641SAndroid Build Coastguard Worker
149*635a8641SAndroid Build Coastguard Worker flat_tree(std::initializer_list<value_type> ilist,
150*635a8641SAndroid Build Coastguard Worker FlatContainerDupes dupe_handling = KEEP_FIRST_OF_DUPES,
151*635a8641SAndroid Build Coastguard Worker const key_compare& comp = key_compare());
152*635a8641SAndroid Build Coastguard Worker
153*635a8641SAndroid Build Coastguard Worker ~flat_tree();
154*635a8641SAndroid Build Coastguard Worker
155*635a8641SAndroid Build Coastguard Worker // --------------------------------------------------------------------------
156*635a8641SAndroid Build Coastguard Worker // Assignments.
157*635a8641SAndroid Build Coastguard Worker //
158*635a8641SAndroid Build Coastguard Worker // Assume that move assignment invalidates iterators and references.
159*635a8641SAndroid Build Coastguard Worker
160*635a8641SAndroid Build Coastguard Worker flat_tree& operator=(const flat_tree&);
161*635a8641SAndroid Build Coastguard Worker flat_tree& operator=(flat_tree&&);
162*635a8641SAndroid Build Coastguard Worker // Takes the first if there are duplicates in the initializer list.
163*635a8641SAndroid Build Coastguard Worker flat_tree& operator=(std::initializer_list<value_type> ilist);
164*635a8641SAndroid Build Coastguard Worker
165*635a8641SAndroid Build Coastguard Worker // --------------------------------------------------------------------------
166*635a8641SAndroid Build Coastguard Worker // Memory management.
167*635a8641SAndroid Build Coastguard Worker //
168*635a8641SAndroid Build Coastguard Worker // Beware that shrink_to_fit() simply forwards the request to the
169*635a8641SAndroid Build Coastguard Worker // underlying_type and its implementation is free to optimize otherwise and
170*635a8641SAndroid Build Coastguard Worker // leave capacity() to be greater that its size.
171*635a8641SAndroid Build Coastguard Worker //
172*635a8641SAndroid Build Coastguard Worker // reserve() and shrink_to_fit() invalidate iterators and references.
173*635a8641SAndroid Build Coastguard Worker
174*635a8641SAndroid Build Coastguard Worker void reserve(size_type new_capacity);
175*635a8641SAndroid Build Coastguard Worker size_type capacity() const;
176*635a8641SAndroid Build Coastguard Worker void shrink_to_fit();
177*635a8641SAndroid Build Coastguard Worker
178*635a8641SAndroid Build Coastguard Worker // --------------------------------------------------------------------------
179*635a8641SAndroid Build Coastguard Worker // Size management.
180*635a8641SAndroid Build Coastguard Worker //
181*635a8641SAndroid Build Coastguard Worker // clear() leaves the capacity() of the flat_tree unchanged.
182*635a8641SAndroid Build Coastguard Worker
183*635a8641SAndroid Build Coastguard Worker void clear();
184*635a8641SAndroid Build Coastguard Worker
185*635a8641SAndroid Build Coastguard Worker size_type size() const;
186*635a8641SAndroid Build Coastguard Worker size_type max_size() const;
187*635a8641SAndroid Build Coastguard Worker bool empty() const;
188*635a8641SAndroid Build Coastguard Worker
189*635a8641SAndroid Build Coastguard Worker // --------------------------------------------------------------------------
190*635a8641SAndroid Build Coastguard Worker // Iterators.
191*635a8641SAndroid Build Coastguard Worker
192*635a8641SAndroid Build Coastguard Worker iterator begin();
193*635a8641SAndroid Build Coastguard Worker const_iterator begin() const;
194*635a8641SAndroid Build Coastguard Worker const_iterator cbegin() const;
195*635a8641SAndroid Build Coastguard Worker
196*635a8641SAndroid Build Coastguard Worker iterator end();
197*635a8641SAndroid Build Coastguard Worker const_iterator end() const;
198*635a8641SAndroid Build Coastguard Worker const_iterator cend() const;
199*635a8641SAndroid Build Coastguard Worker
200*635a8641SAndroid Build Coastguard Worker reverse_iterator rbegin();
201*635a8641SAndroid Build Coastguard Worker const_reverse_iterator rbegin() const;
202*635a8641SAndroid Build Coastguard Worker const_reverse_iterator crbegin() const;
203*635a8641SAndroid Build Coastguard Worker
204*635a8641SAndroid Build Coastguard Worker reverse_iterator rend();
205*635a8641SAndroid Build Coastguard Worker const_reverse_iterator rend() const;
206*635a8641SAndroid Build Coastguard Worker const_reverse_iterator crend() const;
207*635a8641SAndroid Build Coastguard Worker
208*635a8641SAndroid Build Coastguard Worker // --------------------------------------------------------------------------
209*635a8641SAndroid Build Coastguard Worker // Insert operations.
210*635a8641SAndroid Build Coastguard Worker //
211*635a8641SAndroid Build Coastguard Worker // Assume that every operation invalidates iterators and references.
212*635a8641SAndroid Build Coastguard Worker // Insertion of one element can take O(size). Capacity of flat_tree grows in
213*635a8641SAndroid Build Coastguard Worker // an implementation-defined manner.
214*635a8641SAndroid Build Coastguard Worker //
215*635a8641SAndroid Build Coastguard Worker // NOTE: Prefer to build a new flat_tree from a std::vector (or similar)
216*635a8641SAndroid Build Coastguard Worker // instead of calling insert() repeatedly.
217*635a8641SAndroid Build Coastguard Worker
218*635a8641SAndroid Build Coastguard Worker std::pair<iterator, bool> insert(const value_type& val);
219*635a8641SAndroid Build Coastguard Worker std::pair<iterator, bool> insert(value_type&& val);
220*635a8641SAndroid Build Coastguard Worker
221*635a8641SAndroid Build Coastguard Worker iterator insert(const_iterator position_hint, const value_type& x);
222*635a8641SAndroid Build Coastguard Worker iterator insert(const_iterator position_hint, value_type&& x);
223*635a8641SAndroid Build Coastguard Worker
224*635a8641SAndroid Build Coastguard Worker // This method inserts the values from the range [first, last) into the
225*635a8641SAndroid Build Coastguard Worker // current tree. In case of KEEP_LAST_OF_DUPES newly added elements can
226*635a8641SAndroid Build Coastguard Worker // overwrite existing values.
227*635a8641SAndroid Build Coastguard Worker template <class InputIterator>
228*635a8641SAndroid Build Coastguard Worker void insert(InputIterator first,
229*635a8641SAndroid Build Coastguard Worker InputIterator last,
230*635a8641SAndroid Build Coastguard Worker FlatContainerDupes dupes = KEEP_FIRST_OF_DUPES);
231*635a8641SAndroid Build Coastguard Worker
232*635a8641SAndroid Build Coastguard Worker template <class... Args>
233*635a8641SAndroid Build Coastguard Worker std::pair<iterator, bool> emplace(Args&&... args);
234*635a8641SAndroid Build Coastguard Worker
235*635a8641SAndroid Build Coastguard Worker template <class... Args>
236*635a8641SAndroid Build Coastguard Worker iterator emplace_hint(const_iterator position_hint, Args&&... args);
237*635a8641SAndroid Build Coastguard Worker
238*635a8641SAndroid Build Coastguard Worker // --------------------------------------------------------------------------
239*635a8641SAndroid Build Coastguard Worker // Erase operations.
240*635a8641SAndroid Build Coastguard Worker //
241*635a8641SAndroid Build Coastguard Worker // Assume that every operation invalidates iterators and references.
242*635a8641SAndroid Build Coastguard Worker //
243*635a8641SAndroid Build Coastguard Worker // erase(position), erase(first, last) can take O(size).
244*635a8641SAndroid Build Coastguard Worker // erase(key) may take O(size) + O(log(size)).
245*635a8641SAndroid Build Coastguard Worker //
246*635a8641SAndroid Build Coastguard Worker // Prefer base::EraseIf() or some other variation on erase(remove(), end())
247*635a8641SAndroid Build Coastguard Worker // idiom when deleting multiple non-consecutive elements.
248*635a8641SAndroid Build Coastguard Worker
249*635a8641SAndroid Build Coastguard Worker iterator erase(iterator position);
250*635a8641SAndroid Build Coastguard Worker iterator erase(const_iterator position);
251*635a8641SAndroid Build Coastguard Worker iterator erase(const_iterator first, const_iterator last);
252*635a8641SAndroid Build Coastguard Worker template <typename K>
253*635a8641SAndroid Build Coastguard Worker size_type erase(const K& key);
254*635a8641SAndroid Build Coastguard Worker
255*635a8641SAndroid Build Coastguard Worker // --------------------------------------------------------------------------
256*635a8641SAndroid Build Coastguard Worker // Comparators.
257*635a8641SAndroid Build Coastguard Worker
258*635a8641SAndroid Build Coastguard Worker key_compare key_comp() const;
259*635a8641SAndroid Build Coastguard Worker value_compare value_comp() const;
260*635a8641SAndroid Build Coastguard Worker
261*635a8641SAndroid Build Coastguard Worker // --------------------------------------------------------------------------
262*635a8641SAndroid Build Coastguard Worker // Search operations.
263*635a8641SAndroid Build Coastguard Worker //
264*635a8641SAndroid Build Coastguard Worker // Search operations have O(log(size)) complexity.
265*635a8641SAndroid Build Coastguard Worker
266*635a8641SAndroid Build Coastguard Worker template <typename K>
267*635a8641SAndroid Build Coastguard Worker size_type count(const K& key) const;
268*635a8641SAndroid Build Coastguard Worker
269*635a8641SAndroid Build Coastguard Worker template <typename K>
270*635a8641SAndroid Build Coastguard Worker iterator find(const K& key);
271*635a8641SAndroid Build Coastguard Worker
272*635a8641SAndroid Build Coastguard Worker template <typename K>
273*635a8641SAndroid Build Coastguard Worker const_iterator find(const K& key) const;
274*635a8641SAndroid Build Coastguard Worker
275*635a8641SAndroid Build Coastguard Worker template <typename K>
276*635a8641SAndroid Build Coastguard Worker std::pair<iterator, iterator> equal_range(const K& key);
277*635a8641SAndroid Build Coastguard Worker
278*635a8641SAndroid Build Coastguard Worker template <typename K>
279*635a8641SAndroid Build Coastguard Worker std::pair<const_iterator, const_iterator> equal_range(const K& key) const;
280*635a8641SAndroid Build Coastguard Worker
281*635a8641SAndroid Build Coastguard Worker template <typename K>
282*635a8641SAndroid Build Coastguard Worker iterator lower_bound(const K& key);
283*635a8641SAndroid Build Coastguard Worker
284*635a8641SAndroid Build Coastguard Worker template <typename K>
285*635a8641SAndroid Build Coastguard Worker const_iterator lower_bound(const K& key) const;
286*635a8641SAndroid Build Coastguard Worker
287*635a8641SAndroid Build Coastguard Worker template <typename K>
288*635a8641SAndroid Build Coastguard Worker iterator upper_bound(const K& key);
289*635a8641SAndroid Build Coastguard Worker
290*635a8641SAndroid Build Coastguard Worker template <typename K>
291*635a8641SAndroid Build Coastguard Worker const_iterator upper_bound(const K& key) const;
292*635a8641SAndroid Build Coastguard Worker
293*635a8641SAndroid Build Coastguard Worker // --------------------------------------------------------------------------
294*635a8641SAndroid Build Coastguard Worker // General operations.
295*635a8641SAndroid Build Coastguard Worker //
296*635a8641SAndroid Build Coastguard Worker // Assume that swap invalidates iterators and references.
297*635a8641SAndroid Build Coastguard Worker //
298*635a8641SAndroid Build Coastguard Worker // Implementation note: currently we use operator==() and operator<() on
299*635a8641SAndroid Build Coastguard Worker // std::vector, because they have the same contract we need, so we use them
300*635a8641SAndroid Build Coastguard Worker // directly for brevity and in case it is more optimal than calling equal()
301*635a8641SAndroid Build Coastguard Worker // and lexicograhpical_compare(). If the underlying container type is changed,
302*635a8641SAndroid Build Coastguard Worker // this code may need to be modified.
303*635a8641SAndroid Build Coastguard Worker
304*635a8641SAndroid Build Coastguard Worker void swap(flat_tree& other) noexcept;
305*635a8641SAndroid Build Coastguard Worker
306*635a8641SAndroid Build Coastguard Worker friend bool operator==(const flat_tree& lhs, const flat_tree& rhs) {
307*635a8641SAndroid Build Coastguard Worker return lhs.impl_.body_ == rhs.impl_.body_;
308*635a8641SAndroid Build Coastguard Worker }
309*635a8641SAndroid Build Coastguard Worker
310*635a8641SAndroid Build Coastguard Worker friend bool operator!=(const flat_tree& lhs, const flat_tree& rhs) {
311*635a8641SAndroid Build Coastguard Worker return !(lhs == rhs);
312*635a8641SAndroid Build Coastguard Worker }
313*635a8641SAndroid Build Coastguard Worker
314*635a8641SAndroid Build Coastguard Worker friend bool operator<(const flat_tree& lhs, const flat_tree& rhs) {
315*635a8641SAndroid Build Coastguard Worker return lhs.impl_.body_ < rhs.impl_.body_;
316*635a8641SAndroid Build Coastguard Worker }
317*635a8641SAndroid Build Coastguard Worker
318*635a8641SAndroid Build Coastguard Worker friend bool operator>(const flat_tree& lhs, const flat_tree& rhs) {
319*635a8641SAndroid Build Coastguard Worker return rhs < lhs;
320*635a8641SAndroid Build Coastguard Worker }
321*635a8641SAndroid Build Coastguard Worker
322*635a8641SAndroid Build Coastguard Worker friend bool operator>=(const flat_tree& lhs, const flat_tree& rhs) {
323*635a8641SAndroid Build Coastguard Worker return !(lhs < rhs);
324*635a8641SAndroid Build Coastguard Worker }
325*635a8641SAndroid Build Coastguard Worker
326*635a8641SAndroid Build Coastguard Worker friend bool operator<=(const flat_tree& lhs, const flat_tree& rhs) {
327*635a8641SAndroid Build Coastguard Worker return !(lhs > rhs);
328*635a8641SAndroid Build Coastguard Worker }
329*635a8641SAndroid Build Coastguard Worker
330*635a8641SAndroid Build Coastguard Worker friend void swap(flat_tree& lhs, flat_tree& rhs) noexcept { lhs.swap(rhs); }
331*635a8641SAndroid Build Coastguard Worker
332*635a8641SAndroid Build Coastguard Worker protected:
333*635a8641SAndroid Build Coastguard Worker // Emplaces a new item into the tree that is known not to be in it. This
334*635a8641SAndroid Build Coastguard Worker // is for implementing map operator[].
335*635a8641SAndroid Build Coastguard Worker template <class... Args>
336*635a8641SAndroid Build Coastguard Worker iterator unsafe_emplace(const_iterator position, Args&&... args);
337*635a8641SAndroid Build Coastguard Worker
338*635a8641SAndroid Build Coastguard Worker // Attempts to emplace a new element with key |key|. Only if |key| is not yet
339*635a8641SAndroid Build Coastguard Worker // present, construct value_type from |args| and insert it. Returns an
340*635a8641SAndroid Build Coastguard Worker // iterator to the element with key |key| and a bool indicating whether an
341*635a8641SAndroid Build Coastguard Worker // insertion happened.
342*635a8641SAndroid Build Coastguard Worker template <class K, class... Args>
343*635a8641SAndroid Build Coastguard Worker std::pair<iterator, bool> emplace_key_args(const K& key, Args&&... args);
344*635a8641SAndroid Build Coastguard Worker
345*635a8641SAndroid Build Coastguard Worker // Similar to |emplace_key_args|, but checks |hint| first as a possible
346*635a8641SAndroid Build Coastguard Worker // insertion position.
347*635a8641SAndroid Build Coastguard Worker template <class K, class... Args>
348*635a8641SAndroid Build Coastguard Worker std::pair<iterator, bool> emplace_hint_key_args(const_iterator hint,
349*635a8641SAndroid Build Coastguard Worker const K& key,
350*635a8641SAndroid Build Coastguard Worker Args&&... args);
351*635a8641SAndroid Build Coastguard Worker
352*635a8641SAndroid Build Coastguard Worker private:
353*635a8641SAndroid Build Coastguard Worker // Helper class for e.g. lower_bound that can compare a value on the left
354*635a8641SAndroid Build Coastguard Worker // to a key on the right.
355*635a8641SAndroid Build Coastguard Worker struct KeyValueCompare {
356*635a8641SAndroid Build Coastguard Worker // The key comparison object must outlive this class.
357*635a8641SAndroid Build Coastguard Worker explicit KeyValueCompare(const key_compare& key_comp)
358*635a8641SAndroid Build Coastguard Worker : key_comp_(key_comp) {}
359*635a8641SAndroid Build Coastguard Worker
360*635a8641SAndroid Build Coastguard Worker template <typename T, typename U>
361*635a8641SAndroid Build Coastguard Worker bool operator()(const T& lhs, const U& rhs) const {
362*635a8641SAndroid Build Coastguard Worker return key_comp_(extract_if_value_type(lhs), extract_if_value_type(rhs));
363*635a8641SAndroid Build Coastguard Worker }
364*635a8641SAndroid Build Coastguard Worker
365*635a8641SAndroid Build Coastguard Worker private:
366*635a8641SAndroid Build Coastguard Worker const key_type& extract_if_value_type(const value_type& v) const {
367*635a8641SAndroid Build Coastguard Worker GetKeyFromValue extractor;
368*635a8641SAndroid Build Coastguard Worker return extractor(v);
369*635a8641SAndroid Build Coastguard Worker }
370*635a8641SAndroid Build Coastguard Worker
371*635a8641SAndroid Build Coastguard Worker template <typename K>
372*635a8641SAndroid Build Coastguard Worker const K& extract_if_value_type(const K& k) const {
373*635a8641SAndroid Build Coastguard Worker return k;
374*635a8641SAndroid Build Coastguard Worker }
375*635a8641SAndroid Build Coastguard Worker
376*635a8641SAndroid Build Coastguard Worker const key_compare& key_comp_;
377*635a8641SAndroid Build Coastguard Worker };
378*635a8641SAndroid Build Coastguard Worker
379*635a8641SAndroid Build Coastguard Worker const flat_tree& as_const() { return *this; }
380*635a8641SAndroid Build Coastguard Worker
381*635a8641SAndroid Build Coastguard Worker iterator const_cast_it(const_iterator c_it) {
382*635a8641SAndroid Build Coastguard Worker auto distance = std::distance(cbegin(), c_it);
383*635a8641SAndroid Build Coastguard Worker return std::next(begin(), distance);
384*635a8641SAndroid Build Coastguard Worker }
385*635a8641SAndroid Build Coastguard Worker
386*635a8641SAndroid Build Coastguard Worker // This method is inspired by both std::map::insert(P&&) and
387*635a8641SAndroid Build Coastguard Worker // std::map::insert_or_assign(const K&, V&&). It inserts val if an equivalent
388*635a8641SAndroid Build Coastguard Worker // element is not present yet, otherwise it overwrites. It returns an iterator
389*635a8641SAndroid Build Coastguard Worker // to the modified element and a flag indicating whether insertion or
390*635a8641SAndroid Build Coastguard Worker // assignment happened.
391*635a8641SAndroid Build Coastguard Worker template <class V>
392*635a8641SAndroid Build Coastguard Worker std::pair<iterator, bool> insert_or_assign(V&& val) {
393*635a8641SAndroid Build Coastguard Worker auto position = lower_bound(GetKeyFromValue()(val));
394*635a8641SAndroid Build Coastguard Worker
395*635a8641SAndroid Build Coastguard Worker if (position == end() || value_comp()(val, *position))
396*635a8641SAndroid Build Coastguard Worker return {impl_.body_.emplace(position, std::forward<V>(val)), true};
397*635a8641SAndroid Build Coastguard Worker
398*635a8641SAndroid Build Coastguard Worker *position = std::forward<V>(val);
399*635a8641SAndroid Build Coastguard Worker return {position, false};
400*635a8641SAndroid Build Coastguard Worker }
401*635a8641SAndroid Build Coastguard Worker
402*635a8641SAndroid Build Coastguard Worker // This method is similar to insert_or_assign, with the following differences:
403*635a8641SAndroid Build Coastguard Worker // - Instead of searching [begin(), end()) it only searches [first, last).
404*635a8641SAndroid Build Coastguard Worker // - In case no equivalent element is found, val is appended to the end of the
405*635a8641SAndroid Build Coastguard Worker // underlying body and an iterator to the next bigger element in [first,
406*635a8641SAndroid Build Coastguard Worker // last) is returned.
407*635a8641SAndroid Build Coastguard Worker template <class V>
408*635a8641SAndroid Build Coastguard Worker std::pair<iterator, bool> append_or_assign(iterator first,
409*635a8641SAndroid Build Coastguard Worker iterator last,
410*635a8641SAndroid Build Coastguard Worker V&& val) {
411*635a8641SAndroid Build Coastguard Worker auto position = std::lower_bound(first, last, val, value_comp());
412*635a8641SAndroid Build Coastguard Worker
413*635a8641SAndroid Build Coastguard Worker if (position == last || value_comp()(val, *position)) {
414*635a8641SAndroid Build Coastguard Worker // emplace_back might invalidate position, which is why distance needs to
415*635a8641SAndroid Build Coastguard Worker // be cached.
416*635a8641SAndroid Build Coastguard Worker const difference_type distance = std::distance(begin(), position);
417*635a8641SAndroid Build Coastguard Worker impl_.body_.emplace_back(std::forward<V>(val));
418*635a8641SAndroid Build Coastguard Worker return {std::next(begin(), distance), true};
419*635a8641SAndroid Build Coastguard Worker }
420*635a8641SAndroid Build Coastguard Worker
421*635a8641SAndroid Build Coastguard Worker *position = std::forward<V>(val);
422*635a8641SAndroid Build Coastguard Worker return {position, false};
423*635a8641SAndroid Build Coastguard Worker }
424*635a8641SAndroid Build Coastguard Worker
425*635a8641SAndroid Build Coastguard Worker // This method is similar to insert, with the following differences:
426*635a8641SAndroid Build Coastguard Worker // - Instead of searching [begin(), end()) it only searches [first, last).
427*635a8641SAndroid Build Coastguard Worker // - In case no equivalent element is found, val is appended to the end of the
428*635a8641SAndroid Build Coastguard Worker // underlying body and an iterator to the next bigger element in [first,
429*635a8641SAndroid Build Coastguard Worker // last) is returned.
430*635a8641SAndroid Build Coastguard Worker template <class V>
431*635a8641SAndroid Build Coastguard Worker std::pair<iterator, bool> append_unique(iterator first,
432*635a8641SAndroid Build Coastguard Worker iterator last,
433*635a8641SAndroid Build Coastguard Worker V&& val) {
434*635a8641SAndroid Build Coastguard Worker auto position = std::lower_bound(first, last, val, value_comp());
435*635a8641SAndroid Build Coastguard Worker
436*635a8641SAndroid Build Coastguard Worker if (position == last || value_comp()(val, *position)) {
437*635a8641SAndroid Build Coastguard Worker // emplace_back might invalidate position, which is why distance needs to
438*635a8641SAndroid Build Coastguard Worker // be cached.
439*635a8641SAndroid Build Coastguard Worker const difference_type distance = std::distance(begin(), position);
440*635a8641SAndroid Build Coastguard Worker impl_.body_.emplace_back(std::forward<V>(val));
441*635a8641SAndroid Build Coastguard Worker return {std::next(begin(), distance), true};
442*635a8641SAndroid Build Coastguard Worker }
443*635a8641SAndroid Build Coastguard Worker
444*635a8641SAndroid Build Coastguard Worker return {position, false};
445*635a8641SAndroid Build Coastguard Worker }
446*635a8641SAndroid Build Coastguard Worker
447*635a8641SAndroid Build Coastguard Worker void sort_and_unique(iterator first,
448*635a8641SAndroid Build Coastguard Worker iterator last,
449*635a8641SAndroid Build Coastguard Worker FlatContainerDupes dupes) {
450*635a8641SAndroid Build Coastguard Worker // Preserve stability for the unique code below.
451*635a8641SAndroid Build Coastguard Worker std::stable_sort(first, last, impl_.get_value_comp());
452*635a8641SAndroid Build Coastguard Worker
453*635a8641SAndroid Build Coastguard Worker auto comparator = [this](const value_type& lhs, const value_type& rhs) {
454*635a8641SAndroid Build Coastguard Worker // lhs is already <= rhs due to sort, therefore
455*635a8641SAndroid Build Coastguard Worker // !(lhs < rhs) <=> lhs == rhs.
456*635a8641SAndroid Build Coastguard Worker return !impl_.get_value_comp()(lhs, rhs);
457*635a8641SAndroid Build Coastguard Worker };
458*635a8641SAndroid Build Coastguard Worker
459*635a8641SAndroid Build Coastguard Worker iterator erase_after;
460*635a8641SAndroid Build Coastguard Worker switch (dupes) {
461*635a8641SAndroid Build Coastguard Worker case KEEP_FIRST_OF_DUPES:
462*635a8641SAndroid Build Coastguard Worker erase_after = std::unique(first, last, comparator);
463*635a8641SAndroid Build Coastguard Worker break;
464*635a8641SAndroid Build Coastguard Worker case KEEP_LAST_OF_DUPES:
465*635a8641SAndroid Build Coastguard Worker erase_after = LastUnique(first, last, comparator);
466*635a8641SAndroid Build Coastguard Worker break;
467*635a8641SAndroid Build Coastguard Worker }
468*635a8641SAndroid Build Coastguard Worker erase(erase_after, last);
469*635a8641SAndroid Build Coastguard Worker }
470*635a8641SAndroid Build Coastguard Worker
471*635a8641SAndroid Build Coastguard Worker // To support comparators that may not be possible to default-construct, we
472*635a8641SAndroid Build Coastguard Worker // have to store an instance of Compare. Using this to store all internal
473*635a8641SAndroid Build Coastguard Worker // state of flat_tree and using private inheritance to store compare lets us
474*635a8641SAndroid Build Coastguard Worker // take advantage of an empty base class optimization to avoid extra space in
475*635a8641SAndroid Build Coastguard Worker // the common case when Compare has no state.
476*635a8641SAndroid Build Coastguard Worker struct Impl : private value_compare {
477*635a8641SAndroid Build Coastguard Worker Impl() = default;
478*635a8641SAndroid Build Coastguard Worker
479*635a8641SAndroid Build Coastguard Worker template <class Cmp, class... Body>
480*635a8641SAndroid Build Coastguard Worker explicit Impl(Cmp&& compare_arg, Body&&... underlying_type_args)
481*635a8641SAndroid Build Coastguard Worker : value_compare(std::forward<Cmp>(compare_arg)),
482*635a8641SAndroid Build Coastguard Worker body_(std::forward<Body>(underlying_type_args)...) {}
483*635a8641SAndroid Build Coastguard Worker
484*635a8641SAndroid Build Coastguard Worker const value_compare& get_value_comp() const { return *this; }
485*635a8641SAndroid Build Coastguard Worker const key_compare& get_key_comp() const { return *this; }
486*635a8641SAndroid Build Coastguard Worker
487*635a8641SAndroid Build Coastguard Worker underlying_type body_;
488*635a8641SAndroid Build Coastguard Worker } impl_;
489*635a8641SAndroid Build Coastguard Worker
490*635a8641SAndroid Build Coastguard Worker // If the compare is not transparent we want to construct key_type once.
491*635a8641SAndroid Build Coastguard Worker template <typename K>
492*635a8641SAndroid Build Coastguard Worker using KeyTypeOrK = typename std::
493*635a8641SAndroid Build Coastguard Worker conditional<IsTransparentCompare<key_compare>::value, K, key_type>::type;
494*635a8641SAndroid Build Coastguard Worker };
495*635a8641SAndroid Build Coastguard Worker
496*635a8641SAndroid Build Coastguard Worker // ----------------------------------------------------------------------------
497*635a8641SAndroid Build Coastguard Worker // Lifetime.
498*635a8641SAndroid Build Coastguard Worker
499*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
500*635a8641SAndroid Build Coastguard Worker flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree() = default;
501*635a8641SAndroid Build Coastguard Worker
502*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
503*635a8641SAndroid Build Coastguard Worker flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(
504*635a8641SAndroid Build Coastguard Worker const KeyCompare& comp)
505*635a8641SAndroid Build Coastguard Worker : impl_(comp) {}
506*635a8641SAndroid Build Coastguard Worker
507*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
508*635a8641SAndroid Build Coastguard Worker template <class InputIterator>
509*635a8641SAndroid Build Coastguard Worker flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(
510*635a8641SAndroid Build Coastguard Worker InputIterator first,
511*635a8641SAndroid Build Coastguard Worker InputIterator last,
512*635a8641SAndroid Build Coastguard Worker FlatContainerDupes dupe_handling,
513*635a8641SAndroid Build Coastguard Worker const KeyCompare& comp)
514*635a8641SAndroid Build Coastguard Worker : impl_(comp, first, last) {
515*635a8641SAndroid Build Coastguard Worker sort_and_unique(begin(), end(), dupe_handling);
516*635a8641SAndroid Build Coastguard Worker }
517*635a8641SAndroid Build Coastguard Worker
518*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
519*635a8641SAndroid Build Coastguard Worker flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(
520*635a8641SAndroid Build Coastguard Worker const flat_tree&) = default;
521*635a8641SAndroid Build Coastguard Worker
522*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
523*635a8641SAndroid Build Coastguard Worker flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(
524*635a8641SAndroid Build Coastguard Worker std::vector<value_type> items,
525*635a8641SAndroid Build Coastguard Worker FlatContainerDupes dupe_handling,
526*635a8641SAndroid Build Coastguard Worker const KeyCompare& comp)
527*635a8641SAndroid Build Coastguard Worker : impl_(comp, std::move(items)) {
528*635a8641SAndroid Build Coastguard Worker sort_and_unique(begin(), end(), dupe_handling);
529*635a8641SAndroid Build Coastguard Worker }
530*635a8641SAndroid Build Coastguard Worker
531*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
532*635a8641SAndroid Build Coastguard Worker flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(
533*635a8641SAndroid Build Coastguard Worker std::initializer_list<value_type> ilist,
534*635a8641SAndroid Build Coastguard Worker FlatContainerDupes dupe_handling,
535*635a8641SAndroid Build Coastguard Worker const KeyCompare& comp)
536*635a8641SAndroid Build Coastguard Worker : flat_tree(std::begin(ilist), std::end(ilist), dupe_handling, comp) {}
537*635a8641SAndroid Build Coastguard Worker
538*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
539*635a8641SAndroid Build Coastguard Worker flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::~flat_tree() = default;
540*635a8641SAndroid Build Coastguard Worker
541*635a8641SAndroid Build Coastguard Worker // ----------------------------------------------------------------------------
542*635a8641SAndroid Build Coastguard Worker // Assignments.
543*635a8641SAndroid Build Coastguard Worker
544*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
545*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::operator=(
546*635a8641SAndroid Build Coastguard Worker const flat_tree&) -> flat_tree& = default;
547*635a8641SAndroid Build Coastguard Worker
548*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
549*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::operator=(flat_tree &&)
550*635a8641SAndroid Build Coastguard Worker -> flat_tree& = default;
551*635a8641SAndroid Build Coastguard Worker
552*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
553*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::operator=(
554*635a8641SAndroid Build Coastguard Worker std::initializer_list<value_type> ilist) -> flat_tree& {
555*635a8641SAndroid Build Coastguard Worker impl_.body_ = ilist;
556*635a8641SAndroid Build Coastguard Worker sort_and_unique(begin(), end(), KEEP_FIRST_OF_DUPES);
557*635a8641SAndroid Build Coastguard Worker return *this;
558*635a8641SAndroid Build Coastguard Worker }
559*635a8641SAndroid Build Coastguard Worker
560*635a8641SAndroid Build Coastguard Worker // ----------------------------------------------------------------------------
561*635a8641SAndroid Build Coastguard Worker // Memory management.
562*635a8641SAndroid Build Coastguard Worker
563*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
564*635a8641SAndroid Build Coastguard Worker void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::reserve(
565*635a8641SAndroid Build Coastguard Worker size_type new_capacity) {
566*635a8641SAndroid Build Coastguard Worker impl_.body_.reserve(new_capacity);
567*635a8641SAndroid Build Coastguard Worker }
568*635a8641SAndroid Build Coastguard Worker
569*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
570*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::capacity() const
571*635a8641SAndroid Build Coastguard Worker -> size_type {
572*635a8641SAndroid Build Coastguard Worker return impl_.body_.capacity();
573*635a8641SAndroid Build Coastguard Worker }
574*635a8641SAndroid Build Coastguard Worker
575*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
576*635a8641SAndroid Build Coastguard Worker void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::shrink_to_fit() {
577*635a8641SAndroid Build Coastguard Worker impl_.body_.shrink_to_fit();
578*635a8641SAndroid Build Coastguard Worker }
579*635a8641SAndroid Build Coastguard Worker
580*635a8641SAndroid Build Coastguard Worker // ----------------------------------------------------------------------------
581*635a8641SAndroid Build Coastguard Worker // Size management.
582*635a8641SAndroid Build Coastguard Worker
583*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
584*635a8641SAndroid Build Coastguard Worker void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::clear() {
585*635a8641SAndroid Build Coastguard Worker impl_.body_.clear();
586*635a8641SAndroid Build Coastguard Worker }
587*635a8641SAndroid Build Coastguard Worker
588*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
589*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::size() const
590*635a8641SAndroid Build Coastguard Worker -> size_type {
591*635a8641SAndroid Build Coastguard Worker return impl_.body_.size();
592*635a8641SAndroid Build Coastguard Worker }
593*635a8641SAndroid Build Coastguard Worker
594*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
595*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::max_size() const
596*635a8641SAndroid Build Coastguard Worker -> size_type {
597*635a8641SAndroid Build Coastguard Worker return impl_.body_.max_size();
598*635a8641SAndroid Build Coastguard Worker }
599*635a8641SAndroid Build Coastguard Worker
600*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
601*635a8641SAndroid Build Coastguard Worker bool flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::empty() const {
602*635a8641SAndroid Build Coastguard Worker return impl_.body_.empty();
603*635a8641SAndroid Build Coastguard Worker }
604*635a8641SAndroid Build Coastguard Worker
605*635a8641SAndroid Build Coastguard Worker // ----------------------------------------------------------------------------
606*635a8641SAndroid Build Coastguard Worker // Iterators.
607*635a8641SAndroid Build Coastguard Worker
608*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
609*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::begin() -> iterator {
610*635a8641SAndroid Build Coastguard Worker return impl_.body_.begin();
611*635a8641SAndroid Build Coastguard Worker }
612*635a8641SAndroid Build Coastguard Worker
613*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
614*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::begin() const
615*635a8641SAndroid Build Coastguard Worker -> const_iterator {
616*635a8641SAndroid Build Coastguard Worker return impl_.body_.begin();
617*635a8641SAndroid Build Coastguard Worker }
618*635a8641SAndroid Build Coastguard Worker
619*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
620*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::cbegin() const
621*635a8641SAndroid Build Coastguard Worker -> const_iterator {
622*635a8641SAndroid Build Coastguard Worker return impl_.body_.cbegin();
623*635a8641SAndroid Build Coastguard Worker }
624*635a8641SAndroid Build Coastguard Worker
625*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
626*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::end() -> iterator {
627*635a8641SAndroid Build Coastguard Worker return impl_.body_.end();
628*635a8641SAndroid Build Coastguard Worker }
629*635a8641SAndroid Build Coastguard Worker
630*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
631*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::end() const
632*635a8641SAndroid Build Coastguard Worker -> const_iterator {
633*635a8641SAndroid Build Coastguard Worker return impl_.body_.end();
634*635a8641SAndroid Build Coastguard Worker }
635*635a8641SAndroid Build Coastguard Worker
636*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
637*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::cend() const
638*635a8641SAndroid Build Coastguard Worker -> const_iterator {
639*635a8641SAndroid Build Coastguard Worker return impl_.body_.cend();
640*635a8641SAndroid Build Coastguard Worker }
641*635a8641SAndroid Build Coastguard Worker
642*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
643*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::rbegin()
644*635a8641SAndroid Build Coastguard Worker -> reverse_iterator {
645*635a8641SAndroid Build Coastguard Worker return impl_.body_.rbegin();
646*635a8641SAndroid Build Coastguard Worker }
647*635a8641SAndroid Build Coastguard Worker
648*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
649*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::rbegin() const
650*635a8641SAndroid Build Coastguard Worker -> const_reverse_iterator {
651*635a8641SAndroid Build Coastguard Worker return impl_.body_.rbegin();
652*635a8641SAndroid Build Coastguard Worker }
653*635a8641SAndroid Build Coastguard Worker
654*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
655*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::crbegin() const
656*635a8641SAndroid Build Coastguard Worker -> const_reverse_iterator {
657*635a8641SAndroid Build Coastguard Worker return impl_.body_.crbegin();
658*635a8641SAndroid Build Coastguard Worker }
659*635a8641SAndroid Build Coastguard Worker
660*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
661*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::rend()
662*635a8641SAndroid Build Coastguard Worker -> reverse_iterator {
663*635a8641SAndroid Build Coastguard Worker return impl_.body_.rend();
664*635a8641SAndroid Build Coastguard Worker }
665*635a8641SAndroid Build Coastguard Worker
666*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
667*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::rend() const
668*635a8641SAndroid Build Coastguard Worker -> const_reverse_iterator {
669*635a8641SAndroid Build Coastguard Worker return impl_.body_.rend();
670*635a8641SAndroid Build Coastguard Worker }
671*635a8641SAndroid Build Coastguard Worker
672*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
673*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::crend() const
674*635a8641SAndroid Build Coastguard Worker -> const_reverse_iterator {
675*635a8641SAndroid Build Coastguard Worker return impl_.body_.crend();
676*635a8641SAndroid Build Coastguard Worker }
677*635a8641SAndroid Build Coastguard Worker
678*635a8641SAndroid Build Coastguard Worker // ----------------------------------------------------------------------------
679*635a8641SAndroid Build Coastguard Worker // Insert operations.
680*635a8641SAndroid Build Coastguard Worker //
681*635a8641SAndroid Build Coastguard Worker // Currently we use position_hint the same way as eastl or boost:
682*635a8641SAndroid Build Coastguard Worker // https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set.h#L493
683*635a8641SAndroid Build Coastguard Worker
684*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
685*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert(
686*635a8641SAndroid Build Coastguard Worker const value_type& val) -> std::pair<iterator, bool> {
687*635a8641SAndroid Build Coastguard Worker return emplace_key_args(GetKeyFromValue()(val), val);
688*635a8641SAndroid Build Coastguard Worker }
689*635a8641SAndroid Build Coastguard Worker
690*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
691*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert(
692*635a8641SAndroid Build Coastguard Worker value_type&& val) -> std::pair<iterator, bool> {
693*635a8641SAndroid Build Coastguard Worker return emplace_key_args(GetKeyFromValue()(val), std::move(val));
694*635a8641SAndroid Build Coastguard Worker }
695*635a8641SAndroid Build Coastguard Worker
696*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
697*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert(
698*635a8641SAndroid Build Coastguard Worker const_iterator position_hint,
699*635a8641SAndroid Build Coastguard Worker const value_type& val) -> iterator {
700*635a8641SAndroid Build Coastguard Worker return emplace_hint_key_args(position_hint, GetKeyFromValue()(val), val)
701*635a8641SAndroid Build Coastguard Worker .first;
702*635a8641SAndroid Build Coastguard Worker }
703*635a8641SAndroid Build Coastguard Worker
704*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
705*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert(
706*635a8641SAndroid Build Coastguard Worker const_iterator position_hint,
707*635a8641SAndroid Build Coastguard Worker value_type&& val) -> iterator {
708*635a8641SAndroid Build Coastguard Worker return emplace_hint_key_args(position_hint, GetKeyFromValue()(val),
709*635a8641SAndroid Build Coastguard Worker std::move(val))
710*635a8641SAndroid Build Coastguard Worker .first;
711*635a8641SAndroid Build Coastguard Worker }
712*635a8641SAndroid Build Coastguard Worker
713*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
714*635a8641SAndroid Build Coastguard Worker template <class InputIterator>
715*635a8641SAndroid Build Coastguard Worker void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert(
716*635a8641SAndroid Build Coastguard Worker InputIterator first,
717*635a8641SAndroid Build Coastguard Worker InputIterator last,
718*635a8641SAndroid Build Coastguard Worker FlatContainerDupes dupes) {
719*635a8641SAndroid Build Coastguard Worker if (first == last)
720*635a8641SAndroid Build Coastguard Worker return;
721*635a8641SAndroid Build Coastguard Worker
722*635a8641SAndroid Build Coastguard Worker // Cache results whether existing elements should be overwritten and whether
723*635a8641SAndroid Build Coastguard Worker // inserting new elements happens immediately or will be done in a batch.
724*635a8641SAndroid Build Coastguard Worker const bool overwrite_existing = dupes == KEEP_LAST_OF_DUPES;
725*635a8641SAndroid Build Coastguard Worker const bool insert_inplace =
726*635a8641SAndroid Build Coastguard Worker is_multipass<InputIterator>() && std::next(first) == last;
727*635a8641SAndroid Build Coastguard Worker
728*635a8641SAndroid Build Coastguard Worker if (insert_inplace) {
729*635a8641SAndroid Build Coastguard Worker if (overwrite_existing) {
730*635a8641SAndroid Build Coastguard Worker for (; first != last; ++first)
731*635a8641SAndroid Build Coastguard Worker insert_or_assign(*first);
732*635a8641SAndroid Build Coastguard Worker } else
733*635a8641SAndroid Build Coastguard Worker std::copy(first, last, std::inserter(*this, end()));
734*635a8641SAndroid Build Coastguard Worker return;
735*635a8641SAndroid Build Coastguard Worker }
736*635a8641SAndroid Build Coastguard Worker
737*635a8641SAndroid Build Coastguard Worker // Provide a convenience lambda to obtain an iterator pointing past the last
738*635a8641SAndroid Build Coastguard Worker // old element. This needs to be dymanic due to possible re-allocations.
739*635a8641SAndroid Build Coastguard Worker const size_type original_size = size();
740*635a8641SAndroid Build Coastguard Worker auto middle = [this, original_size]() {
741*635a8641SAndroid Build Coastguard Worker return std::next(begin(), original_size);
742*635a8641SAndroid Build Coastguard Worker };
743*635a8641SAndroid Build Coastguard Worker
744*635a8641SAndroid Build Coastguard Worker // For batch updates initialize the first insertion point.
745*635a8641SAndroid Build Coastguard Worker difference_type pos_first_new = original_size;
746*635a8641SAndroid Build Coastguard Worker
747*635a8641SAndroid Build Coastguard Worker // Loop over the input range while appending new values and overwriting
748*635a8641SAndroid Build Coastguard Worker // existing ones, if applicable. Keep track of the first insertion point.
749*635a8641SAndroid Build Coastguard Worker if (overwrite_existing) {
750*635a8641SAndroid Build Coastguard Worker for (; first != last; ++first) {
751*635a8641SAndroid Build Coastguard Worker std::pair<iterator, bool> result =
752*635a8641SAndroid Build Coastguard Worker append_or_assign(begin(), middle(), *first);
753*635a8641SAndroid Build Coastguard Worker if (result.second) {
754*635a8641SAndroid Build Coastguard Worker pos_first_new =
755*635a8641SAndroid Build Coastguard Worker std::min(pos_first_new, std::distance(begin(), result.first));
756*635a8641SAndroid Build Coastguard Worker }
757*635a8641SAndroid Build Coastguard Worker }
758*635a8641SAndroid Build Coastguard Worker } else {
759*635a8641SAndroid Build Coastguard Worker for (; first != last; ++first) {
760*635a8641SAndroid Build Coastguard Worker std::pair<iterator, bool> result =
761*635a8641SAndroid Build Coastguard Worker append_unique(begin(), middle(), *first);
762*635a8641SAndroid Build Coastguard Worker if (result.second) {
763*635a8641SAndroid Build Coastguard Worker pos_first_new =
764*635a8641SAndroid Build Coastguard Worker std::min(pos_first_new, std::distance(begin(), result.first));
765*635a8641SAndroid Build Coastguard Worker }
766*635a8641SAndroid Build Coastguard Worker }
767*635a8641SAndroid Build Coastguard Worker }
768*635a8641SAndroid Build Coastguard Worker
769*635a8641SAndroid Build Coastguard Worker // The new elements might be unordered and contain duplicates, so post-process
770*635a8641SAndroid Build Coastguard Worker // the just inserted elements and merge them with the rest, inserting them at
771*635a8641SAndroid Build Coastguard Worker // the previously found spot.
772*635a8641SAndroid Build Coastguard Worker sort_and_unique(middle(), end(), dupes);
773*635a8641SAndroid Build Coastguard Worker std::inplace_merge(std::next(begin(), pos_first_new), middle(), end(),
774*635a8641SAndroid Build Coastguard Worker value_comp());
775*635a8641SAndroid Build Coastguard Worker }
776*635a8641SAndroid Build Coastguard Worker
777*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
778*635a8641SAndroid Build Coastguard Worker template <class... Args>
779*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace(Args&&... args)
780*635a8641SAndroid Build Coastguard Worker -> std::pair<iterator, bool> {
781*635a8641SAndroid Build Coastguard Worker return insert(value_type(std::forward<Args>(args)...));
782*635a8641SAndroid Build Coastguard Worker }
783*635a8641SAndroid Build Coastguard Worker
784*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
785*635a8641SAndroid Build Coastguard Worker template <class... Args>
786*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace_hint(
787*635a8641SAndroid Build Coastguard Worker const_iterator position_hint,
788*635a8641SAndroid Build Coastguard Worker Args&&... args) -> iterator {
789*635a8641SAndroid Build Coastguard Worker return insert(position_hint, value_type(std::forward<Args>(args)...));
790*635a8641SAndroid Build Coastguard Worker }
791*635a8641SAndroid Build Coastguard Worker
792*635a8641SAndroid Build Coastguard Worker // ----------------------------------------------------------------------------
793*635a8641SAndroid Build Coastguard Worker // Erase operations.
794*635a8641SAndroid Build Coastguard Worker
795*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
796*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase(
797*635a8641SAndroid Build Coastguard Worker iterator position) -> iterator {
798*635a8641SAndroid Build Coastguard Worker return impl_.body_.erase(position);
799*635a8641SAndroid Build Coastguard Worker }
800*635a8641SAndroid Build Coastguard Worker
801*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
802*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase(
803*635a8641SAndroid Build Coastguard Worker const_iterator position) -> iterator {
804*635a8641SAndroid Build Coastguard Worker return impl_.body_.erase(position);
805*635a8641SAndroid Build Coastguard Worker }
806*635a8641SAndroid Build Coastguard Worker
807*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
808*635a8641SAndroid Build Coastguard Worker template <typename K>
809*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase(const K& val)
810*635a8641SAndroid Build Coastguard Worker -> size_type {
811*635a8641SAndroid Build Coastguard Worker auto eq_range = equal_range(val);
812*635a8641SAndroid Build Coastguard Worker auto res = std::distance(eq_range.first, eq_range.second);
813*635a8641SAndroid Build Coastguard Worker erase(eq_range.first, eq_range.second);
814*635a8641SAndroid Build Coastguard Worker return res;
815*635a8641SAndroid Build Coastguard Worker }
816*635a8641SAndroid Build Coastguard Worker
817*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
818*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::erase(
819*635a8641SAndroid Build Coastguard Worker const_iterator first,
820*635a8641SAndroid Build Coastguard Worker const_iterator last) -> iterator {
821*635a8641SAndroid Build Coastguard Worker return impl_.body_.erase(first, last);
822*635a8641SAndroid Build Coastguard Worker }
823*635a8641SAndroid Build Coastguard Worker
824*635a8641SAndroid Build Coastguard Worker // ----------------------------------------------------------------------------
825*635a8641SAndroid Build Coastguard Worker // Comparators.
826*635a8641SAndroid Build Coastguard Worker
827*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
828*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::key_comp() const
829*635a8641SAndroid Build Coastguard Worker -> key_compare {
830*635a8641SAndroid Build Coastguard Worker return impl_.get_key_comp();
831*635a8641SAndroid Build Coastguard Worker }
832*635a8641SAndroid Build Coastguard Worker
833*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
834*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::value_comp() const
835*635a8641SAndroid Build Coastguard Worker -> value_compare {
836*635a8641SAndroid Build Coastguard Worker return impl_.get_value_comp();
837*635a8641SAndroid Build Coastguard Worker }
838*635a8641SAndroid Build Coastguard Worker
839*635a8641SAndroid Build Coastguard Worker // ----------------------------------------------------------------------------
840*635a8641SAndroid Build Coastguard Worker // Search operations.
841*635a8641SAndroid Build Coastguard Worker
842*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
843*635a8641SAndroid Build Coastguard Worker template <typename K>
844*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::count(
845*635a8641SAndroid Build Coastguard Worker const K& key) const -> size_type {
846*635a8641SAndroid Build Coastguard Worker auto eq_range = equal_range(key);
847*635a8641SAndroid Build Coastguard Worker return std::distance(eq_range.first, eq_range.second);
848*635a8641SAndroid Build Coastguard Worker }
849*635a8641SAndroid Build Coastguard Worker
850*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
851*635a8641SAndroid Build Coastguard Worker template <typename K>
852*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::find(const K& key)
853*635a8641SAndroid Build Coastguard Worker -> iterator {
854*635a8641SAndroid Build Coastguard Worker return const_cast_it(as_const().find(key));
855*635a8641SAndroid Build Coastguard Worker }
856*635a8641SAndroid Build Coastguard Worker
857*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
858*635a8641SAndroid Build Coastguard Worker template <typename K>
859*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::find(
860*635a8641SAndroid Build Coastguard Worker const K& key) const -> const_iterator {
861*635a8641SAndroid Build Coastguard Worker auto eq_range = equal_range(key);
862*635a8641SAndroid Build Coastguard Worker return (eq_range.first == eq_range.second) ? end() : eq_range.first;
863*635a8641SAndroid Build Coastguard Worker }
864*635a8641SAndroid Build Coastguard Worker
865*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
866*635a8641SAndroid Build Coastguard Worker template <typename K>
867*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::equal_range(
868*635a8641SAndroid Build Coastguard Worker const K& key) -> std::pair<iterator, iterator> {
869*635a8641SAndroid Build Coastguard Worker auto res = as_const().equal_range(key);
870*635a8641SAndroid Build Coastguard Worker return {const_cast_it(res.first), const_cast_it(res.second)};
871*635a8641SAndroid Build Coastguard Worker }
872*635a8641SAndroid Build Coastguard Worker
873*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
874*635a8641SAndroid Build Coastguard Worker template <typename K>
875*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::equal_range(
876*635a8641SAndroid Build Coastguard Worker const K& key) const -> std::pair<const_iterator, const_iterator> {
877*635a8641SAndroid Build Coastguard Worker auto lower = lower_bound(key);
878*635a8641SAndroid Build Coastguard Worker
879*635a8641SAndroid Build Coastguard Worker GetKeyFromValue extractor;
880*635a8641SAndroid Build Coastguard Worker if (lower == end() || impl_.get_key_comp()(key, extractor(*lower)))
881*635a8641SAndroid Build Coastguard Worker return {lower, lower};
882*635a8641SAndroid Build Coastguard Worker
883*635a8641SAndroid Build Coastguard Worker return {lower, std::next(lower)};
884*635a8641SAndroid Build Coastguard Worker }
885*635a8641SAndroid Build Coastguard Worker
886*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
887*635a8641SAndroid Build Coastguard Worker template <typename K>
888*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::lower_bound(
889*635a8641SAndroid Build Coastguard Worker const K& key) -> iterator {
890*635a8641SAndroid Build Coastguard Worker return const_cast_it(as_const().lower_bound(key));
891*635a8641SAndroid Build Coastguard Worker }
892*635a8641SAndroid Build Coastguard Worker
893*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
894*635a8641SAndroid Build Coastguard Worker template <typename K>
895*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::lower_bound(
896*635a8641SAndroid Build Coastguard Worker const K& key) const -> const_iterator {
897*635a8641SAndroid Build Coastguard Worker static_assert(std::is_convertible<const KeyTypeOrK<K>&, const K&>::value,
898*635a8641SAndroid Build Coastguard Worker "Requested type cannot be bound to the container's key_type "
899*635a8641SAndroid Build Coastguard Worker "which is required for a non-transparent compare.");
900*635a8641SAndroid Build Coastguard Worker
901*635a8641SAndroid Build Coastguard Worker const KeyTypeOrK<K>& key_ref = key;
902*635a8641SAndroid Build Coastguard Worker
903*635a8641SAndroid Build Coastguard Worker KeyValueCompare key_value(impl_.get_key_comp());
904*635a8641SAndroid Build Coastguard Worker return std::lower_bound(begin(), end(), key_ref, key_value);
905*635a8641SAndroid Build Coastguard Worker }
906*635a8641SAndroid Build Coastguard Worker
907*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
908*635a8641SAndroid Build Coastguard Worker template <typename K>
909*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::upper_bound(
910*635a8641SAndroid Build Coastguard Worker const K& key) -> iterator {
911*635a8641SAndroid Build Coastguard Worker return const_cast_it(as_const().upper_bound(key));
912*635a8641SAndroid Build Coastguard Worker }
913*635a8641SAndroid Build Coastguard Worker
914*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
915*635a8641SAndroid Build Coastguard Worker template <typename K>
916*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::upper_bound(
917*635a8641SAndroid Build Coastguard Worker const K& key) const -> const_iterator {
918*635a8641SAndroid Build Coastguard Worker static_assert(std::is_convertible<const KeyTypeOrK<K>&, const K&>::value,
919*635a8641SAndroid Build Coastguard Worker "Requested type cannot be bound to the container's key_type "
920*635a8641SAndroid Build Coastguard Worker "which is required for a non-transparent compare.");
921*635a8641SAndroid Build Coastguard Worker
922*635a8641SAndroid Build Coastguard Worker const KeyTypeOrK<K>& key_ref = key;
923*635a8641SAndroid Build Coastguard Worker
924*635a8641SAndroid Build Coastguard Worker KeyValueCompare key_value(impl_.get_key_comp());
925*635a8641SAndroid Build Coastguard Worker return std::upper_bound(begin(), end(), key_ref, key_value);
926*635a8641SAndroid Build Coastguard Worker }
927*635a8641SAndroid Build Coastguard Worker
928*635a8641SAndroid Build Coastguard Worker // ----------------------------------------------------------------------------
929*635a8641SAndroid Build Coastguard Worker // General operations.
930*635a8641SAndroid Build Coastguard Worker
931*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
932*635a8641SAndroid Build Coastguard Worker void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::swap(
933*635a8641SAndroid Build Coastguard Worker flat_tree& other) noexcept {
934*635a8641SAndroid Build Coastguard Worker std::swap(impl_, other.impl_);
935*635a8641SAndroid Build Coastguard Worker }
936*635a8641SAndroid Build Coastguard Worker
937*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
938*635a8641SAndroid Build Coastguard Worker template <class... Args>
939*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::unsafe_emplace(
940*635a8641SAndroid Build Coastguard Worker const_iterator position,
941*635a8641SAndroid Build Coastguard Worker Args&&... args) -> iterator {
942*635a8641SAndroid Build Coastguard Worker return impl_.body_.emplace(position, std::forward<Args>(args)...);
943*635a8641SAndroid Build Coastguard Worker }
944*635a8641SAndroid Build Coastguard Worker
945*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
946*635a8641SAndroid Build Coastguard Worker template <class K, class... Args>
947*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace_key_args(
948*635a8641SAndroid Build Coastguard Worker const K& key,
949*635a8641SAndroid Build Coastguard Worker Args&&... args) -> std::pair<iterator, bool> {
950*635a8641SAndroid Build Coastguard Worker auto lower = lower_bound(key);
951*635a8641SAndroid Build Coastguard Worker if (lower == end() || key_comp()(key, GetKeyFromValue()(*lower)))
952*635a8641SAndroid Build Coastguard Worker return {unsafe_emplace(lower, std::forward<Args>(args)...), true};
953*635a8641SAndroid Build Coastguard Worker return {lower, false};
954*635a8641SAndroid Build Coastguard Worker }
955*635a8641SAndroid Build Coastguard Worker
956*635a8641SAndroid Build Coastguard Worker template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
957*635a8641SAndroid Build Coastguard Worker template <class K, class... Args>
958*635a8641SAndroid Build Coastguard Worker auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace_hint_key_args(
959*635a8641SAndroid Build Coastguard Worker const_iterator hint,
960*635a8641SAndroid Build Coastguard Worker const K& key,
961*635a8641SAndroid Build Coastguard Worker Args&&... args) -> std::pair<iterator, bool> {
962*635a8641SAndroid Build Coastguard Worker GetKeyFromValue extractor;
963*635a8641SAndroid Build Coastguard Worker if ((hint == begin() || key_comp()(extractor(*std::prev(hint)), key))) {
964*635a8641SAndroid Build Coastguard Worker if (hint == end() || key_comp()(key, extractor(*hint))) {
965*635a8641SAndroid Build Coastguard Worker // *(hint - 1) < key < *hint => key did not exist and hint is correct.
966*635a8641SAndroid Build Coastguard Worker return {unsafe_emplace(hint, std::forward<Args>(args)...), true};
967*635a8641SAndroid Build Coastguard Worker }
968*635a8641SAndroid Build Coastguard Worker if (!key_comp()(extractor(*hint), key)) {
969*635a8641SAndroid Build Coastguard Worker // key == *hint => no-op, return correct hint.
970*635a8641SAndroid Build Coastguard Worker return {const_cast_it(hint), false};
971*635a8641SAndroid Build Coastguard Worker }
972*635a8641SAndroid Build Coastguard Worker }
973*635a8641SAndroid Build Coastguard Worker // hint was not helpful, dispatch to hintless version.
974*635a8641SAndroid Build Coastguard Worker return emplace_key_args(key, std::forward<Args>(args)...);
975*635a8641SAndroid Build Coastguard Worker }
976*635a8641SAndroid Build Coastguard Worker
977*635a8641SAndroid Build Coastguard Worker // For containers like sets, the key is the same as the value. This implements
978*635a8641SAndroid Build Coastguard Worker // the GetKeyFromValue template parameter to flat_tree for this case.
979*635a8641SAndroid Build Coastguard Worker template <class Key>
980*635a8641SAndroid Build Coastguard Worker struct GetKeyFromValueIdentity {
981*635a8641SAndroid Build Coastguard Worker const Key& operator()(const Key& k) const { return k; }
982*635a8641SAndroid Build Coastguard Worker };
983*635a8641SAndroid Build Coastguard Worker
984*635a8641SAndroid Build Coastguard Worker } // namespace internal
985*635a8641SAndroid Build Coastguard Worker
986*635a8641SAndroid Build Coastguard Worker // ----------------------------------------------------------------------------
987*635a8641SAndroid Build Coastguard Worker // Free functions.
988*635a8641SAndroid Build Coastguard Worker
989*635a8641SAndroid Build Coastguard Worker // Erases all elements that match predicate. It has O(size) complexity.
990*635a8641SAndroid Build Coastguard Worker template <class Key,
991*635a8641SAndroid Build Coastguard Worker class Value,
992*635a8641SAndroid Build Coastguard Worker class GetKeyFromValue,
993*635a8641SAndroid Build Coastguard Worker class KeyCompare,
994*635a8641SAndroid Build Coastguard Worker typename Predicate>
995*635a8641SAndroid Build Coastguard Worker void EraseIf(base::internal::flat_tree<Key, Value, GetKeyFromValue, KeyCompare>&
996*635a8641SAndroid Build Coastguard Worker container,
997*635a8641SAndroid Build Coastguard Worker Predicate pred) {
998*635a8641SAndroid Build Coastguard Worker container.erase(std::remove_if(container.begin(), container.end(), pred),
999*635a8641SAndroid Build Coastguard Worker container.end());
1000*635a8641SAndroid Build Coastguard Worker }
1001*635a8641SAndroid Build Coastguard Worker
1002*635a8641SAndroid Build Coastguard Worker } // namespace base
1003*635a8641SAndroid Build Coastguard Worker
1004*635a8641SAndroid Build Coastguard Worker #endif // BASE_CONTAINERS_FLAT_TREE_H_
1005