package aed_gabriel;


    public class AvlTree
    {
        private AvlNode root;

        public AvlNode getRoot(){
        return root;
        }

        public AvlTree( )
        {
            root = null;
        }


        public void add( Pais p )
        {
            root = insert( p, root );
        }


        public void remove( Pais p )
        {
            System.out.println( "Sorry, remove unimplemented" );
        }





        public Comparable find( Comparable x )
        {
            return elementAt( find( x, root ) );
        }



        private AvlNode find( Comparable x, AvlNode t )
        {
            System.out.println("sdadas");

                    while( t != null )
//                System.out.printf("search %s with %s\n", ((Pais) t.pais).getNome(),((Pais) x).getNome() );
                if( x.compareTo(t.pais ) < 0 )
                    t = t.left;
                else if( x.compareTo(t.pais ) > 0 )
                    t = t.right;
                else
                    return t;    // Match

            return null;   // No match
        }




        public void printTree( )
        {
            if( root==null )
                System.out.println( "root==null" );
            else
                printTree( root );
        }


        private Comparable elementAt( AvlNode t )
        {
            if(t != null){
                return t.pais;
            }
            else return null;

        }


        private AvlNode insert( Comparable x, AvlNode t )
        {
            if( t == null )
                t = new AvlNode( x, null, null );
            else if( x.compareTo(t.pais ) < 0 )
            {
                t.left = insert( x, t.left );
                if( altura( t.left ) - altura( t.right ) == 2 )
                    if( x.compareTo(t.left.pais ) < 0 )
                        t = rotateWithLeftChild( t );
                    else
                        t = doubleWithLeftChild( t );
            }
            else if( x.compareTo(t.pais ) > 0 )
            {
                t.right = insert( x, t.right );
                if( altura( t.right ) - altura( t.left ) == 2 )
                    if( x.compareTo(t.right.pais ) > 0 )
                        t = rotateWithRightChild( t );
                    else
                        t = doubleWithRightChild( t );
            }
            else

            t.altura = max( altura( t.left ), altura( t.right ) ) + 1;
            return t;
        }





        private void printTree( AvlNode t )
        {
            if( t != null )
            {
                printTree( t.left );
                System.out.printf("%s\t\t\t\t%s\n" ,((Pais) t.pais).getNome(),((Pais) t.pais).getSigla() );
                printTree( t.right );
            }
        }


        private static int altura( AvlNode t )
        {
            if ( t == null) return -1;

            int altura = t.altura;

            return altura;
        }


        private static int max( int a, int b )
        {
            return a > b ? a : b;
        }


        private static AvlNode rotateWithLeftChild( AvlNode k2 )
        {
            AvlNode k1 = k2.left;
            k2.left = k1.right;
            k1.right = k2;
            k2.altura = max( altura( k2.left ), altura( k2.right ) ) + 1;
            k1.altura = max( altura( k1.left ), k2.altura ) + 1;
            return k1;
        }


        private static AvlNode rotateWithRightChild( AvlNode k1 )
        {
            AvlNode k2 = k1.right;
            k1.right = k2.left;
            k2.left = k1;
            k1.altura = max( altura( k1.left ), altura( k1.right ) ) + 1;
            k2.altura = max( altura( k2.right ), k1.altura ) + 1;
            return k2;
        }

        private static AvlNode doubleWithLeftChild( AvlNode k3 )
        {
            k3.left = rotateWithRightChild( k3.left );
            return rotateWithLeftChild( k3 );
        }


        private static AvlNode doubleWithRightChild( AvlNode k1 )
        {
            k1.right = rotateWithLeftChild( k1.right );
            return rotateWithRightChild( k1 );
        }




}