include/Structs/Graphs/packedMemoryArrayImpl.h

#ifndef PACKEDMEMORYARRAYIMPL_H
#define PACKEDMEMORYARRAYIMPL_H

#include <Utilities/mersenneTwister.h>
#include <vector>

template<typename Vtype, typename Etype>
class PMANode;
template<typename Vtype, typename Etype>
class PMAEdge;
template<typename Vtype, typename Etype>
class PMAInEdge;
template<typename Vtype, typename Etype>
class PMANodeObserver;
template<typename Vtype, typename Etype>
class PMAEdgeObserver;
template<typename Vtype, typename Etype>
class PMAInEdgeObserver;

template<typename Vtype, typename Etype>
class PackedMemoryArrayImpl
{

    friend class PMANodeObserver< Vtype, Etype>;
    friend class PMAEdgeObserver< Vtype, Etype>;
    friend class PMAInEdgeObserver< Vtype, Etype>;

public:
    
    typedef unsigned int                                                        SizeType;
    typedef PMANode<Vtype,Etype>**                                              NodeDescriptor;
    typedef PMAEdge<Vtype,Etype>**                                              EdgeDescriptor;
    typedef typename PackedMemoryArray< PMANode< Vtype, Etype> >::Iterator      NodeIterator;
    typedef typename PackedMemoryArray< PMAEdge< Vtype, Etype> >::Iterator      EdgeIterator;
    typedef typename PackedMemoryArray< PMAInEdge< Vtype, Etype> >::Iterator  InEdgeIterator;
    

    PackedMemoryArrayImpl()
    {
        m_nodeObserver = new PMANodeObserver< Vtype, Etype>(this);
        m_nodes.registerObserver( m_nodeObserver);
        
        m_edgeObserver = new PMAEdgeObserver< Vtype, Etype>(this);
        m_edges.registerObserver( m_edgeObserver);       
   
        m_InEdgeObserver = new PMAInEdgeObserver< Vtype, Etype>(this);
        m_InEdges.registerObserver( m_InEdgeObserver);
    }

    ~PackedMemoryArrayImpl() 
    {
        delete m_nodeObserver;
        delete m_edgeObserver;
        delete m_InEdgeObserver;

        NodeIterator end = m_nodes.end();
        EdgeIterator end_edges = m_edges.end();

        for( NodeIterator u = m_nodes.begin(); u != end; ++u)
        {
            delete u->getDescriptor();
        }

        for( EdgeIterator e = m_edges.begin(); e != end_edges; ++e)
        {
            //std::cout << "Erasing " << e->getDescriptor() << std::endl;
            delete e->getDescriptor();
        }
    }

    NodeDescriptor insertNode() 
    { 
        NodeDescriptor m_auxNodeDescriptor = new PMANode<Vtype,Etype>*();
        *m_auxNodeDescriptor = 0;
        //std::cout << "\nMalloced for node" << m_auxNodeDescriptor << std::endl;
        PMANode<Vtype,Etype> newNode;
        newNode.setDescriptor( m_auxNodeDescriptor);
        NodeIterator m_auxNodeIterator = m_nodes.optimalInsert( newNode);
        //NodeIterator m_auxNodeIterator = m_nodes.insert( m_nodes.end(),newNode);

        
        //NodeIterator m_auxNodeIterator = m_nodes.insert( m_nodes.begin(),newNode);
        *m_auxNodeDescriptor = m_auxNodeIterator.getAddress();
        return m_auxNodeDescriptor;
    }
    
    EdgeDescriptor insertEdge( const NodeDescriptor& uD, const NodeDescriptor& vD) 
    { 
        /*std::ofstream out("/home/michai/Projects/pgl/ResultGenerators/converters/test.dot");
        printDot(out);
        out.close();*/
        assert( isValid());
        NodeIterator u = getNodeIterator( uD);
        NodeIterator v = getNodeIterator( vD);
        EdgeIterator e = endEdges(u);
        InEdgeIterator k = endInEdges(v);
        
        //std::cout << "Inserting edge " << u.getPoolIndex() << "->" << v.getPoolIndex() << std::endl;
        
        EdgeDescriptor m_auxEdgeDescriptor = new PMAEdge<Vtype,Etype>*();        
        *m_auxEdgeDescriptor = 0;

        PMAEdge<Vtype, Etype> newEdge( v.getAddress(), m_auxEdgeDescriptor);
        PMAInEdge<Vtype, Etype> newInEdge( u.getAddress());

        //std::cout << "\nMalloced for edge" << m_auxEdgeDescriptor << std::endl;
        //newEdge.setDescriptor( m_auxEdgeDescriptor);
        e = m_edges.insert( e, newEdge);
        k = m_InEdges.insert( k, newInEdge);        
        *m_auxEdgeDescriptor = e.getAddress();

        //e->m_adjacentNode = v.getPoolIndex();
        e->m_InEdge = k.getAddress();
        //e->setDescriptor(m_auxEdgeDescriptor);

        //k->m_adjacentNode = u.getPoolIndex();
        k->m_edge = e.getAddress();  
        //k->setDescriptor(m_auxEdgeDescriptor);

        assert( k->m_adjacentNode != 0);

        if( !u->hasEdges())
        {
            u->m_firstEdge = e.getAddress();
        } 
        
        if( !v->hasInEdges())
        {
            v->m_firstInEdge = k.getAddress();
        } 

        return m_auxEdgeDescriptor;
    }

    void eraseNode( const NodeIterator& u) 
    { 
        NodeDescriptor descriptor = u->getDescriptor();
        delete descriptor;
        descriptor = 0;
        u->setDescriptor(0);
        m_nodes.erase(u);
    }
    
    void eraseEdge( const InEdgeIterator& k)
    {
        eraseEdge( getEdgeIterator(k));
    }

    void eraseEdge( const EdgeIterator& e) 
    { 
        //EdgeIterator e = getEdgeIterator(descriptor);
        assert( e->isEdge());
        NodeIterator v = getNodeIterator(e->m_adjacentNode);
        EdgeIterator k = getInEdgeIterator(e->m_InEdge);
        NodeIterator u = getNodeIterator(k->m_adjacentNode);

        //std::cout << "Erasing descriptor of " << e->getId() << " and " << k->getId() << " at " << e->getDescriptor() << "/" << k->getDescriptor() << std::endl;
        
        EdgeDescriptor descriptor = e->getDescriptor();
        delete descriptor;
        descriptor = 0;
        //e->setDescriptor(0);
        //k->setDescriptor(0);

        EdgeIterator f,g;

        if( u->m_firstEdge == e.getPoolIndex() )
        {
            f = e;
                    ++f;
            f == endEdges(u) ? u->m_firstEdge = 0 : u->m_firstEdge = f.getPoolIndex();
        }

        if( v->m_firstInEdge == k.getPoolIndex() )
                {
                        g = k;
                    ++g;
                        g == endInEdges(v) ? v->m_firstInEdge = 0 : v->m_firstInEdge = g.getPoolIndex();
                }
    
        assert( getDescriptor(e) == getDescriptor(k));
        m_edges.erase( e);
        m_InEdges.erase( k);   
    }


    NodeIterator beginNodes()
    { 
        return  m_nodes.begin();
    }
    
    NodeIterator endNodes()
    { 
        return m_nodes.end();
    }
    
    EdgeIterator beginEdges()
    {
        return m_edges.begin();
    }
    
    EdgeIterator endEdges()
    {
        return m_edges.end();
    }

    NodeIterator findFirstNodeWithEdges( const NodeIterator& u)
    {
        NodeIterator m_auxNodeIterator = u;
        NodeIterator end = m_nodes.end();
        for( ; m_auxNodeIterator != end; ++m_auxNodeIterator)
        {
            if( m_auxNodeIterator->hasEdges())
            {
                //std::cout << "Found next edge at distance: " << m_auxNodeIterator - u << "***" << std::endl;
                return m_auxNodeIterator;
            }
        }
        return end;
    }

    NodeIterator findFirstNodeWithInEdges( const NodeIterator& u)
    {
        NodeIterator m_auxNodeIterator = u;
        NodeIterator end = m_nodes.end();
        for( ; m_auxNodeIterator != end; ++m_auxNodeIterator)
        {
            if( m_auxNodeIterator->hasInEdges())
            {
                //std::cout << "Found next back edge at distance: " << m_auxNodeIterator - u  << std::endl;
                return m_auxNodeIterator;
            }
        }
        return end;
    }

    EdgeIterator beginEdges( const NodeIterator& u)  
    { 
        if( u != m_nodes.end())
        {
            if( u->hasEdges())
            {
                return getEdgeIteratorAtAddress(u->m_firstEdge);
            }
            else
            {
                return beginEdges( findFirstNodeWithEdges(u));
            }
        }
        else
        {
            return m_edges.end();
        }

        /*NodeIterator m_auxNodeIterator = u;
        NodeIterator end = m_nodes.end();
        while( m_auxNodeIterator != end && (!m_auxNodeIterator->hasEdges()) )
                {
                        ++m_auxNodeIterator;
                }
                if( m_auxNodeIterator != end)
                {
            return getEdgeIterator(m_auxNodeIterator->m_firstEdge);
                }
        return m_edges.end();*/
    }
    
    EdgeIterator endEdges( const NodeIterator& u)  
    { 
        NodeIterator m_auxNodeIterator = u;
        ++m_auxNodeIterator;
        return beginEdges( m_auxNodeIterator);
    }
    
    InEdgeIterator beginInEdges( const NodeIterator& u)  
    { 
        if( u != m_nodes.end())
        {
            if( u->hasInEdges())
            {
                return getInEdgeIteratorAtAddress( u->m_firstInEdge);
            }
            else
            {
                return beginInEdges( findFirstNodeWithInEdges(u));
            }
        }
        else
        {
            return m_InEdges.end();
        }
        /*
        NodeIterator m_auxNodeIterator = u;
        NodeIterator end = m_nodes.end();
        while( m_auxNodeIterator != end && (!m_auxNodeIterator->hasInEdges()) )
                {
                        ++m_auxNodeIterator;
                }
                if( m_auxNodeIterator != end)
                {
            return getInEdgeIterator( m_auxNodeIterator->m_firstInEdge);
                }
        return m_InEdges.end();*/
    }
        
    InEdgeIterator endInEdges( const NodeIterator& u)  
    { 
        NodeIterator m_auxNodeIterator = u;
        ++m_auxNodeIterator;
        return beginInEdges( m_auxNodeIterator);
    }
    
        NodeIterator chooseNode()  
        { 
            double random = m_random.getRandomNormalizedDouble();
        SizeType pos = m_nodes.size() * random;
        
        NodeIterator m_auxNodeIterator = m_nodes.begin() + pos;
        return m_auxNodeIterator;
        }

    /*EdgeIterator getEdgeIterator( const EdgeDescriptor& descriptor) 
    { 
        return m_edges.atAddress(*descriptor);
    }*/
   
    NodeIterator getNodeIterator( const NodeDescriptor& descriptor) 
    { 
        return m_nodes.atAddress(*descriptor);
    }

    EdgeIterator getEdgeIteratorAtIndex( const SizeType& position)
    {
        return m_edges.atIndex(position);
    } 

    EdgeIterator getEdgeIteratorAtAddress( PMAEdge<Vtype,Etype>* addr)
    {
        return m_edges.atAddress(addr);
    } 

    InEdgeIterator getInEdgeIteratorAtIndex( const SizeType& position)
    {
        return m_InEdges.atIndex(position);
    } 

    InEdgeIterator getInEdgeIteratorAtAddress( PMAInEdge<Vtype,Etype>* addr)
    {
        return m_InEdges.atAddress(addr);
    }
   
    NodeIterator getNodeIterator( const SizeType& position) 
    { 
        return m_nodes.atIndex(position);
    }

    NodeIterator getNodeIterator( PMAEdge<Vtype,Etype>* addr) 
    { 
        return m_nodes.atAddress(addr);
    }

    NodeIterator getAdjacentNodeIterator( const EdgeIterator& e)
    { 
        return m_nodes.atAddress( e->m_adjacentNode);
    }

    NodeIterator getAdjacentNodeIterator( const InEdgeIterator& k)
    {
        return m_nodes.atAddress( k->m_adjacentNode);
    }

    InEdgeIterator getInEdgeIterator( const EdgeIterator& e)
    {
        return m_InEdges.atAddress( e->m_InEdge);
    }

    EdgeIterator getEdgeIterator( const InEdgeIterator& k)
    {
        return m_edges.atAddress(k->m_oppositeEdge);
    }

/*    const bool& isInEdge( const EdgeIterator& e) const
    {
        return e->m_isInEdge;
    }
*/
    bool hasEdges( const NodeIterator& u)
    {        
        return u->hasEdges();
    }

    bool hasInEdges( const NodeIterator& u)
    {
        return u->hasInEdges();
    }

    bool hasEdge( const EdgeDescriptor& descriptor)
    {
        return descriptor != 0;
    }
  
    bool hasNode( const NodeDescriptor& descriptor)
    {
        return descriptor != 0;
    }

    NodeIterator nilNode()
    {
        return m_nodes.end();
    }   
    
    EdgeIterator nilEdge() 
    { 
        return m_edges.end();
    }
    
    bool isValid()
    {
        PMAEdge<Vtype,Etype>* lastEdge = 0;
        PMAInEdge<Vtype,Etype>* lastInEdge = 0;

        NodeIterator u;
        NodeIterator end = endNodes();
        bool valid = true;
        for( u = beginNodes(); u != end; ++u)
        {
            if( u->hasEdges())
            {
                if( lastEdge > u->m_firstEdge)
                {
                    valid = false;
                }
                lastEdge = u->m_firstEdge;
            }
            if( u->hasInEdges())
            {
                if( lastInEdge > u->m_firstInEdge)
                {
                    valid = false;
                }
                lastInEdge = u->m_firstInEdge;
            }
        }        
        return valid;
    }


    SizeType memUsage()   
    { 
        std::cout << "Nodes:\t\t" << m_nodes.size() << "\t" << m_nodes.capacity() << "\n"; 
        std::cout << "Edges:\t\t" << m_edges.size() << "\t" << m_edges.capacity() << "\n"; 
        std::cout << "InEdges:\t" << m_InEdges.size() << "\t" << m_InEdges.capacity() << "\n"; 
        std::cout << "Node Size:\t" << PMANode<Vtype,Etype>::memUsage() << "bytes" << std::endl;
        std::cout << "Edge Size:\t" << PMAEdge<Vtype,Etype>::memUsage() << "bytes" << std::endl;
        std::cout << "BWEdge Size:\t" << PMAInEdge<Vtype,Etype>::memUsage() << "bytes" << std::endl;

        return  PMANode<Vtype,Etype>::memUsage() * m_nodes.capacity() + 
                PMAEdge<Vtype,Etype>::memUsage() * m_edges.capacity() + 
                PMAInEdge<Vtype,Etype>::memUsage() * m_InEdges.capacity();
    }

    SizeType getId( const NodeIterator& u) const
    {
        return u.getElementIndex();
    }

    NodeDescriptor getDescriptor( const NodeIterator& u) const
    {
        return u->getDescriptor();
    }

    EdgeDescriptor getDescriptor( const EdgeIterator& e) const
    {
        return e->getDescriptor();
    }

    void printDot(std::ostream& out)
    {
        out << "digraph BST {\n\tnode [fontname=\"Arial\"]\n";
        m_nodes.printDot( out, "n", "e");
        m_edges.printDot( out, "e", "b");
        m_InEdges.printDot( out,"b");
        out << "}";
    }

    void reserve( const SizeType& numNodes, const SizeType& numEdges)
    {
        m_nodes.reserve( numNodes);
        m_edges.reserve( numEdges);
        m_InEdges.reserve( numEdges);
    }

    void clear()
    {
        m_nodes.clear();
        m_edges.clear();
        m_InEdges.clear();
    }

private:
    PackedMemoryArray< PMANode< Vtype, Etype> >     m_nodes;
    PackedMemoryArray< PMAEdge< Vtype, Etype> >     m_edges; 
    PackedMemoryArray< PMAInEdge< Vtype, Etype> >   m_InEdges;
    PMANodeObserver< Vtype, Etype>*                 m_nodeObserver;
    PMAEdgeObserver< Vtype, Etype>*                 m_edgeObserver;
    PMAInEdgeObserver< Vtype, Etype>*               m_InEdgeObserver;

    MersenneTwister m_random;
};

template<typename Vtype, typename Etype>
class PMAEdge : public GraphElement< Etype, typename PackedMemoryArrayImpl<Vtype,Etype>::EdgeDescriptor>
{

public:
    typedef typename PackedMemoryArrayImpl<Vtype,Etype>::EdgeDescriptor   EdgeDescriptor;
    //typedef typename PackedMemoryArrayImpl<Vtype,Etype>::NodeDescriptor   NodeDescriptor;
    typedef typename PackedMemoryArrayImpl<Vtype,Etype>::SizeType         SizeType;
    
    PMAEdge( unsigned int init = 0): GraphElement< Etype, EdgeDescriptor>(),
                        m_adjacentNode(0), 
                        m_InEdge(0)
    {
    }
   
    PMAEdge( PMANode<Vtype,Etype>* adjacentNode , EdgeDescriptor descriptor):
            GraphElement< Etype, EdgeDescriptor>(descriptor),
                        m_adjacentNode(adjacentNode),
                        m_InEdge(0)
    {
    }

    static unsigned int memUsage() 
    {
        return sizeof(PMAEdge);
    }


    friend std::ostream& operator << ( std::ostream& out, PMAEdge other)
        {
        if( other.m_adjacentNode != 0)
        {
            out << "{" << other.m_adjacentNode << "|";
        }
        else
        {
            out << "{-|";
        }
        if( other.m_InEdge != 0)
        {   
            out << other.m_InEdge << "|";
        }
        else
        {
            out << "-|";
        }
        out << "}|" << other.m_descriptor;
        //out << "}";
                return out;
        }

    PMANode<Vtype,Etype>*       m_adjacentNode;
    PMAInEdge<Vtype,Etype>*   m_InEdge;   
};


template<typename Vtype, typename Etype>
class PMAInEdge : public Etype
{

public:
    typedef typename PackedMemoryArrayImpl<Vtype,Etype>::EdgeDescriptor   EdgeDescriptor;
    typedef typename PackedMemoryArrayImpl<Vtype,Etype>::NodeDescriptor   NodeDescriptor;
    typedef typename PackedMemoryArrayImpl<Vtype,Etype>::SizeType         SizeType;
   
    PMAInEdge( unsigned int init = 0): Etype(),
                        m_adjacentNode(0), 
                        m_edge(0)
    {
    }
   
    PMAInEdge( PMANode<Vtype,Etype>* adjacentNode):
            Etype(),
                        m_adjacentNode(adjacentNode),
                        m_edge(0)
    {
    }

    static unsigned int memUsage() 
    {
        return sizeof(PMAInEdge);
    }

    bool operator ==( const PMAInEdge& other) const
        {
        return ( m_edge == other.m_edge) && (m_adjacentNode == other.m_adjacentNode);
        }
        
        bool operator !=( const PMAInEdge& other) const
        {
                return (m_edge != other.m_edge) || (m_adjacentNode != other.m_adjacentNode);
        }

    friend std::ostream& operator << ( std::ostream& out, PMAInEdge other)
        {
        if( other.m_adjacentNode != 0)
        {
            out << "{" << other.m_adjacentNode << "|";
        }
        else
        {
            out << "{-|";
        }
        if( other.m_edge != 0)
        {   
            out << other.m_edge << "|";
        }
        else
        {
            out << "-|";
        }
        //out << "}|" << other.m_descriptor;
        //out << "}";
                return out;
        }

    PMANode<Vtype,Etype>*    m_adjacentNode;
    PMAEdge<Vtype,Etype>*    m_edge;   
};


template<typename Vtype, typename Etype>
class PMANode : public GraphElement< Vtype, typename PackedMemoryArrayImpl<Vtype,Etype>::NodeDescriptor>
{
public:
    typedef typename PackedMemoryArrayImpl<Vtype,Etype>::NodeDescriptor NodeDescriptor;
    typedef typename PackedMemoryArrayImpl<Vtype,Etype>::SizeType       SizeType;

    PMANode( unsigned int init = 0):GraphElement< Vtype, NodeDescriptor>(), 
                                    m_firstEdge(0), 
                                    m_firstInEdge(0)
    {
    }

    PMANode( NodeDescriptor descriptor):GraphElement< Vtype, NodeDescriptor>(descriptor), 
                                        m_firstEdge(0), 
                                        m_firstInEdge(0)
    {
    }
    
    bool hasEdges() const
    {
        return m_firstEdge != 0;
    }

    bool hasInEdges() const
    {
        return m_firstInEdge != 0;
    }

    static unsigned int memUsage() 
    {
        return sizeof(PMANode);
    }

    friend std::ostream& operator << ( std::ostream& out, PMANode other)
        {
        if( other.hasEdges())
        {
            out << "{" << other.m_firstEdge << "|";
        }
        else
        {
            out << "{-|";
        }
        if( other.hasInEdges())
        {   
            out << other.m_firstInEdge << "|";
        }
        else
        {
            out << "-|";
        }
        //out << "}";
        out << "}|" << other.m_descriptor;
                return out;
        }


    PMAEdge<Vtype,Etype>*       m_firstEdge;
    PMAInEdge<Vtype,Etype>*   m_firstInEdge;
};




template<typename Vtype, typename Etype>
class PMANodeObserver : public PackedMemoryArray< PMANode<Vtype,Etype> >::Observer
{
public:

    typedef typename PackedMemoryArrayImpl<Vtype,Etype>::EdgeIterator   EdgeIterator;
    typedef typename PackedMemoryArrayImpl<Vtype,Etype>::InEdgeIterator   InEdgeIterator;
    typedef typename PackedMemoryArrayImpl<Vtype,Etype>::NodeIterator   NodeIterator;
    typedef typename PackedMemoryArrayImpl<Vtype,Etype>::SizeType       SizeType;

    PMANodeObserver( PackedMemoryArrayImpl<Vtype,Etype>* G): m_G(G)
    {
    }

    void move( PMANode<Vtype,Etype>* source, PMANode<Vtype,Etype>* sourcePool, PMANode<Vtype,Etype>* destination, PMANode<Vtype,Etype>* destinationPool, const PMANode<Vtype,Etype>& node)
    {
        assert( node != m_G->m_nodes.getEmptyElement());
       
        /*if( node.m_firstEdge)
        {
            //get first edge
            e = m_G->m_edges.atAddress( node.m_firstEdge);
            //advance and update while the opposite points to this node
            while ( e != m_G->m_edges.end() && ( m_G->m_InEdges.atAddress(e->m_InEdge))->m_adjacentNode == source)
            {
                (m_G->m_InEdges.atAddress(e->m_InEdge))->m_adjacentNode = destination;
                ++e;
            }
        }
       
        // if the node has back edges
        if( node.m_firstInEdge)
        {
            //get first back edge
            back_e = m_G->m_InEdges.atAddress( node.m_firstInEdge);
            //advance and update while the opposite points to this node
            while ( back_e != m_G->m_InEdges.end() && ( m_G->m_edges.atAddress(back_e->m_edge))->m_adjacentNode == source)
            {
                (m_G->m_edges.atAddress(back_e->m_edge))->m_adjacentNode = destination;
                ++back_e;
            }
        }*/

        //std::cout << "Moving " << source << " to " << destination << std::endl;
                *(node.getDescriptor()) = destination;        
    }
private:
    PackedMemoryArrayImpl<Vtype,Etype>* m_G;
    EdgeIterator                        e, end;
    InEdgeIterator                    back_e, back_end;
};


template<typename Vtype, typename Etype>
class PMAEdgeObserver : public PackedMemoryArray< PMAEdge<Vtype,Etype> >::Observer
{
public:
    typedef typename PackedMemoryArrayImpl<Vtype,Etype>::SizeType       SizeType;
    typedef typename PackedMemoryArrayImpl<Vtype,Etype>::NodeIterator   NodeIterator;
    typedef typename PackedMemoryArrayImpl<Vtype,Etype>::InEdgeIterator   InEdgeIterator;

    PMAEdgeObserver( PackedMemoryArrayImpl<Vtype,Etype>* G): m_G(G)
    {
    }

    void move( PMAEdge<Vtype,Etype>* source, PMAEdge<Vtype,Etype>* sourcePool, PMAEdge<Vtype,Etype>* destination, PMAEdge<Vtype,Etype>* destinationPool, const PMAEdge<Vtype,Etype>& edge)
    {
        if( source == destination) return;
        assert( edge != m_G->m_edges.getEmptyElement());

        *(edge.getDescriptor()) = destination;
        edge.m_InEdge->m_edge = destination;

        if( (edge.m_InEdge->m_adjacentNode->m_firstEdge == source) 

            && (edge.m_InEdge->m_adjacentNode != lastChangedNode))
        {
            edge.m_InEdge->m_adjacentNode->m_firstEdge = destination;
            lastChangedNode = edge.m_InEdge->m_adjacentNode;
        }
    }

    void reset()
    {
        lastChangedNode = 0;
    }
private:
    PackedMemoryArrayImpl<Vtype,Etype>* m_G;
    PMANode<Vtype,Etype>*   lastChangedNode;
};


template<typename Vtype, typename Etype>
class PMAInEdgeObserver : public PackedMemoryArray< PMAInEdge<Vtype,Etype> >::Observer
{
public:
    typedef typename PackedMemoryArrayImpl<Vtype,Etype>::SizeType       SizeType;
    typedef typename PackedMemoryArrayImpl<Vtype,Etype>::NodeIterator   NodeIterator;
    typedef typename PackedMemoryArrayImpl<Vtype,Etype>::EdgeIterator   EdgeIterator;

    PMAInEdgeObserver( PackedMemoryArrayImpl<Vtype,Etype>* G): m_G(G)
    {
    }

    void move( PMAInEdge<Vtype,Etype>* source, PMAInEdge<Vtype,Etype>* sourcePool, PMAInEdge<Vtype,Etype>* destination, PMAInEdge<Vtype,Etype>* destinationPool, const PMAInEdge<Vtype,Etype>& InEdge)
    {
        if( source == destination) return;

        assert( InEdge != m_G->m_InEdges.getEmptyElement());

        InEdge.m_edge->m_InEdge = destination;

        if( (InEdge.m_edge->m_adjacentNode->m_firstInEdge == source) 

            && (InEdge.m_edge->m_adjacentNode != lastChangedNode))
        {
            InEdge.m_edge->m_adjacentNode->m_firstInEdge = destination;
            lastChangedNode = InEdge.m_edge->m_adjacentNode;
        }
    }

    void reset()
    {
        lastChangedNode = 0;
    }
private:
    PackedMemoryArrayImpl<Vtype,Etype>* m_G;
    PMANode<Vtype,Etype>*  lastChangedNode;
};


#endif //PACKEDMEMORYARRAYIMPL_H

---