#include <boost/shared_ptr.hpp>
#include <boost/weak_ptr.hpp>
#include <boost/bind.hpp>
#include <map>
#include <vector>
#include <algorithm>
#include <iostream>

class enable_tracking;

typedef std::vector< boost::shared_ptr<enable_tracking> > ref_list_type;

class enable_tracking
{
protected:

    ~enable_tracking()
    {
    }

public:

    virtual void enumerate( ref_list_type & v, bool move ) = 0;
};

typedef std::map< boost::weak_ptr<enable_tracking>, int > map_type;

void build_dependency_graph( map_type & m, boost::weak_ptr<enable_tracking> pw )
{
    if( boost::shared_ptr<enable_tracking> px = pw.lock() )
    {
        if( ++m[ pw ] == 1 )
        {
            ref_list_type v;

            px->enumerate( v, false );

            std::for_each( v.begin(), v.end(), boost::bind( build_dependency_graph, boost::ref( m ), _1 ) );
        }
    }
}

void print_graph_node( map_type::value_type const & v )
{
    void * p = v.first.lock().get();

    std::cout << p << ": " << v.second << " ( " << v.first.use_count() << " )\n";
}

void count_to_reachability( map_type::value_type & v )
{
    v.second = v.second != v.first.use_count();
}

void propagate_reachability_3( map_type & m, bool & r, boost::shared_ptr<enable_tracking> const & px )
{
    if( px && m[ px ] == 0 )
    {
        m[ px ] = 1;
        r = true;
    }
}

void propagate_reachability_2( map_type & m, bool & r, map_type::value_type & v )
{
    if( v.second )
    {
        ref_list_type v2;

        v.first.lock()->enumerate( v2, false );

        std::for_each( v2.begin(), v2.end(), boost::bind( propagate_reachability_3, boost::ref( m ), boost::ref( r ), _1 ) );
    }
}

bool propagate_reachability( map_type & m )
{
    bool r = false;

    std::for_each( m.begin(), m.end(), boost::bind( propagate_reachability_2, boost::ref( m ), boost::ref( r ), _1 ) );

    return r;
}

void break_cycles_if_unreachable( map_type::value_type & v, ref_list_type & v2 )
{
    if( v.second == 0 )
    {
        v.first.lock()->enumerate( v2, true );
    }
}

template<class T> void reset_and_collect( boost::shared_ptr<T> & root )
{
    map_type m;

    build_dependency_graph( m, root );

    std::for_each( m.begin(), m.end(), print_graph_node );
    std::cout << "--\n";

    std::for_each( m.begin(), m.end(), count_to_reachability );

    std::for_each( m.begin(), m.end(), print_graph_node );
    std::cout << "--\n";

    while( propagate_reachability( m ) );

    std::for_each( m.begin(), m.end(), print_graph_node );
    std::cout << "--\n";

    ref_list_type tmp;
    std::for_each( m.begin(), m.end(), boost::bind( break_cycles_if_unreachable, _1, boost::ref( tmp ) ) );

    root.reset();
}

struct X: public enable_tracking
{
    X()
    {
        ++instances;
    }

    ~X()
    {
        --instances;
    }

    boost::shared_ptr<X> link1, link2;

    void enumerate( std::vector< boost::shared_ptr<enable_tracking> > & v, bool move )
    {
         v.push_back( link1 );
         v.push_back( link2 );

         if( move )
         {
             link1.reset();
             link2.reset();
         }
    }

    static int instances;
};

int X::instances;

int main()
{
    boost::shared_ptr<X> root( new X );

    root->link1.reset( new X );
    root->link2.reset( new X );

    root->link1->link1 = root->link2;
    root->link2->link1 = root->link1;

    boost::shared_ptr<X> root2( new X );

    root2->link1 = root->link1;

    std::cout << X::instances << std::endl;

    reset_and_collect( root );

    std::cout << X::instances << std::endl;

    reset_and_collect( root2 );

    std::cout << X::instances << std::endl;
}