#include "simple_gen_list.h"

// 广义表数据结构中不会存储‘(’和‘)’。
void SimpleGenList::createByQueueRecursive_(queue<char>& char_queue, simple_gen_list::SimpleGenListNode*& node)
{
	// 空表
	if (char_queue.empty())
		return;

	char chr = char_queue.front(); // 取出队首元素
	char_queue.pop(); // 队首元素出队

	// 递归建表
	if (chr == '(')
	{	
		node = new simple_gen_list::SimpleGenListNode(simple_gen_list::SimpleGenListNode::LIST);
		this->createByQueueRecursive_(char_queue,node->head);
		this->createByQueueRecursive_(char_queue,node);
	}
	else if (isalpha(chr)) //判断一个字符是否是字母（无论是大写字母还是小写字母）
	{
		node = new simple_gen_list::SimpleGenListNode(simple_gen_list::SimpleGenListNode::ATOM, chr);
		this->createByQueueRecursive_(char_queue, node);
	}
	else if (chr == ',')
	{
		this->createByQueueRecursive_(char_queue,node->next);
	}
	else if (chr == ')')
	{
		if (node)
			node->next = NULL;
	}
}

// 子表构造字符队列(递归)，并且要恢复‘(’和‘)’。
bool SimpleGenList::toCharQueueRecursive_(queue<char>& char_queue, simple_gen_list::SimpleGenListNode* node)
{
	// error
	if (node->type != simple_gen_list::SimpleGenListNode::LIST)
		return false;

	char_queue.push('(');

	simple_gen_list::SimpleGenListNode* cur = node->head;

	while (cur)
	{
		if (cur->type == simple_gen_list::SimpleGenListNode::LIST)
		{
			bool res = this->toCharQueueRecursive_(char_queue,cur);
			if (!res)
				return false;
		}
		else if (cur->type == simple_gen_list::SimpleGenListNode::ATOM)
		{
			char_queue.push(cur->data);
		}

		if (cur->next)
			char_queue.push(',');

		cur = cur->next;
	}

	char_queue.push(')');

	return true;
}

// 求子表深度(递归)
int SimpleGenList::subGenListDepthRecursive_(simple_gen_list::SimpleGenListNode* node)
{
	simple_gen_list::SimpleGenListNode* cur = node->head;
	if (!cur) // 空的广义表的深度为 1
		return 1;

	int max_sub_list_depth = 1; // 广义表的每个原子元素深度算 1

	while (cur)
	{
		if (cur->type == simple_gen_list::SimpleGenListNode::LIST)
		{
			int cur_sub_list_depth = this->subGenListDepthRecursive_(cur);
			if (max_sub_list_depth < cur_sub_list_depth)
				max_sub_list_depth = cur_sub_list_depth;
		}

		cur = cur->next;
	}
	return max_sub_list_depth + 1; // 非空广义表的深度为其所有元素的深度中的最大值加 1
}

// 求子表长度(递归)
int SimpleGenList::subGenListLengthRecursive_(simple_gen_list::SimpleGenListNode* node)
{
	if (!node) // 空表
		return 0;

	int sub_list_length = this->subGenListDepthRecursive_(node->next) + 1;

	return sub_list_length;
}

void SimpleGenList::createByString(const string& gen_list_string)
{
	queue<char> char_queue;

	for (int i = 0; i < gen_list_string.length(); i++)
	{
		char chr = gen_list_string[i];
		char_queue.push(chr);
	}

	this->createByQueueRecursive_(char_queue,this->list_node_);
}

// 生成字符串
string SimpleGenList::toString()
{
	string str;
	queue<char> char_queue;

	bool res = this->toCharQueueRecursive_(char_queue,this->list_node_);
	if (!res)
		throw exception("error in toCharQueueRecursive_");

	// 队列非空
	while (!char_queue.empty())
	{
		char chr = char_queue.front();
		str.push_back(chr);

		char_queue.pop();
	}
	return str;
}

int SimpleGenList::depth()
{
	int depth = this->subGenListDepthRecursive_(this->list_node_);

	return depth;
}

int SimpleGenList::length()
{
	int list_length = this->subGenListLengthRecursive_(this->list_node_->head);
	return list_length;
}