查找TreeSet中以給定前綴開頭的字符串

Question

我試圖找到以給定前綴開頭的TreeSet<String>中的字符串。我發現前面的問題要求相同的東西— Searching for a record in a TreeSet on the fly —但給出的答案不適合我，因爲它假設字符串不包括Character.MAX_VALUE，我的可以。

（答案有使用treeSet.subSet(prefix, prefix + Character.MAX_VALUE)，這給之間prefix（含）prefix + Character.MAX_VALUE（獨家），其中就出來與prefix除了那些與prefix + Character.MAX_VALUE開始啓動所有字符串。但在所有的字符串我情況下，我需要找到與prefix開始所有串，包括那些與prefix + Character.MAX_VALUE開始。）

我怎樣才能做到這一點？

Answer 1

首先，我建議重新檢查您的要求。 Character.MAX_VALUE是U + FFFF，它不是一個有效的Unicode字符，永遠不會;所以我想不出你需要支持它的一個很好的理由。

但是，如果這個要求有一個很好的理由，那麼你需要「增加」你的前綴來計算最大的字符串，它大於以你的前綴開頭的所有字符串。例如，給定"city"，則需要"citz"。你可以做如下：

/** 
* @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當它沒有返回值：

/** 
* @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); 
    } 
} 

在看到它在行動：http://ideone.com/YvO4b3。