#include <iostream>
using namespace std;

// Definition of Class ListNode
class ListNode {
private:  // Each object contains two values
    int data;
    ListNode *link;
public:   // These are the member functions for the Class ListNode
    void SetNext(ListNode * ptr) {link = ptr; return;};
    ListNode * GetNext() {return link;};
    void SetData(int x) {data = x; return;};
    int GetData() {return data;};
    ListNode(int);
    ~ListNode() { cout << "deallocated ListNode " << this << endl;};

};

// Constructor for Class ListNode
ListNode::ListNode(int element = 0) // 0 is the default argument
{
    data = element;
    link = 0; // null pointer constant
    cout << "allocated ListNode " << this << " with initial value " << data << endl;
}

// Definition for Class List
class List {
private: // Each object contains two values
    ListNode *first;  // Pointer to first ListNode object in List
    ListNode *last;    // Pointer to last ListNode object in List
    void InsertAfterNode(ListNode *p, int x);
    void InsertFront(int x);
    void InsertSorted(int x);
public: // Member functions
    List();
    ~List() { cout << "deallocated List " << this << endl;};
    void Readin();
    void Printout();
    void Erase();
};

// Constructor for Class List
List::List()
{last = first = 0;
 cout << "allocated List " << this << endl;
}

void List::Printout() // Printing out the contents of a List
{   int contents;
    ListNode  *ptr;
    ptr = first;
    while(ptr)
     { cout << ptr->GetData() << " Listode " << ptr << endl;
       ptr = ptr->GetNext();
     }
    return;
}

void List::Readin()  // Reading in the contents of a List
{ int contents;
  cout << "Input a List. one element per line and ending with a line with just a zero" << endl;
  cin >> contents;
  while (contents)
   {this->InsertSorted(contents);
    cin >> contents;   
   }
}

void List::InsertAfterNode(ListNode *p, int x) // Insert a ListNode after
                                           // certain ListNode in a List
{
    ListNode *t = new ListNode(x); // create and initialize new node
    // insert after p
    t->SetNext( p->GetNext() );
    p->SetNext( t );
    if (last == p) last=t;
}

void List::InsertFront(int x) // Insert a ListNode at the
                              // beginning of a List
{
    ListNode *t = new ListNode(x); // create and initialize new node
    t->SetNext( first );
    if (last == 0) last = t;
    first = t;
}

void List::InsertSorted(int x) { // Insert a ListNode with data value x
    ListNode *p = first;
    if (p == 0) {InsertFront(x); return;}
    if (x == p->GetData()) return;
    if (x < p->GetData()) {InsertFront(x); return;}
    while (p->GetNext())
       { 
         if (p->GetNext()->GetData() == x) return;
         if (p->GetNext()->GetData() > x) {InsertAfterNode(p,x); return;}
         p = p->GetNext();
       }
    InsertAfterNode(p,x);
}

void List::Erase() {
   ListNode *ptr, *tempptr;
   ptr = first;
   while(ptr)
     {
       tempptr=ptr->GetNext();
       delete(ptr);
       ptr=tempptr;
     }
   last = first = 0;
}


main()
{
  cout << endl;

  List l;
  l.Readin();
  cout << "List l" << " Located at " << &l << endl;
  l.Printout();
  cout << endl;

  List m;
  m.Readin();
  cout << "List m"  << " Located at " << &m<< endl;
  m.Printout();
  cout << endl;

  List o;
//  Terrible copy because it does not make a list of the copy
  o = m;
  cout << "List o"  << " Located at " << &o<< endl;
  o.Printout();
  cout << endl;

  l.Erase();
  m.Erase();

// One should not use the o list after this point

  cout << "List l"  << " Located at " << &l<< endl;
  l.Printout();
  cout << "List m"  << " Located at " << &m<< endl;
  m.Printout();
  cout << "List o"  << " Located at " << &o<< endl;
  o.Printout();
  cout << endl;
}