source: lemon-0.x/src/lemon/lemon_reader.h @ 1408:892c29484414

/* -*- C++ -*-
 * src/lemon/lemon_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 Format reader.

#ifndef LEMON_LEMON_READER_H
#define LEMON_LEMON_READER_H

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <memory>

#include <lemon/error.h>
#include "item_reader.h"


namespace lemon {

  /// \addtogroup io_group
  /// @{

  /// \brief Lemon Format reader class.
  /// 
  class LemonReader {
  private:
    
    class FilterStreamBuf : public std::streambuf {
    public:

      typedef std::streambuf Parent;
      typedef Parent::char_type char_type;
      FilterStreamBuf(std::istream& is, int& num) 
        : _is(is), _base(0), _eptr(0), 
          _num(num), skip_state(after_endl) {}

    protected:

      enum skip_state_type {
        no_skip,
        after_comment,
        after_endl,
        empty_line
      };

      char_type small_buf[1];


      std::istream& _is;

      char_type* _base;
      char_type* _eptr;

      int& _num;

      skip_state_type skip_state;


      char_type* base() { return _base; }

      char_type* eptr() { return _eptr; }

      int blen() { return _eptr - _base; }

      void setb(char_type* buf, int len) {
        _base = buf;
        _eptr = buf + len;
      }
  
      virtual std::streambuf* setbuf(char *buf, int len) {
        if (base()) return 0;
        if (buf != 0 && len >= (int)sizeof(small_buf)) {
          setb(buf, len);
        } else {
          setb(small_buf, sizeof(small_buf));
        }
        setg(0, 0, 0);
        return this;
      }

      bool put_char(char c) {
        switch (skip_state) {
        case no_skip:
          switch (c) {
          case '\n': 
            skip_state = after_endl;
            return true;
          case '#':
            skip_state = after_comment;
            return false;
          default:
            return true;
          }
        case after_comment:
          switch (c) {
          case '\n': 
            skip_state = after_endl;
            return true;
          default:
            return false;
          }        
        case after_endl:
          switch (c) {
          case '@':
            return false;
          case '\n': 
            return false;
          case '#':
            skip_state = empty_line;
            return false;
          default:
            if (!isspace(c)) {
              skip_state = no_skip;
              return true;
            } else {
              return false;
            }
          }
          break;
        case empty_line:
          switch (c) {
          case '\n': 
            skip_state = after_endl;
            return false;
          default:
            return false;
          }
        }
        return false;
      }

      virtual int underflow() {
        char c;
        if (_is.read(&c, 1)) {
          _is.putback(c);
          if (c == '@') {
            return EOF;
          }
        } else {
          return EOF;
        }
        char_type *ptr;
        for (ptr = base(); ptr != eptr(); ++ptr) {
          if (_is.read(&c, 1)) {
            if (c == '\n') ++_num;
            if (put_char(c)) {
              *ptr = c;
            } else {
              if (skip_state == after_endl && c == '@') {
                _is.putback('@');
                break;
              }
              --ptr;
            }
          } else {
            break;
          }
        }
        setg(base(), base(), ptr);
        return *base();
      }

      virtual int sync() {
        return EOF;
      }
    };

  public:

    class SectionReader {
    public:
      /// \e
      virtual bool header(const std::string& line) = 0;
      /// \e
      virtual void read(std::istream& is) = 0;
    };

    /// \e
    LemonReader(std::istream& _is) 
      : is(&_is), own_is(false) {}

    LemonReader(const std::string& filename) 
      : is(0), own_is(true) {
      is = new std::ifstream(filename.c_str());
    }


    ~LemonReader() {
      if (own_is) {
        delete is;
      }
    }

  private:
    LemonReader(const LemonReader&);
    void operator=(const LemonReader&);

  public:
    
    /// \e
    void attach(SectionReader& reader) {
      readers.push_back(&reader);
    }

    /// \e
    void detach(SectionReader& reader) {
      std::vector<SectionReader*>::iterator it = 
        std::find(readers.begin(), readers.end(), &reader);
      if (it != readers.end()) {
        readers.erase(it);
      }
    }

    /// \e
    void run() {
      int line_num = 0;
      std::string line;
      try {
        while ((++line_num, getline(*is, line)) && line.find("@end") != 0) {
          SectionReaders::iterator it;
          for (it = readers.begin(); it != readers.end(); ++it) {
            if ((*it)->header(line)) {
              char buf[2048];
              FilterStreamBuf buffer(*is, line_num);
              buffer.pubsetbuf(buf, sizeof(buf));
              std::istream is(&buffer);
              (*it)->read(is);
              break;
            }
          }
        }
      } catch (DataFormatError& error) {
        error.line(line_num);
        throw error;
      } 
    }


  private:

    std::istream* is;
    bool own_is;

    typedef std::vector<SectionReader*> SectionReaders;
    SectionReaders readers;

  };


  /// \e
  class CommonSectionReaderBase : public LemonReader::SectionReader {
  protected:
    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&) const = 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) const {
        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) const {
        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);
      }
    };

    template <typename _Item>
    class ResolverReaderBase {
    public:
      typedef _Item Item;
      virtual Item resolve(std::istream& is) const = 0;
    };

    template <typename _Item, typename _Resolver>
    class ResolverReader : public ResolverReaderBase<_Item> {
    public:
      typedef _Item Item;
      typedef _Resolver Resolver;

      const Resolver& resolver;

      ResolverReader(const Resolver& _resolver) 
        : resolver(_resolver) {}

      virtual Item resolve(std::istream& is) const {
        return resolver.resolve(is);
      }
    };

    class ValueReaderBase {
    public:
      virtual void read(std::istream&) {};
    };

    template <typename _Value, typename _Reader>
    class ValueReader : public ValueReaderBase {
    public:
      typedef _Value Value;
      typedef _Reader Reader;

      ValueReader(Value& _value, const Reader& _reader)
        : value(_value), reader(_reader) {}

      virtual void read(std::istream& is) {
        reader.read(is, value);
      }
    private:
      Value& value;
      Reader reader;
    };
    
  };


  template <typename _Graph, typename _Traits = DefaultReaderTraits>
  class NodeSetReader : public CommonSectionReaderBase {
    typedef CommonSectionReaderBase Parent;
  public:

    typedef _Graph Graph;
    typedef _Traits Traits;
    typedef typename Graph::Node Item;
    typedef typename Traits::Skipper DefaultSkipper;

    NodeSetReader(LemonReader& _reader, Graph& _graph, 
                  const std::string& _id = std::string(),
                  const DefaultSkipper& _defreader = DefaultSkipper()) 
      : graph(_graph), id(_id), skipper(_defreader) {
      _reader.attach(*this);
    } 

    virtual ~NodeSetReader() {
      for (typename MapReaders::iterator it = readers.begin(); 
           it != readers.end(); ++it) {
        delete it->second;
      }
    }

  private:
    NodeSetReader(const NodeSetReader&);
    void operator=(const NodeSetReader&);
  
  public:

    /// \brief Add a new node map reader command for the reader.
    ///
    /// Add a new node map reader command for the reader.
    template <typename Map>
    NodeSetReader& readMap(std::string name, Map& map) {
      return readMap<typename Traits::
        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>
    NodeSetReader& readMap(std::string name, Map& map, 
                             const Reader& reader = Reader()) {
      if (readers.find(name) != readers.end()) {
        ErrorMessage msg;
        msg << "Multiple read rule for node map: " << name;
        throw IOParameterError(msg.message());
      }
      readers.insert(
        make_pair(name, new MapReader<Item, 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>
    NodeSetReader& skipMap(std::string name, 
                           const Reader& reader = Reader()) {
      if (readers.find(name) != readers.end()) {
        ErrorMessage msg;
        msg << "Multiple read rule for node map: " << name;
        throw IOParameterError(msg.message());
      }
      readers.insert(make_pair(name, new SkipReader<Item, Reader>(reader)));
      return *this;
    }

    /// \e
    virtual bool header(const std::string& line) {
      std::istringstream ls(line);
      std::string command;
      std::string name;
      ls >> command >> name;
      return command == "@nodeset" && name == id;
    }

    /// \e
    virtual void read(std::istream& is) {
      std::vector<ReaderBase<Item>* > index;
      std::string line;

      getline(is, line);
      std::istringstream ls(line);      
      while (ls >> id) {
        typename MapReaders::iterator it = readers.find(id);
        if (it != readers.end()) {
          index.push_back(it->second);
        } else {
          index.push_back(&skipper);
        }
        if (id == "id" && inverter.get() == 0) {
          inverter.reset(index.back()->getInverter());
          index.back() = inverter.get();
        }
      }
      while (getline(is, line)) {       
        typename Graph::Node node = graph.addNode();
        std::istringstream ls(line);
        for (int i = 0; i < (int)index.size(); ++i) {
          index[i]->read(ls, node);
        }
      }
    }

    bool isResolver() const {
      return inverter.get() != 0;
    }

    typename Graph::Node resolve(std::istream& is) const {
      return inverter->read(is);
    } 

  private:

    typedef std::map<std::string, ReaderBase<Item>*> MapReaders;
    MapReaders readers;
   
    Graph& graph;   
    std::string id;
    SkipReader<Item, DefaultSkipper> skipper;

    std::auto_ptr<InverterBase<Item> > inverter;
  };


 
  /// \e
  template <typename _Graph, typename _Traits = DefaultReaderTraits>
  class EdgeSetReader : public CommonSectionReaderBase {
    typedef CommonSectionReaderBase Parent;
  public:

    typedef _Graph Graph;
    typedef _Traits Traits;
    typedef typename Graph::Edge Item;
    typedef typename Traits::Skipper DefaultSkipper;

    template <typename Resolver>
    EdgeSetReader(LemonReader& _reader, Graph& _graph, 
                  const Resolver& _nodeResolver, 
                  const std::string& _id = std::string(),
                  const DefaultSkipper& _defreader = DefaultSkipper()) 
      : graph(_graph), id(_id), skipper(_defreader),
      nodeResolver(new ResolverReader<typename Graph::Node, Resolver>
                   (_nodeResolver)) {
      _reader.attach(*this);
    } 

    virtual ~EdgeSetReader() {
      for (typename MapReaders::iterator it = readers.begin(); 
           it != readers.end(); ++it) {
        delete it->second;
      }
    }

  private:
    EdgeSetReader(const EdgeSetReader&);
    void operator=(const EdgeSetReader&);

  public:

    /// \brief Add a new node map reader command for the reader.
    ///
    /// Add a new node map reader command for the reader.
    template <typename Map>
    EdgeSetReader& readMap(std::string name, Map& map) {
      return readMap<typename Traits::
        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>
    EdgeSetReader& readMap(std::string name, Map& map, 
                             const Reader& reader = Reader()) {
      if (readers.find(name) != readers.end()) {
        ErrorMessage msg;
        msg << "Multiple read rule for edge map: " << name;
        throw IOParameterError(msg.message());
      }
      readers.insert(
        make_pair(name, new MapReader<Item, 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>
    EdgeSetReader& skipMap(std::string name, 
                           const Reader& reader = Reader()) {
      if (readers.find(name) != readers.end()) {
        ErrorMessage msg;
        msg << "Multiple read rule for node map: " << name;
        throw IOParameterError(msg.message());
      }
      readers.insert(make_pair(name, new SkipReader<Item, Reader>(reader)));
      return *this;
    }

    /// \e
    virtual bool header(const std::string& line) {
      std::istringstream ls(line);
      std::string command;
      std::string name;
      ls >> command >> name;
      return command == "@edgeset" && name == id;
    }

    /// \e
    virtual void read(std::istream& is) {
      std::vector<ReaderBase<Item>* > index;
      std::string line;

      getline(is, line);
      std::istringstream ls(line);      
      while (ls >> id) {
        typename MapReaders::iterator it = readers.find(id);
        if (it != readers.end()) {
          index.push_back(it->second);
        } else {
          index.push_back(&skipper);
        }
        if (id == "id" && inverter.get() == 0) {
          inverter.reset(index.back()->getInverter());
          index.back() = inverter.get();
        }
      }
      while (getline(is, line)) {       
        std::istringstream ls(line);
        typename Graph::Node from = nodeResolver->resolve(ls);
        typename Graph::Node to = nodeResolver->resolve(ls);
        typename Graph::Edge edge = graph.addEdge(from, to);
        for (int i = 0; i < (int)index.size(); ++i) {
          index[i]->read(ls, edge);
        }
      }
    }

    bool isResolver() const {
      return inverter.get() != 0;
    }

    typename Graph::Edge resolve(std::istream& is) {
      return inverter->read(is);
    } 

  private:

    typedef std::map<std::string, ReaderBase<Item>*> MapReaders;
    MapReaders readers;
   
    Graph& graph;   
    std::string id;
    SkipReader<Item, DefaultSkipper> skipper;

    std::auto_ptr<InverterBase<Item> > inverter;
    std::auto_ptr<ResolverReaderBase<typename Graph::Node> > nodeResolver;
  };


  /// \e
  template <typename _Traits = DefaultReaderTraits>
  class AttributeReader : public CommonSectionReaderBase {
    typedef CommonSectionReaderBase Parent;
    typedef _Traits Traits; 
  public:
    /// \e
    AttributeReader(LemonReader& _reader, 
                    const std::string& _id = std::string()) : id(_id) {
      _reader.attach(*this);
    }

    /// \e
    virtual ~AttributeReader() {
      for (typename Readers::iterator it = readers.begin(); 
           it != readers.end(); ++it) {
        delete it->second;
      }
    }

  private:
    AttributeReader(const AttributeReader&);
    void operator=(AttributeReader&);

  public:
    /// \e
    template <typename Value>
    AttributeReader& readAttribute(const std::string& id, Value& value) {
      return readAttribute<typename Traits::template Reader<Value> >
        (id, value);
    }

    /// \e
    template <typename Reader, typename Value>
    AttributeReader& readAttribute(const std::string& name, Value& value,
                                   const Reader& reader = Reader()) {
      if (readers.find(name) != readers.end()) {
        ErrorMessage msg;
        msg << "Multiple read rule for attribute: " << name;
        throw IOParameterError(msg.message());
      }
      readers.insert(make_pair(name, new ValueReader<Value, Reader>
                               (value, reader)));
      return *this;
    }

    /// \e
    bool header(const std::string& line) {
      std::istringstream ls(line);
      std::string command;
      std::string name;
      ls >> command >> name;
      return command == "@attributes" && name == id;
    }

    /// \e
    void read(std::istream& is) {
      std::string line;
      while (getline(is, line)) {
        std::istringstream ls(line);
        std::string id;
        ls >> id;
        typename Readers::iterator it = readers.find(id);
        if (it != readers.end()) {
          it->second->read(ls);
        }
      }
    }    

  private:
    std::string id;

    typedef std::map<std::string, ValueReaderBase*> Readers;
    Readers readers;
  
  };

  template <typename _Graph>
  class NodeReader : public CommonSectionReaderBase {
    typedef CommonSectionReaderBase Parent;
    typedef _Graph Graph;
    typedef typename Graph::Node Item;
  public:
    
    template <typename Resolver>
    NodeReader(LemonReader& _reader, const Resolver& _resolver, 
               const std::string& _id = std::string()) 
      : id(_id), resolver(new ResolverReader<typename Graph::Node, Resolver>
                     (_resolver)) {
      _reader.attach(*this);
    } 

    virtual ~NodeReader() {}

  private:
    NodeReader(const NodeReader&);
    void operator=(const NodeReader&);

  public:

    void readNode(const std::string& name, Item& item) {
      if (readers.find(name) != readers.end()) {
        ErrorMessage msg;
        msg << "Multiple read rule for node: " << name;
        throw IOParameterError(msg.message());
      }
      readers.insert(make_pair(name, &item));
    }

    virtual bool header(const std::string& line) {
      std::istringstream ls(line);
      std::string command;
      std::string name;
      ls >> command >> name;
      return command == "@nodes" && name == id;
    }

    virtual void read(std::istream& is) {
      std::string line;
      while (getline(is, line)) {
        std::istringstream ls(line);
        std::string id;
        ls >> id;
        typename ItemReaders::iterator it = readers.find(id);
        if (it != readers.end()) {
          *(it->second) = resolver->resolve(ls); 
        }       
      }
    }
    
  private:

    std::string id;

    typedef std::map<std::string, Item*> ItemReaders;
    ItemReaders readers;
    std::auto_ptr<ResolverReaderBase<Item> > resolver;
  };

  template <typename _Graph>
  class EdgeReader : public CommonSectionReaderBase {
    typedef CommonSectionReaderBase Parent;
    typedef _Graph Graph;
    typedef typename Graph::Edge Item;
  public:
    
    template <typename Resolver>
    EdgeReader(LemonReader& _reader, const Resolver& _resolver, 
               const std::string& _id = std::string()) 
      : id(_id), resolver(new ResolverReader<typename Graph::Node, Resolver>
                     (_resolver)) {
      _reader.attach(*this);
    } 

    virtual ~EdgeReader() {}
  private:
    EdgeReader(const EdgeReader&);
    void operator=(const EdgeReader&);

  public:

    void readEdge(const std::string& name, Item& item) {
      if (readers.find(name) != readers.end()) {
        ErrorMessage msg;
        msg << "Multiple read rule for edge: " << name;
        throw IOParameterError(msg.message());
      }
      readers.insert(make_pair(name, &item));
    }


    virtual bool header(const std::string& line) {
      std::istringstream ls(line);
      std::string command;
      std::string name;
      ls >> command >> name;
      return command == "@nodes" && name == id;
    }

    virtual void read(std::istream& is) {
      std::string line;
      while (getline(is, line)) {
        std::istringstream ls(line);
        std::string id;
        ls >> id;
        typename ItemReaders::iterator it = readers.find(id);
        if (it != readers.end()) {
          *(it->second) = resolver->resolve(ls); 
        }       
      }
    }
    
  private:

    std::string id;

    typedef std::map<std::string, Item*> ItemReaders;
    ItemReaders readers;
    std::auto_ptr<ResolverReaderBase<Item> > resolver;
  };

  /// \e
  class PrintReader : public LemonReader::SectionReader {
    typedef LemonReader::SectionReader Parent;
  public:

    /// \e
    PrintReader(LemonReader& reader) {
      reader.attach(*this);
    }

    /// \e
    bool header(const std::string& line) {
      std::cout << "Asked header: " << line << std::endl; 
      return true;
    }

    /// \e
    void read(std::istream& is) {
      std::string line;
      while (std::getline(is, line)) {
        std::cout << line << std::endl;
      }
    }
  
  };

  /// @}
}
#endif