#pragma once
#include "mylib.h" 

namespace mylib {
	template<typename elemtype>
	class list_item {
	public:
		typedef elemtype value_type;

		list_item(elemtype, list_item<elemtype>*);   //構造函數
		list_item(const list_item<elemtype>&);       //拷貝構造函數
		const elemtype date () const;                //返回節點數據
		const list_item<elemtype>* next() const;     //返回下個節點
		void get_date (const elemtype);              //改寫節點數據
		void get_next (const list_item<elemtype>*);  //改寫下個節點

		const list_item<elemtype>&
			operator= (const list_item<elemtype>&);   //賦值
	
	private:
		elemtype  _date;//數據
		list_item<elemtype>* _next;//下個節點 
	};//單鏈表節點類
	//節點類代碼實現
	template<typename elemtype>
		list_item<elemtype>::list_item(elemtype ia = 0,
		                               list_item<elemtype> *p = NULL) 
	{
		get_date(ia);
		if(p == NULL)
			get_next(NULL);
		else 
		{
			get_next(p->next());
			p->get_next(this);
		}
	}
	template<typename elemtype> list_item<elemtype>::
		list_item(const list_item<elemtype>& node)
	{
		get_date(node.ia);
		if(node.next() == NULL)
			get_next(NULL);
		else
		{
			get_next(node.next());
			node.get_next(this);
		}
	}

	template<typename elemtype>
		const list_item<elemtype>& list_item<elemtype>::
		operator= (const list_item<elemtype>& node)
	{
		if(this != &node)
		{
			get_date(node.ia);
			if(node.next() == NULL)
				get_next(NULL);
			else
			{
				get_next(node.next());
				node.get_next(this);
			}
		}
		return *this;
	}
	
	template<typename elemtype>
		const elemtype 
		list_item<elemtype>::date() const 
	{
		return _date;
	}
	template<typename elemtype> const 
		list_item<elemtype>* list_item<elemtype>::
		next(void) const  
	{
		return _next;
	}
	template<typename elemtype>
		void list_item<elemtype>::
		get_date(const elemtype de)
	{
		_date = de; 
    }
	template<typename elemtype>
		void list_item<elemtype>::
		get_next( const list_item<elemtype> *pev )
    { 
       _next = ( list_item<elemtype>* )pev;   
    }

	template<typename elemtype> 
	class list{
	public:
		list();                              //構造函數
		list( const list<elemtype>& );       //拷貝構造函數。只聲明
		~list();                             //析構函數
		const int size() const              ;//返回長度
		bool empty() const;            //測試是否為空
		void insert( const elemtype, const elemtype);
		                                      //在某個位子插入
		void insert_front( const elemtype );  //在頭部插入
		void insert_end( const elemtype );    //在尾部插入
		void remove( const elemtype );        //刪除某個節點
		void remove_all();                    //刪除所有
		void remove_front();                  //刪除頭節點
		void print() const;                   //打印
		const list_item<elemtype>* 
			find(const elemtype);           //查找
		const list<elemtype>&
			operator= (const list<elemtype>&);    //賦值。只聲明
	
	private:
		//私有函數集合
		void down_size();
		void add_size();
		//私有數據集合
		list_item<elemtype> *at_front;
		list_item<elemtype> *at_end;
		list_item<elemtype> *at_move;
		int                _size;
	};//鏈表類定義
	//函數實現代碼
	//私有函數集合
	template<typename elemtype>
		void list<elemtype>::add_size() 
    {
       ++_size; 
    }

	template<typename elemtype>
		void list<elemtype>::down_size() 
    {
       --_size; 
    }

	//公有函數集合
	template<typename elemtype>
		list<elemtype>::list(void)
    { 
       at_front = NULL;
       at_end = NULL;
       _size = 0;
    }

	template<typename elemtype>
		list<elemtype>::~list(void) 
    {
       remove_all();
    }

	template<typename elemtype>
		bool list<elemtype>::
		empty(void) const 
    {
       return size() == 0 ? true : false;
    }

	template<typename elemtype>
		const int list<elemtype>::
		size(void) const
    { 
       return _size;
    }

	template<typename elemtype>
		void list<elemtype>::insert_front(const elemtype iva)
    {
       list_item<elemtype> *pv = 
              new list_item<elemtype>(iva, 0);
       if(!at_front)
       {
           at_front = at_end = pv;
       }
       else 
       {
           pv->get_next(at_front);
           at_front = pv;
       }
       add_size();
    }

	template<typename elemtype>
		void list<elemtype>::insert_end(const elemtype iva) 
	{
       if( at_end == NULL) 
       {
           at_end = at_front =
                  new list_item( iva, 0 );
       }
       else 
           at_end = new list_item( iva, at_end ); 
       add_size();
    }

	template<typename elemtype> void list<elemtype>::
		insert( const elemtype ixa, const elemtype iva ) 
    {
       list_item<elemtype> *pev = 
              ( list_item<elemtype>* )find( iva );
       if( pev == NULL )
       {
           cerr << "err!" ;
           return;
       }
      if( pev == at_front ) 
           insert_front( ixa );
       else
	   {
           new list_item( ixa, pev );
           add_size();
       }
    }

	template<typename elemtype> const 
		list_item<elemtype>* list<elemtype>::
		find( const elemtype iva )
    {
       list_item *at_move = at_front;
       while( at_move != NULL ) 
       {
           if( at_move->date() == iva )
              return at_move;
           at_move = ( list_item<elemtype>* )at_move->next();
           
       }
           return NULL;
    }

	template<typename elemtype>
		void list<elemtype>::remove_front()
    {
       if( at_front )
       {
           list_item <elemtype> *pev = at_front;
           at_front = ( list_item<elemtype>* )at_front->next();
           delete pev;
           down_size();
       }
    }

	template<typename elemtype>
		void list<elemtype>::remove( elemtype iva )
    {
       list_item<elemtype> *pev = at_front;
       while(pev && (pev->date()==iva))
       {
           pev = ( list_item<elemtype>* )pev->next();
           remove_front();
       }
       if( !pev )
           return ;
       list_item *prv = pev;
       pev = ( list_item<elemtype>* )pev->next();
       while( pev ) 
       {
           if( pev->date() == iva ) 
           {
              prv->get_next( pev->next() );          
              down_size();
              delete pev;
              pev = ( list_item<elemtype>* )prv->next();
              if( pev != NULL )
              {
                  at_end = prv;
                  return;
              }
           }
           else 
           {
              prv = pev;
              pev = ( list_item<elemtype>* )pev->next();
           }
       }
    }

	template<typename elemtype>
		void list<elemtype>::remove_all()
    {
       while( at_front )
           remove_front();
       _size = 0;
       at_front = at_end = NULL;
    }

	template<typename elemtype>
		void list<elemtype>::print() const 
    {
       list_item<elemtype> *pev = at_front;
	   std::cout << '[' << size() << ']';
	   std::cout << '{';
       for( int ix = 0; pev && ix < size(); ++ix ) 
       {
		   std::cout << pev->date() << ' ';
           pev = (list_item<elemtype>*)pev->next();
       }
	   std:::cout << '}' << std::endl;
    }

};