// @topic T03020 Lists
// @brief circularly linked list

// circularly_linked_list.cpp
#include <cassert>
#include <iostream>
using namespace std;

class Node
{
    friend void print_list( Node const& head, int line );
private:
    mutable Node* pnext;
public:
    int data;

    Node( int value = 0 )
        : pnext( NULL ), data( value )
    {
        pnext = this;
    }

    Node( Node const& other )
        : pnext( NULL ), data( other.data )
    {
        pnext = this;
        other.insert( *this );
    }

    ~Node()
    {
        remove( *this );
        assert( is_single() );
    }

    Node& insert( Node& other ) const
    {
        assert( other.is_single() ); // check that other is not already on some list
        assert( -1 == distance( other ) ); // check that other is not already on this list

        other.pnext = pnext;
        pnext = &other;
        return other;
    }

    size_t size() const
    {
        int size = 1 + pnext->distance( *this );
        assert( size > 0 );
        return size;
    }

    int distance( Node const& other ) const
    {
        if ( &other == this && is_single() ) {
            return 0;

        } else if ( other.is_single() ) {
            // distance cannot be measured
            return -1;
        }

        int hops = 1;

        Node const* previous = this;
        Node const* iter = pnext;
        while ( iter != &other ) {
            previous = iter;
            if ( previous == this ) {
                return -1; // other not found on this list
            }
            iter = iter->pnext;
            ++hops;
        }

        return hops;
    }

    bool is_single() const
    {
        return ( pnext == this );
    }

    bool remove( Node& other )
    {
        if ( &other == this ) {
            // Removing itself from the list:
            if ( is_single() ) {
                // ignore this call: the node is single
                return false;
            } else {
                // ask your sibling to remove you from the list:
                return pnext->remove( other );
            }
        }

        if ( other.is_single() ) // distance cannot be measured
            return false;

        Node* previous = this;
        Node* iter = pnext;
        while ( iter != &other ) {
            previous = iter;
            if ( previous == this ) {
                //cout << "Node " << &other << ':' << other.data << " not found\n";
                assert( other.is_single() );
                return false;
            }
            iter = iter->pnext;
        }
        previous->pnext = iter->pnext;
        other.pnext = &other; // make node single after successful removal
        return true;
    }
};

void print_list( Node const& head, int line = 0 )
{
    if ( line )
        cout << line << '\t';

    int list_size = head.size();
    int invariant_size = 0;
    cout << '[' << list_size << "] ";

    Node const* iter = &head;
    do {
        cout << iter->data << ' ';
        iter = iter->pnext;
        ++invariant_size;

    } while ( iter != &head );

    assert( invariant_size == list_size );
    assert( invariant_size > 1 || head.is_single() );
    cout << '\n';
}

int main( )
{
    Node n12( 12 );
    Node n99( 99 );
    Node n37( 37 );

    assert( n12.is_single() );
    assert( n12.distance( n12 ) == 0 );
    assert( n12.size() == 1 );

    n12.insert( n99 );
    assert( n12.distance( n12 ) == 2 );
    assert( n12.size() == 2 );
    print_list( n12, __LINE__ ); // 12 99
    print_list( n99, __LINE__ ); // 99 12

    n99.insert( n37 );
    assert( n12.distance( n12 ) == 3 );

    print_list( n12, __LINE__ ); // 12 99 37
    print_list( n99, __LINE__ ); // 99 37 12
    print_list( n37, __LINE__ ); // 37 12 99

    Node single;
    bool result = n12.remove( single );
    assert( result == false );

    n12.remove( n99 );
    print_list( n12, __LINE__ ); // 12 37

    n12.insert( n99 );
    print_list( n12, __LINE__ ); // 12 99 37

    n12.remove( n12 );
    print_list( n99, __LINE__ ); // 99 37

    n99.remove( n37 );
    assert( n99.is_single() );
    assert( n37.is_single() );
    assert( n12.is_single() );
    print_list( n99, __LINE__ ); // 99

    n99.remove( n99 );
    print_list( n99, __LINE__ ); // 99

    n37.insert( n99 );
    n99.insert( n12 );

    print_list( n37, __LINE__ ); // 37 99 12

    Node n55 = n12;
    n55.data = 55;
    print_list( n55, __LINE__ ); // 55 37 99 12

    result = n99.remove( n99 );
    assert( result );
    print_list( n99, __LINE__ ); // 99
    print_list( n55, __LINE__ ); // 55 37 12

    return 0;
}