#pragma once

#include "address_list.hpp"

#include "opcode_utility.hpp"
#include "instruction_map.hpp"
#include "instruction_scanner.hpp"
#include "instruction_output.hpp"
#include "nes_program_image.hpp"

#include <vector>
#include <list>
#include <map>
#include <iostream>
#include <sstream>
#include <algorithm>

#include <boost/shared_ptr.hpp>
#include "debug_macro.hpp"

/** This list element can hold tag value.
 *  It can holds same elements, unlike map's key.
 *
 *  @ Usage:
 *  enum Type { BYTE, WORD, POINTER,};
 *  TagList<Type, std::string> symbols;
 *  symbols.push(BYTE, "hoge");
 *  symbols.push(WORD, "piyo");
 *  symbols.push(BYTE, "fuga");
 *  
 */
template <typename _TagEnum, typename _Tp>
class TagList
{
	struct TagPair 
	{
		_TagEnum tag;
		_Tp value;
	};
	std::vector< std::pair<_TagEnum, _Tp> > m_vector;
public:
	typedef _TagEnum tag_type;
	typedef _Tp value_type;
	
	void push(tag_type tag, value_type val);
};

/** It has entry, label, branch, data list*/
class ControlPointList
{
public:
	/** TODO naming.*/
	enum AddressReferenceType {
		ENTRY, LABEL, BRANCH, DATA, CALL,
	};
	typedef boost::shared_ptr<ControlPointList> shared_ptr;
	AddressList::shared_ptr m_entry_list;
	AddressList::shared_ptr m_label_list;
	/** branch includes JMP, JSR, BCC etd, RTS RTI BRK.*/
	AddressList::shared_ptr m_branch_list;
	/** data section is const data in executive code */
	AddressList::shared_ptr m_data_list;
	ControlPointList()
	{
		m_entry_list = AddressList::create();
		m_label_list = AddressList::create();
		m_branch_list = AddressList::create();
		m_data_list = AddressList::create();
	}
	AddressList::shared_ptr getEntryList()const
	{
		return m_entry_list;
	}
	AddressList::shared_ptr getLabelList()const
	{
		return m_label_list;
	}
	AddressList::shared_ptr getBranchList()const
	{
		return m_branch_list;
	}
	AddressList::shared_ptr getDataList()const
	{
		return m_data_list;
	}
	void pushEntry(unsigned address)
	{
		m_entry_list->push_back(address);
	}
	void pushLabel(unsigned address)
	{
		m_label_list->push_back(address);
	}
	void pushBranch(unsigned address)
	{
		m_branch_list->push_back(address);
	}
	void pushData(unsigned address)
	{
		m_data_list->push_back(address);
	}
	/* remove the redundant element from each list.*/
	void straighten()
	{
		AddressList::straighten(m_entry_list);
		AddressList::straighten(m_label_list);
		AddressList::straighten(m_branch_list);
		AddressList::straighten(m_data_list);
		AddressList::excludeListFrom(m_data_list,m_label_list);
	}
	/** display brief result.*/
	void display(std::ostream& os) 
	{
		os << m_entry_list->size()<< " entrys, "
		   << m_label_list->size()<< " labels, "
		   << m_branch_list->size()<< " branches, "
		   << m_data_list->size()<< " datas ";
	}
};

/** This worker collect entry list by map and bytecode*/
class ControlPointAnalyzer
{
	AddressMarker m_visit_record;
	
	MemoryImage::shared_ptr m_code;
	InstructionMap::shared_ptr m_map;
	ControlPointList::shared_ptr m_control_list;
	
	unsigned byte_count; /** this value counts how many bytes are analyzed.*/
	std::stringstream log;
	
public:
	ControlPointAnalyzer(MemoryImage::shared_ptr bytecode,
						   InstructionMap::shared_ptr map)
			:m_code(bytecode),
			 m_map(map),
			 m_control_list(new ControlPointList),
			 byte_count(0)
	{
	}
	/** This getter is used to get the result of ControlPointAnalyzer */
	ControlPointList::shared_ptr getControlPointList()const
	{
		return m_control_list;
	}
	/** This method is public because client add address before analysis.*/
	void pushEntryPoint(unsigned address)
	{
		m_control_list->pushEntry(address);
		m_control_list->pushLabel(address);
	}
	
	bool isScanned(unsigned address)const
	{
		return (m_map->find(address) != m_map->end()) ;
	}
	/** if jump destination address is not scanned, post scan.*/
	void postScan(unsigned address)
	{
		InstructionPostScanner post_scan(m_map, address);
		post_scan.readThreeBytes(
				m_code->at(address),
				m_code->at(address+1),
				m_code->at(address+2));
	}
	
	/** Push entry point before calling analyze.  */
	bool isSkip(unsigned address)const
	{
		return m_visit_record.found(address) || !m_code->includes(address);
	}
	void analyze()
	{
		analyzeVerbose(log);
	}
	void analyzeVerbose(std::ostream& os)
	{
		AddressWorkList call_list;
		AddressWorkList work_list;
		AddressWorkList resume_list;

		AddressList::shared_ptr entry_list = m_control_list->getEntryList();
		for (unsigned i=0; i < entry_list->size(); ++i) {
			call_list.push_back((*entry_list)[i]);
		}
		
		while (!call_list.empty() || !resume_list.empty()) {
			unsigned address = (!call_list.empty())
					? call_list.pop() : resume_list.pop();
			
			while (true) {
				if (isSkip(address)) {
					if (!work_list.empty()) {
						address = work_list.pop();
						continue; // check again.
					} else {
						break;
					}
				} else if (!isScanned(address)) {
					postScan(address);
				}
		
				m_visit_record.mark(address);
				Instruction::shared_ptr instr = (*m_map)[address];
				byte_count+=instr->bytelength();
				
				//displayInstruction(os, instr);
				opcode::OperationType optype(instr->op());
				
				bool is_dest_ok = m_code->includes(instr->parameter());
				if (optype.is_return) {
					resume_list.push_back(instr->next());
					
					m_control_list->pushBranch(address);
					m_control_list->pushData(instr->next());
					continue;
				} else if (optype.is_conditional && is_dest_ok) {
					work_list.push(instr->parameter());
					
					m_control_list->pushBranch(address);
					m_control_list->pushLabel(instr->parameter());
				} else if (optype.is_call && is_dest_ok) {
					call_list.push(instr->parameter());

					m_control_list->pushBranch(address);
					m_control_list->pushEntry(instr->parameter());
					m_control_list->pushLabel(instr->parameter());
				} else if (optype.is_jump && is_dest_ok) {
					work_list.push(instr->parameter());
					resume_list.push_back(instr->next());
					
					m_control_list->pushBranch(address);
					m_control_list->pushLabel(instr->parameter());
					m_control_list->pushData(instr->next());//suspect.
					continue;
				} else if (instr->accessType() == opcode::RD && is_dest_ok) {
					m_control_list->pushData(instr->next());
				}
				address = instr->next();
			}
		}
		m_control_list->straighten();
		displayBriefResult(os);
		//displayList(os, m_control_list->getEntryList());
		//displayDataSections(os);
	}
	void displayInstruction(std::ostream& os,
							Instruction::shared_ptr instr)const
	{
		InstructionQuadrupleOutput quadruple(instr);
		InstructionBytecodeOutput byte_out(instr);
				
		os << "               " << quadruple
		   << "   " << byte_out << std::endl;
	}
	void displayBriefResult(std::ostream& os)const
	{
		os << (HexadecimalFormat(byte_count))<< " bytes, ";
		m_control_list->display(os);
		os<< std::endl;
		
	}
	void displayList(std::ostream& os,
					   AddressList::shared_ptr entry_list)const
	{
		unsigned count = 0;
		for (auto i=entry_list->begin(); i!=entry_list->end(); ++i) {
			if (count % 10 == 0) {
				os << std::endl << DecimalFormat(count).width(4) << "    ";
			}
			count++;
			os << HexadecimalFormat(*i) << " ";
		}
		os << std::endl;
	}
	/* inspect data sections. */
	void displayDataSections(std::ostream& os)const
	{
		AddressWorkList work_list;
		AddressList::shared_ptr data_list = m_control_list->getDataList();
		
		AddressList::isInList is_branch(m_control_list->getBranchList());
		AddressList::isInList is_label(m_control_list->getLabelList());
		AddressList::isInList is_data(data_list);

		for (unsigned i=0; i < data_list->size(); ++i) {
			work_list.push_back((*data_list)[i]);
		}
		unsigned address = 0;
		while (!work_list.empty()) {
			if (m_map->find(address) == m_map->end()
				|| is_label(address)
				|| is_branch(address))
			{
				if (!work_list.empty()) {
					while (!work_list.empty()) {
						address = work_list.pop();
						if (m_map->find(address) != m_map->end())
						{
							break;
						}
					}
					os << HexadecimalFormat(address) << std::endl;
					continue;
				} else {
					break;
				}
			}
			Instruction::shared_ptr instr = (*m_map)[address];
			displayInstruction(os, instr);

			address = instr->next();
			
			if (is_data(address)){
				address = 0;
			}
		}
	}
	void displayProgress(std::ostream& os,
						 unsigned call_size, unsigned resume_size,
						 unsigned address)const
	{
		os << HexadecimalFormat(address).width(4) << ": "
		   << call_size<< " calls "
		   << resume_size<< " section remained"
		   << std::endl;
	}
};
