#include <algorithm>
#include <cmath>
#include <iostream>
#include "red_black_tree.h"

using namespace std;

/*
   Program ten testuje klasę drzew czerwono-czarnych.
*/

/**
   Wykonuje prosty, podręcznikowy test.
*/
void test_from_book()
{
   RedBlackTree t;
   t.insert("D");
   t.insert("B");
   t.insert("A");
   t.insert("C");
   t.insert("F");
   t.insert("E");
   t.insert("I");
   t.insert("G");
   t.insert("H");
   t.insert("J");
   t.erase("A"); // Usuwanie liścia
   t.erase("B"); // Usuwanie elementu z jednym dzieckiem
   t.erase("F"); // Usuwanie elementu z dwojgiem dzieci
   t.erase("D"); // Usuwanie korzenia
   t.print();
   cout << "Spodziewane: C E G H I J" << endl;
}

/**
   Wstawia wszystkie permutacje ciągu do drzewa czerwono-czarnego i sprawdza,
   czy zawiera potem te ciągi.
   @param letters posortowany ciąg liter bez powtórzeń
   @return liczba pomyślnie zaliczonych testów
*/
int insertion_test(string letters)
{
   int count = 0;
   string s = letters;
   do
   {
      RedBlackTree t;
      for (int i = 0; i < s.length(); i++)
      {
         t.insert(s.substr(i, 1));
      }
      bool pass = true;
      for (int i = 0; i < s.length(); i++)
      {
         string e = s.substr(i, 1);
         if (t.count(e) == 0)
         {
            cout << e << " nie zostało wstawione" << endl;
            pass = false;
         }
      }
      if (pass) 
      {
         count++;
      }
      else
      {
         cout << "Niepowodzenie w przypadku liter " << letters << endl;
      }
   }
   while(next_permutation(s.begin(), s.end()));
   return count;
}

/**
   Liczy węzły drzewa binarnego.
   @param n korzeń drzewa binarnego
   @return liczba węzłów w drzewie
*/
int size(Node* n)
{
   if (n == nullptr) { return 0; }
   else { return 1 + size(n->left) + size(n->right); }
}

/**
   Oblicza koszt przejścia z węzła do korzenia.
   @param n węzeł drzewa czerwono-czarnego
   @return liczba czarnych węzłów pomiędzy węzłem n a korzeniem
*/
int cost_to_root(Node* n)
{
   int c = 0;
   while (n != nullptr) { c = c + n->color; n = n->parent; }
   return c;
}

/**
   Kopiuje wszystkie węzły drzewa czerwono-czarnego.
   @param n korzeń drzewa czerwono-czarnego
   @return korzeń skopiowanego drzewa
*/
Node* copy(Node* n)
{
   if (n == nullptr) { return nullptr; }
   Node* new_node = new Node;
   new_node->set_left_child(copy(n->left));
   new_node->set_right_child(copy(n->right));
   new_node->data = n->data;
   new_node->color = n->color;
   return new_node;
}

/**
   Generuje lustrzane odbicie drzewa czerwono-czarnego.
   @param n korzeń drzewa, którego lustrzanego odbicie ma być wykonane
   @return korzeń lustrzanego odbicia drzewa
*/
Node* mirror(Node* n)
{
   if (n == nullptr) { return nullptr; }
   Node* new_node = new Node;
   new_node->set_left_child(mirror(n->right));
   new_node->set_right_child(mirror(n->left));
   new_node->data = n->data;
   new_node->color = n->color;
   return new_node;
}

/**
   Tworzy całkowicie czarne drzewo o podanej głębokości.
   @param depth wymagana głębokość
   @return korzeń całkowicie czarnego drzewa
*/
Node* full_tree(int depth)
{
   if (depth <= 0) { return nullptr; }
   Node* r = new Node;
   r->color = BLACK;
   r->set_left_child(full_tree(depth - 1));
   r->set_right_child(full_tree(depth - 1));
   return r;
}

/**
   Pobiera wszystkie węzły poddrzewa i wypełnia nimi wektor.
   @param n korzeń  poddrzewa
   @param nodes wektor, w którym mają być umieszczone węzły
*/
void get_nodes(Node* n, vector<Node*>& nodes)
{
   if (n == nullptr) { return; }
   get_nodes(n->left, nodes);
   nodes.push_back(n);
   get_nodes(n->right, nodes);
}

/**
   Wyświetla dokładny widok drzewa binarnego.
   @param n korzeń drzewa do wyświetlenia
   @param level poziom wcięcia dla korzenia
*/   
void print_detailed(Node* n, int level)
{
   if (n == nullptr) { return; }
   print_detailed(n->left, level + 1);
   for (int i = 0; i < level; i++) { cout << "  "; }
   cout << n->data << " " << n->color << endl;
   print_detailed(n->right, level + 1);
}

/**
   Wypełnia drzewo wartościami A, B, C, ... .
   @param t drzewo czerwono-czarne
   @return liczba węzłów w drzewie t
*/
int populate(RedBlackTree& t)
{
   vector<Node*> nodes;
   get_nodes(t.root, nodes);
   for (int i = 0; i < nodes.size(); i++)
   {
      string d = "A";
      d[0] = d[0] + i;
      nodes[i]->data = d;
   }
   return nodes.size();
}   
   
/**
   Sprawdza, czy drzewo zaczynające się w danym korzeniu jest czerwono-czarne
   i wyświetla komunikat o błędzie, jeśli znaleziony został błąd w struktury.
   @param n korzeń sprawdzanego poddrzewa
   @param is_root wartość true, jeśli jest to korzeń drzewa
   @param report_errors czy wyświetlać komunikaty o błędach
   @return czarna wysokość tego poddrzewa lub wartość -1, jeśli nie jest to
   poprawne drzewo czerwono-czarne
*/
int check_red_black(Node* n, bool is_root, bool report_errors)
{
   if (n == nullptr) { return 0; }
   int nleft = check_red_black(n->left, false, report_errors);
   int nright = check_red_black(n->right, false, report_errors);
   if (nleft == -1 || nright == -1) return -1;
   if (nleft != nright) 
   {
      if (report_errors)
      {
         cout << "Lewe i prawe dziecko węzła " << n->data
            << " mają rożną czarną głębokość" << endl;
      }
      return -1;
   }
   if (n->parent == nullptr)
   {
      if (!is_root) 
      {
         if (report_errors)
         {
            cout << n->data << " nie jest korzeniem i nie ma rodzica" << endl;
         }
         return -1;
      }
      if (n->color != BLACK) 
      {
         if (report_errors)
         {
            cout << "Korzeń " << n->data << " nie jest czarny.";
         }
         return -1;
      }
   }
   else
   {
      if (is_root) 
      {
         if (report_errors)
         {
            cout << n->data << " jest korzeniem i ma rodzica." << endl;
         }
         return -1;
      }
      if (n->color == RED && n->parent->color == RED) 
      {
         if (report_errors)
         {
            cout << "Rodzic czerwonego węzła " << n->data << " jest czerwony." << endl;
         }
         return -1;
      }
   }
   if (n->left != nullptr && n->left->parent != n) 
   {
      if (report_errors)
      {
         cout << "Lewe dziecko węzła " << n->data
            << " ma złe łącze do rodzica." << endl;
      }
      return -1;
   }
   if (n->right != nullptr && n->right->parent != n) 
   {
      if (report_errors)
      {         
         cout << "Prawe dziecko węzła " << n->data
            << " ma złe łącze do rodzica." << endl;
      }
      return -1;
   }
   if (n->color != RED && n->color != BLACK) 
   {
      if (report_errors)
      {         
         cout << n->data << " ma kolor " << n->color;
      }
      return -1;
   }
   return n->color + nleft;
}

/**
   Sprawdza, czy drzewo czerwono-czarne jest poprawne i zgłasza błąd, jeśli nie jest.
   @param t drzewo do sprawdzenia
   @param report_errors czy wyświetlać komunikaty o błędach
   @return wartość true, jeśli drzewo przechodzi test, albo false, jeśli nie
*/
bool check_red_black(RedBlackTree& t, bool report_errors)
{
   int result = check_red_black(t.root, true, report_errors);
   if (result == -1) { return false; }     
   
   // Sprawdź, czy to binarne drzewo poszukiwań.
   vector<Node*> nodes;
   get_nodes(t.root, nodes);
   for (int i = 0; i < nodes.size() - 1; i++)
   {
      if (nodes[i]->data > nodes[i + 1]->data > 0)
      {
         if (report_errors)
         {
            cout << nodes[i]->data << " jest większe niż " <<
               nodes[i + 1]->data << endl;
         }
         return false;
      }
   }
   return true;
}

/**
   Testuje usuwanie na podstawie szablonu drzewa z czarnym węzłem
   do usunięcia. Pozostałe węzły będą tworzyć wszystkie możliwe kombinacje
   kolorów czerwonego i czarnego.
   @param t szablon dla przypadków testowych
   @return liczba pomyślnie ukończonych testów
*/
int removal_test(const RedBlackTree& t)
{
   int count = 0;
   for (int m = 0; m <= 1; m++)
   {
      int nodes_to_color = size(t.root) - 2;
        // Nie zmieniamy koloru korzenia ani węzła to_delete.
      for (int k = 0; k < pow(2, nodes_to_color); k++)
      {
         RedBlackTree rb;
         if (m == 0) { rb.root = copy(t.root); }
         else { rb.root = mirror(t.root); }
         vector<Node*> nodes;
         get_nodes(rb.root, nodes);
         Node* to_delete = nullptr;

         // Pokoloruj wg wzorca bitów liczby k.
         int bits = k;
         for (Node* n : nodes)
         {
            if (n == rb.root)
            {
               n->color = BLACK;
            }
            else if (n->color == BLACK) 
            { 
               to_delete = n; 
            }
            else 
            {
               n->color = bits % 2;
               bits = bits / 2;
            }
         }
	
         // Dodaj dzieci, by wyrównać koszty dotarcia do wskaźnika nullptr.
         int target_cost = cost_to_root(to_delete);
         for (Node* n : nodes) 
         {
            int cost = target_cost - cost_to_root(n);
            if (n->left == nullptr)
            {
               n->set_left_child(full_tree(cost));
            }
            if (n->right == nullptr)
            {
               n->set_right_child(full_tree(cost));
            }
         }
		   
         int filled_size = populate(rb);

         if (check_red_black(rb, false)) // Znaleziono poprawne drzewo.
         {            
            string d = to_delete->data;
            rb.erase(d);
            bool pass = check_red_black(rb, true);
            for (int j = 0; j < filled_size; j++)
            {
               string s = "A";
               s[0] = s[0] + j;
               if (rb.count(s) == 0 && d != s)
               {
                  cout << s << " usunięty" << endl;
                  pass = false;
               }
            }
            if (rb.count(d) > 0)
            {
               cout << d << " nie usunięty" << endl;
               pass = false;
            }
            if (pass)
            {
               count++;
            }
            else
            {
               cout << "Drzewo z błędami: " << endl;
               print_detailed(rb.root, 0);
            }
         }
      }
   }
   return count;
}

/**
   Tworzy szablon do testowania usuwania.
   Usuwany węzeł jest czarny.
   @return niepełne drzewo czerwono-czarne do testów.
*/
RedBlackTree removal_test_template() 
{
   RedBlackTree result; 
      
   /*
                            n7
                           /  \
                          n1   n8
                         /  \
                       n0    n3
                            /  \
                           n2*  n5
                                /\
                              n4  n6
   */

   Node* n[9];
   for (int i = 0; i < 9; i++) { n[i] = new Node; }
   result.root = n[7];
   n[7]->set_left_child(n[1]);
   n[7]->set_right_child(n[8]);
   n[1]->set_left_child(n[0]);
   n[1]->set_right_child(n[3]);
   n[3]->set_left_child(n[2]);
   n[3]->set_right_child(n[5]);
   n[5]->set_left_child(n[4]);
   n[5]->set_right_child(n[6]);     
   n[2]->color = BLACK;   
   return result;
}  

int main()
{
   test_from_book();
   int passing = insertion_test("ABCDEFGHIJ");
   cout << passing << " testy wstawiania zakończone pomyślnie." << endl;
   passing = removal_test(removal_test_template());
   cout << passing << " testy usuwania zakończone pomyślnie." << endl;
   return 0;
}

