Line data Source code
1 : /*
2 : * SPDX-License-Identifier: GPL-3.0-only
3 : * MuseScore-CLA-applies
4 : *
5 : * MuseScore Studio
6 : * Music Composition & Notation
7 : *
8 : * Copyright (C) 2021 MuseScore Limited and others
9 : *
10 : * This program is free software: you can redistribute it and/or modify
11 : * it under the terms of the GNU General Public License version 3 as
12 : * published by the Free Software Foundation.
13 : *
14 : * This program is distributed in the hope that it will be useful,
15 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 : * GNU General Public License for more details.
18 : *
19 : * You should have received a copy of the GNU General Public License
20 : * along with this program. If not, see <https://www.gnu.org/licenses/>.
21 : */
22 : #pragma once
23 :
24 : #include <algorithm>
25 : #include <vector>
26 : #include <list>
27 : #include <set>
28 : #include <unordered_set>
29 : #include <map>
30 : #include <unordered_map>
31 :
32 : //! NOTE useful functions for containers
33 :
34 : namespace muse {
35 : static constexpr size_t nidx = static_cast<size_t>(-1);
36 :
37 : // vector
38 : template<typename T>
39 2808643 : inline bool contains(const std::vector<T>& vec, const T& v)
40 : {
41 2808643 : return std::find(vec.cbegin(), vec.cend(), v) != vec.cend();
42 : }
43 :
44 : template<typename T, typename Predicate>
45 404 : inline bool contains_if(const std::vector<T>& vec, Predicate&& pred)
46 : {
47 404 : return std::find_if(vec.cbegin(), vec.cend(), std::forward<Predicate>(pred)) != vec.cend();
48 : }
49 :
50 : template<typename T>
51 180557 : inline T value(const std::vector<T>& vec, size_t idx)
52 : {
53 180557 : if (idx < vec.size()) {
54 180557 : return vec.at(idx);
55 : }
56 :
57 : if constexpr (std::is_pointer<T>::value) {
58 0 : return nullptr;
59 : } else {
60 0 : return T();
61 : }
62 : }
63 :
64 : template<typename T>
65 248081 : inline bool remove(std::vector<T>& vec, const T& v)
66 : {
67 248081 : size_t origSize = vec.size();
68 248081 : vec.erase(std::remove(vec.begin(), vec.end(), v), vec.end());
69 248081 : return origSize != vec.size();
70 : }
71 :
72 : template<typename T, typename Predicate>
73 4396 : inline bool remove_if(std::vector<T>& vec, Predicate p)
74 : {
75 4396 : size_t origSize = vec.size();
76 4396 : vec.erase(std::remove_if(vec.begin(), vec.end(), p), vec.end());
77 4396 : return origSize != vec.size();
78 : }
79 :
80 : template<typename T>
81 : inline void removeFirst(std::vector<T>& vec)
82 : {
83 : vec.erase(vec.begin());
84 : }
85 :
86 : template<typename T>
87 166687 : inline T takeAt(std::vector<T>& vec, size_t idx)
88 : {
89 166687 : T v = value(vec, idx);
90 166687 : vec.erase(vec.begin() + idx);
91 166687 : return v;
92 0 : }
93 :
94 : template<typename T>
95 1716 : inline T takeFirst(std::vector<T>& vec)
96 : {
97 1716 : return takeAt(vec, 0);
98 : }
99 :
100 : template<typename T>
101 163487 : inline T takeLast(std::vector<T>& vec)
102 : {
103 163487 : return takeAt(vec, vec.size() - 1);
104 : }
105 :
106 : template<typename T>
107 0 : inline void swapItemsAt(std::vector<T>& vec, size_t idx1, size_t idx2)
108 : {
109 0 : T v1 = vec[idx1];
110 0 : vec[idx1] = vec[idx2];
111 0 : vec[idx2] = v1;
112 0 : }
113 :
114 : template<typename T>
115 4 : inline bool moveItem(std::vector<T>& vec, size_t oldIdx, size_t newIdx)
116 : {
117 4 : if (oldIdx == muse::nidx || oldIdx == newIdx) {
118 1 : return false;
119 : }
120 :
121 3 : newIdx = std::min(vec.size() - 1, newIdx);
122 :
123 3 : if (oldIdx > newIdx) {
124 1 : std::rotate(vec.rend() - oldIdx - 1, vec.rend() - oldIdx, vec.rend() - newIdx);
125 : } else {
126 2 : std::rotate(vec.begin() + oldIdx, vec.begin() + oldIdx + 1, vec.begin() + newIdx + 1);
127 : }
128 :
129 3 : return true;
130 : }
131 :
132 : template<typename T>
133 591 : std::vector<T> mid(const std::vector<T>& c, size_t pos, int alength = -1)
134 : {
135 591 : if (c.empty()) {
136 0 : return std::vector<T>();
137 : }
138 :
139 591 : size_t end = 0;
140 591 : if (alength < 0) {
141 591 : end = c.size();
142 : } else {
143 0 : end = pos + static_cast<size_t>(alength);
144 : }
145 :
146 591 : if (end > (c.size())) {
147 0 : end = c.size();
148 : }
149 :
150 591 : if (end == 0) {
151 0 : return std::vector<T>();
152 : }
153 :
154 591 : if (pos >= end) {
155 0 : return std::vector<T>();
156 : }
157 :
158 591 : std::vector<T> sub(c.begin() + pos, c.begin() + end);
159 591 : return sub;
160 591 : }
161 :
162 : template<typename T>
163 117 : inline void join(std::vector<T>& l1, const std::vector<T>& l2)
164 : {
165 117 : l1.insert(l1.end(), l2.begin(), l2.end());
166 117 : }
167 :
168 : // list
169 : template<typename T>
170 7729 : inline bool contains(const std::list<T>& l, const T& v)
171 : {
172 7729 : return std::find(l.cbegin(), l.cend(), v) != l.cend();
173 : }
174 :
175 : template<typename T>
176 0 : inline void join(std::list<T>& l1, const std::list<T>& l2)
177 : {
178 0 : l1.insert(l1.end(), l2.begin(), l2.end());
179 0 : }
180 :
181 : template<typename T>
182 1487 : inline bool remove(std::list<T>& l, const T& v)
183 : {
184 1487 : if (!contains(l, v)) {
185 0 : return false;
186 : }
187 1487 : l.remove(v);
188 1487 : return true;
189 : }
190 :
191 : template<typename T>
192 : inline T takeFirst(std::list<T>& l)
193 : {
194 : T v = l.front();
195 : l.pop_front();
196 : return v;
197 : }
198 :
199 : template<typename T>
200 : inline T takeLast(std::list<T>& l)
201 : {
202 : T v = l.back();
203 : l.pop_back();
204 : return v;
205 : }
206 :
207 : template<typename T>
208 : inline std::pair<bool, T> take(std::list<T>& l, const T& v)
209 : {
210 : auto it = std::find(l.begin(), l.end(), v);
211 : if (it == l.end()) {
212 : return std::make_pair(false, T());
213 : }
214 : std::pair<bool, T> ret = std::make_pair(true, *it);
215 : l.erase(it);
216 : return ret;
217 : }
218 :
219 : // ===========================
220 : // Set
221 : // ===========================
222 : template<typename T>
223 116238 : inline bool contains(const std::set<T>& s, const T& v)
224 : {
225 116238 : return s.find(v) != s.cend();
226 : }
227 :
228 : template<typename T>
229 3472488 : inline bool contains(const std::unordered_set<T>& s, const T& v)
230 : {
231 3472488 : return s.find(v) != s.cend();
232 : }
233 :
234 : // ===========================
235 : // Array
236 : // ===========================
237 : template<typename T, size_t size>
238 1391 : inline bool contains(const std::array<T, size>& s, const T& v)
239 : {
240 1391 : return std::find(s.begin(), s.end(), v) != s.cend();
241 : }
242 :
243 : // ===========================
244 : // General
245 : // ===========================
246 :
247 : template<typename Container, typename T>
248 394464 : inline size_t indexOf(const Container& c, const T& v)
249 : {
250 394464 : auto it = std::find(c.cbegin(), c.cend(), v);
251 394464 : if (it != c.cend()) {
252 788756 : return std::distance(c.cbegin(), it);
253 : }
254 86 : return muse::nidx;
255 : }
256 :
257 : template<typename K, typename V>
258 105513 : inline bool contains(const std::map<K, V>& m, const K& k)
259 : {
260 105513 : return m.find(k) != m.cend();
261 : }
262 :
263 : template<typename K, typename V>
264 12 : inline bool contains(const std::multimap<K, V>& m, const K& k)
265 : {
266 12 : return m.find(k) != m.cend();
267 : }
268 :
269 : template<typename K, typename V>
270 534228 : inline bool contains(const std::unordered_map<K, V>& m, const K& k)
271 : {
272 534228 : return m.find(k) != m.cend();
273 : }
274 :
275 : template<typename Map>
276 7116 : inline auto values(const Map& m) -> std::vector<typename Map::mapped_type>
277 : {
278 7116 : std::vector<typename Map::mapped_type> result;
279 7116 : result.reserve(m.size());
280 7243 : for (const auto& p : m) {
281 127 : result.push_back(p.second);
282 : }
283 7116 : return result;
284 0 : }
285 :
286 : template<typename Map, typename V, typename K>
287 4240 : inline K key(const Map& m, const V& v, const K& def)
288 : {
289 21721 : for (const auto& p : m) {
290 20735 : if (p.second == v) {
291 3254 : return p.first;
292 : }
293 : }
294 986 : return def;
295 : }
296 :
297 : template<typename Map, typename V>
298 22 : inline auto key(const Map& m, const V& v) -> typename Map::key_type
299 : {
300 1732 : for (const auto& p : m) {
301 1732 : if (p.second == v) {
302 22 : return p.first;
303 : }
304 : }
305 0 : typename Map::key_type def {};
306 0 : return def;
307 0 : }
308 :
309 : template<typename Map>
310 146236 : inline auto value(const Map& m, const typename Map::key_type& k) -> typename Map::mapped_type
311 : {
312 146236 : auto it = m.find(k);
313 146236 : if (it != m.end()) {
314 104990 : return it->second;
315 : }
316 41246 : typename Map::mapped_type def {};
317 41246 : return def;
318 41244 : }
319 :
320 : template<typename Map>
321 2557744 : inline auto value(const Map& m, const typename Map::key_type& k, const typename Map::mapped_type& def) -> typename Map::mapped_type
322 : {
323 2557744 : auto it = m.find(k);
324 2557744 : if (it != m.end()) {
325 158990 : return it->second;
326 : }
327 2398754 : return def;
328 : }
329 :
330 : template<typename Map, typename T>
331 131 : inline bool remove(Map& c, const T& k)
332 : {
333 131 : auto it = c.find(k);
334 131 : if (it != c.end()) {
335 61 : c.erase(it);
336 61 : return true;
337 : }
338 70 : return false;
339 : }
340 :
341 : template<typename Map, typename Predicate>
342 11 : inline size_t remove_if(Map& c, Predicate pred)
343 : {
344 11 : auto old_size = c.size();
345 11 : for (auto first = c.begin(), last = c.end(); first != last;) {
346 0 : if (pred(*first)) {
347 0 : first = c.erase(first);
348 : } else {
349 0 : ++first;
350 : }
351 : }
352 11 : return old_size - c.size();
353 : }
354 :
355 : template<typename Map, typename K>
356 4668 : inline auto take(Map& m, const K& k) -> typename Map::mapped_type
357 : {
358 4668 : auto it = m.find(k);
359 4668 : if (it != m.end()) {
360 4668 : auto v = it->second;
361 4668 : m.erase(it);
362 4668 : return v;
363 0 : }
364 0 : typename Map::mapped_type def {};
365 0 : return def;
366 0 : }
367 :
368 : template<typename K, typename V>
369 1864 : inline std::set<K> uniqueKeys(const std::multimap<K, V>& mm)
370 : {
371 1864 : std::set<K> keys;
372 2212 : for (auto it = mm.begin(); it != mm.end(); ++it) {
373 348 : keys.insert(it->first);
374 : }
375 1864 : return keys;
376 0 : }
377 :
378 : template<typename K, typename V>
379 18626 : inline auto values(const std::multimap<K, V>& mm, const K& key) -> std::vector<typename std::multimap<K, V>::mapped_type>
380 : {
381 18626 : std::vector<typename std::multimap<K, V>::mapped_type> result;
382 18626 : const auto range = mm.equal_range(key);
383 29789 : for (auto it = range.first; it != range.second; ++it) {
384 11163 : result.push_back(it->second);
385 : }
386 18626 : return result;
387 0 : }
388 :
389 : template<typename Container>
390 9495 : inline typename Container::const_iterator findLessOrEqual(const Container& c, const typename Container::key_type& k)
391 : {
392 9495 : if (c.empty()) {
393 3769 : return c.cend();
394 : }
395 :
396 5726 : auto it = c.upper_bound(k);
397 5726 : if (it == c.cbegin()) {
398 2507 : return c.cend();
399 : }
400 :
401 3219 : return std::prev(it);
402 : }
403 :
404 : template<typename Container>
405 117 : inline typename Container::iterator findLessOrEqual(Container& c, const typename Container::key_type& k)
406 : {
407 117 : if (c.empty()) {
408 89 : return c.end();
409 : }
410 :
411 28 : auto it = c.upper_bound(k);
412 28 : if (it == c.begin()) {
413 5 : return c.end();
414 : }
415 :
416 23 : return std::prev(it);
417 : }
418 :
419 : template<typename Container>
420 : inline typename Container::const_iterator findLess(const Container& c, const typename Container::key_type& k)
421 : {
422 : if (c.empty()) {
423 : return c.cend();
424 : }
425 :
426 : auto it = c.lower_bound(k);
427 : if (it == c.cbegin()) {
428 : return c.cend();
429 : }
430 :
431 : return std::prev(it);
432 : }
433 :
434 : template<typename Container>
435 505 : inline typename Container::iterator findLess(Container& c, const typename Container::key_type& k)
436 : {
437 505 : if (c.empty()) {
438 463 : return c.end();
439 : }
440 :
441 42 : auto it = c.lower_bound(k);
442 42 : if (it == c.begin()) {
443 22 : return c.end();
444 : }
445 :
446 20 : return std::prev(it);
447 : }
448 :
449 : template<typename ForwardIterator>
450 665569 : inline void DeleteAll(ForwardIterator begin, ForwardIterator end)
451 : {
452 972226 : while (begin != end) {
453 306657 : delete *begin;
454 306657 : ++begin;
455 : }
456 665569 : }
457 :
458 : template<typename Container>
459 665569 : inline void DeleteAll(const Container& c)
460 : {
461 665569 : DeleteAll(c.begin(), c.end());
462 665569 : }
463 : }
464 :
465 : template<typename T>
466 0 : inline std::set<T>& operator<<(std::set<T>& s, const T& v)
467 : {
468 0 : s.insert(v);
469 0 : return s;
470 : }
|
