template <typename VST> void traverse(VST visit);
// template <typename VST> virtual void traverse(VST visit, T* e);
template <typename VST> void traverse(VST visit, T* e);

// 单个T类型元素加1的类
template <typename T>
struct Increase {
  virtual void operator()(T &e) {e++;}    // Increase<T>()实现函数功能  
};

struct Base {    // 声明virtual后, 可被继承类override重载
  virtual void print() {std::cout << "Base\n";}
};

struct Derived : Base {   // 'override'可写可不写
  void print() override {std::cout << "Derived\n";}
};

struct Base {
  void print() {std::cout << "Base\n";}
};

struct Derived : Base {
  void print() {std::cout << "Derived\n";}
};

// 注释是使用virtual结果
  Base b;
  Derived d;

  Base& br = b;      // refer b, br的类型是Base&
  Base& dr = d;      // dr类型也是Base&
  br.print();        // Base
  dr.print();        // Derived

  Base* pb = &b;     // pointer to b, Base*
  Base* pd = &d;     // Base* as well

  pb->print();       // Base
  pd->print();       // Derived

  b.Base::print();   // Base
  d.Base::print();   // Base

// 函数对象用virtual声明operator()()
struct Increase {
  // 重载()后, 对象可充当函数的功能
  virtual void operator()(int* e) {(*e)++;}
};

struct Increase_two : Increase {
  void operator()(int* e) override {(*e)+= 2;}    // 元素+2;
};

void f_increase() {
  Increase a;
  Increase_two b;

  Increase& ra = a;
  Increase& rb = b;     // rb的类型为 Increase&

  int e = 5; int* pe = &e;
  ra.operator()(pe);
  std::cout << "e = " << e << std::endl;    // prints "e = 6"
  int e2 = 5; int* pe2 = &e2;
  rb.operator()(pe2);   // 调用基类的引用时, 动态绑定到Increase_two中的方法
  std::cout << "e2 = " << e2 << std::endl;  // prints "e2 = 7"
}

void f0() {     // ERROR: 先存放再输入不会修改数组中的数据
  int a, b;
  int iarr[2] = {a, b};
  std::cin >> a >> b;   // 不合理:先存放, 再输入
  std::cout << iarr[0] << ' ' << iarr[1] << std::endl;
  // 4197661 0
}

void f1() {
  int iarr[2] = {};
  std::cin >> iarr[0] >> iarr[1];     // 直接输入到数组中
}

void f2() {
  int a, b;
  std::cin >> a >> b;     // 先输入, 再存放
  int iarr[2] = {a, b};
}

void f3() {  // BUG: 为什么不能通过数组中保存的指针修改数组??
  int *pa, *pb;
  int* iarr[2] = {pa, pb};
  int tmp_a, tmp_b;
  std::cin >> tmp_a >> tmp_b;        // 存放到临时变量
  pa = &tmp_a; pb = &tmp_b;
  std::cout << "*pa = " << *pa << std::endl;    // *pa = 1
  std::cout << *(*iarr) << std::endl;
  std::cout << *(iarr[0]) << ' ' << *(iarr[1]) << std::endl;
}

void revise_value_int(int* arr, int n) {
  // 索引为n指向的整数递增1
  (*(arr+n)) += 1;
}

void call_revise() {
  int iarr[] = {0, 1, 2};
  revise_value_int(iarr, 2);
  std::cout << "iarr[2] = " << iarr[2] << std::endl;
}

call_revise();

int* pa, *pb, *pc;
int ptrArr[] = {pa, pb, pc};

int* pa, *pb, *pc;
int* ptrArr[] = {pa, pb, pc};

void revise_value_ptr(int** ptrArr, int n) {
  // 索引为n的指向的指针所指向的整数递增1
  (**(ptrArr+n))+=1;
}

int* pa, *pb, *pc;
int* ptrArr[] = {pa, pb, pc};

void call_revise() {
  int a = 1, b = 2, c = 3;
  int* pa = &a, *pb = &b, *pc = &c;
  int* ptrArr[] = {pa, pb, pc};
  another_revise_value_ptr(ptrArr, 2);
  std::cout << "**(ptrArr)   = " << **(ptrArr)   << '\n'
            << "**(ptrArr+1) = " << **(ptrArr+1) << '\n'
            << "**(ptrArr+2) = " << **(ptrArr+2) << std::endl;
}

call_revise()

void f4() {     // DEBUG: 先存放再输入不会修改数组中的数据
  int a, b;
  int* pa = &a, int* pb = &b;     // 注意: 不要定义空指针
  int* iarr[2] = {pa, pb};        // 注意数组的类型是数组中元素的类型
  std::cin >> a >> b;   // 也能合理:先存放, 再输入
  std::cout << **iarr << ' ' << **(iarr+1) << std::endl; // 解引用
  // 4197661 0
}

int* pa;

int *pa = &a;

int* iarr[2] = {pa, pb};        // 类型为 int*

int* iarr[2] = {pa, pb};        // 如果数组这样定义
iarr;                           // iarr是指向数组首个元素的指针
*iarr;                          // 因为pa是指针, 所以解引用数组头指针, 得到pa地址
**iarr;                         // 再次解引用得到pa指向的int

template <typename T>
class Name {
  char* _c; int _length; int _capacity;
 public:
  Name(char* c, int length): _c(c), _length(length) {}
  char* getName() const;
  int getLength() const;
};

template <typename T>
char* Name<T>::getName() const {
  return _c;
}

template <typename T>
int Name<T>::getLength() const {
  return _length;
}



void class_array() {
  char c1[] = {'t', 'i', 'm'};
  char c2[] = {'h', 'u'};
  int length1 = 3, length2 = 2;
  Name<int> name1(c1, length1), name2(c2, length2);
  Name<int> nArr[] = {name1, name2};
  int size = 2;
  print_instance_data_in_array(nArr, size);
}

void f() {
  char c[] = {'t', 'i', 'm'};
  int length = 3;
  Name<int> n(c, length);
}

void print_instance_data_in_array(Name<int>* nArr, int size) {
  for (int i = 0; i < size; i++) {
    std::cout << "Name = ";
    for (int j = 0; j < nArr[i].getLength(); j++) {
      std::cout << *((nArr[i].getName())+j);
    }
    std::cout << "\n";
  }
}

void f_array() {
  int a = 3, b = 5, c = 7;
  int* pa = &a, *pb = &b, *pc = &c;
  int _size_pa = 1, _size_pb = 1, _size_pc = 1;
  int* pArr1[] = {pa};    // pArr1数组存放pa, pb指针
  int _size_pArr1 = 1;
  int* pArr2[] = {pa, pb, pc};    // pArr2数组存放pa, pb, pc指针
  int _size_pArr2 = 3;
  int* pArr3[] = {pa, pc};
  int _size_pArr3 = 2;
  int size_pArr[] = {1, 3, 2};
  int** ppArr[] = {pArr1, pArr2, pArr3};   // ppArr存放3个指针数组
  int _size_ppArr = 3;
  int size_ppArr[] = {3};
  int* size_arr[] = {size_ppArr, size_pArr};
  // convert_size_structor(size_arr);
  print_arr_b(ppArr);
}

void print_arr_b(int*** ppArr) {
  // 解引用并打印ppArr数组中依次数组中的pa, pb, pc
  std::cout << "a0 = " << ***ppArr<< " in pArr1[0]" << '\n'
            << "b0 = " << **(*(ppArr+1)+1)<< " in pArr2[1]" << '\n'
            << "c0 = " << **(*(ppArr+2)+1)<< " in pArr3[1]" << '\n'
            << std::endl;
}

class MyClass {
  int x = 0;
 public:
  int c = 5;
  MyClass(int v) :x(v) {}
  const int& get() const {return x;}   // 常量成员函数在是否为常量上可以重载
  int& get() {return --x;}
};

//..
int a = 5
const int& get() const {return --a;}    // 错误：改变a的值,

template <typename T>
class mycontainer {
  T element;
 public:
  mycontainer(const T e) : element(e) {}
  T increase() {return ++element;}    // 递增element
  T getElement() const {return element;}   // 返回element数据
};

template <>
class mycontainer<char> {
  char element;
 public:
  mycontainer(const char e): element(e) {}
  char increase() {return ++element;}    // 递增char
  char getElement() const {return element;}   // 返回element数据
  char uppercase() {
    if (element <= 'z' && element >= 'a') {   // 是小写字母
      element += 'A' - 'a'; return element;
    }  // 返回元素
    std::cout << "element " << element << "is not lower" << std::endl;
    return element;
  }
};

template <typename T> class mycontainer {...}
template <> class mycontainer<char> {...}

template <typename T>
void Vector<T>::shrunk() {
  if (_size > (_capacity/2)) return;   // 规模大于1/2不必缩容
  _capacity = std::max(_capacity, DEAFAULT_CAPACITY);
  // 储存一份旧元素, 创建新的数据空间
  T* old_elem = _elem; _elem = new T[_capacity >>= 1];
  for (Rank r = 0; r < _size; r++) {
    _elem[r] = old_elem[r];
  }
  // 删除旧元素的内存空间
  delete [] old_elem;
}

void copyFrom(T* tarr, int lo, int hi) {
    _elem = new T[_capacity = 2*(hi - lo)];
    _size = hi - lo;
    std::cout << "*tarr = " << tarr[1] << std::endl;
    std::cout << "*_elem = " << *_elem << std::endl;
    // for (int i = 0; i < _size; i++) {*(_elem+i) = tarr[i];}
  }

void copyFrom(T* tarr, int lo, int hi) {
    
    _size = hi - lo;
    std::cout << "*tarr = " << tarr[1] << std::endl;
    std::cout << "*_elem = " << *_elem << std::endl;
    // for (int i = 0; i < _size; i++) {*(_elem+i) = tarr[i];}
  }

void f() {
  std::cout << "---- test in same if statement----" << std::endl;
  int i = 1;
  int arr[] = {0, 1, 2, 3, 4};
  // 在同if, for, while中, 对某一变量i后置递增, i前后不变
  if (equal(i++, arr[i])) std::cout << "equal\n"
                                    << "now i = " << i << std::endl;
}

template <typename T>
T& Vector<T>::operator--() {          // 重载前置--操作符
  for (int i = 0; i < _size; i++)
    _elem[i]--;                    // 对每个元素-1
  return *_elem;                    // 返回当前 *this or *_elem
}

template <typename T>
T* Vector<T>::operator--(int i) {          // 重载后置--操作符
  T* e = _elem;
  --*this;                         // 调用前置递减
  return e;
}

template <typename T>
void Vector<T>::traverse(void (*visit)(T&))      // 函数指针
  {for (int i = 0; i < _size; i++) visit(_elem[i]);}

template <typename T> <template VST>
void Vector<T>::traverse(VST & visit) {        // 函数对象
  for (int i = 0; i < _size; i++) visit(_elem[i];)
}

int getLarger(const int& i1, const int& i2) {
  return i1 < i2 ? i2: i1;            // 返回两者较大
}

int (*pf1)(const int&, const int&);

pf1 = getLarget;
pf1 = &getLarget;       // 等价,

int (*pf1)(const int&, const int&) = &getLarger;

int i_pf1 = (*pf1)(3, 5);
int i_pf1_2 = (pf1)(3, 5);           // 等价
int i_pf1_3 = getLarget(3, 5);       // 等价 调用原函数

bool compareInt(const int& i1, const int& i2) {
  return i1 < i2 ? true : false;      // i1 < i2, 返回true
}

// 声明并定义
bool (*pf)(const int&, const int&) = &compareInt;

// 赋nullptr:指针没有指向任何一个函数
pf = 0;
pf = getLarger;     // error: pf已经被声明成bool(*)(const int&, const int&)
pf = increment;     // error: 同上

bool otherCompare(const int& i1, const int&) {return 0;}

pf = otherCompare;

void ff(int*);
void ff(unsigned int);

// 重载
void (*pff1)(int *) = &ff;      // pff1指向ff的 void (int*)版本

void (*pff2)(int) = &ff;        // Error
int (*pff3)(unsigned) = &ff;    // Error

// 第三个参数是函数指针类型
void useBigger(const int&, const int&, bool (*pf)(const int&, const int&));

// 调用时, 传入指向compareInt的指针
useBigger(i1, i2, &compareInt);

typedef decltype(compareInt) *FuncP2;    // FuncP2是指向函数的指针类型
typedef decltype(compareInt) Func;       // decltype()返回函数类型, Func是函数类型

void useBigger(const int&, const int&, FuncP2);
void useBigger(const int&, const int&, Func2);   // 编译器将Func2函数类型自动转换为了函数的指针类型

using PF = bool(*)(const int&, const int&);      // PF是函数的指针类型
using F = bool(const int&, const int&);          // F是指针类型

PF f1(int);          // 返回函数的指针类型
F *f1(int);          // 显式f1返回的是一个指针类型
F f2(int);           // Error:F是函数类型, 无法返回一个函数

// 定义一个函数对象
class Sum{
 public:
  int sum = 0;
  void operator()(int iarr[], int n) {
    for (int i = 0; i < n; i++)
      sum += iarr[i];
    std::cout << "sum = " << sum << std::endl;
  }
};

Sum s;
int iarr[] = {1, 2, 3, 4, 5, 6};
int n = 6;
s(iarr, n);      // sum = 21

// 函数对象作为另一个函数的形参
template <typename CLS>
void f(CLS & c) {
  int iarr[] = {3, 6, 9};
  int n = 3;
  c(iarr, n);
}


// 调用
Sum s1;
f(s1);       // sum = 18

template <typename T> template <typename VST>
void Vector<T>::traverse(VST visit) {
  // 对每个元素执行visit操作
  for (int i = 0; i < _size; i++) {visit(_elem[i]);}
}

// 为什么不能用引用类型?
// no known conversion for argument 1 from ‘Increase<int>’ to ‘Increase<int>&’

/* my error test
template <typename T>
void increase(Vector<T> V) {
  V.traverse(Increase(T& e));
}
*/
template <typename T>
void increase(Vector<T> V) {
  V.traverse(Increase<T>());
}

// 为什么不用实例化, 带入参数便可直接调用??

template <typename T> class Vector {};    // template定义方式

template <typename T> class Vector {
};
class BinTree {
};
template <typename T> class Tree {
};

int main() {
  // ..
  Vector<int> myVector;    // Right

  Vector<float> myfVector;

  Vector<BinTree> binForest;       // Combine with other class;
  Vector<Tree<int>> binForest;     // Combine with template;
  return 0;
}

// 寻秩访问
/* // my test
template <typename T>
T& Vector<T>::operator[](std::size_t n) {    // 这个类 Vector<T>
  assert(n < _size);
  return _elem[n];
}
*/

template <typename T>
T& Vector<T>::operator[](Rank r) const {   // 不改变数据成员, 定义成常量成员函数
  // 在vector内部, 定义了秩的类型, 统一用Rank
  assert(r < _size);   // 对下标秩进行溢出检测
  return _elem[r];
}

// 插入
/* my test
template <typename T>
void Vector<T>::insert(const Rank r, const int value) {
  // 检查移动后是否需要扩容
  if (++_size > _capacity) expand();
  // 将秩为r后的所有元素后移一位
  for (Rank i = _size-2; i >= r; i--) {     // 为了不覆盖数据, 从尾部开始移动
    _elem[i+1] = _elem[i];     // 向后移动一位
  }
  // 在r秩位置上填入要插入的值
  _elem[r] = value;
}
*/
template <typename T>
void Vector<T>::insert(const Rank r, T const &e) {
  // value不应该是某一中特点的类型, 而应该利用template的特性
  assert(0<= r && r < _size);
  expand();  // 若有必要扩容  结合expand()中, _size < _capacity的定义
  for (int i = _size; i > r; i--)  // 习惯把改变后的值的索引设置成i
    _elem[i] = _elem[i-1];     // 后继元素顺次后移一个单元
  _elem[r] = e; _size++;
}

// 删除操作
/* my test code
template <typename T>
void Vector<T>::del(const Rank lo, const Rank hi) {
  for (Rank i = lo; i < _size; i++) {
    // 清空区间元素
    if (i < hi) { _elem[i] = 0;
    } else {
      // 将元素整体前移
      _elem[i - (hi-lo)] = _elem[i];
      // 前移后元素清空
       _elem[i] = 0;
    }
  }
  // 缩短规模和空间容量
  _size -= hi-lo; _capacity -= hi-lo;
}
*/


template <typename T>
int Vector<T>::del(Rank lo, Rank hi) {
  // 处理退化情况
  if (lo == hi) return 0;
  const int length = hi - lo;
  // 自前向后的迁移操作
  while (lo < _size) {
    if (hi < _capacity) {_elem[lo++] = _elem[hi++];
    } else {_elem[lo++] = 0;}   // 处理hi++超出_capacityg容量的情况
  }
  // 更新规模或者缩容
  _size -= length;
  shrunk();
  // 返回被删除元素的数目
  return hi-lo;
}

// 查找
/* my test code
template <typename T>
int Vector<T>::find(Rank lo, Rank hi, T const &e) const {
  // 查找e在区间[lo,hi)内
  // 从右往左查找
  while (hi >= lo) {
    if (_elem[hi] == e) {return hi;
    }
    hi--;
  }
  // 没有在while循环中返回, 不存在匹配元素
  return -1;
}
*/

template <typename T>
Rank Vector<T>::find(Rank lo, Rank hi, T const &e) const {
  // O(hi - lo) = O(n), 在命中多个元素时可返回秩最大者
  while (lo < hi-- && e != _elem[hi]) {}   // 逆向查找
  return hi;   // hi < lo失败; 否则hi即命中元素的秩
}

// 删除单个元素
/* my test code
template <typename T>
void Vector<T>::remove(Rank r) {
  // 单元素的删除操作, 视为区间操作的特例 [r, r+1)
  remove(r, r+1);
}
*/
template <typename T>     // 删除向量中秩为r的元素, 0 <= r < size
T& Vector<T>::remove(Rank r) {  // O(n-r)
  T& old_t = _elem[r];    // 备份被删除的元素
  remove(r, r+1);         // 调用区间删除算法
  return old_t;           // 返回被删除元素
}

// 唯一化
/*
template <typename T>
void Vector<T>::deduplicate(Rank lo, Rank hi) {
  // 对向量中的元素遍历,
  for (Rank i = lo; i < hi; i++) {
    // find右往左查, 返回lo-1代表失败
    // 删除当前元素, 不再对后续元素查找
    if (find(lo, i, _elem[i]) != lo-1) {remove(i); break;}
    if (find(i+1, hi, _elem[i]) != i) { remove(i);}
  }
}
*/

template <typename T>
int Vector<T>::deduplicate() {
  int old_size = _size;
  Rank i = 1;
  while (i < _size) {
    find(0, i, _elem[i]) < 0 ?
                             i++  // 小于0说明无雷同, 继续查找
                             : remove(i);    // 删除雷同者(至多一个?!)
  }
  return  old_size - _size;      // 返回规模的变化量
}

// 遍历运用函数对象机制，对各个元素减1
/* my test code
// 单个T类型元素减1的类
template <typename T>
Vector<T>::struct Decrease {
  virtual void operator() {T &e--;}     // 重载()操作, 类对象当作函数来用
};

template <typename T>
void decrease(Vector<T>& V) {
  V.traverse(Decrease<T>());
}
// 泛型模板在调用的时候都要带<type>
*/

template <typename T>
struct Decrease {
  virtual void operator()(T &e) {e--;}
};

template <typename T>
void decrease(Vector<T> & V) {
  V.traverse(Decrease<T>());
}

template <typename T>
struct Double_value {
  virtual void operator()(T& e) {e *= 2;}   // 函数对象对元素翻倍
};

template <typename T>
void double_value(Vector<T>& V) {
  V.traverse(Double_value<T>());      // 函数对象作为遍历函数的参数
}

template <typename T>
void sum_ptr(Vector<T>& V) {
  T* sumPtr = &(V[0]);        // 别定义空指针, 该指针指向向量首位
  T sum = V.traverse(Sum<T>(), sumPtr);     // 调用并赋值
  std::cout << "sum = " << sum << std::endl;
}

template <typename T>
void sum_ptr(Vector<T>& V) {
  T sum_init = V[0];              // 创建一个副本, 避免通过指针修改V[0]
  T* sumPtr = &(sum_init);        // 别定义空指针, 该指针指向副本
  T sum = V.traverse(Sum<T>(), sumPtr);     // 调用并赋值
  std::cout << "sum = " << sum << std::endl;
}

// 通过类内static求和的函数对象
template <typename T>
struct Sum_static {
  static T sum_t;     // 内部声明存放求和结果的static变量
  virtual void operator()(T& e) {
    sum_t += e; std::cout << "revise static sum_t, sum_t = "
                          << sum_t << std::endl;    // 当心全局变量出错
  }
};

template <typename T>
T Sum_static<T>::sum_t = 0;   // 外部定义静态数据成员

template <typename T>
void sum_static(Vector<T> V) {
  Sum_static<T> sumstc;           // 实例化模板别忘记<type>
  V.traverse(Sum_static<T>());
  T sum = sumstc.sum_t;
  std::cout << "in sum_static, sum = " << sum << std::endl;
}

template <typename T>
void Vector<T>::expand() {
  if (_size < _capacity) return;    // 容量未到达不必扩容
  _capacity = max(_capacity, DEAFAULT_CAPACITY);    // 不小于最小容量
  // 存储旧元素, 新数组容量扩大
  T* old_elem = _elem; _elem = new T[_capacity <<= 1];
  for (int i = 0; i < _size; i++) {
    _elem[i] = old_elem[i];   // 复制原数组到新数组的对应位置
  }
  delete [] old_elem;    // 释放原数组的对应空间，归还系统
}

/* my test code
template <typename T>
void Vector<T>::expand() {
  if (_size == _capacity) {   // 规模到达最大容量时
    // 创建一个容量更大的数组
    T* _new_elem = new T[_capacity *= 1.2];  // ERROR:没有delete又重新new了一个
    Rank _tmp_size = _size;
    _size = 0;
    // 复制原数组到新数组的对应位置
    copyFrom(this->_elem, 0, _tmp_size);
    // 释放原数组的对应空间，归还系统
    delete [] _elem;
  }
}
*/

/* 最终版本的expand()中, new一个数组储存旧元素, 下面new一个数组, 作为扩容数组
template <typename T>
void Vector<T>::expand() {
  if (_size < _capacity) return;    // 容量未到达不必扩容
  _capacity = max(_capacity, DEAFAULT_CAPACITY);    // 不小于最小容量
  // 存储旧元素, 新数组容量扩大
  T* new_elem = new T[_capacity <<= 1];
  for (int i = 0; i < _size; i++) {
    new_elem[i] = _elem[i];   // 复制原数组到新数组的对应位置
  }
  // ERROR:不能直接赋值, 需要copyFrom(), 这里对_elem的更新不直接, 先新后旧的原则
  _elem = new_elem;      // ERROR:当前数组元素更新为新数组元素, 可T类型还没有operator=()
  delete [] new_elem;    // 释放临时数组的对应空间，归还系统
}
*/

_elem = new[T = _capacity + INCREMENT];     // 追加固定大小量

typedef int Rank;             // 秩
#define DEAFAULT_CAPACITY 3   // 默认初始容量

template <typename T> class Vector {   // 向量模板类
 private:
  Rank _size; int _capacity; T* _elem;   // 规模, 容量, 数据区
 protected:
  /* ... 内部函数*/
 public:
  /* ... 构造函数*/
  /* ... 析构函数*/
  /* ... 只读函数*/
  /* ... 可写函数*/
  /* ... 遍历函数*/
};

template <typename T> class Vector {   // 向量模板类
 private:
  Rank _size; int _capacity; T* _elem;   // 规模, 容量, 数据区
 protected:
  /* ... 内部函数*/
 public:
  // /* ... 构造函数
  void copyFrom(T* const A, Rank lo, Rank hi);
  Vector(int c = DEAFAULT_CAPACITY)
  {_elem = new T[_capacity = c]; _size = 0;}     // 默认
  Vector(T* const A, Rank lo, Rank hi)          // 数组区间复制
  {copyFrom(A, lo, hi);}
  Vector(Vector<T> const& V, Rank lo, Rank hi)   // 向量区间复制
  {copyFrom(V, lo, hi);}
  Vector(Vector<T> const& V)                     // 向量整体复制
  {copyFrom(V._elem, 0, V._size);}
  //  */
  // /* ... 析构函数
  ~Vector() {delete [] _elem;}                   // 释放内部空间
  // */
  /* ... 只读函数*/
  /* ... 可写函数*/
  /* ... 遍历函数*/
};

template <typename T>
void Vector<T>::copyFrom(T* const A, Rank lo, Rank hi) {
  _elem = new T[_capacity = 2*(hi- lo)];      // 分配空间
  _size = 0;  // 清零规模
  while (lo < hi)   // A[lo, hi)中的元素逐一
    _elem[_size++] = A[lo++];
}