#pragma once

#include <iostream>
#include <cstdlib>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

namespace gen_list
{
	template <class T>
	class GenListNode;

	template <class T>
	union GenNodeUnion
	{
		int ref_count;	// 引用计数						// 0
		T value;		// 数据							// 1
		GenListNode<T>* ref_node;	// 下一个表的地址	// 2
	};

	template <class T>
	struct Item
	{
		int type;
		GenNodeUnion<T> union_info;

		Item() :type(GenListNode<T>::REF_TYPE)
		{
			this->union_info.ref_count = 0;
		}

		Item(Item<T>& item) :type(item.union_type_) // ???
		{
			this->union_info = item.union_info;
		}
	};
	
	template <class T>
	class GenListNode
	{
		static const int REF_TYPE = 0;			// 引用类型
		static const int ELEM_TYPE = 1;			// 数据结点类型
		static const int CHILD_LIST_TYPE = 2;	// 子表类型

		int type;					// 类型，影响Union类型		
		GenNodeUnion<T> union_info;	// Union类型

		GenListNode<T>* next;		// 下一节点指针

		// 默认就是引用类型
		GenListNode() :type(GenListNode<T>::REF_TYPE), next(NULL) { this->union_info.ref_count = 0; }
	
		GenListNode(GenListNode<T>& node)
			:type(node.type), next(node.next), union_info(node.union_info) {}
	};

}

template <class T>
class GenList
{
	// 重载 >> 运算符实现输入功能
	friend istream& operator>> <>(istream& in, GenList<T> & gen_list);

private:
	vector<T> gen_list_name_vec_; // 各表节点的vector
	vector<gen_list::GenListNode<T>*> gen_list_node_vec_; // 各表节点指针的vector
	// 上面两个vector内的元素是对应关系，表名和表实体指针对应关系

	// 子表打印
	void subGenToStringRecursive_(gen_list::GenListNode<T>* node, vector<T> & char_vec);

	// 子表长度（递归）
	int subGenListLengthRecursive_(gen_list::GenListNode<T>* un_ref_type_node);

	// 子表深度（递归）
	int subGenListDepthRecursive_(gen_list::GenListNode<T>* ref_type_node);

	// 是否是表名（大写字母）
	bool isGenListNameChar_(T chr);

	// 是否是表起始字符（大写字母或者‘（’）
	bool isGenListBeginChar_(T chr);

	// 左括号处理
	void leftBracketHandler_(queue<T>& char_queue);

	// ‘#’对应的右括号处理
	void passRightBracketAfterSharpChar(queue<T>& char_queue);

	// 新建元素节点
	gen_list::GenListNode<T>* newElemTypeNode_(T chr);

	// 新建子表节点
	gen_list::GenListNode<T>* newChildGenListNode_();

	// 查找已经被引用的节点
	gen_list::GenListNode<T>* findReferredNodePtr_(T chr);

	// 复制子树
	gen_list::GenListNode<T>* copy_(gen_list::GenListNode<T>* & ref_type_node);

public:
	gen_list::GenListNode<T>* ref_node_; // 广义表的引用节点

	GenList();

	bool head(gen_list::Item<T> & item);

	bool tail(GenList<T>& tail_list);

	void copyFrom(GenList<T> & src_gen_list);

	int length();

	int depth();

	void createGenListByQueueRecursive(queue<T> & char_queue,gen_list::GenListNode<T>* & node, bool & in_referred_list);

	void createListByString(string gen_list_string);

	// 删除节点，to do
	void remove(gen_list::GenListNode<T> * node_ptr);

	string toString();
};


// 重载>>运算符，实现输入功能
template <typename T>
istream& operator>>(istream& in, GenList<T>& gen_list)
{
	string input_str;
	cout << "Input the string：" << endl;

	in >> input_str;

	gen_list.createListByString(input_str);

	return in; // 支持链式编程
}

// 子表的字符化，字符进入vector容器
template<class T>
inline void GenList<T>::subGenToStringRecursive_(gen_list::GenListNode<T>* node, vector<T>& char_vec)
{
	for (int i = 0; i < this->gen_list_node_vec_.size(); i++)
	{
		if (this->gen_list_node_vec_[i] == node)
		{
			char_vec.push_back(this->gen_list_name_vec_[i]);
			char_vec.push_back('(');

			break;
		}
	}

	gen_list::GenListNode<T>* cur_node = node->next;

	if (!cur_node)
	{
		char_vec.push_back("#");
		char_vec.push_back(")");
	}

	while (cur_node)
	{
		if (cur_node->type == gen_list::GenListNode<T>::CHILD_LIST_TYPE)
			this->subGenToStringRecursive_(cur_node->union_info.ref_node, char_vec);
		else if (cur_node->type == gen_list::GenListNode<T>::ELEM_TYPE)
			char_vec.push_back(cur_node->union_info.value);

		if (cur_node->next)
			char_vec.push_back(',');
		cur_node = cur_node->next;
	}

	char_vec.push_back(')');
}

template<class T>
inline int GenList<T>::subGenListLengthRecursive_(gen_list::GenListNode<T>* un_ref_type_node)
{
	// 空广义表深度为1，长度为0
	if (!un_ref_type_node)
		return 0;

	int sub_list_length = this->subGenListLengthRecursive_(un_ref_type_node->next) + 1;

	return sub_list_length;
}

template<class T>
inline int GenList<T>::subGenListDepthRecursive_(gen_list::GenListNode<T>* ref_type_node)
{
	// 空广义表深度为1，长度为0
	gen_list::GenListNode<T>* cur_node = ref_type_node->next;

	if (!cur_node)
		return 1;

	int max_sub_list_depth = 1; //  1 为深度的最小可能值

	while (cur_node)
	{
		if (cur_node->type == gen_list::GenListNode<T>::CHILD_LIST_TYPE)
		{
			int sub_list_depth = this->subGenListDepthRecursive_(cur_node->union_info.ref_node);
			if (max_sub_list_depth < sub_list_depth)
				max_sub_list_depth = sub_list_depth;
		}

		cur_node = cur_node->next;
	}

	return max_sub_list_depth + 1;
}

// 判断是否是表名（大写字母）
template<class T>
inline bool GenList<T>::isGenListNameChar_(T chr)
{
	return isalpha(chr) && isupper(chr);
}

// 判断是否是线性表的起始字符，大写字母或者‘（’
template<class T>
inline bool GenList<T>::isGenListBeginChar_(T chr)
{
	return (isalpha(chr) && isupper(chr)) || chr == '(';
}

// 左括号处理函数
// 如果队头元素是 '('，则继续运行程序；否则，程序直接退出。
template<class T>
inline void GenList<T>::leftBracketHandler_(queue<T>& char_queue)
{
	T chr = char_queue.front();

	char_queue.pop();

	if (chr != '(')
		exit(1);
}

// '#'(sharp)对应的右括号处理
template<class T>
inline void GenList<T>::passRightBracketAfterSharpChar(queue<T>& char_queue)
{
	T chr = char_queue.front();
	char_queue.pop();

	if (chr != ')')
		exit(1);
}

template<class T>
inline gen_list::GenListNode<T>* GenList<T>::newElemTypeNode_(T chr)
{
	gen_list::GenListNode<T>* node = new gen_list::GenListNode<T>();
	node->type = gen_list::GenListNode::ELEM_TYPE;
	node->union_info.value = chr;

	return node;
}

template<class T>
inline gen_list::GenListNode<T>* GenList<T>::newChildGenListNode_()
{
	gen_list::GenListNode<T>* node = new gen_list::GenListNode<T>();
	node->type = gen_list::GenListNode<T>::CHILD_LIST_TYPE;

	return node;
}

template<class T>
inline gen_list::GenListNode<T>* GenList<T>::findReferredNodePtr_(T chr)
{
	gen_list::GenListNode<T>* node = NULL;
	// 使用 typename 关键字是为了明确告诉编译器，vector<T>::iterator 是一个类型（而不是一个静态成员或其他非类型的东西）
	typename vector<T>::iterator name_iter = gen_list_name_vec_.begin();
	typename vector<gen_list::GenListNode<T>*>::iterator node_iter = gen_list_name_vec_.begin();

	// 遍历this->gen_list_name，找到存在于字符串中的字符
	for (; name_iter != this->gen_list_name_vec_.end(); name_iter++, node_iter++)
	{
		if (chr == *name_iter)
		{
			node = *node_iter;
			break;
		}
	}

	return node;
}

template<class T>
inline gen_list::GenListNode<T>* GenList<T>::copy_(gen_list::GenListNode<T>*& ref_type_node)
{
	gen_list::GenListNode<T>* cur_node = NULL;

	if (this->ref_node_)
	{
		cur_node = new gen_list::GenListNode<T>();
		cur_node->type = this->ref_node_->type;

		switch (ref_type_node->type)
		{
		case gen_list::GenListNode<T>::REF_TYPE:
			cur_node->union_info.ref_count = ref_type_node->union_info.ref_count;
			break;
		case gen_list::GenListNode<T>::ELEM_TYPE:
			cur_node->union_info.value = ref_type_node->union_info.value;
			break;
		case gen_list::GenListNode<T>::CHILD_LIST_TYPE:
			cur_node->union_info.ref_node = this->copy_(ref_type_node->union_info.ref_node);
			break;
		default:
			break;
		}

		cur_node->next = this->copy_(ref_type_node->next);

	}
	return cur_node;
}

template<class T>
inline GenList<T>::GenList()
{
	this->ref_node_ = new gen_list::GenListNode<T>();
	if (!this->ref_node_)
		throw bad_alloc();
		//cerr << "GenList constructor wrong." << endl;
}

template<class T>
inline bool GenList<T>::head(gen_list::Item<T>& item)
{
	if (!this->ref_node_->next) // 空表没有表头
		return false;
	else
	{
		item.type = this->ref_node_->type;
		item.union_info = this->ref_node_->union_info;
	}
}

template<class T>
inline bool GenList<T>::tail(GenList<T>& tail_list)
{
	if (!this->ref_node_->next) // 空表没有表尾
		return false;
	else
	{
		tail_list.ref_node_->type = gen_list::GenListNode<T>::REF_TYPE;
		tail_list.ref_node_->union_info.ref_count = 0;
		tail_list.ref_node_->next = this->copyFrom(this->ref_node_->next->next);
	}
}

template<class T>
inline void GenList<T>::copyFrom(GenList<T>& src_gen_list)
{
	this->ref_node_ = this->copy_(src_gen_list.ref_node_);
}

template<class T>
inline int GenList<T>::length()
{
	int list_length = this->subGenListLengthRecursive_(this->ref_node_->next);

	return list_length;
}

template<class T>
inline int GenList<T>::depth()
{
	return this->subGenListDepthRecursive_(this->ref_node_);
}

template<class T>
inline void GenList<T>::createGenListByQueueRecursive(queue<T>& char_queue, gen_list::GenListNode<T>*& node, bool& in_referred_list)
{
	T chr = char_queue.front();
	char_queue.pop();

	gen_list::GenListNode<T>* referred_node = NULL;

	bool is_gen_list_begin_char = this->isGenListBeginChar_(chr);

	if (is_gen_list_begin_char)
	{
		// 是否是大写字符(表名)
		bool is_gen_list_name_char = this->isGenListNameChar_(chr);

		if (is_gen_list_name_char)
		{
			// 重复引用，节省空间
			referred_node = this->findReferredNodePtr_(chr);

			if (referred_node) // 已有该子表
			{
				// 创建一个子表节点，即类型（2）的节点
				node = this->newChildGenListNode_();
				node->union_info.ref_node = referred_node; // 指向这个已经存在的子表
				referred_node->union_info.ref_count++; // 该子表对应的引用计数+1
			
				in_referred_list = true;
			}
			else
			{
				node = this->newChildGenListNode_();
				gen_list::GenListNode<T>* ref_type_node = new gen_list::GenListNode<T>();
				ref_type_node->union_info.ref_count = 1;
				node->union_info.ref_node = ref_type_node;

				this->gen_list_name_vec_.push_back(chr);
				this->gen_list_node_vec_.push_back(ref_type_node);

				in_referred_list = false;
			}

			// 将队列中的‘(’出队，要求格式“表名后必须加‘(’”
			this->leftBracketHandler_(char_queue);

			this->createGenListByQueueRecursive(char_queue,node->union_info.ref_node->next,in_referred_list);
			this->createGenListByQueueRecursive(char_queue,node,in_referred_list);
		}
	}
	else if (isalpha(chr) && islower(chr))
	{
		if (!in_referred_list) // 没有在进行遍历的子表
		{
			node = this->newElemTypeNode_(chr);
			this->createGenListByQueueRecursive(char_queue,node,in_referred_list);
		}
	}
	else if (chr == ',')
	{
		createGenListByQueueRecursive(char_queue,node->next,in_referred_list);
	}
	else if (chr == ')')
	{
		if (!in_referred_list)
			node->next = NULL;
		in_referred_list = false;
	}
	else if (chr == '#')
	{
		if (!in_referred_list)
		{
			node = NULL;
			this->passRightBracketAfterSharpChar(char_queue);
		}
		in_referred_list = false;
	}

}

template<class T>
inline void GenList<T>::createListByString(string gen_list_string)
{
	queue<T> char_queue;

	// 先将字符串放入队列中
	for (int i = 0; i < gen_list_string.length(); i++)
	{
		char_queue.push(gen_list_string[i]);
	}

	bool in_referred_list = false;

	this->createGenListByQueueRecursive(char_queue,this->ref_node_->next,in_referred_list);
	
	// 调整ref_node_
	this->ref_node_ = this->ref_node_->next->union_info.ref_node;
}

template<class T>
inline void GenList<T>::remove(gen_list::GenListNode<T>* node_ptr)
{
}

template<class T>
inline string GenList<T>::toString()
{
	vector<T> char_vec;
	this->subGenToStringRecursive_(this->ref_node_,char_vec);

	string gen_list_string(char_vec.begin(),char_vec.end());

	return gen_list_string;
}