/* -*- 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