#include <iostream>

class Elem {
private:
	int v;
	Elem* next_elem;
	Elem* prev_elem;

public:
	Elem() {		//tworzy pusty element
	}
	Elem(int x) {				//tworzy element przechowujący x
		v = x;
	}
	int value(){
		return v;
	}
	void setValue(int v) {		//ustawia warość v
		this->v = v;
	}
	Elem* next() {				//zwraca następny element
		return next_elem;
	}
	Elem* prev() {				//zwraca poprzednielement
		return prev_elem;
	}
	void setNext(Elem* p) {		//ustawia p jako następny element
		next_elem = p;
	}
	void setPrev(Elem* p) {		//ustawia p jako poprzedni element
		prev_elem = p;
	}
};

class SortedDLList {
private:
	Elem* head;			//wskaźnik na pierwszy element list
	Elem* tail;			//wskaźnik na ostatni element list
	int list_size;			//długość listy

public:
	SortedDLList(){
		head = tail = nullptr;
		list_size = 0;
	}
	bool empty() {
		return (list_size == 0);
	}
	int size() {
		return list_size;
	}
	Elem* first() {  			//zwraca pozycję pierwszego elementu
		return head;
	}
	Elem* last() {			//zwraca pozycję ostatniego elementu
		return tail;
	}
	Elem* next(Elem * p) {				//zwraca pozycję elementu następnego za p
		return p->next();
	}
	Elem* prev(Elem* p) {		//zwraca pozycję elementu poprzedniego przed p
		return p->prev();
	}
	int retrieve(Elem* p) {		//zwraca relement z pozycji p
		return p->value();
	}
	Elem* locate(int x) {		//zwraca pozycję pierwszego wystąpienia elementu x, -1 jeśli x nie występuje
		Elem* actual = head;
		while (actual != tail) {
			if (actual->value() == x)
				return actual;
			actual = actual->next();
		}
		return nullptr;
	}
	void insert(int x) {			//wstawia x z zachowniem porządku
		Elem* newEl = new Elem(x);
		if (head == tail && list_size==0) {
			head = newEl;
			tail = newEl;
		}
		else if (head == tail && list_size != 0) {
			if (x > head->value()) {
				tail = newEl;
				tail->setPrev(head);
				head->setNext(newEl);
			}
			else {
				head = newEl;
				head->setNext(tail);
				tail->setPrev(head);
			}
		}
		else if (x < head->value()) {
			newEl->setNext(head);
			newEl->setPrev(nullptr);
			head->setPrev(newEl);
			head = newEl;
		}
		else if (x > tail->value()) {
			newEl->setNext(nullptr);
			newEl->setPrev(tail);
			tail->setNext(newEl);
			tail = newEl;
		}
		else {

		}
		list_size++;
	}
	void del(int x) {		//usuwa pierwsze wystąpienie element x
		Elem* pos = locate(x);
		if (pos==head){
			head = pos->next();
		}
		else if (pos == tail) {
			tail = pos->prev();
		}
		else {
			Elem* posnext = pos->next();
			while (posnext != tail) {
				pos->setPrev(posnext->prev());
				pos->setNext(posnext->next());
				pos->setNext(posnext->next());
				pos->setValue(posnext->value());
				posnext = pos->next();
			}
		}
	}
	void clear() {  //usuwa całą listę
		Elem* current = head;
		Elem* next;

		while (current != nullptr)
		{
			next = current->next();
			free(current);
			current = next;
			list_size--;
		}

		head = NULL;
	}
	friend std::ostream& operator<<(std::ostream& out, SortedDLList& l){		 //wypisuje elementu listy
			Elem* current = l.first();
		do{
			out << current->value() << "\t";
			current = current->next();
		  }
		while (current != l.last());
		  out << l.last()->value();
		return out;
	}
};

int main(){
	SortedDLList *DLlist = new SortedDLList();
	DLlist->insert(5);
	DLlist->insert(4);
	DLlist->insert(10);
	DLlist->insert(8);
	//std::cout << DLlist->last()->value();
	//std::cout << DLlist->first()->value();
	std::cout << *DLlist;
	//DLlist->clear();
	//std::cout << *DLlist;
}