// mbd.cpp : Defines the entry point for the console application.
//
#include <stdlib.h>
#include <crtdbg.h>
#include <sstream>
#include <stdio.h>
#include <process.h>
#include <iostream>
#include <fstream>

#include "mbd.h"

using namespace std;
using namespace stdext;

void MBD::set_ordering(MBD_VAR_ORDERING& o)
{
	order2var =o;
	var2order.resize(order2var.size());

	for (uint i=0; i<o.size(); i++)
		var2order[order2var[i]] = i;
};

void MBD::switch_parent_links(Node* n, Node* new_n)
{
	for (uint i=0; i<n->parents.size(); i++)
	{
		Node* pn = (Node*) n->parents[i];

		if (pn->hi == n)
		{
			map.erase(NodeKey(pn->lo->node_id, pn->hi->node_id, pn->var_id));
			pn->hi = new_n;
			map.insert(NodeMapPair(NodeKey(pn->lo->node_id, pn->hi->node_id, pn->var_id), NodeVal(pn)));
		}
		if (pn->lo == n)
		{
			map.erase(NodeKey(pn->lo->node_id, pn->hi->node_id, pn->var_id));
			pn->lo = new_n;
			map.insert(NodeMapPair(NodeKey(pn->lo->node_id, pn->hi->node_id, pn->var_id), NodeVal(pn)));
		}
	}
}

void MBD::change_node_sons(Node* n, Node* new_lo, Node* new_hi)
{
	map.erase(NodeKey(n->hi->node_id, n->lo->node_id, n->var_id));
	n->lo = new_lo;
	n->hi = new_hi;
	map.insert(NodeMapPair(NodeKey(n->hi->node_id, n->lo->node_id, n->var_id), NodeVal(n)));
}

uint MBD::get_different_parent_count(Node* n, uint eq_vid)
{
	uint c=0;

	for (uint i=0; i<n->parents.size(); i++)
	{
		Node *pn = (Node*)n->parents[i];

		if (pn->var_id != eq_vid)
			c++;
	}

 return c;
}

uint MBD::swap_vars(uint o1, uint o2)
{
	NodeMap::iterator i;
	uint v1,v2;
	bool nodes_swapped=true;
	uint c=0;

	v1 = MBD_ID_FROM_LOC(order2var[o1]);
	v2 = MBD_ID_FROM_LOC(order2var[o2]);

	while (nodes_swapped)
	{
		nodes_swapped=false;
	for (i=map.begin(); i!=map.end(); i++)
	{
		Node* n = i->second.node;
		Node* lo = (Node*)i->first.lo_node_id;
		Node* hi = (Node*)i->first.hi_node_id;
		c++;

		if (n->var_id == v1)
		{
			if ((lo->var_id == v2) && (hi->var_id == v2))// remove 3 old nodes - create 3 new nodes
			{
				Node *l_h,*l_l,*h_l,*h_h;
				Node *new_n,*new_l,*new_h;

				l_l = lo->lo; l_h = lo->hi;
				h_l = hi->lo; h_h = hi->hi;

				// create new nodes
				new_l = get_node(v1, lo->lo, hi->lo);
				new_h = get_node(v1, lo->hi, hi->hi);
				new_n = get_node(v2, new_l, new_h);

				// copy parents
				new_n->parents = n->parents;
				
				// clean up (if possible)
				map.erase(NodeKey(n->lo->node_id, n->hi->node_id, n->var_id));

				switch_parent_links(n, new_n);

				if (n == root)
					root = new_n;

				lo->rem_parent(n->node_id);

				if (lo->parents.size() == 0)
				{
					lo->hi->rem_parent(lo->node_id);
					lo->lo->rem_parent(lo->node_id);
					map.erase(NodeKey(lo->lo->node_id, lo->hi->node_id, v2));
					delete lo;
				}

				hi->rem_parent(n->node_id);
				if (hi->parents.size() == 0)
				{
					hi->hi->rem_parent(hi->node_id);
					hi->lo->rem_parent(hi->node_id);
					map.erase(NodeKey(hi->lo->node_id, hi->hi->node_id, v2));
					delete hi;
				}

				i = map.begin();
				nodes_swapped=true;
			}
			else if (lo->var_id == v2)
			{
				Node *l_h,*l_l;
				Node *new_n,*new_l,*new_h;

				l_l = lo->lo; l_h = lo->hi;

				map.erase(NodeKey(lo->node_id, hi->node_id, v1));
								
				new_l = get_node(v1, l_l, hi);
				new_h = get_node(v1, l_h, hi);
				new_n = get_node(v2, new_l, new_h);

				// copy parents
				new_n->parents = n->parents;

				// link parents to new node
				switch_parent_links(n, new_n);

				if (n == root)
					root = new_n;

				hi->rem_parent(n->node_id);
				// remove links to sons of lo
				lo->rem_parent(n->node_id);

				if (lo->parents.size() == 0)
				{
					lo->hi->rem_parent(lo->node_id);
					lo->lo->rem_parent(lo->node_id);
					map.erase(NodeKey(lo->lo->node_id, lo->hi->node_id, v2));
					delete lo;
				}
				i = map.begin();
				nodes_swapped=true;
			}
			else if (hi->var_id == v2)
			{
				Node *h_h,*h_l;
				Node *new_n,*new_l,*new_h;

				h_l = hi->lo; h_h = hi->hi;

				map.erase(NodeKey(lo->node_id, hi->node_id, v1));
				
				new_l = get_node(v1, lo, hi->lo);
				new_h = get_node(v1, lo, hi->hi);
				new_n = get_node(v2, new_l, new_h);

				// copy parents
				new_n->parents = n->parents;
				// link parents to new node
				switch_parent_links(n, new_n);

				// change root node if needed
				if (n == root)
					root = new_n;

				// remove links to father of lo
				lo->rem_parent(n->node_id);
				// remove links to sons of hi
				hi->rem_parent(n->node_id);
				if (hi->parents.size() == 0)
				{
					hi->hi->rem_parent(hi->node_id);
					hi->lo->rem_parent(hi->node_id);
					map.erase(NodeKey(hi->lo->node_id, hi->hi->node_id, v2));
					delete hi;
				}
				// start from beggining
				i = map.begin();
				nodes_swapped=true;
			}
		}
	}
	}

	order2var[o1] = MBD_LOC_FROM_ID(v2);
	order2var[o2] = MBD_LOC_FROM_ID(v1);

	var2order[order2var[o1]] = o1;
	var2order[order2var[o2]] = o2;

 return 0;
}


bool MBD::is_in_map(uint nid)
{
	NodeMap::iterator i;

	for (i=map.begin(); i!=map.end(); i++)
	{
		if (i->second.node->node_id == nid)
			return true;
	}

	return false;
}

uint MBD::check_integrity()
{
	NodeMap::iterator i;

	for (i=map.begin(); i!=map.end(); i++)
	{
		Node* n = i->second.node;
		Node* nlo = (Node*)i->first.lo_node_id;
		Node* nhi = (Node*)i->first.hi_node_id;

		if (nlo->node_id==nhi->node_id)
			cout << "lo==hi" << endl;
		//if (((n->var_id >= nlo->var_id) && !nlo->is_term()) || ((n->var_id >= nhi->var_id) && !nhi->is_term()))
		//	cout << "var higher" << endl;
		if ((!nlo->is_parent(n->node_id)) || (!nhi->is_parent(n->node_id)))
		{
			cout << "not parent" << endl;
			//save_to_dot("not_par.dot");
		}
		if ((!is_in_map(nlo->node_id)&&(!nlo->is_term())) || ((!is_in_map(nhi->node_id))&&(!nhi->is_term())))
		{
			cout << "not in map" << endl;
			save_to_dot("not_par.dot");
		}

		for (uint i2=0; i2<n->parents.size(); i2++)
		{
			if (!is_in_map(n->parents[i2]))
				cout << "no - parent not in map - NID: "<< n->parents[i2] << "; VID: "<< ((Node*)n->parents[i2])->var_id << endl;
		}
		for (uint i2=0; i2<nlo->parents.size(); i2++)
		{
			if (!is_in_map(nlo->parents[i2]))
				cout << "lo - parent not in map - NID: "<< nlo->parents[i2] << "; VID: "<< ((Node*)nlo->parents[i2])->var_id << endl;
		}
		for (uint i2=0; i2<nhi->parents.size(); i2++)
		{
			if (!is_in_map(nhi->parents[i2]))
				cout << "hi - parent not in map - NID: "<< nhi->parents[i2] << "; VID: "<< ((Node*)nhi->parents[i2])->var_id << endl;
		}
	}

	return 0;
}

Node* MBD::get_node(uint vid, Node* lo, Node* hi)
{
	Node *t;
	NodeMap::const_iterator it;

	if (lo->node_id == hi->node_id)
	{
		return lo;
	}

	if (map.end() != (it = map.find(NodeKey(lo->node_id, hi->node_id, vid))))
	{
		t = it->second.node;
	}
	else
	{
		t = new Node(vid, hi, lo);
		
		lo->parents.push_back(t->node_id);
		hi->parents.push_back(t->node_id);

		map.insert(NodeMapPair(NodeKey(lo->node_id, hi->node_id, vid), NodeVal(t)));
	}

 return t;
}

uint MBD::cleanup(Node* d)
{
	if ((d != NULL) && (!d->is_term()))
	{
		d->hi->rem_parent(d->node_id);
		if (d->hi->parents.size() == 0)
			cleanup(d->hi);

		d->lo->rem_parent(d->node_id);
		if (d->lo->parents.size() == 0)
			cleanup(d->lo);

		if (d->parents.size() == 0)
			delete d;
	}
 
 return MBD_ERROR___OK;
}


uint MBD::cleanup()
{
	NodeMap::iterator i;
	for (i=map.begin(); i!=map.end(); i++)
	{
		delete i->second.node;
	}
	//cleanup(root);
	map.clear();
 
 return MBD_ERROR___OK;
}

MBD::MBD(uint in, MBD_VAR_ORDERING o)
{
	root=NULL;
	term0 = new Node(TERM_0);
	term1 = new Node(TERM_1);
	termX = new Node(TERM_X);
	in_num=in;

	set_ordering(o);
}

MBD::MBD(uint in)
{
	root=NULL;
	term0 = new Node(TERM_0);
	term1 = new Node(TERM_1);
	termX = new Node(TERM_X);
	in_num=in;

	for (uint i=0; i<in_num; i++)
	{
		order2var.push_back(i);
		var2order.push_back(i);
	}
}

MBD::~MBD()
{
	cleanup();
	delete term0;
	delete term1;
	delete termX;
}

void MBD::get_pla(PLA& pla, Node* n)
{
	PLA pla_lo(in_num,1), pla_hi(in_num,1);

	if (n->lo->is_term() && (n->lo->var_id == TERM_1))
		pla_lo.rows.push_back(PLA_Row(in_num,1));
	else if (!n->lo->is_term()) get_pla(pla_lo, n->lo);
	
	if (n->hi->is_term() && (n->hi->var_id == TERM_1))
		pla_hi.rows.push_back(PLA_Row(in_num,1));
	else if (!n->hi->is_term()) get_pla(pla_hi, n->hi);

	pla_lo.and_var(MBD_LOC_FROM_ID(n->var_id), TERM_0);
	pla_hi.and_var(MBD_LOC_FROM_ID(n->var_id), TERM_1);

	pla.or_pla(pla_lo);
	pla.or_pla(pla_hi);

	string s = "espresso.exe -Dexact hlu01.pla > hlu02.pla";
	pla.save("hlu01.pla");
	system(s.data());
	pla.clear();
	pla.load("hlu02.pla");
}

void MBD::get_pla(PLA& pla)
{
	pla.i_num = in_num;
	pla.o_num = 1;
	get_pla(pla, root);
}

uint MBD::get_output(Node* d, PLA_Row& row)
{
	if (d->is_term())
		return d->var_id;

	if (row.inputs[MBD_LOC_FROM_ID(d->var_id)] == TERM_0)
		return get_output(d->lo, row);
	else return get_output(d->hi, row);

 return -1;
}

//uint get_output(Node* d, PLA_Row& row)
//{
//	if (d->is_term())
//		return d->var_id;
//
//	if (row.inputs[MBD_LOC_FROM_ID(d->var_id)] == TERM_0)
//		return get_output(d->lo, row);
//	else return get_output(d->hi, row);
//
//	return -1;
//}
//
//Node* MBD::apply_OR(Node* d1, Node* d2)
//{
//	Node* t_lo,*t_hi;//, *t;
//	NodeMap::const_iterator it;
//
//	if (d1->is_term() && d2->is_term())
//	{
//		if ((d1->var_id == TERM_1) || (d2->var_id == TERM_1))
//			return term1;
//		else if ((d1->var_id == TERM_X) || (d2->var_id == TERM_X))
//			return termX;
//		else
//			return term0;
//	}
//
//	if (d1->var_id == d2->var_id)
//	{
//		t_lo = apply_OR(d1->lo, d2->lo);
//		t_hi = apply_OR(d1->hi, d2->hi);
//		return get_node(d1->var_id, t_lo, t_hi);
//	}
//	else //if (d1->id < d1->id)
//	{
//		if (d1->var_id > d2->var_id)
//			{t_lo = d1; d1 = d2; d2 = t_lo;}
//
//		if (d1->is_term())
//		{
//			if (d1->var_id == TERM_1)
//			{
//				return term1;
//			}
//			else if (d1->var_id == TERM_0)
//			{
//				t_lo = apply_OR(term0, d2->lo);
//				t_hi = apply_OR(term0, d2->hi);
//
//				return get_node(d2->var_id, t_lo, t_hi);
//			}
//			else
//			{
//				t_lo = apply_OR(d1, d2->lo);
//				t_hi = apply_OR(d1, d2->hi);
//				return get_node(d1->var_id, t_lo, t_hi);
//			}
//		}
//		else
//		{
//			t_lo = apply_OR(d1->lo, d2);
//			t_hi = apply_OR(d1->hi, d2);
//			return get_node(d1->var_id, t_lo, t_hi);
//		}
//	}
//
//	return NULL;
//}
//
//Node* MBD::apply(Node *d1, Node *d2, MBD_OP_Type op)
//{
//	if (op == OP_OR)
//		return apply_OR(d1, d2);
//
//	return NULL;
//}


Node* MBD::add_var_to_minterm(PLA_Row& row, uint vpos)
{
	Node *lo,*hi;

	if (vpos == row.inputs.size())
	{
		if (row.outputs[0] == TERM_X)
			return termX;
		else if (row.outputs[0] == TERM_1)
			return term1;
	}

	if (row.inputs[order2var[vpos]] == TERM_X)
		return add_var_to_minterm(row, vpos+1);

	if (row.inputs[order2var[vpos]] == TERM_0)
	{
		lo = add_var_to_minterm(row, vpos+1);
		hi = term0;
	}
	else
	{
		hi = add_var_to_minterm(row, vpos+1);
		lo = term0;
	}

 return get_node(MBD_ID_FROM_LOC(order2var[vpos]), lo, hi);
}

uint MBD::load_pla_row(PLA_Row& row)
{
	cleanup();
	root = add_var_to_minterm(row,0);
	return MBD_ERROR___OK;
}

//uint MBD::reduce(uint start_var)
//{
//	Node* new_root;
//	map.clear();
//	new_root = reduce(start_var, root);
//	delete root;
//	root = new_root;
//
// return 0;
//}
//
//Node* MBD::reduce(uint start_var, Node* n)
//{
//	bool changed = true;
//	uint i=0;
//	uint cvar = start_var;
//
//	while (!changed)
//	{
//		changed = false;
//		//start_again:
//		for (NodeMap::iterator it=map.begin(); it != map.end(); it++)
//		{
//			if (it->second.node->hi->node_id == it->second.node->lo->node_id)
//			{
//				switch_parent_links(it->second.node, it->second.node->lo);
//				it = map.erase(it);
//				changed = true;
//			}
//			else
//			{
//			}
//		}
//	}
//
//	return 0;
//}

uint MBDLIB::reduce(MBD** mbd_dst, MBD* mbd_src)
{
	MBD mbd_hlp(mbd_src->in_num);

	mbd_hlp.set_root(mbd_hlp.term0);
	(*mbd_dst)->set_root(apply_OR(*mbd_dst, mbd_src->get_root(), mbd_hlp.term0));

 return 0;
}

uint MBDLIB::get_output(Node* d, PLA_Row& row)
{
	if (d->is_term())
		return d->var_id;

	if (row.inputs[MBD_LOC_FROM_ID(d->var_id)] == TERM_0)
		return get_output(d->lo, row);
	else return get_output(d->hi, row);

	return -1;
}

struct x_subst_posibility
{
	uint node;
	vector<uint> pos;
};


uint MBDLIB::minimize_X(MBD** mbd_d)
{
	NodeMap::iterator i;
	uint x_num=0;
	uint x_0=0;
	MBD* mbd = *mbd_d;

	if (x_subst_method == MBD_MIN_X_SUBST_METHOD___BROTHER)
	{
		for (i=mbd->map.begin(); i!=mbd->map.end(); i++)
		{
			if ((i->first.hi_node_id==mbd->termX->node_id) || (i->first.lo_node_id==mbd->termX->node_id))
			{
				if (i->first.hi_node_id==mbd->termX->node_id)
					i->second.node->hi = i->second.node->lo;
				else i->second.node->lo = i->second.node->hi;
				x_num++;
			}
		}
	}
	else if (x_subst_method == MBD_MIN_X_SUBST_METHOD___RAND_NODE)
	{
		vector<x_subst_posibility> subs;
		for (i=mbd->map.begin(); i!=mbd->map.end(); i++)
		{
			x_subst_posibility xpos;

			if ((i->first.hi_node_id==mbd->termX->node_id) || (i->first.lo_node_id==mbd->termX->node_id))
			{
				NodeMap::iterator i2;
				uint n=0;
				uint par_node,son_node;

				if (i->first.hi_node_id==mbd->termX->node_id)
					son_node = i->first.lo_node_id;
				else son_node = i->first.hi_node_id;

				par_node = i->second.node->node_id;

				xpos.node = par_node;

				x_num++;
				
				for (i2=mbd->map.begin(); i2!=mbd->map.end(); i2++)
				{
					if (((i2->first.hi_node_id==son_node) || (i2->first.lo_node_id==son_node)) 
						&& (par_node != i2->second.node->node_id) && (i->first.var_id == i2->second.node->var_id))
					{
						if ((i2->first.hi_node_id==son_node) && (i2->first.lo_node_id != ((uint)mbd->termX)))
							 xpos.pos.push_back(i2->first.hi_node_id);
						else if (i2->first.hi_node_id!=((uint)mbd->termX))
							xpos.pos.push_back(i2->first.lo_node_id);
						n++;
					}
				}

				if (n==0)x_0++;
				//cout << n << endl;

				subs.push_back(xpos);
			}
		}
		
		srand( (unsigned)time( NULL ) );

		for (uint n=0; n<subs.size() ;n++)
		{
			Node* tmp = (Node*)subs[n].node;

			if (subs[n].pos.size() == 0)
			{
				if (tmp->hi==mbd->termX)
					tmp->hi=tmp->lo;
				else tmp->lo = tmp->hi;
			}
			else
			{
				uint p = (uint) (rand() % subs[n].pos.size());
				if (tmp->hi == mbd->termX)
					tmp->hi = (Node*)subs[n].pos[p];
				else
					tmp->lo = (Node*) subs[n].pos[p];
			}
		}
	}

	MBD* mbd_dst = new MBD(mbd->in_num,mbd->order2var);

	reduce(&mbd_dst, mbd);
	delete mbd;

	*mbd_d = mbd_dst;

	return 0;
}


uint MBDLIB::copy(MBD** dst, MBD* src)
{
	MBD* t = new MBD(src->in_num, src->order2var);
	t->root = t->term0;
	*dst = new MBD(src->in_num, src->order2var);
	(*dst)->root = apply_OR(*dst, src->get_root(), t->get_root());

	return 0;
}

bool goes_to_x(Node* d)
{
	if (d->is_term())
	{
		if (d->var_id == TERM_X)
			return true;
		return false;
	}
	
	return (goes_to_x(d->lo) || goes_to_x(d->hi));
}

Node* MBDLIB::apply_OR(MBD* dest, Node* d1, Node* d2)
{
	Node* t_lo,*t_hi;//, *t;
	NodeMap::const_iterator it;

	if (d1->is_term() && d2->is_term())
	{
		if ((d1->var_id == TERM_1) || (d2->var_id == TERM_1))
			return dest->term1;
		else if ((d1->var_id == TERM_X) || (d2->var_id == TERM_X))
			return dest->termX;
		else
			return dest->term0;
	}

	if (d1->var_id == d2->var_id)
	{
		t_lo = apply_OR(dest, d1->lo, d2->lo);
		t_hi = apply_OR(dest, d1->hi, d2->hi);
		return dest->get_node(d1->var_id, t_lo, t_hi);
	}
	else //if (d1->id < d1->id)
	{
		if (d1->is_term() || d2->is_term())
		{
			if (d1->var_id > d2->var_id)
				{t_lo = d1; d1 = d2; d2 = t_lo;}

			if (d1->var_id == TERM_1)
			{
				if (goes_to_x(d2))
				{
					// Don't care priority!!!
					t_lo = apply_OR(dest, dest->term0, d2);
					t_hi = apply_OR(dest, dest->term0, d2);

					return dest->get_node(d2->var_id, t_lo, t_hi);
				}
				else return dest->term1;
			}
			else if (d1->var_id == TERM_0)
			{
				t_lo = apply_OR(dest, dest->term0, d2->lo);
				t_hi = apply_OR(dest, dest->term0, d2->hi);

				return dest->get_node(d2->var_id, t_lo, t_hi);
			}
			else //if (d1->var_id == TERM_X)
			{
				// Don't care priority!!!
				return dest->termX;
				//t_lo = apply_OR(dest, d1, d2->lo);
				//t_hi = apply_OR(dest, d1, d2->hi);
				//return dest->get_node(d2->var_id, t_lo, t_hi);
			}
		}
		else
		{
			if (dest->var2order[MBD_LOC_FROM_ID(d1->var_id)] > dest->var2order[MBD_LOC_FROM_ID(d2->var_id)])
				{t_lo = d1; d1 = d2; d2 = t_lo;}

			t_lo = apply_OR(dest, d1->lo, d2);
			t_hi = apply_OR(dest, d1->hi, d2);
			return dest->get_node(d1->var_id, t_lo, t_hi);
		}
	}

	return NULL;
}

void MBDLIB::apply(MBD** dest, MBD* s1, MBD* s2, MBD_OP_Type op)
{
	*dest = new MBD(s1->in_num, s1->order2var);
	(*dest)->root = apply_OR(*dest, s1->root, s2->root);
}

uint MBDLIB::get_span(PLA* pt, MBD_VAR_ORDERING& o)
{
	int max_o, min_o, span=0;
	
	if (o.size() != pt->i_num)
		return 0;
	
	for (uint r=0; r<pt->rows.size(); r++)
	{
		if (pt->rows[r].outputs[0] == TERM_0)
			continue;

		max_o = min_o = -1;
		for (uint p=0; p < o.size(); p++)
		{
			if (pt->rows[r].inputs[o[p]] != TERM_X)
			{
				if (min_o == -1)
					min_o = p;
				max_o = p;
			}
		}
		span += max_o-min_o;
	}

 return span;
}

uint MBDLIB::get_cut(PLA* pt, MBD_VAR_ORDERING& o)
{
	// not implemented 
	return 0;
}

MBD_VAR_ORDERING MBDLIB::ord_force(PLA* pla, MBD_VAR_ORDERING* io)
{
	MBD_VAR_ORDERING no,to;
	vector<float> cog;
	vector<order_for_var_from_cog> neworder;
	uint span,old_span;

	if (io)
		no = *io;
	else
	{
		no = ord_random(pla);
	}
	
	span = get_span(pla,no);
	
	while (1)
	{
		float t_cog;
		cog.clear();
		neworder.clear();

		// get centers of gravity for each hyperedge (term)
		for (uint r=0; r<pla->rows.size(); r++)
		{
			if (pla->rows[r].outputs[0] == TERM_0)
			{
				t_cog = .0;
			}
			else
			{
				float sum,num;
				num = sum = .0;
				for (uint p=0; p < no.size(); p++)
				{
					if (pla->rows[r].inputs[p] != TERM_X)
					{

						sum += float(no[p]+1);
						num++;
					}
				}
				t_cog = sum/num;
			}

			cog.push_back(t_cog);
		}

		for (uint v=0; v<no.size(); v++)
		{
			float cog_cnt;
			float cog_num;
			cog_cnt = 0;
			cog_num = 0;
			order_for_var_from_cog ofvfc;

			for (uint r=0; r<pla->rows.size(); r++)
			{
				if (pla->rows[r].outputs[0] == TERM_0)
					continue;

				if (pla->rows[r].inputs[v] != TERM_X)
				{
					cog_cnt += cog[r];
					cog_num++;
				}
			}

			ofvfc.var_id = v;
			ofvfc.cog_val = cog_num ? cog_cnt/cog_num : 0;
			neworder.push_back(ofvfc);
		}

		sort(neworder.begin(),neworder.end());

		to.clear();
		to.resize(neworder.size());

		for (uint i=0; i<neworder.size(); i++)
		{
			to[neworder[i].var_id] = i;
		}

		old_span = span;
		span = get_span(pla,to);

		if (span < old_span)
		{
			no = to;
		}	
		else
		{
			break;
		}
	}

	return no;
}


MBD_VAR_ORDERING MBDLIB::ord_histogram(PLA* pla)
{
	PLA_Input_Var_Histogram hst;
	MBD_VAR_ORDERING o,io;

	pla->get_histogram(hst);

	o.resize(pla->i_num);
	io.resize(pla->i_num);

	for (uint i=0; i<hst.size(); i++)
	{
		o[i] = hst[i].id;
		io[hst[i].id] = i;
	}

	// BNS
	for (uint i=0; i<o.size()-1; i++)
	{
		uint ngb_o = io[hst[i].bngb];

		if ((hst[ngb_o].num == hst[i].num) && (ngb_o != (i+1)) && (hst[i].num))
		{
			PLA_Input_Var_Histogram_Item t = hst[ngb_o];

			if (ngb_o > i)
			{
				hst[ngb_o] = hst[i+1];
				hst[i+1] = t;
				io[hst[i+1].id] = i+1;
				io[hst[ngb_o].id] = ngb_o;
			}
			else
			{
				hst.erase(hst.begin()+ngb_o);
				hst.insert(hst.begin()+i,t);
				for (uint i=0; i<hst.size(); i++)
					io[hst[i].id] = i;
			}
		}
	}

	for (uint i=0; i<hst.size(); i++)
		o[i] = hst[i].id;

	return o;
}


MBD_VAR_ORDERING MBDLIB::order_vars_static(PLA* pla, MBD_VAR_ORDERING* io)
{
	switch (static_ordering_method)
	{
		case MBD_STATIC_ORDERING_METHOD___FORCE:
			return ord_force(pla, io);
		case MBD_STATIC_ORDERING_METHOD___STAT:
			return ord_histogram(pla);
		case MBD_STATIC_ORDERING_METHOD___RANDOM:
			return ord_random(pla);
		case MBD_STATIC_ORDERING_METHOD___NONE:
		default:
			if (io == NULL)
			{
				MBD_VAR_ORDERING o;
				for (uint i=0; i<pla->i_num; i++)
					o.push_back(i);
				return o;
			}
			else return *io;
	}
}

uint MBDLIB::order_vars_dynamic(MBD* mbd)
{
	bool cost_changed = true;
	uint cost = mbd->get_node_count();
	uint totalcost = 0;

	MBD_VAR_ORDERING o = mbd->order2var;
	
	while (cost_changed)
	{
		cost_changed = false;

		for (uint i=0; i < mbd->in_num-1; i++)
		{
			MBD_VAR_ORDERING o1,o2;
			o1 = mbd->order2var;
			mbd->swap_vars(i, i+1);
			o2 = mbd->order2var;
			
			if (mbd->get_node_count() < cost)
			{
				cost = mbd->get_node_count();
				totalcost += cost;
				
				cost_changed = true;
			}
			else
			{
				mbd->swap_vars(i, i+1);
			}
		}
	}

	return totalcost;
}

uint MBDLIB::verify_pla(PLA* pla, MBD* mbd)
{
	for (uint i=0; i<pla->rows.size(); i++)
	{
		if ((pla->rows[i].outputs[0] != TERM_0) && (pla->rows[i].outputs[0] != TERM_X))
			if (get_output(mbd->get_root(),pla->rows[i]) != pla->rows[i].outputs[0])
				cout<< i+1 <<") ERROR" << endl;
	}
	return 0;
}

uint MBDLIB::load_from_pla(PLA* pla, MBD** mbd, MBD_VAR_ORDERING& ord)
{
	MBD* t,*t_new,*t_old;
	uint ret=0;

	t_old = new MBD(pla->i_num, ord);
	t_old->set_root(t_old->term0);
	t_old->set_in_num(pla->i_num);

	for (uint i=0; i<pla->rows.size(); i++)
	{
		if (pla->rows[i].outputs[0] != TERM_0)
		{
			t = new MBD(pla->i_num, ord);

			t->load_pla_row(pla->rows[i]);
			apply(&t_new, t_old, t, OP_OR);

			delete t_old;
			t_old = t_new;
			delete t;
		}
	}

	*mbd = t_new;

	ret = MBD_ERROR___OK;

	return ret;
}

uint MBDLIB::load_from_pla(PLA* pla, MBD** mbd)
{
	uint ret=0;
	MBD_VAR_ORDERING ord;

	ord = order_vars_static(pla);

	ret = load_from_pla(pla, mbd, ord);
 
	return ret;
}


uint MBDLIB::load_from_pla(char* filename, MBD** mbd, PLA** pla)
{
	uint ret=0;
 
	*pla = new PLA();

	if (PLA_TABLE_ERROR___OK != (*pla)->load(filename))
	{
		ret = MBD_ERROR___CANT_LOAD_FILE;
		delete (*pla);
		(*pla) = NULL;
		goto MBD_LOAD_ERROR;
	}

	ret = load_from_pla(*pla, mbd);

MBD_LOAD_ERROR:;
	return ret;
}


MBDLIB::MBDLIB()
{
	order_vars_after_load = true;
	static_ordering_method = MBD_STATIC_ORDERING_METHOD___NONE;
	x_subst_method = MBD_MIN_X_SUBST_METHOD___NONE;
}

void MBDLIB::print_ordering(MBD_VAR_ORDERING o)
{
	for (uint i=0; i<o.size(); i++)
	{
		cout << i <<" - "<<o[i]<<endl;
	}
}

MBD_VAR_ORDERING MBDLIB::ord_random(PLA* pla)
{
	MBD_VAR_ORDERING o,t;
	uint inum=pla->i_num; 

	for (uint i=0; i<inum; i++)
	{
		t.push_back(i);
	}

	srand( (unsigned)time( NULL ) );
	o.resize(inum);

	for (uint i=0; i<inum; i++)
	{
		while(1)
		{
			uint ind = rand()%inum;
			if (t[ind] < inum)
			{
				o[i] = t[ind];
				t[ind] = inum;
				break;
			}
		}
	}

	return o;
}


uint MBDLIB::get_terms_count(MBD* s)
{
	return get_terms_count(s->get_root());
}

uint MBDLIB::get_terms_count(Node* n)
{
	if (n->is_term())
	{
		if ((n->var_id == TERM_1) || (n->var_id == TERM_1))
			return 1;
		return 0;
	}
	else return (get_terms_count(n->hi) + get_terms_count(n->lo));
}

struct bdd2dot
{
	uint vid,nid;
	uint lo_id;
	uint hi_id;

	bool operator < (const bdd2dot& x)
	{
		return vid < x.vid;
	}
};

void MBD::save_to_dot(char* filename)
{
	NodeMap::iterator i;
	vector<bdd2dot> d;
	MBD* mbd=this;

	for (i=mbd->map.begin(); i!=mbd->map.end(); i++)
	{
		bdd2dot t;
		t.vid = i->second.node->var_id;
		t.nid = i->second.node->node_id;
		t.hi_id = (uint)i->second.node->hi;
		t.lo_id = (uint)i->second.node->lo;
		d.push_back(t);
	}

	sort(d.begin(), d.end());

	string s;

	s = "digraph BDD {\n";
	s += "size=\"7,11\"\n\n";

	s += "node [fontname=\"Helvetica\",fontsize=\"20\",height=\"0.3\",width=\"0.6\",color=black,style=unfilled,shape=box]\n";
	s += "\t{ rank=same; ";
	if (mbd->term1->parents.size() > 0)
		s += "\t\t "+to_string(mbd->term1->node_id)+" [label=\"1\"];";
	if (mbd->term0->parents.size() > 0)
		s += "\t\t "+to_string(mbd->term0->node_id)+" [label=\"0\"];";
	if (mbd->termX->parents.size() > 0)
		s += "\t\t "+to_string(mbd->termX->node_id)+" [label=\"X\"];";
	s += "\t}\n\n";

	s += "node [fontname=\"Helvetica\",fontsize=\"20\",height=\"0.3\",width=\"0.5\",color=black,style=unfilled,shape=circle]\n";
	s += "\n";

	for (uint i=0; i<d.size(); i++)
	{
		//Node* n = i->second.node;

		s += "\t{ rank=same;\n";

		while (true)
		{
			//<tspan>x<tspan baseline-shift="-25%" font-size="80%">0</tspan></tspan>
			s += "\t\t"+to_string(d[i].nid) + " [label=\"x" + to_string(MBD_LOC_FROM_ID(d[i].vid)) + "\"];\n";
			if (((i+1)<d.size()) && (d[i+1].vid == d[i].vid))
				i++;
			else break;
		}

		s += "\t}\n\n";
	}

	//s += "";

	s += "edge [arrowsize=\"1.0\",fontname=\"Helvetica\",fontsize=\"8\"];\n";
	for (uint i=0; i<d.size(); i++)
	{
		s += "\t"+to_string(d[i].nid) + " -> " + to_string(d[i].lo_id) + " [style=dotted];\n";

		s += "\t"+to_string(d[i].nid) + " -> " + to_string(d[i].hi_id) + " [style=solid];\n";
	}

	s += "}";

	fstream f(filename, ios::out);
	f<<s;

	f.close();
}