// Copyright (C) 2004 The Trustees of Indiana University.

// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

//  Authors: Douglas Gregor
//           Andrew Lumsdaine
#include "expat.h"
#include <boost/config.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/any.hpp>
#include <boost/type_traits/is_convertible.hpp>
#include <typeinfo>
#include <boost/mpl/bool.hpp>
#include <exception>
#include <sstream>

namespace boost {

template<typename MutableGraph>
class graphml_reader
{
  typedef graphml_reader self_type;
  typedef typename graph_traits<MutableGraph>::vertex_descriptor
    vertex_descriptor;
  typedef typename graph_traits<MutableGraph>::edge_descriptor edge_descriptor;

  typedef typename graph_traits<MutableGraph>::directed_category
    directed_category;

  BOOST_STATIC_CONSTANT(bool, 
    graph_is_directed = 
      (is_convertible<directed_category*, directed_tag*>::value));

public:
  graphml_reader(MutableGraph& g, dynamic_properties& dp) : g(g), dp(dp) { }

  void run(std::istream& in)
  {
    const int buffer_size = 4096;
    XML_Parser parser = XML_ParserCreate(0);
    XML_SetElementHandler(parser, &on_start_element, &on_end_element);
    XML_SetCharacterDataHandler(parser, &on_character_data);
    XML_SetUserData(parser, this);
    char buffer[buffer_size];
    do {
      in.read(buffer, buffer_size);
    } while (XML_Parse(parser, buffer, in.gcount(), in.gcount() == 0) 
             && in.good());

    if (in.good()) {
      std::cerr << "Parse error: " << XML_ErrorString(XML_GetErrorCode(parser))
                << " on line " << XML_GetCurrentLineNumber(parser)
                << ", column " << XML_GetCurrentColumnNumber(parser)
                << std::endl;
    }
    XML_ParserFree(parser);
  }

private:
  /// The kinds of keys. Not all of these are supported
  enum key_kind { 
    graph_key, 
    node_key, 
    edge_key,
    hyperedge_key,
    port_key,
    endpoint_key, 
    all_key,
  };

  void 
  unrecognized_attribute(const std::string& element, const std::string& key,
                         const std::string&)
  {
    std::cerr << "Unrecognized attribute `" << key << "' of element `" 
              << element << "'. Ignoring..." << std::endl;
  }

  void 
  unrecognized_element(const std::string& name)
  {
    std::cerr << "Unrecognized element `" << name << "'" << std::endl;
  }

  void
  unhandled_data(const std::string& key)
  {
    std::cerr << "warning: unable to store data element with key \"" + key + "\", ignoring..." << std::endl;
  }

  static void 
  on_start_element(void* user_data, const XML_Char *c_name,
                   const XML_Char **atts)
  {
    self_type* self = static_cast<self_type*>(user_data);

    std::string name(c_name);
    if (name == "graphml") {
      while (*atts) {
        std::string name = *atts++;
        std::string value = *atts++;
        self->unrecognized_attribute("graphml", name, value);
      }
    }
    else if (name == "key") {
      std::string id;
      key_kind kind = all_key;

      while (*atts) {
        std::string name = *atts++;
        std::string value = *atts++;

        if (name == "id") id = value;
        else if (name == "for") {
          if (value == "graph") kind = graph_key;
          else if (value == "node") kind = node_key;
          else if (value == "edge") kind = edge_key;
          else if (value == "hyperedge") kind = hyperedge_key;
          else if (value == "port") kind = port_key;
          else if (value == "endpoint") kind = endpoint_key;
          else if (value == "all") kind = all_key;
          else {
            throw std::runtime_error("error: unrecognized key kind '" + value + "'");
          }
        }
        else self->unrecognized_attribute("key", name, value);
      }

      self->keys[id] = kind;
    } else if (name == "node") {
      std::string id;

      while (*atts) {
        std::string name = *atts++;
        std::string value = *atts++;

        if (name == "id") id = value;
        else self->unrecognized_attribute("node", name, value);
      }

      self->vertex[id] = add_vertex(self->g);
      self->active_descriptor = id;
    } else if (name == "edge") {
      std::string id;
      vertex_descriptor source, target;
      while (*atts) {
        std::string name = *atts++;
        std::string value = *atts++;

        if (name == "id") id = value;
        else if (name == "source") source = self->vertex[value];
        else if (name == "target") target = self->vertex[value];
        else if (name == "directed") {
          bool edge_is_directed = (value == "directed");
          if (edge_is_directed != graph_is_directed) {
            if (edge_is_directed) 
              throw std::runtime_error("error: unable to add a directed edge to an undirected graph");
            else
              throw std::runtime_error("error: unable to add an undirected edge to a directed graph");
          }
        }
        else self->unrecognized_attribute("edge", name, value);
      }

      self->edge[id] = add_edge(source, target, self->g).first;
      self->active_descriptor = id;
    } else if (name == "graph") {
      while (*atts) {
        std::string name = *atts++;
        std::string value = *atts++;

        if (name == "id") self->id = value;
        else if (name == "edgedefault") {
          bool edge_is_directed = (value == "directed");
          if (edge_is_directed != graph_is_directed) 
            throw std::runtime_error("error: default directness of edges must coincide for graph and data file");
        } else self->unrecognized_attribute("graph", name, value);
      }
    } else if (name == "data") {
      std::string id;

      while (*atts) {
        std::string name = *atts++;
        std::string value = *atts++;

        if (name == "key") self->active_key = value;
        else self->unrecognized_attribute("data", name, value);
      }
    } else self->unrecognized_element(name);

    self->character_data.clear();
  }

  static void
  on_end_element(void* user_data, const XML_Char *c_name)
  {
    self_type* self = static_cast<self_type*>(user_data);
    std::string name(c_name);

    bool stored = false;

    if (name == "data") {
      typename std::map<std::string, vertex_descriptor>::iterator v = 
        self->vertex.find(self->active_descriptor);
      if (v != self->vertex.end()) {
        stored = put(self->active_key, self->dp, *v, self->character_data);
      } else {
        typename std::map<std::string, edge_descriptor>::iterator e = 
          self->edge.find(self->active_descriptor);
        if (e != self->edge.end())
          stored = put(self->active_key, self->dp, *e, self->character_data);
      }

      if (!stored) self->unhandled_data(self->active_key);
    }
  }

  static void
  on_character_data(void* user_data, const XML_Char* s, int len)
  {
    self_type* self = static_cast<self_type*>(user_data);
    self->character_data.append(s, len);
  }

  std::string id;
  MutableGraph& g;
  dynamic_properties& dp;
  std::map<std::string, key_kind> keys;
  std::map<std::string, vertex_descriptor> vertex;
  std::map<std::string, edge_descriptor> edge;
  std::string active_descriptor;
  std::string active_key;
  std::string character_data;
};

template<typename MutableGraph>
void
read_graphml(std::istream& in, MutableGraph& g, dynamic_properties& dp)
{
  graphml_reader<MutableGraph> reader(g, dp);
  reader.run(in);
}

template<typename Graph, typename VertexIndexMap>
void
write_graphml(std::ostream& out, const Graph& g, VertexIndexMap vertex_index,
              const dynamic_properties& dp)
{
  typedef typename graph_traits<Graph>::directed_category directed_category;
  typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;

  BOOST_STATIC_CONSTANT(bool, 
    graph_is_directed = 
      (is_convertible<directed_category*, directed_tag*>::value));

  out << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n"
      << "<graphml xmlns=\"http://graphml.graphdrawing.org/xmlns/graphml\"  xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" xsi:schemaLocation=\"http://graphml.graphdrawing.org/xmlns/graphml http://graphml.graphdrawing.org/xmlns/graphml/graphml-attributes-1.0rc.xsd\">\n";

  // Output keys
  for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i) {
    out << "  <key id=\"" << i->first << "\" for=\"" 
        << (i->second->key() == typeid(vertex_descriptor)? "node" : "edge")
        << "\"/>\n";
  }

  out << "  <graph id=\"G\" edgedefault=\"" 
      << (graph_is_directed? "directed" : "undirected") << "\">\n";

  typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
  vertex_iterator v, v_end;
  for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
    out << "    <node id=\"n" << get(vertex_index, *v) << "\">\n";

    // Output data
    for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
    {
      if (i->second->key() == typeid(vertex_descriptor)) {
        out << "      <data key=\"" << i->first << "\">"
            << i->second->get_string(*v) << "</data>\n";
      }
    }
    
    out << "    </node>\n";
  }

  typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
  edge_iterator e, e_end;
  typename graph_traits<Graph>::edges_size_type edge_count = 0;
  for (tie(e, e_end) = edges(g); e != e_end; ++e) {
    out << "    <edge id=\"e" << edge_count++ << "\" source=\"n"
        << get(vertex_index, source(*e, g)) << "\" target=\"n"
        << get(vertex_index, target(*e, g)) << "\">\n";

    // Output data
    for (dynamic_properties::const_iterator i = dp.begin(); i != dp.end(); ++i)
    {
      if (i->second->key() == typeid(edge_descriptor)) {
        out << "      <data key=\"" << i->first << "\">"
            << i->second->get_string(*e) << "</data>\n";
      }
    }

    out << "    </edge>\n";
  }

  out << "  </graph>\n"
      << "</graphml>\n";
}

}