#ifndef RED_BLACK_TREE_H
#define RED_BLACK_TREE_H

#include <string>
#include <vector>

using namespace std;

const int BLACK = 1;
const int RED = 0;
const int NEGATIVE_RED = -1;
const int DOUBLE_BLACK = 2;

/**
   Węzeł drzewa czerwono-czarnego przechowuje element danych oraz referencje
   do dzieci po lewej i po prawej stronie. Kolor
   to "koszt" przejścia przez węzeł; liczba 1 dla czarnego, a 0 dla czerwonego węzła.
   Tymczasowo może wynosić 2 lub -1.
*/
class Node
{
public:   
   /**
      Konstruuje czerwony węzeł bez danych.
   */
   Node();
   ~Node();
      
private:
   /**
      Dodaje węzeł jako dziecko bieżącego węzła.
      @param new_node dodawany węzeł
   */
   void add_node(Node* new_node);
public: // Te składowe są publiczne na potrzeby testowania.
   /**
      Przypisuje węzłowi lewe dziecko i aktualizuje w tym dziecku referencję do rodzica.
      @param child nowe lewe dziecko
   */
   void set_left_child(Node* child);

   /**
      Przypisuje węzłowi lewe dziecko i aktualizuje w tym dziecku referencję do rodzica.
      @param child nowe prawe dziecko
   */
   void set_right_child(Node* child);

   string data;
   Node* left;
   Node* right;
   Node* parent;
   int color;
   
friend class RedBlackTree;
};

/*
   Klasa ta stanowi implementację drzewa czerwono-czarnego.
*/
class RedBlackTree
{  
public: 
   /**
      Konstruuje puste drzewo.
   */
   RedBlackTree();
   ~RedBlackTree();
   RedBlackTree(const RedBlackTree& other); // Niezaimplementowane.
   RedBlackTree& operator=(const RedBlackTree& other);  // Niezaimplementowane.
   
   /**
      Wstawia do drzewa nowy element.
      @param element element do wstawienia
   */
   void insert(string element); 

   /**
      Próbuje znaleźć w drzewie pewien element.
      @param element element do znalezienia
      @return liczba 1, jeśli drzewo zawiera ten element, w przeciwnym razie 0
   */
   int count(string element) const;
   
   /**
      Próbuje usunąć element  z drzewa. Jeśli drzewo
      go nie zawiera, nic nie robi.
      @param element element do usunięcia
   */
   void erase(string element);

   /**
      Wyświetla zawartość drzewa wg porządku sortowania.
   */
   void print() const;
   
private:
   /**
      Wyświetla węzeł i wszystkich jego potomków wg porządku sortowania.
      @param parent korzeń wyświetlanego poddrzewa
   */
   void print(Node* parent) const;
   
   /**
      Akrualizuje łącza w rodzicu i węźle zastępującym
      kiedy ten węzeł jest zamieniany.
      Jeśli zastępowanym węzłem jest korzeń, aktualizuje również referencję do korzenia.
      @param to_be_replaced węzeł, kóry ma być zastąpiony
      @param replacement węzeł, który zastąpi dotychczasowy węzeł
   */
   void replace_with(Node* to_be_replaced, Node* replacement);

   /**
      Przywraca warunki drzewa czerwono-czarnego po dodaniu węzłą.
      @param new_node węzeł, króry został dodany
   */
   void fix_after_add(Node* new_node);

   /** 	
     Przywraca warunki drzewa czerwono-czarnego po usunięciu węzła
     @param to_be_removed węzeł do usunięcia
   */
   void fix_before_remove(Node* to_be_removed);
   
   /**
      Przenosi opłatę z dwojga dzieci na ich rodzica.
      @param parent węzeł z dwomojgiem dzieci lub
      nullptr (w tym przypadku nic nie jest wykonywane)
   */
   void bubble_up(Node* parent);

   /**
      Naprawia błąd minusowo czerwonego węzła lub podwójnych czerwonych węzłów wprowadzony przez przeniesienie w górę opłaty.
      @param child dziecko do sprawdzenia pod kątem błędu węzła minusowo czerwonego
      lub podwójnych czerwonych węzłów
      @return wartość true, jeśli drzewo zostało naprawione
   */
   bool bubble_up_fix(Node* child);
   
   /**
      Naprawia błąd "podwójnych czerwonych węzłów".
      @param child dziecko z czerwonym rodzicem
   */
   void fix_double_red(Node* child);
   
   /**
      Naprawia błąd węzła "minusowo czerwonego".
      @param neg_red węzeł minusowo czerwony
   */
   void fix_negative_red(Node* neg_red);

public: // na potrzeby testowania
   Node* root; 
};

#endif

