package com.wrox.algorithms.bstrees;

import com.wrox.algorithms.sorting.Comparator;

/**
 * Binarne drzewo wyszukiwawcze bez mechanizmów równoważenia
 *
 */
public class BinarySearchTree {
    /** Komparator wyznaczający porządek wartości reprezentowanych przez węzły */
    private final Comparator _comparator;

    /** Wskazanie na korzeń lub wartość pusta dla pustego drzewa */
    private Node _root;

    /**
     * Konstruktor
     * Parametr: Komparator wyznaczający porządek wartości
     */
    public BinarySearchTree(Comparator comparator) {
        assert comparator != null : "nie określono komparatora";
        _comparator = comparator;
    }

    /**
     * Poszukiwanie wartości w drzewie
     * Parametr: szukana wartość
     * Wynik: węzeł reprezentujący wartość lub wartość pusta
     */
    public Node search(Object value) {
        assert value != null : "nie podano wartości";

        Node node = _root;

        while (node != null) {
            int cmp = _comparator.compare(value, node.getValue());
            if (cmp == 0) {
               break;
            }

            node = cmp < 0 ? node.getSmaller() : node.getLarger();
        }

        return node;
    }

    /**
     * Wstawianie węzła do drzewa
     *
     * Parametr: wartość do wstawienia
     * Wynik: węzeł reprezentujący wartość
     */
    public Node insert(Object value) {
        Node parent = null;
        Node node = _root;
        int cmp = 0;

        while (node != null) {
            parent = node;
            cmp = _comparator.compare(value, node.getValue());
            node = cmp <= 0 ? node.getSmaller() : node.getLarger();
        }

        Node inserted = new Node(value);
        inserted.setParent(parent);

        if (parent == null) {
            _root = inserted;
        } else if (cmp < 0) {
            parent.setSmaller(inserted);
        } else {
            parent.setLarger(inserted);
        }

        return inserted;
    }

    /**
     * Usuwanie wartości z drzewa
     * Parametr: wartość do usunięcia
     * Wynik: usunięty węzeł lub wartość pusta
     */
    public Node delete(Object value) {
        Node node = search(value);
        if (node == null) {
            return null;
        }

        Node deleted = 
            node.getSmaller() != null && node.getLarger() != null 
                              ? node.successor() : node;
        assert deleted != null : "podano pustą wartość";

        Node replacement = 
            deleted.getSmaller() != null ? deleted.getSmaller() : deleted.getLarger();
        if (replacement != null) {
            replacement.setParent(deleted.getParent());
        }

        if (deleted == _root) {
            _root = replacement;
        } else if (deleted.isSmaller()) {
            deleted.getParent().setSmaller(replacement);
        } else {
            deleted.getParent().setLarger(replacement);
        }

        if (deleted != node) {
            Object deletedValue = node.getValue();
            node.setValue(deleted.getValue());
            deleted.setValue(deletedValue);
        }

        return deleted;
    }

    /**
     * Zwraca korzeń drzewa
     * Wynik: korzeń drzewa lub wartość pusta
     */
    public Node getRoot() {
        return _root;
    }
}
