00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00020
00021 #include <iostream>
00022 #include <sstream>
00023
00024 #include <map>
00025 #include <vector>
00026
00027 #include <memory>
00028
00029 #include <lemon/error.h>
00030
00032
00033
00034 namespace lemon {
00035
00036
00037
00038 class IOException {
00039 public:
00040 virtual ~IOException() {}
00041 virtual string what() const = 0;
00042 };
00043
00044 class DataFormatException : public IOException {
00045 std::string message;
00046 public:
00047 DataFormatException(const std::string& _message)
00048 : message(_message) {}
00049 std::string what() const {
00050 return "DataFormatException: " + message;
00051 }
00052 };
00053
00054 template <typename _Exception>
00055 class StreamException : public _Exception {
00056 public:
00057 typedef _Exception Exception;
00058 StreamException(int _line, Exception _exception)
00059 : Exception(_exception), line_num(_line) {}
00060 virtual int line() const {
00061 return line_num;
00062 }
00063
00064 virtual ~StreamException() {}
00065
00066 virtual std::string what() const {
00067 ostringstream os;
00068 os << Exception::what() << " in line " << line();
00069 return os.str();
00070 }
00071 private:
00072 int line_num;
00073 };
00074
00075
00080 struct DefaultReaderTraits {
00081
00085 template <typename _Value>
00086 struct Reader {
00088 typedef _Value Value;
00092 void read(std::istream& is, Value& value) {
00093 if (!(is >> value))
00094 throw DataFormatException("Default Reader format exception");
00095 }
00096 };
00097
00099 typedef Reader<std::string> DefaultReader;
00100
00101 };
00102
00107 class QuotedStringReader {
00108 public:
00109 typedef std::string Value;
00110
00115 QuotedStringReader(bool _escaped = true) : escaped(_escaped) {}
00116
00120 void read(std::istream& is, std::string& value) {
00121 char c;
00122 value.clear();
00123 is >> ws;
00124 if (!is.get(c) || c != '\"')
00125 throw DataFormatException("Quoted string format");
00126 while (is.get(c) && c != '\"') {
00127 if (escaped && c == '\\') {
00128 value += readEscape(is);
00129 } else {
00130 value += c;
00131 }
00132 }
00133 if (!is) throw DataFormatException("Quoted string format");
00134 }
00135
00136 private:
00137
00138 static char readEscape(std::istream& is) {
00139 char c;
00140 switch (is.get(c), c) {
00141 case '\\':
00142 return '\\';
00143 case '\"':
00144 return '\"';
00145 case '\'':
00146 return '\'';
00147 case '\?':
00148 return '\?';
00149 case 'a':
00150 return '\a';
00151 case 'b':
00152 return '\b';
00153 case 'f':
00154 return '\f';
00155 case 'n':
00156 return '\n';
00157 case 'r':
00158 return '\r';
00159 case 't':
00160 return '\t';
00161 case 'v':
00162 return '\v';
00163 case 'x':
00164 {
00165 int code;
00166 if (!is.get(c) || !isHex(c))
00167 throw DataFormatException("Escape format exception");
00168 else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
00169 else code = code * 16 + valueHex(c);
00170 return code;
00171 }
00172 default:
00173 {
00174 int code;
00175 if (!isOct(c))
00176 throw DataFormatException("Escape format exception");
00177 else if (code = valueOct(c), !is.get(c) || !isOct(c))
00178 is.putback(c);
00179 else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c))
00180 is.putback(c);
00181 else code = code * 8 + valueOct(c);
00182 return code;
00183 }
00184 }
00185 }
00186
00187 static bool isOct(char c) {
00188 return '0' <= c && c <='7';
00189 }
00190
00191 static int valueOct(char c) {
00192 return c - '0';
00193 }
00194
00195 static bool isHex(char c) {
00196 return ('0' <= c && c <= '9') ||
00197 ('a' <= c && c <= 'z') ||
00198 ('A' <= c && c <= 'Z');
00199 }
00200
00201 static int valueHex(char c) {
00202 if ('0' <= c && c <= '9') return c - '0';
00203 if ('a' <= c && c <= 'z') return c - 'a' + 10;
00204 return c - 'A' + 10;
00205 }
00206
00207 bool escaped;
00208 };
00209
00215 template <typename _Graph, typename _ReaderTraits = DefaultReaderTraits>
00216 class GraphReader {
00217 public:
00218
00219 typedef _Graph Graph;
00220 typedef typename Graph::Node Node;
00221 typedef typename Graph::Edge Edge;
00222
00223 typedef _ReaderTraits ReaderTraits;
00224 typedef typename ReaderTraits::DefaultReader DefaultReader;
00225
00231 GraphReader(std::istream& _is, Graph& _graph,
00232 const DefaultReader& _reader = DefaultReader())
00233 : is(_is), graph(_graph), nodeSkipper(_reader), edgeSkipper(_reader) {}
00234
00238 ~GraphReader() {
00239
00240 for (typename NodeMapReaders::iterator it = node_map_readers.begin();
00241 it != node_map_readers.end(); ++it) {
00242 delete it->second;
00243 }
00244
00245 for (typename EdgeMapReaders::iterator it = edge_map_readers.begin();
00246 it != edge_map_readers.end(); ++it) {
00247 delete it->second;
00248 }
00249
00250 }
00251
00255 template <typename Map>
00256 GraphReader& addNodeMap(std::string name, Map& map) {
00257 return addNodeMap<typename ReaderTraits::template
00258 Reader<typename Map::Value>, Map>(name, map);
00259 }
00260
00264 template <typename Reader, typename Map>
00265 GraphReader& addNodeMap(std::string name, Map& map,
00266 const Reader& reader = Reader()) {
00267 if (node_map_readers.find(name) != node_map_readers.end()) {
00268 throw Exception() << "Multiple read rule for node map: " << name;
00269 }
00270 node_map_readers.insert(
00271 make_pair(name, new MapReader<Node, Map, Reader>(map, reader)));
00272 return *this;
00273 }
00274
00278 template <typename Reader>
00279 GraphReader& skipNodeMap(std::string name,
00280 const Reader& reader = Reader()) {
00281 if (node_map_readers.find(name) != node_map_readers.end()) {
00282 throw Exception() << "Multiple read rule for node map: " << name;
00283 }
00284 node_map_readers.insert(
00285 make_pair(name, new SkipReader<Node, Reader>(reader)));
00286 return *this;
00287 }
00288
00292 template <typename Map>
00293 GraphReader& addEdgeMap(std::string name, Map& map) {
00294 return addEdgeMap<typename ReaderTraits::template
00295 Reader<typename Map::Value>, Map>(name, map);
00296 }
00297
00298
00302 template <typename Reader, typename Map>
00303 GraphReader& addEdgeMap(std::string name, Map& map,
00304 const Reader& reader = Reader()) {
00305 if (edge_map_readers.find(name) != edge_map_readers.end()) {
00306 throw Exception() << "Multiple read rule for edge map: " << name;
00307 }
00308 edge_map_readers.insert(
00309 make_pair(name, new MapReader<Edge, Map, Reader>(map, reader)));
00310 return *this;
00311 }
00312
00316 template <typename Reader>
00317 GraphReader& skipEdgeMap(std::string name,
00318 const Reader& reader = Reader()) {
00319 if (edge_map_readers.find(name) != edge_map_readers.end()) {
00320 throw Exception() << "Multiple read rule for edge map: " << name;
00321 }
00322 edge_map_readers.insert(
00323 make_pair(name, new SkipReader<Edge, Reader>(reader)));
00324 return *this;
00325 }
00326
00330 GraphReader& addNode(std::string name, Node& node) {
00331 if (node_readers.find(name) != node_readers.end()) {
00332 throw Exception() << "Multiple read rule for node";
00333 }
00334 node_readers.insert(make_pair(name, &node));
00335 return *this;
00336 }
00337
00341 GraphReader& addEdge(std::string name, Edge& edge) {
00342 if (edge_readers.find(name) != edge_readers.end()) {
00343 throw Exception() << "Multiple read rule for edge";
00344 }
00345 edge_readers.insert(make_pair(name, &edge));
00346 return *this;
00347 }
00348
00352 void run() {
00353 int line_num = 0;
00354 std::auto_ptr<InverterBase<Node> > nodeInverter;
00355 std::auto_ptr<InverterBase<Edge> > edgeInverter;
00356 try {
00357 std::string line = readNotEmptyLine(is, line_num);
00358 if (line.find("@nodeset") == 0) {
00359 line = readNodeSet(line_num, nodeInverter);
00360 }
00361 if (line.find("@edgeset") == 0) {
00362 line = readEdgeSet(line_num, edgeInverter, nodeInverter);
00363 }
00364 if (line.find("@nodes") == 0) {
00365 line = readNodes(line_num, nodeInverter);
00366 }
00367 if (line.find("@edges") == 0) {
00368 line = readEdges(line_num, edgeInverter);
00369 }
00370 if (line.find("@end") != 0) {
00371 throw DataFormatException("Invalid control sequence: " + line);
00372 }
00373 } catch (DataFormatException e) {
00374 throw StreamException<DataFormatException>(line_num, e);
00375 }
00376 }
00377
00378 private:
00379
00380 template <typename Item> class InverterBase;
00381
00382 std::string readNodeSet(int& line_num,
00383 auto_ptr<InverterBase<Node> > & nodeInverter) {
00384 std::vector<ReaderBase<Node>* > index;
00385 {
00386 std::string line = readNotEmptyLine(is, line_num);
00387 std::string id;
00388 std::istringstream ls(line);
00389 while (ls >> id) {
00390 if (id[0] == '#') break;
00391 typename NodeMapReaders::iterator it = node_map_readers.find(id);
00392 if (it != node_map_readers.end()) {
00393 index.push_back(it->second);
00394 node_map_readers.erase(it);
00395 } else {
00396 index.push_back(&nodeSkipper);
00397 }
00398 }
00399 }
00400
00401 if (index.size() == 0) {
00402 throw DataFormatException("No node map found");
00403 }
00404
00405 nodeInverter = auto_ptr<InverterBase<Node> >(index[0]->getInverter());
00406 std::string line;
00407 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
00408 Node node = graph.addNode();
00409 std::istringstream ls(line);
00410 nodeInverter->read(ls, node);
00411 for (int i = 1; i < (int)index.size(); ++i) {
00412 index[i]->read(ls, node);
00413 }
00414 }
00415 return line;
00416 }
00417
00418 std::string readEdgeSet(int& line_num,
00419 auto_ptr<InverterBase<Edge> > & edgeInverter,
00420 auto_ptr<InverterBase<Node> > & nodeInverter) {
00421 std::vector<ReaderBase<Edge>*> index;
00422 {
00423 std::string line = readNotEmptyLine(is, line_num);
00424 std::string id;
00425 std::istringstream ls(line);
00426 while (ls >> id) {
00427 if (id[0] == '#') break;
00428 typename EdgeMapReaders::iterator it = edge_map_readers.find(id);
00429 if (it != edge_map_readers.end()) {
00430 index.push_back(it->second);
00431 edge_map_readers.erase(it);
00432 } else {
00433 index.push_back(&edgeSkipper);
00434 }
00435 }
00436 }
00437
00438 if (index.size() == 0) {
00439 throw DataFormatException("No edge map found");
00440 }
00441
00442 edgeInverter = auto_ptr<InverterBase<Edge> >(index[0]->getInverter());
00443 std::string line;
00444 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
00445 std::istringstream ls(line);
00446 Node source = nodeInverter->read(ls);
00447 Node target = nodeInverter->read(ls);
00448 Edge edge = graph.addEdge(source, target);
00449 edgeInverter->read(ls, edge);
00450 for (int i = 1; i < (int)index.size(); ++i) {
00451 index[i]->read(ls, edge);
00452 }
00453 }
00454 return line;
00455 }
00456
00457 std::string readNodes(int& line_num,
00458 auto_ptr<InverterBase<Node> >& nodeInverter) {
00459 std::string line;
00460 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
00461 std::istringstream ls(line);
00462 std::string name;
00463 ls >> name;
00464 typename NodeReaders::iterator it = node_readers.find(name);
00465 if (it != node_readers.end()) {
00466 *(it -> second) = nodeInverter->read(ls);
00467 }
00468 }
00469 return line;
00470 }
00471
00472 std::string readEdges(int& line_num,
00473 auto_ptr<InverterBase<Edge> >& edgeInverter) {
00474 std::string line;
00475 while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
00476 std::istringstream ls(line);
00477 std::string name;
00478 ls >> name;
00479 typename EdgeReaders::iterator it = edge_readers.find(name);
00480 if (it != edge_readers.end()) {
00481 *(it -> second) = edgeInverter->read(ls);
00482 }
00483 }
00484 return line;
00485 }
00486
00487 std::string readNotEmptyLine(std::istream& is, int& line_num) {
00488 std::string line;
00489 while (++line_num, getline(is, line)) {
00490 int vi = line.find_first_not_of(" \t");
00491 if (vi != (int)string::npos && line[vi] != '#') {
00492 return line.substr(vi);
00493 }
00494 }
00495 throw DataFormatException("End of stream");
00496 }
00497
00498
00499
00500
00501 template <typename _Item>
00502 class InverterBase {
00503 public:
00504 typedef _Item Item;
00505 virtual void read(std::istream&, const Item&) = 0;
00506 virtual Item read(std::istream&) = 0;
00507 };
00508
00509 template <typename _Item, typename _Map, typename _Reader>
00510 class MapReaderInverter : public InverterBase<_Item> {
00511 public:
00512 typedef _Item Item;
00513 typedef _Reader Reader;
00514 typedef typename Reader::Value Value;
00515 typedef _Map Map;
00516 typedef std::map<Value, Item> Inverse;
00517
00518 Map& map;
00519 Reader reader;
00520 Inverse inverse;
00521
00522 MapReaderInverter(Map& _map, const Reader& _reader)
00523 : map(_map), reader(_reader) {}
00524
00525 virtual ~MapReaderInverter() {}
00526
00527 virtual void read(std::istream& is, const Item& item) {
00528 Value value;
00529 reader.read(is, value);
00530 map.set(item, value);
00531 typename Inverse::iterator it = inverse.find(value);
00532 if (it == inverse.end()) {
00533 inverse.insert(make_pair(value, item));
00534 } else {
00535 throw DataFormatException("Multiple ID occurence");
00536 }
00537 }
00538
00539 virtual Item read(std::istream& is) {
00540 Value value;
00541 reader.read(is, value);
00542 typename Inverse::const_iterator it = inverse.find(value);
00543 if (it != inverse.end()) {
00544 return it->second;
00545 } else {
00546 throw DataFormatException("Invalid ID");
00547 }
00548 }
00549 };
00550
00551 template <typename _Item, typename _Reader>
00552 class SkipReaderInverter : public InverterBase<_Item> {
00553 public:
00554 typedef _Item Item;
00555 typedef _Reader Reader;
00556 typedef typename Reader::Value Value;
00557 typedef std::map<Value, Item> Inverse;
00558
00559 Reader reader;
00560
00561 SkipReaderInverter(const Reader& _reader)
00562 : reader(_reader) {}
00563
00564 virtual ~SkipReaderInverter() {}
00565
00566 virtual void read(std::istream& is, const Item& item) {
00567 Value value;
00568 reader.read(is, value);
00569 typename Inverse::iterator it = inverse.find(value);
00570 if (it == inverse.end()) {
00571 inverse.insert(make_pair(value, item));
00572 } else {
00573 throw DataFormatException("Multiple ID occurence");
00574 }
00575 }
00576
00577 virtual Item read(std::istream& is) {
00578 Value value;
00579 reader.read(is, value);
00580 typename Inverse::const_iterator it = inverse.find(value);
00581 if (it != inverse.end()) {
00582 return it->second;
00583 } else {
00584 throw DataFormatException("Invalid ID");
00585 }
00586 }
00587 private:
00588 Inverse inverse;
00589 };
00590
00591
00592
00593 template <typename _Item>
00594 class ReaderBase {
00595 public:
00596 typedef _Item Item;
00597
00598
00599
00600 virtual void read(std::istream& is, const Item& item) = 0;
00601 virtual InverterBase<_Item>* getInverter() = 0;
00602 };
00603
00604 template <typename _Item, typename _Map, typename _Reader>
00605 class MapReader : public ReaderBase<_Item> {
00606 public:
00607 typedef _Map Map;
00608 typedef _Reader Reader;
00609 typedef typename Reader::Value Value;
00610 typedef _Item Item;
00611
00612 Map& map;
00613 Reader reader;
00614
00615 MapReader(Map& _map, const Reader& _reader)
00616 : map(_map), reader(_reader) {}
00617
00618 virtual ~MapReader() {}
00619
00620 virtual void read(std::istream& is, const Item& item) {
00621 Value value;
00622 reader.read(is, value);
00623 map.set(item, value);
00624 }
00625
00626 virtual InverterBase<_Item>* getInverter() {
00627 return new MapReaderInverter<Item, Map, Reader>(map, reader);
00628 }
00629 };
00630
00631
00632 template <typename _Item, typename _Reader>
00633 class SkipReader : public ReaderBase<_Item> {
00634 public:
00635 typedef _Reader Reader;
00636 typedef typename Reader::Value Value;
00637 typedef _Item Item;
00638
00639 Reader reader;
00640 SkipReader(const Reader& _reader) : reader(_reader) {}
00641
00642 virtual ~SkipReader() {}
00643
00644 virtual void read(std::istream& is, const Item& item) {
00645 Value value;
00646 reader.read(is, value);
00647 }
00648
00649 virtual InverterBase<Item>* getInverter() {
00650 return new SkipReaderInverter<Item, Reader>(reader);
00651 }
00652 };
00653
00654
00655 typedef std::map<std::string, ReaderBase<Node>*> NodeMapReaders;
00656 NodeMapReaders node_map_readers;
00657
00658 typedef std::map<std::string, ReaderBase<Edge>*> EdgeMapReaders;
00659 EdgeMapReaders edge_map_readers;
00660
00661 typedef std::map<std::string, Node*> NodeReaders;
00662 NodeReaders node_readers;
00663
00664 typedef std::map<std::string, Edge*> EdgeReaders;
00665 EdgeReaders edge_readers;
00666
00667 std::istream& is;
00668 Graph& graph;
00669
00670 SkipReader<Node, DefaultReader> nodeSkipper;
00671 SkipReader<Edge, DefaultReader> edgeSkipper;
00672
00673 };
00674
00675 }