Java recursion: pass by reference

Question

I realize this is a hotly debated, controversial topic for Java programmers, but I believe my problem is somewhat unique. My algorithm REQUIRES pass by reference. I am doing a clockwise/counterclockwise pre-order traversal of a general tree (i.e. n-children) to assign virtual (x,y) coordinates. This simply means I count (and tag) the nodes of tree I visit as I visit them.

/**
 * Generates a "pre-ordered" list of the nodes contained in this object's subtree
 * Note: This is counterclockwise pre-order traversal
 * 
 * @param clockwise set to true for clockwise traversal and false for counterclockwise traversal
 * 
 * @return Iterator<Tree> list iterator
 */
public Iterator<Tree> PreOrder(boolean clockwise)
{
    LinkedList<Tree> list = new LinkedList<Tree>();
    if(!clockwise)
        PreOCC(this, list);
    else
        PreO(this,list);
    count = 0;
    return list.iterator();
}
private void PreOCC(Tree rt, LinkedList<Tree> list)
{
    list.add(rt);
    rt.setVirtual_y(count);
    count++;
    Iterator<Tree> ci = rt.ChildrenIterator();
    while(ci.hasNext())
        PreOCC(ci.next(), list);      
}
private void PreO(Tree rt, LinkedList<Tree> list, int count)
{
    list.add(rt);
    rt.setX_vcoordinate(count);
    Iterator<Tree> ci = rt.ReverseChildrenIterator();
    while(ci.hasNext())
        PreO(ci.next(), list, ++count);
}

Here I generate the structure of the tree:

Tree root = new Tree(new Integer(0));
root.addChild(new Tree(new Integer(1), root));
root.addChild(new Tree(new Integer(2), root));
root.addChild(new Tree(new Integer(3), root));
Iterator<Tree> ci = root.ChildrenIterator();
ci.next();
Tree select = ci.next();
select.addChild(new Tree(new Integer(4), select));
select.addChild(new Tree(new Integer(5), select));

And here is my output when I print the order the nodes are traversed and the coordinates it assigns to the respective node.

0 3 2 5 4 1
0 1 2 3 4 3

0 1 2 4 5 3
0 1 2 3 4 3

Note: The first two lines is a clockwise pre-order traversal and assignment of the x-coordinates. The next two lines are a counterclockwise pre-order traversal and assignment of they y-coordinates.

My question is how I can get the second lines to read: 0 1 2 3 4 5

EDIT 1: Here is the code I use to print the order I visit the nodes and the coordinates I assign.

Iterator<Tree> pre = root.PreOrder(true);
System.out.println("              \t");
while(pre.hasNext())
    System.out.print(pre.next() + "\t");

pre = root.PreOrder(true);
System.out.println();
System.out.println("x-coordinates:\t");
while(pre.hasNext())
System.out.print(pre.next().getVirtual_x() + "\t");

System.out.println();
System.out.println();

Iterator<Tree> preCC = root.PreOrder(false);
System.out.println("              \t");
while(preCC.hasNext())
    System.out.print(preCC.next() + "\t");

preCC = root.PreOrder(false);
System.out.println();
System.out.println("x-coordinates:\t");
while(preCC.hasNext())
System.out.print(preCC.next().getVirtual_y() + "\t");

Also here is a quote to better explain the x,y coordinates. the vertices.the y-coordinates for the vertices.

Compute the counterclockwise pre-ordering of the vertices of T (the ordering are numbered from 0 to n − 1), use them as the x-coordinates for the vertices.

Compute the clockwise pre-ordering of the vertices of T (the ordering are numbered from 0 to n − 1), use them as the y-coordinates for the vertices.

Answer 1

Java's pass by value, always - for both primitives and objects. It's references that are passed for non-primitives, so you can change the state of the objects they point to but not the references themselves.

From James Gosling in "The Java Programming Language":

"...There is exactly one parameter passing mode in Java - pass by value - and that keeps things simple. .."

I think that's the final authority on this.

I realize this is a hotly debated, controversial topic for Java programmers

No, there's no debate. This has been baked into the language since the beginning by James Gosling. If you think it's controversial, you're sadly deluded or ignorant.

Answer 2

actually, there is a way to pass by reference in Java:

class Pointer {
    private Object ptr;
    public Pointer(Object v)  { set(v);  }
    public void set(Object v) { ptr = v; }
    public Object get()       { return ptr; }
}

and you use them:

public void swap(Pointer a, Pointer b) {
    Object tmp = a.get();
    a.set(b.get());
    b.set(tmp);
}

and call swap like this:

public static void main(String[] args) {
    Integer one = 1; 
    Integer two = 2;
    Pointer pone; pone.set(one);
    Pointer ptwo; ptwo.set(two);
    swap(pone, ptwo);
    System.out.println((Integer) pone.get());
    System.out.println((Integer) ptwo.get());
}

though, if you're really doing this, then you're probably either insane or just not thinking in Java yet.

Answer 3

You don't require pass by reference, you require a function with side effects. Pass by reference would be one way to achieve this; using a mutable object as a function argument would be another.

private void PreO(Tree rt, LinkedList<Tree> list, int[] count)
{
    list.add(rt);
    rt.setX_vcoordinate(count[0]);
    Iterator<Tree> ci = rt.ReverseChildrenIterator();
    while(ci.hasNext()) {
        ++count[0];
        PreO(ci.next(), list, count);
    }
}