Javaでのオブジェクト参照の変更

Question

Javaで接尾辞トライを実装しようとしています。トライにはルートノードがあり、トライにはエッジが接続されています。しかし、constructTrie(T)（文字列Tを与えられたtrieを構築する）やsubstring(S,T)（SがTの部分文字列かどうかを調べる）のような関数を実装するときは、現在検討中のノードcNodeを検討しています。

cNodeの値を正しく変更しているかどうかわかりません。以下はクラスTrieです。

import java.util.*; 

class Trie{ 

    protected Node root = null; 

    public Trie(){ 
     Node n = new Node(); 
     root = n; 
    } 

    // Constructs a trie for a given string T 
    public void constructTrie(String T){ 
     ArrayList<String> suffixArray = new ArrayList<String>(); 
     T += "#"; // Terminator 
     int length = T.length(); 
     // Creates suffix array and removes first letter with every iteration 
     for(int i=0; i<length; i++){ 
      suffixArray.add(T); 
      T = T.substring(1); 
     } 

     // Goes through suffix array 
     for(int i=0; i<length; i++){ 
      Node cNode = null; 
      cNode = root; // Current node 
      int j = 0; 
      // Goes through each letter of an entry in the suffix array 
      while(j < (suffixArray.get(i)).length()){ 
       int index = cNode.findEdge((suffixArray.get(i)).charAt(j)); 
       // If an edge is found at the root with the current letter, update cNode and remove the letter from word 
       if(index != -1){ 
        cNode = cNode.getEdge(index).getNode(); // Gets node pointed at by edge and sets it as current node 
        String replace = (suffixArray.get(i)).substring(1); 
        suffixArray.set(0, replace); // Erases first letter of suffix 
        j++; 
        System.out.println(i + " " + j + " " + replace); 
       } 
       // If an edge is not found at the root, write the whole word 
       else{ 
        for(int k=0; k<(suffixArray.get(i)).length(); k++){ 
         Edge e = new Edge((suffixArray.get(i)).charAt(k)); // Creates edge with current letter of current entry of the suffix array 
         Node n = new Node(); // Creates node to be pointed at by edge 
         e.setNode(n); 
         cNode.newEdge(e); 
         cNode = n; // Updates current node 
        } 
        j = (suffixArray.get(i)).length(); // If the word is written, we break from the while and move on to the next suffix array entry 
       } 
      } 
     } 
    } 

    // Checks if S is a substring of T 
    public boolean substring(String S, String T){ 
     constructTrie(T); 
     Node cNode = null; 
     cNode = root; 

     int index; 
     for(int i=0; i<S.length(); i++){ 
      index = cNode.findEdge(S.charAt(i)); 
      if(index == -1) 
       return false; // Substring was not found because a path was not followed 
      cNode = (cNode.getEdge(index)).getNode(); // Reset current node to the next node in the path 
     } 
     return true; // Substring was found 
    } 

具体的には、Iタイプトライのオブジェクトが作成されるときrootを初期化、クラス変数としてNode root = nullを設定し、方法に示すようにcNodeを変化させてい？コードはエラーなしでコンパイルされますが、テスト時に必ずしも正しい応答を出力するとは限りません。テストされると、 'es'は 'pest'の部分文字列ではないことを出力します。

Answer 1

クラスのメソッドのフィールドを更新すると、クラスはスレッドセーフではありません。あなたのメソッドには、クラスのユーザーが期待するものではないかもしれない副作用があります。

を考えてみましょう：あなたはsubstringメソッドでrootフィールドを更新している場合は、最初のサブストリングの呼び出しがトライを変更するので

Trie t = new Trie("My String"); 

boolean startsWithMy = t.substring("My"); 
boolean startsWithMyString = t.substring("My String"); 

を、そして第二の呼び出しは、あなたが期待するかもしれない何をしません。

public class Trie { 
    private final Node root; 

    public Trie(String input) { 
     // Construct the Trie here and assign it to root: 
     this.root = constructTry(input); 
    } 

    public boolean substring(String part) { 
     // Create a local Node variable: 
     Node currentNode = root; 

     // Navigate the Trie here using currentNode: 
     // ... 

     return result; 
    } 
} 

あなたも、（メソッドを追加することができます：あなたは最小限の副作用で使いやすい、再利用可能なクラスを作成したい場合は

、その後、私はどうなるのかは、この基本的なパターン、次のクラスを記述していますTrieのサブパートを返すために：

public Trie subTrie(String part) { 
    // Find the Node here that matches the substring part, and return it. 
    // If nothing found, then throw NoSuchElementException or return null. 

    Node subNode = findNode(part); 

    if (subNode == null) { 
     throw new NoSuchElementException("No element starting with: " + part); 
    } 

    // Constructs a new Trie with a different root node using a 2nd constructor option 
    return new Trie(subNode); 
} 

Answer 2

あなたのルートノードの参照は、それにガーベッジを追加して変更しています。

Trie trie = new Trie(); 
trie.substring("es", "pest"); // this returns true. 

をしかし、あなたは

Trie trie = new Trie(); 
trie.substring("es", "pest"); 
trie.substring("te", "Master"); 

を行う場合は、サブストリングの2回目の呼び出し場所をあなたの最後の呼び出しの左をピックアップします： レッツは、あなたがこれを行うと言います。ルートは既に初期化されており、 "pest"という単語のツリーが含まれていますroot(p, e, s, t, #)。 2回目の呼び出しの後に、root(M, a, s, t, e, r, #)の代わりにroot(p, e, s, t, #, M, a, r)となります。それはまったく別の言葉です。したがってteはpest#Marの部分文字列ではありません。

しかし、あなたは、@のjohn16384に応じてそれを実装する場合は、副作用を排除する、次の操作を行うことを余儀なくされます。

Trie trie = new Trie("pest"); 
trie.substring("es"); // this returns true. 

trie = new Trie("Master"); 
trie.substring("te") // this returns true. 

は、この方法はなかれクリーンなルートから開始するようにあなたを強制的にそれをやって。以下の実装を参照してください：

class Trie { 

protected Node root = null; 

public Trie(String T) { 
    root = constructTrie(T); 
} 

// Constructs a trie for a given string T 
private Node constructTrie(String T) { 
    ArrayList<String> suffixArray = new ArrayList<String>(); 
    T += "#"; // Terminator 
    int length = T.length(); 
    // Creates suffix array and removes first letter with every iteration 
    for (int i = 0; i < length; i++) { 
     suffixArray.add(T); 
     T = T.substring(1); 
    } 
    Node localRoot = new Node(); 
    // Goes through suffix array 
    for (int i = 0; i < length; i++) { 
     Node cNode = localRoot; 
     int j = 0; 
     // Goes through each letter of an entry in the suffix array 
     while (j < (suffixArray.get(i)).length()) { 
      int index = cNode.findEdge((suffixArray.get(i)).charAt(j)); 
      // If an edge is found at the root with the current letter, update cNode and remove the letter from word 
      if (index != -1) { 
       cNode = cNode.getEdge(index).getNode(); // Gets node pointed at by edge and sets it as current node 
       String replace = (suffixArray.get(i)).substring(1); 
       suffixArray.set(0, replace); // Erases first letter of suffix 
       j++; 
       System.out.println(i + " " + j + " " + replace); 
      } 
      // If an edge is not found at the root, write the whole word 
      else { 
       for (int k = 0; k < (suffixArray.get(i)).length(); k++) { 
        Edge e = new Edge((suffixArray.get(i)).charAt(k)); // Creates edge with current letter of current entry of the suffix array 
        Node n = new Node(); // Creates node to be pointed at by edge 
        e.setNode(n); 
        cNode.newEdge(e); 
        cNode = n; // Updates current node 
       } 
       j = (suffixArray.get(i)).length(); // If the word is written, we break from the while and move on to the next suffix array entry 
      } 
     } 
    } 
    return localRoot; 
} 

// Checks if S is a substring of T 
public boolean substring(String S) { 
    Node cNode = root; 
    int index; 
    for (int i = 0; i < S.length(); i++) { 
     index = cNode.findEdge(S.charAt(i)); 
     if (index == -1) 
      return false; // Substring was not found because a path was not followed 
     cNode = (cNode.getEdge(index)).getNode(); // Reset current node to the next node in the path 
    } 
    return true; // Substring was found 
} 
}