Global.h 23 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778
  1. /*
  2. * Global.h, part of VCMI engine
  3. *
  4. * Authors: listed in file AUTHORS in main folder
  5. *
  6. * License: GNU General Public License v2.0 or later
  7. * Full text of license available in license.txt file, in main folder
  8. *
  9. */
  10. #pragma once
  11. /* ---------------------------------------------------------------------------- */
  12. /* Compiler detection */
  13. /* ---------------------------------------------------------------------------- */
  14. // Fixed width bool data type is important for serialization
  15. static_assert(sizeof(bool) == 1, "Bool needs to be 1 byte in size.");
  16. /* ---------------------------------------------------------------------------- */
  17. /* System detection. */
  18. /* ---------------------------------------------------------------------------- */
  19. // Based on: http://sourceforge.net/p/predef/wiki/OperatingSystems/
  20. // and on: http://stackoverflow.com/questions/5919996/how-to-detect-reliably-mac-os-x-ios-linux-windows-in-c-preprocessor
  21. // TODO?: Should be moved to vstd\os_detect.h (and then included by Global.h)
  22. #ifdef _WIN16 // Defined for 16-bit environments
  23. # error "16-bit Windows isn't supported"
  24. #elif defined(_WIN64) // Defined for 64-bit environments
  25. # define VCMI_WINDOWS
  26. # define VCMI_WINDOWS_64
  27. #elif defined(_WIN32) // Defined for both 32-bit and 64-bit environments
  28. # define VCMI_WINDOWS
  29. # define VCMI_WINDOWS_32
  30. #elif defined(_WIN32_WCE)
  31. # error "Windows CE isn't supported"
  32. #elif defined(__linux__) || defined(__gnu_linux__) || defined(linux) || defined(__linux)
  33. # define VCMI_UNIX
  34. # define VCMI_XDG
  35. # if defined(__ANDROID__) || defined(ANDROID)
  36. # define VCMI_ANDROID
  37. # endif
  38. #elif defined(__FreeBSD_kernel__) || defined(__FreeBSD__)
  39. # define VCMI_UNIX
  40. # define VCMI_XDG
  41. # define VCMI_FREEBSD
  42. #elif defined(__OpenBSD__)
  43. # define VCMI_UNIX
  44. # define VCMI_XDG
  45. # define VCMI_OPENBSD
  46. #elif defined(__HAIKU__)
  47. # define VCMI_UNIX
  48. # define VCMI_XDG
  49. # define VCMI_HAIKU
  50. #elif defined(__GNU__) || defined(__gnu_hurd__) || (defined(__MACH__) && !defined(__APPLE__))
  51. # define VCMI_UNIX
  52. # define VCMI_XDG
  53. # define VCMI_HURD
  54. #elif defined(__APPLE__) && defined(__MACH__)
  55. # define VCMI_UNIX
  56. # define VCMI_APPLE
  57. # include "TargetConditionals.h"
  58. # if TARGET_OS_SIMULATOR || TARGET_IPHONE_SIMULATOR
  59. # define VCMI_IOS
  60. # define VCMI_IOS_SIM
  61. # elif TARGET_OS_IPHONE
  62. # define VCMI_IOS
  63. # elif TARGET_OS_MAC
  64. # define VCMI_MAC
  65. # else
  66. //# warning "Unknown Apple target."?
  67. # endif
  68. #else
  69. # error "This platform isn't supported"
  70. #endif
  71. #if defined(VCMI_ANDROID) || defined(VCMI_IOS)
  72. #define VCMI_MOBILE
  73. #endif
  74. /* ---------------------------------------------------------------------------- */
  75. /* Commonly used C++, Boost headers */
  76. /* ---------------------------------------------------------------------------- */
  77. #ifdef VCMI_WINDOWS
  78. # ifndef WIN32_LEAN_AND_MEAN
  79. # define WIN32_LEAN_AND_MEAN // Exclude rarely-used stuff from Windows headers - delete this line if something is missing.
  80. # endif
  81. # ifndef NOMINMAX
  82. # define NOMINMAX // Exclude min/max macros from <Windows.h>. Use std::[min/max] from <algorithm> instead.
  83. # endif
  84. # ifndef _NO_W32_PSEUDO_MODIFIERS
  85. # define _NO_W32_PSEUDO_MODIFIERS // Exclude more macros for compiling with MinGW on Linux.
  86. # endif
  87. #endif
  88. /* ---------------------------------------------------------------------------- */
  89. /* A macro to force inlining some of our functions */
  90. /* ---------------------------------------------------------------------------- */
  91. // Compiler (at least MSVC) is not so smart here-> without that displaying is MUCH slower
  92. #ifdef _MSC_VER
  93. # define STRONG_INLINE __forceinline
  94. #elif __GNUC__
  95. # define STRONG_INLINE inline __attribute__((always_inline))
  96. #else
  97. # define STRONG_INLINE inline
  98. #endif
  99. // Required for building boost::stacktrace on macOS.
  100. // See https://github.com/boostorg/stacktrace/issues/88
  101. #if defined(VCMI_APPLE)
  102. #define _GNU_SOURCE
  103. #endif
  104. #define _USE_MATH_DEFINES
  105. #include <algorithm>
  106. #include <any>
  107. #include <array>
  108. #include <atomic>
  109. #include <bitset>
  110. #include <cassert>
  111. #include <chrono>
  112. #include <climits>
  113. #include <cmath>
  114. #include <condition_variable>
  115. #include <cstdio>
  116. #include <cstdlib>
  117. #include <fstream>
  118. #include <functional>
  119. #include <iomanip>
  120. #include <iostream>
  121. #include <map>
  122. #include <memory>
  123. #include <mutex>
  124. #include <numeric>
  125. #include <optional>
  126. #include <queue>
  127. #include <random>
  128. #include <regex>
  129. #include <set>
  130. #include <shared_mutex>
  131. #include <sstream>
  132. #include <string>
  133. #include <thread>
  134. #include <unordered_map>
  135. #include <unordered_set>
  136. #include <utility>
  137. #include <variant>
  138. #include <vector>
  139. // VCMI requires features that were added to TBB 2021.4
  140. // However, until TBB 2021.7 they were only available with this define
  141. // For versions TBB 2021.7 and later this define is not required
  142. #define TBB_PREVIEW_TASK_GROUP_EXTENSIONS 1
  143. #include <boost/version.hpp>
  144. // As of Boost 1.50+, the only available version is 3,
  145. // Version 4 has been added in Boost 1.77
  146. #define BOOST_FILESYSTEM_VERSION 3
  147. #if BOOST_VERSION == 107400
  148. # define BOOST_ALLOW_DEPRECATED_HEADERS
  149. #endif
  150. #include <boost/algorithm/string.hpp>
  151. #include <boost/container/small_vector.hpp>
  152. #include <boost/container/static_vector.hpp>
  153. // C++ 20 -> std::source_location::function_name
  154. #include <boost/current_function.hpp>
  155. // C++ 17 -> std::filesystem
  156. #include <boost/filesystem/directory.hpp>
  157. #include <boost/filesystem/exception.hpp>
  158. #include <boost/filesystem/file_status.hpp>
  159. #include <boost/filesystem/operations.hpp>
  160. #include <boost/filesystem/path.hpp>
  161. #include <boost/format.hpp>
  162. #include <boost/logic/tribool.hpp>
  163. #include <boost/multi_array.hpp>
  164. // C++ 20 -> std::range
  165. #include <boost/range/adaptor/filtered.hpp>
  166. #include <boost/range/adaptor/reversed.hpp>
  167. #include <boost/range/algorithm/copy.hpp>
  168. #include <boost/range/algorithm/count.hpp>
  169. #include <boost/range/algorithm/count_if.hpp>
  170. #include <boost/range/algorithm/fill.hpp>
  171. #include <boost/range/algorithm/find.hpp>
  172. #include <boost/range/algorithm/find_if.hpp>
  173. #include <boost/range/algorithm/max_element.hpp>
  174. #include <boost/range/algorithm/min_element.hpp>
  175. #include <boost/range/algorithm/remove.hpp>
  176. #include <boost/range/algorithm/remove_if.hpp>
  177. #include <boost/range/algorithm/replace.hpp>
  178. #include <boost/range/algorithm/sort.hpp>
  179. #include <boost/range/algorithm/unique.hpp>
  180. #include <boost/range/algorithm/upper_bound.hpp>
  181. #ifndef M_PI
  182. # define M_PI 3.14159265358979323846
  183. #endif
  184. /* ---------------------------------------------------------------------------- */
  185. /* Usings */
  186. /* ---------------------------------------------------------------------------- */
  187. using namespace std::placeholders;
  188. /* ---------------------------------------------------------------------------- */
  189. /* Typedefs */
  190. /* ---------------------------------------------------------------------------- */
  191. // Integral data types
  192. typedef uint64_t ui64; //unsigned int 64 bits (8 bytes)
  193. typedef uint32_t ui32; //unsigned int 32 bits (4 bytes)
  194. typedef uint16_t ui16; //unsigned int 16 bits (2 bytes)
  195. typedef uint8_t ui8; //unsigned int 8 bits (1 byte)
  196. typedef int64_t si64; //signed int 64 bits (8 bytes)
  197. typedef int32_t si32; //signed int 32 bits (4 bytes)
  198. typedef int16_t si16; //signed int 16 bits (2 bytes)
  199. typedef int8_t si8; //signed int 8 bits (1 byte)
  200. // Lock typedefs
  201. using TLockGuard = std::lock_guard<std::mutex>;
  202. using TLockGuardRec = std::lock_guard<std::recursive_mutex>;
  203. /* ---------------------------------------------------------------------------- */
  204. /* Macros */
  205. /* ---------------------------------------------------------------------------- */
  206. // Import + Export macro declarations
  207. #ifdef VCMI_WINDOWS
  208. # ifdef VCMI_DLL_STATIC
  209. # define DLL_IMPORT
  210. # define DLL_EXPORT
  211. # elif defined(__GNUC__)
  212. # define DLL_IMPORT __attribute__((dllimport))
  213. # define DLL_EXPORT __attribute__((dllexport))
  214. # else
  215. # define DLL_IMPORT __declspec(dllimport)
  216. # define DLL_EXPORT __declspec(dllexport)
  217. # endif
  218. # define ELF_VISIBILITY
  219. #else
  220. # ifdef __GNUC__
  221. # define DLL_IMPORT __attribute__ ((visibility("default")))
  222. # define DLL_EXPORT __attribute__ ((visibility("default")))
  223. # define ELF_VISIBILITY __attribute__ ((visibility("default")))
  224. # endif
  225. #endif
  226. #ifdef VCMI_DLL
  227. # define DLL_LINKAGE DLL_EXPORT
  228. #else
  229. # define DLL_LINKAGE DLL_IMPORT
  230. #endif
  231. // old iOS SDKs compatibility
  232. #ifdef VCMI_IOS
  233. #include <AvailabilityVersions.h>
  234. #ifndef __IPHONE_13_0
  235. #define __IPHONE_13_0 130000
  236. #endif
  237. #endif // VCMI_IOS
  238. // single-process build makes 2 copies of the main lib by wrapping it in a namespace
  239. #ifdef VCMI_LIB_NAMESPACE
  240. #define VCMI_LIB_NAMESPACE_BEGIN namespace VCMI_LIB_NAMESPACE {
  241. #define VCMI_LIB_NAMESPACE_END }
  242. #define VCMI_LIB_USING_NAMESPACE using namespace VCMI_LIB_NAMESPACE;
  243. #define VCMI_LIB_WRAP_NAMESPACE(x) VCMI_LIB_NAMESPACE::x
  244. #else
  245. #define VCMI_LIB_NAMESPACE_BEGIN
  246. #define VCMI_LIB_NAMESPACE_END
  247. #define VCMI_LIB_USING_NAMESPACE
  248. #define VCMI_LIB_WRAP_NAMESPACE(x) ::x
  249. #endif
  250. /* ---------------------------------------------------------------------------- */
  251. /* VCMI standard library */
  252. /* ---------------------------------------------------------------------------- */
  253. #include <vstd/CLoggerBase.h>
  254. VCMI_LIB_NAMESPACE_BEGIN
  255. namespace vstd
  256. {
  257. // combine hashes. Present in boost but not in std
  258. template <class T>
  259. inline void hash_combine(std::size_t& seed, const T& v)
  260. {
  261. std::hash<T> hasher;
  262. seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
  263. }
  264. //returns true if container c contains item i
  265. template <typename Container, typename Item>
  266. bool contains(const Container & c, const Item &i)
  267. {
  268. return std::find(std::begin(c), std::end(c),i) != std::end(c);
  269. }
  270. //returns true if container c contains item i
  271. template <typename Container, typename Pred>
  272. bool contains_if(const Container & c, Pred p)
  273. {
  274. return std::find_if(std::begin(c), std::end(c), p) != std::end(c);
  275. }
  276. //returns true if map c contains item i
  277. template <typename V, typename Item, typename Item2>
  278. bool contains(const std::map<Item,V> & c, const Item2 &i)
  279. {
  280. return c.find(i)!=c.end();
  281. }
  282. //returns true if unordered set c contains item i
  283. template <typename Item>
  284. bool contains(const std::unordered_set<Item> & c, const Item &i)
  285. {
  286. return c.find(i)!=c.end();
  287. }
  288. template <typename V, typename Item, typename Item2>
  289. bool contains(const std::unordered_map<Item,V> & c, const Item2 &i)
  290. {
  291. return c.find(i)!=c.end();
  292. }
  293. //returns position of first element in vector c equal to s, if there is no such element, -1 is returned
  294. template <typename Container, typename T2>
  295. int find_pos(const Container & c, const T2 &s)
  296. {
  297. int i=0;
  298. for (auto iter = std::begin(c); iter != std::end(c); iter++, i++)
  299. if(*iter == s)
  300. return i;
  301. return -1;
  302. }
  303. //Func f tells if element matches
  304. template <typename Container, typename Func>
  305. int find_pos_if(const Container & c, const Func &f)
  306. {
  307. auto ret = std::find_if(c.begin(), c.end(), f);
  308. if(ret != std::end(c))
  309. return std::distance(std::begin(c), ret);
  310. return -1;
  311. }
  312. //returns iterator to the given element if present in container, end() if not
  313. template <typename Container, typename Item>
  314. typename Container::iterator find(Container & c, const Item &i)
  315. {
  316. return std::find(c.begin(),c.end(),i);
  317. }
  318. //returns const iterator to the given element if present in container, end() if not
  319. template <typename Container, typename Item>
  320. typename Container::const_iterator find(const Container & c, const Item &i)
  321. {
  322. return std::find(c.begin(),c.end(),i);
  323. }
  324. // returns existing value from map, or default value if key does not exists
  325. template <typename Map>
  326. const typename Map::mapped_type & find_or(const Map& m, const typename Map::key_type& key, const typename Map::mapped_type& defaultValue) {
  327. auto it = m.find(key);
  328. if (it == m.end())
  329. return defaultValue;
  330. return it->second;
  331. }
  332. // given a map from keys to values, creates a new map from values to keys
  333. template<typename K, typename V>
  334. static std::map<V, K> reverseMap(const std::map<K, V>& m) {
  335. std::map<V, K> r;
  336. for (const auto& kv : m)
  337. r[kv.second] = kv.first;
  338. return r;
  339. }
  340. //returns first key that maps to given value if present, returns success via found if provided
  341. template <typename Key, typename T>
  342. Key findKey(const std::map<Key, T> & map, const T & value, bool * found = nullptr)
  343. {
  344. for(auto iter = map.cbegin(); iter != map.cend(); iter++)
  345. {
  346. if(iter->second == value)
  347. {
  348. if(found)
  349. *found = true;
  350. return iter->first;
  351. }
  352. }
  353. if(found)
  354. *found = false;
  355. return Key();
  356. }
  357. //removes element i from container c, returns false if c does not contain i
  358. template <typename Container, typename Item>
  359. typename Container::size_type operator-=(Container &c, const Item &i)
  360. {
  361. typename Container::iterator itr = find(c,i);
  362. if(itr == c.end())
  363. return false;
  364. c.erase(itr);
  365. return true;
  366. }
  367. //assigns greater of (a, b) to a and returns maximum of (a, b)
  368. template <typename t1, typename t2>
  369. t1 &amax(t1 &a, const t2 &b)
  370. {
  371. if(a >= (t1)b)
  372. return a;
  373. else
  374. {
  375. a = t1(b);
  376. return a;
  377. }
  378. }
  379. //assigns smaller of (a, b) to a and returns minimum of (a, b)
  380. template <typename t1, typename t2>
  381. t1 &amin(t1 &a, const t2 &b)
  382. {
  383. if(a <= (t1)b)
  384. return a;
  385. else
  386. {
  387. a = t1(b);
  388. return a;
  389. }
  390. }
  391. //makes a to fit the range <b, c>
  392. template <typename T>
  393. void abetween(T &value, const T &min, const T &max)
  394. {
  395. value = std::clamp(value, min, max);
  396. }
  397. //checks if a is between b and c
  398. template <typename t1, typename t2, typename t3>
  399. bool isbetween(const t1 &value, const t2 &min, const t3 &max)
  400. {
  401. return value > (t1)min && value < (t1)max;
  402. }
  403. //checks if a is within b and c
  404. template <typename t1, typename t2, typename t3>
  405. bool iswithin(const t1 &value, const t2 &min, const t3 &max)
  406. {
  407. return value >= (t1)min && value <= (t1)max;
  408. }
  409. template <typename t1, typename t2>
  410. struct assigner
  411. {
  412. public:
  413. t1 &op1;
  414. t2 op2;
  415. assigner(t1 &a1, const t2 & a2)
  416. :op1(a1), op2(a2)
  417. {}
  418. void operator()()
  419. {
  420. op1 = op2;
  421. }
  422. };
  423. //deleted pointer and sets it to nullptr
  424. template <typename T>
  425. void clear_pointer(T* &ptr)
  426. {
  427. delete ptr;
  428. ptr = nullptr;
  429. }
  430. template <typename Container>
  431. typename Container::const_reference circularAt(const Container &r, size_t index)
  432. {
  433. assert(r.size());
  434. index %= r.size();
  435. auto itr = std::begin(r);
  436. std::advance(itr, index);
  437. return *itr;
  438. }
  439. template <typename Container, typename Item>
  440. void erase(Container &c, const Item &item)
  441. {
  442. c.erase(std::remove(c.begin(), c.end(), item), c.end());
  443. }
  444. template<typename Range, typename Predicate>
  445. void erase_if(Range &vec, Predicate pred)
  446. {
  447. vec.erase(std::remove_if(vec.begin(), vec.end(), pred), vec.end());
  448. }
  449. template<typename Elem, typename Predicate>
  450. void erase_if(std::set<Elem> &setContainer, Predicate pred)
  451. {
  452. auto itr = setContainer.begin();
  453. auto endItr = setContainer.end();
  454. while(itr != endItr)
  455. {
  456. auto tmpItr = itr++;
  457. if(pred(*tmpItr))
  458. setContainer.erase(tmpItr);
  459. }
  460. }
  461. template<typename Elem, typename Predicate>
  462. void erase_if(std::unordered_set<Elem> &setContainer, Predicate pred)
  463. {
  464. auto itr = setContainer.begin();
  465. auto endItr = setContainer.end();
  466. while(itr != endItr)
  467. {
  468. auto tmpItr = itr++;
  469. if(pred(*tmpItr))
  470. setContainer.erase(tmpItr);
  471. }
  472. }
  473. //works for map and std::map, maybe something else
  474. template<typename Key, typename Val, typename Predicate>
  475. void erase_if(std::map<Key, Val> &container, Predicate pred)
  476. {
  477. auto itr = container.begin();
  478. auto endItr = container.end();
  479. while(itr != endItr)
  480. {
  481. auto tmpItr = itr++;
  482. if(pred(*tmpItr))
  483. container.erase(tmpItr);
  484. }
  485. }
  486. //works for std::unordered_map, maybe something else
  487. template<typename Key, typename Val, typename Predicate>
  488. void erase_if(std::unordered_map<Key, Val> & container, Predicate pred)
  489. {
  490. auto itr = container.begin();
  491. auto endItr = container.end();
  492. while(itr != endItr)
  493. {
  494. auto tmpItr = itr++;
  495. if(pred(*tmpItr))
  496. container.erase(tmpItr);
  497. }
  498. }
  499. // Removes all duplicate elements from the vector
  500. template<typename T>
  501. void unique(std::vector<T> &vec)
  502. {
  503. std::sort(vec.begin(), vec.end());
  504. auto newEnd = std::unique(vec.begin(), vec.end());
  505. vec.erase(newEnd, vec.end());
  506. }
  507. template<typename InputRange, typename OutputIterator, typename Predicate>
  508. OutputIterator copy_if(const InputRange &input, OutputIterator result, Predicate pred)
  509. {
  510. return std::copy_if(std::cbegin(input), std::end(input), result, pred);
  511. }
  512. template <typename Container>
  513. std::insert_iterator<Container> set_inserter(Container &c)
  514. {
  515. return std::inserter(c, c.end());
  516. }
  517. //Returns iterator to the element for which the value of ValueFunction is minimal
  518. template<class ForwardRange, class ValueFunction>
  519. auto minElementByFun(const ForwardRange& rng, ValueFunction vf)
  520. {
  521. /* Clang crashes when instantiating this function template and having PCH compilation enabled.
  522. * There is a bug report here: http://llvm.org/bugs/show_bug.cgi?id=18744
  523. * Current bugfix is to don't use a typedef for decltype(*std::begin(rng)) and to use decltype
  524. * directly for both function parameters.
  525. */
  526. return std::min_element(rng.begin(), rng.end(), [&] (decltype(*std::begin(rng)) lhs, decltype(*std::begin(rng)) rhs) -> bool
  527. {
  528. return vf(lhs) < vf(rhs);
  529. });
  530. }
  531. //Returns iterator to the element for which the value of ValueFunction is maximal
  532. template<class ForwardRange, class ValueFunction>
  533. auto maxElementByFun(const ForwardRange& rng, ValueFunction vf)
  534. {
  535. /* Clang crashes when instantiating this function template and having PCH compilation enabled.
  536. * There is a bug report here: http://llvm.org/bugs/show_bug.cgi?id=18744
  537. * Current bugfix is to don't use a typedef for decltype(*std::begin(rng)) and to use decltype
  538. * directly for both function parameters.
  539. */
  540. return std::max_element(rng.begin(), rng.end(), [&] (decltype(*std::begin(rng)) lhs, decltype(*std::begin(rng)) rhs) -> bool
  541. {
  542. return vf(lhs) < vf(rhs);
  543. });
  544. }
  545. /// Increments value by specific delta
  546. /// similar to std::next but works with other types, e.g. enum class
  547. template<typename T>
  548. T next(const T &obj, int change)
  549. {
  550. return static_cast<T>(static_cast<ptrdiff_t>(obj) + change);
  551. }
  552. template <typename Container>
  553. typename Container::value_type backOrNull(const Container &c) //returns last element of container or nullptr if it is empty (to be used with containers of pointers)
  554. {
  555. if(c.size())
  556. return c.back();
  557. else
  558. return typename Container::value_type();
  559. }
  560. template <typename Container>
  561. typename Container::value_type frontOrNull(const Container &c) //returns first element of container or nullptr if it is empty (to be used with containers of pointers)
  562. {
  563. if(c.size())
  564. return c.front();
  565. else
  566. return nullptr;
  567. }
  568. template <typename Container, typename Index>
  569. bool isValidIndex(const Container &c, Index i)
  570. {
  571. return i >= 0 && i < c.size();
  572. }
  573. template <typename Container>
  574. typename Container::const_reference atOrDefault(const Container &r, size_t index, const typename Container::const_reference &defaultValue)
  575. {
  576. if(index < r.size())
  577. return r[index];
  578. return defaultValue;
  579. }
  580. template <typename Container, typename Item>
  581. bool erase_if_present(Container &c, const Item &item)
  582. {
  583. auto i = std::find(c.begin(), c.end(), item);
  584. if (i != c.end())
  585. {
  586. c.erase(i);
  587. return true;
  588. }
  589. return false;
  590. }
  591. template <typename V, typename Item, typename Item2>
  592. bool erase_if_present(std::map<Item,V> & c, const Item2 &item)
  593. {
  594. auto i = c.find(item);
  595. if (i != c.end())
  596. {
  597. c.erase(i);
  598. return true;
  599. }
  600. return false;
  601. }
  602. template <typename Container>
  603. void removeDuplicates(Container &vec)
  604. {
  605. std::sort(vec.begin(), vec.end());
  606. vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
  607. }
  608. template <typename Container>
  609. void concatenate(Container &dest, const Container &src)
  610. {
  611. dest.reserve(dest.size() + src.size());
  612. dest.insert(dest.end(), src.begin(), src.end());
  613. }
  614. template <typename T>
  615. std::vector<T> intersection(std::vector<T> &v1, std::vector<T> &v2)
  616. {
  617. std::vector<T> v3;
  618. std::sort(v1.begin(), v1.end());
  619. std::sort(v2.begin(), v2.end());
  620. std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v3));
  621. return v3;
  622. }
  623. template <typename T>
  624. std::set<T> difference(const std::set<T> &s1, const std::set<T> s2)
  625. {
  626. std::set<T> s3;
  627. std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), std::inserter(s3, s3.end()));
  628. return s3;
  629. }
  630. template <typename Key, typename V>
  631. bool containsMapping(const std::multimap<Key,V> & map, const std::pair<const Key,V> & mapping)
  632. {
  633. auto range = map.equal_range(mapping.first);
  634. for(auto contained = range.first; contained != range.second; contained++)
  635. {
  636. if(mapping.second == contained->second)
  637. return true;
  638. }
  639. return false;
  640. }
  641. //c++20 feature
  642. template<typename Arithmetic, typename Floating>
  643. Arithmetic lerp(const Arithmetic & a, const Arithmetic & b, const Floating & f)
  644. {
  645. return a + (b - a) * f;
  646. }
  647. /// Divides dividend by divisor and rounds result up
  648. /// For use with integer-only arithmetic
  649. template<typename Integer1, typename Integer2>
  650. Integer1 divideAndCeil(const Integer1 & dividend, const Integer2 & divisor)
  651. {
  652. static_assert(std::is_integral_v<Integer1> && std::is_integral_v<Integer2>, "This function should only be used with integral types");
  653. return (dividend + divisor - 1) / divisor;
  654. }
  655. /// Divides dividend by divisor and rounds result to nearest
  656. /// For use with integer-only arithmetic
  657. template<typename Integer1, typename Integer2>
  658. Integer1 divideAndRound(const Integer1 & dividend, const Integer2 & divisor)
  659. {
  660. static_assert(std::is_integral_v<Integer1> && std::is_integral_v<Integer2>, "This function should only be used with integral types");
  661. return (dividend + divisor / 2 - 1) / divisor;
  662. }
  663. /// Divides dividend by divisor and rounds result down
  664. /// For use with integer-only arithmetic
  665. template<typename Integer1, typename Integer2>
  666. Integer1 divideAndFloor(const Integer1 & dividend, const Integer2 & divisor)
  667. {
  668. static_assert(std::is_integral_v<Integer1> && std::is_integral_v<Integer2>, "This function should only be used with integral types");
  669. return dividend / divisor;
  670. }
  671. template<typename Floating>
  672. bool isAlmostZero(const Floating & value)
  673. {
  674. constexpr Floating epsilon(0.00001);
  675. return std::abs(value) <= epsilon;
  676. }
  677. template<typename Floating1, typename Floating2>
  678. bool isAlmostEqual(const Floating1 & left, const Floating2 & right)
  679. {
  680. using Floating = decltype(left + right);
  681. constexpr Floating epsilon(0.00001);
  682. const Floating relativeEpsilon = std::max(std::abs(left), std::abs(right)) * epsilon;
  683. const Floating value = std::abs(left - right);
  684. return value <= relativeEpsilon;
  685. }
  686. ///compile-time version of std::abs for ints for int3, in clang++15 std::abs is constexpr
  687. static constexpr int abs(int i) {
  688. if(i < 0) return -i;
  689. return i;
  690. }
  691. ///C++23
  692. template< class Enum > constexpr std::underlying_type_t<Enum> to_underlying( Enum e ) noexcept
  693. {
  694. return static_cast<std::underlying_type_t<Enum>>(e);
  695. }
  696. }
  697. using vstd::operator-=;
  698. VCMI_LIB_NAMESPACE_END