#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <deque>
#include <iterator>

#include <getopt.h>

#include "graph.h"
#include "routing.h"

#include "net.h"
#include "route_table.h"

typedef set<string> addr_set_t;
typedef map<string, string> addr_map_t;
typedef map<string, set<string> > addr_set_map_t;

using namespace std;

// Functor called by a for_each to remove a node (address) from the graph
class node_remover : public unary_function<string, void> {
    protected:
	graph &g;
    public:
	node_remover(graph& gg) : g(gg) { }
	void operator()(const string &s) { g.remove_node(s); }
};

// Functor called by for_each to remove a node (leaf) from the given set.
class leaf_remover : public unary_function<string, void> {
    protected:
	addr_set_t &l;
    public:
	leaf_remover(addr_set_t& ll) : l(ll) { }
	void operator()(const string &s) { l.erase(s); }
};

// Functor called by for_each to print a node's forwarding table to a file with
// the name of the node (a parameter) in the outdir specified at object
// creation time.  Also in the object are sets of destination objects, a map
// from node name to addresses, and the map from interfaces to leaf nodes.  The
// full routing matrix is also a parameter at creation time.
class node_writer : public unary_function<string, void> {
    protected:
	addr_set_t& addrs;	    // All destination addresses
	addr_set_map_t& node_addrs; // Node name to address set map
	addr_set_map_t& children;   // Leaf nodes attached to an interface
	routing& r;		    // The routing
	const string& outdir;	    // The output directory
	bool compress;		    // True if we are compressing tables
	ostream *verbose;	    // Pointer to verbouse output stream
	mutable int num;	    // Number of calls to this functor
    public:
	node_writer(addr_set_t& a, addr_set_map_t& na, addr_set_map_t& c,
	    routing& rr, const string& od, bool cm, ostream *v) : 
	    addrs(a), node_addrs(na), children(c), r(rr), outdir(od),
	    compress(cm), verbose(v), num(0) { }

	void operator()(const string &n) const {
	    string out_fn = outdir + "/" + n ;	    // destination filename
	    ofstream out(out_fn.c_str());	    // output stream
	    addr_set_t& my_addrs = node_addrs[n];   // this node's addresses
	    route_table rt;			    // The routes to compress

	    // Build the route table
	    for (addr_set_t::const_iterator d = addrs.begin(); 
		    d != addrs.end(); 
		    d++) {
		// Find the best route to each destination.  Because a node may
		// have multiple addresses, we have to check each outgoing
		// interface and pick the shortest.
		string src;	// outgoing interface of best route
		int best = 0;	// length of best route
		string nh;	// The next hop IP address for shortest route

		for (addr_set_t::const_iterator i = my_addrs.begin(); 
			i != my_addrs.end(); i++) {
		    if (src.empty() || r.path_cost(*i, *d) < best ) { 
			src = *i;
			best = r.path_cost(*i, *d);
		    }
		}

		// Ignore single hop paths unless not compressing.
		if (r.path_cost(src, *d) > 1 || !compress) {
		    nh = r.next_hop(src, *d);

		    if ( !nh.empty() ) {
			// Insert the nodes as the /24 containing them
			Net n(*d);
			n.set_mask(24);
			rt.insert(n, Host(nh));
		    }
		}
		else nh = *d;

		// Output children of the destination unless they are this
		// node's children and we are compressing.
		if ( my_addrs.count(*d) == 0 || !compress) {
		    addr_set_map_t::iterator c = children.find(*d);

		    if ( c != children.end()) {
			Host gw = Host(nh);
			for (addr_set_t::const_iterator i = (*c).second.begin();
				i != (*c).second.end(); i++) 
			    rt.insert(Net(*i), gw);
		    }
		}

	    }
	    // Collapse the route map (if we're compressing) and print it
	    if (compress) rt.collapse();
	    out << rt;
	    if (verbose && ++num % 10 == 0)
		*verbose << num << '\r';
	}
};

// Functor to output a leaf node's routing table.  The table has the same name
// as the node and is output into outdir.  The parent_addr map (node to parent
// address) is passed in.
class leaf_writer : public unary_function<string, void> {
    protected:
	addr_map_t& parent_addr;    // Parent address map
	addr_set_t& addrs;	    // All destination addresses
	addr_set_map_t& children;   // Leaf nodes attached to an interface
	const string& outdir;	    // The output directory
	bool compress;		    // Compress routing tables
	ostream *verbose;	    // Verbose output
	mutable int num;	    // Number of calls on this functor
    public:
	leaf_writer(addr_map_t& pa, addr_set_t& a, addr_set_map_t& c, 
		const string& od, bool cm, ostream *v ) :
	    parent_addr(pa), addrs(a), children(c), outdir(od), compress(cm),
	    verbose(v), num(0) { }
	void operator()(const string &n) const {
	    string out_fn = outdir + "/" + n;
	    ofstream out(out_fn.c_str());

	    // Compressed leaves have a single default route
	    if (compress) 
		out << "10.0.0.0/8 " << parent_addr[n] << endl;
	    else {
		// For uncompressed leaves, all thr routes go to the parent,
		// but we have to enumerate them as all addresses and the
		// children of any address with leaves.
		string my_parent = parent_addr[n];

		out << my_parent << "/32 " << my_parent << endl;
		for (addr_set_t::const_iterator d = addrs.begin(); 
			d != addrs.end(); d++) {
		    out << *d << "/32 " << my_parent << endl;

		    addr_set_map_t::iterator c = children.find(*d);
		    
		    if ( c != children.end() ) {
			for (addr_set_t::const_iterator i = (*c).second.begin();
				i != (*c).second.end(); i++) 
			    out << *i << "/32 " << my_parent << endl;
		    }
		}
	    }
	    if (verbose && ++num % 10 == 0) 
		*verbose << num << '\r';
	}
};


void parse_graph_description(graph& g, addr_set_t& nodes, addr_set_t& addrs,
	addr_set_t& leaves, addr_map_t& leaf_addr, addr_set_map_t& node_addrs,
	istream *in=0) {
    // Create the basic data structures from the input format.  The input is a
    // series of lines of the form:
    // node: addr,addr,addr
    // or
    // addr: addr,addr,addr
    //
    // The first line lists a node's interfaces and the second the
    // interconnections between addresses.  The nodes are captured in nodes and
    // leaves (a potential leaf is in both, nodes with multiple interfaces are
    // only in nodes).  Addrs is all addresses, leaf_add maps a leaf node to
    // its only address, node_addrs maps each node or leaf to its address(es).
    // g is the grahp of address interconnections.
    string line;    // Currnet line
    if (!in ) in = &cin;

    while (getline(*in, line, '\n')) {
	string::size_type p = line.find(':');	// String offsets for parsing
	string::size_type q;			// String offsets for parsing
	string name;				// Node name
	string ename;				// Edge name (an address)
	graph::node *node = 0;			// Curren graph node (address)
	bool make_node;				// True if this is a node
	addr_set_t my_addrs;			// Current set of node addrs

	if (p != string::npos) {
	    name = line.substr(0, p);
	    if (name.find_first_not_of("0123456789.") != string::npos) {
		make_node = true;
	    }
	    else {
		node = g.get_node(name);
		addrs.insert(name);
		make_node = false;
	    }
	}
	else continue;
	p += 2;
	while ( (q = line.find(',', p)) != string::npos) {
	    ename = line.substr(p, q-p);
	    if (make_node) {
		my_addrs.insert(ename);
	    }
	    else {
		g.get_node(ename);
		node->add_edge(ename, 1.0);
	    }
	    p = q+1;
	}
	ename = line.substr(p);
	if (make_node) {
	    my_addrs.insert(ename);

	    nodes.insert(name);
	    node_addrs[name] = my_addrs;
	    if (my_addrs.size() == 1) {
		// Potential leaf node.  No need to cross connect, but we do
		// need to list it and its interfaces as leaves.  We won't know
		// if it is a leaf node until we find out if it is on a lan.
		leaves.insert(name);
		leaf_addr[name] = ename;
	    }
	    else {
		// Not a leaf.  Add it to nodes and interconnect its interfaces.
		for (addr_set_t::const_iterator i = node_addrs[name].begin();
			i != node_addrs[name].end(); i ++) {
		    for (addr_set_t::const_iterator j =node_addrs[name].begin();
			    j != node_addrs[name].end(); j ++) {
			if ( *i != *j && !g.has_edge(*i, *j)) {
			    graph::node *a = g.get_node(*i);
			    g.get_node(*j);
			    a->add_edge(*j, 1.0);
			}
		    }
		}
	    }
	}
	else {
	    g.get_node(ename);
	    node->add_edge(ename, 1.0);
	}
    }
}

void trim_leaves(graph &g, addr_set_t& nodes, addr_set_t& leaves, 
	addr_map_t& leaf_addr, addr_set_t& addrs, addr_map_t& parent_addr, 
	addr_set_map_t& children) {
    // Leaves is the set of nodes that may be leaves - nodes connected to one
    // node.  Walk that set, eliminate false positives, and for the real leaves
    // remove them from the node set, the addr_set and set their parent_addr
    // (the upstream interface), and add the leaf to the parent interface's
    // children map.

    addr_set_t graph_remove;	// nodes to remove from the graph
    addr_set_t leaf_remove;	// leaves to remove from the leaves set.

    for (addr_set_t::const_iterator l = leaves.begin(); l != leaves.end(); 
	    l++) {
	string la = leaf_addr[*l];	    // leaf address
	graph::node *ln = g.get_node(la);   // leaf address node
	if (ln-> degree() == 1 ) {
	    graph::edge e = *ln->begin();	    // edge
	    string pa = e.get_node_name();	    // parent address
	    addr_set_map_t::iterator c = children.find(pa); // children entry 

	    parent_addr[*l] = pa;
	    if (c != children.end() ) 
		(*c).second.insert(la);
	    else {
		children[pa] = addr_set_t();
		children[pa].insert(la);
	    }
	    // This is a confirmed leaf, so get it out of nodes.
	    nodes.erase(*l);
	    // NB cannot remove parent address as it may be a destination from
	    // other palces in the net.
	    graph_remove.insert(la);
	    addrs.erase(la);
	}
	else {
	    // Not a leaf after all, leave it in nodes and remove it from
	    // leaves.
	    leaf_remove.insert(*l);
	}

    }
    // Clean up the data structures we've been pulling things from.
    for_each(graph_remove.begin(), graph_remove.end(), node_remover(g));
    for_each(leaf_remove.begin(), leaf_remove.end(), leaf_remover(leaves));
    g.fix_edges();
}
enum { OUTPUT_OPT='o', DEBUG_OPT='d', NOCOMPRESS_OPT='C', INPUT_OPT='f'};
struct option opts[] = {
    { "output", required_argument, 0, OUTPUT_OPT}, 
    { "input", required_argument, 0, INPUT_OPT}, 
    { "debug", no_argument, 0, DEBUG_OPT}, 
    { "uncompressed", required_argument, 0, NOCOMPRESS_OPT}, 
};

void fatal(const string& my_name) {
    cerr << "Usage: " << my_name << 
	": [options] [outputdir [filename]]" << endl;
    exit(20);
}


int main(int argc, char**argv) {
    addr_set_t nodes;		// Set of nodenames (not addresses)
    addr_set_t addrs;		// All valid destination addresses
    addr_set_t leaves;		// Leaf nodes
    addr_map_t parent_addr;	// Map from leaf address to parent address
    addr_map_t leaf_addr;	// Map from leaf node name to leaf address
    addr_set_map_t node_addrs;	// Map from each node to its addresses
    addr_set_map_t children;	// Map from a parent addess to its 
				// leaf children
    graph g;			// Graph represention
    string my_name = argv[0];	// The name of the program
    string outdir;		// Output directory
    string uncompressed_dir;	// Output for uncompressed routing tables
    int fl;			// Option parsing
    bool debug=false;		// True for debugging output
    ifstream *inf = 0;		// Input file, if any

    while (( fl = getopt_long(argc, argv, "o:dC:", opts, 0)) != -1) {
	switch (fl) {
	    case DEBUG_OPT:
		debug = true;
		break;
	    case OUTPUT_OPT:
		outdir = optarg;
		break;
	    case INPUT_OPT:
		if (!(inf = new ifstream(optarg))) {
		    cerr << "Cannot open " << optarg << endl;
		    fatal(my_name);
		}
		break;
	    case NOCOMPRESS_OPT:
		uncompressed_dir=optarg;
		break;
	}
    }
    argc -= optind;
    argv += optind;
    if (argc > 0 && outdir.empty()) {
	outdir = argv[0];
	argc--; argv++;
    }
    if (argc > 0 && !inf) {
	if (!(inf = new ifstream(optarg))) {
	    cerr << "Cannot open " << optarg << endl;
	    fatal(my_name);
	}
	argc--; argv++;
    }

    if (outdir.empty()) fatal(my_name);

    parse_graph_description(g, nodes, addrs, leaves, leaf_addr, node_addrs,inf);
    trim_leaves(g, nodes, leaves, leaf_addr, addrs, parent_addr, children);

    routing r = routing(g, debug ? &cerr: 0);

    for_each(nodes.begin(), nodes.end(), 
	    node_writer(addrs, node_addrs, children, r, outdir, true,
		debug ? &cerr : 0));
    if (debug) cerr << endl;
    for_each(leaves.begin(), leaves.end(), 
	    leaf_writer(parent_addr, addrs, children, outdir, true,
		debug ? &cerr : 0));
    if (debug) cerr << endl;

    if (!uncompressed_dir.empty()) {
	for_each(nodes.begin(), nodes.end(), 
		node_writer(addrs, node_addrs, children, r, 
		    uncompressed_dir, false, debug ? &cerr : 0));
	if (debug) cerr << endl;
	for_each(leaves.begin(), leaves.end(), 
		leaf_writer(parent_addr, addrs, children, 
		    uncompressed_dir, false, debug ? &cerr : 0));
	if (debug) cerr << endl;
    }

}