/**
 * ac.h
 * Author : erdao
 * Date : 2016/8/5
 */

#ifndef _AC_H__
#define _AC_H__

#include <stdint.h>
#include <unordered_map>
#include <vector>

//< 转换规则，用作map的key
class TransformPolicy {
public:
	virtual uint64_t transform(void *) = 0;
};


// Trie树结构的定义
template <typename valueType, typename tagType, class Trans>
struct TrieNode {
	//unordered_map快速定位子节点
	//using ChildMapType = std::unordered_map<uint64_t, TrieNode *>;

	valueType 	value;
	tagType 	tag;
	bool		flag;

	std::unordered_map<uint64_t, TrieNode *>	children;
	TrieNode		*fail;

	TrieNode()
		: value{}
		, tag{}
		, flag{false}
		, fail{ nullptr }
	{}
};

template <typename valueType, typename tagType, class Trans>
class AC_Automation {
	using ACNode = TrieNode<valueType, tagType, Trans>;

public:
	AC_Automation()
		: pRoot(nullptr) {
		pRoot = new ACNode{};
	}
	~AC_Automation() {
		this->removeNode(pRoot);
		pRoot = nullptr;
	}

	void addData(valueType* pValArray, uint32_t uValNum, tagType vTag);
	void buildFail();

	//返回的格式包括位置和tagType
	std::vector<std::pair<uint32_t, tagType>> Search(valueType *pValArray, uint32_t uValNum);

private:
	void removeNode(ACNode *pNode) {
		if (pNode) {
			for (auto &child : pNode->children) {
				removeNode(child.second);
			}
			pNode->children.clear();
			delete pNode;
		}
	}

private:
	ACNode *pRoot;
};

#endif//_AC_H__

/**
 * ac.cpp
 * Author : erdao
 * Date : 2016/8/5
 */
 
#include <stdint.h>
#include <queue>
#include <vector>

#include "ac.h"

template <typename valueType, typename tagType, class Trans>
void AC_Automation<valueType, tagType, Trans>::addData(valueType* pValArray, uint32_t uValNum, tagType vTag)  {
	using ACNode = TrieNode<valueType, tagType, Trans>;
	
	Trans t{};
	ACNode *p = pRoot;
	for (uint32_t i = 0; i < uValNum; ++i) {
		uint64_t key = t.transform(&pValArray[i]);
		if (p->children.find(key) != p->children.end()) {
			p = p->children[key];
		}
		else {
			p->children[key] = new ACNode{};
			p = p->children[key];
			p->value = pValArray[i];
		}
	}
	p->tag = vTag;
	p->flag = true;
}

template <typename valueType, typename tagType, class Trans>
void AC_Automation<valueType, tagType, Trans>::buildFail() {
	using ACNode = TrieNode<valueType, tagType, Trans>;
	
	//实际上，由于所有的fail指针都相交于pRoot，且相互间平行，不存在交叉情况，可以采用自上而下的遍历方式进行创建
	Trans t{};
	std::queue<ACNode *> qNode;
	qNode.push(pRoot);
	/*pRoot默认指向nullptr，可以作为fail跳转终止条件；另外pRoot本身也是终止条件，按照喜好处理*/

	while (!qNode.empty()) {
		ACNode *p = qNode.front();
		//为p的所有child创建fail
		for (const auto &child : p->children) {
			if (p == pRoot) {
				//深度为1的节点失败都跳转到root
				child.second->fail = pRoot;
			}
			//否则的话，寻找父节点失败指针串中与child值相同的节点
			else{
				uint64_t key = t.transform(&child.second->value);
				ACNode *pFail = p->fail;
				while (pFail) {
					if (pFail->children.find(key) != pFail->children.end()) {
						child.second->fail = pFail->children[key];
						break;
					}
					pFail = pFail->fail;
				}
				if (!pFail)
					child.second->fail = pRoot;
			}
			//将本身处理好的节点放入队列，准备处理子节点
			qNode.push(child.second);
		}
		//将子节点处理好的节点弹出队列
		qNode.pop();
	}	

}

template <typename valueType, typename tagType, class Trans>
std::vector<std::pair<uint32_t, tagType>> AC_Automation<valueType, tagType, Trans>::Search(valueType *pValArray, uint32_t uValNum) {
	using ACNode = TrieNode<valueType, tagType, Trans>;

	//搜索的入口从root开始，不停的迭代Trie树中的fail指针，匹配上时进行记录
	std::vector<std::pair<uint32_t, tagType>> vRes;
	ACNode *p = pRoot;
	Trans t{};
	for (uint32_t i = 0; i < uValNum; ++i) {
		uint64_t key = t.transform(&pValArray[i]);
		//寻找到当前p下fail串中能匹配上的p
		while (p->children.find(key) == p->children.end() && p != pRoot) {
			p = p->fail;
		}
		//如果遍历完没找到的话，那么终止条件是p=pRoot（所有fail最终交会）
		if (p->children.find(key) == p->children.end())
			continue;
		p = p->children[key];

		//如果找到了，检查这一层的fail中是否具有终结标记
		auto pFail = p;
		while (pFail) {
			if (pFail->flag)
				vRes.push_back(std::move (std::make_pair(i, pFail->tag)));
			pFail = pFail->fail;
		}
	}

	return std::move(vRes);
}

//	test.cpp
int main() {
	//转换规则
	class TransChar : public TransformPolicy {
	public:
		uint64_t transform(void *a) { return (uint64_t)*(char *)a; }
	};

	char test_words[][10] {
		"her", "she", "shy", "here", "hi", "he"
	};

	AC_Automation<char, int, TransChar> ac{};
	for (uint32_t i = 0; i < sizeof(test_words) / sizeof(test_words[0]); i++) {
		ac.addData(test_words[i], strlen(test_words[i]), i);
	}
	ac.buildFail();

	const char *query = "Oh, she is there so shy, let's go say hi.";
	auto ret = ac.Search((char *)query, strlen(query));

	std::cout << query << std::endl;
	for (auto &r : ret) {
		uint32_t pos = r.first + 1 - strlen(test_words[r.second]);
		for (uint32_t k = 0; k < pos; ++k)
			std::cout << "-";
		std::cout << test_words[r.second] << std::endl;
	}
	
	return 0;
}