]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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_type</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_type</span><span class="special">> > </span><span class="identifier">iterator_type</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_type</span><span class="special">;</span> | |
93 | <span class="keyword">typedef</span> <span class="identifier">scanner_policies</span><span class="special"><</span>iter_policy_type<span class="special">></span> <span class="identifier">scanner_policies_type</span><span class="special">;</span> | |
94 | <span class="keyword">typedef</span> <span class="identifier">scanner</span><span class="special"><</span>iterator_type, scanner_policies_type<span class="special">></span> <span class="identifier">scanner_type</span><span class="special">;</span> | |
95 | ||
96 | <span class="keyword">typedef</span> rule<span class="special"><</span>scanner_type<span class="special">></span> <span class="identifier">rule_type</span><span class="special">;</span> | |
97 | ||
98 | <span class="identifier">iter_policy_type</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_type</span> <span class="identifier">policies</span><span class="special">(</span><span class="identifier">iter_policy</span><span class="special">);</span> | |
100 | iterator_type first( | |
101 | make_multi_pass(std::istreambuf_iterator<char_type>(in))); | |
102 | ||
103 | scanner_type <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_type</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_type 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_type</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_type</span><span class="special">;<br><br> </span><span class="identifier">functor_multi_pass_type first </span><span class="special">= </span><span class="identifier">functor_multi_pass_type</span><span class="special">(</span><span class="identifier">my_functor</span><span class="special">());<br> </span><span class="identifier">functor_multi_pass_type 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_if_valid</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> |