/* -*- C++ -*-
 * src/lemon/graph_reader.h - Part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2004 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 gio
///\file
///\brief Graph reader.

#include <iostream>
#include <sstream>

#include <map>
#include <vector>

#include <memory>

#include <lemon/error.h>

/// \todo fix exceptions


namespace lemon {

  // Exceptions

  class IOException {
  public:
    virtual string what() const = 0;
  };

  class DataFormatException : public IOException {
    std::string message;
  public:
    DataFormatException(const std::string& _message) 
      : message(_message) {}
    std::string what() const {
      return "DataFormatException: " + message; 
    }
  };

  template <typename _Exception>
  class StreamException : public _Exception {
  public:
    typedef _Exception Exception;
    StreamException(int _line, Exception _exception) 
      : line_num(_line), Exception(_exception) {}
    virtual int line() const {
      return line_num;
    }
    virtual std::string what() const {
      ostringstream os;
      os << Exception::what() << " in line " << line();
      return os.str();
    }
  private:
    int line_num;
  };  


  // Readers and ReaderTraits
  
  struct DefaultReaderTraits {

    template <typename _Value>
    struct Reader {
      typedef _Value Value;
      void read(std::istream& is, Value& value) {
	if (!(is >> value)) 
	  throw DataFormatException("Default Reader format exception");
      }
    };

    typedef Reader<std::string> DefaultReader;

  };

  class QuotedStringReader {
  public:
    typedef std::string Value;

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

    void read(std::istream& is, std::string& value) {
      char c;
      value.clear();
      is >> ws;
      if (!is.get(c) || c != '\"') throw DataFormatException("Quoted string format");
      while (is.get(c) && c != '\"') {
	if (escaped && c == '\\') {
	  value += readEscape(is);
	} else {
	  value += c;
	}
      }
      if (!is) throw DataFormatException("Quoted string format");
    }

  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 DataFormatException("Escape format exception");
	  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 DataFormatException("Escape format exception");
	  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;
  };





  // Graph reader
  
  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;

    GraphReader(std::istream& _is, Graph& _graph, const DefaultReader& _reader = DefaultReader()) 
      : is(_is), graph(_graph), nodeSkipper(_reader), edgeSkipper(_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;
      }

    }

    // Node map rules

    template <typename Map>
    GraphReader& readNodeMap(std::string name, Map& map) {
      return readNodeMap<typename ReaderTraits::template Reader<typename Map::Value>, Map>(name, map);
    }

    template <typename Reader, typename Map>
    GraphReader& readNodeMap(std::string name, Map& map, const Reader& reader = Reader()) {
      if (node_map_readers.find(name) != node_map_readers.end()) {
	throw Exception() << "Multiple read rule for node map: " << name;
      }
      node_map_readers.insert(make_pair(name, new MapReader<Node, Map, Reader>(map, reader)));
      return *this;
    }

    template <typename Reader>
    GraphReader& skipNodeMap(std::string name, const Reader& reader = Reader()) {
      if (node_map_readers.find(name) != node_map_readers.end()) {
	throw Exception() << "Multiple read rule for node map: " << name;
      }
      node_map_readers.insert(make_pair(name, new SkipReader<Node, Reader>(reader)));
      return *this;
    }

    // Edge map rules

    template <typename Map>
    GraphReader& readEdgeMap(std::string name, Map& map) { 
      return readEdgeMap<typename ReaderTraits::template Reader<typename Map::Value>, Map>(name, map);
    }


    template <typename Reader, typename Map>
    GraphReader& readEdgeMap(std::string name, Map& map, const Reader& reader = Reader()) {
      if (edge_map_readers.find(name) != edge_map_readers.end()) {
	throw Exception() << "Multiple read rule for edge map: " << name;
      }
      edge_map_readers.insert(make_pair(name, new MapReader<Edge, Map, Reader>(map, reader)));
      return *this;
    }

    template <typename Reader>
    GraphReader& skipEdgeMap(std::string name, const Reader& reader = Reader()) {
      if (edge_map_readers.find(name) != edge_map_readers.end()) {
	throw Exception() << "Multiple read rule for edge map: " << name;
      }
      edge_map_readers.insert(make_pair(name, new SkipReader<Edge, Reader>(reader)));
      return *this;
    }

    // Node rules
    GraphReader& readNode(std::string name, Node& node) {
      if (node_readers.find(name) != node_readers.end()) {
	throw Exception() << "Multiple read rule for node";
      }
      node_readers.insert(make_pair(name, &node));
    }

    // Edge rules

    GraphReader& readEdge(std::string name, Edge& edge) {
      if (edge_readers.find(name) != edge_readers.end()) {
	throw Exception() << "Multiple read rule for edge";
      }
      edge_readers.insert(make_pair(name, &edge));
    }

    void read() {
      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 DataFormatException("Invalid control sequence: " + line);
	}
      } catch (DataFormatException e) {
	throw StreamException<DataFormatException>(line_num, e);
      }
    }

  private:

    template <typename Item> class InverterBase;

    std::string readNodeSet(int& line_num, 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) {
	  if (id[0] == '#') break;
	  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 (index.size() == 0) {
	throw DataFormatException("No node map found");
      }

      nodeInverter = 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);
	nodeInverter->read(ls, node);
	for (int i = 1; i < index.size(); ++i) {
	  index[i]->read(ls, node);
	}
      }
      return line;
    }

    std::string readEdgeSet(int& line_num, 
		     auto_ptr<InverterBase<Edge> > & edgeInverter, 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) {
	  if (id[0] == '#') break;
	  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 (index.size() == 0) {
	throw DataFormatException("No edge map found");
      }

      edgeInverter = 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);
	edgeInverter->read(ls, edge);
	for (int i = 1; i < index.size(); ++i) {
	  index[i]->read(ls, edge);
	}
      }      
      return line;
    }

    std::string readNodes(int& line_num, auto_ptr<InverterBase<Node> >& nodeInverter) {
      std::string line;
      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, auto_ptr<InverterBase<Edge> >& edgeInverter) {
      std::string line;
      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_first_not_of(" \t");
	if (vi != string::npos && line[vi] != '#') {
	  return line.substr(vi);
	}
      }
      throw DataFormatException("End of stream");
    }
    
    // Inverters store and give back the Item from the id,
    // and may put the ids into a map.
    
    template <typename _Item>
    class InverterBase {
    public:
      typedef _Item Item;
      virtual void read(std::istream&, const Item&) = 0;
      virtual Item read(std::istream&) = 0;
    };

    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 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(make_pair(value, item));
	} else {
	  throw DataFormatException("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 DataFormatException("Invalid ID");
	}
      }      
    };

    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 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(make_pair(value, item));
	} else {
	  throw DataFormatException("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 DataFormatException("Invalid ID");
	}
      }      
    private:
      Inverse inverse;
    };

    // Readers

    template <typename _Item>    
    class ReaderBase {
    public:
      typedef _Item Item;

      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 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 void read(std::istream& is, const Item& 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;

  };

}