#ifndef ROUTE_TABLE_H
#define ROUTE_TABLE_H

#include "net.h"
#include <vector>
#include <set>
#include <map>

#include <algorithm>
#include <functional>
#include <ext/functional>

using __gnu_cxx::compose1;

class route_table {
    protected:
	typedef std::set<Net> net_set_t;
	typedef std::map<Net, Host> net_map_t;
	typedef std::map<Host, net_set_t> route_map_t;
	route_map_t rm;
	net_map_t nm;
	net_set_t empty;
	// Helper functor that just returns the first member of a
	// pair
	template <class p>
	    class select1st {
		public:
		typename p::first_type operator()(p x) const { return x.first; }
	    };

	class contains : public std::unary_function<Net, bool> {
	    protected:
		const Net& container;   // Net that may contain test values
	    public:
		contains(const Net& c) : container(c) { }
		bool operator()(const Net& n) const {
		    return n.inside(container);
		}
	};

	class set_remover : public std::unary_function<Net, void> {
	    protected:
		net_set_t& s;
	    public:
		set_remover(net_set_t& ss) : s(ss) { }
		void operator()(const Net& n) { s.erase(n); }
	};

    public:
	route_table() : rm(), nm(), empty() { }
	void insert(const Net& dest, const Host& gw) {
	    net_map_t::iterator n = nm.find(dest);

	    if ( n == nm.end() || gw < (*n).second) {
		// never seen this network before, insert it, or it's a
		// duplicate and the next hop is a lower IP address than the
		// last attempted insert.  Keep the lower GW for consistency
		// (Remove any dupes, though)
		if (gw <  (*n).second) {
		    remove(dest, (*n).second);
		}

		route_map_t::iterator r = rm.find(gw);

		if ( r != rm.end()) {
		    (*r).second.insert(dest);
		}
		else { 
		    rm[gw] = net_set_t();
		    rm[gw].insert(dest);
		}
		nm.insert(net_map_t::value_type(dest, gw));
	    }
	}
	const net_set_t& get(const Host& gw) const { 
	    route_map_t::const_iterator r = rm.find(gw);

	    if ( r != rm.end()) return (*r).second;
	    else return empty;
	}

	void remove(const Net& dest, const Host& gw) {
	    route_map_t::iterator r = rm.find(gw);

	    if ( r != rm.end()) {
		(*r).second.erase(dest);
		// Remove the entry from the netmap
		nm.erase(dest);
		// If this gateway has no destinations, remove it from the map
		// all togther.
		if ((*r).second.empty()) 
		    rm.erase(gw);
	    }
	}

	std::ostream& print(std::ostream& f) const {
	    for (route_map_t::const_iterator i = rm.begin(); i != rm.end(); i++)
		for (net_set_t::const_iterator j = (*i).second.begin();
			j != (*i).second.end(); j++)
		    f << (*j) << " " << (*i).first << std::endl;
	    return f;
	}

	bool collision(const Net& tryit, const Host& out) const {
	    // Return true if there is a routing in rm that would be dirsupted
	    // by adding the net in tryit to the out gateway.  That is, if any
	    // destination network on another interface is inside tryit, return
	    // false.
	    for (route_map_t::const_iterator r = rm.begin(); 
		    r != rm.end(); r++) {
		if ((*r).first == out) continue;
		for (net_set_t::const_iterator n = (*r).second.begin(); 
			n != (*r).second.end(); n++) {
		    if ((*n).inside(tryit)) return true;
		}
	    }
	    return false;
	}


	void collapse() {
	    // Try to make rm as small as possible by expanding each
	    // destination network until it either conflicts with a destination
	    // network on another gateway or is a /8.
	    std::vector<Host> gateways;

	    transform(rm.begin(), rm.end(), back_inserter(gateways), 
		    select1st<route_map_t::value_type>());

	    for (std::vector<Host>::const_iterator gw = gateways.begin(); 
		    gw != gateways.end(); gw++) {
		// Try to expand all the destinations on gw.  Copy them into
		// candidates for expansion and try all the candidates.
		net_set_t candidates = get(*gw);

		while (! candidates.empty()) {

		    // Pop a value from the set.
		    Net tryit = *candidates.begin();
		    candidates.erase(tryit);

		    // While it grows, try to expand it and remove any networks
		    // it expands over.
		    bool growing = true;
		    while (growing && tryit.get_mask() > 8) {
			tryit.set_mask(tryit.get_mask() - 1);

			if ( collision(tryit, *gw) ) {
			    growing = false; 
			}
			else {
			    // Successfully got bigger.  Remove nets inside the
			    // new new from the routing table and candidate
			    // set, and insert the larger net into the table.
			    std::vector<Net> to_remove;

			    // Collect the Nets to remove
			    std::remove_copy_if(get(*gw).begin(), 
				    get(*gw).end(),
				    std::back_inserter(to_remove),
				    compose1(std::logical_not<bool>(),
					contains(tryit)));
			    // Remove 'em - calling remove makes sure the
			    // internal route_table data structures stay in
			    // sync.  This has been a bug source in the past.
			    for (std::vector<Net>::const_iterator tr = 
				    to_remove.begin(); 
				    tr != to_remove.end(); tr++) {
				remove(*tr, *gw);
				candidates.erase(*tr);
			    }
			    // New bigger candidate gots into the route_table
			    // here.
			    insert(tryit, *gw);
			}
		    }
		}
	    }
	}
};

inline std::ostream& operator<<(std::ostream& f, const route_table& rt ) {
    return rt.print(f);
}

#endif