// @topic T03010 Lists
// @brief singly linked list

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

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

    // Constructor taking initial value:
    Node( int value = 0 )
        : pnext( NULL ), data( value )
    {
    }

    // Insert other node in front:
    void insert( Node& other ) const
    {
        other.pnext = pnext;
        pnext = &other;
    }

    // Remove other node in front:
    bool remove( Node const& other )
    {
        Node* previous = this;
        Node* iter = pnext;
        while ( iter != &other ) {
            if ( iter == NULL )
                return false;
            previous = iter;
            iter = iter->pnext;
        }
        previous->pnext = iter->pnext;
        // Make node "single" after successful removal:
        other.pnext = NULL;
        return true;
    }

    // Calculate number of nodes in the list:
    size_t size() const
    {
        return 1 + distance( *this );
    }

    // Measure distance to other node:
    int distance( Node const& other ) const
    {
        int hops = 1;
        Node const* iter = pnext;
        while ( iter != &other ) {
            if ( iter == NULL )
                return hops - 1;
            iter = iter->pnext;
            ++hops;
        }
        return hops;
    }
};

// Print contents of the list:
void print_list( Node const& head )
{
    cout << '[' << head.size() << "]\t";
    Node const* iter = &head;
    do {
        cout << iter->data << ' ';
        iter = iter->pnext;

    } while ( iter != NULL );
    cout << '\n';
}

// Main driver to test list functionality:
int main( )
{
    Node n12( 12 );
    Node n99( 99 );
    Node n37( 37 );

    assert( n12.distance( n12 ) == 0 );

    n12.insert( n99 );
    assert( n12.distance( n99 ) == 1 );

    print_list( n12 ); // 12 99
    print_list( n99 ); // 99

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

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

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

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

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

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

    n99.remove( n37 );
    print_list( n99 ); // 99

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

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

    print_list( n37 ); // 37 99 12

    result = n37.remove( n99 );
    assert( result );
    print_list( n99 ); // 99
    print_list( n37 ); // 37 12

    return 0;
}