The C5 Generic Collection Library for C# and CLI
Niels Jørgen Kokholm, Peter Sestoft · 2006
as base bool break byte case catch char checked class const continue decimal default delegate do double else enum event explicit extern false finally fixed float for foreach goto if implicit in int interface internal is lock long namespace new null object operator out override params private protected public readonly ref return sbyte sealed short sizeof stackalloc static string struct switch this throw true try typeof uint ulong unchecked unsafe ushort using virtual void volatile Such word recognition can be performed efficiently using at least three different kinds of collections: Hash sets, tree sets, and sorted arrays. This example is in file KeywordRecognition.cs. To use a hash set, build it once and for all, then use it in a bool method. For instance, it may be bound to a static read-only field kw1, initialized in a static constructor, and then used in a method IsKeyword1: class KeywordRecognition { static readonly String[] keywordArray = { abstract, ..., while }; private static readonly ICollection kw1; static KeywordRecognition() { kw1 = new HashSet (); kw1.AddAll(keywordArray); } public static bool IsKeyword1(String s) { return kw1.Contains(s); } } In this code HashSet could be replaced with TreeSet or SortedArray . By far the fastest solution is to use a hash set. To a large extent that is because the string comparison is quite slow (due to locales or cultures) so the string comparer used by a tree set or sorted array is much slower than the string hash function and equality predicate used by the hash set. §11.2 Building a concordance for a text file 187 11.2 Building a concordance for a text file This example builds and prints a concordance from a text file: for every word in the file it finds the line numbers on which the word occurs. The example is in file Fileindex.cs. We can use a dictionary to map each word to a set of the numbers of lines on which it occurs; a set avoids duplicate line numbers for each word. The dictionary is a tree dictionary to make sure the words come out sorted when the dictionary is printed, and the set of line numbers is a tree set to make sure the line numbers for each word are sorted. For each word the line numbers are represented by a TreeSet and hence the entire concordance is represented by a TreeDictionary >. Method IndexFile builds the concordance for a given file name: static IDictionary > IndexFile(String filename) { IDictionary > index = new TreeDictionary >(); Regex delim = new Regex([^a-zA-Z0-9]+); using (TextReader rd = new StreamReader(filename)) { int lineno = 0; for (String line = rd.ReadLine(); line != null; line = rd.ReadLine()) { String[] res = delim.Split(line); lineno++; foreach (String s in res) if (s != ) { if (!index.Contains(s)) index[s] = new TreeSet (); index[s].Add(lineno); } } } return index; } Instead of a tree dictionary, one might have used a hash dictionary and then sort the entries before printing them. Instead of a tree set of line numbers one might have used a list (because the lines are scanned in order of increasing line numbers anyway) and either eliminate duplicates afterwards (see pattern 80), or use a hashed (array or linked) list to avoid duplicated during the construction. It is not clear that these alternatives would have been any more efficient. Using a tree dictionary and tree sets naturally achieves the absence of duplicates, and the result index returned by method IndexFile above will print in alphabetical order without further ado: foreach (String word in index.Keys) { Console.Write({0}: , word); foreach (int ln in index[word]) Console.Write({0} , ln); Console.WriteLine(); } 188 Convex hull in the plane §11.3 11.3 Convex hull in the plane The convex hull is the least convex set that encloses a given set of points. A point set is convex if every point between to points that belong to the set also belongs to the set: the set has no holes or inward dents. Figure 11.1 shows an example of several points and their convex hull, enclosed by a solid line.