package com.wrox.algorithms.bstrees;

public class Node implements Cloneable {
    /** Wartość reprezentowana przez węzeł */
    private Object _value;

    /** Węzeł-ojciec lub wartość pusta */
    private Node _parent;

    /** Lewy syn ("mniejszy" węzeł) lub wartość pusta */
    private Node _smaller;

    /** Prawy syn ("większy" węzeł) lub wartość pusta */
    private Node _larger;

    /**
     * Konstruktor - tworzy węzeł-liść 
     * Parametr: wartość reprezentowana przez węzeł
     */
    public Node(Object value) {
        this(value, null, null);
    }

    /**
     * Konstruktor. Tworzy węzeł pośredni
     * Parametry:
     *   - wartość reprezentowana przez węzeł
     *   - lewy syn
     *   - prawy syn
     */
    public Node(Object value, Node smaller, Node larger) {
        setValue(value);
        setSmaller(smaller);
        setLarger(larger);

        if (smaller != null) {
            smaller.setParent(this);
        }

        if (larger != null) {
            larger.setParent(this);
        }
    }

    /**
     * Pobranie wartości reprezentowanej przez węzeł
     */
    public Object getValue() {
        return _value;
    }

    /**
     * Zmiana wartości reprezentowanej przez węzeł
     * Parametr - nowa wartość
     */
    public void setValue(Object value) {
        assert value != null : "podano pustą wartość";
        _value = value;
    }

    /**
     * Węzeł-ojciec lub wartość pusta
     */
    public Node getParent() {
        return _parent;
    }

    /**
     * Przypisanie węzła-ojca
     * Parametr: węzeł-ojciec lub wartość pusta
     */
    public void setParent(Node parent) {
        _parent = parent;
    }

    /**
     * Lewy syn lub wartość pusta
     */
    public Node getSmaller() {
        return _smaller;
    }

    /**
     * Przypisanie lewego syna
     * Parametr: lewy syn lub wartość pusta
     */
    public void setSmaller(Node smaller) {
        assert smaller != getLarger() : "lewy syn nie może być tożsamy z prawym";
        _smaller = smaller;
    }

    /**
     * Prawy syn lub wartość pusta
     */
    public Node getLarger() {
        return _larger;
    }


   /**
     * Przypisanie prawego syna
     * Parametr: prawy syn lub wartość pusta
     */
    public void setLarger(Node larger) {
        assert larger != getSmaller() : "prawy syn nie może być tożsamy z lewym";
        _larger = larger;
    }

    /**
     * Sprawdzenie, czy węzeł jest lewym synem swego ojca
     *
     */
    public boolean isSmaller() {
        return getParent() != null && this == getParent().getSmaller();
    }


   /**
     * Sprawdzenie, czy węzeł jest prawym synem swego ojca
     *
     */

    public boolean isLarger() {
        return getParent() != null && this == getParent().getLarger();
    }

    /**
     * Poszukiwanie węzła-minimum w drzewie o określonym korzeniu
     */
    public Node minimum() {
        Node node = this;

        while (node.getSmaller() != null) {
            node = node.getSmaller();
        }

        return node;
    }

   /**
     * Poszukiwanie węzła-maksimum w drzewie o określonym korzeniu
     */

    public Node maximum() {
        Node node = this;

        while (node.getLarger() != null) {
            node = node.getLarger();
        }

        return node;
    }

    /**
     * Poszukiwanie następnika
     */
    public Node successor() {
        if (getLarger() != null) {
            return getLarger().minimum();
        }

        Node node = this;

        while (node.isLarger()) {
            node = node.getParent();
        }

        return node.getParent();
    }

    /**
     * Poszukiwanie poprzednika
     */


    public Node predecessor() {
        if (getSmaller() != null) {
            return getSmaller().maximum();
        }

        Node node = this;

        while (node.isSmaller()) {
            node = node.getParent();
        }

        return node.getParent();
    }

    /**
     * Liczba węzłów drzewa o danym korzeniu
     */
    public int size() {
        return size(this);
    }

    /**
     * Wysokość drzewa o danym korzeniu
     */
    public int height() {
        return height(this) - 1;
    }


    public boolean equals(Object object) {
        if (this == object) {
            return true;
        }

        if (object == null || object.getClass() != getClass()) {
            return false;
        }

        Node other = (Node) object;

        return getValue().equals(other.getValue())
                && equalsSmaller(other.getSmaller())
                && equalsLarger(other.getLarger());
    }

    /**
     * Rekurencyjne obliczanie liczby węzłów w drzewie o danym korzeniu
     * Parametr: korzeń drzewa
     */
    private int size(Node node) {
        if (node == null) {
            return 0;
        }

        return 1 + size(node.getSmaller()) + size(node.getLarger());
    }



    private int hashCode(Node node) {
        if (node == null) {
            return 0;
        }

        return getValue().hashCode() ^ hashCode(node.getSmaller()) ^ hashCode(node.getLarger());
    }







    private boolean equalsSmaller(Node other) {
        return getSmaller() == null 
                    && other == null || getSmaller() != null 
                    && getSmaller().equals(other);
    }

    private boolean equalsLarger(Node other) {
        return getLarger() == null 
                    && other == null || getLarger() != null 
                    && getLarger().equals(other);
    }
}
