1

I know references to objects in java are passed by copy , but the copy still points to the same memory in system , so after updating some data of the complex object in another function , the original data should me maintained. But interestingly something is going wrong here. I am working with Tries.

Here is my implementation of Trie, it's fairly custom implementation because of some custom rules:

public class Trie {
    boolean isEnd;
    Trie trie[] = new Trie[256];
    ArrayList<Integer> indexNode;

    public static Trie createTrieNode() {
        Trie temp = new Trie();
        temp.isEnd = false;
        temp.indexNode = new ArrayList<Integer>();
        for (int i = 0; i < temp.trie.length; i++) {
            temp.trie[i] = null;
        }

        return temp;
    }

    public static void insertIntoTrie(Trie root, char[] alpha, int index, int i) {
        if (root == null)
            root = createTrieNode();
        if (i < alpha.length)
            insertIntoTrie(root.trie[alpha[i] - 'a'], alpha, index, i + 1);
        else {
            if (root.isEnd == true) {
                root.indexNode.add(index);
            } else {
                root.isEnd = true;
                root.indexNode.add(index);
            }
        }

    }

}

Now my object root comes from this class and In the debugger I can see this statement being executed : root.isEnd = true;

Class:

 public class AnagramsTogether {
        public Trie root = new Trie();
        public void printAnagrams(String[] anagrams){
            char[] buffer;
            for (int i = 0; i < anagrams.length; i++) {
                buffer = anagrams[i].toCharArray();
                Arrays.sort(buffer);
              Trie.insertIntoTrie(root, buffer, i, 0);
            }
            AnagramsUtil.anagramUtil(root,anagrams);
        }
  }

But when when root is passed here AnagramsUtil.anagramUtil(root,anagrams);

public class AnagramsUtil {

    public static void anagramUtil(Trie root, String[] anagrams) {

        if (root.isEnd == true) {

            for (Iterator<Integer> iterator = root.indexNode.iterator(); iterator
                    .hasNext();) {
                Integer integer = (Integer) iterator.next();
                System.out.println(anagrams[integer]);
            }
        } else {
            for (int i = 0; i < root.trie.length; i++) {
                if (root.trie[i] == null)
                    continue;
                anagramUtil(root.trie[i], anagrams);
            }
        }
    }

}
public class Anagram{
                   public static String string[] = {"cat", "dog", "god","act", "tac","gdo"};
                   public static void main(String args){
                      new AnagramsTogether().printAnagrams(Anagram.string); 
                 }
}

This statement if (root.isEnd == true) in never executed and so is this is never executed anagramUtil(root.trie[i], anagrams); . The program just keep executing the continue statement. Which should not be the case as I've already seen root.trie[i] receiving values. Why does this happen?I am fairly new to java.

Arjun Verma
  • 105
  • 1
  • 6

3 Answers3

0

You have many Trie objects in your program and you are confusing them. If you check object identity (object number) with your debugger, you will see that they are not the same.

Mario Rossi
  • 7,651
  • 27
  • 37
0

You are saying that you see in the debugger the statement root.isEnd = true; to be executed however you don't mention for which object is executing.

Your insertIntoTrie() method is called recursively so, that statement is probably executed for the Trie objects that the root has in its trie[] array but not for the root object itself.

Since the actual execution depends on the arguments you are using to call printAnagrams(String[] anagrams) please add those to your question if you need a more specific answer.

Update: Ok after you have edited your question it is clear that you are making the mistake to misuse object references even though you know that all "...references to objects in java are passed by copy". Your insertIntoTrie() is faulty. It seems that you intend to create a new object if the argument root is null however that new object will be lost because root argument is a copy. At the end of your method if you print the whole trie[] member of your original root object (the one in the AnagramsTogether class) you will see that all objects are null.

c.s.
  • 4,786
  • 18
  • 32
0

In Java, null is not an object, it is only a special type. Therefore null hasn't got a reference. So that, for example:

Trie root = null;
insertIntoTrie(root, alpha, index, i); 
// after called this function, root = null

After called this function, root is still null because the variable root isn't yet an object before calling this function. So that there wasn't any reference of the variable root to be passed by copy in this calling.

Solution:

Change your function:

 public static void insertIntoTrie(Trie root, char[] alpha, int index, int i) {
    if (root == null)
        root = createTrieNode();
    if (i < alpha.length)
        insertIntoTrie(root.trie[alpha[i] - 'a'], alpha, index, i + 1);
    else {
        if (root.isEnd == true) {
            root.indexNode.add(index);
        } else {
            root.isEnd = true;
            root.indexNode.add(index);
        }
    }

}

Into :

public static void insertIntoTrie(Trie root, char[] alpha, int index, int i) {
    if (i < alpha.length) {
        if (root.trie[alpha[i] - 'a'] == null) {
            root.trie[alpha[i] - 'a'] = createTrieNode();
        }
        insertIntoTrie(root.trie[alpha[i] - 'a'], alpha, index, i + 1);
    }
    else {
        if (root.isEnd == true) {
            root.indexNode.add(index);
        } else {
            root.isEnd = true;
            root.indexNode.add(index);
        }
    }

}

This solution make sure that the root is always an object before passing to the insertIntoTrie(...) function.

Van Dan NGUYEN
  • 991
  • 5
  • 5