/** * @file dl_algorithm.h * @brief 算法 * * * @version 1.0 * @author lveyou * @date 23-06-22 * * @note 不得包含dl_range.h */ #pragma once #include #include #include #include #include #include #include "base/dl_concept.h" #include "base/dl_array.h" namespace dl { /** * @brief 限制数值到 [a, b] */ template constexpr T clamp(const T& x, const T& a, const T& b) { if (x < a) return a; if (b < x) return b; return x; } /** * @brief 限制数值到 [0, 1] */ template constexpr T saturate(const T& x) { #if DL_PLATFORM == DL_PLATFORM_LINUX return dl::clamp(x, 0, 1); #else return std::clamp(x, 0, 1); #endif } /** * @brief 是否数值在[0, 1] */ template constexpr T is_saturate(const T& x) { return x >= 0 && x <= 1; } /** * @brief 向量叉乘 */ template constexpr Array cross(const Array& a, const Array& b) { return { a[1] * b[2] - a[2] * b[1], a[2] * b[0] - a[0] * b[2], a[0] * b[1] - a[1] * b[0] }; } /** * @brief 动态类型强转 * @note 记得传入指针进行多态 */ template [[deprecated]] inline T cast_dynamic(void* p) { return dynamic_cast(p); } /** * @brief 限制到大于某个值,如果修改了原值则返回true */ template bool limit_bigger(Array& a, const Array& limit) { bool ret = false; for (int i = 0; i != N; ++i) { if (a[i] < limit[i]) { a[i] = limit[i]; ret = true; } } return ret; } template inline const T& as_const(T& a) { #if DL_PLATFORM == DL_PLATFORM_WIN32 return std::as_const(a); #else return (const T&)a; #endif } //-------------------------------------------------------other----------------------------------------- /** * @brief 从容器container中移除 最后 匹配到的a元素 之前(包含a)的所有元素,如果没有匹配到,则什么都不做。 * @param container 操作的容器 * @param[in] a 要匹配的元素 * @remarks {"data/image/cat.png", '/'} -> "cat.png" */ template void erase_head_from_last(T& container, const V& a) { auto iter = find(container.rbegin(), container.rend(), a); if (iter != container.rend()) container.erase(container.begin(), iter.base()); } /** * @brief 从容器container不断取出第一个元素,执行操作 * @param container 操作的容器 * @param[in] func 对元素执行的操作 * @note 将容器置空可以中断执行 */ template void operate_front(C& container, F func) { while (!container.empty()) { auto iter = container.front(); container.pop_front(); func(iter); } } //! 查找算法 //namespace Find //{ // /** // * @brief find,返回下标 // * @note 失败返回-1 // */ // template // size_t Index(const T& container, const V& v) // { // size_t size = container.size(); // for (size_t i = 0; i < size; ++i) // { // if (container[i] == v) // { // return i; // } // } // return -1; // } // /** // * @brief find,返回下标 // * @note 失败返回y == size // */ // template // array Index(const vector>& container, const V& v) // { // array ret{}; // for (; ret[1] < container.size(); ++ret[1]) // { // auto& line = container[ret[1]]; // for (ret[0] = 0; ret[0] < line.size(); ++ret[0]) // { // if (line[ret[0]] == v) // { // return ret; // } // } // } // return ret; // } //} /** * @brief 取地址,可用于右值 * @note 注意对象生命周期 */ template inline T* pointer(T&& x) { return &x; } /** * @brief 加上const修饰 */ template inline const T& constant(T& v) { return v; } /** * @brief 替换容器元素值 */ //template //inline void replace(T& vec, V v, V v_new) //{ // for (auto& iter : vec) // { // if (iter == v) // iter = v_new; // } //} /** * @brief 返回 重复元素位置,没有返回end */ template auto find_equal(C& container) { for (auto iter = container.begin(); iter != container.end(); ++iter) { auto iter1 = iter; ++iter1; for (; iter1 < container.end(); ++iter1) { if (*iter == *iter1) return iter1; } } return container.end(); } /** * @brief 隔n个元素就插入1个分割符,首尾不会出现分割符 * @remarks { "1234567890", ',', 3} -> 123,456,789,0 */ template T insert_per_num(const T& container, V v, size_t per_num) { if (container.size() <= per_num) return T(container); size_t num = (container.size() - 1) / per_num;//每3个插入计算得出:9 -> 2; 11 -> 3 T ret; ret.resize(num + container.size()); size_t i = 0; auto iter = container.begin(); auto iter_ret = ret.begin(); while (iter != container.end()) { *iter_ret++ = *iter++; ++i; //满per_num额外加入一个v,且不为最后一个 if (i % per_num == 0 && i < container.size()) *iter_ret++ = v; } return ret; } /** * @brief 从后面往前,隔n个元素就插入1个值,首尾不会出现分割符 * @remarks { "123456789", ',', 3} -> 123,456,789 */ template T r_insert_per_num(const T& container, V v, size_t per_num) { if (container.size() <= per_num) return T(container); size_t num = (container.size() - 1) / per_num;//每3个插入计算得出:9 -> 2; 11 -> 3 T ret; ret.resize(num + container.size()); size_t i = 0; auto iter = container.rbegin(); auto iter_ret = ret.rbegin(); while (iter != container.rend()) { *iter_ret++ = *iter++; ++i; //满per_num额外加入一个v,且不为最后一个 if (i % per_num == 0 && i < container.size()) *iter_ret++ = v; } return ret; } /** * @brief 以 元素 分割 容器 * @param[in] container 容器 * @param[in] delimiter 分割符 * @param[out] ret 返回分割之后的 * * @note 空容器返回空,其余返回数量必定为分割符数量+1 * * @remarks {} -> {} * @remarks {1} -> {1} * @remarks {1,2,2,5,} -> {1 2 2 5 0} * @remarks {,1,2,2,5} -> {0 1 2 2 5} * @remarks {,,1,,,2,2,5} -> {0 0 1 0 0 2 2 5} */ template void split(const T& container, V delimiter, std::vector& ret) { if (container.empty()) return; //主迭代器位置 auto iter_begin = container.begin(); while (true) { //当前位置就是分隔符,则添加 空元素 if (*iter_begin == delimiter) { ret.push_back(T()); if (++iter_begin == container.end()) { ret.push_back(T());//还要额外添加一个 return; } } else { //分隔符位置 auto iter_find = std::find(iter_begin, container.end(), delimiter); if (iter_find == container.end()) {//分隔符 未找到(说明字符串读完了,最后没有分隔符的情况) ret.push_back(T(iter_begin, container.end())); return; } else { ret.push_back(T(iter_begin, iter_find)); iter_begin = iter_find + 1; if (iter_begin == container.end()) { ret.push_back(T(iter_begin, container.end())); return; } } } } } /** * @brief 以 元素 分割 容器 * @param[in] container 容器 * @param[in] delimiter 分割符 * @param[out] ret 返回分割之后的 * * @note 不会构造空元素 * * @remarks {1,2,2,5,} -> {1 2 2 5} * @remarks {,1,2,2,5} -> {1 2 2 5} * @remarks {,,1,,,2,2,5} -> {1 2 2 5} */ template void split_no_empty(const T& container, V delimiter, std::vector& ret) { if (container.empty()) return; //主迭代器位置 auto iter_begin = container.begin(); while (true) { //当前位置就是分隔符,不添加 空元素,只往后移动 if (*iter_begin == delimiter) { if (++iter_begin == container.end()) return; } else { //分隔符位置 auto iter_find = std::find(iter_begin, container.end(), delimiter); if (iter_find == container.end()) {//分隔符 未找到(说明字符串读完了,最后没有分隔符的情况) ret.push_back(T(iter_begin, container.end())); return; } else { ret.push_back(T(iter_begin, iter_find)); iter_begin = iter_find + 1; if (iter_begin == container.end()) return; } } } } /** * @brief 以 子串 分割 容器 * @param[in] container 容器 * @param[in] delimiter 分割符 * @param[out] ret 返回分割之后的 * * * @remarks "xxABCxxABCxxABC",xx" -> {"", "ABC", "ABC", "ABC"} */ template void split_sub(const T& container, const T& delimiter, std::vector& ret) { if (container.empty()) return; assert(!delimiter.empty()); auto iter_pre = container.begin(); auto iter_d = delimiter.begin(); bool mode_d = false;//是否匹配分隔符中 auto iter_cur = iter_pre; auto iter_cat = iter_pre;//开始匹配分隔符的位置 while (true) { if (!mode_d) {//正常模式 if (iter_cur == container.end()) { ret.push_back(T(iter_pre, iter_cur)); return; } if (*iter_cur == *iter_d) { // 匹配到分隔符首个,进入匹配模式 mode_d = true; iter_cat = iter_cur; ++iter_cur; ++iter_d; continue; } else { ++iter_cur; } } else {//匹配模式 if (iter_d == delimiter.end()) {//完全匹配分隔符 ret.push_back(T(iter_pre, iter_cat)); mode_d = false; iter_d = delimiter.begin(); iter_pre = iter_cur; continue; } if (iter_cur == container.end()) {//字符结束,未完全匹配 ret.push_back(T(iter_pre, iter_cur)); return; } if (*iter_cur == *iter_d) {//当前匹配 ++iter_cur; ++iter_d; continue; } else {//不匹配,进入普通模式 mode_d = false; iter_d = delimiter.begin(); continue; } } } } /** * @brief 生成序列 * @param[in] container 容器 * @note 前闭后开区间 */ template void make_sequence(T& c, const std::initializer_list>& vec) { for (auto& iter : vec) { assert(iter.size() == 2); V f = *iter.begin(); const V& b = *(iter.begin() + 1); assert(f < b); while (f < b) { c.push_back(f++); } } } /** * @brief 成对遍历 * @param[in] container 容器 * @param[in] func 操作函数 * @param[in] ring 为真时,末尾元素 与 首元素成对再操作一次 * * @note ring为真时,1个元素操作{0, 0},2个元素操作{0, 1}, {1, 0} */ template void for_couple(const C& container, F func, bool ring = false) { if (container.empty()) { return; } auto iter_pre = std::begin(container); auto iter_cur = std::next(iter_pre); for (; iter_cur != std::end(container);) { func(*iter_pre, *iter_cur); ++iter_pre; ++iter_cur; } if (ring) func(*iter_pre, *std::begin(container)); } /** * @brief 反向成对遍历 * @note 参考for_couple */ template void for_couple_r(const C& container, F func, bool ring = false) { if (container.empty()) { return; } auto iter_pre = std::rbegin(container); auto iter_cur = std::next(iter_pre); for (; iter_cur != std::rend(container);) { func(*iter_pre, *iter_cur); ++iter_pre; ++iter_cur; } if (ring) func(*iter_pre, *std::rbegin(container)); } /** * @brief 遍历树(使用栈,深度优先) * @param[in] root 根节点 * @param[in] func_child 获取子节点函数 * @param[in] func 操作节点函数 * * @note 注意T为指针类型。可以尝试使用NTree类 */ template void for_tree(T root, FC func_child, F func) { std::stack s; s.push(root); while (!s.empty()) { T node_this = s.top(); s.pop(); func(node_this); //反向添加,这样左子树先遍历 using C = decltype(func_child(node_this)); C c = func_child(node_this); for (auto iter = c->rbegin(); iter != c->rend(); ++iter) { T& node = *iter; s.push(node); } } } /** * @brief RAII清理操作 */ template class finally { public: finally(F&& func) : _func(func) {} ~finally() { _func(); } private: F _func; }; /** * @brief 返回静态数组长度 * @note 使用std::size,类似C::a时才需使用自己 */ /*template [[deprecated]] constexpr size_t arr_size(const T(&)[N]) { return N; }*/ /** * @brief 返回数组最后一个元素 */ template constexpr T& arr_last(const T(&arr)[N]) { return arr[N - 1]; } /** * @brief 返回符号,正数返回1、负数返回-1、0返回0 */ template constexpr T sign(const T& v) { if (v > 0) return 1; else if (v < 0) return -1; else return 0; } /** * @brief 固定条件的字符串,生成唯一id * @param[in] str 字符数组 * * @note 最多10个字符,可包含 字母、数字、下划线、点 * @note 与base64一致,下划线替换+,点替换/ */ template consteval uint64_t str_uid(const char(&str)[N]) { //64 / 6 = 10 再加1结束符 static_assert(N > 0 && N <= 11, "字符串长度过长!"); uint64_t ret = 0; for (size_t i = 0; i < N - 1; ++i) { char ch = str[i]; if (ch >= 48 && ch <= 57) ch += 6;//0-9 else if (ch >= 65 && ch <= 90) ch -= 65;//A-Z else if (ch >= 97 && ch <= 122) ch -= 71;//a-z else if (ch == 95) ch = 62; else if (ch == 46) ch = 63; else assert(0 && "只能是字母、数字、下划线、点!"); ret |= ((uint64_t)ch << (i * 6)); } return ret; } }