#include <map>
#include <list>
#include <string>
#include <functional>
#include <iostream>

// -------------------------------------------------------------------
// Three example types, just enough to effectively simulate
// the original (compile-time) problem.
struct Edge {
    Edge() : eName("") {}
    Edge(const std::string& name) : eName(name) {}
    std::string eName;
};
typedef std::string edgeDescriptor;
typedef std::map<edgeDescriptor, Edge> Graph;

// -------------------------------------------------------------------
// The SortByName template-struct functor type.
template <typename Graph, typename edgeDescriptor>
struct SortByName : public std::binary_function<edgeDescriptor, edgeDescriptor, bool>
{
    bool operator()(const Graph& g, const edgeDescriptor& a, const edgeDescriptor& b)
    {
        return g[a].eName < g[b].eName;
    }
};

// -------------------------------------------------------------------
// The Sort_Test template-function attempts to actually *use*
// SortByName. 
template <typename Graph>
void Sort_Test(Graph& g)
{
    typedef std::list<edgeDescriptor> edge_list;
    edge_list A;

    // Put some edges into the edge_list A.
    A.push_back(edgeDescriptor("Fred"));
    A.push_back(edgeDescriptor("Barney"));
    A.push_back(edgeDescriptor("Wilma"));
    A.push_back(edgeDescriptor("Betty"));

    // Attempt to sort using a SortByName functor.
    A.sort(SortByName<typename Graph, typename edgeDescriptor>());

    // Output the sorted result, assuming the sort succeeds.
    for (std::list<edgeDescriptor>::iterator i = A.begin(); i != A.end(); ++i) {
        std::cout << *i << " => " << g[*i].eName << std::endl;
    }
}

// -------------------------------------------------------------------
// Just populate a Graph object and passes it to Sort_Test.
int main(int argc, const char* argv[])
{
    Graph the_graph;

    the_graph["Fred"] = Edge("Flinstone");
    the_graph["Barney"] = Edge("Rubble");
    the_graph["Wilma"] = Edge("Flintstone");
    the_graph["Betty"] = Edge("Rubble");

    Sort_Test<Graph>(the_graph);

    return 0;
}