696 lines
13 KiB
C++
696 lines
13 KiB
C++
/**
|
||
* @file dl_algorithm.h
|
||
* @brief 算法
|
||
*
|
||
*
|
||
* @version 1.0
|
||
* @author lveyou
|
||
* @date 23-06-22
|
||
*
|
||
* @note 不得包含dl_range.h
|
||
*/
|
||
#pragma once
|
||
|
||
#include <algorithm>
|
||
#include <cassert>
|
||
#include <stack>
|
||
#include <array>
|
||
#include <vector>
|
||
#include <cstdint>
|
||
|
||
|
||
#include "base/dl_concept.h"
|
||
#include "base/dl_array.h"
|
||
|
||
namespace dl
|
||
{
|
||
|
||
/**
|
||
* @brief 限制数值到 [a, b]
|
||
*/
|
||
template<typename T>
|
||
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<typename T>
|
||
constexpr T saturate(const T& x)
|
||
{
|
||
#if DL_PLATFORM == DL_PLATFORM_LINUX
|
||
return dl::clamp<T>(x, 0, 1);
|
||
#else
|
||
return std::clamp<T>(x, 0, 1);
|
||
#endif
|
||
}
|
||
|
||
/**
|
||
* @brief 是否数值在[0, 1]
|
||
*/
|
||
template<typename T>
|
||
constexpr T is_saturate(const T& x)
|
||
{
|
||
return x >= 0 && x <= 1;
|
||
}
|
||
|
||
/**
|
||
* @brief 向量叉乘
|
||
*/
|
||
template<typename T>
|
||
constexpr Array<T, 3> cross(const Array<T, 3>& a, const Array<T, 3>& 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<typename T>
|
||
[[deprecated]]
|
||
inline T cast_dynamic(void* p)
|
||
{
|
||
return dynamic_cast<T>(p);
|
||
}
|
||
|
||
|
||
/**
|
||
* @brief 限制到大于某个值，如果修改了原值则返回true
|
||
*/
|
||
template<typename T, size_t N>
|
||
bool limit_bigger(Array<T, N>& a, const Array<T, N>& 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 <typename T>
|
||
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<typename T, typename V>
|
||
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<PopFrontAble C, typename F>
|
||
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<typename T, typename V>
|
||
// 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<typename T, typename V>
|
||
// array<size_t, 2> Index(const vector<vector<T>>& container, const V& v)
|
||
// {
|
||
// array<size_t, 2> 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<typename T>
|
||
inline T* pointer(T&& x)
|
||
{
|
||
return &x;
|
||
}
|
||
|
||
/**
|
||
* @brief 加上const修饰
|
||
*/
|
||
template<typename T>
|
||
inline const T& constant(T& v)
|
||
{
|
||
return v;
|
||
}
|
||
|
||
|
||
|
||
/**
|
||
* @brief 替换容器元素值
|
||
*/
|
||
//template<typename T, typename V>
|
||
//inline void replace(T& vec, V v, V v_new)
|
||
//{
|
||
// for (auto& iter : vec)
|
||
// {
|
||
// if (iter == v)
|
||
// iter = v_new;
|
||
// }
|
||
//}
|
||
|
||
/**
|
||
* @brief 返回 重复元素位置，没有返回end
|
||
*/
|
||
template<typename C>
|
||
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<typename T, typename V>
|
||
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<typename T, typename V>
|
||
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<typename T, typename V>
|
||
void split(const T& container, V delimiter, std::vector<T>& 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<typename T, typename V>
|
||
void split_no_empty(const T& container, V delimiter, std::vector<T>& 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<typename T>
|
||
void split_sub(const T& container, const T& delimiter, std::vector<T>& 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<typename T, typename V>
|
||
void make_sequence(T& c, const std::initializer_list<std::initializer_list<V>>& 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<typename C, typename F>
|
||
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<typename C, typename F>
|
||
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<IsPointer T, typename FC, typename F>
|
||
void for_tree(T root, FC func_child, F func)
|
||
{
|
||
std::stack<T> 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<typename F>
|
||
class finally
|
||
{
|
||
public:
|
||
finally(F&& func) : _func(func) {}
|
||
~finally() { _func(); }
|
||
private:
|
||
F _func;
|
||
};
|
||
|
||
/**
|
||
* @brief 返回静态数组长度
|
||
* @note 使用std::size，类似C::a时才需使用自己
|
||
*/
|
||
/*template<typename T, size_t N>
|
||
[[deprecated]]
|
||
constexpr size_t arr_size(const T(&)[N])
|
||
{
|
||
return N;
|
||
}*/
|
||
|
||
|
||
/**
|
||
* @brief 返回数组最后一个元素
|
||
*/
|
||
template<typename T, size_t N>
|
||
constexpr T& arr_last(const T(&arr)[N])
|
||
{
|
||
return arr[N - 1];
|
||
}
|
||
|
||
/**
|
||
* @brief 返回符号，正数返回1、负数返回-1、0返回0
|
||
*/
|
||
template<IsSigned T>
|
||
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<size_t N>
|
||
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;
|
||
}
|
||
}
|