diff -r 8d066154b66a -r 83a48cfd8553 src/lemon/graph_reader.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/lemon/graph_reader.h	Mon Feb 07 11:29:25 2005 +0000
@@ -0,0 +1,674 @@
+/* -*- 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 ~IOException() {}
+    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) 
+      : Exception(_exception), line_num(_line) {}
+    virtual int line() const {
+      return line_num;
+    }
+
+    virtual ~StreamException() {}
+
+    virtual std::string what() const {
+      ostringstream os;
+      os << Exception::what() << " in line " << line();
+      return os.str();
+    }
+  private:
+    int line_num;
+  };  
+
+
+  /// \brief Standard ReaderTraits for the GraphReader class.
+  ///
+  /// Standard ReaderTraits for the GraphReader class.
+  /// It defines standard reading method for all type of value. 
+  struct DefaultReaderTraits {
+
+    /// \brief Template class for reading an value.
+    ///
+    /// Template class for reading an value.
+    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 DataFormatException("Default Reader format exception");
+      }
+    };
+
+    /// 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.
+  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 >> 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;
+  };
+
+  /// \brief The graph reader class.
+  ///
+  /// The reader class for the graph input.
+  /// \see graph-io-page
+  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 from the given map,
+    /// it constructs the given map 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()) {
+	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;
+    }
+
+    /// \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()) {
+	throw Exception() << "Multiple read rule for node map: " << name;
+      }
+      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()) {
+	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;
+    }
+
+    /// \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()) {
+	throw Exception() << "Multiple read rule for edge map: " << name;
+      }
+      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()) {
+	throw Exception() << "Multiple read rule for node";
+      }
+      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()) {
+	throw Exception() << "Multiple read rule for edge";
+      }
+      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 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 < (int)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 < (int)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 != (int)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 ~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(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 ~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(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 ~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& 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;
+
+  };
+
+}