#pragma once

#include "routine_list.hpp"
#include "address_list.hpp"

#include <vector>
#include <algorithm>
#include <memory>
#include <boost/shared_ptr.hpp>

/** for each block */
class DominatorList
{
public:
	typedef boost::shared_ptr<DominatorList> shared_ptr;
private:
	unsigned m_start_address;
	unsigned m_size;
	
	unsigned char* m_bytes;
	unsigned m_byte_size;
	AddressMap::shared_ptr m_id_map;
	
public:
	enum Constant {
		BIT_LENGTH = 8,
	};
	DominatorList(unsigned start_address, unsigned size,
				  AddressMap::shared_ptr to_id)
			:m_start_address(start_address),
			 m_size(size),
			 m_id_map(to_id)
	{
		m_byte_size = size/BIT_LENGTH + 1;
		m_bytes = new unsigned char[size/BIT_LENGTH + 1];
	}
	~DominatorList()
	{
		delete[] m_bytes;
	}
	void fill(bool value)
	{
		for (unsigned i=0; i<m_byte_size; ++i) {
			m_bytes[i] = value ? 0xFF : 0x0000;
		}
	}
	unsigned toID(unsigned address)const
	{
		return (*m_id_map)[address];
	}
	unsigned getIndex(unsigned id)const
	{
		return id/BIT_LENGTH;
	}
	unsigned getDigit(unsigned id)const
	{
		return id%BIT_LENGTH;
	}
	unsigned char getDigitMask(unsigned id)const
	{
		return 1 << getDigit(id);
	}
	void set(unsigned address)
	{
		unsigned id=toID(address);
		m_bytes[getIndex(id)] |= getDigitMask(id);
	}
	bool find(unsigned address)const
	{
		unsigned id=toID(address);
		return findByID(id);
	}
	bool findByID(unsigned id)const
	{
		return m_bytes[getIndex(id)] & getDigitMask(id);
	}
	unsigned value()const
	{
		unsigned result=0;
		for (unsigned i=0; i<m_byte_size; ++i) {
			for (unsigned v=m_bytes[i]; v > 0; v >>= 1) {
				result += v & 1;
			}
		}
		return result;
	}
	bool isGreaterThanOne()const
	{
		unsigned result=0;
		for (unsigned i=0; i<m_byte_size; ++i) {
			for (unsigned v=m_bytes[i]; v > 0; v >>= 1) {
				result += v & 1;
				if (result > 1) {
					return true;
				}
			}
		}
		return false;
	}
	void copy(const DominatorList& that)
	{
		for (unsigned i=0; i<m_byte_size; ++i) {
			m_bytes[i] = that.m_bytes[i];
		}
		return;
	}
	DominatorList& operator&=(const DominatorList& that)
	{
		for (unsigned i=0; i<m_byte_size; ++i) {
			m_bytes[i] &= that.m_bytes[i];
		}
		return *this;
	}
	DominatorList& operator|=(const DominatorList& that)
	{
		for (unsigned i=0; i<m_byte_size; ++i) {
			m_bytes[i] |= that.m_bytes[i];
		}
		return *this;
	}
	bool operator==(const DominatorList& that)const
	{
		for (unsigned i=0; i<m_byte_size; ++i) {
			if (m_bytes[i] != that.m_bytes[i]){
				return false;
			}
		}
		return true;
	}
	bool operator!=(const DominatorList& that)const
	{
		return !(*this == that);
	}
	void display(std::ostream& os)const
	{
		os << DecimalFormat(toID(m_start_address)).width(2) << " "
		   << HexadecimalFormat(m_start_address) << ": ";
		
		for (unsigned i=0; i<m_size; ++i) {
			if (m_bytes[i/BIT_LENGTH] & (1 << (i%BIT_LENGTH))) {
				os << DecimalFormat(i).width(2) << " ";
			}
		}
	}
	unsigned startAddress()const
	{
		return m_start_address;
	}
private:
};

/** for each routine.*/
class DominatorLattice
{
public:
	typedef boost::shared_ptr<DominatorLattice> shared_ptr;
	
	/** map address to id.*/
	AddressMap::shared_ptr  m_id_map;
	std::vector<DominatorList::shared_ptr> m_dominators;
	DominatorList::shared_ptr m_temporary;
	
	static shared_ptr create(AddressMap::shared_ptr id_map)
	{
		shared_ptr result(new DominatorLattice(id_map));
		return result;
	}
	DominatorLattice(AddressMap::shared_ptr id_map)
			:m_id_map(id_map)
	{
		unsigned size = m_id_map->size();
		m_temporary.reset(new DominatorList(0, size, m_id_map));
		for (auto i=m_id_map->begin(); i!=m_id_map->end(); ++i) {
			DominatorList::shared_ptr dom(new DominatorList(
												i->first, size, m_id_map));
			dom->fill(true);
			m_dominators.push_back(dom);
		}
	}
	/** temporary dominator list which can solve address in the block.*/
	DominatorList::shared_ptr temporary()
	{
		return m_temporary;
	}
	/** get dominator list by the address.*/
	DominatorList::shared_ptr of(unsigned address)
	{
		return m_dominators[(*m_id_map)[address]];
	}
	/** get dominator list by id.*/
	DominatorList::shared_ptr at(unsigned id)
	{
		return m_dominators[id];
	}
	unsigned size()const
	{
		return m_dominators.size();
	}
	void display(std::ostream& os) const
	{
		for (auto i=m_dominators.begin(); i!= m_dominators.end(); ++i) {
			(*i)->display(os);
			os << std::endl;
		}
	}
};
/** This worker constructs DominatorLattice.*/
class DominatorAnalyzer
{
public:
	DominatorAnalyzer()
	{
	}
	/** This class is used to collect immediate dominators.*/
	AddressMap::shared_ptr
	computeImmediateDominator(DominatorLattice::shared_ptr dominators)
	{
		AddressMap::shared_ptr immediate = AddressMap::create();
		for (unsigned i=0; i<dominators->size(); ++i) {
			DominatorList::shared_ptr former = dominators->at(i);
			unsigned last_size = 0;
			for (unsigned j=0; j<dominators->size(); ++j) {
				if (i==j || !former->findByID(j)) {
					continue;// skip self or not dominator
				}
				DominatorList::shared_ptr latter = dominators->at(j);
				if (latter->value() > last_size) {
					(*immediate)[former->startAddress()]
							=latter->startAddress();
				}
			}
		}
		return immediate;
	}
	DominatorLattice::shared_ptr
	getDominatorLattice(
			Routine::shared_ptr routine) 
	{
		BasicBlockList::shared_ptr block_list = routine->blockList();
		AddressMap::shared_ptr id_map = AddressMap::create();
		unsigned count = 0;
		for (auto i=block_list->begin(); i!=block_list->end(); ++i) {
			(*id_map)[i->first] = count;
			++count;
		}
		
		DominatorLattice::shared_ptr dominators
				= DominatorLattice::create(id_map);

		unsigned entry_point = Routine::FAKE_ENTRY;
		auto d = dominators->of(entry_point);
		d->fill(false);
		d->set(entry_point);
		
		bool changed;
		do {
			changed = false;
			for (auto i=block_list->begin(); i!=block_list->end(); ++i) {
				unsigned current = i->first;
				auto current_dom = dominators->of(i->first);
				
				if (!current_dom->isGreaterThanOne()) {
					continue;
				}
				
				auto adjacent = i->second->predessorList();
				for (auto j= adjacent->begin(); j != adjacent->end(); ++j) {
					auto last = dominators->temporary();
					last->copy(*current_dom);
					*current_dom &= *(dominators->of(*j));
					current_dom->set(current);
					if (*current_dom != *last) {
						changed = true;
					}
				}
			}
		} while (changed);

		return dominators;
	}
};
