A list is an ordered collection that becomes a practical word index when its elements are kept sorted. Sorting allows binary search without relying on a hash set. section 5.1.2
A sorted list supports two useful operations:
- Contains calls BinarySearch and checks whether the returned index is nonnegative. section 5.1.2
- StartsWith binary-searches for the prefix, converts a negative insertion result with ~i, then scans matching neighbors until the prefix no longer matches. section 5.1.2
- Contains costs O(m log n) for words of length m; prefix search adds O(m) work for every matching word and can reach O(mn). section 5.1.2
Prefix lookup
Given a sorted list of words, search for "app". BinarySearch identifies the first plausible position; iteration yields consecutive words beginning with that prefix and stops at the first nonmatching word. 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();
}
Inspect the complete C# implementation, including BinarySearch handling, iterator-based results, and the bitwise-complement insertion index. section 5.1.2
