Wjr Z AlgorithmAndDataStructure Save Abandoned

主要用于学习C++的相关知识，例如if else的分治预测，右值引用和左值引用，参数包，初始化列表，迭代器，封装，运算符重载，效率优化和测试等等。代码在VS上可以很好地运行，在其他的环境则不能保证，可以尝试在math_func.h注释掉

#define TEST

bint.h、bint.cpp

现有较为完善的大整数类，支持10进制和2进制两种，可通过中括号访问每一位，并且封装了vector进行动态扩展（超过现有长度自动扩展），可以直接使用int或者long long赋值等等，乘法使用了暴力、Karatsuba、TOOM-COOK、FFT，但Karatsuba和TOOM-COOK只进行了学习，并保留但未使用。除法暂时只用了我自己想到的两种分治除法和knuth除法。实现了大整数随机数，大整数随机质数，二进制和十进制的快速转化（分治）。

upd 2021.8.18 : 修复pollard-rho以及高精度和低精度比较的部分bug，现在pollard-rho可以很快跑出绝大部分10^30以内的数，支持int、long long 和大整数。

upd 2021.10.6:大数除法优化（暂未使用牛顿迭代，因其常数过大），十进制和二进制转化使用unordered_map进行优化，对中见结果进行了存储

常用运算符：+（单目/双目）、- (单目/双目)、* 、/ 等，二进制有 ^ 、| 、& 等，基本能像int那样用。

只能显示构造！
正确的初始化：
bint a(7);
bint a("124");
bint a(1),b(a),c(a,false);
bint a("-123");
...
错误的初始化：
bint a=7;
bint a="124";
bint a="-123";
...
    
赋值和int基本类似

toint() :转化为int
toll() :转化为long long
tostr() :转换为字符串,bint2默认转为十进制，tostr(2)即转为二进制串

length() :数字长度，不包括符号
relength() :改变长度，不足补0
[]: 十进制/二进制下的第几位的数字
at()、save_at() :压位后第几位的数字(bint8个十进制位为一位，bint2 32个二进制位为一位)

is_prime() : 判断是否是素数，10^100大致需要0~0.5ms ,10^1000大约100ms
rand_prime(int l) : 生成长度为l的随机大素数（暂未进行更多的算法优化），生成10^300的素数约100~2000ms
pollard_rho(bint x) : 素数分解，使用的pollard_rho算法
randbint(int l) : 生成随机数
randbint2(int l)
...

math_func.h、math_func.cpp

只实现了一些简单函数

log(log n)的向下取整 log2和log10，思想很好理解。

mtool.h、mtool.cpp

template<typename... _Type>
class in_type;//用于判断第一个参数是否在后面的参数列表中，如果在value为true
//例如：
in_type<int,int,double>::value //true
in_type<int,double,float>::value //false

template<typename _Type1, typename _Type2, typename... _Res>
class out_type;//判断是否不在后面的参数列表中，若不在则value为false

timereference Time();//获取当前时间，精度更高
double operator-(const timereference& lhs, const timereference& rhs);//两个时间的间隔，单位为毫秒

//例子：
auto start=Time();
...//待测函数
auto end=Time();
cout<<end-start<<endl;

template<typename Fn>
double qtime(const Fn& ToBeTest)//返回无参数函数运行一次的耗时

template<typename Fn, typename... Args>
double qtime(const Fn& ToBeTest, Args&&...List)//返回带参函数运行一次的耗时

template<typename Fn>
double qavltime(const Fn& ToBeTest, int kth)//返回无参函数运行k次的平均耗时

template<typename Fn, typename... Args>
double qavltime(const Fn& ToBeTest, int kth, Args&&...List)//返回带参函数运行k次的平均耗时

template<typename Fn>
double qcounttime(const Fn& ToBeTest, int kth)//返回无参函数运行k次的总耗时

template<typename Fn, typename... Args>
double qcounttime(const Fn& ToBeTest, int kth, Args&&...List)//返回带参函数运行k次的总耗时
    
//例子：
void print(int x){
    cout<<x<<endl;
}
cout<<qtime(print,3)<<endl;
cout<<qtime(
	[](int&x){
        cout<<x<<endl;
    },3
)<<endl;

//其余的基本同理，只是多了一个k参数

template<typename Ty>
bool check(Ty* arr1,Ty*arr2,int n)//比较前n个元素是否相同

template<typename Ty,typename... Args>
bool check(const Ty&head,const Ty&nxt,Args ...toBeTest)//比较所有参数是否相同（同类型）

template<typename Ty>
void qswap(Ty* Start, Ty* End, int* rev)
//设数组为a,让所有的a[i]=a[rev[i]]
//进行了内存优化，使用了自己的bint2即二进制大整数，之后也许会单独写一个动态长度bitset
//只使用了sizeof(int)*(n/8)的内存，并且避免了拷贝，主要思想是进行若干个环形移动

//例子：

int aa[3]={6,3,7};
qswap(aa, aa + 3, { 1,0,2 });
cout<<aa[0]<<endl<<aa[1]<<endl<<aa[2]<<endl;

void bucketsort(uint32_t* Start, uint32_t* End);
//unsigned int桶排序
//设n为元素个数
//n<=500时为sort。
//500<n<=32768时为桶的个数为256的桶排序。
//32768<n时为桶的个数为65536的桶排序。
//当数据范围很大时，并且数据接近随机时快于sort 2~4倍。

std::vector<std::string> getFiles(const std::string& path);
//获取一个文件夹下的所有文件路径，如果该路径是文件，则只获取该路径
//若路径不合法，则返回空的vector

std::string readFiles(const std::string&filename);
void writeFiles(const std::string&filename,const std::string&str);
//简单封装，读取文件全部内容，返回string

std::string includeTree(const std::string&filename);
//文件include 树
//无法根据宏判断是否include

lz77.h、lz77.cpp

自己实现的lz77算法

接口非常简单，具体见代码

#define LZLEVEL 2 //2:体积最小,1：速度最快

string_tool.h、string_tool.cpp

string相关的工具类

class find_tool;//使用最坏复杂度O(n)的方式进行搜索，同时在平均情况下用时良好
find_init //用于初始化pattern串
find // 匹配

CTimer.h、CTimer.cpp

定时器

暂支持毫秒级定时，三种定时模式

设等待时间为delta

• normal模式：每次执行完任务后等待delta
• accurate模式：每delta秒执行任务，若任务时长长于delta，则最少间隔5ms
• thread模式：每delta秒执行任务，但每个任务单独启动一个线程，限制最多同时threads线程

mjson.h、mjson.cpp

json序列化和反序列化

暂时有 jsonValue 、jsonReader

前者解析时将Object存入unordered_map，Array存入vector，解析较慢，但数据范围较大时查询快

后者全部使用链表存储，解析较快，但数据范围较大时查询慢

jsonValue使用比较简单

thread_pool.h、thread_pool.cpp

线程池

本来是自己写了一个线程池的，但是看到star第一的ThreadPool后深感自己有多菜...

源仓库ThreadPool/ThreadPool.h at master · progschj/ThreadPool (github.com)

fraction.h

分数类

保证分子和分母始终互质，为最简形式

读入时若有分数符号，则需要紧挨分子

template<typename T>
class fraction; //T为分子和分母类型，只能是int,long long,bint

fraction<int> a(3);//3/1
fraction<int> a(3,2);//3/2
fraction<int> a(6,8);//3/4
//支持四则运算，赋值，复制，比较，输入，输出
//输出时若分母为1，则只输出分子

matrix.h

矩阵类

暂未使用vector<vector<T>> ，因此避免频繁的增大矩阵大小

template<typename T>
class matrix;

matrix<int> a="[1,3,2;0,4]";
matrix<int> a="1,3,2;0,4";
matrix<int> a=" 1 3 2 ; 0 4 ";
//以上赋值等价，使用分号代表换行，同一行不同数字见用非数字，非负号隔开即可
//读入字符串会从第一个负号/数字开始读入第一个数字，因此不能出现单独的负号（属于不合法）

//支持加、减、乘法（暂未未使用算法优化）、高斯消元、求逆元

//高斯消元
typedef fraction<int> fr;
matrix<fr>a,b;
a="[11/12,-1/4,-1/6;-1/4,3/2,-1;-1/6,-1,31/24]";
b="[6;2;-2]";
int g=Gauss(a,b);
cout<<b;
//得到答案 [2152/251;1280/251;880/251]

//矩阵求逆元，不合法时可能有问题
inv(const mat&)

var.h

可以存储任意类型

基本类型 及其 varType
bool               0
int                1
unsigned int       2
long long          3
unsigned long long 4
float              5
double             6
char               7
UndefinedType      31

其余varType需要自行注册，否则默认为31（UndefinedType)

REGISTER_VARTYPE(TYPE,VALUE) (VALUE为[8,30]且互不相同)

可用任意类型构造

var x(3);
var x(4.0);
var x("wjr"); //默认类型为char [4]而不是const char*
var x(string());
var x(list<int>());
...

type(); //返回type_info
Type(); //返回varType(constexpr), 数组类型如 T[Size] 的 Type = Type(T) | (Size<<8) 
value<T>(); //返回值

geometry.h

计算几何类

待icpc退役后实现

String.h

学习facebook的fbString实现的

能力和精力有限，未实现COW等

Deque.h

于2021.8.29进行了大幅重构

与vector不同之处在于在头部也预留了部分空间，头尾预留相同大小的空间

练手用的

splay.h

splay的封装，可以通过洛谷上的平衡树题，但暂且接口易用性不高，以后也许可能会进行简化。

平衡树，动态插入节点或者区间，自定义区间维护，区间翻转等。

upd 2021.10.6 : 不太完善，接口不宜用，练手用的

Allocator.h

网上找到的内存池类。