c206.c

	
/* c206.c **********************************************************}
{* Téma: Dvousměrně vázaný lineární seznam
**
**                   Návrh a referenční implementace: Bohuslav Křena, říjen 2001
**                            Přepracované do jazyka C: Martin Tuček, říjen 2004
**                                             Úpravy: Bohuslav Křena, říjen 2013
**
** Implementujte abstraktní datový typ dvousměrně vázaný lineární seznam.
** Užitečným obsahem prvku seznamu je hodnota typu int.
** Seznam bude jako datová abstrakce reprezentován proměnnou
** typu tDLList (DL znamená Double-Linked a slouží pro odlišení
** jmen konstant, typů a funkcí od jmen u jednosměrně vázaného lineárního
** seznamu). Definici konstant a typů naleznete v hlavičkovém souboru c206.h.
**
** Vaším úkolem je implementovat následující operace, které spolu
** s výše uvedenou datovou částí abstrakce tvoří abstraktní datový typ
** obousměrně vázaný lineární seznam:
**
**      DLInitList ...... inicializace seznamu před prvním použitím,
**      DLDisposeList ... zrušení všech prvků seznamu,
**      DLInsertFirst ... vložení prvku na začátek seznamu,
**      DLInsertLast .... vložení prvku na konec seznamu, 
**      DLFirst ......... nastavení aktivity na první prvek,
**      DLLast .......... nastavení aktivity na poslední prvek, 
**      DLCopyFirst ..... vrací hodnotu prvního prvku,
**      DLCopyLast ...... vrací hodnotu posledního prvku, 
**      DLDeleteFirst ... zruší první prvek seznamu,
**      DLDeleteLast .... zruší poslední prvek seznamu, 
**      DLPostDelete .... ruší prvek za aktivním prvkem,
**      DLPreDelete ..... ruší prvek před aktivním prvkem, 
**      DLPostInsert .... vloží nový prvek za aktivní prvek seznamu,
**      DLPreInsert ..... vloží nový prvek před aktivní prvek seznamu,
**      DLCopy .......... vrací hodnotu aktivního prvku,
**      DLActualize ..... přepíše obsah aktivního prvku novou hodnotou,
**      DLSucc .......... posune aktivitu na další prvek seznamu,
**      DLPred .......... posune aktivitu na předchozí prvek seznamu, 
**      DLActive ........ zjišťuje aktivitu seznamu.
**
** Při implementaci jednotlivých funkcí nevolejte žádnou z funkcí
** implementovaných v rámci tohoto příkladu, není-li u funkce
** explicitně uvedeno něco jiného.
**
** Nemusíte ošetřovat situaci, kdy místo legálního ukazatele na seznam 
** předá někdo jako parametr hodnotu NULL.
**
** Svou implementaci vhodně komentujte!
**
** Terminologická poznámka: Jazyk C nepoužívá pojem procedura.
** Proto zde používáme pojem funkce i pro operace, které by byly
** v algoritmickém jazyce Pascalovského typu implemenovány jako
** procedury (v jazyce C procedurám odpovídají funkce vracející typ void).
**/

#include "c206.h"

int solved;
int errflg;

void DLError() {
/*
** Vytiskne upozornění na to, že došlo k chybě.
** Tato funkce bude volána z některých dále implementovaných operací.
**/	
    printf ("*ERROR* This program has performed an illegal operation.\n");
    errflg = TRUE;             /* globální proměnná -- příznak ošetření chyby */
    return;
}

void DLInitList (tDLList *L)	{
/*
** Provede inicializaci seznamu L před jeho prvním použitím (tzn. žádná
** z následujících funkcí nebude volána nad neinicializovaným seznamem).
** Tato inicializace se nikdy nebude provádět nad již inicializovaným
** seznamem, a proto tuto možnost neošetřujte. Vždy předpokládejte,
** že neinicializované proměnné mají nedefinovanou hodnotu.
**/
   L->First = NULL;	//Inicializacia zoznamu.Jedna sa o prazdny zoznam,takze vsetky ukazatele budu NULL
   L->Act = NULL;
   L->Last = NULL; 
}

void DLDisposeList (tDLList *L)	{
/*
** Zruší všechny prvky seznamu L a uvede seznam do stavu, v jakém
** se nacházel po inicializaci. Rušené prvky seznamu budou korektně
** uvolněny voláním operace free. 
**/
	tDLElemPtr PomUk = NULL;  //Vytvorenie pomocneho ukazatela, na zaciatku bude NULL
	while (L->First != NULL) //Rus postupne prvky , az pokial nebude prvy NULL
		{
			PomUk = L->First; //Zaciatok si ulozime do pomocneho ukazatela
			L->First = L->First->rptr; //nasledujuci prvok (od prveho) sa premiestni do prveho
						
			free(PomUk); //zrusi sa v podstate prvy prvok..a takto v cykle postupne
		}
	L->Last = NULL;
	L->Act = NULL;	
	
 
}

void DLInsertFirst (tDLList *L, int val)	{
/*
** Vloží nový prvek na začátek seznamu L.
** V případě, že není dostatek paměti pro nový prvek při operaci malloc,
** volá funkci DLError().
**/
	tDLElemPtr PomUk = NULL;  //Vytvorenie pomocneho ukazatela, na zaciatku bude NULL
	PomUk = (tDLElemPtr)malloc(sizeof(struct tDLElem));	

	if(PomUk == NULL) //Ak sa alokacia nepodari, zavolaj danu funkciu
	{
		DLError();
		return;
	}

	PomUk->data = val; //parameter val bude priradeny do data
	PomUk->lptr = NULL; //Predchadzajuci prvok neexistuje, pretoze tato funkcia vklada prvy prvok
	PomUk->rptr = L->First; //Nasledujuci prvok je vlastne prvym alebo NULL

	if(L->First != NULL) //Ak prvy prvok nieje NULL - to znamena ze sa nejedna o prazdny zoznam
		L->First->lptr = PomUk;
	else				//Ak sa jedna o prazdny zoznam , tak prvy a posledny prvok su rovnake
		L->Last = PomUk; 

		L->First = PomUk; //Prvemu prvku priradim hodnotu ktora ma byt na prvom mieste v zozname
	
}

void DLInsertLast(tDLList *L, int val)	{
/*
** Vloží nový prvek na konec seznamu L (symetrická operace k DLInsertFirst).
** V případě, že není dostatek paměti pro nový prvek při operaci malloc,
** volá funkci DLError().
**/ 	
	tDLElemPtr PomUk = NULL;  //Vytvorenie pomocneho ukazatela, na zaciatku bude NULL
	PomUk = (tDLElemPtr)malloc(sizeof(struct tDLElem));	

	if(PomUk == NULL) //Ak sa alokacia nepodari, zavolaj danu funkciu
	{
		DLError();
		return;
	}

	PomUk->data = val; //parameter val bude priradeny do data
	PomUk->lptr = L->Last; //Predchadzajuci prvok 
	PomUk->rptr = NULL; //Nasledujuci prvok neexistuje, lebo vkladame posledny prvok.

	if((L->First != NULL) && (L->Last != NULL)) //Ak prvy a posledny prvok nieje NULL - to znamena ze sa nejedna o prazdny zoznam
		L->Last->rptr = PomUk;
	else
		L->First = PomUk; //ak sa jedna o prazdny zoznam, posledny bude prvy

		L->Last = PomUk; //poslednemu prvku priradim hodnotu ktora ma byt na poslednom mieste v zozname
}



void DLFirst (tDLList *L)	{
/*
** Nastaví aktivitu na první prvek seznamu L.
** Funkci implementujte jako jediný příkaz (nepočítáme-li return),
** aniž byste testovali, zda je seznam L prázdný.
**/
	
	L->Act = L->First;
}

void DLLast (tDLList *L)	{
/*
** Nastaví aktivitu na poslední prvek seznamu L.
** Funkci implementujte jako jediný příkaz (nepočítáme-li return),
** aniž byste testovali, zda je seznam L prázdný.
**/
	
	L->Act = L->Last;
}

void DLCopyFirst (tDLList *L, int *val)	{
/*
** Prostřednictvím parametru val vrátí hodnotu prvního prvku seznamu L.
** Pokud je seznam L prázdný, volá funkci DLError().
**/

	if(L->First == NULL) 	
	{
		DLError();
		return;
	}

	*val = L->First->data; //Do parametru val prirad hodnotu ktora sa nachadza v prvom prvku 
 
}

void DLCopyLast (tDLList *L, int *val)	{
/*
** Prostřednictvím parametru val vrátí hodnotu posledního prvku seznamu L.
** Pokud je seznam L prázdný, volá funkci DLError().
**/

	if(L->First == NULL)	
	{	
		DLError();
		return;
	}
	*val = L->Last->data; //Symetricka funkcia s predchadzajucou, ibaze kopiruje poslednu prvok

}

void DLDeleteFirst (tDLList *L)	{
/*
** Zruší první prvek seznamu L. Pokud byl první prvek aktivní, aktivita 
** se ztrácí. Pokud byl seznam L prázdný, nic se neděje.
**/
	tDLElemPtr PomUk = NULL;  //Vytvorenie pomocneho ukazatela, na zaciatku bude NULL
	
	if(L->First == NULL)	
	{	
		free(PomUk);
		return;
	}

	if(L->Act == L->First)	  //Ak je prvy aktivnym, nastav ukazatel aktivneho na NULL...teda zrus aktivitu
		L->Act = NULL;

	if(L->First == L->Last) //Ak je prvy zaroven poslednym, vynuluj posledny
		L->Last = NULL; 

	PomUk = L->First->rptr; //Ulozim si hodnotu dalsieho prvku do pomocneho ukazatela, vzapati sa z neho stane prvy prvok
	free(L->First);	//Prvy zrusime

	L->First = PomUk; //Ulozili sme si hodnotu Dalsieho prvku do pomocneho ukazatela , teraz sa z neho stane prvy prvok v zozname
	if(L->First != NULL)
		L->First->lptr = NULL; //Lavy vynulujeme, aby bol prvy naozaj prvym a nic nalavo 
}	

void DLDeleteLast (tDLList *L)	{
/*
** Zruší poslední prvek seznamu L. Pokud byl poslední prvek aktivní,
** aktivita seznamu se ztrácí. Pokud byl seznam L prázdný, nic se neděje.
**/ 
	tDLElemPtr PomUk = NULL;  //Vytvorenie pomocneho ukazatela, na zaciatku bude NULL
	

	if (L->First == NULL)
	{
		free(PomUk);
		return;
	}

	PomUk=L->Last;
	
	if(L->Last == L->Act)	  //Ak je posledny aktivnym, nastav ukazatel aktivneho na NULL...teda zrus aktivitu
		L->Act = NULL;

	if(L->First == L->Last)
	{
		L->First = NULL; 
		L->Last = NULL;
	}
	else
	{
	L->Last = L->Last->lptr; //Ulozim si hodnotu predosleho prvku do pomocneho ukazatela, vzapati sa z neho stane prvy prvok
	
	L->Last->rptr = NULL;
	}
	free(PomUk);
}

void DLPostDelete (tDLList *L)	{
/*
** Zruší prvek seznamu L za aktivním prvkem.
** Pokud je seznam L neaktivní nebo pokud je aktivní prvek
** posledním prvkem seznamu, nic se neděje.
**/
	tDLElemPtr PomUk = NULL;

	if((L->Act == NULL) || (L->Act == L->Last))	//Presne podla zadania (neaktivita ....) -> zrus ukazatel, a nic nerob 
 		{
 			free(PomUk);
 			return ;
 		}

 	PomUk = L->Act->rptr; //ukazatel na prvok ktory sa nachadza napravo od aktivneho
 	
 	if(PomUk->rptr != NULL) //Moze byt nasledujuci nulovy alebo nie ....a na zaver zrus pomocny ukazatel
 		{
 			L->Act->rptr = PomUk->rptr;
 			PomUk->rptr->lptr = L->Act;
 		}
 	else
 		{
 			L->Act->rptr=NULL;
 			L->Last = L->Act;
 		}
 			free(PomUk);
}

void DLPreDelete (tDLList *L)	{
/*
** Zruší prvek před aktivním prvkem seznamu L .
** Pokud je seznam L neaktivní nebo pokud je aktivní prvek
** prvním prvkem seznamu, nic se neděje.
**/
	
	tDLElemPtr PomUk = NULL;
	
	if((L->Act == NULL) || (L->Act == L->First))	//Presne podla zadania (neaktivita ....) -> zrus ukazatel, a nic nerob	
 		{
 			free(PomUk);
 			return ;
 		}

 	PomUk = L->Act->lptr;  //ukazatel na prvok ktory sa nachadza nalavo od aktivneho

 	if(PomUk->lptr != NULL) //Moze byt predosly nulovy alebo nie ....a na zaver zrus pomocny ukazatel
 		{
 			L->Act->lptr = PomUk->lptr;
 			PomUk->lptr->rptr = L->Act;
 		}
 	else
 		{
 			L->Act->lptr=NULL;
 			L->First = L->Act;
 		}
 			free(PomUk);
}

void DLPostInsert (tDLList *L, int val) {
/*
** Vloží prvek za aktivní prvek seznamu L.
** Pokud nebyl seznam L aktivní, nic se neděje.
** V případě, že není dostatek paměti pro nový prvek při operaci malloc,
** volá funkci DLError().
**/
	
	tDLElemPtr PomUk = NULL;  //Vytvorenie pomocneho ukazatela, na zaciatku bude NULL
	PomUk = (tDLElemPtr)malloc(sizeof(struct tDLElem));	

	if(PomUk == NULL) //Ak sa alokacia nepodari, zavolaj danu funkciu
	{	
		DLError();
	}

	if(L->Act == NULL) //Ak je neaktivny nic sa nedeje
		return;

	if(L->Act->rptr == NULL) //Ak je napravo od aktivneho nulovy, tak sa z pomocneho ukazatela do posledneho vlozi prvok
		L->Last =PomUk;
	else
		L->Act->rptr->lptr = PomUk; 

	PomUk->rptr = L->Act->rptr;	//ukazatele na dalsi a predchadzajuci
	PomUk->lptr = L->Act;
	L->Act->rptr = PomUk;

	PomUk->data = val; //VLozime prvok do miesta kam ukazuje pomocny ukazatel
	
}

void DLPreInsert (tDLList *L, int val)		{
/*
** Vloží prvek před aktivní prvek seznamu L.
** Pokud nebyl seznam L aktivní, nic se neděje.
** V případě, že není dostatek paměti pro nový prvek při operaci malloc,
** volá funkci DLError().
**/
	
	tDLElemPtr PomUk = NULL;  //Vytvorenie pomocneho ukazatela, na zaciatku bude NULL
	PomUk = (tDLElemPtr)malloc(sizeof(struct tDLElem));	

	if(PomUk == NULL) //Ak sa alokacia nepodari, zavolaj danu funkciu
	{
		DLError();
		return;
	}

	if(L->Act == NULL)	//Ak je neaktivny nic sa nedeje
		return;

	if(L->Act->lptr == NULL)	//Ak je naplavo od aktivneho nulovy, tak sa z pomocneho ukazatela do prveho vlozi prvok
		L->First = PomUk;

	else
		L->Act->lptr->rptr = PomUk;

	PomUk->lptr = L->Act->lptr; //ukazatele na predchadzajuci a dalsi
	PomUk->rptr = L->Act;
	L->Act->lptr = PomUk;

	PomUk->data = val;  //Vlozime prvok do miesta kam ukazuje pomocny ukazatel
}

void DLCopy (tDLList *L, int *val)	{
/*
** Prostřednictvím parametru val vrátí hodnotu aktivního prvku seznamu L.
** Pokud seznam L není aktivní, volá funkci DLError ().
**/
		
	if (L->Act == NULL) //Ak je zoznam neaktivny nic nerob resp. zavolaj iba funkciu ktora to oznami
	{
		DLError();
		return;
	}
	*val = L->Act->data;	//inak prirad do parametru val hodnotu z aktivneho prvku
	
 
}

void DLActualize (tDLList *L, int val) {
/*
** Přepíše obsah aktivního prvku seznamu L.
** Pokud seznam L není aktivní, nedělá nic.
**/
	
	if(L->Act == NULL) //Nic nerob ak je zoznam aktivny...inak prirad do aktivneho hodnotu z parametru val
		return;
	L->Act->data = val;
 
}

void DLSucc (tDLList *L)	{
/*
** Posune aktivitu na následující prvek seznamu L.
** Není-li seznam aktivní, nedělá nic.
** Všimněte si, že při aktivitě na posledním prvku se seznam stane neaktivním.
**/
	if (L->Act == NULL) 	//Nic nerob ak nieje zoznam aktivny
		return;

	if (L->Act == L->Last) //zrus aktivitu ak je posledny aktivny
	{
      L->Act = NULL;
      return;
  	}
  	L->Act = L->Act->rptr;
 }



void DLPred (tDLList *L)	{
/*
** Posune aktivitu na předchozí prvek seznamu L.
** Není-li seznam aktivní, nedělá nic.
** Všimněte si, že při aktivitě na prvním prvku se seznam stane neaktivním.
**/
	if(L->Act == NULL) //Nic nerob ak nieje zoznam aktivny
		return;

	if (L->Act == L->First) //zrus aktivitu ak je prvy aktivny
	{
      L->Act = NULL;
      return;
  	}
	L->Act = L->Act->lptr;

}

int DLActive (tDLList *L) {		
/*
** Je-li seznam aktivní, vrací true. V opačném případě vrací false.
** Funkci implementujte jako jediný příkaz.
**/
	
	return (L->Act != NULL) ? 1 : 0;	// 1 predstavuje TRUE, 0 predstavuje FALSE
 
}

/* Konec c206.c*/