00001 #ifndef PACKEDMEMORYARRAYIMPL_H
00002 #define PACKEDMEMORYARRAYIMPL_H
00003
00004 #include <Utilities/mersenneTwister.h>
00005 #include <vector>
00006
00007 template<typename Vtype, typename Etype>
00008 class PMANode;
00009 template<typename Vtype, typename Etype>
00010 class PMAEdge;
00011 template<typename Vtype, typename Etype>
00012 class PMAInEdge;
00013 template<typename Vtype, typename Etype>
00014 class PMANodeObserver;
00015 template<typename Vtype, typename Etype>
00016 class PMAEdgeObserver;
00017 template<typename Vtype, typename Etype>
00018 class PMAInEdgeObserver;
00019
00020 template<typename Vtype, typename Etype>
00021 class PackedMemoryArrayImpl
00022 {
00023
00024 friend class PMANodeObserver< Vtype, Etype>;
00025 friend class PMAEdgeObserver< Vtype, Etype>;
00026 friend class PMAInEdgeObserver< Vtype, Etype>;
00027
00028 public:
00029
00030 typedef unsigned int SizeType;
00031 typedef PMANode<Vtype,Etype>** NodeDescriptor;
00032 typedef PMAEdge<Vtype,Etype>** EdgeDescriptor;
00033 typedef typename PackedMemoryArray< PMANode< Vtype, Etype> >::Iterator NodeIterator;
00034 typedef typename PackedMemoryArray< PMAEdge< Vtype, Etype> >::Iterator EdgeIterator;
00035 typedef typename PackedMemoryArray< PMAInEdge< Vtype, Etype> >::Iterator InEdgeIterator;
00036
00037
00038 PackedMemoryArrayImpl()
00039 {
00040 m_nodeObserver = new PMANodeObserver< Vtype, Etype>(this);
00041 m_nodes.registerObserver( m_nodeObserver);
00042
00043 m_edgeObserver = new PMAEdgeObserver< Vtype, Etype>(this);
00044 m_edges.registerObserver( m_edgeObserver);
00045
00046 m_InEdgeObserver = new PMAInEdgeObserver< Vtype, Etype>(this);
00047 m_InEdges.registerObserver( m_InEdgeObserver);
00048 }
00049
00050 ~PackedMemoryArrayImpl()
00051 {
00052 delete m_nodeObserver;
00053 delete m_edgeObserver;
00054 delete m_InEdgeObserver;
00055
00056 NodeIterator end = m_nodes.end();
00057 EdgeIterator end_edges = m_edges.end();
00058
00059 for( NodeIterator u = m_nodes.begin(); u != end; ++u)
00060 {
00061 delete u->getDescriptor();
00062 }
00063
00064 for( EdgeIterator e = m_edges.begin(); e != end_edges; ++e)
00065 {
00066
00067 delete e->getDescriptor();
00068 }
00069 }
00070
00071 NodeDescriptor insertNode()
00072 {
00073 NodeDescriptor m_auxNodeDescriptor = new PMANode<Vtype,Etype>*();
00074 *m_auxNodeDescriptor = 0;
00075
00076 PMANode<Vtype,Etype> newNode;
00077 newNode.setDescriptor( m_auxNodeDescriptor);
00078 NodeIterator m_auxNodeIterator = m_nodes.optimalInsert( newNode);
00079
00080
00081
00082
00083 *m_auxNodeDescriptor = m_auxNodeIterator.getAddress();
00084 return m_auxNodeDescriptor;
00085 }
00086
00087 EdgeDescriptor insertEdge( const NodeDescriptor& uD, const NodeDescriptor& vD)
00088 {
00089
00090
00091
00092 assert( isValid());
00093 NodeIterator u = getNodeIterator( uD);
00094 NodeIterator v = getNodeIterator( vD);
00095 EdgeIterator e = endEdges(u);
00096 InEdgeIterator k = endInEdges(v);
00097
00098
00099
00100 EdgeDescriptor m_auxEdgeDescriptor = new PMAEdge<Vtype,Etype>*();
00101 *m_auxEdgeDescriptor = 0;
00102
00103 PMAEdge<Vtype, Etype> newEdge( v.getAddress(), m_auxEdgeDescriptor);
00104 PMAInEdge<Vtype, Etype> newInEdge( u.getAddress());
00105
00106
00107
00108 e = m_edges.insert( e, newEdge);
00109 k = m_InEdges.insert( k, newInEdge);
00110 *m_auxEdgeDescriptor = e.getAddress();
00111
00112
00113 e->m_InEdge = k.getAddress();
00114
00115
00116
00117 k->m_edge = e.getAddress();
00118
00119
00120 assert( k->m_adjacentNode != 0);
00121
00122 if( !u->hasEdges())
00123 {
00124 u->m_firstEdge = e.getAddress();
00125 }
00126
00127 if( !v->hasInEdges())
00128 {
00129 v->m_firstInEdge = k.getAddress();
00130 }
00131
00132 return m_auxEdgeDescriptor;
00133 }
00134
00135 void eraseNode( const NodeIterator& u)
00136 {
00137 NodeDescriptor descriptor = u->getDescriptor();
00138 delete descriptor;
00139 descriptor = 0;
00140 u->setDescriptor(0);
00141 m_nodes.erase(u);
00142 }
00143
00144 void eraseEdge( const InEdgeIterator& k)
00145 {
00146 eraseEdge( getEdgeIterator(k));
00147 }
00148
00149 void eraseEdge( const EdgeIterator& e)
00150 {
00151
00152 assert( e->isEdge());
00153 NodeIterator v = getNodeIterator(e->m_adjacentNode);
00154 EdgeIterator k = getInEdgeIterator(e->m_InEdge);
00155 NodeIterator u = getNodeIterator(k->m_adjacentNode);
00156
00157
00158
00159 EdgeDescriptor descriptor = e->getDescriptor();
00160 delete descriptor;
00161 descriptor = 0;
00162
00163
00164
00165 EdgeIterator f,g;
00166
00167 if( u->m_firstEdge == e.getPoolIndex() )
00168 {
00169 f = e;
00170 ++f;
00171 f == endEdges(u) ? u->m_firstEdge = 0 : u->m_firstEdge = f.getPoolIndex();
00172 }
00173
00174 if( v->m_firstInEdge == k.getPoolIndex() )
00175 {
00176 g = k;
00177 ++g;
00178 g == endInEdges(v) ? v->m_firstInEdge = 0 : v->m_firstInEdge = g.getPoolIndex();
00179 }
00180
00181 assert( getDescriptor(e) == getDescriptor(k));
00182 m_edges.erase( e);
00183 m_InEdges.erase( k);
00184 }
00185
00186
00187 NodeIterator beginNodes()
00188 {
00189 return m_nodes.begin();
00190 }
00191
00192 NodeIterator endNodes()
00193 {
00194 return m_nodes.end();
00195 }
00196
00197 EdgeIterator beginEdges()
00198 {
00199 return m_edges.begin();
00200 }
00201
00202 EdgeIterator endEdges()
00203 {
00204 return m_edges.end();
00205 }
00206
00207 NodeIterator findFirstNodeWithEdges( const NodeIterator& u)
00208 {
00209 NodeIterator m_auxNodeIterator = u;
00210 NodeIterator end = m_nodes.end();
00211 for( ; m_auxNodeIterator != end; ++m_auxNodeIterator)
00212 {
00213 if( m_auxNodeIterator->hasEdges())
00214 {
00215
00216 return m_auxNodeIterator;
00217 }
00218 }
00219 return end;
00220 }
00221
00222 NodeIterator findFirstNodeWithInEdges( const NodeIterator& u)
00223 {
00224 NodeIterator m_auxNodeIterator = u;
00225 NodeIterator end = m_nodes.end();
00226 for( ; m_auxNodeIterator != end; ++m_auxNodeIterator)
00227 {
00228 if( m_auxNodeIterator->hasInEdges())
00229 {
00230
00231 return m_auxNodeIterator;
00232 }
00233 }
00234 return end;
00235 }
00236
00237 EdgeIterator beginEdges( const NodeIterator& u)
00238 {
00239 if( u != m_nodes.end())
00240 {
00241 if( u->hasEdges())
00242 {
00243 return getEdgeIteratorAtAddress(u->m_firstEdge);
00244 }
00245 else
00246 {
00247 return beginEdges( findFirstNodeWithEdges(u));
00248 }
00249 }
00250 else
00251 {
00252 return m_edges.end();
00253 }
00254
00255
00256
00257
00258
00259
00260
00261
00262
00263
00264
00265
00266 }
00267
00268 EdgeIterator endEdges( const NodeIterator& u)
00269 {
00270 NodeIterator m_auxNodeIterator = u;
00271 ++m_auxNodeIterator;
00272 return beginEdges( m_auxNodeIterator);
00273 }
00274
00275 InEdgeIterator beginInEdges( const NodeIterator& u)
00276 {
00277 if( u != m_nodes.end())
00278 {
00279 if( u->hasInEdges())
00280 {
00281 return getInEdgeIteratorAtAddress( u->m_firstInEdge);
00282 }
00283 else
00284 {
00285 return beginInEdges( findFirstNodeWithInEdges(u));
00286 }
00287 }
00288 else
00289 {
00290 return m_InEdges.end();
00291 }
00292
00293
00294
00295
00296
00297
00298
00299
00300
00301
00302
00303
00304 }
00305
00306 InEdgeIterator endInEdges( const NodeIterator& u)
00307 {
00308 NodeIterator m_auxNodeIterator = u;
00309 ++m_auxNodeIterator;
00310 return beginInEdges( m_auxNodeIterator);
00311 }
00312
00313 NodeIterator chooseNode()
00314 {
00315 double random = m_random.getRandomNormalizedDouble();
00316 SizeType pos = m_nodes.size() * random;
00317
00318 NodeIterator m_auxNodeIterator = m_nodes.begin() + pos;
00319 return m_auxNodeIterator;
00320 }
00321
00322
00323
00324
00325
00326
00327 NodeIterator getNodeIterator( const NodeDescriptor& descriptor)
00328 {
00329 return m_nodes.atAddress(*descriptor);
00330 }
00331
00332 EdgeIterator getEdgeIteratorAtIndex( const SizeType& position)
00333 {
00334 return m_edges.atIndex(position);
00335 }
00336
00337 EdgeIterator getEdgeIteratorAtAddress( PMAEdge<Vtype,Etype>* addr)
00338 {
00339 return m_edges.atAddress(addr);
00340 }
00341
00342 InEdgeIterator getInEdgeIteratorAtIndex( const SizeType& position)
00343 {
00344 return m_InEdges.atIndex(position);
00345 }
00346
00347 InEdgeIterator getInEdgeIteratorAtAddress( PMAInEdge<Vtype,Etype>* addr)
00348 {
00349 return m_InEdges.atAddress(addr);
00350 }
00351
00352 NodeIterator getNodeIterator( const SizeType& position)
00353 {
00354 return m_nodes.atIndex(position);
00355 }
00356
00357 NodeIterator getNodeIterator( PMAEdge<Vtype,Etype>* addr)
00358 {
00359 return m_nodes.atAddress(addr);
00360 }
00361
00362 NodeIterator getAdjacentNodeIterator( const EdgeIterator& e)
00363 {
00364 return m_nodes.atAddress( e->m_adjacentNode);
00365 }
00366
00367 NodeIterator getAdjacentNodeIterator( const InEdgeIterator& k)
00368 {
00369 return m_nodes.atAddress( k->m_adjacentNode);
00370 }
00371
00372 InEdgeIterator getInEdgeIterator( const EdgeIterator& e)
00373 {
00374 return m_InEdges.atAddress( e->m_InEdge);
00375 }
00376
00377 EdgeIterator getEdgeIterator( const InEdgeIterator& k)
00378 {
00379 return m_edges.atAddress(k->m_oppositeEdge);
00380 }
00381
00382
00383
00384
00385
00386
00387 bool hasEdges( const NodeIterator& u)
00388 {
00389 return u->hasEdges();
00390 }
00391
00392 bool hasInEdges( const NodeIterator& u)
00393 {
00394 return u->hasInEdges();
00395 }
00396
00397 bool hasEdge( const EdgeDescriptor& descriptor)
00398 {
00399 return descriptor != 0;
00400 }
00401
00402 bool hasNode( const NodeDescriptor& descriptor)
00403 {
00404 return descriptor != 0;
00405 }
00406
00407 NodeIterator nilNode()
00408 {
00409 return m_nodes.end();
00410 }
00411
00412 EdgeIterator nilEdge()
00413 {
00414 return m_edges.end();
00415 }
00416
00417 bool isValid()
00418 {
00419 PMAEdge<Vtype,Etype>* lastEdge = 0;
00420 PMAInEdge<Vtype,Etype>* lastInEdge = 0;
00421
00422 NodeIterator u;
00423 NodeIterator end = endNodes();
00424 bool valid = true;
00425 for( u = beginNodes(); u != end; ++u)
00426 {
00427 if( u->hasEdges())
00428 {
00429 if( lastEdge > u->m_firstEdge)
00430 {
00431 valid = false;
00432 }
00433 lastEdge = u->m_firstEdge;
00434 }
00435 if( u->hasInEdges())
00436 {
00437 if( lastInEdge > u->m_firstInEdge)
00438 {
00439 valid = false;
00440 }
00441 lastInEdge = u->m_firstInEdge;
00442 }
00443 }
00444 return valid;
00445 }
00446
00447
00448 SizeType memUsage()
00449 {
00450 std::cout << "Nodes:\t\t" << m_nodes.size() << "\t" << m_nodes.capacity() << "\n";
00451 std::cout << "Edges:\t\t" << m_edges.size() << "\t" << m_edges.capacity() << "\n";
00452 std::cout << "InEdges:\t" << m_InEdges.size() << "\t" << m_InEdges.capacity() << "\n";
00453 std::cout << "Node Size:\t" << PMANode<Vtype,Etype>::memUsage() << "bytes" << std::endl;
00454 std::cout << "Edge Size:\t" << PMAEdge<Vtype,Etype>::memUsage() << "bytes" << std::endl;
00455 std::cout << "BWEdge Size:\t" << PMAInEdge<Vtype,Etype>::memUsage() << "bytes" << std::endl;
00456
00457 return PMANode<Vtype,Etype>::memUsage() * m_nodes.capacity() +
00458 PMAEdge<Vtype,Etype>::memUsage() * m_edges.capacity() +
00459 PMAInEdge<Vtype,Etype>::memUsage() * m_InEdges.capacity();
00460 }
00461
00462 SizeType getId( const NodeIterator& u) const
00463 {
00464 return u.getElementIndex();
00465 }
00466
00467 NodeDescriptor getDescriptor( const NodeIterator& u) const
00468 {
00469 return u->getDescriptor();
00470 }
00471
00472 EdgeDescriptor getDescriptor( const EdgeIterator& e) const
00473 {
00474 return e->getDescriptor();
00475 }
00476
00477 void printDot(std::ostream& out)
00478 {
00479 out << "digraph BST {\n\tnode [fontname=\"Arial\"]\n";
00480 m_nodes.printDot( out, "n", "e");
00481 m_edges.printDot( out, "e", "b");
00482 m_InEdges.printDot( out,"b");
00483 out << "}";
00484 }
00485
00486 void reserve( const SizeType& numNodes, const SizeType& numEdges)
00487 {
00488 m_nodes.reserve( numNodes);
00489 m_edges.reserve( numEdges);
00490 m_InEdges.reserve( numEdges);
00491 }
00492
00493 void clear()
00494 {
00495 m_nodes.clear();
00496 m_edges.clear();
00497 m_InEdges.clear();
00498 }
00499
00500 private:
00501 PackedMemoryArray< PMANode< Vtype, Etype> > m_nodes;
00502 PackedMemoryArray< PMAEdge< Vtype, Etype> > m_edges;
00503 PackedMemoryArray< PMAInEdge< Vtype, Etype> > m_InEdges;
00504 PMANodeObserver< Vtype, Etype>* m_nodeObserver;
00505 PMAEdgeObserver< Vtype, Etype>* m_edgeObserver;
00506 PMAInEdgeObserver< Vtype, Etype>* m_InEdgeObserver;
00507
00508 MersenneTwister m_random;
00509 };
00510
00511 template<typename Vtype, typename Etype>
00512 class PMAEdge : public GraphElement< Etype, typename PackedMemoryArrayImpl<Vtype,Etype>::EdgeDescriptor>
00513 {
00514
00515 public:
00516 typedef typename PackedMemoryArrayImpl<Vtype,Etype>::EdgeDescriptor EdgeDescriptor;
00517
00518 typedef typename PackedMemoryArrayImpl<Vtype,Etype>::SizeType SizeType;
00519
00520 PMAEdge( unsigned int init = 0): GraphElement< Etype, EdgeDescriptor>(),
00521 m_adjacentNode(0),
00522 m_InEdge(0)
00523 {
00524 }
00525
00526 PMAEdge( PMANode<Vtype,Etype>* adjacentNode , EdgeDescriptor descriptor):
00527 GraphElement< Etype, EdgeDescriptor>(descriptor),
00528 m_adjacentNode(adjacentNode),
00529 m_InEdge(0)
00530 {
00531 }
00532
00533 static unsigned int memUsage()
00534 {
00535 return sizeof(PMAEdge);
00536 }
00537
00538
00539 friend std::ostream& operator << ( std::ostream& out, PMAEdge other)
00540 {
00541 if( other.m_adjacentNode != 0)
00542 {
00543 out << "{" << other.m_adjacentNode << "|";
00544 }
00545 else
00546 {
00547 out << "{-|";
00548 }
00549 if( other.m_InEdge != 0)
00550 {
00551 out << other.m_InEdge << "|";
00552 }
00553 else
00554 {
00555 out << "-|";
00556 }
00557 out << "}|" << other.m_descriptor;
00558
00559 return out;
00560 }
00561
00562 PMANode<Vtype,Etype>* m_adjacentNode;
00563 PMAInEdge<Vtype,Etype>* m_InEdge;
00564 };
00565
00566
00567 template<typename Vtype, typename Etype>
00568 class PMAInEdge : public Etype
00569 {
00570
00571 public:
00572 typedef typename PackedMemoryArrayImpl<Vtype,Etype>::EdgeDescriptor EdgeDescriptor;
00573 typedef typename PackedMemoryArrayImpl<Vtype,Etype>::NodeDescriptor NodeDescriptor;
00574 typedef typename PackedMemoryArrayImpl<Vtype,Etype>::SizeType SizeType;
00575
00576 PMAInEdge( unsigned int init = 0): Etype(),
00577 m_adjacentNode(0),
00578 m_edge(0)
00579 {
00580 }
00581
00582 PMAInEdge( PMANode<Vtype,Etype>* adjacentNode):
00583 Etype(),
00584 m_adjacentNode(adjacentNode),
00585 m_edge(0)
00586 {
00587 }
00588
00589 static unsigned int memUsage()
00590 {
00591 return sizeof(PMAInEdge);
00592 }
00593
00594 bool operator ==( const PMAInEdge& other) const
00595 {
00596 return ( m_edge == other.m_edge) && (m_adjacentNode == other.m_adjacentNode);
00597 }
00598
00599 bool operator !=( const PMAInEdge& other) const
00600 {
00601 return (m_edge != other.m_edge) || (m_adjacentNode != other.m_adjacentNode);
00602 }
00603
00604 friend std::ostream& operator << ( std::ostream& out, PMAInEdge other)
00605 {
00606 if( other.m_adjacentNode != 0)
00607 {
00608 out << "{" << other.m_adjacentNode << "|";
00609 }
00610 else
00611 {
00612 out << "{-|";
00613 }
00614 if( other.m_edge != 0)
00615 {
00616 out << other.m_edge << "|";
00617 }
00618 else
00619 {
00620 out << "-|";
00621 }
00622
00623
00624 return out;
00625 }
00626
00627 PMANode<Vtype,Etype>* m_adjacentNode;
00628 PMAEdge<Vtype,Etype>* m_edge;
00629 };
00630
00631
00632 template<typename Vtype, typename Etype>
00633 class PMANode : public GraphElement< Vtype, typename PackedMemoryArrayImpl<Vtype,Etype>::NodeDescriptor>
00634 {
00635 public:
00636 typedef typename PackedMemoryArrayImpl<Vtype,Etype>::NodeDescriptor NodeDescriptor;
00637 typedef typename PackedMemoryArrayImpl<Vtype,Etype>::SizeType SizeType;
00638
00639 PMANode( unsigned int init = 0):GraphElement< Vtype, NodeDescriptor>(),
00640 m_firstEdge(0),
00641 m_firstInEdge(0)
00642 {
00643 }
00644
00645 PMANode( NodeDescriptor descriptor):GraphElement< Vtype, NodeDescriptor>(descriptor),
00646 m_firstEdge(0),
00647 m_firstInEdge(0)
00648 {
00649 }
00650
00651 bool hasEdges() const
00652 {
00653 return m_firstEdge != 0;
00654 }
00655
00656 bool hasInEdges() const
00657 {
00658 return m_firstInEdge != 0;
00659 }
00660
00661 static unsigned int memUsage()
00662 {
00663 return sizeof(PMANode);
00664 }
00665
00666 friend std::ostream& operator << ( std::ostream& out, PMANode other)
00667 {
00668 if( other.hasEdges())
00669 {
00670 out << "{" << other.m_firstEdge << "|";
00671 }
00672 else
00673 {
00674 out << "{-|";
00675 }
00676 if( other.hasInEdges())
00677 {
00678 out << other.m_firstInEdge << "|";
00679 }
00680 else
00681 {
00682 out << "-|";
00683 }
00684
00685 out << "}|" << other.m_descriptor;
00686 return out;
00687 }
00688
00689
00690 PMAEdge<Vtype,Etype>* m_firstEdge;
00691 PMAInEdge<Vtype,Etype>* m_firstInEdge;
00692 };
00693
00694
00695
00696
00697 template<typename Vtype, typename Etype>
00698 class PMANodeObserver : public PackedMemoryArray< PMANode<Vtype,Etype> >::Observer
00699 {
00700 public:
00701
00702 typedef typename PackedMemoryArrayImpl<Vtype,Etype>::EdgeIterator EdgeIterator;
00703 typedef typename PackedMemoryArrayImpl<Vtype,Etype>::InEdgeIterator InEdgeIterator;
00704 typedef typename PackedMemoryArrayImpl<Vtype,Etype>::NodeIterator NodeIterator;
00705 typedef typename PackedMemoryArrayImpl<Vtype,Etype>::SizeType SizeType;
00706
00707 PMANodeObserver( PackedMemoryArrayImpl<Vtype,Etype>* G): m_G(G)
00708 {
00709 }
00710
00711 void move( PMANode<Vtype,Etype>* source, PMANode<Vtype,Etype>* sourcePool, PMANode<Vtype,Etype>* destination, PMANode<Vtype,Etype>* destinationPool, const PMANode<Vtype,Etype>& node)
00712 {
00713 assert( node != m_G->m_nodes.getEmptyElement());
00714
00715
00716
00717
00718
00719
00720
00721
00722
00723
00724
00725
00726
00727
00728
00729
00730
00731
00732
00733
00734
00735
00736
00737
00738
00739
00740
00741 *(node.getDescriptor()) = destination;
00742 }
00743 private:
00744 PackedMemoryArrayImpl<Vtype,Etype>* m_G;
00745 EdgeIterator e, end;
00746 InEdgeIterator back_e, back_end;
00747 };
00748
00749
00750 template<typename Vtype, typename Etype>
00751 class PMAEdgeObserver : public PackedMemoryArray< PMAEdge<Vtype,Etype> >::Observer
00752 {
00753 public:
00754 typedef typename PackedMemoryArrayImpl<Vtype,Etype>::SizeType SizeType;
00755 typedef typename PackedMemoryArrayImpl<Vtype,Etype>::NodeIterator NodeIterator;
00756 typedef typename PackedMemoryArrayImpl<Vtype,Etype>::InEdgeIterator InEdgeIterator;
00757
00758 PMAEdgeObserver( PackedMemoryArrayImpl<Vtype,Etype>* G): m_G(G)
00759 {
00760 }
00761
00762 void move( PMAEdge<Vtype,Etype>* source, PMAEdge<Vtype,Etype>* sourcePool, PMAEdge<Vtype,Etype>* destination, PMAEdge<Vtype,Etype>* destinationPool, const PMAEdge<Vtype,Etype>& edge)
00763 {
00764 if( source == destination) return;
00765 assert( edge != m_G->m_edges.getEmptyElement());
00766
00767 *(edge.getDescriptor()) = destination;
00768 edge.m_InEdge->m_edge = destination;
00769
00770 if( (edge.m_InEdge->m_adjacentNode->m_firstEdge == source)
00771
00772 && (edge.m_InEdge->m_adjacentNode != lastChangedNode))
00773 {
00774 edge.m_InEdge->m_adjacentNode->m_firstEdge = destination;
00775 lastChangedNode = edge.m_InEdge->m_adjacentNode;
00776 }
00777 }
00778
00779 void reset()
00780 {
00781 lastChangedNode = 0;
00782 }
00783 private:
00784 PackedMemoryArrayImpl<Vtype,Etype>* m_G;
00785 PMANode<Vtype,Etype>* lastChangedNode;
00786 };
00787
00788
00789 template<typename Vtype, typename Etype>
00790 class PMAInEdgeObserver : public PackedMemoryArray< PMAInEdge<Vtype,Etype> >::Observer
00791 {
00792 public:
00793 typedef typename PackedMemoryArrayImpl<Vtype,Etype>::SizeType SizeType;
00794 typedef typename PackedMemoryArrayImpl<Vtype,Etype>::NodeIterator NodeIterator;
00795 typedef typename PackedMemoryArrayImpl<Vtype,Etype>::EdgeIterator EdgeIterator;
00796
00797 PMAInEdgeObserver( PackedMemoryArrayImpl<Vtype,Etype>* G): m_G(G)
00798 {
00799 }
00800
00801 void move( PMAInEdge<Vtype,Etype>* source, PMAInEdge<Vtype,Etype>* sourcePool, PMAInEdge<Vtype,Etype>* destination, PMAInEdge<Vtype,Etype>* destinationPool, const PMAInEdge<Vtype,Etype>& InEdge)
00802 {
00803 if( source == destination) return;
00804
00805 assert( InEdge != m_G->m_InEdges.getEmptyElement());
00806
00807 InEdge.m_edge->m_InEdge = destination;
00808
00809 if( (InEdge.m_edge->m_adjacentNode->m_firstInEdge == source)
00810
00811 && (InEdge.m_edge->m_adjacentNode != lastChangedNode))
00812 {
00813 InEdge.m_edge->m_adjacentNode->m_firstInEdge = destination;
00814 lastChangedNode = InEdge.m_edge->m_adjacentNode;
00815 }
00816 }
00817
00818 void reset()
00819 {
00820 lastChangedNode = 0;
00821 }
00822 private:
00823 PackedMemoryArrayImpl<Vtype,Etype>* m_G;
00824 PMANode<Vtype,Etype>* lastChangedNode;
00825 };
00826
00827
00828 #endif //PACKEDMEMORYARRAYIMPL_H