Changeset 698:625de6f1e766 in lemon-0.x for src/work
- Timestamp:
- 07/09/04 09:33:12 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@949
- Location:
- src/work/deba
- Files:
-
- 2 deleted
- 2 edited
- 3 copied
-
bin_heap.h (copied) (copied from src/hugo/bin_heap.h)
-
dijkstra.h (copied) (copied from src/hugo/dijkstra.h)
-
invalid.h (deleted)
-
list_graph.h (copied) (copied from src/hugo/list_graph.h) (11 diffs)
-
main.cpp (modified) (1 diff)
-
test_graph.h (deleted)
-
vector_map_factory.h (modified) (5 diffs)
Legend:
- Unmodified
- Added
- Removed
-
src/work/deba/list_graph.h
r695 r698 9 9 10 10 #include <vector> 11 #include <limits.h> 12 13 #include <hugo/invalid.h> 11 #include <climits> 12 13 #include "invalid.h" 14 15 #include "vector_map_factory.h" 16 #include "map_registry.h" 17 18 #include "map_defines.h" 14 19 15 20 namespace hugo { … … 17 22 /// \addtogroup graphs 18 23 /// @{ 19 20 class SymListGraph;21 24 22 25 ///A list graph class. … … 59 62 protected: 60 63 61 template <typename Key> class DynMapBase62 {63 protected:64 const ListGraph* G;65 public:66 virtual void add(const Key k) = 0;67 virtual void erase(const Key k) = 0;68 DynMapBase(const ListGraph &_G) : G(&_G) {}69 virtual ~DynMapBase() {}70 friend class ListGraph;71 };72 73 64 public: 74 template <typename T> class EdgeMap;75 template <typename T> class NodeMap;76 65 77 66 class Node; 78 67 class Edge; 79 68 80 // protected: 81 // HELPME: 82 protected: 83 ///\bug It must be public because of SymEdgeMap. 84 /// 85 mutable std::vector<DynMapBase<Node> * > dyn_node_maps; 86 ///\bug It must be public because of SymEdgeMap. 87 /// 88 mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps; 89 69 typedef ListGraph Graph; 70 90 71 public: 91 72 … … 95 76 class InEdgeIt; 96 77 78 CREATE_MAP_REGISTRIES; 79 CREATE_MAPS(VectorMapFactory); 80 97 81 public: 98 82 … … 104 88 first_free_edge(_g.first_free_edge) {} 105 89 106 ~ListGraph()107 {108 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();109 i!=dyn_node_maps.end(); ++i) (**i).G=NULL;110 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();111 i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;112 }113 90 114 91 int nodeNum() const { return nodes.size(); } //FIXME: What is this? … … 214 191 215 192 //Update dynamic maps 216 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 217 i!=dyn_node_maps.end(); ++i) (**i).add(nn); 193 node_maps.add(nn); 218 194 219 195 return nn; … … 246 222 247 223 //Update dynamic maps 248 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin(); 249 i!=dyn_edge_maps.end(); ++i) (**i).add(e); 224 edge_maps.add(e); 250 225 251 226 return e; … … 272 247 //Update dynamic maps 273 248 Edge e; e.n=n; 274 for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();275 i!=dyn_edge_maps.end(); ++i) (**i).erase(e);276 249 } 277 250 … … 293 266 294 267 //Update dynamic maps 295 for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin(); 296 i!=dyn_node_maps.end(); ++i) (**i).erase(nn); 297 } 298 299 void erase(Edge e) { eraseEdge(e.n); } 268 node_maps.erase(nn); 269 } 270 271 void erase(Edge e) { 272 edge_maps.erase(e); 273 eraseEdge(e.n); 274 } 300 275 301 276 ///\bug Dynamic maps must be updated! … … 395 370 InEdgeIt (Invalid i) : Edge(i) { } 396 371 InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in) {} 397 };398 399 template <typename T> class NodeMap : public DynMapBase<Node>400 {401 std::vector<T> container;402 403 public:404 typedef T ValueType;405 typedef Node KeyType;406 407 NodeMap(const ListGraph &_G) :408 DynMapBase<Node>(_G), container(_G.maxNodeId())409 {410 G->dyn_node_maps.push_back(this);411 }412 NodeMap(const ListGraph &_G,const T &t) :413 DynMapBase<Node>(_G), container(_G.maxNodeId(),t)414 {415 G->dyn_node_maps.push_back(this);416 }417 418 NodeMap(const NodeMap<T> &m) :419 DynMapBase<Node>(*m.G), container(m.container)420 {421 G->dyn_node_maps.push_back(this);422 }423 424 template<typename TT> friend class NodeMap;425 426 ///\todo It can copy between different types.427 ///428 template<typename TT> NodeMap(const NodeMap<TT> &m) :429 DynMapBase<Node>(*m.G), container(m.container.size())430 431 {432 G->dyn_node_maps.push_back(this);433 typename std::vector<TT>::const_iterator i;434 for(typename std::vector<TT>::const_iterator i=m.container.begin();435 i!=m.container.end();436 i++)437 container.push_back(*i);438 }439 ~NodeMap()440 {441 if(G) {442 std::vector<DynMapBase<Node>* >::iterator i;443 for(i=G->dyn_node_maps.begin();444 i!=G->dyn_node_maps.end() && *i!=this; ++i) ;445 //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...446 //A better way to do that: (Is this really important?)447 if(*i==this) {448 *i=G->dyn_node_maps.back();449 G->dyn_node_maps.pop_back();450 }451 }452 }453 454 void add(const Node k)455 {456 if(k.n>=int(container.size())) container.resize(k.n+1);457 }458 459 void erase(const Node) { }460 461 void set(Node n, T a) { container[n.n]=a; }462 //'T& operator[](Node n)' would be wrong here463 typename std::vector<T>::reference464 operator[](Node n) { return container[n.n]; }465 //'const T& operator[](Node n)' would be wrong here466 typename std::vector<T>::const_reference467 operator[](Node n) const { return container[n.n]; }468 469 ///\warning There is no safety check at all!470 ///Using operator = between maps attached to different graph may471 ///cause serious problem.472 ///\todo Is this really so?473 ///\todo It can copy between different types.474 const NodeMap<T>& operator=(const NodeMap<T> &m)475 {476 container = m.container;477 return *this;478 }479 template<typename TT>480 const NodeMap<T>& operator=(const NodeMap<TT> &m)481 {482 std::copy(m.container.begin(), m.container.end(), container.begin());483 return *this;484 }485 486 void update() {} //Useless for Dynamic Maps487 void update(T a) {} //Useless for Dynamic Maps488 };489 490 template <typename T> class EdgeMap : public DynMapBase<Edge>491 {492 protected:493 std::vector<T> container;494 495 public:496 typedef T ValueType;497 typedef Edge KeyType;498 499 EdgeMap(const ListGraph &_G) :500 DynMapBase<Edge>(_G), container(_G.maxEdgeId())501 {502 //FIXME: What if there are empty Id's?503 //FIXME: Can I use 'this' in a constructor?504 G->dyn_edge_maps.push_back(this);505 }506 EdgeMap(const ListGraph &_G,const T &t) :507 DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)508 {509 G->dyn_edge_maps.push_back(this);510 }511 EdgeMap(const EdgeMap<T> &m) :512 DynMapBase<Edge>(*m.G), container(m.container)513 {514 G->dyn_edge_maps.push_back(this);515 }516 517 template<typename TT> friend class EdgeMap;518 519 ///\todo It can copy between different types.520 ///521 template<typename TT> EdgeMap(const EdgeMap<TT> &m) :522 DynMapBase<Edge>(*m.G), container(m.container.size())523 {524 G->dyn_edge_maps.push_back(this);525 typename std::vector<TT>::const_iterator i;526 for(typename std::vector<TT>::const_iterator i=m.container.begin();527 i!=m.container.end();528 i++)529 container.push_back(*i);530 }531 ~EdgeMap()532 {533 if(G) {534 std::vector<DynMapBase<Edge>* >::iterator i;535 for(i=G->dyn_edge_maps.begin();536 i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;537 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...538 //A better way to do that: (Is this really important?)539 if(*i==this) {540 *i=G->dyn_edge_maps.back();541 G->dyn_edge_maps.pop_back();542 }543 }544 }545 546 void add(const Edge k)547 {548 if(k.n>=int(container.size())) container.resize(k.n+1);549 }550 void erase(const Edge) { }551 552 void set(Edge n, T a) { container[n.n]=a; }553 //T get(Edge n) const { return container[n.n]; }554 typename std::vector<T>::reference555 operator[](Edge n) { return container[n.n]; }556 typename std::vector<T>::const_reference557 operator[](Edge n) const { return container[n.n]; }558 559 ///\warning There is no safety check at all!560 ///Using operator = between maps attached to different graph may561 ///cause serious problem.562 ///\todo Is this really so?563 ///\todo It can copy between different types.564 const EdgeMap<T>& operator=(const EdgeMap<T> &m)565 {566 container = m.container;567 return *this;568 }569 template<typename TT>570 const EdgeMap<T>& operator=(const EdgeMap<TT> &m)571 {572 std::copy(m.container.begin(), m.container.end(), container.begin());573 return *this;574 }575 576 void update() {} //Useless for DynMaps577 void update(T a) {} //Useless for DynMaps578 372 }; 579 373 … … 601 395 ///\todo this date structure need some reconsiderations. Maybe it 602 396 ///should be implemented independently from ListGraph. 603 604 class SymListGraph : public ListGraph605 {606 public:607 template<typename T> class SymEdgeMap;608 template<typename T> friend class SymEdgeMap;609 610 SymListGraph() : ListGraph() { }611 SymListGraph(const ListGraph &_g) : ListGraph(_g) { }612 ///Adds a pair of oppositely directed edges to the graph.613 Edge addEdge(Node u, Node v)614 {615 Edge e = ListGraph::addEdge(u,v);616 ListGraph::addEdge(v,u);617 return e;618 }619 620 void erase(Node n) { ListGraph::erase(n); }621 ///The oppositely directed edge.622 623 ///Returns the oppositely directed624 ///pair of the edge \c e.625 Edge opposite(Edge e) const626 {627 Edge f;628 f.idref() = e.idref() - 2*(e.idref()%2) + 1;629 return f;630 }631 632 ///Removes a pair of oppositely directed edges to the graph.633 void erase(Edge e) {634 ListGraph::erase(opposite(e));635 ListGraph::erase(e);636 }637 638 ///Common data storage for the edge pairs.639 640 ///This map makes it possible to store data shared by the oppositely641 ///directed pairs of edges.642 template <typename T> class SymEdgeMap : public DynMapBase<Edge>643 {644 std::vector<T> container;645 646 public:647 typedef T ValueType;648 typedef Edge KeyType;649 650 SymEdgeMap(const SymListGraph &_G) :651 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)652 {653 static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);654 }655 SymEdgeMap(const SymListGraph &_G,const T &t) :656 DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)657 {658 G->dyn_edge_maps.push_back(this);659 }660 661 SymEdgeMap(const SymEdgeMap<T> &m) :662 DynMapBase<SymEdge>(*m.G), container(m.container)663 {664 G->dyn_node_maps.push_back(this);665 }666 667 // template<typename TT> friend class SymEdgeMap;668 669 ///\todo It can copy between different types.670 ///671 672 template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :673 DynMapBase<SymEdge>(*m.G), container(m.container.size())674 {675 G->dyn_node_maps.push_back(this);676 typename std::vector<TT>::const_iterator i;677 for(typename std::vector<TT>::const_iterator i=m.container.begin();678 i!=m.container.end();679 i++)680 container.push_back(*i);681 }682 683 ~SymEdgeMap()684 {685 if(G) {686 std::vector<DynMapBase<Edge>* >::iterator i;687 for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin();688 i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end()689 && *i!=this; ++i) ;690 //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...691 //A better way to do that: (Is this really important?)692 if(*i==this) {693 *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();694 static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();695 }696 }697 }698 699 void add(const Edge k)700 {701 if(!k.idref()%2&&k.idref()/2>=int(container.size()))702 container.resize(k.idref()/2+1);703 }704 void erase(const Edge k) { }705 706 void set(Edge n, T a) { container[n.idref()/2]=a; }707 //T get(Edge n) const { return container[n.idref()/2]; }708 typename std::vector<T>::reference709 operator[](Edge n) { return container[n.idref()/2]; }710 typename std::vector<T>::const_reference711 operator[](Edge n) const { return container[n.idref()/2]; }712 713 ///\warning There is no safety check at all!714 ///Using operator = between maps attached to different graph may715 ///cause serious problem.716 ///\todo Is this really so?717 ///\todo It can copy between different types.718 const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)719 {720 container = m.container;721 return *this;722 }723 template<typename TT>724 const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)725 {726 std::copy(m.container.begin(), m.container.end(), container.begin());727 return *this;728 }729 730 void update() {} //Useless for DynMaps731 void update(T a) {} //Useless for DynMaps732 733 };734 397 735 398 }; -
src/work/deba/main.cpp
r674 r698 1 1 #include <iostream> 2 2 #include <cstdlib> 3 #include " test_graph.h"3 #include "list_graph.h" 4 4 5 5 using namespace std; -
src/work/deba/vector_map_factory.h
r627 r698 4 4 #include <vector> 5 5 6 #include "map_registry.h"7 8 6 namespace hugo { 9 7 10 8 template <typename MapRegistry> 11 class VectorMapFactory {12 public:9 class VectorMapFactory { 10 public: 13 11 14 12 typedef typename MapRegistry::Graph Graph; … … 17 15 18 16 typedef typename MapRegistry::MapBase MapBase; 17 19 18 20 19 template <typename V> … … 23 22 typedef V Value; 24 23 24 typedef std::vector<Value> Container; 25 25 Map() {} 26 26 … … 35 35 36 36 37 Value&operator[](const Key& key) {37 typename Container::reference operator[](const Key& key) { 38 38 int id = graph->id(key); 39 39 return container[id]; 40 40 } 41 41 42 const Value&operator[](const Key& key) const {42 typename Container::const_reference operator[](const Key& key) const { 43 43 int id = graph->id(key); 44 44 return container[id]; 45 45 } 46 46 47 const Value& get(const Key& key) const {48 int id = graph->id(key);49 return container[id];50 }51 52 47 void set(const Key& key, const Value& val) { 53 48 int id = graph->id(key); … … 64 59 void erase(const Key& key) {} 65 60 61 class const_iterator { 62 63 private: 64 65 }; 66 67 class iterator { 68 public: 69 iterator() {} 70 71 std::pair<const Key&, Value&> operator*() { 72 return std::pair<const Key&, Value&>(static_cast<Key&>(it), map[it]); 73 } 74 75 iterator& operator++() { ++it; return *this; } 76 iterator operator++(int) { iterator tmp(it); ++it; return tmp; } 77 private: 78 Map& map; 79 KeyIt it; 80 }; 81 66 82 private: 67 83 typedef std::vector<Value> Container; 68 84 69 85 Container container; 86 87 70 88 }; 89 90 91 71 92 72 93 };
Note: See TracChangeset
for help on using the changeset viewer.
