Using wrapper class instead of static variables

Question

This is my first question ever at StackOverFlow: I am studying to interviews with the help of "Cracking the code interview" (5th Edition) book, and I was solving the next problem:

Implement a function to check if a binary tree is a binary search tree (Q 4.5 pg 86).

Before we move on, I would like just to remind you the difference between a Binary search tree to a simple Binary tree:

A Binary search tree imposes the condition that for all nodes, the left children are less than or equal to the current node, which is less than all the right nodes.

So one of the solution the book offers is to scan the tree with In-Order traversal and on the fly to check if every node we visit is greater then the last one, and it assumes the tree can't have a duplicate values:

public static int last_printed = Integer.MIN_VALUE;
public static boolean checkBST(TreeNode n) {
    if(n == null) return true;

        // Check / recurse left
        if (!checkBST(n.left)) return false;

        // Check current
        if (n.data <= last_printed) return false;
        last_printed = n.data;

        // Check / recurse right
        if (!checkBST(n.right)) return false;

        return true; // All good!
}

Now, up here everything is good, but then the book quotes :

If you don't like the use of static variables, then you can tweak this code to use a wrapper class for the integer, as shown below:

Class WrapInt {
    public int value;
}

After reading on wrapper class all over here and in other websites I just couldn't come to the conclusion, why and how should I use the wrapper class here instead of the static variable?

score 2 · Accepted Answer · answered Apr 21 '15 at 11:32

This is a mechanism whereby you can create an instance of WrapInt, and pass it around. You then expose the value only to code that should know about it, instead of a public static non-final variable that can be accessed and changed from anywhere.

The reason you have the wrapper class is because Java primitives are pass-by-value; passing around an int and then updating it wouldn't propagate the change through the rest of your system.

This would look like this:

public static boolean checkBST(TreeNode n) {
    WrapInt counter = new WrapInt();
    return checkBST(n, counter);
}

public static boolean checkBST(TreeNode n, WrapInt counter) {
    if(n == null) return true;

        // Check / recurse left
        if (!checkBST(n.left, counter)) return false;

        // Check current
        if (n.data <= counter.value) return false;
        counter.value = n.data;

        // Check / recurse right
        if (!checkBST(n.right, counter)) return false;

        return true; // All good!
}

Thanks for the quick answer. so basically to use the wrapper, I will need to create an instance of it and pass it as one of the function parameters? — vigdora, Apr 21 '15 at 11:38
Yes, because this allows checkBST to remain as a stateless static method. It then allows you to use the method from multple threads, because there's no global state. — Steve Chaloner, Apr 21 '15 at 11:42

score 1 · Answer 2 · answered Apr 21 '15 at 11:34

Here you go:

public static boolean checkBST(TreeNode n) {
     WrapInt i = new WrapInt();
     i.value = INTEGER.MIN_VALUE;
     doCheckBST(n, i);
}

private static boolean doCheckBST(TreeNode n, WrapInt last_printed) {
if(n == null) return true;

    // Check / recurse left
    if (!checkBST(n.left, last_printed)) return false;

    // Check current
    if (n.data <= last_printed.value) return false;
    last_printed.value = n.data;

    // Check / recurse right
    if (!checkBST(n.right, last_printed)) return false;

    return true; // All good!
}

score 1 · Answer 3 · answered Apr 21 '15 at 11:37

If there is the possibility that there will run 2+ sorts at the same time. The static will be used for both sortings. Both sortings have access to the same static value.

//thread 1
Sorting A = new Sorting(5,9,8);
A.sort();

//thread 2
Sorting B = new Sorting(999,100,7);
B.sort();

We cant predict which/how the thread is processed.

So this could end up in

A.checkBST(5)    // last_printed  = 5
B.checkBST(999)  // last_printed  = ??
B.checkBST(100)  // last_printed  = ??
A.checkBST(9)    // last_printed  = ??

... ...

If every sort instance has his own last_printed, you won't have synchronisation issues.

score 1 · Answer 4 · edited May 23 '17 at 12:14

I think this is more formal way how to avoid of public static context property (e.g for thread safety), which is not optimal approach in object programming. But there are standard Primitive wrapper classes as: https://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html which can be used instead of new classes. Generally Wrapper pattern can be more general than your example: What is a wrapper class?

score 0 · Answer 5 · answered Apr 21 '15 at 11:39

The problem with static variable is that another class/method or something can modify it and it will break your code. Can you make it like that:

Class WrapInt {
public int value=Integer.MIN_VALUE;
} 

public static boolean checkBST(TreeNode n,WrapInt lastPrinted) {
if(n == null) return true;

    // Check / recurse left
    if (!checkBST(n.left,lastPrinted)) return false;

    // Check current
    if (n.data <= lastPrinted.value) return false;
    lastPrinted.value = n.data;

    // Check / recurse right
    if (!checkBST(n.right,lastPrinted)) return false;

    return true; // All good!

}

Using wrapper class instead of static variables

5 Answers5