#include <iostream>
#include "List.h"
#include <cassert>
#include <set>

// default Constructor
List::List() 
  : head_(0) 
{}

// destructor
List::~List() 
{
  clear();
}

// clear
void List::clear ()
{
  Node* p = head_;
  while (p != 0) {
    p = p->get_next();
    delete head_;
    head_ = p;
  }
  head_ = 0;
}

// copy constructor
List::List (const List& l) 
  : head_ (0)
{
  copy (l.head_);
}

// private copy method
void List::copy (const Node* from) 
{
  assert (head_ == 0);
  if (from != 0) {
    // copy first element to head
    head_ = new Node (from->get_key());
    Node* p = from->get_next();
    Node* q = head_;
    // copy remaining elements
    while (p != 0) {
      q->set_next (new Node (p->get_key()));
      p = p->get_next();
      q = q->get_next();
    }
  }
}

// assignment operator
List& List::operator= (const List& l) 
{
  if (head_ != l.head_) { //check for self-assignment
    clear();
    copy (l.head_);
  }
  return *this;
}

// push_front
void List::push_front (int key) 
{
  head_ = new Node (key, head_);
}

// push_back
void List::push_back (int key) 
{
  if (head_ == 0)
    head_ = new Node (key);
  else {
    Node* p = head_;
    while (p->get_next() != 0) 
      p = p->get_next();
    p->set_next (new Node (key));
  }		 
}

// removed
void List::remove (int key) 
{
  if (head_ != 0) {
    Node* p = head_;
    if (p->get_key() == key) {
      head_ = head_->get_next();
      delete p;
    } else 
      while (p->get_next() != 0) {
	Node* q = p->get_next();
	if (q->get_key() == key) {
	  p->set_next(q->get_next());
	  delete q;
	  break;
	} else
	  p = q;
      }
  }
}

const Node* List::get_head() const
{
  return head_;
}

// Append a compy of l
void List::append(const List& l) 
{
	List* temp = new List(l);
	if (head_  == 0)
		head_ = temp->head_;
	else {
		Node* p = head_;
		while (p->get_next() != 0)
			p = p->get_next();
		p->set_next(temp->head_);
	}
}

// Appending by ponting the last elemnt of this via next to head of l - leads to aliasing (should not be part of the interface - just for exercises)
void List::append(const List* l) {
	if (head_  == 0)
		head_ = l->head_;
	else {
		Node* p = head_;
		while (p->get_next() != 0)
			p = p->get_next();
		p->set_next(l->head_);
	}
}

// Iterative version of getting size of the list
int List::size() const
{
	int result = 0;
	for (Node* p = head_; p != 0; p = p->get_next()) 
		result++;
	return result;
}

// Removes duplicates from *this
void List::unique()
{
   std::set<int> seen;
   Node* p = head_;
		Node* q = head_;
   while (p != 0) {
     if (seen.count(p->get_key())) {
       q->set_next(p->get_next());
       delete p;
       p = q->get_next();      	  		
     }
     else {
       seen.insert(p->get_key());
       q = p;
       p = p->get_next();
     }
   }	
}

// POST: The elements of *this are in reversed order
void List::reverse() 
{
	// Your code goes here...
}
	
// POST: *this is written to std::cout
std::ostream& operator<< (std::ostream& o, const List& l) {
  const Node* p = l.get_head();
  while (p != 0) {
    o << p->get_key() << " ";
    p = p->get_next();
  }
  return o;
}