1//     __ _____ _____ _____
2//  __|  |   __|     |   | |  JSON for Modern C++
3// |  |  |__   |  |  | | | |  version 3.11.2
4// |_____|_____|_____|_|___|  https://github.com/nlohmann/json
5//
6// SPDX-FileCopyrightText: 2013-2022 Niels Lohmann <https://nlohmann.me>
7// SPDX-License-Identifier: MIT
8
9#pragma once
10
11#include <functional> // equal_to, less
12#include <initializer_list> // initializer_list
13#include <iterator> // input_iterator_tag, iterator_traits
14#include <memory> // allocator
15#include <stdexcept> // for out_of_range
16#include <type_traits> // enable_if, is_convertible
17#include <utility> // pair
18#include <vector> // vector
19
20#include <nlohmann/detail/macro_scope.hpp>
21#include <nlohmann/detail/meta/type_traits.hpp>
22
23NLOHMANN_JSON_NAMESPACE_BEGIN
24
25/// ordered_map: a minimal map-like container that preserves insertion order
26/// for use within nlohmann::basic_json<ordered_map>
27template <class Key, class T, class IgnoredLess = std::less<Key>,
28          class Allocator = std::allocator<std::pair<const Key, T>>>
29                  struct ordered_map : std::vector<std::pair<const Key, T>, Allocator>
30{
31    using key_type = Key;
32    using mapped_type = T;
33    using Container = std::vector<std::pair<const Key, T>, Allocator>;
34    using iterator = typename Container::iterator;
35    using const_iterator = typename Container::const_iterator;
36    using size_type = typename Container::size_type;
37    using value_type = typename Container::value_type;
38#ifdef JSON_HAS_CPP_14
39    using key_compare = std::equal_to<>;
40#else
41    using key_compare = std::equal_to<Key>;
42#endif
43
44    // Explicit constructors instead of `using Container::Container`
45    // otherwise older compilers choke on it (GCC <= 5.5, xcode <= 9.4)
46    ordered_map() noexcept(noexcept(Container())) : Container{} {}
47    explicit ordered_map(const Allocator& alloc) noexcept(noexcept(Container(alloc))) : Container{alloc} {}
48    template <class It>
49    ordered_map(It first, It last, const Allocator& alloc = Allocator())
50        : Container{first, last, alloc} {}
51    ordered_map(std::initializer_list<value_type> init, const Allocator& alloc = Allocator() )
52        : Container{init, alloc} {}
53
54    std::pair<iterator, bool> emplace(const key_type& key, T&& t)
55    {
56        for (auto it = this->begin(); it != this->end(); ++it)
57        {
58            if (m_compare(it->first, key))
59            {
60                return {it, false};
61            }
62        }
63        Container::emplace_back(key, std::forward<T>(t));
64        return {std::prev(this->end()), true};
65    }
66
67    template<class KeyType, detail::enable_if_t<
68                 detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0>
69    std::pair<iterator, bool> emplace(KeyType && key, T && t)
70    {
71        for (auto it = this->begin(); it != this->end(); ++it)
72        {
73            if (m_compare(it->first, key))
74            {
75                return {it, false};
76            }
77        }
78        Container::emplace_back(std::forward<KeyType>(key), std::forward<T>(t));
79        return {std::prev(this->end()), true};
80    }
81
82    T& operator[](const key_type& key)
83    {
84        return emplace(key, T{}).first->second;
85    }
86
87    template<class KeyType, detail::enable_if_t<
88                 detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0>
89    T & operator[](KeyType && key)
90    {
91        return emplace(std::forward<KeyType>(key), T{}).first->second;
92    }
93
94    const T& operator[](const key_type& key) const
95    {
96        return at(key);
97    }
98
99    template<class KeyType, detail::enable_if_t<
100                 detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0>
101    const T & operator[](KeyType && key) const
102    {
103        return at(std::forward<KeyType>(key));
104    }
105
106    T& at(const key_type& key)
107    {
108        for (auto it = this->begin(); it != this->end(); ++it)
109        {
110            if (m_compare(it->first, key))
111            {
112                return it->second;
113            }
114        }
115
116        JSON_THROW(std::out_of_range("key not found"));
117    }
118
119    template<class KeyType, detail::enable_if_t<
120                 detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0>
121    T & at(KeyType && key)
122    {
123        for (auto it = this->begin(); it != this->end(); ++it)
124        {
125            if (m_compare(it->first, key))
126            {
127                return it->second;
128            }
129        }
130
131        JSON_THROW(std::out_of_range("key not found"));
132    }
133
134    const T& at(const key_type& key) const
135    {
136        for (auto it = this->begin(); it != this->end(); ++it)
137        {
138            if (m_compare(it->first, key))
139            {
140                return it->second;
141            }
142        }
143
144        JSON_THROW(std::out_of_range("key not found"));
145    }
146
147    template<class KeyType, detail::enable_if_t<
148                 detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0>
149    const T & at(KeyType && key) const
150    {
151        for (auto it = this->begin(); it != this->end(); ++it)
152        {
153            if (m_compare(it->first, key))
154            {
155                return it->second;
156            }
157        }
158
159        JSON_THROW(std::out_of_range("key not found"));
160    }
161
162    size_type erase(const key_type& key)
163    {
164        for (auto it = this->begin(); it != this->end(); ++it)
165        {
166            if (m_compare(it->first, key))
167            {
168                // Since we cannot move const Keys, re-construct them in place
169                for (auto next = it; ++next != this->end(); ++it)
170                {
171                    it->~value_type(); // Destroy but keep allocation
172                    new (&*it) value_type{std::move(*next)};
173                }
174                Container::pop_back();
175                return 1;
176            }
177        }
178        return 0;
179    }
180
181    template<class KeyType, detail::enable_if_t<
182                 detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0>
183    size_type erase(KeyType && key)
184    {
185        for (auto it = this->begin(); it != this->end(); ++it)
186        {
187            if (m_compare(it->first, key))
188            {
189                // Since we cannot move const Keys, re-construct them in place
190                for (auto next = it; ++next != this->end(); ++it)
191                {
192                    it->~value_type(); // Destroy but keep allocation
193                    new (&*it) value_type{std::move(*next)};
194                }
195                Container::pop_back();
196                return 1;
197            }
198        }
199        return 0;
200    }
201
202    iterator erase(iterator pos)
203    {
204        return erase(pos, std::next(pos));
205    }
206
207    iterator erase(iterator first, iterator last)
208    {
209        if (first == last)
210        {
211            return first;
212        }
213
214        const auto elements_affected = std::distance(first, last);
215        const auto offset = std::distance(Container::begin(), first);
216
217        // This is the start situation. We need to delete elements_affected
218        // elements (3 in this example: e, f, g), and need to return an
219        // iterator past the last deleted element (h in this example).
220        // Note that offset is the distance from the start of the vector
221        // to first. We will need this later.
222
223        // [ a, b, c, d, e, f, g, h, i, j ]
224        //               ^        ^
225        //             first    last
226
227        // Since we cannot move const Keys, we re-construct them in place.
228        // We start at first and re-construct (viz. copy) the elements from
229        // the back of the vector. Example for first iteration:
230
231        //               ,--------.
232        //               v        |   destroy e and re-construct with h
233        // [ a, b, c, d, e, f, g, h, i, j ]
234        //               ^        ^
235        //               it       it + elements_affected
236
237        for (auto it = first; std::next(it, elements_affected) != Container::end(); ++it)
238        {
239            it->~value_type(); // destroy but keep allocation
240            new (&*it) value_type{std::move(*std::next(it, elements_affected))}; // "move" next element to it
241        }
242
243        // [ a, b, c, d, h, i, j, h, i, j ]
244        //               ^        ^
245        //             first    last
246
247        // remove the unneeded elements at the end of the vector
248        Container::resize(this->size() - static_cast<size_type>(elements_affected));
249
250        // [ a, b, c, d, h, i, j ]
251        //               ^        ^
252        //             first    last
253
254        // first is now pointing past the last deleted element, but we cannot
255        // use this iterator, because it may have been invalidated by the
256        // resize call. Instead, we can return begin() + offset.
257        return Container::begin() + offset;
258    }
259
260    size_type count(const key_type& key) const
261    {
262        for (auto it = this->begin(); it != this->end(); ++it)
263        {
264            if (m_compare(it->first, key))
265            {
266                return 1;
267            }
268        }
269        return 0;
270    }
271
272    template<class KeyType, detail::enable_if_t<
273                 detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0>
274    size_type count(KeyType && key) const
275    {
276        for (auto it = this->begin(); it != this->end(); ++it)
277        {
278            if (m_compare(it->first, key))
279            {
280                return 1;
281            }
282        }
283        return 0;
284    }
285
286    iterator find(const key_type& key)
287    {
288        for (auto it = this->begin(); it != this->end(); ++it)
289        {
290            if (m_compare(it->first, key))
291            {
292                return it;
293            }
294        }
295        return Container::end();
296    }
297
298    template<class KeyType, detail::enable_if_t<
299                 detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0>
300    iterator find(KeyType && key)
301    {
302        for (auto it = this->begin(); it != this->end(); ++it)
303        {
304            if (m_compare(it->first, key))
305            {
306                return it;
307            }
308        }
309        return Container::end();
310    }
311
312    const_iterator find(const key_type& key) const
313    {
314        for (auto it = this->begin(); it != this->end(); ++it)
315        {
316            if (m_compare(it->first, key))
317            {
318                return it;
319            }
320        }
321        return Container::end();
322    }
323
324    std::pair<iterator, bool> insert( value_type&& value )
325    {
326        return emplace(value.first, std::move(value.second));
327    }
328
329    std::pair<iterator, bool> insert( const value_type& value )
330    {
331        for (auto it = this->begin(); it != this->end(); ++it)
332        {
333            if (m_compare(it->first, value.first))
334            {
335                return {it, false};
336            }
337        }
338        Container::push_back(value);
339        return {--this->end(), true};
340    }
341
342    template<typename InputIt>
343    using require_input_iter = typename std::enable_if<std::is_convertible<typename std::iterator_traits<InputIt>::iterator_category,
344            std::input_iterator_tag>::value>::type;
345
346    template<typename InputIt, typename = require_input_iter<InputIt>>
347    void insert(InputIt first, InputIt last)
348    {
349        for (auto it = first; it != last; ++it)
350        {
351            insert(*it);
352        }
353    }
354
355private:
356    JSON_NO_UNIQUE_ADDRESS key_compare m_compare = key_compare();
357};
358
359NLOHMANN_JSON_NAMESPACE_END
360