//
// Created by 罗炳国 on 2022/6/8.
//

#ifndef COMMONHEADERS_H
#define COMMONHEADERS_H

#include <iostream>
#include <vector>
#include <string>
#include <limits.h>
#include <cmath>
#include <string.h>
#include <map>
#include <algorithm>
#include <map>
#include <list>
#include <queue>
#include <set>
#include <cstdlib>
#include <ctime>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <stdlib.h>
#include <random>
#include <stdio.h>
#include <chrono>

using namespace std;

void vec2DShow(vector<vector<int>>& arr)
{
    std::cout << "********** vecshow begin ********" << std::endl;
    for(int i = 0; i < arr.size(); i++)
    {
        for(int j = 0; j < arr[0].size(); j++)
        {
            std::cout << arr[i][j] << " ";
        }
        std::cout << std::endl;
    }
    std::cout << "********** vecshow end ********" << std::endl;
}

typedef struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
}TreeNode;

//关于值的一个wrapper
template <typename T>
class VNode {
public:
    T value;
    //标识当前节点是否为不可用信息
    bool isInvalid{true};
    bool operator < (const VNode<T>& obj) const
    {
        return this->value < obj.value;
    }
    bool operator ==(const VNode<T>& obj) const
    {
        return (this->value == obj.value) || (this->isInvalid && obj.isInvalid);
    }
    bool operator !=(const VNode<T>& obj) const
    {
        return !((this->value == obj.value) || (this->isInvalid && obj.isInvalid));
    }
};

//普通单链表结点
typedef struct _listNode
{
    int val{0};
    struct _listNode* next{nullptr};
    _listNode() {}
    _listNode(int x = 0, struct _listNode* pnext = nullptr) : val(x), next(pnext)
    {

    }
} ListNode;


//带随机指针的链表结点
typedef struct RandomListNode {
    int val{0};
    struct _RandomListNode* next;
    struct _RandomListNode* randPtr;
}RandomListNode;


//带指向父节点指针的二叉树
typedef struct _binaryTreeNode{
    int value;
    _binaryTreeNode* pLeft{nullptr};
    _binaryTreeNode* pRight{nullptr};
    _binaryTreeNode* pParent{nullptr};//指向父节点的指针
}binaryTreeNode;

/**
 * 获得[a, b]范围区间内的随机整数
 * 要取得[0,n)  就是rand（）%n     表示 从0到n-1的数
 * 要取得[a,b)的随机整数，使用(rand() % (b-a))+ a;
 * 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a;
 * 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1;
 * 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。
 * 要取得a到b之间的随机整数，另一种表示：a + (int)b * rand() / (RAND_MAX + 1)。
 * 要取得0～1之间的浮点数，可以使用rand() / double(RAND_MAX)。
 *
*/
int getRand(int a, int b)
{
    static bool bFirst = true;
    if(bFirst)
    {
        srand((int)time(0));
        bFirst = false;
    }
    int min = a < b ? a : b;
    int max = min == a ? b : a;
    return (rand() % (max - min + 1)) + min;
}

bool isArrayEqual(vector<int> & arr1, vector<int>& arr2)
{
    bool bRet = true;
    if(&arr1 == &arr2)
    {
        return bRet;
    }
    if(arr1.size() != arr2.size())
    {
        bRet = false;
        return bRet;
    }
    for(size_t i = 0; i < arr1.size(); i++)
    {
        if(arr1[i] != arr2[i])
            return false;
    }
    return bRet;
}

vector<int>& getRandomArray(vector<int>& arr, int ilength, int min = INT32_MIN/2, int max = INT32_MAX/2)
{
    if(ilength <= 0) return arr;
    arr.clear();
    arr.reserve(ilength);
    for(int i = 0; i < ilength; i++)
    {
        arr.push_back(getRand(min, max));
    }
    return arr;
}

vector<int>& getUnMultRandomArray(vector<int>& arr, int ilength, int min = INT32_MIN, int max = INT32_MAX)
{
    arr.clear();
    arr.reserve(ilength);
    unordered_set<int> used;
    int val = 0;
    for(int i = 0; i < ilength; )
    {
        val = getRand(min, max);
        if(used.find(val) == used.end())
        {
            arr.push_back(val);
            used.insert(val);
            i++;
        }
    }
    return arr;
}

void vec2DInit(vector<vector<int>>& vec2D, int row, int col, int val)
{
    for(int i = 0; i < row; i++)
    {
        vector<int> iVec;
        for(int j = 0; j < col; j++)
        {
            iVec.push_back(val);
        }
        vec2D.push_back(iVec);
    }
}

void vec3DInit(vector<vector<vector<int>>>& vec3D, int row, int col, int height, int val)
{
    for(int i = 0; i < row; i++){
        vector<vector<int>> v2d;
        for(int j = 0; j < col; j++){
            vector<int> tvec;
            for(int k = 0; k < height; k++){
                tvec.push_back(val);
            }
            v2d.push_back(tvec);
        }
        vec3D.push_back(v2d);
    }
}

void vecShow(vector<int>& arr)
{
    std::cout<< "*****vecshow begin*****" << std::endl;
    for(int i = 0; i < arr.size(); i++)
    {
        std::cout << arr[i] << ", ";
    }
    std::cout<< std::endl << "*****vecshow end*****" << std::endl;
}

void vecShow(vector<string>& arr)
{
    std::cout<< "*****vecshow begin*****" << std::endl;
    for(int i = 0; i < arr.size(); i++)
    {
        std::cout << arr[i] << std::endl;
    }
    std::cout<< std::endl << "*****vecshow end*****" << std::endl;
}

template <typename T>
void containerShow(T &con) {
    auto iter = con.begin();
    std::cout<< "*****show begin*****" << std::endl;
    while (iter != con.end()) {
        std::cout << *iter << std::endl;
        iter++;
    }
    std::cout<< std::endl << "*****show end*****" << std::endl;
}

void vecSwap(vector<int>& arr, int left, int right)
{
    if(left == right || left < 0 || right < 0 ||
       left >= arr.size() || right >= arr.size())
    {
        return;
    }
    int tmp = arr[left];
    arr[left] = arr[right];
    arr[right] = tmp;
}

string generateString(int len) {
    string ret;
    for (int i = 0; i < len; i++) {
        int a = getRand(0, 25);
        ret += 'a' + a;
    }
    return ret;
}

TreeNode *generateBinaryTree() {
    TreeNode *root = new TreeNode(getRand(1, 100)), *cursor;

    // 树的深度
    int treeDeep = getRand(2, 5);

    // 几轮赋值
    int loop = getRand(1, 7);

    for (int i = 0; i < loop; i++) {
        int t = treeDeep, val;
        cursor = root;

        while(t-- > 0) {
            val = getRand(0, 2);
            switch (val) {
                case 0:
                    goto tag_loop;
                case 1:
                    if (cursor->left == nullptr)
                        cursor->left = new TreeNode(getRand(1, 100));
                    cursor = cursor->left;
                    break;
                case 2:
                    if (cursor->right == nullptr)
                        cursor->right = new TreeNode(getRand(1, 100));
                    cursor = cursor->right;
                    break;
            }
        }
    tag_loop:
        ;
    }

    return root;
}



#endif // COMMONHEADERS_H