| 1 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html><head><title>The multi_pass</title> |
|---|
| 2 | |
|---|
| 3 | <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> |
|---|
| 4 | <link rel="stylesheet" href="theme/style.css" type="text/css"></head> |
|---|
| 5 | <body> |
|---|
| 6 | <table width="100%" border="0" background="theme/bkd2.gif" cellspacing="2"> |
|---|
| 7 | <tbody><tr> |
|---|
| 8 | <td width="10"> |
|---|
| 9 | <br> |
|---|
| 10 | </td> |
|---|
| 11 | <td width="85%"> <font size="6" face="Verdana, Arial, Helvetica, sans-serif"><b>The |
|---|
| 12 | multi_pass</b></font> </td> |
|---|
| 13 | <td width="112"><a href="http://spirit.sf.net"><img src="theme/spirit.gif" width="112" height="48" align="right" border="0"></a></td> |
|---|
| 14 | </tr> |
|---|
| 15 | </tbody></table> |
|---|
| 16 | <br> |
|---|
| 17 | <table border="0"> |
|---|
| 18 | <tbody><tr> |
|---|
| 19 | <td width="10"><br> |
|---|
| 20 | </td> |
|---|
| 21 | <td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td> |
|---|
| 22 | <td width="30"><a href="trees.html"><img src="theme/l_arr.gif" border="0"></a></td> |
|---|
| 23 | <td width="30"><a href="file_iterator.html"><img src="theme/r_arr.gif" border="0"></a></td> |
|---|
| 24 | </tr> |
|---|
| 25 | </tbody></table> |
|---|
| 26 | <p>Backtracking in Spirit requires the use of the following types of iterator: |
|---|
| 27 | forward, bidirectional, or random access. Because of backtracking, input iterators |
|---|
| 28 | cannot be used. Therefore, the standard library classes istreambuf_iterator |
|---|
| 29 | and istream_iterator, that fall under the category of input iterators, cannot |
|---|
| 30 | be used. Another input iterator that is of interest is one that wraps a lexer, |
|---|
| 31 | such as LEX.</p> |
|---|
| 32 | <table width="80%" border="0" align="center"> |
|---|
| 33 | <tbody><tr> |
|---|
| 34 | <td class="note_box"> <img src="theme/note.gif" width="16" height="16"> <b>Input |
|---|
| 35 | Iterators</b> <br> |
|---|
| 36 | <br> |
|---|
| 37 | In general, Spirit is a backtracking parser. This is not an absolute requirement |
|---|
| 38 | though. In the future, we shall see more deterministic parsers that require |
|---|
| 39 | no more than 1 character (token) of lookahead. Such parsers allow us to |
|---|
| 40 | use input iterators such as the istream_iterator as is. </td> |
|---|
| 41 | </tr> |
|---|
| 42 | </tbody></table> |
|---|
| 43 | <p> Unfortunately, with an input iterator, there is no way to save an iterator |
|---|
| 44 | position, and thus input iterators will not work with backtracking in Spirit. |
|---|
| 45 | One solution to this problem is to simply load all the data to be parsed into |
|---|
| 46 | a container, such as a vector or deque, and then pass the begin and end of the |
|---|
| 47 | container to Spirit. This method can be too memory intensive for certain applications, |
|---|
| 48 | which is why the multi_pass iterator was created.</p> |
|---|
| 49 | <p> The multi_pass iterator will convert any input iterator into a forward iterator |
|---|
| 50 | suitable for use with Spirit. multi_pass will buffer data when needed and will |
|---|
| 51 | discard the buffer when only one copy of the iterator exists.</p> |
|---|
| 52 | <p> A grammar must be designed with care if the multi_pass iterator is used. Any rule that may |
|---|
| 53 | need to backtrack, such as one that contains an alternative, will cause data to be buffered. The rules that are optimal to |
|---|
| 54 | use are sequence and repetition. Sequences of the form <tt>a >> b</tt> |
|---|
| 55 | will not buffer data at all. Any rule that repeats, such as kleene_star (<tt>*a</tt>) |
|---|
| 56 | or positive such as (<tt>+a</tt>), will only buffer the data for the current |
|---|
| 57 | repetition.</p> |
|---|
| 58 | <p> In typical grammars, ambiguity and therefore lookahead is often localized. |
|---|
| 59 | In fact, many well designed languages are fully deterministic and require no |
|---|
| 60 | lookahead at all. Peeking at the first character from the input will immediately |
|---|
| 61 | determine the alternative branch to take. Yet, even with highly ambiguous grammars, |
|---|
| 62 | alternatives are often of the form <tt>*(a | b | c | d)</tt>. The input iterator |
|---|
| 63 | moves on and is never stuck at the beginning. Let's look at a Pascal snippet |
|---|
| 64 | for example:</p> |
|---|
| 65 | <pre> <code><span class="identifier">program </span><span class="special">=<br> </span><span class="identifier"> programHeading </span><span class="special">>> </span><span class="identifier">block </span><span class="special">>> </span><span class="literal">'.'<br> </span><span class="special"> ;<br><br> </span><span class="identifier">block </span><span class="special">=<br> *( </span><span class="identifier">labelDeclarationPart<br> </span><span class="special">| </span><span class="identifier">constantDefinitionPart<br> </span><span class="special">| </span><span class="identifier">typeDefinitionPart<br> </span><span class="special"> | </span><span class="identifier">variableDeclarationPart<br> </span><span class="special">| </span><span class="identifier"> procedureAndFunctionDeclarationPart<br> </span><span class="special"> )<br> >> </span><span class="identifier">statementPart<br> </span><span class="special">;<br></span></code></pre> |
|---|
| 66 | <p> Notice the alternatives inside the Kleene star in the rule block . The rule |
|---|
| 67 | gobbles the input in a linear manner and throws away the past history with each |
|---|
| 68 | iteration. As this is fully deterministic LL(1) grammar, each failed alternative |
|---|
| 69 | only has to peek 1 character (token). The alternative that consumes more than |
|---|
| 70 | 1 character (token) is definitely a winner. After which, the Kleene star moves |
|---|
| 71 | on to the next.</p> |
|---|
| 72 | <p>Be mindful if you use the free parse functions. |
|---|
| 73 | All of these make a copy of the iterator passed to them.<br> |
|---|
| 74 | </p> |
|---|
| 75 | <p>Now, after the lecture on the features to be careful with when using multi_pass, |
|---|
| 76 | you may think that multi_pass is way too restrictive to use. That's |
|---|
| 77 | not the case. If your grammar is deterministic, you can make use of flush_multi_pass in your grammar to ensure that data is not buffered when unnecessary.<br> |
|---|
| 78 | </p> |
|---|
| 79 | |
|---|
| 80 | <p> Again, following up the example we started to use in the section on the scanner |
|---|
| 81 | . Here's an example using the multi_pass: This time around we are extracting |
|---|
| 82 | our input from the input stream using an istreambuf_iterator.</p> |
|---|
| 83 | <pre> <span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">spirit</span><span class="special">/</span><span class="identifier">core</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> |
|---|
| 84 | <code><span class="preprocessor"> #include </span><span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">spirit</span><span class="special">/</span><span class="identifier">iterator</span><span class="special">/</span><span class="identifier">multi_pass</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span><span class="comment"> |
|---|
| 85 | |
|---|
| 86 | </span><span class="keyword">using namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">spirit</span><span class="special">; |
|---|
| 87 | </span><span class="keyword">using namespace</span> <span class="identifier">std</span><span class="special">;</span> |
|---|
| 88 | |
|---|
| 89 | <span class="identifier">ifstream in</span><span class="special">(</span><span class="string">"input_file.txt"</span><span class="special">); </span><span class="comment">// we get our input from this file<br><br> </span><span class="keyword">typedef char </span><span class="identifier">char_t</span><span class="special">;</span> |
|---|
| 90 | <span class="keyword">typedef </span><span class="identifier">multi_pass</span><span class="special"><</span><span class="identifier">istreambuf_iterator</span><span class="special"><</span><span class="identifier">char_t</span><span class="special">> > </span><span class="identifier">iterator_t</span><span class="special">;</span> |
|---|
| 91 | |
|---|
| 92 | <span class="keyword">typedef</span> <span class="identifier">skip_parser_iteration_policy</span><span class="special"><</span><span class="identifier">space_parser</span><span class="special">></span> <span class="identifier">iter_policy_t</span><span class="special">;</span> |
|---|
| 93 | <span class="keyword">typedef</span> <span class="identifier">scanner_policies</span><span class="special"><</span>iter_policy_t<span class="special">></span> <span class="identifier">scanner_policies_t</span><span class="special">;</span> |
|---|
| 94 | <span class="keyword">typedef</span> <span class="identifier">scanner</span><span class="special"><</span>iterator_t, scanner_policies_t<span class="special">></span> <span class="identifier">scanner_t</span><span class="special">;</span> |
|---|
| 95 | |
|---|
| 96 | <span class="keyword">typedef</span> rule<span class="special"><</span>scanner_t<span class="special">></span> <span class="identifier">rule_t</span><span class="special">;</span> |
|---|
| 97 | |
|---|
| 98 | <span class="identifier">iter_policy_t</span> <span class="identifier">iter_policy</span><span class="special">(</span><span class="identifier">space_p</span><span class="special">);</span> |
|---|
| 99 | <span class="identifier">scanner_policies_t</span> <span class="identifier">policies</span><span class="special">(</span><span class="identifier">iter_policy</span><span class="special">);</span> |
|---|
| 100 | iterator_t first( |
|---|
| 101 | make_multi_pass(std::istreambuf_iterator<char_t>(in))); |
|---|
| 102 | |
|---|
| 103 | scanner_t <span class="identifier">scan</span><span class="special">(</span> |
|---|
| 104 | first<span class="special">,</span> make_multi_pass(std::istreambuf_iterator<span class="special"><</span><span class="identifier">char_t</span><span class="special">>()),</span> |
|---|
| 105 | <span class="identifier">policies</span><span class="special">)</span>; |
|---|
| 106 | <span class="special"><br> </span><span class="identifier">rule_t n_list </span><span class="special">= </span><span class="identifier">real_p </span><span class="special">>> *(</span><span class="literal">',' </span><span class="special">>> </span><span class="identifier">real_p</span><span class="special">);<br> </span><span class="identifier">match</span><span class="special"><></span><span class="identifier"> m </span><span class="special">= </span><span class="identifier">n_list</span><span class="special">.</span><span class="identifier">parse</span><span class="special">(</span><span class="identifier">scan</span><span class="special">);<br></span></code></pre> |
|---|
| 107 | <a name="flush_multi_pass"></a> |
|---|
| 108 | <h2>flush_multi_pass</h2> |
|---|
| 109 | <p> There is a predefined pseudo-parser called flush_multi_pass. When this parser |
|---|
| 110 | is used with multi_pass, it will call multi_pass::clear_queue(). This will cause |
|---|
| 111 | any buffered data to be erased. This also will invalidate all other copies of |
|---|
| 112 | multi_pass and they should not be used. If they are, an boost::illegal_backtracking |
|---|
| 113 | exception will be thrown.</p> |
|---|
| 114 | <a name="multi_pass_policies"></a> |
|---|
| 115 | <h2>multi_pass Policies</h2> |
|---|
| 116 | <p> multi_pass is a templated policy driven class. The description of multi_pass |
|---|
| 117 | above is how it was originally implemented (before it used policies), and is |
|---|
| 118 | the default configuration now. But, multi_pass is capable of much more. Because |
|---|
| 119 | of the open-ended nature of policies, you can write your own policy to make |
|---|
| 120 | multi_pass behave in a way that we never before imagined.</p> |
|---|
| 121 | <p> The multi_pass class has five template parameters:</p> |
|---|
| 122 | <ul> |
|---|
| 123 | <li>InputT - The type multi_pass uses to acquire it's input. This is typically |
|---|
| 124 | an input iterator, or functor.</li> |
|---|
| 125 | <li>InputPolicy - A class that defines how multi_pass acquires it's input. The |
|---|
| 126 | InputPolicy is parameterized by InputT.</li> |
|---|
| 127 | <li>OwnershipPolicy - This policy determines how multi_pass deals with it's |
|---|
| 128 | shared components.</li> |
|---|
| 129 | <li>CheckingPolicy - This policy determines how checking for invalid iterators |
|---|
| 130 | is done.</li> |
|---|
| 131 | <li>StoragePolicy - The buffering scheme used by multi_pass is determined and |
|---|
| 132 | managed by the StoragePolicy.</li> |
|---|
| 133 | </ul> |
|---|
| 134 | <a name="predefined_policies"></a> |
|---|
| 135 | <h2>Predefined policies</h2> |
|---|
| 136 | <p> All predefined multi_pass policies are in the namespace boost::spirit::multi_pass_policies.</p> |
|---|
| 137 | <a name="predefined_inputpolicy_classes"></a> |
|---|
| 138 | <h3>Predefined InputPolicy classes</h3> |
|---|
| 139 | <a name="input_iterator"></a> |
|---|
| 140 | <h4>input_iterator</h4> |
|---|
| 141 | <p> This policy directs multi_pass to read from an input iterator of type InputT.</p> |
|---|
| 142 | <a name="lex_input"></a> |
|---|
| 143 | <h4>lex_input</h4> |
|---|
| 144 | <p> This policy obtains it's input by calling yylex(), which would typically be |
|---|
| 145 | provided by a scanner generated by LEX. If you use this policy your code must |
|---|
| 146 | link against a LEX generated scanner.</p> |
|---|
| 147 | <a name="functor_input"></a> |
|---|
| 148 | <h4>functor_input</h4> |
|---|
| 149 | <p> This input policy obtains it's data by calling a functor of type InputT. The |
|---|
| 150 | functor must meet certain requirements. It must have a typedef called result_type |
|---|
| 151 | which should be the type returned from operator(). Also, since an input policy |
|---|
| 152 | needs a way to determine when the end of input has been reached, the functor |
|---|
| 153 | must contain a static variable named eof which is comparable to a variable of |
|---|
| 154 | result_type.</p> |
|---|
| 155 | <a name="predefined_ownershippolicy_classes"></a> |
|---|
| 156 | <h3>Predefined OwnershipPolicy classes</h3> |
|---|
| 157 | <a name="ref_counted"></a> |
|---|
| 158 | <h4>ref_counted</h4> |
|---|
| 159 | <p> This class uses a reference counting scheme. multi_pass will delete it's shared |
|---|
| 160 | components when the count reaches zero.</p> |
|---|
| 161 | <a name="first_owner"></a> |
|---|
| 162 | <h4>first_owner</h4> |
|---|
| 163 | <p> When this policy is used, the first multi_pass created will be the one that |
|---|
| 164 | deletes the shared data. Each copy will not take ownership of the shared data. |
|---|
| 165 | This works well for spirit, since no dynamic allocation of iterators is done. |
|---|
| 166 | All copies are made on the stack, so the original iterator has the longest lifespan.</p> |
|---|
| 167 | <a name="predefined_checkingpolicy_classes"></a> |
|---|
| 168 | <h3>Predefined CheckingPolicy classes</h3> |
|---|
| 169 | <a name="no_check"></a> |
|---|
| 170 | <h4>no_check</h4> |
|---|
| 171 | <p> This policy does no checking at all.</p> |
|---|
| 172 | <a name="buf_id_check"></a> |
|---|
| 173 | <h4>buf_id_check</h4> |
|---|
| 174 | <p> buf_id_check keeps around a buffer id, or a buffer age. Every time clear_queue() |
|---|
| 175 | is called on a multi_pass iterator, it is possible that all other iterators |
|---|
| 176 | become invalid. When clear_queue() is called, buf_id_check increments the buffer |
|---|
| 177 | id. When an iterator is dereferenced, this policy checks that the buffer id |
|---|
| 178 | of the iterator matches the shared buffer id. This policy is most effective |
|---|
| 179 | when used together with the std_deque StoragePolicy. It should not be used with |
|---|
| 180 | the fixed_size_queue StoragePolicy, because it will not detect iterator dereferences |
|---|
| 181 | that are out of range.</p> |
|---|
| 182 | <a name="full_check"></a> |
|---|
| 183 | <h4>full_check</h4> |
|---|
| 184 | <p> This policy has not been implemented yet. When it is, it will keep track of |
|---|
| 185 | all iterators and make sure that they are all valid.</p> |
|---|
| 186 | <a name="predefined_storagepolicy_classes"></a> |
|---|
| 187 | <h3>Predefined StoragePolicy classes</h3> |
|---|
| 188 | <a name="std_deque"></a> |
|---|
| 189 | <h4>std_deque</h4> |
|---|
| 190 | <p> This policy keeps all buffered data in a std::deque. All data is stored as |
|---|
| 191 | long as there is more than one iterator. Once the iterator count goes down to |
|---|
| 192 | one, and the queue is no longer needed, it is cleared, freeing up memory. The |
|---|
| 193 | queue can also be forcibly cleared by calling multi_pass::clear_queue().</p> |
|---|
| 194 | <a name="fixed_size_queue_lt_n_gt_"></a> |
|---|
| 195 | <h4>fixed_size_queue<N></h4> |
|---|
| 196 | <p> fixed_size_queue keeps a circular buffer that is size N+1 and stores N elements. |
|---|
| 197 | fixed_size_queue is a template with a std::size_t parameter that specified the |
|---|
| 198 | queue size. It is your responsibility to ensure that N is big enough for your |
|---|
| 199 | parser. Whenever the foremost iterator is incremented, the last character of |
|---|
| 200 | the buffer is automatically erased. Currently there is no way to tell if an |
|---|
| 201 | iterator is trailing too far behind and has become invalid. No dynamic allocation |
|---|
| 202 | is done by this policy during normal iterator operation, only on initial construction. |
|---|
| 203 | The memory usage of this StoragePolicy is set at N+1 bytes, unlike std_deque, |
|---|
| 204 | which is unbounded.</p> |
|---|
| 205 | <a name="combinations__how_to_specify_your_own_custom_multi_pass"></a> |
|---|
| 206 | <h2>Combinations: How to specify your own custom multi_pass</h2> |
|---|
| 207 | <p> The beauty of policy based designs is that you can mix and match policies |
|---|
| 208 | to create your own custom class by selecting the policies you want. Here's an |
|---|
| 209 | example of how to specify a custom multi_pass that wraps an istream_iterator<char>, |
|---|
| 210 | and is slightly more efficient than the default because it uses the first_owner |
|---|
| 211 | OwnershipPolicy and the no_check CheckingPolicy:</p> |
|---|
| 212 | <pre> <code><span class="keyword">typedef </span><span class="identifier">multi_pass</span><span class="special"><<br> </span><span class="identifier">istream_iterator</span><span class="special"><</span><span class="keyword">char</span><span class="special">>,<br> </span><span class="identifier">multi_pass_policies</span><span class="special">::</span><span class="identifier">input_iterator</span><span class="special">,<br> </span><span class="identifier">multi_pass_policies</span><span class="special">::</span><span class="identifier">first_owner</span><span class="special">,<br> </span><span class="identifier">multi_pass_policies</span><span class="special">::</span><span class="identifier">no_check</span><span class="special">,<br> </span><span class="identifier">multi_pass_policies</span><span class="special">::</span><span class="identifier">std_deque<br> </span><span class="special">> </span><span class="identifier">first_owner_multi_pass_t</span><span class="special">;<br></span></code></pre> |
|---|
| 213 | <p> The default template parameters for multi_pass are: input_iterator InputPolicy, |
|---|
| 214 | ref_counted OwnershipPolicy, buf_id_check CheckingPolicy and std_deque StoragePolicy. |
|---|
| 215 | So if you use multi_pass<istream_iterator<char> > you will get those |
|---|
| 216 | pre-defined behaviors while wrapping an istream_iterator<char>.</p> |
|---|
| 217 | <p> There is one other pre-defined class called look_ahead. look_ahead has two |
|---|
| 218 | template parameters: InputT, the type of the input iterator to wrap, and a std::size_t |
|---|
| 219 | N, which specifies the size of the buffer to the fixed_size_queue policy. While |
|---|
| 220 | the default multi_pass configuration is designed for safey, look_ahead is designed |
|---|
| 221 | for speed. look_ahead is derived from a multi_pass with the following policies: |
|---|
| 222 | input_iterator InputPolicy, first_owner OwnershipPolicy, no_check CheckingPolicy, |
|---|
| 223 | and fixed_size_queue<N> StoragePolicy.</p> |
|---|
| 224 | <a name="how_to_write_a_functor_for_use_with_the_functor_input_inputpolicy"></a> |
|---|
| 225 | <h3>How to write a functor for use with the functor_input InputPolicy</h3> |
|---|
| 226 | <p> If you want to use the functor_input InputPolicy, you can write your own functor |
|---|
| 227 | that will supply the input to multi_pass. The functor must satisfy two requirements. |
|---|
| 228 | It must have a typedef result_type which specifies the return type of operator(). |
|---|
| 229 | This is standard practice in the STL. Also, it must supply a static variable |
|---|
| 230 | called eof which is compared against to know whether the input has reached the |
|---|
| 231 | end. Here is an example:</p> |
|---|
| 232 | <pre> <code><span class="keyword">class </span><span class="identifier">my_functor<br> </span><span class="special">{<br> </span><span class="keyword">public</span><span class="special">:<br><br> </span><span class="keyword">typedef char </span><span class="identifier">result_type</span><span class="special">;<br><br> </span><span class="identifier">my_functor</span><span class="special">()<br> : </span><span class="identifier">c</span><span class="special">(</span><span class="literal">'A'</span><span class="special">) {}<br><br> </span><span class="keyword">char operator</span><span class="special">()() </span><span class="keyword">const<br> </span><span class="special">{<br> </span><span class="keyword">if </span><span class="special">(</span><span class="identifier">c </span><span class="special">== </span><span class="literal">'M'</span><span class="special">)<br> </span><span class="keyword">return </span><span class="identifier">eof</span><span class="special">;<br> </span><span class="keyword">else<br> return </span><span class="identifier">c</span><span class="special">++;<br> }<br><br> </span><span class="keyword">static </span><span class="identifier">result_type eof</span><span class="special">;<br><br> </span><span class="keyword">private</span><span class="special">:<br><br> </span><span class="keyword">char </span><span class="identifier">c</span><span class="special">;<br> };<br><br> </span><span class="identifier">my_functor</span><span class="special">::</span><span class="identifier">result_type my_functor</span><span class="special">::</span><span class="identifier">eof </span><span class="special">= </span><span class="literal">'\0'</span><span class="special">;<br><br> </span><span class="keyword">typedef </span><span class="identifier">multi_pass</span><span class="special"><<br> </span><span class="identifier">my_functor</span><span class="special">,<br> </span><span class="identifier">multi_pass_policies</span><span class="special">::</span><span class="identifier">functor_input</span><span class="special">,<br> </span><span class="identifier">multi_pass_policies</span><span class="special">::</span><span class="identifier">first_owner</span><span class="special">,<br> </span><span class="identifier">multi_pass_policies</span><span class="special">::</span><span class="identifier">no_check</span><span class="special">,<br> </span><span class="identifier">multi_pass_policies</span><span class="special">::</span><span class="identifier">std_deque<br> </span><span class="special">> </span><span class="identifier">functor_multi_pass_t</span><span class="special">;<br><br> </span><span class="identifier">functor_multi_pass_t first </span><span class="special">= </span><span class="identifier">functor_multi_pass_t</span><span class="special">(</span><span class="identifier">my_functor</span><span class="special">());<br> </span><span class="identifier">functor_multi_pass_t last</span><span class="special">;<br></span></code></pre> |
|---|
| 233 | <a name="how_to_write_policies_for_use_with_multi_pass"></a> |
|---|
| 234 | <h3>How to write policies for use with multi_pass</h3> |
|---|
| 235 | <a name="inputpolicy"></a> |
|---|
| 236 | <h4>InputPolicy</h4> |
|---|
| 237 | <p> An InputPolicy must have the following interface:</p> |
|---|
| 238 | <pre> <code><span class="keyword">class </span><span class="identifier">my_input_policy </span><span class="comment">// your policy name<br> </span><span class="special">{<br> </span><span class="keyword">public</span><span class="special">:<br><br> </span><span class="comment">// class inner will be instantiated with the type given<br> // as the InputT parameter to multi_pass.<br><br> </span><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">InputT</span><span class="special">><br> </span><span class="keyword">class </span><span class="identifier">inner<br> </span><span class="special">{<br> </span><span class="keyword">public</span><span class="special">:<br><br> </span><span class="comment">// these typedefs determine the iterator_traits for multi_pass<br> </span><span class="keyword">typedef </span><span class="identifier">x </span><span class="identifier">value_type</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">x </span><span class="identifier">difference_type</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">x </span><span class="identifier">pointer</span><span class="special">;<br> </span><span class="keyword">typedef </span><span class="identifier">x </span><span class="identifier">reference</span><span class="special">;<br><br> </span><span class="keyword">protected</span><span class="special">:<br><br> </span><span class="identifier">inner</span><span class="special">();<br> </span><span class="identifier">inner</span><span class="special">(</span><span class="identifier">InputT </span><span class="identifier">x</span><span class="special">);<br> </span><span class="identifier">inner</span><span class="special">(</span><span class="identifier">inner </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">x</span><span class="special">);<br> </span><span class="comment">// delete or clean up any state<br> </span><span class="keyword">void </span><span class="identifier">destroy</span><span class="special">();<br> </span><span class="comment">// return true if *this and x have the same input<br> </span><span class="keyword">bool </span><span class="identifier">same_input</span><span class="special">(</span><span class="identifier">inner </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">x</span><span class="special">) </span><span class="keyword">const</span><span class="special">;<br> </span><span class="keyword">void </span><span class="identifier">swap</span><span class="special">(</span><span class="identifier">inner</span><span class="special">& </span><span class="identifier">x</span><span class="special">);<br><br> </span><span class="keyword">public</span><span class="special">:<br><br> </span><span class="comment">// get an instance from the input<br> </span><span class="identifier">result_type </span><span class="identifier">get_input</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br> </span><span class="comment">// advance the input<br> </span><span class="keyword">void </span><span class="identifier">advance_input</span><span class="special">();<br> </span><span class="comment">// return true if the input is at the end<br> </span><span class="keyword">bool </span><span class="identifier">input_at_eof</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br> </span><span class="special">};<br> </span><span class="special">};<br></span></code></pre> |
|---|
| 239 | <p> Because of the way that multi_pass shares a buffer and input among multiple |
|---|
| 240 | copies, class inner should keep a pointer to it's input. The copy constructor |
|---|
| 241 | should simply copy the pointer. destroy() should delete it. same_input should |
|---|
| 242 | compare the pointers. For more details see the various implementations of InputPolicy |
|---|
| 243 | classes.</p> |
|---|
| 244 | <a name="ownershippolicy"></a> |
|---|
| 245 | <h4>OwnershipPolicy</h4> |
|---|
| 246 | <p> The OwnershipPolicy must have the following interface:</p> |
|---|
| 247 | <pre> <code><span class="keyword">class </span><span class="identifier">my_ownership_policy<br> </span><span class="special">{<br> </span><span class="keyword">protected</span><span class="special">:<br><br> </span><span class="identifier">my_ownership_policy</span><span class="special">();<br> </span><span class="identifier">my_ownership_policy</span><span class="special">(</span><span class="identifier">my_ownership_policy </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">x</span><span class="special">);<br> </span><span class="comment">// clone is called when a copy of the iterator is made<br> </span><span class="keyword">void </span><span class="identifier">clone</span><span class="special">();<br> </span><span class="comment">// called when a copy is deleted. Return true to indicate<br> // resources should be released<br> </span><span class="keyword">bool </span><span class="identifier">release</span><span class="special">();<br> </span><span class="keyword">void </span><span class="identifier">swap</span><span class="special">(</span><span class="identifier">my_ownership_policy</span><span class="special">& </span><span class="identifier">x</span><span class="special">);<br><br> </span><span class="keyword">public</span><span class="special">:<br> </span><span class="comment">// returns true if there is only one iterator in existence.<br> // std_dequeue StoragePolicy will free it's buffered data if this<br> // returns true.<br> </span><span class="keyword">bool </span><span class="identifier">unique</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br> </span><span class="special">};<br></span></code></pre> |
|---|
| 248 | <a name="checkingpolicy"></a> |
|---|
| 249 | <h4>CheckingPolicy</h4> |
|---|
| 250 | <p> The CheckingPolicy must have the following interface:</p> |
|---|
| 251 | <pre> <code><span class="keyword">class </span><span class="identifier">my_check<br> </span><span class="special">{<br> </span><span class="keyword">protected</span><span class="special">:<br><br> </span><span class="identifier">my_check</span><span class="special">();<br> </span><span class="identifier">my_check</span><span class="special">(</span><span class="identifier">my_check </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">x</span><span class="special">);<br> </span><span class="keyword">void </span><span class="identifier">destroy</span><span class="special">();<br> </span><span class="keyword">void </span><span class="identifier">swap</span><span class="special">(</span><span class="identifier">my_check</span><span class="special">& </span><span class="identifier">x</span><span class="special">);<br> </span><span class="comment">// check should make sure that this iterator is valid<br> </span><span class="keyword">void </span><span class="identifier">check</span><span class="special">() </span><span class="keyword">const</span><span class="special">;<br> </span><span class="keyword">void </span><span class="identifier">clear_queue</span><span class="special">();<br> </span><span class="special">};<br></span></code></pre> |
|---|
| 252 | <a name="storagepolicy"></a> |
|---|
| 253 | <h4>StoragePolicy</h4> |
|---|
| 254 | <p> A StoragePolicy must have the following interface:</p> |
|---|
| 255 | <pre> <code><span class="keyword">class </span><span class="identifier">my_storage_policy<br> </span><span class="special">{<br> </span><span class="keyword">public</span><span class="special">:<br><br> </span><span class="comment">// class inner will be instantiated with the value_type from the InputPolicy<br><br> </span><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">ValueT</span><span class="special">><br> </span><span class="keyword">class </span><span class="identifier">inner<br> </span><span class="special">{<br> </span><span class="keyword">protected</span><span class="special">:<br><br> </span><span class="identifier">inner</span><span class="special">();<br> </span><span class="identifier">inner</span><span class="special">(</span><span class="identifier">inner </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">x</span><span class="special">);<br> </span><span class="comment">// will be called from the destructor of the last iterator.<br> </span><span class="keyword">void </span><span class="identifier">destroy</span><span class="special">();<br> </span><span class="keyword">void </span><span class="identifier">swap</span><span class="special">(</span><span class="identifier">inner</span><span class="special">& </span><span class="identifier">x</span><span class="special">);<br> </span><span class="comment">// This is called when the iterator is dereferenced. It's a template<br> // method so we can recover the type of the multi_pass iterator<br> // and access it.<br> </span><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">MultiPassT</span><span class="special">><br> </span><span class="keyword">static </span><span class="identifier">ValueT </span><span class="identifier">dereference</span><span class="special">(</span><span class="identifier">MultiPassT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">mp</span><span class="special">);<br> </span><span class="comment">// This is called when the iterator is incremented. It's a template<br> // method so we can recover the type of the multi_pass iterator<br> // and access it.<br> </span><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">MultiPassT</span><span class="special">><br> </span><span class="keyword">static </span><span class="keyword">void </span><span class="identifier">increment</span><span class="special">(</span><span class="identifier">MultiPassT</span><span class="special">& </span><span class="identifier">mp</span><span class="special">);<br> </span><span class="keyword">void </span><span class="identifier">clear_queue</span><span class="special">();<br> </span><span class="comment">// called to determine whether the iterator is an eof iterator<br> </span><span class="keyword">template </span><span class="special"><</span><span class="keyword">typename </span><span class="identifier">MultiPassT</span><span class="special">><br> </span><span class="keyword">static </span><span class="keyword">bool </span><span class="identifier">is_eof</span><span class="special">(</span><span class="identifier">MultiPassT </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">mp</span><span class="special">);<br> </span><span class="comment">// called by operator==<br> </span><span class="keyword">bool </span><span class="identifier">equal_to</span><span class="special">(</span><span class="identifier">inner </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">x</span><span class="special">) </span><span class="keyword">const</span><span class="special">;<br> </span><span class="comment">// called by operator<<br> </span><span class="keyword">bool </span><span class="identifier">less_than</span><span class="special">(</span><span class="identifier">inner </span><span class="keyword">const</span><span class="special">& </span><span class="identifier">x</span><span class="special">) </span><span class="keyword">const</span><span class="special">;<br> </span><span class="special">}; </span><span class="comment"> // class inner<br> </span><span class="special">};<br></span></code></pre> |
|---|
| 256 | <p> A StoragePolicy is the trickiest policy to write. You should study and understand |
|---|
| 257 | the existing StoragePolicy classes before you try and write your own.</p> |
|---|
| 258 | <table border="0"> |
|---|
| 259 | <tbody><tr> |
|---|
| 260 | <td width="10"><br> |
|---|
| 261 | </td> |
|---|
| 262 | <td width="30"><a href="../index.html"><img src="theme/u_arr.gif" border="0"></a></td> |
|---|
| 263 | <td width="30"><a href="trees.html"><img src="theme/l_arr.gif" border="0"></a></td> |
|---|
| 264 | <td width="30"><a href="file_iterator.html"><img src="theme/r_arr.gif" border="0"></a></td> |
|---|
| 265 | </tr> |
|---|
| 266 | </tbody></table> |
|---|
| 267 | <br> |
|---|
| 268 | <hr size="1"> |
|---|
| 269 | <p class="copyright">Copyright © 2001-2002 Daniel C. Nuffer<br> |
|---|
| 270 | <br> |
|---|
| 271 | <font size="2">Use, modification and distribution is subject to the Boost Software |
|---|
| 272 | License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
|---|
| 273 | http://www.boost.org/LICENSE_1_0.txt) </font> </p> |
|---|
| 274 | <p class="copyright"> </p> |
|---|
| 275 | <br> |
|---|
| 276 | </body></html> |
|---|
