package casa09;

public class SplayTreeImpl implements SplayTree {

    No raiz;
    private String visita;

    @Override
    public int inserir( int elem ) {
        if ( elem < 0 ) return -1;

        No y = null;
        No x = raiz;
        No z = new No( elem );

        while ( x != null ) {
            y = x;
            if ( z.getValor() < x.getValor() )
                x = x.getEsquerda();
            else if ( z.getValor() > x.getValor() )
                x = x.getDireita();
            else {
                splay(x);
                return 1;
            }
        }
        z.setPai( y );

        if ( y == null ) {
            raiz = z;
        } else if ( z.getValor() < y.getValor() ) {
            y.setEsquerda( z );
        } else {
            y.setDireita( z );
        }

        splay(z);
        return 0;
    }


    public No pesquisarNode( int elem ) {
        No temp = raiz;
        No tempPai = null;

        // Pesquisa o Nó
        while ( temp != null && temp.getValor() != elem ) {
            tempPai = temp.getPai();

            if ( temp.getValor() > elem )
                temp = temp.getEsquerda();
            else
                temp = temp.getDireita();
        }

//      if (temp != null)
//          splay(temp);
//      else
//          splay(tempPai);

        return temp;
    }

    @Override
    public int pesquisar( int elem ) {
        No temp = pesquisarNode( elem );
        return temp == null ? -1 : profundidade( temp.getPai() );
    }

    @Override
    public int remover( int elem ) {
        No temp = raiz;
        No tempPai = null;

        // Pesquisa o Nó
        while ( temp != null && temp.getValor() != elem ) {
            tempPai = temp.getPai();

            if ( temp.getValor() > elem )
                temp = temp.getEsquerda();
            else
                temp = temp.getDireita();
        }


        return -1;
    }

    @Override
    public String percorrePreOrdem() {
        visita = "";
        percorrePreOrdem( raiz );

        return "[" + visita.trim() + "]";
    }

    private void percorrePreOrdem( No no ) {
        if ( no != null ) {
            visita += no.getValor() + " ";
            percorrePreOrdem( no.getEsquerda() );
            percorrePreOrdem( no.getDireita() );
        }
    }

    /**
     * Retorna a profundidade de um determinado Nó
     * @param n Nó para achar a profundidade
     * @return Profundidade do Nó n.
     */
    public int profundidade( No n ) {
        if ( n == null ) return -1;

        No no = n;
        int count = 0;

        while ( no.getPai() != null ) {
            no = no.getPai();
            count++;
        }

        return count;
    }


    public void splay( No filho ) {

        if (raiz == null || raiz.equals( filho ))
            return;

        while ( !filho.equals( raiz ) ) {

            No pai = filho.getPai();
            No avo = pai.getPai();

            // Se o avo for null, então o pai é a raiz. zig simples.
            if ( avo == null ) {
                // Se for o filho da esquerda é zig_Right
                if ( filho.equals( pai.getEsquerda() ) ) {
                    zig_Right( filho );
                // Se não, é zig_Left
                } else {
                    zig_Left( filho );
                }
            // Se o avo não for null, entao é zig duplo.
                // Se for filho da esquerda:
            } else if ( filho.equals( pai.getEsquerda() ) ) {
                // Se for neto da esquerda, entao é zig_Zig_Right
                if ( pai.equals( avo.getEsquerda() ) ) {
                    zig_Zig_Right( filho );
                // Se não é zig_Zag_Left
                } else {
                    zig_Zag_Left( filho );
                }
                // Se nao for filho da esquerda, é filho da direita:
            } else {
                // Se for neto da direita, entao é zig_Zig_Left
                if ( pai.equals( avo.getDireita() ) ) {
                    zig_Zig_Left( filho );
                // Se não é zig_Zag_Right
                } else {
                    zig_Zag_Right( filho );
                }
            }
        }
    }

    public void zig_Right( No filho ) {
        No pai = filho.getPai();
        No B = filho.getDireita();

        // Muda o pai de filho
        filho.setPai( null );
        // Muda o filho Direito de filho
        filho.setDireita( pai );
        // Muda o pai de pai
        pai.setPai( filho );

        // Muda o filho Esquerdo de pai
        pai.setEsquerda( B );
        // Muda o pai de B
        if ( B != null )
            B.setPai( pai );

        // atualiza a raiz;
        raiz = filho;

    }

    public void zig_Left( No filho ) {
        No pai = filho.getPai();
        No B = filho.getEsquerda();

        // Muda o pai de filho
        filho.setPai( null );
        // Muda o filho Esquerdo de filho
        filho.setEsquerda( pai );
        // Muda o pai de pai
        pai.setPai( filho );

        // Muda o filho Direito de pai
        pai.setDireita( B );
        // Muda o pai de B
        if ( B != null )
            B.setPai( pai );

        // atualiza a raiz;
        raiz = filho;
    }

    public void zig_Zig_Right( No filho ) {
        // Guardo o Pai, Avo e os Filhos da direita de filho e de pai
        No pai = filho.getPai();
        No avo = pai.getPai();
        No B = filho.getDireita();
        No C = pai.getDireita();
        No bisavo = avo.getPai();

        // Mudo o pai e o filho direito de filho
        filho.setPai( bisavo );
        filho.setDireita( pai );

        // Mudo o pai e os filhos de pai
        pai.setPai( filho );
        pai.setEsquerda( B );
        pai.setDireita( avo );

        // Mudo o pai e o filho esquerda de avo
        avo.setPai( pai );
        avo.setEsquerda( C );

        // Atualizo os pais de B e C
        if ( B != null )
            B.setPai( pai );
        if ( C != null )
            C.setPai( avo );

        // Se tiver bisavo:
        if ( bisavo != null ) {
            // Se o avo for o filho Esquerdo de Bisavo:
            if ( bisavo.getEsquerda().equals( avo ) ) {
                bisavo.setEsquerda( filho );
            // Se nao, o avo é filho Direito do Bisavo:
            } else {
                bisavo.setDireita( filho );
            }
        // Se não tiver bisavo, é porque o avo era a raiz. Atualiz a raiz:
        } else {
            raiz = filho;
        }
    }

    public void zig_Zig_Left( No filho ) {
        // Guardo o Pai, Avo e os Filhos da direita de filho e de pai
        No pai = filho.getPai();
        No avo = pai.getPai();
        No bisavo = avo.getPai();
        No B = pai.getEsquerda();
        No C = filho.getEsquerda();

        // Mudo o pai e o filho esquerda de filho
        filho.setPai( bisavo );
        filho.setEsquerda( pai );

        // Mudo o pai e os filhos de pai
        pai.setPai( filho );
        pai.setEsquerda( avo );
        pai.setDireita( C );

        // Mudo o pai e o filho direita de avo
        avo.setPai( pai );
        avo.setDireita( B );

        // Atualizo os pais de B e C
        if ( C != null )
            C.setPai( pai );
        if ( B != null )
            B.setPai( avo );

        // Se tiver bisavo:
        if ( bisavo != null ) {
            // Se o avo for o filho Esquerdo de Bisavo:
            if ( bisavo.getEsquerda().equals( avo ) ) {
                bisavo.setEsquerda( filho );
            // Se nao, o avo é filho Direito do Bisavo:
            } else {
                bisavo.setDireita( filho );
            }
        // Se não tiver bisavo, é porque o avo era a raiz. Atualiz a raiz:
        } else {
            raiz = filho;
        }
    }

    public void zig_Zag_Right( No filho ) {
        // Guardo o Pai, Avo e os Filhos da direita de filho e de pai
        No pai = filho.getPai();
        No avo = pai.getPai();
        No bisavo = avo.getPai();
        No B = filho.getEsquerda();
        No C = filho.getDireita();

        // Muda o pai e os filhos de filho
        filho.setPai( avo.getPai() );
        filho.setEsquerda( pai );
        filho.setDireita( avo );

        //  Muda o pai e o filho direita de pai
        pai.setPai( filho );
        pai.setDireita( B );

        // Mudo o pai e o filho esquerda de avo
        avo.setPai( filho );
        avo.setEsquerda( C );

        // Atualizo os pais de B e C
        if ( B != null )
            B.setPai( pai );
        if ( C != null )
            C.setPai( avo );

        // Se tiver bisavo:
        if ( bisavo != null ) {
            // Se o avo for o filho Esquerdo de Bisavo:
            if ( avo.equals( bisavo.getEsquerda() ) ) {
                bisavo.setEsquerda( filho );
            // Se nao, o avo é filho Direito do Bisavo:
            } else {
                bisavo.setDireita( filho );
            }
        // Se não tiver bisavo, é porque o avo era a raiz. Atualiz a raiz:
        } else {
            raiz = filho;
        }
    }

    public void zig_Zag_Left( No filho ) {
        // Guardo o Pai, Avo e os Filhos da direita de filho e de pai
        No pai = filho.getPai();
        No avo = pai.getPai();
        No bisavo = avo.getPai();
        No B = filho.getEsquerda();
        No C = filho.getDireita();

        // Muda o pai e os filhos de filho
        filho.setPai( avo.getPai() );
        filho.setEsquerda( avo );
        filho.setDireita( pai );

        // Mudo o pai e o filho esquerda de pai
        pai.setPai( filho );
        pai.setEsquerda( C );

        // Mudo o pai e o filho direita de avo
        avo.setPai( filho );
        avo.setDireita( B );

        // Atualizo os pais de B e C
        if ( C != null )
            C.setPai( pai );
        if ( B != null )
            B.setPai( avo );

        // Se tiver bisavo:
        if ( bisavo != null ) {
            // Se o avo for o filho Esquerdo de Bisavo:
            if ( avo.equals( bisavo.getEsquerda() ) ) {
                bisavo.setEsquerda( filho );
            // Se nao, o avo é filho Direito do Bisavo:
            } else {
                bisavo.setDireita( filho );
            }
        // Se não tiver bisavo, é porque o avo era a raiz. Atualiz a raiz:
        } else {
            raiz = filho;
        }
    }

}