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

class enable_sp_collect
{
protected:

    ~enable_sp_collect()
    {
    }

public:

    virtual void sp_enumerate( std::vector< boost::shared_ptr<enable_sp_collect> > & v ) = 0;
    virtual void sp_reset() = 0;
};

typedef std::map< boost::shared_ptr<enable_sp_collect>, int > map_type;

void build_dependency_graph( map_type & m, boost::shared_ptr<enable_sp_collect> const & px )
{
    if( px && ++m[ px ] == 1 )
    {
        std::vector< boost::shared_ptr<enable_sp_collect> > v;

        px->sp_enumerate( v );

        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 )
{
    std::cout << v.first << ": " << 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_sp_collect> 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 )
    {
        std::vector< boost::shared_ptr<enable_sp_collect> > v2;

        v.first->sp_enumerate( v2 );

        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 reset_if_unreachable( map_type::value_type & v )
{
    if( v.second == 0 )
    {
        v.first->sp_reset(); // locked
    }
}

static std::set< boost::weak_ptr<enable_sp_collect> > s_instances;

void sp_track( boost::shared_ptr<enable_sp_collect> const & px )
{
    s_instances.insert( px );
}

void sp_collect()
{
    map_type m;

    std::set< boost::weak_ptr<enable_sp_collect> > tmp( s_instances ); // locked

    for( std::set< boost::weak_ptr<enable_sp_collect> >::iterator i = tmp.begin(); i != tmp.end(); ++i )
    {
        if( boost::shared_ptr<enable_sp_collect> px = i->lock() )
        {
            build_dependency_graph( m, px );
        }
    }

    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";

    std::for_each( m.begin(), m.end(), reset_if_unreachable );
}

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

    ~X()
    {
        --instances;
    }

    boost::shared_ptr<X> link1, link2;

    void sp_enumerate( std::vector< boost::shared_ptr<enable_sp_collect> > & v )
    {
         v.push_back( link1 );
         v.push_back( link2 );
    }

    void sp_reset()
    {
        link1.reset();
        link2.reset();
    }

    static int instances;
};

int X::instances;

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

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

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

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

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

    root2->link1 = root->link1;

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

    sp_collect();

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

    root.reset();
    sp_collect();

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

    root2.reset();
    sp_collect();

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