//**************************************************************
//  CS 240B   : Winter 2003 Ohio University Travis Dillon
//  Project 5 : linked list
//  file      : list.cc
//  started   : 02-27-03
//
//**************************************************************

#include "list.h"
#include "node.h"
#include "prog5b.h"

List::List()
{
   first = NULL;
}

List::List(T dat_arr[], int size)
{
   first = NULL;
   for(int i(0); i < size; ++i)
   {
      Node temp;
      temp.data = dat_arr[i];
      push_back(temp);
   }
}

List::List(const List& orig)
{
   if(orig.first == NULL){first = NULL; return;}
   Node* iterr = orig.first;
   first = new Node(*iterr);
   Node* iterl = first;
   while(iterr -> fore != NULL)
   {
      iterr = iterr -> fore;
      iterl -> fore = new Node(*iterr);
      iterl = iterl -> fore;
   }
   iterl -> fore = NULL;
}

List::~List()
{
   strip();
}

List& List::operator =(const List& rop)
{
   if(this == &rop) return *this;  //self assignment
   strip();
   if(rop.first == NULL){first = NULL; return *this;}
   Node* iterr = rop.first;
   first = new Node(*iterr);
   Node* iterl = first;
   while(iterr -> fore != NULL)
   {
      iterr = iterr -> fore;
      iterl -> fore = new Node(*iterr);
      iterl = iterl -> fore;
   }
   iterl -> fore = NULL;
   return *this;
}

bool List::operator !=(const List& rop)const
{
   Node* iterl = first;
   Node* iterr = rop.first;
   if(iterr == NULL && iterl == NULL) return false;
   if(iterr == NULL || iterl == NULL) return true;
   while(iterl -> data == iterr -> data)
   {
      iterl = iterl -> fore;
      iterr = iterr -> fore;
      if(iterl == NULL && iterr == NULL) return false;
      if(iterl == NULL || iterr == NULL) return true;
   }
   return true;
}

bool List::operator ==(const List& rop)const
{
   return !(*this != rop);
}

ostream& operator <<(ostream& os, const Node& rop)
{
   os <<"\n data    fore\n";
   os <<setw(5) << rop.data << "    " << rop.fore;
   os <<endl;
   return os;
}

ostream& operator <<(ostream& os, const List& rop)
{
   os <<"\n\nList : ";
   if(rop.first == NULL){os <<"empty\n"; return os;}
   int cnt(0);
   for(Node* iter = rop.first; iter != NULL; iter = iter -> fore)
   {
      ++cnt;
      os << setw(7) << iter -> data;
      if(cnt % 10 == 0) os << endl << "       ";
   }
   os << endl;
   return os;
}

void List::tell_all(ostream& os, string name, int max_to_tell)
{
   os <<"\nlist name = " << name << endl;
   if(first == NULL){os <<"This list is empty.\n"; return;}
   os <<"       num      data   address      fore\n";
   int cnt(0);
   for(Node* iter = first; iter != NULL; iter = iter -> fore)
      os << endl << setw(10) << ++cnt << setw(10) << iter -> data
      << "  " << iter << "  " << iter -> fore  ;
   os << endl;
}
   
void List::push_back(const Node& in)
{
   if(first == NULL){push_front(in); return;}  //empty list
   Node* iter = first;
   while(iter -> fore != NULL) iter = iter -> fore;  //general
   iter -> fore = new Node(in);
   iter -> fore -> fore = NULL;
}

void List::push_front(const Node& in)
{
   if(first == NULL)  //empty list
   {
      first = new Node(in);
      first -> fore = NULL;
      return;
   }
   Node* save = first;  //general list
   first = new Node(in);
   first -> fore = save;
   return;
}

void List::push_before(int loc, const Node& in)
{
   //empty list or push in first location
   if(loc == 1 || first == NULL) {push_front(in); return;}
   Node* iter = first;
   int i(1);
   //general, insert at loc or at end if loc > number of nodes
   while(++i < loc && iter -> fore != NULL) iter = iter -> fore;
   Node* save = iter -> fore;
   iter -> fore = new Node(in);
   iter -> fore -> fore = save;
}

void List::push_in_order(const Node& in)
{
   if(first == NULL){push_front(in); return;}  //empty list
   if(in.data <= first -> data){push_front(in); return;}  //in front
   
   Node* iterr = first;
   Node* iterl = iterr;
   //general, check for data bigger than in.data
   while(iterr != NULL && iterr -> data < in.data)
   {
      iterl = iterr;
      iterr = iterr -> fore;
   }
   iterl -> fore = new Node(in);
   iterl -> fore -> fore = iterr;
   return;
}

void List::push_in_order(const T& in)
{
   Node in_node(in);  //first make a node
   if(first == NULL){push_front(in_node); return;}  //empty list
   if(in_node.data <= first -> data){push_front(in_node); return;}
   Node* iterr = first;
   Node* iterl = iterr;
   while(iterr != NULL && iterr -> data < in_node.data)
   {
      iterl = iterr;
      iterr = iterr -> fore;
   }
   iterl -> fore = new Node(in_node);
   iterl -> fore -> fore = iterr;
   return;
}

void List::steal(List& rl)
{
   *this += rl;  //append rl onto end of calling list, then empty rl
   rl.strip();
}

void List::operator +=(const List& rl)
{  //append rl onto end of calling list, leave rl alone
   if(rl.first == NULL) return;
   if(first == NULL) {*this = rl; return;}
   
   Node* iter;
   for(iter = first; iter -> fore != NULL; iter = iter -> fore);
   
   Node* temp = rl.first;
   while(temp -> fore != NULL)
   {
      iter -> fore = new Node(*temp);
      temp = temp -> fore;
      iter = iter -> fore;
   }
   iter -> fore = new Node(*temp);
   iter -> fore -> fore = NULL;
}

Node* List::get_back()
{  //return pointer to the end node in the list
   Node* iter;
   if(first == NULL) return NULL;
   for(iter = first; iter -> fore != NULL; iter = iter -> fore);
   return iter;
}

Node* List::get_front()
{  //return pointer to first node in the list
   if(first == NULL) return NULL;
   return first;
}

Node* List::get_at(int n)
{  //return pointer of node at position n
   if(first == NULL) return NULL;
   Node* iter;
   int counter(0);
   for(iter = first; iter -> fore != NULL; iter = iter -> fore)
   {
      if(++counter == n) return iter;
   }
   return iter;
}

void List::pop_back()
{  //delete last node in list
   if(first == NULL) {cout <<"\nEmpty List\n"; return;}
   if(first -> fore == NULL)
   {
      delete first;
      first = NULL;
      return;
   }
   Node* iterr;
   Node* iterl;
   for(iterr = first; iterr -> fore != NULL; iterr = iterr -> fore)
   {
      iterl = iterr;
   }
   delete iterr;
   iterl -> fore = NULL;
}

void List::pop_front()
{  //delete first node in list
   if(first == NULL) {cout <<"\nEmpty List\n"; return;}
   Node* iter = first;
   first = iter -> fore;
   delete iter;
}

void List::pop_at(int n)
{  //delete node in position n
   if(first == NULL) {cout <<"\nEmpty List\n"; return;}
   if(first -> fore == NULL || n == 1) {pop_front(); return;}
   int counter(1);
   Node* iter = first;
   Node* follow;
   while(iter -> fore != NULL && counter++ < n)
   {
      follow = iter;
      iter = iter -> fore;
   }
   follow -> fore = iter -> fore;
   delete iter;
}

void List::strip()
{  //delete all nodes in list
   Node* iter1 = first;
   Node* iter2;
   while(iter1 != NULL)
   {
      iter2 = iter1;
      iter1 = iter1 -> fore;
      delete iter2;
   }
   first = NULL;
}

bool List::is_empty()
{
   return (first == NULL);
}

bool List::is_sorted()
{
   if(first == NULL) return true;
   if(first -> fore == NULL) return true;
   Node* iter = first;
   while(iter -> data <= iter -> fore -> data)
   {
      iter = iter -> fore;
      if(iter -> fore == NULL) return true;
   }
   return false;
}

int List::count()
{
   if(first == NULL) return 0;
   int counter(1);
   for(Node* iter = first; iter -> fore != NULL; iter = iter -> fore)
      counter++;
   return counter;
}

Node* List::search(T tar)
{
   Node* iter = first;
   while(iter != NULL)
   {
      if(iter -> data == tar) return iter;
      iter = iter -> fore;
   }
   return NULL;
}

Node* List::find_min()
{
   if(first == NULL) return NULL;
   if(first -> fore == NULL) return first;
   Node* iter = first;
   Node* smallest = iter;
   for(; iter != NULL; iter = iter -> fore)   
   {
      if(iter -> data < smallest -> data)      
         smallest = iter;
      if(iter -> fore  == NULL) return smallest;
   }
   return smallest;   
}

void List::generic_sort()
{  //my generic sort function
   if(first == NULL || first -> fore == NULL) return;
   List temp;
   int num_nodes = count();
   int cnt(1);
   Node* min_node;
   Node* iter;
   for(int i(0); i < num_nodes; ++i)
   {      
      min_node = find_min();      
      temp.push_back(*min_node);
      for(iter = first; iter != min_node; iter = iter -> fore) ++cnt;
      pop_at(cnt);
      cnt = 1;
   }
   *this += temp;   
}

void List::selection_sort()
{
   if(first == NULL) return;
   if(first -> fore == NULL) return;
   Node* holder = find_min();
   Node* min;
   Node* before;
   Node* follow = holder;
   while(first -> fore != NULL)
   {
      min = find_min();
      if(first == min)
      {
         first = first -> fore;
      }      
      else
      {
         for(before = first; before -> fore != min; before = before -> fore);
         before -> fore = min -> fore;
         min -> fore = first;
      }
      follow -> fore = min;
      follow = min;
   }
   first = holder;
}

void sorted_merge(List& out, List& in1, List& in2)
{
   Node* iter1 = in1.first;
   Node* iter2 = in2.first;
   Node* iter3 = out.first;
   out.strip();
   //put in1 and in2 together in order into out
   if(iter1 != NULL && iter2 != NULL)
   {
      if(iter1 -> data < iter2 -> data)
      {
         out.first = new Node(*iter1);
         iter1 = iter1 -> fore;
      }
      else
      {
         out.first = new Node(*iter2);
         iter2 = iter2 -> fore;
      }
   }
   else if(iter1 != NULL)
   {
      out.first = new Node (*iter1);
      iter1 = iter1 -> fore;
   }
   else  //if(iter2 != NULL)
   {
      out.first = new Node (*iter2);
      iter2 = iter2 -> fore;
   }
   iter3 = out.first;
   while(iter1 != NULL || iter2 != NULL)
   {
      if(iter1 != NULL && iter2 != NULL)
      {
         if(iter1 -> data < iter2 -> data)
         {
            iter3 -> fore = new Node (*iter1);
            iter3 = iter3 -> fore;
            iter1 = iter1 -> fore;
         }
         else
         {
            iter3 -> fore = new Node (*iter2);
            iter3 = iter3 -> fore;
            iter2 = iter2 -> fore;
         }
      }
      else if(iter1 != NULL)
      {
         iter3 -> fore = new Node (*iter1);
         iter3 = iter3 -> fore;
         iter1 = iter1 -> fore;
      }
      else  //if(iter2 != NULL)
      {
         iter3 -> fore = new Node (*iter2);
         iter3 = iter3 -> fore;
         iter2 = iter2 -> fore;
      }
   }
   iter3 -> fore = NULL;
}