/* ------------------------------- c403.c ----------------------------------- */
/* Téma: Vyhledávací tabulka v neseřazeném poli se zarážkou (optimalizace)
**       První implementace: Petr Přikryl, prosinec 1994
**       Úpravy: Petr Přikryl, listopad 1997, květen 1998
**       Další úprava: Martin Tuček, srpen 2005 (jazyk C)
**       Další úprava: Roman Lukáš, říjen 2006
**
** Implementujte vyhledávací tabulku podle následujících požadavků.
** Tabulka je implementována v poli, obsah prvků pole není seřazen.
** Při vyhledávání se sekvenčně prochází celé využité pole s využitím
** takzvané zarážky. Maximální kapacita tabulky je tedy o jedničku nižší,
** než maximální využitelná kapacita pole. Implementujte následující procedury
** a funkce (zkratka AS pochází ze slova Array = pole a Sentinel = zde zarážka):
** 
**   ASInit ..... inicializace tabulky
**   ASSearch ... vyhledávání se zarážkou v neseřazeném poli
**   ASInsert ... vkládání do neseřazeného pole s využitím ASSearch
**
** Při každém vyhledání se optimalizuje doba vyhledávání často hledaných
** položek tím, že se nalezená položka vždy posunuje o jedno místo směrem
** k začátku pole.
**
** Definici typů naleznete v souboru c403.h. Tabulka je reprezentována
** datovou strukturou typu tASTable, která se skládá z pole 'arr' a indexu
** poslední využité položky pole 'last'. Položky pole jsou tvořeny záznamy
** typu tASData, ve kterých se nachází složka Key (klíčem je pro jednoduchost
** číslo typu integer) a obsah Cont (demonstrativně int). Při implementaci těl
** řešených procedur uvažujte maximální rozměr pole ASSize (viz poznámka
** v c403.h).
**
** Důležitým rysem vyhledávacích metod je počet porovnávání vyhledávaného
** klíče s klíči prohledávaných položek pole. K porovnávání využívejte
** povinně funkce ASCompare (viz dále). Počet porovnávání omezte
** na minimum. To znamená, že nebudete volat podruhé funkci ASCompare
** pro stejné klíče tam, kde jste si mohli výsledek porovnání zapamatovat
** v pomocné proměnné.
*/

#include "c403.h"
int ASCompNum;
int solved;
int errflg;

int ASCompare (int k1, int k2) {
  ASCompNum = ASCompNum + 1;      /* počet porovnání */ 
  if (k1 < k2)                    /* porovnání dvou klíčů */
    return(-1);
  else if (k1 == k2)
    return(0);
  else                            /* k1 > k2 */ 
    return(1);
}

void ASError() {
  printf("Chyba: Polozka jiz nemuze byt vlozena\n");
  errflg = TRUE;
}
/* ------------------------------------------------------------------------- */
void ASInit(tASTable *Tab) {
/* Inicializace tabulky (výsledkem je prázdná tabulka).
** Inicializace tabulky se provede tak, že se index posledního prvku nastaví na
** hodnotu -1. Hodnoty prvků ani klíčů se v tabulce nemění.
*/

	Tab -> last = -1;

}


int ASSearch (tASTable *Tab, int key, int* ind) {
/* Vyhledávání v NESEŘAZENÉM poli se zarážkou a s přesunem nalezené
** položky o jednu pozici dopředu (výměna s předchozí položkou).
**
** Vyhledávacím klíčem je hodnota key. Funkce vrací příznak, zda byl prvek
** nalezen. Pokud ne (vrací false), pak se v proměnné 'ind' vrací první
** volná pozice, na kterou se může prvek vložit.
** Pokud byl prvek nalezen (vrací true), došlo k jeho posunutí o jednu
** pozici dopředu a v proměnné ind se vrací nová pozice nalezeného prvku.
**
** Pro porovnání dvou klíčů používejte předdefinovanou funkci ASCompare
** (viz. výše). Vzhledem k tomu, že se při vyhledávání vždy používá
** zarážka, bude minimální počet porovnání (při prázdné tabulce) roven 1.
**
** POZOR!!!
** Při vložení zarážky se hodnota 'last' NEMĚNÍ! Zarážka se tedy nachází
** na pozici 'last' + 1. Zarážka může obsahovat obecně libovolnou hodnotu, 
** vy ale hodnotu zarážky nastavte na -1, aby se vám shodovaly výsledky testů!
*/

	Tab -> arr[Tab -> last + 1].Key = key; //zarazka klice
	Tab -> arr[Tab -> last + 1].Cont = -1; //zarazka obsahu
	unsigned int index = 0; //index pole
	while (ASCompare(key, Tab -> arr[index].Key) != 0) { // dokud jsme nenasli klic (nebo zarazku)
		index++; //pousunujeme se v poli
	}
	if (index != Tab -> last + 1) { //kdyz jsme nenasli zarazku, budeme prohazovat prvky
		if (index > 0) { //prvek uplne na zacatku uz by nebylo s cim prohodit
			tASData swap = Tab -> arr[index]; //zalohujeme nalezeny prvek
			Tab -> arr[index] = Tab -> arr[index - 1]; //prohodime prvky
			Tab -> arr[index - 1] = swap; //vlozime nalezeny prvek
			index--; //taku by bylo dobry aby index ukazoval spravne ;)
		}
		*ind = index; //nastavime nalezeny index
		return TRUE; //a skoncime
	}
	*ind = index; //nastavime nalezeny index (na prazdny prvek)
	return FALSE; //skoncime

}


void ASInsert (tASTable *Tab, int Key, int Content) {
/* Vloží novou položku s obsahem Content a klíčem Key do tabulky Tab.
**
** Pokud by vložením další položky došlo k přeplnění Tab (pokud by nešlo
** při dalším vyhledávání uložit zarážku), volejte proceduru ASError()
** a novou položku nevkládejte.
**
** Pokud daná položka (udaná klíčem Key) v poli již existuje, přiřadí se do
** odpovídající složky záznamu nový obsah. Při vyhledávání již existující 
** položky využijte dříve implementovanou funkci ASSearch (to znamená, že se
** existující a modifikovaná položka automaticky posune dopředu).
*/

	int index = 0; //index polozky v poli
	short nasli = ASSearch(Tab, Key, &index); //zjistime jestli nahodou takovy klic uz neexistuje (a posuneme ho)
	if (nasli) { //kdyz uz klic existuje
		Tab -> arr[index].Cont = Content; //zapiseme novou hodnutu
	} else { //klic neexistuje, vlozime novy
		if (index > ASSize - 2) { //bacha, lezem za roh (-2 kvuli zarazce a indexovani od 0)
			ASError(); //zakric
		} else { //vlezeme se
			Tab -> arr[index].Key = Key; //novy klic
			Tab -> arr[index].Cont = Content; //novy obsah
			Tab -> last = index; //nova posledni prazdna polozka
		}
	}

}

/* -------------------------- konec c403.c --------------------------------- */