#pragma once

#include "basic_block.hpp"
#include "control_point.hpp"//address_list
#include "container_utility.hpp"

#include "chocolat/string/number_format.hpp"

/** Object of this class is node of call graph.*/
class Routine
{
public:
	typedef boost::shared_ptr<Routine> shared_ptr;
	enum {
		FAKE_ENTRY = 0, FAKE_EXIT = 0xFFFF,
	};
	
	AddressList::shared_ptr m_entry_points;
	AddressList::shared_ptr m_exit_points;
	BasicBlockList::shared_ptr m_block_list;
	Routine()
			:m_entry_points(AddressList::create()),
			 m_exit_points(AddressList::create()),
			 m_block_list(BasicBlockList::create())
	{
	}
	AddressList::shared_ptr entryPointList()
	{
		return m_entry_points;
	}
	AddressList::shared_ptr entryExitList()
	{
		return m_exit_points;
	}
	BasicBlockList::shared_ptr blockList()
	{
		return m_block_list;
	}
	void pushBlock(BasicBlock::shared_ptr block)
	{
		(*m_block_list)[block->startAddress()] = block;
	}
	void pushEntryPoint(unsigned address)
	{
		m_entry_points->push_back(address);
	}
	void pushExitPoint(unsigned address)
	{
		m_exit_points->push_back(address);
	}
	/** multi entry -> single entry point.*/
	void insertFakeBlock()
	{
		BasicBlock::shared_ptr fake_entry = BasicBlock::create(0);
		BasicBlock::shared_ptr fake_exit = BasicBlock::create(0xFFFF);
		
		(*m_block_list)[FAKE_ENTRY]=fake_entry;
		(*m_block_list)[FAKE_EXIT]=fake_exit;
		
		for (auto i=m_entry_points->begin();
			 i!=m_entry_points->end(); ++i)
		{
			fake_entry->linkTo((*m_block_list)[*i]);
		}
		for (auto i=m_exit_points->begin();
			 i!=m_exit_points->end(); ++i)
		{
			((*m_block_list)[*i])->linkTo(fake_exit);
		}
	}
	unsigned firstEntryPoint()const
	{
		if (m_entry_points->empty()) {
			return 0;
		} else {
			return *(m_entry_points->begin());
		}
	}
	unsigned size()const
	{
		unsigned result=0;
		for (auto i=m_block_list->begin(); i!=m_block_list->end(); ++i) {
			result += i->second->size();
		}
		return result;
	}
	void straighten()
	{
		AddressList::straighten(m_entry_points);
		AddressList::straighten(m_exit_points);
		insertFakeBlock();
	}
	void display(std::ostream& os)const
	{
		AddressListManipulater entries(m_entry_points);
		os << entries.to_s() << ": ";
		os << m_entry_points->size() << " entries "
		   << m_exit_points->size() << " exits "
		   << m_block_list->size() << " blocks "
		   << size() << " bytes";
	}
};
/** the list of Routine.*/
class RoutineList
{
public:
	typedef std::vector<Routine::shared_ptr> vector;
	typedef boost::shared_ptr<vector> shared_ptr;
	RoutineList::shared_ptr m_list;
	static RoutineList::shared_ptr create()
	{
		return RoutineList::shared_ptr(new RoutineList::vector);
	}
	RoutineList()
	{
		m_list = RoutineList::create();
	}
	shared_ptr getList()
	{
		return m_list;
	}
	unsigned size()const
	{
		return m_list->size();
	}
	void push(Routine::shared_ptr routine)
	{
		m_list->push_back(routine);
	}
	void display(std::ostream& os)const
	{
		for (auto i=m_list->begin(); i!=m_list->end(); ++i) {
			(*i)->display(os);
			os << std::endl;
		}
	}
	/** sorting predicate.*/
	struct byEntryPoint
	{
		bool operator()(Routine::shared_ptr lh, Routine::shared_ptr rh)
		{
			return lh->firstEntryPoint() < rh->firstEntryPoint();
		}
	};
	void straighten()
	{
		for (auto i=m_list->begin(); i!=m_list->end(); ++i) {
			(*i)->straighten();
		}
		std::sort(m_list->begin(), m_list->end(), byEntryPoint());
	}
};
/** analyze basic blocks.*/
class RoutineAnalyzer
{
	BasicBlockList::shared_ptr m_block_list;
	BasicBlockBox m_box;
	RoutineList m_routine_list;
public:
	RoutineAnalyzer(BasicBlockList::shared_ptr block_list)
			:m_block_list(block_list)
	{
		for (auto i=m_block_list->begin(); i!=m_block_list->end(); ++i) {
			m_box.push(i->second);
		}
	}
	RoutineList::shared_ptr getRoutineList()
	{
		return m_routine_list.getList();
	}
	void analyze()
	{
		while (!m_box.empty()){
			composeRoutine();
		}
		m_routine_list.straighten();
	}
	void display(std::ostream& os)const
	{
		std::cout << m_routine_list.size() << " routines found." << std::endl;
		m_routine_list.display(os);
	}
	void composeRoutine()
	{
		Routine::shared_ptr routine(new Routine);
		m_routine_list.push(routine);
		
		BasicBlockBox work_list;
		work_list.push(m_box.pop());
		while (!work_list.empty()) {
			BasicBlock::shared_ptr block = work_list.pop();
			if (!block->isValid()){
				continue;
			}
			routine->pushBlock(block);
			auto preds = block->predessorList();
			auto succs = block->successorList();
			bool is_self_loop = block->isSelfLoop();
			
			if (block->isEntryPoint()) {
				routine->pushEntryPoint(block->startAddress());
			}
			if (succs->empty() || (succs->size() == 1 && is_self_loop) ) {
				routine->pushExitPoint(block->startAddress());
			}
			for (auto i=preds->begin(); i!=preds->end(); ++i) {
				work_list.push(m_box.checkOut(*i));
			}
			for (auto i=succs->begin(); i!=succs->end(); ++i) {
				work_list.push(m_box.checkOut(*i));
			}
		}
	}
};

