class String
{
private:
 size_t  _size;
 char *_string;
 void init (size_t , const char *);
public:
 String () { init (0, NULL); }
 String (const char * str) { init (strlen(str), str); }
 String (const String & str) { init (str.size (), str.c_str());}
 ~String () { delete [] _string; }
 //member methods
 int count (char ch)const;
 size_t size ()const { return _size; }
 char * c_str ()const {return _string ;}
 const char * to_upper ()const;
 //assign operator
 String & operator = (const char * str);
 String & operator = (const String & str);
 //overload operators
 bool operator == (const char *str)const {return strcmp (_string, str) == 0; }
 bool operator == (const String &str)const {return strcmp (_string, str.c_str ()) == 0; }
 bool operator != (const String & str)const { return strcmp (_string, str.c_str ()) != 0; }
 bool operator != (const char *str)const {return strcmp (_string, str) != 0; }
 bool operator < (const char *str)const {return strcmp (_string, str) < 0; }
 bool operator < (const String & str)const {return strcmp (_string, str.c_str ()) < 0; }
 bool operator > (const char *str)const {return strcmp (_string, str) > 0; }
 bool operator > (const String & str)const {return strcmp (_string, str.c_str ()) > 0; }
 String &  operator += (const char *str);
 String  & operator += (const String & str);
 char & operator [] (size_t i) { assert(i >= 0 && i < _size); return _string[i]; }
 //friend methods
 friend std::ostream & operator << (std::ostream & os, const String & str);
 friend std::istream & operator >> (std::istream &is, String & str);
 friend bool operator == (const char *cstr, const String & sstr) {return sstr.operator == (cstr); }
 friend bool operator != (const char *cstr, const String & sstr) {return sstr.operator != (cstr); }
 friend bool operator < (const char *cstr, const String & sstr) {return sstr.operator <(cstr); }
 friend bool operator > (const char *cstr, const String & sstr) {return sstr.operator >(cstr); }
};

#endif
//string.cpp
#include "String.h"
#include <cstring>
#include <iomanip>
#pragma warning(disable : 4996)

void String::init(size_t size, const char *str)
{
 _size = size;
 if (!str)
 {
  _string = new char [1];
  _string[0]  = '\0';
 }
 _string = new char[_size + 1];
 strncpy (_string, str, _size);
 _string[_size ] = '\0';
 //strcpy (_string, str);
}

String & String::operator = (const char *str)
{
 delete [] _string;
 init (strlen (str), str);std::cout << this->_string << "_";
 return *this;
}

String & String::operator = (const String &str)
{
 if (*this == str)
  return *this;
 delete [] _string;
 init (str.size (), str.c_str ());
 return *this;
}

String  & String::operator +=(const char *str)
{
 String temp(*this);
 _size += strlen (str);
 _string = new char[_size + 1];
 strcpy (_string, temp.c_str ());
 //strcat (_string, str);
 strcpy (_string+temp.size (), str);
 return *this;
}

String & String::operator +=(const String &str)
{
 String temp(*this);
 _size +=  str.size ();
 _string = new char[_size + 1];
 strcpy (_string, temp.c_str ());
 //strcat (_string , str.c_str ());
 strcpy (_string+temp.size (), str.c_str ());
 return *this;
}

int String::count (char ch)const
{
 int cn = 0;
 for (size_t i = 0; i < _size; i++)
  if (ch == tolower(_string[i]))
   cn++;
 return cn;
}

const char * String::to_upper ()const
{
 size_t size = strlen (_string);
 char *temp = new char[size + 1]; 
 size_t j = 0;
 for (size_t i = 0; i < size; i++)
  if (isalpha(_string[i]) || _string[i] == ' ')
   if (isalpha (_string[i]))
    temp[j++] = toupper (_string[i]);
   else
    temp[j++] = _string[i];
 temp[j] = '\0';
 return temp;
}
std::ostream & operator << (std::ostream & os, const String & str)
{
 return os << str.c_str ();
}

std::istream & operator >> (std::istream & is, String & str)
{
 const int limit_string_size = 50;
 char Inbuf [limit_string_size];

 //is.read (Inbuf, limit_string_size);
 //is >> setw (limit_string_size) >> Inbuf;
 is.getline (Inbuf, limit_string_size-1, '\n');
 /*if (is)
 {
  while (is.get () == '\n')
   break;
  Inbuf[limit_string_size-1] = '\0';
 }*/
 //is >> Inbuf;
 str = Inbuf;
 return is;
}

//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;
}

template <typename Type, int N>
class N_Grid
{
public:
 //constructors and destructors
 N_Grid ();
 N_Grid (int size);
 N_Grid (const N_Grid<Type, N> & );
 ~N_Grid ();
 //member methods
 N_Grid<Type, N> & operator = (const N_Grid<Type, N> & );
 void resize (int size );
 N_Grid<Type, N-1> & operator [] (int i);
 const N_Grid<Type, N-1> & operator [] (int i)const ;
 void print (std::ostream & os = std::cout)const;
 int get_size ()const { return _size; }
 static const int _Default_size = 10;
protected:
 void copy_from (const N_Grid<Type, N> & ); 
 int _size;
 N_Grid<Type, N-1> *_elem;
};
//definitions

template <typename Type, int N>
N_Grid<Type, N>::N_Grid(): _size (_Default_size)
{
 _elem = new N_Grid<Type, N-1> [_size];
}

template <typename Type, int N>
N_Grid<Type, N>::N_Grid(int size) : _size (size)
{
 _elem = new N_Grid<Type, N-1> [_size];
 //Allocate the array above calls the 0-argument
 //constructor for the N_Grid<Type, N-1>, which
 //constructs it with the default size.
 for (int i = 0; i < _size; i ++)
  _elem[i].resize (_size);
}

template <typename Type, int N>
N_Grid<Type, N>::N_Grid(const N_Grid<Type,N> & n_grid)
{
 copy_from (n_grid);
}

template <typename Type, int N>
N_Grid<Type, N>::~N_Grid ()
{
 delete [] _elem;
}

template <typename Type, int N>
void N_Grid<Type, N>::copy_from(const N_Grid<Type,N> & n_grid)
{
 _size = n_grid._size;
 _elem = new N_Grid<Type, N-1> [_size];
 for (int i = 0; i < _size; i++)
  _elem[i] = n_grid._elem [i];
}

template <typename Type, int N>
N_Grid<Type, N> & N_Grid<Type, N>::operator =(const N_Grid<Type,N> & n_grid)
{
 if (this == &n_grid)
  return *this;
 delete [] _elem;
 copy_from (n_grid);
 return *this;
}

template <typename Type, int N>
void N_Grid<Type, N>::resize(int size)
{
 N_Grid<Type, N> temp (*this);
 _size = size;
 _elem = new N_Grid<Type, N-1> [_size];
 for (int i = 0; i < _size && i < temp._size; i++)
 {
  _elem[i] = temp._elem[i];
  //risize the nested Grid elements recursively
  _elem[i].resize (_size);
 }
}

template <typename Type, int N>
N_Grid<Type, N-1> & N_Grid<Type, N>::operator [](int i)
{
 assert (i >= 0 && i < _size);
 return _elem[i];
}

template <typename Type, int N>
const N_Grid<Type, N-1> & N_Grid<Type, N>::operator [](int i) const
{
 assert (i >= 0 && i < _size);
 return _elem[i];
}

template <typename Type, int N>
void N_Grid<Type, N>::print(std::ostream &os = std::cout) const
{
 for (int i = 0; i < _size ; i++)
  _elem[i].print ();
 os << '\n';
}

template <typename Type>
class N_Grid<Type, 1>
{
public:
 //constructors and destructors
 N_Grid ();
 N_Grid (int size);
 N_Grid (const N_Grid<Type, 1> & );
 ~N_Grid ();
 //member methods
 N_Grid<Type, 1> & operator = (const N_Grid<Type, 1> & );
 void resize (int size );
 N_Grid<Type, 1> & operator [] (int i);
 const N_Grid<Type, 1> & operator [] (int i)const ;
 void print (std::ostream & os = std::cout)const;
 int get_size ()const { return _size; }
 static const int _Default_size = 10;
protected:
 void copy_from (const N_Grid<Type, 1> & ); 
 int _size;
 N_Grid<Type, 1> *_elem;
};
template <typename Type>
N_Grid<Type, 1>::N_Grid() : _size (_Default_size)
{
 _elem = new Type [_size];
}

template <typename Type>
N_Grid<Type, 1>::N_Grid(int size) : _size (size)
{
 _elem = new Type [_size];
}

template <typename Type>
N_Grid<Type, 1>::N_Grid(const N_Grid<Type, 1> & grid)
{
 copy_from (grid);
}

template <typename Type>
N_Grid<Type, 1>::~N_Grid()
{
 delete [] _elem;
}

template <typename Type>
void N_Grid<Type, 1>::copy_from(const N_Grid<Type,1> & grid)
{
 _size = grid._size;
 _elem = new Type [_size];
 for (int i = 0; i < _size; i++)
  _elem[i] = grid._elem[i];
}

template <typename Type>
N_Grid<Type, 1> & N_Grid<Type, 1>::operator =(const N_Grid<Type,1> & grid)
{
 if (this == &grid)
  return *this;
 delete [] _elem;
 copy_from (grid);
 return *this;
}

template <typename Type>
void N_Grid<Type, 1>::resize(int size)
{
 N_Grid<Type, 1> temp (*this);
 _size = size;
 _elem = new Type[_size];
 for (int i = 0; i < _size; i++)
  _elem[i] = temp._elem[i];
}

template <typename Type>
N_Grid<Type, 1> & N_Grid<Type, 1>::operator [](int i)
{
 assert (i >= 0 && i < _size);
 return _elem[i];
}

template <typename Type>
const N_Grid<Type, 1> & N_Grid<Type, 1>::operator [](int i) const
{
 assert (i >= 0 && i < _size);
 return _elem[i];
}

template <typename Type>
void N_Grid<Type, 1>::print(std::ostream &os = std::cout) const
{
 for (int i = 0; i < _size; i++)
   os << _size;
 os << '\n';
}
#endif