Changeset 1413:3f45d58969d4 in lemon0.x
 Timestamp:
 05/11/05 19:36:25 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1882
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/graph_utils.h
r1402 r1413 23 23 #include <lemon/invalid.h> 24 24 #include <lemon/utility.h> 25 #include <lemon/maps.h> 25 26 26 27 ///\ingroup gutils … … 340 341 /// @{ 341 342 342 /// Provides an immutable and unique id for each item in the graph.343 344 /// The IdMap class provides an unique and immutable mapping for each item345 /// in the graph.346 ///347 template <typename _Graph, typename _Item>348 class IdMap {349 public:350 typedef _Graph Graph;351 typedef int Value;352 typedef _Item Item;353 typedef _Item Key;354 355 /// \brief The class represents the inverse of the map.356 ///357 /// The class represents the inverse of the map.358 /// \see inverse()359 class InverseMap {360 public:361 /// \brief Constructor.362 ///363 /// Constructor for creating an idtoitem map.364 InverseMap(const Graph& _graph) : graph(&_graph) {}365 /// \brief Gives back the given item from its id.366 ///367 /// Gives back the given item from its id.368 ///369 Item operator[](int id) const { return graph>fromId(id, Item());}370 private:371 const Graph* graph;372 };373 374 /// \brief Constructor.375 ///376 /// Constructor for creating id map.377 IdMap(const Graph& _graph) : graph(&_graph) {}378 379 /// \brief Gives back the \e id of the item.380 ///381 /// Gives back the immutable and unique \e id of the map.382 int operator[](const Item& item) const { return graph>id(item);}383 384 /// \brief Gives back the inverse of the map.385 ///386 /// Gives back the inverse of the map.387 InverseMap inverse() const { return InverseMap(*graph);}388 389 private:390 const Graph* graph;391 392 };393 394 395 343 template <typename Map, typename Enable = void> 396 344 struct ReferenceMapTraits { … … 414 362 }; 415 363 364 365 /// Provides an immutable and unique id for each item in the graph. 366 367 /// The IdMap class provides an unique and immutable mapping for each item 368 /// in the graph. 369 /// 370 template <typename _Graph, typename _Item> 371 class IdMap { 372 public: 373 typedef _Graph Graph; 374 typedef int Value; 375 typedef _Item Item; 376 typedef _Item Key; 377 378 /// \brief Constructor. 379 /// 380 /// Constructor for creating id map. 381 IdMap(const Graph& _graph) : graph(&_graph) {} 382 383 /// \brief Gives back the \e id of the item. 384 /// 385 /// Gives back the immutable and unique \e id of the map. 386 int operator[](const Item& item) const { return graph>id(item);} 387 388 389 private: 390 const Graph* graph; 391 392 public: 393 394 /// \brief The class represents the inverse of the map. 395 /// 396 /// The class represents the inverse of the map. 397 /// \see inverse() 398 class InverseMap { 399 public: 400 /// \brief Constructor. 401 /// 402 /// Constructor for creating an idtoitem map. 403 InverseMap(const Graph& _graph) : graph(&_graph) {} 404 405 /// \brief Constructor. 406 /// 407 /// Constructor for creating an idtoitem map. 408 InverseMap(const IdMap& idMap) : graph(idMap.graph) {} 409 410 /// \brief Gives back the given item from its id. 411 /// 412 /// Gives back the given item from its id. 413 /// 414 Item operator[](int id) const { return graph>fromId(id, Item());} 415 private: 416 const Graph* graph; 417 }; 418 419 /// \brief Gives back the inverse of the map. 420 /// 421 /// Gives back the inverse of the map. 422 InverseMap inverse() const { return InverseMap(*graph);} 423 424 }; 425 426 416 427 /// \brief General inversable graphmap type. 417 428 … … 427 438 typename _Value, 428 439 typename _Map 429 = typename ItemSetTraits<_Graph, _Item>::template Map<_Value> 440 = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent 430 441 > 431 class Inver sableMap : protected _Map {442 class InvertableMap : protected _Map { 432 443 433 444 public: … … 435 446 typedef _Map Map; 436 447 typedef _Graph Graph; 437 /// The key type of InversableMap (Node, Edge, UndirEdge). 448 449 /// The key type of InvertableMap (Node, Edge, UndirEdge). 438 450 typedef typename _Map::Key Key; 439 /// The value type of the Inver sableMap.451 /// The value type of the InvertableMap. 440 452 typedef typename _Map::Value Value; 441 453 442 typedef std::map<Value, Key> InverseMap;443 444 typedef typename _Map::ConstReference ConstReference;445 446 454 /// \brief Constructor. 447 455 /// 448 /// Construct a new Inver sableMap for the graph.449 /// 450 Inver sableMap(const Graph& graph) : Map(graph) {}456 /// Construct a new InvertableMap for the graph. 457 /// 458 InvertableMap(const Graph& graph) : Map(graph) {} 451 459 452 460 /// \brief The setter function of the map. 453 461 /// 454 462 /// Sets the mapped value. 455 463 void set(const Key& key, const Value& val) { 456 464 Value oldval = Map::operator[](key); 457 typename InverseMap::iterator it = invMap.find(oldval);465 typename Container::iterator it = invMap.find(oldval); 458 466 if (it != invMap.end() && it>second == key) { 459 467 invMap.erase(it); … … 466 474 /// 467 475 /// It gives back the value associated with the key. 468 ConstReference operator[](const Key& key) const {476 const Value operator[](const Key& key) const { 469 477 return Map::operator[](key); 470 478 } … … 484 492 virtual void erase(const Key& key) { 485 493 Value val = Map::operator[](key); 486 typename InverseMap::iterator it = invMap.find(val);494 typename Container::iterator it = invMap.find(val); 487 495 if (it != invMap.end() && it>second == key) { 488 496 invMap.erase(it); … … 500 508 } 501 509 510 private: 511 512 typedef std::map<Value, Key> Container; 513 Container invMap; 514 515 public: 516 517 /// \brief The inverse map type. 518 /// 519 /// The inverse of this map. The subscript operator of the map 520 /// gives back always the item what was last assigned to the value. 521 class InverseMap { 522 public: 523 /// \brief Constructor of the InverseMap. 524 /// 525 /// Constructor of the InverseMap. 526 InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {} 527 528 /// The value type of the InverseMap. 529 typedef typename InvertableMap::Key Value; 530 /// The key type of the InverseMap. 531 typedef typename InvertableMap::Value Key; 532 533 /// \brief Subscript operator. 534 /// 535 /// Subscript operator. It gives back always the item 536 /// what was last assigned to the value. 537 Value operator[](const Key& key) const { 538 typename Container::const_iterator it = inverted.invMap.find(key); 539 return it>second; 540 } 541 542 private: 543 const InvertableMap& inverted; 544 }; 545 502 546 /// \brief It gives back the just readeable inverse map. 503 547 /// 504 548 /// It gives back the just readeable inverse map. 505 const InverseMap&inverse() const {506 return invMap;549 InverseMap inverse() const { 550 return InverseMap(*this); 507 551 } 508 552 509 553 510 private: 511 InverseMap invMap; 554 512 555 }; 513 556 … … 516 559 /// 517 560 /// The DescriptorMap class provides a mutable, continuous and immutable 518 /// mapping for each item in the graph. 561 /// mapping for each item in the graph. The value for an item may mutated 562 /// on each operation when the an item erased or added to graph. 519 563 /// 520 564 /// \param _Graph The graph class the \c DescriptorMap belongs to. … … 522 566 /// UndirEdge. 523 567 /// \param _Map A ReadWriteMap mapping from the item type to integer. 524 525 568 template < 526 569 typename _Graph, 527 570 typename _Item, 528 typename _Map = typename ItemSetTraits<_Graph, _Item>::template Map<int> 571 typename _Map 572 = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent 529 573 > 530 574 class DescriptorMap : protected _Map { … … 542 586 typedef typename _Map::Value Value; 543 587 544 typedef std::vector<Item> InverseMap;545 546 588 /// \brief Constructor. 547 589 /// 548 /// Constructor for creatingdescriptor map.590 /// Constructor for descriptor map. 549 591 DescriptorMap(const Graph& _graph) : Map(_graph) { 550 592 build(); … … 568 610 Map::set(invMap.back(), Map::operator[](item)); 569 611 invMap[Map::operator[](item)] = invMap.back(); 612 invMap.pop_back(); 570 613 Map::erase(item); 571 614 } … … 601 644 } 602 645 646 private: 647 648 typedef std::vector<Item> Container; 649 Container invMap; 650 651 public: 652 /// \brief The inverse map type. 653 /// 654 /// The inverse map type. 655 class InverseMap { 656 public: 657 /// \brief Constructor of the InverseMap. 658 /// 659 /// Constructor of the InverseMap. 660 InverseMap(const DescriptorMap& _inverted) 661 : inverted(_inverted) {} 662 663 664 /// The value type of the InverseMap. 665 typedef typename DescriptorMap::Key Value; 666 /// The key type of the InverseMap. 667 typedef typename DescriptorMap::Value Key; 668 669 /// \brief Subscript operator. 670 /// 671 /// Subscript operator. It gives back the item 672 /// that the descriptor belongs to currently. 673 Value operator[](const Key& key) const { 674 return inverted.invMap[key]; 675 } 676 677 private: 678 const DescriptorMap& inverted; 679 }; 680 603 681 /// \brief Gives back the inverse of the map. 604 682 /// 605 683 /// Gives back the inverse of the map. 606 684 const InverseMap inverse() const { 607 return invMap; 608 } 609 610 private: 611 std::vector<Item> invMap; 685 return InverseMap(*this); 686 } 612 687 }; 613 688
Note: See TracChangeset
for help on using the changeset viewer.