#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;

struct prvek {
		int key;
		string value;
		prvek * prev;
		prvek * next;
	};

struct seznam {
		prvek * first;
		prvek * last;
	};

void init (seznam & d) {
	d.first = nullptr;
	d.last = nullptr;
}

void link (seznam & d, 
		   prvek * a, prvek * b, prvek * c)
{
	b->prev=a;
	if(a!=nullptr) a->next=b;
	else d.first=b;
	b->next=c;
	if(c!=nullptr) c->prev=b;
	else d.last=b;
}


void pridejPrvekKonec (seznam &d, int k, string v){
	prvek * p = new prvek;
	p->key = k;
	p->value = v;
	p->prev = nullptr;
	p->next = nullptr;

	link (d, d.last, p, nullptr);
}

void vloz (seznam &d, int k, string v){
	prvek *p = new prvek;
	p->key = k;
	p->value = v;

	prvek *h = d.first;
	while ( h!=0 && h->key <= p->key)
		h = h->next;

	// link (d, h!=0 ? h->prev : d.last, p, h);

	if (h != 0 )
	   link (d, h->prev, p, h);
	else
	   link (d, d.last, p, h);
}

void odstran (seznam &d, int k){
	prvek* p= d.first;
	bool stop = false;
	while (p != NULL && p->key !=  k && ! stop)
	{
		if (p->key > k) stop = true;
        p = p->next;
	}
	if (p!= NULL && ! stop)
	{
	 if(p->prev != NULL)
	    p->prev->next = p->next;
	 else 
		d.first = p->next;
	 if(p->next != NULL)
	    p->next->prev = p->prev;
	 else
		 d.last = p->prev;
	 delete p;
	}

}

prvek* find (seznam &d, int k){
	prvek* p = d.first;
	while(p!=nullptr && p->key != k)
        p=p->next;
	return p;
}

void vypis(seznam &d){
	prvek* p;
	p=d.first;
	while(p!=nullptr){
		cout << p->value << " " << p->key << endl;
		p=p->next;
	}}


#if 0

void pridejPrvekZacatek(seznam &d,int k, string v){
	prvek* p = new prvek;
	p->key=k;
	p->value=v;
	p->next=nullptr;

	if (d.first!=nullptr)
		p->next =d.first;
	else 
		d.last =p;

	d.first = p;
}

void hledej(seznam &d, int k){
	prvek* p;
	p=d.first;
	while(p!=nullptr){
		if(p->key == k)
			cout << p->value << " " << p->key << endl;
		p=p->next;
	}
}

prvek* find(seznam &d, int k){
	prvek* p;
	p=d.first;
	while(p!=nullptr){
		if(p->key == k)
			return p;
		p=p->next;
	}
	return NULL;
}

prvek* find2 (seznam &d, int k){
	prvek* p;
	p=d.first;
	bool stop = false;
	while(p!=nullptr && ! stop){
		if(p->key == k)
			stop = true;
		else 
		   p=p->next;
	}
	return p;
}
prvek* find3 (seznam &d, int k){
	prvek * answer = nullptr;
	prvek* p = d.first;
	while(p!=nullptr && answer == nullptr){
		if(p->key == k)
			answer = p;
        p=p->next;
	}
	return answer;
}


prvek* find5 (seznam &d, int k){
	prvek* p = d.first;
	while( p->key != k && p != nullptr) // SPATNE
        p=p->next;
	return p;
}

#endif

seznam s;

int _tmain (int argc, _TCHAR* argv[])
{
	init (s);
	vloz (s, 2, "m");
	vloz (s, 5, "k");
	vloz (s, 1, "a");
	odstran (s, 2);
	odstran (s, 1);
	vypis(s);
	cout << "Hotovo" << endl;
	system ("pause");

	return 0;
}