与えられた接頭辞で始まるツリーセット内の文字列を見つける

Question

TreeSet<String>の接頭辞で始まる文字列を見つけようとしています。私は前の質問で同じことを尋ねました— Searching for a record in a TreeSet on the fly —しかし、文字列にCharacter.MAX_VALUEが含まれていないと仮定しているので、そこに与えられた答えは私にとってはうまくいきません。

（答えはそこ除くprefixprefix + Character.MAX_VALUEで始まるもので始まるすべての文字列に出てくるこれは、prefix）（包括的でprefix + Character.MAX_VALUE（排他）の間のすべての文字列を与える、treeSet.subSet(prefix, prefix + Character.MAX_VALUE)を使用することです。しかし、私の中ケース私はがprefix + Character.MAX_VALUEで始まるものも含めてprefixで始まるすべての文字列を、見つける必要があります。）

私はこれをどのように行うことができますか？

Answer 1

まず、要件を再検討することをお勧めします。 Character.MAX_VALUEはU + FFFFですが、これは有効なUnicode文字ではありません。だから私はあなたがそれをサポートする必要がある理由を考えることができません。

しかし、その理由がある場合は、—は接頭辞で始まるすべての文字列よりも小さい文字列を計算するために接頭辞を "増やす"必要があります。たとえば、"city"と入力すると、"citz"が必要です。

/** 
* @param allElements - a SortedSet of strings. This set must use the 
*      natural string ordering; otherwise this method 
*      may not behave as intended. 
* @param prefix 
* @return The subset of allElements containing the strings that start 
*   with prefix. 
*/ 
private static SortedSet<String> getElementsWithPrefix(
     final SortedSet<String> allElements, final String prefix) { 

    final Optional<String> endpoint = incrementPrefix(prefix); 

    if (endpoint.isPresent()) { 
     return allElements.subSet(prefix, endpoint.get()); 
    } else { 
     return allElements.tailSet(prefix); 
    } 
} 

がでアクションでそれを参照してください。

/** 
* @param prefix 
* @return The least string that's greater than all strings starting with 
*   prefix, if one exists. Otherwise, returns Optional.empty(). 
*   (Specifically, returns Optional.empty() if the prefix is the 
*   empty string, or is just a sequence of Character.MAX_VALUE-s.) 
*/ 
private static Optional<String> incrementPrefix(final String prefix) { 
    final StringBuilder sb = new StringBuilder(prefix); 

    // remove any trailing occurrences of Character.MAX_VALUE: 
    while (sb.length() > 0 && sb.charAt(sb.length() - 1) == Character.MAX_VALUE) { 
     sb.setLength(sb.length() - 1); 
    } 

    // if the prefix is empty, then there's no upper bound: 
    if (sb.length() == 0) { 
     return Optional.empty(); 
    } 

    // otherwise, increment the last character and return the result: 
    sb.setCharAt(sb.length() - 1, (char) (sb.charAt(sb.length() - 1) + 1)); 
    return Optional.of(sb.toString()); 
} 

を、それを使用するには、あなたはそれが何も返さない時には、上記の方法は、文字列を返すsubSet、およびtailSetを使用する必要があります。あなたは次のようにそれを行うことができます：http://ideone.com/YvO4b3。