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

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

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

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

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

// POST: a node with the given key is inserted into *this and the elements of *this are sorted.
void SortedDLList::insert(int key)
{
	// Your code goes here...
}

const DLNode* SortedDLList::find(int key) 
{
	for (DLNode* p = head_; p != 0; p = p->get_next())
		if (p->get_key() == key)
			return p;
	return 0;
} 

// PRE: *n is in *this
// POST: *n is not in *this and all the other elements that were originaly present still are in *this
void SortedDLList::remove(const DLNode* n) 
{
	// Your code goes here...
}

// POST: *this is merged with l
void SortedDLList::merge(const SortedDLList& l)
{
	// Your code goes here...
}

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

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


const DLNode* SortedDLList::get_head() const
{
  return head_;
}

	
// POST: *this is written to std::cout
std::ostream& operator<< (std::ostream& o, const SortedDLList& l) {
  const DLNode* p = l.get_head();
  while (p != 0) {
    o << p->get_key() << " ";
    p = p->get_next();
  }
  return o;
}