#ifndef SORTED_DLLLIST_H_
#define SORTED_DLLLIST_H_

#include <ostream>
#include "DLNode.h"

class SortedDLList{
public:
	// default constructor: 
        // POST: *this is an empty list
        SortedDLList();  

        // destructor
	~SortedDLList();

	// copy constructor
	SortedDLList (const SortedDLList& l);

	// assignment operator
	SortedDLList& operator= (const SortedDLList& l); 

	// POST: a node with the given key is inserted into *this and the elements of *this are sorted.
	void insert(int key);
	
	// 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 remove(const DLNode* n);
	
	// POST: *this is merged with l
	void merge(const SortedDLList& l);

	// POST: returns const pointer to the first node
	const DLNode* get_head() const;

	// POST: the list was emptied
	void clear();
	
	// POST: return a constant pointer to the firs node with the given key, NULL othwerwise
	const DLNode* find(int key);
	
private:
	DLNode* head_;
	
	// PRE: *this is empty
	// POST: list starting at from was copied to *this
	void copy (const DLNode* from);
};

// output operator
std::ostream& operator<< (std::ostream& o, const SortedDLList& l);

#endif