///list.h
using namespace std;
class ilist_item {
    public:
        ilist_item( int value, ilist_item *item_to_link_to = 0 );
        int value() { return _value; }
        ilist_item* next() { return _next; }
        void next( ilist_item *link ) { _next = link; }
        void value( int new_value ) { _value = new_value; }
    private:
        int _value;
        ilist_item *_next;
};
 
class ilist {
    public:
        ilist() : _at_front( 0 ),_at_end( 0 ), _size( 0 ) {}
        int size();
        void insert( ilist_item *ptr, int value );
        void bump_up_size();
        void bump_down_size();
        void insert_front( int value );
        void insert_end( int value );
        ilist_item* find( int value );
        void display( ostream &os = cout );
        void remove_front();
        void remove_all();
        int remove( int value );
        //连接两个链表
        void concat( const ilist &il );
        //翻转一个链表
        void reverse();
        void insert_all( const ilist &rhs );
        ilist( const ilist& );
        ilist& operator=( const ilist& );
    private:
        //禁止用一个链表对象初始化或赋值给另一个
        // ilist( const ilist& );
        //ilist& operator=( const ilist& );
        ilist_item *_at_front;
        ilist_item *_at_end;
        int _size;
        int _value;
        ilist_item *_next;
};

//list.cpp
#include < iostream >
#include "list.h"
using namespace std;
 
inline ilist_item::ilist_item( int value, ilist_item *item ) : _value( value ) {
    if ( !item ) {
        _next = 0;
    } else {
        //这两步要多加注意
        _next = item->_next;
        item->_next = this;
    }
}
 
inline  void ilist::insert( ilist_item *ptr, int value ) {
    if ( !ptr ) {
        insert_front( value );
    } else {
        bump_up_size();
        new ilist_item(value, ptr );
    }
}
 
void ilist::insert_front( int value) {
    ilist_item *ptr = new ilist_item( value );
    if ( !_at_front ) {
        _at_front = _at_end = ptr;
    } else {
        ptr->next( _at_front );
        _at_front = ptr;
    }
    bump_up_size();     
}
 
inline void ilist::insert_end( int value ) {
    if ( !_at_end ) {
        _at_end = _at_front = new ilist_item( value );
    } else {
        _at_end = new ilist_item( value, _at_end );
    }
    bump_up_size();
}
 
 
ilist_item* ilist::find( int value ) {
    ilist_item *ptr = _at_front;
    while ( ptr ) {
        if ( ptr->value() == value ) break;
        ptr = ptr->next();
    }
    return ptr;
}
 
 
//拷贝构造函数
ilist::ilist( const ilist &rhs ): _at_front( 0 ), _at_end( 0 ) {
    insert_all( rhs );
}
 
void ilist::insert_all( const ilist &rhs ) {
    ilist_item *pt = rhs._at_front;
    while ( pt ) {
        insert_end( pt->value() );
        pt = pt->next();
    }
}
 
void ilist::display( ostream &os ) {
    os < < "\n( " << _size << ")(";
    ilist_item *ptr = _at_front;
    while ( ptr ) {
        os << ptr->value() < < " ";                   
        ptr = ptr->next();
    }
    os < < ")\n";
}
 
 
 
inline void ilist::remove_front(){
    if ( _at_front ) {
        ilist_item *ptr = _at_front;
        _at_front = _at_front->next();
        bump_down_size();
        delete ptr;
    }   
}
 
void ilist::remove_all() {
    while ( _at_front ) {
        remove_front();
    }
    _size = 0;
    _at_front = _at_end = 0;
}
 
int ilist::remove( int value ) {
    ilist_item *plist = _at_front;
    int elem_cnt = 0;
    while (plist && plist->value() == value ) {
        plist = plist->next();
        remove_front();
        ++elem_cnt;
    }
 
    if ( !plist ) return elem_cnt;
    ilist_item *prev = plist;
    plist = plist->next();
    while ( plist ) {
        if ( plist->value() == value ) {
            prev->next( plist->next() );
            delete plist;
            ++elem_cnt;
            bump_down_size();
            plist = prev->next();
            if ( !plist ) {
                _at_end = prev;
                return elem_cnt;
            }      
        } else {
            prev = plist;
            plist = plist->next();
        }   
    }   
    return elem_cnt;
}
 
void ilist::concat( const ilist &il ) {
    ilist_item *ptr = il._at_front;
    while ( ptr ) {
        insert_end( ptr->value() );
        ptr = ptr->next();
    }
}
 
void ilist::reverse() {
    ilist_item *ptr = _at_front;
    ilist_item *prev = 0;
    _at_front = _at_end;
    _at_end = ptr;
    while ( ptr != _at_front ) {
        ilist_item *tmp = ptr->next();
        ptr->next( prev );
        prev = ptr;
        ptr = tmp;
    }
    _at_front->next( prev );
}
 
inline void ilist::bump_up_size() { ++_size; }
inline void ilist::bump_down_size() { --_size; }

//下面类的测试代码
#include < iostream >
#include "list.h"
using namespace std;
 
int main()
{
    ilist mylist;
    /* cout < <"#####################测试一####################"<<endl;
       for ( int ix = 0; ix< 10; ++ix ) {
       mylist.insert_front( ix );
       mylist.insert_end( ix );
       }
       cout << "Ok: after insert_front() and insert_end()\n";
       mylist.display();
       ilist_item *it = mylist.find( 8);
       cout << "\n"
       << "Searching for the value 8: found it<<"
       << ( it ? " yes!\n" : " no!\n" );
       mylist.insert( it, 1024 );
       cout << "\n"
       << "Inserting element 1024 following the value 8\n";
       mylist.display();
       int elem_cnt = mylist.remove( 8 );
       cout << "\n"
       << "Removed " << elem_cnt << " of the value 8\n";
       mylist.display();
       cout << "\n" << "Removed front element\n";
       mylist.remove_front();
       mylist.display();
       cout << "\n" << "Removed all elements\n";
       mylist.remove_all();
       mylist.display();
       cout <<"#####################测试一结束################"<<endl;
       */
    /*cout <<"#####################测试二####################"<<endl;
      cout << "\n———————————————–\n"
      << "test #1: items at end\n"
      << "————————————————\n";
      mylist.insert_front( 1 );
      mylist.insert_front( 1 );
      mylist.insert_front( 1 );
      mylist.insert_front( 2 );
      mylist.insert_front( 3 );
      mylist.insert_front( 4 );
      mylist.display();
      int elem_cnt = mylist.remove( 1 );
      cout << "\n" << "Removed " << elem_cnt << " of the value 1\n";
      mylist.display();
      mylist.remove_all();
      cout << "\n———————————————–\n"
      << "test #2: items at front \n"
      << "————————————————-\n";
      mylist.insert_front( 1 ); mylist.insert_front( 1 );
      mylist.insert_front( 1 );
      mylist.display();
      elem_cnt = mylist.remove( 1 );
      cout << "\n" << "Removed " << elem_cnt << " of the value 1\n";
      mylist.display();
      mylist.remove_all();
      cout << "\n———————————————–\n"
      mylist.insert_front( 0 );
      mylist.insert_front( 2 );
      mylist.insert_front( 4 );
      mylist.display();
      elem_cnt = mylist.remove( 1 );
      cout << "\n" << "Removed " << elem_cnt << " of the value 1\n";
      mylist.display();
      mylist.remove_all();
      cout << "\n———————————————-\n"
      << "test #4: items at front and end\n"
      << "———————————————–\n";
      mylist.insert_front( 1 );
      mylist.insert_front( 1 );
      mylist.insert_front( 1 );
      mylist.insert_front( 0 );
      mylist.insert_front( 2 );
      mylist.insert_front( 4 );
      mylist.insert_front( 1 );
      mylist.insert_front( 1 );
      mylist.insert_front( 1 );
      mylist.display();
      elem_cnt = mylist.remove( 1 );
      cout << "\n" << "Removed " << elem_cnt << " of the value 1\n";
      mylist.display();
      cout << "#################测试二结束###################" << endl;*/
    cout <<"#####################测试三##################"<<endl;
    for ( int ix = 0; ix< 10; ++ix ) {
//        mylist.insert_front( ix );
        mylist.insert_front(ix);
    }
    mylist.display();
    cout << "\n" << "reverse the list\n";
    mylist.reverse();
    mylist.display();
    ilist mylist_too;
    mylist_too.insert_end( 0 );
    mylist_too.insert_end( 1 );
    mylist_too.insert_end( 1 );
    mylist_too.insert_end( 2 );
    mylist_too.insert_end( 3 );
    mylist_too.insert_end( 5 );
    cout << "\n" << "mylist_too:\n";
    mylist_too.display();
    mylist.concat( mylist_too );
    cout << "\n" << "mylist after concat with mylist_too:\n";
    mylist.display();
    cout <<"#####################测试三结束###########"<<endl;
    return 0;
}