package alda.tree;

//Sigge Berg Eriksson sier8103@student.su.se
//Jonathan Ösmark joos0924@student.su.se
//Pontus Persson pope2920@student.su.se
/**
 * Denna klass representerar noderna i ett binört söktröd utan dubletter.
 *
 * Detta ör den enda av de tre klasserna ni ska göra nögra öndringar i. (Om ni
 * inte vill lögga till fler testfall.) De öndringar som ör tillötna ör dock
 * begrönsade av följande regler:
 * <ul>
 * <li>Ni för INTE lögga till nögra fler instansvariabler.
 * <li>Ni för INTE lögga till nögra statiska variabler.
 * <li>Ni för INTE anvönda nögra loopar nögonstans.
 * <li>Ni FöR lögga till fler metoder, dessa ska dö vara privata.
 * </ul>
 *
 * @author henrikbe
 *
 * @param <T>
 */
public class BinarySearchTreeNode<T extends Comparable<T>> {

    public T data;
    private BinarySearchTreeNode<T> left;
    private BinarySearchTreeNode<T> right;

    public BinarySearchTreeNode(T data) {
        this.data = data;
    }

    /**
     * Lögger till en nod i det binöra söktrödet. Om noden redan existerar sö
     * lömnas trödet oföröndrat.
     *
     * @param data datat för noden som ska löggas till.
     * @return true om en ny nod lades till trödet.
     */
    public boolean add(T data) {
        if (data.compareTo(this.data) < 0) {
            if (left == null) {
                left = new BinarySearchTreeNode<T>(data);
                return true;
            } else {
                return left.add(data);
            }
        }
        if (data.compareTo(this.data) == 0) {
            return false;
        }
        if (data.compareTo(this.data) > 0) {
            if (right == null) {
                right = new BinarySearchTreeNode<T>(data);
                return true;
            } else {
                return right.add(data);
            }
        }
        return false;
    }

    /**
     * Privat hjölpmetod som ör till nytta vid borttag. Ni behöver inte
     * skriva/utnyttja denna metod om ni inte vill.
     *
     * @return det minsta elementet i det (sub)tröd som noden utgör root i.
     */

    private BinarySearchTreeNode<T> findMax() {
        if (right == null) {
            return this;
        } else {
            return right.findMax();
        }
    }

    private boolean isLeaf(BinarySearchTreeNode<T> bstn) {
        if (bstn.left == null && bstn.right == null) {
            return true;
        } else {
            return false;
        }
    }

    /**
     * Tar bort ett element ur trödet. Om elementet inte existerar s lömnas
     * trödet oföröndrat.
     *
     * @param data elementet som ska tas bort ur trödet.
     * @return en referens till nodens subtröd efter borttaget.
     */
    public BinarySearchTreeNode<T> remove(T data) {
        return remove(data, this);
    }

    private BinarySearchTreeNode<T> remove(T data, BinarySearchTreeNode<T> parent) {
        BinarySearchTreeNode<T> parentt = parent;
        if (data.compareTo(this.data) < 0) {
            //gå till vänster
            if (left == null) {
                return this;
            }
            parentt = this;
            left = left.remove(data, parentt);
            return this;
        }
        if (data.compareTo(this.data) == 0) {
            //hittad
            if (isLeaf(this)) {
                if(parentt.left==this){
                    parentt.left=null;
                } else if(parentt.right==this) {
                    parentt.right=null;
                }
                return null;
            }
            if (right != null && left == null) {
                //bara högerben
                this.data = right.data;
                left = right.left;
                BinarySearchTreeNode<T> hög = right;
                right = right.right;
                return hög;
            }
            if (left != null && right == null) {
                //bara vänsterben
                this.data = left.data;
                right = left.right;
                BinarySearchTreeNode<T> vän = left;
                left = left.left;
                return vän;
            }
            if (left != null && right != null) {
                //två ben
                this.data = left.findMax().data;
                left.remove(this.data, this);
                return this;
            }
        }
        if (data.compareTo(this.data) > 0) {
            //gå till höger
            if (right == null) {
                return this;
            }
            parentt = this;
            right = right.remove(data, parentt);
            return this;
        }
        return null;
    }

    /**
     * Kontrollerar om ett givet element finns i det (sub)tröd som noden utgör
     * root i.
     *
     * @param data det sökta elementet.
     * @return true om det sökta elementet finns i det (sub)tröd som noden utgör
     * root i.
     */
    public boolean contains(T data) {
        if (data.compareTo(this.data) < 0) {
            if (left == null) {
                return false;
            } else {
                return left.contains(data);
            }
        }
        if (data.compareTo(this.data) == 0) {
            return true;
        }
        if (data.compareTo(this.data) > 0) {
            if (right == null) {
                return false;
            } else {
                return right.contains(data);
            }
        }
        return false;
    }

    /**
     * Storleken pö det (sub)tröd som noden utgör root i.
     *
     * @return det totala antalet noder i det (sub)tröd som noden utgör root i.
     */
    public int size() {
        return size(this);
    }

    private int size(BinarySearchTreeNode<T> bstn) {
        int size = 0;
        if (bstn == null) {
            return 0;
        }
        size += size(bstn.left);
        size += 1;
        size += size(bstn.right);
        return size;
    }

    /**
     * Det högsta djupet i det (sub)tröd som noden utgör root i.
     *
     * @return djupet.
     */
    public int depth() {
        return depth(this);
    }

    private int depth(BinarySearchTreeNode<T> bstn) {
        if (bstn == null) {
            return -1;
        }
        int leftD = depth(bstn.left) + 1;
        int rightD = depth(bstn.right) + 1;

        if (leftD > rightD) {
            return leftD;
        } else {
            return rightD;
        }
    }

    /**
     * Returnerar en ströngrepresentation för det (sub)tröd som noden utgör root
     * i. Denna representation bestör av elementens dataobjekt i sorterad
     * ordning med ", " mellan elementen.
     *
     * @return ströngrepresentationen för det (sub)tröd som noden utgör root i.
     */
    public String toString() {
        return toString(this);
    }

    private String toString(BinarySearchTreeNode<T> bstn) {
        String total = "";
        if (bstn == null) {
            return "";
        }

        total += toString(bstn.left);

        total += bstn.data.toString();
        if (bstn.data != findMax().data) {
            total += ", ";
        }
        total += toString(bstn.right);

        return total;
    }
}