dyaml.fastcharsearch source code

1 
2 //          Copyright Ferdinand Majerech 2011.
3 // Distributed under the Boost Software License, Version 1.0.
4 //    (See accompanying file LICENSE_1_0.txt or copy at
5 //          http://www.boost.org/LICENSE_1_0.txt)
6 
7 module dyaml.fastcharsearch;
8 
9 
10 import std.algorithm;
11 import std.conv;
12 
13 
14 package:
15 
16 /**
17  * Mixin used for fast searching for a character in string.
18  *
19  * Creates a lookup table to quickly determine if a character
20  * is present in the string. Size of the lookup table is limited;
21  * any characters not represented in the table will be checked
22  * by ordinary equality comparison.
23  *
24  * Params:  chars     = String to search in.
25  *          tableSize = Maximum number of bytes used by the table.
26  *
27  * Generated method: 
28  *     bool canFind(dchar c)
29  *
30  *     Determines if a character is in the string.
31  */
32 template FastCharSearch(dstring chars, uint tableSize = 256)
33 {
34     private mixin(searchCode!(chars, tableSize)());
35 }
36 
37 /// Generate the search table and the canFind method.
38 string searchCode(dstring chars, uint tableSize)() @safe pure //nothrow
39 {
40     import std.string;
41 
42     const tableSizeStr = tableSize.to!string;
43     ubyte[tableSize] table;
44     table[] = 0;
45 
46     //Characters that don't fit in the table.
47     dchar[] specialChars;
48 
49     foreach(c; chars)
50     {
51         if(c < tableSize) { table[c] = 1; }
52         else              { specialChars ~= c; }
53     }
54 
55     string specialCharsCode()
56     {
57         return specialChars.map!(c => q{cast(uint)c == %s}.format(cast(uint)c)).join(q{ || });
58     }
59 
60     const caseInTable = 
61     q{
62             if(c < %s)
63             {
64                 return cast(immutable(bool))table_[c];
65             }
66     }.format(tableSize);
67 
68     string code;
69     if(tableSize)
70     {
71         code ~= 
72         q{
73             static immutable ubyte[%s] table_ = [
74             %s];
75         }.format(tableSize, table[].map!(c => c ? q{true} : q{false}).join(q{, }));
76     }
77     code ~= 
78     q{
79         bool canFind(const dchar c) @safe pure nothrow @nogc 
80         {
81             %s
82 
83             return %s;
84         }
85     }.format(tableSize ? caseInTable : "", 
86              specialChars.length ? specialCharsCode() : q{false});
87 
88     return code;
89 }