import java.util.ArrayList;

public class Tree24<E extends Comparable<E>> implements Tree<E> {
  private Tree24Node<E> root;
  private int size;
 
  /** Tworzy domyślne drzewo 2-3-4 */
  public Tree24() {
  }

  /** Tworzy drzewo 2-3-4 na podstawie tablicy obiektów */
  public Tree24(E[] elements) {
    for (int i = 0; i < elements.length; i++)
      insert(elements[i]);     
  }

  @Override /* Wyszukuje element w drzewie */
  public boolean search(E e) {
    Tree24Node<E> current = root; // Rozpoczynanie od korzenia

    while (current != null) {
      if (matched(e, current)) { // Element znajduje się w danym węźle
         return true; // Element został znaleziony
      }
      else {
        current = getChildNode(e, current); // Wyszukiwanie w poddrzewie
      }
    }

    return false; // Element nie znajduje się w drzewie
  }

  /** Zwraca true, jeśli element znajduje się w danym węźle */
  private boolean matched(E e, Tree24Node<E> node) {
    for (int i = 0; i < node.elements.size(); i++)
      if (node.elements.get(i).equals(e))
        return true; // Element został znaleziony

    return false; // Element nie znajduje się w danym węźle
  }

  /** Znajduje dziecko, w którym szukany będzie element e */
  private Tree24Node<E> getChildNode(E e, Tree24Node<E> node) {
    if (node.child.size() == 0)
      return null; // Węzeł jest liściem

    int i = locate(e, node); // Znajdowanie punktu wstawiania dla e
    return node.child.get(i); // Zwraca dziecko
  }

  @Override /** Wstawia element e do drzewa.
              * Zwraca true po udanym wstawieniu elementu
   */
  public boolean insert(E e) {
    if (root == null)
      root = new Tree24Node<E>(e); // Tworzenie nowego korzenia, by zapisać w nim element 
    else {
      // Znajdowanie liścia, gdzie można wstawić e
      Tree24Node<E> leafNode = null;
      Tree24Node<E> current = root;
      while (current != null)
        if (matched(e, current)) {
          return false; // Znaleziono taki sam element; nowy element nie jest wstawiany
        }
        else {
          leafNode = current;
          current = getChildNode(e, current);
        }

      // Wstawianie elementu e w liściu
      insert(e, null, leafNode); // Prawe dziecko elementu e to null
    }

    size++; // Zwiększanie wielkości
    return true; // Element został wstawiony
  }

  /** Wstawianie elementu e do węzła u */
  private void insert(E e, Tree24Node<E> rightChildOfe,
      Tree24Node<E> u) {
    // Pobieranie ścieżki wyszukiwania prowadzącej do elementu e
    ArrayList<Tree24Node<E>> path = path(e);

    for (int i = path.size() - 1; i >= 0; i--) {
      if (u.elements.size() < 3) { // u jest 2- lub 3-węzłem
        insert23(e, rightChildOfe, u); // Wstawianie e w węźle u
        break; // Dalsze wstawianie w rodzicu u nie jest konieczne
      }
      else {
        Tree24Node<E> v = new Tree24Node<E>(); // Tworzenie nowego węzła
        E median = split(e, rightChildOfe, u, v); // Podział u

        if (u == root) {
          root = new Tree24Node<E>(median); // Nowy korzeń
          root.child.add(u); // u jest lewym dzieckiem elementu środkowego
          root.child.add(v); // v jest prawym dzieckiem elementu środkowego
          break; // Dalsze wstawianie w rodzicu u nie jest konieczne
        }
        else {
          // W następnej iteracji pętli używane będą nowe wartości
          e = median; // Element wstawiany w rodzicu
          rightChildOfe = v; // Prawe dziecko tego elementu
          u = path.get(i − 1); // Nowy węzeł do wstawiania elementu
        } 
      }
    } 
  }

  /** Wstawia element do 2- lub 3-węzła i zwraca punkt wstawiania */
  private void insert23(E e, Tree24Node<E> rightChildOfe,
      Tree24Node<E> node) {
    int i = this.locate(e, node); // Znajdowanie miejsca wstawiania
    node.elements.add(i, e); // Wstawianie elementu w węźle
    if (rightChildOfe != null)
      node.child.add(i + 1, rightChildOfe); // Wstawianie wskaźnika do dziecka
  }

  /** Dzieli 4-węzeł u na u i v oraz wstawia e do u lub v */
  private E split(E e, Tree24Node<E> rightChildOfe,
      Tree24Node<E> u, Tree24Node<E> v) {
    // Przenoszenie ostatniego elementu z węzła u do v
    v.elements.add(u.elements.remove(2));
    E median = u.elements.remove(1);

    // Podział dzieci w węźle, który nie jest liściem.
    // Przeniesienie dwojga ostatnich dzieci z u do v
    if (u.child.size() > 0) {
      v.child.add(u.child.remove(2));
      v.child.add(u.child.remove(2));
    }

    // Wstawianie e do 2- lub 3-węzła u lub v
    if (e.compareTo(median) < 0)
      insert23(e, rightChildOfe, u);
    else
      insert23(e, rightChildOfe, v);

    return median; // Zwracanie elementu środkowego
  }

  /** Zwracanie ścieżki wyszukiwania prowadzącej do elementu e */
  private ArrayList<Tree24Node<E>> path(E e) {
    ArrayList<Tree24Node<E>> list = new ArrayList<Tree24Node<E>>();
    Tree24Node<E> current = root; // Rozpoczynanie od korzenia

    while (current != null) {
      list.add(current); // Dodawanie węzła do listy
      if (matched(e, current)) {
        break; // Element został znaleziony
      }
      else {
        current = getChildNode(e, current);
      }
    }

    return list; // Zwracanie tablicy węzłów
  }

  @Override /** Usuwa określony element z drzewa */
  public boolean delete(E e) {
    // Znajdowanie węzła zawierającego element e
    Tree24Node<E> node = root;
    while (node != null)
      if (matched(e, node)) {
        delete(e, node); // Usuwanie elementu e z węzła
        size−−; // Po usunięciu jednego elementu
        return true; // Element został usunięty
      }
      else {
        node = getChildNode(e, node); 
      }

    return false; // Element nie występuje w drzewie
  }

  /** Usuwa podany element z węzła */
  private void delete(E e, Tree24Node<E> node) {
    if (node.child.size() == 0) { // e znajduje się w liściu
      // Pobieranie ścieżki z korzenia do e
      ArrayList<Tree24Node<E>> path = path(e);

      node.elements.remove(e); // Usuwanie elementu e

      if (node == root) { // Przypadek specjalny
        if (node.elements.size() == 0) 
          root = null; // Drzewo jest puste
        return; // Gotowe
      }

      validate(e, node, path); // Wykrywanie niedopełnienia węzła
    }
    else { // e znajduje się w węźle wewnętrznym
      // Znajdowanie pierwszego od prawej węzła w lewym poddrzewie danego węzła
      int index = locate(e, node); // Indeks elementu e w węźle
      Tree24Node<E> current = node.child.get(index);
      while (current.child.size() > 0) {
        current = current.child.get(current.child.size() - 1);
      }
      E rightmostElement =
        current.elements.get(current.elements.size() - 1);
      
      // Pobieranie ścieżki z korzenia do e
      ArrayList<Tree24Node<E>> path = path(rightmostElement);

      // Zastępowanie usuniętego elementu elementem pierwszym od prawej
      node.elements.set(index, current.elements.remove(
        current.elements.size() - 1));

      validate(rightmostElement, current, path); // Wykrywanie niedopełnienia
    }
  }

  /** Wykonuje przeniesienie i złączanie (jeśli to konieczne) */
  private void validate(E e, Tree24Node<E> u,
      ArrayList<Tree24Node<E>> path) {
    for (int i = path.size() - 1; u.elements.size() == 0; i--) {
      Tree24Node<E> parentOfu = path.get(i - 1); // Pobieranie rodzica elementu u
      int k = locate(e, parentOfu); // Indeks elementu e w rodzicu

      // Sprawdzanie braci
      if (k > 0 && parentOfu.child.get(k - 1).elements.size() > 1) {
        leftSiblingTransfer(k, u, parentOfu);
      }
      else if (k + 1 < parentOfu.child.size() &&
          parentOfu.child.get(k + 1).elements.size() > 1) {          
        rightSiblingTransfer(k, u, parentOfu);
      }
      else if (k - 1 >= 0) { // Złączanie z lewym bratem
        // Pobieranie lewego brata węzła u
        Tree24Node<E> leftNode = parentOfu.child.get(k - 1);
    
        // Złączanie z lewym bratem węzła u
        leftSiblingFusion(k, leftNode, u, parentOfu);  

        // Koniec, gdy korzeń staje się pusty
        if (parentOfu == root && parentOfu.elements.size() == 0) {
          root = leftNode;
          break;
        }

        u = parentOfu; // Powrót do pętli w celu sprawdzenia rodzica
      }
      else { // Złączanie z prawym bratem (który musi istnieć)
        // Pobieranie lewego brata węzła u
        Tree24Node<E> rightNode = parentOfu.child.get(k + 1);

        // Złączanie z prawym bratem węzła u
        rightSiblingFusion(k, rightNode, u, parentOfu);  

        // Koniec, gdy korzeń staje się pusty
        if (parentOfu == root && parentOfu.elements.size() == 0) {
          root = rightNode;
          break;
        }

        u = parentOfu; // Powrót do pętli w celu sprawdzenia rodzica
      }
    }
  }

  /** Znajdowanie punktu wstawiania elementu w węźle */
  private int locate(E o, Tree24Node<E> node) {
    for (int i = 0; i < node.elements.size(); i++) {
      if (o.compareTo(node.elements.get(i)) <= 0) {
        return i;
      }
    }

    return node.elements.size();
  }

  /** Przeniesienie z lewego brata */
  private void leftSiblingTransfer(int k, 
      Tree24Node<E> u, Tree24Node<E> parentOfu) {
    // Przenoszenie elementu z rodzica do u
    u.elements.add(0, parentOfu.elements.get(k - 1));
    
    // Przenoszenie elementu z lewego węzła do rodzica
    Tree24Node<E> leftNode = parentOfu.child.get(k - 1);
    parentOfu.elements.set(k - 1,
      leftNode.elements.remove(leftNode.elements.size() - 1));

    // Przenoszenie wskaźnika do dziecka z lewego brata do danego węzła
    if (leftNode.child.size() > 0)
      u.child.add(0, leftNode.child.remove(
        leftNode.child.size() - 1));
  }

  /** Przenoszenie z prawego dziecka */
  private void rightSiblingTransfer(int k, 
      Tree24Node<E> u, Tree24Node<E> parentOfu) {
    // Przenoszenie elementu z rodzica do u
    u.elements.add(parentOfu.elements.get(k));
    
    // Przenoszenie elementu z prawego węzła do rodzica
    Tree24Node<E> rightNode = parentOfu.child.get(k + 1);
    parentOfu.elements.set(k, rightNode.elements.remove(0));

    // Przenoszenie wskaźnika do dziecka z prawego brata do danego węzła
    if (rightNode.child.size() > 0)
      u.child.add(rightNode.child.remove(0));
  }

  /** Złączanie z lewym bratem */
  private void leftSiblingFusion(int k, Tree24Node<E> leftNode,
      Tree24Node<E> u, Tree24Node<E> parentOfu) {
    // Przenoszenie elementu z rodzica do lewego brata
    leftNode.elements.add(parentOfu.elements.remove(k - 1));

    // Usuwanie wskaźnika do pustego węzła
    parentOfu.child.remove(k);

    // Modyfikowanie wskaźników do dzieci, jeśli węzeł nie jest liściem
    if (u.child.size() > 0)
      leftNode.child.add(u.child.remove(0));
  }
  
  /** Złączanie z prawym bratem */
  private void rightSiblingFusion(int k, Tree24Node<E> rightNode,
      Tree24Node<E> u, Tree24Node<E> parentOfu) {
    // Przenoszenie elementu z rodzica do prawego brata
    rightNode.elements.add(0, parentOfu.elements.remove(k));

    // Usuwanie wskaźnika do pustego węzła
    parentOfu.child.remove(k);

    // Modyfikowanie wskaźników do dzieci, jeśli węzeł nie jest liściem
    if (u.child.size() > 0)
      rightNode.child.add(0, u.child.remove(0));
  }

  @Override /** Pobiera liczbę węzłów w drzewie */
  public int getSize() {
    return size;
  }

  @Override /** Przechodzi drzewo w porządku preorder, zaczynając od korzenia */
  public void preorder() {
    preorder(root);
  }

  /** Przechodzi drzewo w porządku preorder, zaczynając od poddrzewa */
  private void preorder(Tree24Node<E> root) {
    if (root == null)return;
    for (int i = 0; i < root.elements.size(); i++)
      System.out.print(root.elements.get(i) + " ");

    for (int i = 0; i < root.child.size(); i++)
      preorder(root.child.get(i));
  }

  @Override /** Przechodzi drzewo w porządku inorder, zaczynając od korzenia */
  public void inorder() {
    // Ćwiczenie dla czytelników
  }

  /** Przechodzi drzewo w porządku postorder, zaczynając od korzenia */
  public void postorder() {
    // Ćwiczenie dla czytelników
  }

  @Override /** Zwraca true, jeśli drzewo jest puste */
  public boolean isEmpty() {
    return root == null;
  }
  
  @Override /** Usuwa wszystkie elementy z drzewa */
  public void clear() {
    root = null;
    size = 0;
  }
  
  @Override /** Zwraca iterator do przetwarzania elementów drzewa */
  public java.util.Iterator<E> iterator() {
    // Ćwiczenie dla czytelników
    return null;
  }
  
  /** Definiuje węzeł drzewa 2-3-4 */
  protected static class Tree24Node<E extends Comparable<E>> {
    // Węzły mają maksymalnie trzy elementy
    ArrayList<E> elements = new ArrayList<E>(3);
    // Każdy może mieć do czworga dzieci
    ArrayList<Tree24Node<E>> child 
      = new ArrayList<Tree24Node<E>>(4);

    /** Tworzy pusty węzeł typu Tree24Node */
    Tree24Node() {
    }

    /** Tworzy węzeł typu Tree24Node z początkowym elementem */
    Tree24Node(E o) {
      elements.add(o);
    }
  }
}
