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

    }

  };

  class StreamException : public IOException {

  public:

    virtual int line() = 0;

  private:

    IOException* exception;

    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 exception");

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

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

	  value += readEscape(is);

	} else {

	  value += c;

	}

      }

      if (!is) throw DataFormatException("Quoted string format exception");

    }

  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(istream& _is, Graph& _graph, const DefaultReader& _reader = DefaultReader()) 

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

    ~GraphReader() {

      for (typename NodeReaders::iterator it = node_readers.begin(); it != node_readers.end(); ++it) {

	delete it->second;

      }

      for (typename EdgeReaders::iterator it = edge_readers.begin(); it != edge_readers.end(); ++it) {

	delete it->second;

      }

    }

    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_readers.find(name) != node_readers.end()) {

	Exception e;

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

	throw e;

      }

      node_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_readers.find(name) != node_readers.end()) {

	Exception e;

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

	throw e;

      }

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

      return *this;

    }

    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_readers.find(name) != edge_readers.end()) {

	Exception e;

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

	throw e;

      }

      edge_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_readers.find(name) != edge_readers.end()) {

	Exception e;

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

	throw e;

      }

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

      return *this;

    }

    void read() {

      int line_num = 0;

      InverterBase<Node>* nodeInverter = 0;

      InverterBase<Edge>* edgeInverter = 0;

      // \todo delete the inverters

      //      try {

	{

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

	}

	readNodeSet(line_num, nodeInverter);

	readEdgeSet(line_num, edgeInverter, nodeInverter);

	//      } catch (...){

	if (nodeInverter != 0) delete nodeInverter;

	if (edgeInverter != 0) delete edgeInverter;

	//      }

    }

  private:

    template <typename Item> class InverterBase;

    //    template <typename Item> class InverterBase;

    void readNodeSet(int& line_num, InverterBase<Node>* & nodeInverter) {

      int n = 0;

      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 NodeReaders::iterator it = node_readers.find(id);

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

	    index.push_back(it->second);

	  } else {

	    index.push_back(&nodeSkipper);

	  }

	  ++n;

	}

      }

      nodeInverter = 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 < n; ++i) {

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

	}

      }

    }

    void readEdgeSet(int& line_num, InverterBase<Edge>* & edgeInverter, InverterBase<Node>* & nodeInverter) {

      int n = 0;

      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 EdgeReaders::iterator it = edge_readers.find(id);

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

	    index.push_back(it->second);

	  } else {

	    index.push_back(&edgeSkipper);

	  }

	  ++n;

	}

      }

      edgeInverter = 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 < n; ++i) {

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

	}

      }      

    }

    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 Exception();

    }

    template <typename _Item>

    class InverterBase {

    public:

      typedef _Item Item;

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

      virtual Item read(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(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(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(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(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;

    };

    template <typename _Item>    

    class ReaderBase {

    public:

      typedef _Item Item;

      virtual void read(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(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(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>* > NodeReaders;

    NodeReaders node_readers;

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

    EdgeReaders edge_readers;

    std::istream& is;

    Graph& graph;

    SkipReader<Node, DefaultReader> nodeSkipper;

    SkipReader<Edge, DefaultReader> edgeSkipper;

  };

}