/* -*- C++ -*-

  * src/lemon/graph_reader.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 reader.

 #ifndef LEMON_GRAPH_READER_H

 #define LEMON_GRAPH_READER_H

 #include <iostream>

 #include <sstream>

 #include <map>

 #include <vector>

 #include <memory>

 #include <lemon/error.h>

 namespace lemon {

   /// \addtogroup io_group

   /// @{

   /// \brief Standard ReaderTraits for the GraphReader class.

   ///

   /// Standard ReaderTraits for the GraphReader class.

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

   /// \author Balazs Dezso

   struct DefaultReaderTraits {

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

     ///

     /// Template class for reading an value.

     /// \author Balazs Dezso

     template <typename _Value>

     struct Reader {

       /// The value type.

       typedef _Value Value;

       /// \brief Reads a value from the given stream.

       ///

       /// Reads a value from the given stream.

       void read(std::istream& is, Value& value) {

 	if (!(is >> value)) 

 	  throw DataFormatError("Default reader format exception");

       }

     };

     /// \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";

     }

     /// The reader class for the not needed maps.

     typedef Reader<std::string> DefaultReader;

   };

   /// \brief Reader class for quoted strings.

   ///

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

   /// sequences in the string.

   /// \author Balazs Dezso

   class QuotedStringReader {

   public:

     typedef std::string Value;

     /// \brief Constructor for the reader.

     ///

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

     /// the reader processes the escape sequences.

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

     /// \brief Reads a quoted string from the given stream.

     ///

     /// Reads a quoted string from the given stream.

     void read(std::istream& is, std::string& value) {

       char c;

       value.clear();

       is >> std::ws;

       if (!is.get(c) || c != '\"') 

 	throw DataFormatError("Quoted string format error");

       while (is.get(c) && c != '\"') {

 	if (escaped && c == '\\') {

 	  value += readEscape(is);

 	} else {

 	  value += c;

 	}

       }

       if (!is) throw DataFormatError("Quoted string format error");

     }

   private:

     static char readEscape(std::istream& is) {

       char c;

       switch (is.get(c), c) {

       case '\\':

 	return '\\';

       case '\"':

 	return '\"';

       case '\'':

 	return '\'';

       case '\?':

 	return '\?';

       case 'a':

 	return '\a';

       case 'b':

 	return '\b';

       case 'f':

 	return '\f';

       case 'n':

 	return '\n';

       case 'r':

 	return '\r';

       case 't':

 	return '\t';

       case 'v':

 	return '\v';

       case 'x':

 	{

 	  int code;

 	  if (!is.get(c) || !isHex(c)) 

 	    throw DataFormatError("Escape format error");

 	  else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);

 	  else code = code * 16 + valueHex(c);

 	  return code;

 	}

       default:

 	{

 	  int code;

 	  if (!isOct(c)) 

 	    throw DataFormatError("Escape format error");

 	  else if (code = valueOct(c), !is.get(c) || !isOct(c)) 

 	    is.putback(c);

 	  else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c)) 

 	    is.putback(c);

 	  else code = code * 8 + valueOct(c);

 	  return code;

 	}	      

       } 

     }

     static bool isOct(char c) {

       return '0' <= c && c <='7'; 

     }

     static int valueOct(char c) {

       return c - '0';

     }

    static bool isHex(char c) {

       return ('0' <= c && c <= '9') || 

 	('a' <= c && c <= 'z') || 

 	('A' <= c && c <= 'Z'); 

     }

     static int valueHex(char c) {

       if ('0' <= c && c <= '9') return c - '0';

       if ('a' <= c && c <= 'z') return c - 'a' + 10;

       return c - 'A' + 10;

     }

     bool escaped;

   };

   /// \brief The graph reader class.

   ///

   ///

   /// The given file format may contain several maps and labeled nodes or 

   /// edges.

   ///

   /// If you read a graph you need not read all the maps and items just those

   /// that you need. The interface of the \c GraphReader is very similar to

   /// the GraphWriter but the reading method does not depend on the order the

   /// given commands.

   ///

   /// The reader object suppose that each not readed value does not contain 

   /// whitespaces, therefore it has some extra possibilities to control how

   /// it should skip the values when the string representation contains spaces.

   ///

   /// \code

   /// GraphReader<ListGraph> reader(std::cin, graph);

   /// \endcode

   ///

   /// The \c addNodeMap() function reads a map from the \c \@nodeset section.

   /// If there is a map that you do not want to read from the file and there is

   /// whitespace in the string represenation of the values then you should

   /// call the \c skipNodeMap() template member function with proper 

   /// parameters.

   ///

   /// \code

   /// reader.addNodeMap("x-coord", xCoordMap);

   /// reader.addNodeMap("y-coord", yCoordMap);

   ///

   /// reader.addNodeMap<QuotedStringReader>("label", labelMap);

   /// reader.skipNodeMap<QuotedStringReader>("description");

   ///

   /// reader.addNodeMap("color", colorMap);

   /// \endcode

   ///

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

   /// reading command similar to the NodeMaps. 

   ///

   /// \code

   /// reader.addEdgeMap("weight", weightMap);

   /// reader.addEdgeMap("label", labelMap);

   /// \endcode

   ///

   /// With \c addNode() and \c addEdge() functions you can read labeled Nodes 

   /// and Edges.

   ///

   /// \code

   /// reader.addNode("source", sourceNode);

   /// reader.addNode("target", targetNode);

   ///

   /// reader.addEdge("observed", edge);

   /// \endcode

   ///

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

   /// function, which execute all the commands.

   ///

   /// \code

   /// reader.run();

   /// \endcode

   ///

   /// \see DefaultReaderTraits

   /// \see QuotedStringReader

   /// \see \ref GraphWriter

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

   /// \author Balazs Dezso

   template <typename _Graph, typename _ReaderTraits = DefaultReaderTraits> 

   class GraphReader {

   public:

     typedef _Graph Graph;

     typedef typename Graph::Node Node;

     typedef typename Graph::Edge Edge;

     typedef _ReaderTraits ReaderTraits;

     typedef typename ReaderTraits::DefaultReader DefaultReader;

     /// \brief Construct a new GraphReader.

     ///

     /// Construct a new GraphReader. It reads into the given graph

     /// and it use the given reader as the default skipper.

     GraphReader(std::istream& _is, Graph& _graph, 

 		const DefaultReader& _reader = DefaultReader()) 

       : is(_is), graph(_graph), nodeSkipper(_reader), edgeSkipper(_reader) {}

     /// \brief Destruct the graph reader.

     ///

     /// Destruct the graph reader.

     ~GraphReader() {

       for (typename NodeMapReaders::iterator it = node_map_readers.begin(); 

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

 	delete it->second;

       }

       for (typename EdgeMapReaders::iterator it = edge_map_readers.begin(); 

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

 	delete it->second;

       }

     }

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

     ///

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

     template <typename Map>

     GraphReader& addNodeMap(std::string name, Map& map) {

       return addNodeMap<typename ReaderTraits::template 

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

     }

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

     ///

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

     template <typename Reader, typename Map>

     GraphReader& addNodeMap(std::string name, Map& map, 

 			     const Reader& reader = Reader()) {

       if (node_map_readers.find(name) != node_map_readers.end()) {

 	ErrorMessage msg;

 	msg << "Multiple read rule for node map: " << name;

 	throw IOParameterError(msg.message());

       }

       node_map_readers.insert(

         make_pair(name, new MapReader<Node, Map, Reader>(map, reader)));

       return *this;

     }

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

     ///

     /// Add a new node map skipper command for the reader.

     template <typename Reader>

     GraphReader& skipNodeMap(std::string name, 

 			     const Reader& reader = Reader()) {

       if (node_map_readers.find(name) != node_map_readers.end()) {

 	ErrorMessage msg;

 	msg << "Multiple read rule for node map: " << name;

 	throw IOParameterError(msg.message());

       }

       node_map_readers.insert(

         make_pair(name, new SkipReader<Node, Reader>(reader)));

       return *this;

     }

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

     ///

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

     template <typename Map>

     GraphReader& addEdgeMap(std::string name, Map& map) { 

       return addEdgeMap<typename ReaderTraits::template

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

     }

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

     ///

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

     template <typename Reader, typename Map>

     GraphReader& addEdgeMap(std::string name, Map& map,

 			     const Reader& reader = Reader()) {

       if (edge_map_readers.find(name) != edge_map_readers.end()) {

 	ErrorMessage msg;

 	msg << "Multiple read rule for edge map: " << name;

 	throw IOParameterError(msg.message());

       }

       edge_map_readers.insert(

         make_pair(name, new MapReader<Edge, Map, Reader>(map, reader)));

       return *this;

     }

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

     ///

     /// Add a new edge map skipper command for the reader.

     template <typename Reader>

     GraphReader& skipEdgeMap(std::string name,

 			     const Reader& reader = Reader()) {

       if (edge_map_readers.find(name) != edge_map_readers.end()) {

 	ErrorMessage msg;

 	msg << "Multiple read rule for edge map: " << name;

 	throw IOParameterError(msg.message());

       }

       edge_map_readers.insert(

         make_pair(name, new SkipReader<Edge, Reader>(reader)));

       return *this;

     }

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

     ///

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

     GraphReader& addNode(std::string name, Node& node) {

       if (node_readers.find(name) != node_readers.end()) {

 	ErrorMessage msg;

 	msg << "Multiple read rule for node: " << name;

 	throw IOParameterError(msg.message());

       }

       node_readers.insert(make_pair(name, &node));

       return *this;

     }

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

     ///

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

     GraphReader& addEdge(std::string name, Edge& edge) {

       if (edge_readers.find(name) != edge_readers.end()) {

 	ErrorMessage msg;

 	msg << "Multiple read rule for edge: " << name;

 	throw IOParameterError(msg.message());

       }

       edge_readers.insert(make_pair(name, &edge));

       return *this;

     }

     /// \brief Executes the reader commands.

     ///

     /// Executes the reader commands.

     void run() {

       int line_num = 0;

       std::auto_ptr<InverterBase<Node> > nodeInverter;

       std::auto_ptr<InverterBase<Edge> > edgeInverter;

       try {

 	std::string line = readNotEmptyLine(is, line_num);

 	if (line.find("@nodeset") == 0) {

 	  line = readNodeSet(line_num, nodeInverter);

 	} 

 	if (line.find("@edgeset") == 0) {

 	  line = readEdgeSet(line_num, edgeInverter, nodeInverter);

 	}

 	if (line.find("@nodes") == 0) {

 	  line = readNodes(line_num, nodeInverter);

 	}

 	if (line.find("@edges") == 0) {

 	  line = readEdges(line_num, edgeInverter);

 	}

 	if (line.find("@end") != 0) {

 	  throw DataFormatError("Invalid control sequence error");

 	}

       } catch (DataFormatError e) {

 	e.line(line_num);

 	throw e;

       }

     }

   private:

     template <typename Item> class InverterBase;

     std::string readNodeSet(int& line_num, 

 			    std::auto_ptr<InverterBase<Node> >& nodeInverter) {

       std::vector<ReaderBase<Node>* > index;

       {

 	std::string line = readNotEmptyLine(is, line_num);    

 	std::string id;

 	std::istringstream ls(line);	

 	while (ls >> id) {

 	  typename NodeMapReaders::iterator it = node_map_readers.find(id);

 	  if (it != node_map_readers.end()) {

 	    index.push_back(it->second);

 	    node_map_readers.erase(it);

 	  } else {

 	    index.push_back(&nodeSkipper);

 	  }

 	  if (ReaderTraits::idMapName(id) && nodeInverter.get() == 0) {

 	    nodeInverter.reset(index.back()->getInverter());

 	    index.back() = nodeInverter.get();

 	  }

 	}

       }

 //       if (index.size() == 0) {

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

 //       }

 //       nodeInverter = 

 // 	std::auto_ptr<InverterBase<Node> >(index[0]->getInverter());

       std::string line;

       while (line = readNotEmptyLine(is, line_num), line[0] != '@') {

 	Node node = graph.addNode();

 	std::istringstream ls(line);

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

 	  index[i]->read(ls, node);

 	}

       }

       return line;

     }

     std::string readEdgeSet(int& line_num, 

 			    std::auto_ptr<InverterBase<Edge> >& edgeInverter, 

 			    std::auto_ptr<InverterBase<Node> >& nodeInverter) {

       std::vector<ReaderBase<Edge>*> index;

       {

 	std::string line = readNotEmptyLine(is, line_num);    

 	std::string id;

 	std::istringstream ls(line);	

 	while (ls >> id) {

 	  typename EdgeMapReaders::iterator it = edge_map_readers.find(id);

 	  if (it != edge_map_readers.end()) {

 	    index.push_back(it->second);

 	    edge_map_readers.erase(it);

 	  } else {

 	    index.push_back(&edgeSkipper);

 	  }

 	  if (ReaderTraits::idMapName(id) && edgeInverter.get() == 0) {

 	    edgeInverter.reset(index.back()->getInverter());

 	    index.back() = edgeInverter.get();

 	  }

 	}

       }

       if (nodeInverter.get() == 0) {

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

       }

 //       if (index.size() == 0) {

 // 	throw DataFormatError("Cannot find edge id map");

 //       }

 //       edgeInverter = 

 // 	std::auto_ptr<InverterBase<Edge> >(index[0]->getInverter());

       std::string line;

       while (line = readNotEmptyLine(is, line_num), line[0] != '@') {	

 	std::istringstream ls(line);

 	Node source = nodeInverter->read(ls);

 	Node target = nodeInverter->read(ls);

 	Edge edge = graph.addEdge(source, target);

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

 	  index[i]->read(ls, edge);

 	}

       }      

       return line;

     }

     std::string readNodes(int& line_num, 

 			  std::auto_ptr<InverterBase<Node> >& nodeInverter) {

       std::string line;

       if (nodeInverter.get() == 0) {

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

       }

       while (line = readNotEmptyLine(is, line_num), line[0] != '@') {

 	std::istringstream ls(line);

 	std::string name;

 	ls >> name;

 	typename NodeReaders::iterator it = node_readers.find(name);

 	if (it != node_readers.end()) {

 	  *(it -> second) = nodeInverter->read(ls);

 	} 

       }        

       return line;

     }

     std::string readEdges(int& line_num, 

 			  std::auto_ptr<InverterBase<Edge> >& edgeInverter) {

       std::string line;

       if (edgeInverter.get() == 0) {

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

       }

       while (line = readNotEmptyLine(is, line_num), line[0] != '@') {

 	std::istringstream ls(line);

 	std::string name;

 	ls >> name;

 	typename EdgeReaders::iterator it = edge_readers.find(name);

 	if (it != edge_readers.end()) {

 	  *(it -> second) = edgeInverter->read(ls);

 	} 

       }        

       return line;    

     }

     std::string readNotEmptyLine(std::istream& is, int& line_num) {

       std::string line;

       while (++line_num, getline(is, line)) {	

 	int vi = line.find('#');

 	if (vi != (int)::std::string::npos) {

 	  line = line.substr(0, vi);

 	}

 	vi = line.find_first_not_of(" \t");

 	if (vi != (int)std::string::npos) { 

 	  return line.substr(vi);

 	}

       }

       throw DataFormatError("End of stream error");

     }

     template <typename _Item>

     class ReaderBase;

     template <typename _Item>

     class InverterBase : public ReaderBase<_Item> {

     public:

       typedef _Item Item;

       virtual void read(std::istream&, const Item&) = 0;

       virtual Item read(std::istream&) = 0;

       virtual InverterBase<_Item>* getInverter() {

 	return this;

       }

     };

     template <typename _Item, typename _Map, typename _Reader>

     class MapReaderInverter : public InverterBase<_Item> {

     public:

       typedef _Item Item;

       typedef _Reader Reader;

       typedef typename Reader::Value Value;

       typedef _Map Map;

       typedef std::map<Value, Item> Inverse;

       Map& map;

       Reader reader;

       Inverse inverse;

       MapReaderInverter(Map& _map, const Reader& _reader) 

 	: map(_map), reader(_reader) {}

       virtual ~MapReaderInverter() {}

       virtual void read(std::istream& is, const Item& item) {

 	Value value;

 	reader.read(is, value);

 	map.set(item, value);

 	typename Inverse::iterator it = inverse.find(value);

 	if (it == inverse.end()) {

 	  inverse.insert(std::make_pair(value, item));

 	} else {

 	  throw DataFormatError("Multiple ID occurence");

 	}

       }

       virtual Item read(std::istream& is) {

 	Value value;

 	reader.read(is, value);	

 	typename Inverse::const_iterator it = inverse.find(value);

 	if (it != inverse.end()) {

 	  return it->second;

 	} else {

 	  throw DataFormatError("Invalid ID error");

 	}

       }      

     };

     template <typename _Item, typename _Reader>

     class SkipReaderInverter : public InverterBase<_Item> {

     public:

       typedef _Item Item;

       typedef _Reader Reader;

       typedef typename Reader::Value Value;

       typedef std::map<Value, Item> Inverse;

       Reader reader;

       SkipReaderInverter(const Reader& _reader) 

 	: reader(_reader) {}

       virtual ~SkipReaderInverter() {}

       virtual void read(std::istream& is, const Item& item) {

 	Value value;

 	reader.read(is, value);

 	typename Inverse::iterator it = inverse.find(value);

 	if (it == inverse.end()) {

 	  inverse.insert(std::make_pair(value, item));

 	} else {

 	  throw DataFormatError("Multiple ID occurence error");

 	}

       }

       virtual Item read(std::istream& is) {

 	Value value;

 	reader.read(is, value);	

 	typename Inverse::const_iterator it = inverse.find(value);

 	if (it != inverse.end()) {

 	  return it->second;

 	} else {

 	  throw DataFormatError("Invalid ID error");

 	}

       }      

     private:

       Inverse inverse;

     };

     // Readers

     template <typename _Item>    

     class ReaderBase {

     public:

       typedef _Item Item;

       //      virtual ~ReaderBase() {}

       virtual void read(std::istream& is, const Item& item) = 0;

       virtual InverterBase<_Item>* getInverter() = 0;

     };

     template <typename _Item, typename _Map, typename _Reader>

     class MapReader : public ReaderBase<_Item> {

     public:

       typedef _Map Map;

       typedef _Reader Reader;

       typedef typename Reader::Value Value;

       typedef _Item Item;

       Map& map;

       Reader reader;

       MapReader(Map& _map, const Reader& _reader) 

 	: map(_map), reader(_reader) {}

       virtual ~MapReader() {}

       virtual void read(std::istream& is, const Item& item) {

 	Value value;

 	reader.read(is, value);

 	map.set(item, value);

       }

       virtual InverterBase<_Item>* getInverter() {

 	return new MapReaderInverter<Item, Map, Reader>(map, reader);

       }

     };

     template <typename _Item, typename _Reader>

     class SkipReader : public ReaderBase<_Item> {

     public:

       typedef _Reader Reader;

       typedef typename Reader::Value Value;

       typedef _Item Item;

       Reader reader;

       SkipReader(const Reader& _reader) : reader(_reader) {}

       virtual ~SkipReader() {}

       virtual void read(std::istream& is, const Item&) {

 	Value value;

 	reader.read(is, value);

       }      

       virtual InverterBase<Item>* getInverter() {

 	return new SkipReaderInverter<Item, Reader>(reader);

       }

     };

     typedef std::map<std::string, ReaderBase<Node>*> NodeMapReaders;

     NodeMapReaders node_map_readers;

     typedef std::map<std::string, ReaderBase<Edge>*> EdgeMapReaders;

     EdgeMapReaders edge_map_readers;

     typedef std::map<std::string, Node*> NodeReaders;

     NodeReaders node_readers;

     typedef std::map<std::string, Edge*> EdgeReaders;

     EdgeReaders edge_readers;

     std::istream& is;

     Graph& graph;

     SkipReader<Node, DefaultReader> nodeSkipper;

     SkipReader<Edge, DefaultReader> edgeSkipper;

   };

   /// \brief Read a graph from the input.

   ///

   /// Read a graph from the input.

   /// \param is The input 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 readGraph(std::istream& is, Graph &g, CapacityMap& capacity, 

 		  typename Graph::Node &s, typename Graph::Node &t, 

 		  CostMap& cost) {

     GraphReader<Graph> reader(is, g);

     reader.addEdgeMap("capacity", capacity);

     reader.addEdgeMap("cost", cost);

     reader.addNode("source", s);

     reader.addNode("target", t);

     reader.run();

   }

   /// \brief Read a graph from the input.

   ///

   /// Read a graph from the input.

   /// \param is The input 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 readGraph(std::istream& is, Graph &g, CapacityMap& capacity, 

 		  typename Graph::Node &s, typename Graph::Node &t) {

     GraphReader<Graph> reader(is, g);

     reader.addEdgeMap("capacity", capacity);

     reader.addNode("source", s);

     reader.addNode("target", t);

     reader.run();

   }

   /// \brief Read a graph from the input.

   ///

   /// Read a graph from the input.

   /// \param is The input stream.

   /// \param g The graph.

   /// \param capacity The capacity map.

   /// \param s The source node.

   template<typename Graph, typename CapacityMap>

   void readGraph(std::istream& is, Graph &g, CapacityMap& capacity, 

 		  typename Graph::Node &s) {

     GraphReader<Graph> reader(is, g);

     reader.addEdgeMap("capacity", capacity);

     reader.addNode("source", s);

     reader.run();

   }

   /// \brief Read a graph from the input.

   ///

   /// Read a graph from the input.

   /// \param is The input stream.

   /// \param g The graph.

   /// \param capacity The capacity map.

   template<typename Graph, typename CapacityMap>

   void readGraph(std::istream& is, Graph &g, CapacityMap& capacity) {

     GraphReader<Graph> reader(is, g);

     reader.addEdgeMap("capacity", capacity);

     reader.run();

   }

   /// \brief Read a graph from the input.

   ///

   /// Read a graph from the input.

   /// \param is The input stream.

   /// \param g The graph.

   template<typename Graph>

   void readGraph(std::istream& is, Graph &g) {

     GraphReader<Graph> reader(is, g);

     reader.run();

   }

   /// @}

 }

 #endif