FireSTARR
Loading...
Searching...
No Matches
SortedVector.h
1/* SPDX-License-Identifier: AGPL-3.0-or-later */
2#ifndef FS_SORTEDVECTOR_H
3#define FS_SORTEDVECTOR_H
4#include "stdafx.h"
5namespace fs
6{
7template <class T>
8vector<T> merge(const vector<T>& lhs, const vector<T>& rhs) noexcept
9{
10 vector<T> out{};
11 // maximum size is if no overlap
12 out.reserve(lhs.size() + rhs.size());
13 auto it_lhs = lhs.begin();
14 auto it_rhs = rhs.begin();
15 auto end_lhs = lhs.end();
16 auto end_rhs = rhs.end();
17 while (true)
18 {
19 if (end_lhs == it_lhs)
20 {
21 while (end_rhs != it_rhs)
22 {
23 out.emplace_back(*it_rhs);
24 ++it_rhs;
25 }
26 break;
27 }
28 if (end_rhs == it_rhs)
29 {
30 while (end_lhs != it_lhs)
31 {
32 out.emplace_back(*it_lhs);
33 ++it_lhs;
34 }
35 break;
36 }
37 // at end of neither so pick lower value
38 const T& v0 = *it_lhs;
39 const T& v1 = *it_rhs;
40 if (v0 < v1)
41 {
42 out.emplace_back(v0);
43 ++it_lhs;
44 }
45 else if (v0 > v1)
46 {
47 out.emplace_back(v1);
48 ++it_rhs;
49 }
50 else
51 {
52 out.emplace_back(v0);
53 ++it_lhs;
54 ++it_rhs;
55 }
56 }
57}
58template <class T>
60{
61 std::vector<T> values_{};
62
63public:
64 ~SortedVector() = default;
68 SortedVector() = default;
69 SortedVector(const SortedVector& rhs);
70 SortedVector(SortedVector&& rhs) noexcept;
71 SortedVector& operator=(const SortedVector& rhs) noexcept;
72 SortedVector& operator=(SortedVector&& rhs) noexcept;
73 auto insert(const T& v) noexcept
74 {
75 auto it = std::lower_bound(values_.begin(), values_.end(), v);
76 return values_.insert(it, v);
77 }
78 auto contains(const T& v) const noexcept
79 {
80 auto it = std::lower_bound(values_.begin(), values_.end(), v);
81 return it != values_.end();
82 }
83 [[nodiscard]] size_t size() const noexcept { return values_.size(); }
84 void merge(const SortedVector<T>& rhs) noexcept { values_ = merge(values_, rhs.values_); }
85};
86template <class K, class V>
88{
89 using value_type = std::pair<K, V>;
90 // FIX: duplicate SortedVector for now
91 std::vector<value_type> values_{};
92
93public:
94 static auto compare_function(const value_type& kv0, const value_type& kv1)
95 {
96 return kv0.first <=> kv1.first;
97 };
98 ~LinearMap() = default;
102 LinearMap() = default;
103 LinearMap(const LinearMap& rhs);
104 LinearMap(LinearMap&& rhs) noexcept;
105 LinearMap& operator=(const LinearMap& rhs) noexcept;
106 LinearMap& operator=(LinearMap&& rhs) noexcept;
107 template <class... Args>
108 auto try_emplace(
109 const K& k1,
110 std::function<void(const K& k0, V& v0, V& v1)> fct_merge,
111 Args... args
112 ) noexcept
113 {
114 // find lower bound based on key only
115 auto it = std::lower_bound(values_.begin(), values_.end(), compare_function);
116 if (values_.end() != it)
117 {
118 auto& [k0, v0] = *it;
119 if (k0 == k1)
120 {
121 // if keys match then merge values and keep key
122 fct_merge(k0, v0, V{args...});
123 // key existed
124 return std::pair{it, true};
125 }
126 // keys don't match
127 }
128 // insert at key position
129 it = values_.insert(it, V{args...});
130 // key did not exist
131 return std::pair{it, false};
132 }
133 auto insert(
134 const value_type& kv,
135 std::function<void(const K& k0, V& v0, V& v1)> fct_merge
136 ) noexcept
137 {
138 // find lower bound based on key only
139 auto it = std::lower_bound(values_.begin(), values_.end(), compare_function);
140 if (values_.end() != it)
141 {
142 auto& [k0, v0] = *it;
143 auto& [k1, v1] = kv;
144 if (k0 == k1)
145 {
146 // if keys match then merge values and keep key
147 fct_merge(k0, v0, v1);
148 return it;
149 }
150 // keys don't match
151 }
152 // insert at key position
153 return values_.insert(it, kv);
154 }
155 auto contains(const value_type& v) const noexcept
156 {
157 auto it = std::lower_bound(values_.begin(), values_.end(), compare_function);
158 return it != values_.end();
159 }
160 [[nodiscard]] size_t size() const noexcept { return values_.size(); }
161 // void merge(const LinearMap<K, V>& rhs) noexcept { values_ = merge(values_, rhs.values_); }
162};
163}
164#endif
Definition SortedVector.h:88
LinearMap()=default
Construct empty LinearMap.
Definition SortedVector.h:60
SortedVector()=default
Construct empty SortedVector.