/*
 Программу продготовил: Буренков Игорь (М8О-206Б-17)

 Вариант: АВЛ-дерево

 Коды ошибок:

 1** - процесс ввода
 2** - процесс сотрировки
 3** - процесс вывода

 *42 - Ошибка выделения памяти
 *43 - Ошибка перевыделения памяти
 *50 - Ошибка ввода

 */

#include <stdio.h>
#include <limits.h> // Для контроля вылетов за границы
#include <math.h>   // Для округления
#include <string.h>
#include <stdbool.h>


////////////////////////////////////////////////
// НАСТРОЙКИ
////////////////////////////////////////////////
unsigned short int StringLength = 256; // Длина строки
unsigned short start_init = 4;        // Кол-во инициируемых элементов по умолчанию
float step_init = 1.5;                // Кол-во эл-ов добавляемых в дин. массив за раз


 // Структуры
struct incmd {
    char cmdindex;                      // Сама комманда
    char *cmdword;                      // Текстовый параметр
    unsigned long long int *cmdint;     // Числовой параметр
};

struct avlleaf { // структура для представления узлов дерева
    char key[256];                                // Ключ
    unsigned long long int llupar;                // Числовой параметр
    long long int height;                         // Высота
    struct avlleaf* left;                        // Левый ребенок
    struct avlleaf* right;                       // Правый ребенок
};

// Основные Функции (сигнатуры)
char InputFiller(struct incmd**); //Функция для заполнения массива
char TreeShell(struct incmd**);   //Функция для выполнения комманд

////////////////////////////////////////////
//     ФУНКЦИИ РАБОТЫ С АВЛ - ДЕРЕВОМ     //
////////////////////////////////////////////

// Освобождение памяти
void MakeEmpty(struct avlleaf* tree){
 if(tree == NULL) return;
 MakeEmpty(tree->left);
 MakeEmpty(tree->right);
 free(tree);
}

// Вычисление высоты
long long int Height(struct avlleaf* tree){
 if (tree == NULL) {
     return -1;
 }else {
     return tree->height;
 }
}

// Вычисление максимального элемента
long long int MaxLL(long long int a, long long int b){
 if (a > b) {
     return a;
 } else {
     return b;
 }
}

// Small Right Rotation
struct avlleaf* SRR(struct avlleaf* tree) {
 struct avlleaf* tmp;
 tmp = tree->left;
 tree->left = tmp->right;
 tmp->right = tree;
 tree->height = MaxLL(Height(tree->left), Height(tree->right))+1;
 tmp->height =  MaxLL(Height(tmp->left), tree->height)+1;
 return tmp;
}

// Small Left Rotation
struct avlleaf* SLR(struct avlleaf* tree){
 struct avlleaf* tmp;
 tmp = tree->right;
 tree->right = tmp->left;
 tmp->left = tree;
 tree->height = MaxLL(Height(tree->left), Height(tree->right))+1;
 tmp->height =  MaxLL(Height(tree->right), tree->height)+1 ;
 return tmp;
}

// Full Left Rotation
struct avlleaf* FLR(struct avlleaf* tree){
 tree->right = SRR(tree->right);
 return SLR(tree);
}

// Full Metal Alchemist
struct avlleaf* FRR(struct avlleaf* tree){
 tree->left = SLR(tree->left);
 return SRR(tree);
}

// Добавление листа
struct avlleaf* InsertLeaf(struct avlleaf* tree, char key[256], unsigned long long int llupar){
  unsigned short int i;
    if (tree == NULL) {
       tree         = malloc(sizeof(struct avlleaf));
       tree->llupar = llupar;
       tree->height = 0;
       tree->left   = NULL;
       tree->right  = NULL;
       for (i = 0; i < 256; i++) {
        tree->key[i]   = key[i];
       }
    } else
    if (strcmp(key, tree->key) < 0) {
       tree->left = InsertLeaf(tree->left, key,  llupar);
       if ((Height(tree->left)) - (Height(tree->right)) == 2){
           if (strcmp(key, tree->left->key) < 0) tree = SRR(tree);
           else tree = FRR(tree);
       }
    } else
    if (strcmp(key, tree->key) > 0) {
       tree->right = InsertLeaf(tree->right, key, llupar);
       if ((Height(tree->right)) - (Height(tree->left)) == 2){
           if (strcmp(key, tree->right->key) > 0) tree = SLR(tree);
           else tree = FLR(tree);
       }
    }
    tree->height = MaxLL(Height(tree->left), Height(tree->right))+1;
    return tree;
}

// Поиск минимального листа
struct avlleaf* FindMinL(struct avlleaf* tree){
 if(tree == NULL) return NULL;
 else if(tree->left == NULL) return tree;
 else return FindMinL(tree->left);
}

// Поиск максимального листа
struct avlleaf* FindMaxL(struct avlleaf* tree) {
 if(tree == NULL) return NULL;
 else if(tree->right == NULL) return tree;
 else return FindMaxL(tree->right);
}

// Удаление листа из дерева
struct avlleaf* DeleteLeaf(struct avlleaf* tree, char key[256]){
  struct avlleaf* temp;
  unsigned short int i;

  // Нет совпадений
  if (tree == NULL) return NULL;

  // Поиск элемента
  if (strcmp(key, tree->key) < 0) tree->left = DeleteLeaf(tree->left, key);
  else if (strcmp(key, tree->key) > 0) tree->right = DeleteLeaf(tree->right, key);

  // Иначе элемент найден - обрабатываем случаи
  // Многодетный элемент
  else if((tree->left != NULL) && (tree->right != NULL)){
    temp = FindMinL(tree->right);
    tree->llupar = temp->llupar;
    for (i = 0; i < 256; i++) {
        tree->key[i]   = temp->key[i];
    }
    tree->right = DeleteLeaf(tree->right, tree->key);
  }
  // Один ребенок (2й - нулловый)
  else {
    temp = tree;
    if(tree->left == NULL)    tree = tree->right;
    else if(tree->right == NULL) tree = tree->left;
    free(temp);
  }

  // Если tree стул нуловым - выходим (все ок)
  if(tree == NULL) return tree;

  // Иначе...
  tree->height = MaxLL(Height(tree->left), Height(tree->right))+1;

  // Проверка на нарушение баланса
  // Если удалили левый узел
  if(Height(tree->left) - Height(tree->right) == 2){
            if(Height(tree->left->left) - Height(tree->left->right) == 1)
                return SLR(tree);
            else
                return FLR(tree);
  }
  // Если удалили правый узел
  else if(Height(tree->right) - Height(tree->left) == 2){
            if(Height(tree->right->right) - Height(tree->right->left) == 1)
                return SRR(tree);
            else
                return FRR(tree);
  }

  // Итог
  return tree;
}

// Получить баланс
int GetBalance(struct avlleaf* tree){
        if (tree == NULL) return 0;
        else return Height(tree->left) - Height(tree->right);
}

// Печать дерева
void PrintMe(struct avlleaf* tree, unsigned long long int lvl){
  unsigned long long int i;
  if(tree == NULL) return;
  PrintMe(tree->left, lvl+1);
  for (i = 0; i < lvl; i++) {
    printf("\t");
  }
  printf("%s", tree->key ); printf("\n");
  PrintMe(tree->right, lvl+1);
}

////////////////////////////////////////////
//         Основной "движок"              //
////////////////////////////////////////////
int main()
{
    // Создадим массив ввода
    struct incmd *incmd_dynmass;  // Дин. массив структур
    unsigned short int log_error; // Код ошибки [см. в начале]

    // Считываем ввод комманд
    log_error = InputFiller(&incmd_dynmass);
    if (log_error != 0){
      return 100 + log_error;
    }

    //Выполняем комманд
    log_error = TreeShell(&incmd_dynmass);
    if (log_error != 0){
      return 100 + log_error;
    }

    // ОТЛАДКА
    system("pause");
    return 0;
}


// Функция ввода комманд
char InputFiller(struct incmd **incmd_dynmass) {

    // Переменные
    unsigned long long int initcount = 0; // На сколько элементов выделен массив
    char tmpchar;                         // Переменная для ввода первого параметра сообщения
    unsigned short int ticker;                          // Для цикла for

   // Инициализация структуры
    *incmd_dynmass = malloc(start_init * sizeof**incmd_dynmass);
    // Обработка ошибки памяти
    if (*incmd_dynmass == NULL) {
       return 42;
    }
    (*incmd_dynmass)[0].cmdint = malloc(sizeof(unsigned long long int));
    // Обработка ошибки памяти
    if ((*incmd_dynmass)[0].cmdint == NULL) {
       return 42;
    }
    (*incmd_dynmass)[0].cmdint[0] = 0; //Обнуляем количество элементов
    initcount = start_init;

  // Непосредственное считывание данных
   while ((scanf("%c", &tmpchar) >= 1)){
     if (tmpchar == '*') break;
     // Если кол-во свободных ячеек закончилось
     if (initcount == ((*incmd_dynmass)[0].cmdint[0])+1) {
       if (initcount*step_init <= ULLONG_MAX) {
         initcount=floor(initcount*step_init);
         *incmd_dynmass = realloc(*incmd_dynmass, initcount * sizeof **incmd_dynmass);
         if (*incmd_dynmass == NULL) { // Ошибка перевыделения памяти
           return 43;
         }
       }
     }

     // Непосредственное добавление комманды
     switch (tmpchar){
      case '+':
      // Добавление элемента (1-WORD-ULL)
        ((*incmd_dynmass)[0].cmdint)[0]++; // Увеличиваем кол-во элементов
        (*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdindex = 1;  // Указываем операцию

        // Выделение памяти
        (*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdword = malloc(StringLength*sizeof(char));
        (*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdint =  malloc(sizeof(unsigned long long int));
        if (((*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdword == NULL)||(*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdint == NULL) {
           return 42;  // Ошибка памяти
        }

        // Считывание 2го параметра (WORD)
        if (scanf("%s", (*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdword) < 1) {
          return 50;  // Ошибка ввода
        }

        // Считывание 3го параметра (ULL)
        if (scanf("%llu", &((*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdint[0])) < 1) {
          return 50;  // Ошибка ввода
        }

        break;

      case '-':
      // Добавление элемента (2-WORD)
        ((*incmd_dynmass)[0].cmdint)[0]++; // Увеличиваем кол-во элементов
        (*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdindex = 2;  // Указываем операцию

        // Выделение памяти
        (*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdword = malloc(StringLength*sizeof(char));
        if ((*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdword == NULL) {
           return 42;  // Ошибка памяти
        }

        // Считывание 2го параметра (WORD)
        if (scanf("%s", (*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdword) < 1) {
          return 50;  // Ошибка ввода
        }

        break;

      case '!':
      // Добавление элементов (3-WORD) или (4-WORD)
        ((*incmd_dynmass)[0].cmdint)[0]++; // Увеличиваем кол-во элементов

         // Выделение памяти
        (*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdword = malloc(StringLength*sizeof(char));
        if ((*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdword == NULL) {
           return 42;  // Ошибка памяти
        }

        // Выбор операции
        while ((tmpchar != 'S') && (tmpchar != 's')  && (tmpchar != 'L')  && (tmpchar != 'l')) scanf("%c", &tmpchar);
        if ((tmpchar == 'S')||(tmpchar == 's')) {
          (*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdindex = 3;  // Указываем операцию
        } else
        if ((tmpchar == 'L')||(tmpchar == 'l')) {
          (*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdindex = 4;  // Указываем операцию
        }
        scanf("%s", (*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdword); // Сбрасываем до сл. параметра

        // Считывание 2го параметра (WORD)
        if (scanf("%s", (*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdword) < 1) {
          return 50;  // Ошибка ввода
        }

        break;

      default:
      // Добавление элементов (5-WORD)

        ((*incmd_dynmass)[0].cmdint)[0]++; // Увеличиваем кол-во элементов

        // Выделение памяти
        (*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdword = malloc(StringLength*sizeof(char));
        if ((*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdword == NULL) {
           return 42;  // Ошибка памяти
        }

        (*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdindex = 5;  // Указываем операцию
        if (scanf("%s", (*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdword) < 1) {
          return 50;  // Ошибка ввода
        }

        // Восстановление первого элемента
        for (ticker = 0; ticker < StringLength; ticker++) {
          (*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdword[StringLength-ticker]=
            (*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdword[StringLength-ticker-1];
        }
        (*incmd_dynmass)[((*incmd_dynmass)[0].cmdint)[0]].cmdword[0] = tmpchar;

       break;
     }

     while (getchar() != '\n');


   }

   // ОТЛАДКА
   /*
   for (initcount = 1; initcount <= ((*incmd_dynmass)[0].cmdint)[0]; initcount++){
    printf("\n");
    printf("%i", (*incmd_dynmass)[initcount].cmdindex);
    printf("\n");
   }

    for (initcount = 1; initcount <= ((*incmd_dynmass)[0].cmdint)[0]; initcount++){
    printf("\n");
    printf("%s", (*incmd_dynmass)[initcount].cmdword);
    printf("\n");
   }

   for (initcount = 1; initcount <= ((*incmd_dynmass)[0].cmdint)[0]; initcount++){
    printf("\n");
    if ((*incmd_dynmass)[initcount].cmdint != NULL) {
     printf("%llu", (*incmd_dynmass)[initcount].cmdint[0]);
    }
    printf("\n");
   }
   */

 return 0;
}


char TreeShell(struct incmd **incmd_dynmass) {

 // Переменные
 unsigned long long int tmp1_ull, tmp2_ull; // Временные переменные
 char tmpkey[256];
 struct avlleaf *tree = NULL;


 //Цикл прхода по коммандам
 for (tmp1_ull = 1; tmp1_ull <= ((*incmd_dynmass)[0].cmdint)[0]; tmp1_ull++) {
   //Проходимся по коммандам
    switch ((*incmd_dynmass)[tmp1_ull].cmdindex) {
     case 1:

     // Ввод ключа
      for (tmp2_ull = 0; tmp2_ull < StringLength; tmp2_ull++) {
        tmpkey[tmp2_ull] = ((*incmd_dynmass)[tmp1_ull].cmdword[tmp2_ull]);
      }

      // Создаем ключ
      tree = InsertLeaf(tree, tmpkey, (*incmd_dynmass)[tmp1_ull].cmdint[0]);
      printf("%s", tree->key);
      printf("\n");
    }
 }
 //PrintMe(tree, 0);
 return 0;
}