#include <iostream>

using namespace std;

// recursive version
// finding, adding and deleting items from linked list of char

class node
  {
  public:
    char item;                               // content
    node* link;                              // ptr to next node
    node();                                  // default constructor
    node(char, node*);                       // another constructor
  private:
    friend class list;                       // 'list' fns can see all of node
    friend ostream& operator<< (ostream &, const node &);  // overloaded print op.
    friend bool add_recr_helper(node* current, char new_item, char after);
    friend bool del_recr_helper(node* current, char item);
  };
  
class list
  {
  public:
    node* head;                              // ptr to head of list
    list();                                  // default constructor
    list(const char[]);                      // another constructor
    ~list();                                 // destructor
    list(const list& in_list);               // copy constructor
    list& operator=(const list& in_list);    // overloaded asgt op

         // add item after first occurence of 'after'
    bool add_recr(char new_item, char after);

         // delete first occurence of item
    bool del_recr(char del_item);

  private:
    friend ostream& operator<< (ostream &, const list &);  // overloaded print op.
    void reset();                            // reset to null
  };
  
// ***********************************


int main() 

{

  list list3("");
  cout << "list is " << list3 << endl << endl;

  list3.add_recr('a', 'x' );
  cout << "list is " << list3 << endl << endl;

  list3.add_recr('d', 'a');
  cout << "list is " << list3 << endl << endl;

  list3.add_recr('b', 'a');
  cout << "list is " << list3 << endl << endl;

  list3.add_recr('c', 'b');
  cout << "list is " << list3 << endl << endl;

  list3.add_recr('x', 'y');
  cout << "list is " << list3 << endl << endl;

  list3.del_recr('x');
  cout << "list is " << list3 << endl << endl;

  list3.del_recr('b');
  cout << "list is " << list3 << endl << endl;

  list3.del_recr('a');
  cout << "list is " << list3 << endl << endl;

  list3.del_recr('d');
  cout << "list is " << list3 << endl << endl;

  list3.del_recr('c');
  cout << "list is " << list3 << endl << endl;

  list3.del_recr('x');
  cout << "list is " << list3 << endl << endl;

  return 0;
}

  
// ***********************************

list::list()                        // default constructor
  {
    head = 0;
  }

list::list(const char* in_str)          // another constructor
  {
    int sub;
    node* p = 0;
    node* prev_p;

    head = 0;
    for (sub = 0; sub < strlen(in_str); sub++)
      {
	prev_p = p;
	p = new node(in_str[sub], 0);
	if (sub == 0)
	  head = p;
        else
          prev_p -> link = p;
      }

  }

list::~list()                       // destructor
  {

    if (head != 0)                        // reset list to null
      reset();

  }

void list::reset()                       // reset list to null
  {
    node* p;
    node* p_next;

    if (head != 0)
      {
        p = head;
        while (p != 0)
          {
	    p_next = p -> link;     // get next link while it's still available
            delete p;
	    p = p_next;
          }
        cout << endl;
        head = 0;
      }
  }

list::list(const list& in_list)            // copy constructor
  {
    node* p;
    node* q;
    node* prev_q;

    head = 0;
    if (in_list.head != 0)
      {
	p = in_list.head;
	while (p != 0)
	  {
	    q = new node(*p);        // get new node, copy data members
	    q -> link = 0;           // ... zero out new link,
            if (head == 0)           // ... and make someone point to it
	      head = q;
            else
	      prev_q -> link = q;
	    p = p -> link;
	    prev_q = q;
	  }
      }
  }

list& list::operator=(const list& in_list)    // overloaded asgt op
  {
    node* p;
    node* q;
    node* prev_q;

    if (this != &in_list)                        // Make sure not same object
     {

       if (head != 0)                            // free old result
         reset();

       if (in_list.head != 0)
	 {
	   p = in_list.head;                     // create & fill new list
	   while (p != 0)
	     {
	       q = new node(*p);        // get new node, copy data members
	       q -> link = 0;           // ... zero out new link,
               if (head == 0)           // ... and make someone point to it
	         head = q;
               else
	         prev_q -> link = q;
	       p = p -> link;
	       prev_q = q;
	     }
	 }
     }
    return *this;                          // return ref for chained asgt
  }

ostream& operator<< (ostream& ostr, const list& in_list)
{
  node* p;

  p = in_list.head;
  if (p == 0)
    cout << "empty";
  while (p != 0)
    {
      ostr << *p;
      p = p -> link;
    }

  return ostr;
}

node::node()                        // default constructor
  {
    link = 0;
  }

node::node(char in_item, node* in_link)          // another constructor
  {
    item = in_item;
    link = in_link;
  }

ostream& operator<< (ostream& ostr, const node& in_node)
{
  ostr << in_node.item;

  return ostr;
}

bool list::add_recr(char new_item, char after)
{
// add 'new_item' to list after 'after':

// if list is empty, add new_item to list
// else
// call recursive helper fn

  node* new_node;
  bool ret;

  cout << "attempt to add " << new_item << " after " << after << endl;

  if (head == 0)
    {
      cout << "empty list, OK" << endl;
      new_node = new node;
      new_node -> item = new_item;
      new_node -> link = 0;
      head = new_node;
      return true;
    }
  else
    {
      ret = add_recr_helper(head, new_item, after);
      if (!ret)
	{
	  cout << after << " not found, nothing added" << endl;
	}
      return ret;
    }
}


bool add_recr_helper(node* current, char new_item, char after)
{
  // add 'new_item' to list after 'after' in sublist starting at current

  node* new_node;
  bool ret;

  if (current -> item == after)
    {
      new_node = new node;
      new_node -> item = new_item;
      new_node -> link = current -> link;
      current -> link = new_node;
      return true;
    }
  else if (current->link == 0)
    {
      return false;
    }
  else
    {
      ret = add_recr_helper(current->link, new_item, after);
      return ret;
    }

}


bool list::del_recr(char del_item)
{
// delete first instance of new_item from list:
// if list is empty or item is not found, return false

  bool ret;
  node* new_head;

  cout << "attempt to delete " << del_item << endl;

  if (head == 0)
    {
      cout << "empty list, can't delete" << endl;
      return false;
    }
  else if (head -> item == del_item)
    {
      cout << "deleting first item" << endl;
      new_head = head -> link;
      delete head;
      head = new_head;
      return true;
    }
  else
    {
      ret = del_recr_helper (head, del_item);
      if (!ret)
        {
          cout << del_item << " not found, nothing deleted" << endl;
        }
      return ret;
    }

}


bool del_recr_helper(node* prev, char del_item)
{
// delete first instance of new_item from sublist starting at prev->link:
// if sublist is empty or item is not found, return false

  bool ret;
  node* curr;

  curr = prev->link;

  if (curr == 0)
    {
      return false;
    }
  else if (curr->item == del_item)
    {
      cout << "deleting " << curr->item << endl;
      prev->link = curr->link;
      delete curr;
      return true;
    }
  else
    {
      ret = del_recr_helper (curr, del_item);
      return ret;
    }

}