A sorted list stores words in lexicographic order so ordered searching can use binary search. It is a straightforward choice when the collection can be sorted ahead of time, supporting exact lookup and prefix matching with reasonable performance. section 5.1.2 section 5.0
The two core operations work as follows:
- Contains calls binary search and treats a nonnegative result as an exact match. section 5.1.2
- StartsWith binary-searches for the prefix, converts a negative insertion result with bitwise complement, then scans forward until the prefix no longer matches. section 5.1.2
- Exact lookup costs O(m log n), where n is the list size and m is the typical word length; prefix lookup adds O(m) work for every matching candidate. section 5.1.2
Listing 5.1 A sorted word list
class SortedWordList : IWords
{
private List<string> words;
public SortedWordList(List<string> words) #1
{
this.words = words;
}
public bool Contains(string word) => words.BinarySearch(word) >= 0; #2
public IEnumerable<string> StartsWith(string prefix)
{
int i = words.BinarySearch(prefix);
if (i < 0)
i = ~i; #3
for (; i < words.Count; i += 1)
{
string w = words[i];
if (!w.StartsWith(prefix)) #4
yield break;
yield return w;
}
}
public IEnumerator<string> GetEnumerator() => words.GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
A compact C# implementation exposes the sorted-list invariant, BinarySearch result handling, lazy prefix enumeration, and stopping condition. section 5.1.2
