//头文件
#ifndef MYLIST_H_
#define MYLIST_H_
#include <iostream>

//declarations
template <typename elemType>
class Mylist_item
{
private:
 elemType _value;
 Mylist_item *_next;
public:
 Mylist_item (elemType value, Mylist_item * item = 0);
 ~Mylist_item () { }
 elemType Value () {return _value; }              //return the value of the node
 Mylist_item * Next () { return _next; }               //return the pointer to the next node
 void next (Mylist_item *ptr) { _next = ptr; }
 void set_value (elemType value ) { _value = value; }
};

template <typename elemType>
class Mylist
{
private:
 Mylist_item<elemType> *_at_front;                  //pointer to the head
 Mylist_item<elemType> *_at_end;                   //pointer to the tail
 Mylist_item<elemType> *_current;                   //pointer to the current element
 int _size;
 //renew the size
 void bump_up_size () { ++_size; }
 void bump_down_size () { --_size; }
public:
 Mylist () : _at_front (0), _at_end (0), _size (0) { }
 Mylist (const Mylist & rhs);
 ~Mylist () { }
 Mylist & operator = (const  Mylist  & rhs);

 //operators overloading
 Mylist_item<elemType> * operator ++ ();
 //Mylist_item<elemType> *operator ++ ();

 //sorting function (default in ascending order
 void sort (Mylist_item<elemType> *begin, Mylist_item<elemType> *end);

 //insertion functions, if the Mylist is full, do nothing

 //insert the value to the back of ptr
 void insert (Mylist_item<elemType> *ptr, elemType value);
 //insert the value to the front of the Mylist
 void insert_front (elemType value);
 //insert the value to the end of the Mylist
 void insert_end (elemType value);
 //insert the whole Mylist: rhs to the end of the current Mylist
 void insert_all (const Mylist & rhs);

 //element removing functions,  if the Mylist is empty , do nothing

 //remove all the elements of the Mylist equal to the value and return the numbers of removed elements
 int remove (elemType value);
 //remove all the elements of the Mylist
 void remove_all ();
 //remove the front element of the Mylist
 void remove_front ();

 //find the value that given, if successful, return the pointer to the element, or return null
 Mylist_item<elemType> * find (elemType value, Mylist_item<elemType> *start = 0);
 
 //display all the elements of the Mylist on screen
 void display (std::ostream & os = std::cout)const;

 //concat the given Mylist to the current Mylist
 void concat (const Mylist & rhs);
 Mylist  concat_copy (const Mylist &rhs);

 // reverse the Mylist, front to end
 void reverse ();
 Mylist reverse_copy ();

 //iterators
 Mylist_item<elemType> * init_iter (Mylist_item<elemType> *it = 0);
 Mylist_item<elemType> * next_iter ();

};

//definitions
template <typename elemType>
Mylist_item<elemType>::Mylist_item(elemType value, Mylist_item<elemType> *item)
{
 _value = value;
 if (!item)
  _next = 0;
 else
 {
  _next = item->Next ();
  item->_next = this;
 }
}

template <typename elemType>
Mylist<elemType>::Mylist (const Mylist & rhs): _at_front (0), _at_end (0)
{
 insert_all (rhs);
}

template <typename elemType>
Mylist<elemType> & Mylist<elemType>::operator =(const Mylist<elemType> &rhs)
{
 if (this == & rhs)
  return *this;
 remove_all ();
 insert_all (rhs);
 return *this;
}

template <typename elemType>
Mylist_item<elemType> * Mylist<elemType>::operator ++ ()
{
 return next_iter ();
}

/*template <typename elemType>
Mylist_item <elemType> * Mylist<elemType>::operator ++ ()
{
 Mylist_item<elemType> * temp = this;
 this = next_iter ();
 return temp;
}*/

template <typename elemType>
Mylist_item<elemType> * Mylist<elemType>::init_iter (Mylist_item<elemType> *it)
{
 return _current = it ? _current : _at_front;
}

template <typename elemType>
Mylist_item<elemType> * Mylist<elemType>::next_iter()
{
 Mylist_item<elemType> * temp = _current ? _current = _current->Next () : _current;
 return temp;
}

template <typename elemType>
void Mylist<elemType>::reverse ()
{
 Mylist_item<elemType> *ptr = _at_front;
 Mylist_item<elemType> *pre = 0;
 _at_front = _at_end;
 _at_end = ptr;
 while (ptr != _at_front)
 {
  Mylist_item<elemType> *temp = ptr->Next ();
  ptr->next (pre);
  pre = ptr;
  ptr = temp;
 }
}

template <typename elemType>
Mylist<elemType> Mylist<elemType>::reverse_copy ()
{
 Mylist<elemType>new_list;
 Mylist_item<elemType> *ptr = _at_front;
 for (; ptr ; ptr = ptr->Next ())
  new_list.insert_front (ptr->Value ());
 return new_list;
}

template <typename elemType>
void Mylist<elemType>::concat(const Mylist<elemType> &rhs)
{
 Mylist_item<elemType> * temp = rhs._at_front;
 while (temp)
 {
  insert_end (temp->Value ());
  temp = temp->Next ();
 }
}

template <typename elemType>
Mylist<elemType> Mylist<elemType>::concat_copy (const Mylist<elemType> & rhs)
{
 Mylist<elemType>new_list;
 Mylist_item<elemType> *ptr = _at_front;
 while (ptr)
 {
  new_list.insert_end (ptr->Value ());
  ptr = ptr->Next ();
 }
 for (ptr = rhs._at_front; ptr; ptr = ptr->Next ())
  new_list.insert_end (ptr->Value ());
 return new_list;
}

template <typename elemType>
void Mylist<elemType>::display(std::ostream &os) const
{
 os << " \n( " << _size << " ) ( ";
 Mylist_item<elemType> * ptr = _at_front;
 while (ptr)
 {
  os << ptr->Value () << " ";
  ptr = ptr->Next ();
 }
}

template <typename elemType>
Mylist_item<elemType> * Mylist <elemType>::find(elemType value, Mylist_item<elemType> *start)
{
 Mylist_item<elemType> *ptr = start ?start : _at_front;
 while (ptr)
 {
  if (ptr->Value () == value)
   break;
  ptr = ptr->Next ();
 }
 return ptr;
}

template <typename elemType>
int Mylist<elemType>::remove(elemType value)
{
 Mylist_item<elemType> *ptr = _at_front;
 int count = 0;
 while (ptr && ptr->Value () == value)
 {
  ptr = ptr->Next ();
  remove_front ();
  ++count;
 }
 if (!ptr)
  return count;
 Mylist_item<elemType> * pre = ptr;
 ptr = ptr->Next ();
 while (ptr)
 {
  if (ptr->Value () == value)
  {
   if (_current == ptr)
    _current = ptr->Next ();
   pre->next (ptr->Next ());
   ++count;
   delete ptr;
   bump_down_size ();
   ptr = pre->Next ();
  }
  else
  {
   pre = ptr;
   ptr = ptr->Next ();
  }
 }
 return count;
}

template <typename elemType>
void Mylist<elemType>::remove_front ()
{
 if (_at_front)
 {
  Mylist_item<elemType> * temp = _at_front;
  if (_current == _at_front)
   _current = _at_front->Next ();
  _at_front = _at_front->Next ();
  bump_down_size ();
  delete temp;
 }
}

template <typename elemType>
void Mylist<elemType>::remove_all ()
{
 while (_at_front)
  remove_front ();
 _size = 0;
 _at_front = _at_end = 0;
}

template <typename elemType>
void Mylist<elemType>::insert(Mylist_item<elemType> *ptr, elemType value)
{
 if (!ptr)
  insert_front (value);
 else
 {
  bump_up_size ();
  new Mylist_item<elemType>(value, ptr);
 }
}

template <typename elemType>
void Mylist<elemType>::insert_front(elemType value)
{
 Mylist_item<elemType> *ptr = new Mylist_item<elemType> (value);
 if (!_at_front )
  _at_front = _at_end = ptr;
 else
 {
  ptr->next (_at_front);
  _at_front = ptr;
 }
 bump_up_size ();
}

template <typename elemType>
void Mylist<elemType>::insert_end(elemType value)
{
 Mylist_item<elemType> *ptr = new Mylist_item<elemType> (value);
 if (!_at_end)
  _at_front = _at_end = ptr;
 else                    //_at_end = new Mylist_item<elemType> (value, _at_front);
 {
  _at_end->next (ptr);
  _at_end = ptr;
 }
 bump_up_size ();
}

template <typename elemType>
void Mylist<elemType>::insert_all(const Mylist<elemType> &rhs)
{
 Mylist_item<elemType> *ptr = rhs._at_front;
 while (ptr)
 {
  insert_end (ptr->Value ());
  ptr = ptr->Next ();
 }
}
#endif

//main () 函数

#include <iostream>
#include "Mylist.h"

int main()
{
 using std::cout;
 using std::endl;

 Mylist<int>mylist;

 for (int i = 0; i < 10; ++i)
 {
  mylist.insert_front (i);
  mylist.insert_end (i);
 }

 cout << "\nUse of init_iter() and next_iter () "
  << " to iterater across each Mylist item:\n";

 Mylist_item<int> *iter;
 //for (iter = mylist.init_iter (); iter; iter = mylist.next_iter ())
 for (iter = mylist.init_iter (); iter; iter = mylist++)
  cout << iter->Value () << " ";

 cout << "\nUse of copy constructor\n";

 Mylist<int> mylist2 (mylist);
 mylist.remove_all ();

 for (iter = mylist2.init_iter (); iter; iter = mylist2.next_iter ())
  cout << iter->Value () << " ";

 cout << " \nUse of copy assignment operator\n";
 mylist = mylist2;

 for (iter = mylist.init_iter (); iter; iter = mylist.next_iter ())
  cout << iter->Value () << " ";
 cout <<endl;

 cout << "\nUse of reverse_copy function:\n";
 Mylist<int>mylist3 = mylist.reverse_copy ();

 for (iter = mylist3.init_iter (); iter; iter = mylist3.next_iter ())
  cout << iter->Value () << " ";

 cout << "\nUse of concat_copy function:\n";
 mylist.remove (3);
 mylist.insert (mylist.init_iter (),16);
 mylist2 = mylist3.concat_copy (mylist);
 mylist2.display ();
 
 return 0;
}