//Copyright Dr. Marek A. Suchenek, 2005 - 2025
/*
 * BStree.java
 *
 * Created on April 30, 2007, 11:00 AM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package bs_tree_test;

/**
 *
 * @author suchenek
 */
public class BStree {
    
    private int root; //
    private BStree leftSub; /* if this is the topmost node (header) then leftSub is the actual tree */
    private BStree rightSub;

//    For the topmost node (header), rightSub is not used.
//    It may be used to count number of nodes in each level,
//    which would require passing it to all deletes and inserts for updating.

//    cnt counts comparisons to elements of tree
//    cnt2 counts recursive calls
//    cnt4 enumerates traversals

    
    /** Creates a new instance of empty BStree */
    public BStree() {
        root = 0; //this instance is just a header, not a node in a tree - counts the number of elements in the tree
        leftSub = null;
        rightSub = null; //not used; maintained for the uniformity of the data structure
        
    }
    
    private static BStree deleteMin(BStree subtree, BStree vacant) {
        //deletes minimum element from subtree and writes the deleted element into the root of tree vacant
            cnt2.incr();
        if (subtree.leftSub == null)
        {
            vacant.root = subtree.root;
            return(subtree.rightSub);
        }
//            return deleteMin(subtree.leftSub, vacant); CORRECTED
        subtree.leftSub = deleteMin(subtree.leftSub, vacant);
        return subtree;
    }
    
    
    private static BStree deleteRec(int x, BStree subtree) {
            cnt2.incr();
        if (subtree == null) {
//            System.out.println("Detete failed: " + x + " not found");
            flag.clr(); //deletion not made
            return null;
        }
        if (x < subtree.root) {
            cnt.incr();
            subtree.leftSub =  deleteRec(x, subtree.leftSub);
            return (subtree);
        } else if (x > subtree.root) {
            cnt.incr();
            subtree.rightSub =  deleteRec(x, subtree.rightSub);
            return (subtree);
        }
        /* x should be deleted from here */
        if (subtree.leftSub == null) return (subtree.rightSub);
        else {if (subtree.rightSub == null) return (subtree.leftSub);};
        /* "difficult" case - x has both children*/
        //delete the minimum element from subtree.rightSub and insert the deleted element to subtree.root
        subtree.rightSub = deleteMin(subtree.rightSub, subtree);  //deletes the minimum element of rightSub and writes it into the root of subtree
        return (subtree);
//        return (deleteMin(subtree.rightSub, subtree)); CORRECTED
    }
    
    public boolean delete(int x)
    
    {
        flag.set(); //if the value of flag remains true then the deletion was made
        this.leftSub = deleteRec(x, this.leftSub);
        if (flag.get())
        {
            root--; //one less node in this tree
            return true;
        }
        else return false;
    }
    
    private static BStree insertRec(int x, BStree subtree) {
            cnt2.incr();
        if (subtree == null) {
            subtree = new BStree();
            subtree.root = x;
            
        } else {
            if (x < subtree.root)
            {cnt.incr();
                subtree.leftSub = insertRec(x, subtree.leftSub);
            }
            else if (x > subtree.root)
            {cnt.incr();
                subtree.rightSub = insertRec(x, subtree.rightSub);
            }
//            else  System.out.println("Insert failed: " + x + " already there");
            else  flag.clr(); //insertion not made
            
        } // if x = subtree.root then x is already there - no insertion necessary
        return (subtree);
        
    }
    
    public boolean insert(int x) {
        flag.set(); //if the value of flag remains true then the insertion was made
        this.leftSub = insertRec(x, this.leftSub);
        if (flag.get())
        {
            root++; //one more node in this tree
            return true;
        }
        else return false;
    }
    
    private static void inOrderRec(BStree subtree)
//            Traverses subtree and prints its nodes in inorder sequence
    {
        cnt2.incr();
        if (subtree == null) return;
        inOrderRec(subtree.leftSub);
        System.out.print(subtree.root + " ") ;
        inOrderRec(subtree.rightSub);
    }
    
    public void inOrderPrint()
//            Traverses this tree (ignoring the "dummy" root) and prints its nodes in inorder sequence
    {
        System.out.print("Sorted: ");
        inOrderRec(this.leftSub);
        System.out.println();
    }
    private static void inOrderArrRec(BStree subtree, int[] A)
//            Traverses subtree and feeds its nodes to array A in inorder sequence
//            Stops when array A is full or when subtree was traversed
//            cnt4 identifies the next index to be fed
    {
        cnt2.incr();
        if (subtree == null || cnt4.get() >= A.length) return;
        inOrderArrRec(subtree.leftSub, A);
//        System.out.print(subtree.root + " ") ;
        if (cnt4.get() >= A.length) return;
        A[cnt4.get()] = subtree.root;
        cnt4.incr();
        inOrderArrRec(subtree.rightSub, A);
    }

    public int inOrderToArray(int[] A)
//            Traverses this tree (ignoring the "dummy" root) and feeds its nodes to array A in inorder sequence
//            Stops when array A is full or when subtree was traversed
//            cnt4 identifies the next index to be fed
//            returns the actual length of array fed
    {
//        System.out.print("Sorted: ");
        cnt4.clr();
        inOrderArrRec(this.leftSub, A);
//        for (int i = cnt4.get(); i < A.length; i++) A[i] = 0; //
//        System.out.println();
        return cnt4.get();
    }

    private static void preOrderRec(BStree subtree)
// Traverses subtree and prints its nodes in preorder sequence
    {
        if (subtree == null) return;
        System.out.print(subtree.root + " ") ;
        preOrderRec(subtree.leftSub);
        preOrderRec(subtree.rightSub);
    }

    public void preOrderPrint()
//            Traverses this tree (ignoring the "dummy" root) and prints its nodes in preorder sequence
    {
        System.out.print("Pre-ordered: ");
        preOrderRec(this.leftSub);
        System.out.println();
    }
    private static void preOrderArrRec(BStree subtree, int[] A)
//            Traverses subtree and feeds its nodes to array A in preorder sequence
//            Stops when array A is full or when subtree was traversed
//            cnt4 identifies the next index to be fed
    {
        cnt2.incr();
        if (subtree == null || cnt4.get() >= A.length) return;
//        System.out.print(subtree.root + " ") ;
        if (cnt4.get() >= A.length) return;
        A[cnt4.get()] = subtree.root;
        cnt4.incr();
        preOrderArrRec(subtree.leftSub, A);
        preOrderArrRec(subtree.rightSub, A);
    }

    public int preOrderToArray(int[] A)
//            Traverses this tree (ignoring the "dummy" root) and feeds its nodes to array A in preorder sequence
//            Stops when array A is full or when subtree was traversed
//            cnt4 identifies the next index to be fed
//            returns the actual length of array fed
    {
//        System.out.print("Sorted: ");
        cnt4.clr();
        preOrderArrRec(this.leftSub, A);
//        for (int i = cnt4.get(); i < A.length; i++) A[i] = 0; //
//        System.out.println();
        return cnt4.get();
    }

    public int size()
    {
        return root;
    }


    public int DeleteMin()
    {
        this.leftSub = deleteMin(this.leftSub, this);
        return this.root;
    }



}