/* -*- C++ -*-

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

 *

 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Combinatorial Optimization Research Group, 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