/*
 * (c) Copyright 2007, 2008, 2009 Hewlett-Packard Development Company, LP
 * All rights reserved.
 * [See end of file]
 */

package structure.tree;

import java.util.ArrayList ;
import java.util.Iterator ;
import java.util.List ;

import org.openjena.atlas.io.IndentedWriter ;
import org.openjena.atlas.io.PrintUtils ;
import org.openjena.atlas.io.Printable ;


/** Simple binary tree nodes, including operations that apply to all trees */  

public class TreeNode<R extends Comparable<R>> implements Printable
{
    private TreeNode<R> left ;
    private TreeNode<R> right ;
    private R record ;
    
    public TreeNode(R record)
    {
        this.record = record ;
    }
    
    public TreeNode(R record, TreeNode<R> left, TreeNode<R> right)
    {
        this(record) ;
        this.left = left ;
        this.right = right ;
    }
    
    public R insert(R newRecord)
    { return insert(newRecord, true) ; }
    
    // Unbalanced insert - return the record if the record already present, else null if new.
    public R insert(R newRecord, boolean duplicates)
    {
        int x = this.record.compareTo(newRecord) ;
        
        if ( x > 0 )
        {
            if ( left == null )
            {
                left = new TreeNode<R>(newRecord) ;
                return null ;
            }
            return left.insert(newRecord, duplicates) ;
        }
        
        if ( x == 0 && ! duplicates )
            return this.record ;

        if ( right == null )
        {
            right = new TreeNode<R>(newRecord) ;
            return null ;
        }
        return right.insert(newRecord, duplicates) ;
    }
    
    // Naming: rotateRight means move the left child up to the root and the root to the right
    // The left is the pivot 
    // == shift right
    // == clockwise
    // This is the wikipedia naming but that does not extend to the double rotations. 
    // Different books have different namings, based on the location of the pivot (which would be a left rotate)
    // But when we talk about double rotations, the pivotLeft terminolgy works better.
    // pivotLeft (= case left left) , pivotLeftRight, 
    
    
    // (K1 (K2 A B) C) ==> (K2 A (K1 B C))
    final public void rotateRight() { pivotLeft() ; }
    final public void pivotLeft()
    {
        // Validity checking?
        checkNotNull(left) ;
        
        R k1 = record ;
        R k2 = left.record ;
        TreeNode<R> a = left.left ;
        TreeNode<R> b = left.right ;
        TreeNode<R> c = right ;
        
        // Or reuse left.
        // TreeNode t = new TreeNode(k1, b, c) ;
        TreeNode<R> t = left ; t.record = k1 ; t.left = b ; t.right = c ;
        
        this.record = k2 ;
        this.left = a ;
        this.right = t ;
    }
    
    // (K1 A (K2 B C)) ==> (K2 (K1 A B) C)  
    final public void rotateLeft() { pivotRight() ; }
    final public void pivotRight()
    {
        checkNotNull(right) ;
        R k1 = record ;
        R k2 = right.record ;
        TreeNode<R> a = left ;
        TreeNode<R> b = right.left ;
        TreeNode<R> c = right.right ;
        
        //TreeNode t = new TreeNode(k1, a, b) ;
        TreeNode<R> t = right ; right.record = k1 ; right.left = a ; right.right = b ;  
        
        this.record = k2 ;
        this.left = t ;
        this.right = c ;
    }
    
    // LeftRight
    // (K3 (K1 A (K2 B C)) D) ==> (K2 (K1 A B) (K3 C D))
    //final public void rotateDoubleRight() { pivotLeftRight() ; }
    final public void pivotLeftRight()
    {
        checkNotNull(left) ;
        checkNotNull(left.right) ;
        R k3 = record ;
        R k1 = left.record ;
        R k2 = left.right.record ;
        TreeNode<R> a = left.left ;
        TreeNode<R> b = left.right.left ;
        TreeNode<R> c = left.right.right ;
        TreeNode<R> d = right ;
        
        this.record = k2 ;
//        this.left = new TreeNode<R>(k1, a, b) ;     // Reuse LeftRight
//        this.right = new TreeNode<R>(k3, c, d) ;    // reuse Left
        
        // XXX WRONG?
        this.left = left.right ;
        /*this.left.record = k1 ;*/ this.left.left = a ; this.left.right = b ; 
        this.right = left ;
        /*this.right.record = k3 ;*/ this.right.left = c ; this.right.right = d ;
        
    }
    
    // RightLeft
    // (K1 A (K3 (K2 B C) D)) ==> (K2 (K1 A B) (K3 C D))
    //final public void rotateDoubleLeft() { pivotRightLeft() ; }
    final public void pivotRightLeft()
    {
        checkNotNull(right) ;
        checkNotNull(right.left) ;
        
        R k1 = record ;
        R k3 = right.record ;
        R k2 = right.left.record ;
        TreeNode<R> a = left ;
        TreeNode<R> b = right.left.left ;
        TreeNode<R> c = right.left.right ;
        TreeNode<R> d = right.right ;
        
        this.record = k2 ;
//        this.left = new TreeNode<R>(k1, a, b) ;     // replace by in-place / RightLeft
//        this.right = new TreeNode<R>(k3, c, d) ;    // Right
        
     // XXX WRONG?
        this.left = left.right ; 
        /*this.left.record = k1 ; */this.left.left = a ; this.left.right = b ; 
        this.right = left ; 
        /*this.right.record = k3 ;*/ this.right.left = c ; this.right.right = d ;
        
    }
    
    // Not in this class
    public Iterator<R> records(R min, R max)
    { 
        return null ;
    }
    
    //public Iterator<R> records()
    
    public List<R> records()
    {
        List<R> x = new ArrayList<R>() ;
        records(x) ;
        return x ; // .iterator() ;
    }
    
    public void records(List<R> x)
    {
        if ( left != null )
            left.records(x) ;
        x.add(record) ;
        if ( right != null )
            right.records(x) ;

    }

    @Override
    public String toString() { return PrintUtils.toString(this) ; }
    
    public void outputNested(IndentedWriter out)
    {
        if ( left == null && right == null )
        {
            out.print(record) ;
            return ;
        }
        
        // At least one of left and right.
        
        out.print('(') ;
        out.print(record) ;
        out.print(' ') ;
        out.incIndent() ;
        out.println() ;
        if ( left != null )
            left.output(out) ;
        else
            out.print("undef") ;
        out.println();

        if ( right != null )
            right.output(out) ;
        else
            out.print("undef") ;
        out.print(')') ;
        out.decIndent() ;
    }
    
    @Override
    public void output(IndentedWriter out)
    {
        if ( left == null && right == null )
        {
            out.print(record) ;
            return ;
        }
        
        out.print('(') ;
        out.print(record) ;
        if ( left != null )
        {
            out.print(' ') ;
            left.output(out) ;
        }
        if ( right != null )
        {
            out.print(' ') ;
            right.output(out) ;
        }
        out.print(')') ;
    }

    // Inline me :-)
    final private static void checkNotNull(Object object)
    {
        if ( object == null )
            throw new TreeException("Null") ;
    }
}

/*
 * (c) Copyright 2007, 2008, 2009 Hewlett-Packard Development Company, LP
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */