/* -*- C++ -*-

 * src/lemon/graph_writer.h - Part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

///\ingroup io_group

///\file

///\brief Lemon Graph Format writer.

#ifndef LEMON_GRAPH_WRITER_H

#define LEMON_GRAPH_WRITER_H

#include <iostream>

#include <sstream>

#include <map>

#include <vector>

#include <memory>

#include <lemon/map_utils.h>

#include <lemon/invalid.h>

#include <lemon/error.h>

namespace lemon {

  /// \addtogroup io_group

  /// @{

  /// \brief Standard WriterTraits for the GraphWriter class.

  ///

  /// Standard WriterTraits for the GraphWriter class.

  /// It defines standard writing method for all type of value. 

  /// \author Balazs Dezso

  struct DefaultWriterTraits {

    /// \brief Template class for writing an value.

    ///

    /// Template class for writing an value.

    /// \author Balazs Dezso

    template <typename _Value>

    struct Writer {

      /// The value type.

      typedef _Value Value;

      /// \brief Writes a value to the given stream.

      ///

      /// Writes a value to the given stream.

      void write(std::ostream& os, const Value& value) {

	os << value << '\t';

      }

    };

    /// \brief Returns wheter this name is an ID map name.

    ///

    /// Returns wheter this name is an ID map name.

    static bool idMapName(const std::string& name) {

      return name == "id";

    }

  };

  /// \brief Writer class for quoted strings.

  ///

  /// Writer class for quoted strings. It can process the escape

  /// sequences in the string.

  /// \author Balazs Dezso

  class QuotedStringWriter {

  public:

    typedef std::string Value;

    /// \brief Constructor for the writer.

    ///

    /// Constructor for the writer. If the given parameter is true

    /// the writer creates escape sequences from special characters.

    QuotedStringWriter(bool _escaped = true) : escaped(_escaped) {}

    /// \brief Writes a quoted string to the given stream.

    ///

    /// Writes a quoted string to the given stream.

    void write(std::ostream& os, const std::string& value) {

      os << "\"";

      if (escaped) {

	std::ostringstream ls;

	for (int i = 0; i < (int)value.size(); ++i) {

	  writeEscape(ls, value[i]);

	}

	os << ls.str();

      } else {

	os << value;

      }

      os << "\"";

    }

  private:

    static void writeEscape(std::ostream& os, char c) {

      switch (c) {

      case '\\':

	os << "\\\\";

	return;

      case '\"':

	os << "\\\"";

	return;

      case '\'':

	os << "\\\'";

	return;

      case '\?':

	os << "\\\?";

	return;

      case '\a':

	os << "\\a";

	return;

      case '\b':

	os << "\\b";

	return;

      case '\f':

	os << "\\f";

	return;

      case '\r':

	os << "\\r";

	return;

      case '\n':

	os << "\\n";

	return;

      case '\t':

	os << "\\t";

	return;

      case '\v':

	os << "\\v";

	return;

      default:

	if (c < 0x20) {

	  os << '\\' << std::oct << (int)c;

	} else {

	  os << c;

	}

	return;

      }     

    }

  private:

    bool escaped;

  };

  /// \brief The graph writer class.

  ///

  /// The \c GraphWriter class provides the graph output. To write a graph

  /// you should first give writing commands for the writer. You can declare

  /// write command as \c NodeMap or \c EdgeMap writing and labeled Node and

  /// Edge writing.

  ///

  /// \code

  /// GraphWriter<ListGraph> writer(std::cout, graph);

  /// \endcode

  ///

  /// The \c writeNodeMap() function declares a \c NodeMap writing 

  /// command in the \c GraphWriter. You should give as parameter 

  /// the name of the map and the map object. The NodeMap writing 

  /// command with name "id" should write a unique map because it 

  /// is regarded as ID map.

  ///

  /// \code

  /// IdMap<ListGraph, Node> nodeIdMap;

  /// writer.writeNodeMap("id", nodeIdMap);

  ///

  /// writer.writeNodeMap("x-coord", xCoordMap);

  /// writer.writeNodeMap("y-coord", yCoordMap);

  /// writer.writeNodeMap("color", colorMap);

  /// \endcode

  ///

  /// With the \c writeEdgeMap() member function you can give an edge map

  /// writing command similar to the NodeMaps.

  ///

  /// \code

  /// DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> > 

  ///   edgeDescMap(graph);

  /// writer.writeEdgeMap("descriptor", edgeDescMap);

  ///

  /// writer.writeEdgeMap("weight", weightMap);

  /// writer.writeEdgeMap("label", labelMap);

  /// \endcode

  ///

  /// With \c writeNode() and \c writeEdge() functions you can 

  /// point out Nodes and Edges in the graph. By example, you can 

  /// write out the source and target of the graph.

  ///

  /// \code

  /// writer.writeNode("source", sourceNode);

  /// writer.writeNode("target", targetNode);

  ///

  /// writer.writeEdge("observed", edge);

  /// \endcode

  ///

  /// After you give all write commands you must call the \c run() member

  /// function, which execute all the writer commands.

  ///

  /// \code

  /// writer.run();

  /// \endcode

  ///

  /// \see DefaultWriterTraits

  /// \see QuotedStringWriter

  /// \see IdMap

  /// \see DescriptorMap

  /// \see \ref GraphWriter

  /// \see \ref graph-io-page

  /// \author Balazs Dezso

  template <typename _Graph, typename _WriterTraits = DefaultWriterTraits> 

  class GraphWriter {

  public:

    typedef _Graph Graph;

    typedef typename Graph::Node Node;

    typedef typename Graph::NodeIt NodeIt;

    typedef typename Graph::Edge Edge;

    typedef typename Graph::EdgeIt EdgeIt;

    typedef _WriterTraits WriterTraits;

    /// \brief Construct a new GraphWriter.

    ///

    /// Construct a new GraphWriter. It writes from the given map,

    /// it constructs the given map and it use the given writer as the

    /// default skipper.

    GraphWriter(std::ostream& _os, const Graph& _graph) 

      : os(_os), graph(_graph) {}

    /// \brief Destruct the graph writer.

    ///

    /// Destruct the graph writer.

    ~GraphWriter() {

      for (typename NodeMapWriters::iterator it = node_map_writers.begin(); 

	   it != node_map_writers.end(); ++it) {

	delete it->second;

      }

      for (typename EdgeMapWriters::iterator it = edge_map_writers.begin();

	   it != edge_map_writers.end(); ++it) {

	delete it->second;

      }

    }

    // Node map rules

    /// \brief Add a new node map writer command for the writer.

    ///

    /// Add a new node map writer command for the writer.

    template <typename Map>

    GraphWriter& writeNodeMap(std::string name, const Map& map) {

      return writeNodeMap<typename WriterTraits::template Writer<

	typename Map::Value>, Map>(name, map);

    }

    /// \brief Add a new node map writer command for the writer.

    ///

    /// Add a new node map writer command for the writer.

    template <typename Writer, typename Map>

    GraphWriter& writeNodeMap(std::string name, const Map& map, 

			      const Writer& writer = Writer()) {

      node_map_writers.push_back(

        make_pair(name, new MapWriter<Node, Map, Writer>(map, writer)));

      return *this;

    }

    // Edge map rules

    /// \brief Add a new edge map writer command for the writer.

    ///

    /// Add a new edge map writer command for the writer.

    template <typename Map>

    GraphWriter& writeEdgeMap(std::string name, const Map& map) { 

      return writeEdgeMap<typename WriterTraits::template Writer<

        typename Map::Value>, Map>(name, map);

    }

    /// \brief Add a new edge map writer command for the writer.

    ///

    /// Add a new edge map writer command for the writer.

    template <typename Writer, typename Map>

    GraphWriter& writeEdgeMap(std::string name, 

			    const Map& map, const Writer& writer = Writer()) {

      edge_map_writers.push_back(make_pair(name, 

	new MapWriter<Edge, Map, Writer>(map, writer)));

      return *this;

    }

    /// \brief Add a new labeled node writer for the writer.

    ///

    /// Add a new labeled node writer for the writer.

    GraphWriter& writeNode(std::string name, const Node& node) {

      node_writers.push_back(make_pair(name, node));

      return *this;

    }

    /// \brief Add a new labeled edge writer for the writer.

    ///

    /// Add a new labeled edge writer for the writer.

    GraphWriter& writeEdge(std::string name, const Edge& edge) {

      edge_writers.push_back(make_pair(name, edge));

      return *this;

    }

    /// \brief Executes the writer commands.

    ///

    /// Executes the writer commands.

    void run() {   

      WriterBase<Node>* nodeWriter = 0;

      WriterBase<Edge>* edgeWriter = 0;

      writeNodeSet(nodeWriter);

      writeEdgeSet(nodeWriter, edgeWriter);

      writeNodes(nodeWriter);

      writeEdges(edgeWriter);

      os << "@end" << std::endl;

    }

  private:

    template <class _Item>

    class WriterBase {

    public:

      typedef _Item Item;

      virtual void write(std::ostream&, const Item&) = 0;

    };

    template <class _Item, typename _Map, typename _Writer>

    class MapWriter : public WriterBase<_Item> {

    public:

      typedef _Map Map;

      typedef _Writer Writer;

      typedef typename Writer::Value Value;

      typedef _Item Item;

      const Map& map;

      Writer writer;

      MapWriter(const Map& _map, const Writer& _writer) 

	: map(_map), writer(_writer) {}

      virtual void write(std::ostream& os, const Item& item) {

	writer.write(os, map[item]);

      }

    };

    void writeNodeSet(WriterBase<Node>* & nodeWriter) {

      if (node_map_writers.size() == 0) return;

      os << "@nodeset" << std::endl;

      for (int i = 0; i < (int)node_map_writers.size(); ++i) {

	const std::string& id = node_map_writers[i].first;

	os << id << '\t';

	if (WriterTraits::idMapName(id) && nodeWriter == 0) {

	  nodeWriter = node_map_writers[i].second;

	}

      } 

      os << std::endl;

      for (NodeIt it(graph); it != INVALID; ++it) {

	for (int i = 0; i < (int)node_map_writers.size(); ++i) {

	  node_map_writers[i].second->write(os, it);

	}

	os << std::endl;

      }

    }

    void writeEdgeSet(WriterBase<Node>* nodeWriter, 

		      WriterBase<Edge>* & edgeWriter) {

      if (edge_map_writers.size() == 0) return;

      if (nodeWriter == 0) {

	throw DataFormatError("Cannot find node id map");

      }

      os << "@edgeset" << std::endl;

      os << "\t\t";

      for (int i = 0; i < (int)edge_map_writers.size(); ++i) {

	const std::string& id = edge_map_writers[i].first;

	os << id << '\t';

	if (WriterTraits::idMapName(id) && edgeWriter == 0) {

	  edgeWriter = edge_map_writers[i].second;

	}

      } 

      os << std::endl;

      for (EdgeIt it(graph); it != INVALID; ++it) {

	nodeWriter->write(os, graph.source(it));

	nodeWriter->write(os, graph.target(it));

	for (int i = 0; i < (int)edge_map_writers.size(); ++i) {

	  edge_map_writers[i].second->write(os, it);

	}

	os << std::endl;

      }

    }

    void writeNodes(WriterBase<Node>* nodeWriter) {

      if (node_writers.size() == 0) return;

      if (nodeWriter == 0) {

	throw DataFormatError("Cannot find node id map");

      }

      os << "@nodes" << std::endl;

      for (int i = 0; i < (int)node_writers.size(); ++i) {

	os << node_writers[i].first << '\t';

	nodeWriter->write(os, node_writers[i].second);

	os << std::endl;

      } 

    }

    void writeEdges(WriterBase<Edge>* edgeWriter) {

      if (edge_writers.size() == 0) return;

      if (edgeWriter == 0) {

	throw DataFormatError("Cannot find node id map");

      }

      os << "@edges" << std::endl;

      for (int i = 0; i < (int)edge_writers.size(); ++i) {

	os << edge_writers[i].first << '\t';

        edgeWriter->write(os, edge_writers[i].second);

	os << std::endl;

      } 

    }

    typedef std::vector< std::pair<std::string, WriterBase<Node>*> > 

      NodeMapWriters;

    NodeMapWriters node_map_writers;

    typedef std::vector< std::pair<std::string, WriterBase<Edge>*> > 

      EdgeMapWriters;

    EdgeMapWriters edge_map_writers;

    typedef std::vector<std::pair<std::string, Node> > NodeWriters;

    NodeWriters node_writers;

    typedef std::vector<std::pair<std::string, Edge> > EdgeWriters;

    EdgeWriters edge_writers;

    std::ostream& os;

    const Graph& graph;

  };

  /// \brief Write a graph to the output.

  ///

  /// Write a graph to the output.

  /// \param os The output stream.

  /// \param g The graph.

  /// \param capacity The capacity map.

  /// \param s The source node.

  /// \param t The target node.

  /// \param cost The cost map.

  template<typename Graph, typename CapacityMap, typename CostMap>

  void writeGraph(std::ostream& os, const Graph &g, 

		  const CapacityMap& capacity, const typename Graph::Node &s,

		  const typename Graph::Node &t, const CostMap& cost) {

    GraphWriter<Graph> writer(os, g);

    IdMap<Graph, typename Graph::Node> nodeIdMap(g);

    writer.writeNodeMap("id", nodeIdMap);

    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);

    writer.writeEdgeMap("id", edgeIdMap);

    writer.writeEdgeMap("capacity", capacity);

    writer.writeEdgeMap("cost", cost);

    writer.writeNode("source", s);

    writer.writeNode("target", t);

    writer.run();

  }

  /// \brief Write a graph to the output.

  ///

  /// Write a graph to the output.

  /// \param os The output stream.

  /// \param g The graph.

  /// \param capacity The capacity map.

  /// \param s The source node.

  /// \param t The target node.

  template<typename Graph, typename CapacityMap>

  void writeGraph(std::ostream& os, const Graph &g, 

		  const CapacityMap& capacity, const typename Graph::Node &s,

		  const typename Graph::Node &t) {

    GraphWriter<Graph> writer(os, g);

    IdMap<Graph, typename Graph::Node> nodeIdMap(g);

    writer.writeNodeMap("id", nodeIdMap);

    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);

    writer.writeEdgeMap("id", edgeIdMap);

    writer.writeEdgeMap("capacity", capacity);

    writer.writeNode("source", s);

    writer.writeNode("target", t);

    writer.run();

  }

  /// \brief Write a graph to the output.

  ///

  /// Write a graph to the output.

  /// \param os The output stream.

  /// \param g The graph.

  /// \param capacity The capacity map.

  /// \param s The source node.

  template<typename Graph, typename CapacityMap>

  void writeGraph(std::ostream& os, const Graph &g, 

		  const CapacityMap& capacity, const typename Graph::Node &s) {

    GraphWriter<Graph> writer(os, g);

    IdMap<Graph, typename Graph::Node> nodeIdMap(g);

    writer.writeNodeMap("id", nodeIdMap);

    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);

    writer.writeEdgeMap("id", edgeIdMap);

    writer.writeEdgeMap("capacity", capacity);

    writer.writeNode("source", s);

    writer.run();

  }

  /// \brief Write a graph to the output.

  ///

  /// Write a graph to the output.

  /// \param os The output stream.

  /// \param g The graph.

  /// \param capacity The capacity map.

  template<typename Graph, typename CapacityMap>

  void writeGraph(std::ostream& os, const Graph &g, 

		  const CapacityMap& capacity) {

    GraphWriter<Graph> writer(os, g);

    IdMap<Graph, typename Graph::Node> nodeIdMap(g);

    writer.writeNodeMap("id", nodeIdMap);

    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);

    writer.writeEdgeMap("id", edgeIdMap);

    writer.writeEdgeMap("capacity", capacity);

    writer.run();

  }

  /// \brief Write a graph to the output.

  ///

  /// Write a graph to the output.

  /// \param os The output stream.

  /// \param g The graph.

  template<typename Graph>

  void writeGraph(std::ostream& os, const Graph &g) {

    GraphWriter<Graph> writer(os, g);

    IdMap<Graph, typename Graph::Node> nodeIdMap(g);

    writer.writeNodeMap("id", nodeIdMap);

    IdMap<Graph, typename Graph::Edge> edgeIdMap(g);

    writer.writeEdgeMap("id", edgeIdMap);

    writer.run();

  }

  /// @}

}

#endif