#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/* Chybové kódy */
#define ERR_AVL_MAX       2     /* počet možných chyb */
#define ERR_AVL_INIT      1     /* chyba při malloc */
#define ERR_AVL_KEY       2     /* chyba při malloc klíče */
 
/* Definice stavů */
#define BALANCE  -1 /* podstromy jsou vyvážené */
#define LEFT      0 /* levý podstrom je vyšší  */
#define RIGHT     1 /* pravý podstrom je vyšší */
#define SUBTREES  2 /* počet podstromů celkem  */
 
/* Datové struktury */
typedef struct avl_tree_value {
  void * ptr;
  int type;
  char init;   /* příznak použití */
} tSymbol;
 
typedef struct avl_tree_node {
  char * key;  /* klíč tabulky - řetězec */
  tSymbol * value; /* struktura hodnot tabulky symbolů */
  signed char height;  /* stav výšky */
  struct avl_tree_node * sub[SUBTREES];  /* pole uzlů */
} tAVL;
 
/* Prototypy funkcí */
void tAVLError ( int error_code );
tAVL * tAVLInit ();
tSymbol * tAVLFind ( tAVL * tree, char * str );
int tAVLInsert ( tAVL ** tree, char * str, tSymbol * value );
void tAVLFree ( tAVL * tree );
 
void tAVL_balance_path(tAVL * path, char * str);
void tAVL_balance(tAVL ** top, char * str);
tAVL * tAVL_single_rot(tAVL ** top, int direction );
tAVL * tAVL_double_rot(tAVL ** top, int direction, int third );

static int idcounter = 1;
 /**
 * Vypíše chybu při práci s AVL stromem na standardní chybový výstup
 * @param error_code Kód chyby
 */
void tAVLError ( int error_code ) {
    static const char* ERR_AVL_STRINGS[ERR_AVL_MAX + 1] = {
        "Unknown error",
        "AVL tree error: INIT",
        "AVL tree error: No memory for key"
    };
	  if (error_code <= 0 || error_code > ERR_AVL_MAX)
		    error_code = 0;
	  fprintf(stderr, "%s\n", ERR_AVL_STRINGS[error_code]);
}
 
 
/**
 * Inicializace AVL stromu
 * @return Prázdný AVL strom
 */
tAVL * tAVLInit()
{
    return NULL;
}
 
/**
 * Uvolnění AVL stromu
 * @param Strom k vymazání
 */
void tAVLFree(tAVL * tree)
{
    if (tree == NULL) return;
	  if (tree->sub[LEFT] != NULL) // vejdi do levého podstromu
        tAVLFree(tree->sub[LEFT]);
    if (tree->sub[RIGHT] != NULL) // vejdi do pravého podstromu
        tAVLFree(tree->sub[RIGHT]);
    idcounter = 0;
    free(tree->key); // uvolni paměť
    free(tree); // uvolni paměť
 
}
 
/**
 * Vyhledávání v binárním stromu
 * @param tree AVL strom určen k prohledání
 * @param str Vyhledávaný řetězec
 * @return Uzel s odpovídajícím klíčem
 */
tSymbol * tAVLFind(tAVL * tree, char * str)
{
  /*
    Klíčem je řetězec, proto používáme funkci strcmp, jejíž návratová
    hodnota může nabývat hodnot:
     -1 (nenalezeno, pokračuj směr vlevo),
      0 (nalezeno, vrať uzel) a
      1 (nenazeleno, pokračuj směr vpravo).
    Při naplnění proměnné next nemůže díky podmínce while nastat
    comparation == 0, tedy stačí zjistit zda comparation > 0.
  */
   int comparation;
    if (tree)
        comparation = strcmp(str, tree->key);
    while (tree && comparation) { /* vyhledávací cyklus */
        /* rozcestí vpravo|vlevo */
        int next = (comparation > 0 ? RIGHT : LEFT);
        tree = tree->sub[next]; /* přejdi na potomka */
        if (tree)
            comparation = strcmp(str, tree->key);
    }
    return tree ? tree->value : NULL;
}
 
/**
 * Vkládání do AVL stromu
 * @return 1 při úspěchu, 0 při neúspěchu
 */
int tAVLInsert ( tAVL ** tree, char * str, tSymbol * value )
{
    if (str == NULL) {
        char tmpstr[16];
        sprintf(tmpstr, "$%d", idcounter);
        idcounter++;
        str = malloc(sizeof(char) * strlen(tmpstr));
        if (str == NULL) {
            tAVLError(ERR_AVL_KEY);
            return 0;
        }
        strcpy(str, tmpstr);
    }
    /*  node je ukazatel na uzel stromu,
        ttop je ukazatel na nevyvážený podstrom */
    tAVL * node = *tree, ** ttop = tree;
    /* optimalizace pro výkon, uložení výsledku porovnání */
    int comparation = 0;
    if (node)
        comparation = strcmp(str, node->key);
    while (node && comparation) {
        /* rozcestí vpravo|vlevo */
        int next = (comparation > 0 ? RIGHT : LEFT);
        if (node->height >= 0) /* narážíme na nevyvážený podstrom */
            ttop = tree; /* ulož kořen nevyváženého podstromu */
        tree = &node->sub[next]; /* přejdi na potomka */
        node = *tree; /* změň i pomocný ukazatel na strom */
        if (node)
            comparation = strcmp(str, node->key);
    }
    if (node) return 0; /* klíč již existuje */
    /* klíč nenalezen, ukládání klíče */
    node = malloc(sizeof(*node));
    if (node == NULL) { /* chyba alokace */
        tAVLError(ERR_AVL_INIT);
        return 0;
    }
    node->sub[LEFT]  = NULL; /* nový uzel je prozatím list stromu*/
    node->sub[RIGHT] = NULL;
    node->height = BALANCE;
    node->value = value;
    node->key = str;
    /* klíč nám alokoval scanner, jen uložíme ukazatel
    malloc(strlen(str));
    if (node->key == NULL) {
        tAVLError(ERR_AVL_KEY);
        free(node);
        return 0;
    }
    else
        strncpy(node->key, str, strlen(str));*/
    *tree = node; /* ulož uzel do stromu */
    tAVL_balance(ttop, str); /* vyvaž strom */
    return 1;
}
 
 
/**
 * Druhý průchod stromem při vkládání. Upravuje vyváženost cesty
 * k přidanému uzlu tak, že kromě kořene zneváží všechny uzly.
 * @param path Cesta AVL stromu ( ergo uzel stromu )
 * @param str Hodnota klíče uzlu AVL stromu
 */
void tAVL_balance_path(tAVL * path, char * str)
{
    int comparation;
    if (path)
        comparation = strcmp(str, path->key);
    while (path && comparation) {
        int next = (comparation > 0 ? RIGHT : LEFT);
        path->height = next; /* vyvážení nastaveno dle směru ku klíči */
        path = path->sub[next];
        if (path)
            comparation = strcmp(str, path->key);
    }
}
 
/**
 * Vyvažování stromu. Pokud je strom u kořene nevyvážený, je třeba provést
 * rotaci a upravit vyvážení i na cestě ku klíči.
 * Rozhodování o rotaci probíhá ve třech krocích (first,second,third).
 * @param top Ukazatel na strom
 * @param str Hodnota klíče uzlu AVL stromu
 */
void tAVL_balance(tAVL ** top, char * str)
{
    if (!(*top)) return;
    tAVL * path = *top; /* Začněme od kořene */
    int first, second, third; /* stavy jednotlivých kroků */
    int comparation;
    /* Je-li strom u kořene vyvážený, uprav vyvážení na cestě ku klíči
     * a skonči.
     */
 
    if (path->height < 0) {
        tAVL_balance_path(path, str);
        return;
    }
    /* Kořen podstromu je nevyvážen. first udává stranu, která nese klíč.
     * Pokud first udává stranu kratší stranu podstromu, stačí jen upravit
     * vyvážení kořene a cesty ku klíči a skončit.
     */
    /* strcmp zde nevrátí nulu, protože top je přinejmenším rodič uzlu klíče
     * již před voláním funkce tAVL_balance */
    first = (strcmp(str, path->key) > 0 ? RIGHT : LEFT);
    if (path->height != first) {
        path->height = BALANCE; /* nevyvážený kořen nastav na vyvážený */
        tAVL_balance_path(path->sub[first], str);
        return;
    }
    /* Kořen podstromu je nevyvážen. second udává stranu potomka kořene, která
     * nese klíč. Je-li nevyváženost na stejné straně jako v kořeni, provedeme
     * přehození dvou uzlů (single rotation).
     */
    comparation = strcmp(str, path->sub[first]->key);
    if (comparation == 0)
        second = BALANCE;
    else
        second = (comparation > 0 ? RIGHT : LEFT);
    if (first == second) {
        /* rotace dvou uzlů - single */
        path = tAVL_single_rot(top, first);
        tAVL_balance_path(path, str);
        return;
    }
    /* Kořen podstromu je nevyvážen. third udává vyvážení prapotomka kořene
     * na cestě k uzlu klíče. Provede se rotace tří uzlů (double rotation).
     */
    path = path->sub[first]->sub[second];
    comparation = strcmp(str, path->key);
    if (comparation == 0)
        third = BALANCE;
    else
        third = (comparation > 0 ? RIGHT : LEFT);
    path = tAVL_double_rot(top, first, third);
    tAVL_balance_path(path, str);
}
 
/**
 * Provádí operaci "single rotation", tedy záměnu dvou uzlů a
 * přesuspořádání jimi tvořeného podstromu
 * @param top Kořen měněného podstromu
 * @param direction Směr rotace (0 = vlevo, 1 = vpravo)
 * @return Krajní dolní uzel zvoleného směru
 */
tAVL * tAVL_single_rot(tAVL ** top, int direction )
{
  /*
        B              D
       / \            / \
      A   D    =>    B   E
         / \        / \
        C   D      A   C
  */
    tAVL *B, *C, *D, *E; /* ukazatele na uzly */
    B = *top;
    D = B->sub[direction];
    C = B->sub[1 - direction];
    E = D->sub[direction];
    *top = D; /* novým kořenem je potomek stávajícího */
    D->sub[1 - direction] = B; /* který se stává potomkem nového kořene */
    B->sub[direction] = C; /* potomka D nahradí jeho potomek C */
    B->height = BALANCE;
    D->height = BALANCE;
    return E;
}
 
/**
 * Provádí operaci "double rotation" nad nevyváženým stromem.
 * @param top Kořen měněného podstromu
 * @param direction Směr rotace (0 = vlevo, 1 = vpravo)
 * @param third Vyvážení prapotomka
 * @return Uzel prapotomka
 */
tAVL * tAVL_double_rot(tAVL ** top, int direction, int third )
{
  /*
       B                    _D_
      / \                  /   \
     A   F                B     F
        / \      ===>    / \   / \
       D   G            A   C  E  G
      / \
     C   E
  */
    tAVL *B, *C, *D, *E, *F;
    B = *top;
    F = B->sub[direction];
    D = F->sub[1 - direction];
    C = D->sub[1 - direction];
    E = D->sub[direction];
    *top = D;
    D->sub[1 - direction] = B;
    D->sub[direction] = F;
    B->sub[direction] = C;
    F->sub[1 - direction] = E;
    D->height = BALANCE;
    B->height = BALANCE;
    F->height = BALANCE;
    if (third == BALANCE)
        return NULL;
    if (third == direction) {
        B->height = 1 - direction;
        return E;
    }
    else {
        F->height = direction;
        return C;
    }
}