]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | # Copyright 2001, 2002, 2003 Dave Abrahams |
2 | # Copyright 2006 Rene Rivera | |
3 | # Copyright 2002, 2003 Vladimir Prus | |
4 | # Distributed under the Boost Software License, Version 1.0. | |
5 | # (See accompanying file LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt) | |
6 | ||
7 | import assert ; | |
8 | import numbers ; | |
9 | import modules ; | |
10 | ||
11 | ||
12 | # Note that algorithms in this module execute largely in the caller's module | |
13 | # namespace, so that local rules can be used as function objects. Also note that | |
14 | # most predicates can be multi-element lists. In that case, all but the first | |
15 | # element are prepended to the first argument which is passed to the rule named | |
16 | # by the first element. | |
17 | ||
18 | ||
19 | # Return the elements e of $(sequence) for which [ $(predicate) e ] has a | |
20 | # non-null value. | |
21 | # | |
22 | rule filter ( predicate + : sequence * ) | |
23 | { | |
24 | local caller = [ CALLER_MODULE ] ; | |
25 | local result ; | |
26 | ||
27 | for local e in $(sequence) | |
28 | { | |
29 | if [ modules.call-in $(caller) : $(predicate) $(e) ] | |
30 | { | |
31 | result += $(e) ; | |
32 | } | |
33 | } | |
34 | return $(result) ; | |
35 | } | |
36 | ||
37 | ||
38 | # Return a new sequence consisting of [ $(function) $(e) ] for each element e of | |
39 | # $(sequence). | |
40 | # | |
41 | rule transform ( function + : sequence * ) | |
42 | { | |
43 | local caller = [ CALLER_MODULE ] ; | |
44 | local result ; | |
45 | ||
46 | for local e in $(sequence) | |
47 | { | |
48 | result += [ modules.call-in $(caller) : $(function) $(e) ] ; | |
49 | } | |
50 | return $(result) ; | |
51 | } | |
52 | ||
53 | if [ HAS_NATIVE_RULE sequence : transform : 1 ] | |
54 | { | |
55 | NATIVE_RULE sequence : transform ; | |
56 | } | |
57 | ||
58 | # Returns the elements of 's' in reverse order | |
59 | rule reverse ( s * ) | |
60 | { | |
61 | local r ; | |
62 | for local x in $(s) | |
63 | { | |
64 | r = $(x) $(r) ; | |
65 | } | |
66 | return $(r) ; | |
67 | } | |
68 | ||
69 | ||
70 | rule less ( a b ) | |
71 | { | |
72 | if $(a) < $(b) | |
73 | { | |
74 | return true ; | |
75 | } | |
76 | } | |
77 | ||
78 | ||
79 | # Insertion-sort s using the BinaryPredicate ordered. | |
80 | # | |
81 | rule insertion-sort ( s * : ordered * ) | |
82 | { | |
83 | if ! $(ordered) | |
84 | { | |
85 | return [ SORT $(s) ] ; | |
86 | } | |
87 | else | |
88 | { | |
89 | local caller = [ CALLER_MODULE ] ; | |
90 | ordered ?= sequence.less ; | |
91 | local result = $(s[1]) ; | |
92 | if $(ordered) = sequence.less | |
93 | { | |
94 | local head tail ; | |
95 | for local x in $(s[2-]) | |
96 | { | |
97 | head = ; | |
98 | tail = $(result) ; | |
99 | while $(tail) && ( $(tail[1]) < $(x) ) | |
100 | { | |
101 | head += $(tail[1]) ; | |
102 | tail = $(tail[2-]) ; | |
103 | } | |
104 | result = $(head) $(x) $(tail) ; | |
105 | } | |
106 | } | |
107 | else | |
108 | { | |
109 | for local x in $(s[2-]) | |
110 | { | |
111 | local head tail ; | |
112 | tail = $(result) ; | |
113 | while $(tail) && [ modules.call-in $(caller) : $(ordered) $(tail[1]) $(x) ] | |
114 | { | |
115 | head += $(tail[1]) ; | |
116 | tail = $(tail[2-]) ; | |
117 | } | |
118 | result = $(head) $(x) $(tail) ; | |
119 | } | |
120 | } | |
121 | ||
122 | return $(result) ; | |
123 | } | |
124 | } | |
125 | ||
126 | ||
127 | # Merge two ordered sequences using the BinaryPredicate ordered. | |
128 | # | |
129 | rule merge ( s1 * : s2 * : ordered * ) | |
130 | { | |
131 | ordered ?= sequence.less ; | |
132 | local result__ ; | |
133 | local caller = [ CALLER_MODULE ] ; | |
134 | ||
135 | while $(s1) && $(s2) | |
136 | { | |
137 | if [ modules.call-in $(caller) : $(ordered) $(s1[1]) $(s2[1]) ] | |
138 | { | |
139 | result__ += $(s1[1]) ; | |
140 | s1 = $(s1[2-]) ; | |
141 | } | |
142 | else if [ modules.call-in $(caller) : $(ordered) $(s2[1]) $(s1[1]) ] | |
143 | { | |
144 | result__ += $(s2[1]) ; | |
145 | s2 = $(s2[2-]) ; | |
146 | } | |
147 | else | |
148 | { | |
149 | s2 = $(s2[2-]) ; | |
150 | } | |
151 | ||
152 | } | |
153 | result__ += $(s1) ; | |
154 | result__ += $(s2) ; | |
155 | ||
156 | return $(result__) ; | |
157 | } | |
158 | ||
11fdf7f2 TL |
159 | # Compares two sequences lexicagraphically |
160 | # | |
161 | rule compare ( s1 * : s2 * : ordered * ) | |
162 | { | |
163 | if ! $(ordered) | |
164 | { | |
165 | if $(s1) < $(s2) | |
166 | { | |
167 | return true ; | |
168 | } | |
169 | } | |
170 | else | |
171 | { | |
172 | while true | |
173 | { | |
174 | if ! $(s2[1])-is-defined | |
175 | { | |
176 | return ; | |
177 | } | |
178 | else if ! $(s1[1])-is-defined | |
179 | { | |
180 | return true ; | |
181 | } | |
182 | else if [ $(ordered) $(s1[1]) $(s2[1]) ] | |
183 | { | |
184 | return true ; | |
185 | } | |
186 | else if [ $(ordered) $(s2[1]) $(s1[1]) ] | |
187 | { | |
188 | return ; | |
189 | } | |
190 | s1 = $(s1[2-]) ; | |
191 | s2 = $(s2[2-]) ; | |
192 | } | |
193 | } | |
194 | } | |
7c673cae FG |
195 | |
196 | # Join the elements of s into one long string. If joint is supplied, it is used | |
197 | # as a separator. | |
198 | # | |
199 | rule join ( s * : joint ? ) | |
200 | { | |
201 | joint ?= "" ; | |
202 | return $(s:J=$(joint)) ; | |
203 | } | |
204 | ||
205 | ||
206 | # Find the length of any sequence. | |
207 | # | |
208 | rule length ( s * ) | |
209 | { | |
210 | local result = 0 ; | |
211 | for local i in $(s) | |
212 | { | |
213 | result = [ CALC $(result) + 1 ] ; | |
214 | } | |
215 | return $(result) ; | |
216 | } | |
217 | ||
218 | # Removes duplicates from 'list'. If 'stable' is | |
219 | # passed, then the order of the elements will | |
220 | # be unchanged. | |
221 | rule unique ( list * : stable ? ) | |
222 | { | |
223 | local result ; | |
224 | local prev ; | |
225 | if $(stable) | |
226 | { | |
227 | for local f in $(list) | |
228 | { | |
229 | if ! $(f) in $(result) | |
230 | { | |
231 | result += $(f) ; | |
232 | } | |
233 | } | |
234 | } | |
235 | else | |
236 | { | |
237 | for local i in [ SORT $(list) ] | |
238 | { | |
239 | if $(i) != $(prev) | |
240 | { | |
241 | result += $(i) ; | |
242 | } | |
243 | prev = $(i) ; | |
244 | } | |
245 | } | |
246 | return $(result) ; | |
247 | } | |
248 | ||
249 | ||
250 | # Returns the maximum number in 'elements'. Uses 'ordered' for comparisons or | |
251 | # 'numbers.less' if none is provided. | |
252 | # | |
253 | rule max-element ( elements + : ordered ? ) | |
254 | { | |
255 | ordered ?= numbers.less ; | |
256 | ||
257 | local max = $(elements[1]) ; | |
258 | for local e in $(elements[2-]) | |
259 | { | |
260 | if [ $(ordered) $(max) $(e) ] | |
261 | { | |
262 | max = $(e) ; | |
263 | } | |
264 | } | |
265 | return $(max) ; | |
266 | } | |
267 | ||
268 | ||
269 | # Returns all of 'elements' for which corresponding element in parallel list | |
270 | # 'rank' is equal to the maximum value in 'rank'. | |
271 | # | |
272 | rule select-highest-ranked ( elements * : ranks * ) | |
273 | { | |
274 | if $(elements) | |
275 | { | |
276 | local max-rank = [ max-element $(ranks) ] ; | |
277 | local result ; | |
278 | while $(elements) | |
279 | { | |
280 | if $(ranks[1]) = $(max-rank) | |
281 | { | |
282 | result += $(elements[1]) ; | |
283 | } | |
284 | elements = $(elements[2-]) ; | |
285 | ranks = $(ranks[2-]) ; | |
286 | } | |
287 | return $(result) ; | |
288 | } | |
289 | } | |
290 | NATIVE_RULE sequence : select-highest-ranked ; | |
291 | ||
292 | ||
293 | rule __test__ ( ) | |
294 | { | |
295 | # Use a unique module so we can test the use of local rules. | |
296 | module sequence.__test__ | |
297 | { | |
298 | import assert ; | |
299 | import sequence ; | |
300 | ||
301 | local rule is-even ( n ) | |
302 | { | |
303 | if $(n) in 0 2 4 6 8 | |
304 | { | |
305 | return true ; | |
306 | } | |
307 | } | |
308 | ||
309 | assert.result 4 6 4 2 8 : sequence.filter is-even : 1 4 6 3 4 7 2 3 8 ; | |
310 | ||
311 | # Test that argument binding works. | |
312 | local rule is-equal-test ( x y ) | |
313 | { | |
314 | if $(x) = $(y) | |
315 | { | |
316 | return true ; | |
317 | } | |
318 | } | |
319 | ||
320 | assert.result 3 3 3 : sequence.filter is-equal-test 3 : 1 2 3 4 3 5 3 5 7 ; | |
321 | ||
322 | local rule append-x ( n ) | |
323 | { | |
324 | return $(n)x ; | |
325 | } | |
326 | ||
327 | assert.result 1x 2x 3x : sequence.transform append-x : 1 2 3 ; | |
328 | ||
329 | local rule repeat2 ( x ) | |
330 | { | |
331 | return $(x) $(x) ; | |
332 | } | |
333 | ||
334 | assert.result 1 1 2 2 3 3 : sequence.transform repeat2 : 1 2 3 ; | |
335 | ||
336 | local rule test-greater ( a b ) | |
337 | { | |
338 | if $(a) > $(b) | |
339 | { | |
340 | return true ; | |
341 | } | |
342 | } | |
343 | assert.result 1 2 3 4 5 6 7 8 9 : sequence.insertion-sort 9 6 5 3 8 7 1 2 4 ; | |
344 | assert.result 9 8 7 6 5 4 3 2 1 : sequence.insertion-sort 9 6 5 3 8 7 1 2 4 : test-greater ; | |
345 | assert.result 1 2 3 4 5 6 : sequence.merge 1 3 5 : 2 4 6 ; | |
346 | assert.result 6 5 4 3 2 1 : sequence.merge 5 3 1 : 6 4 2 : test-greater ; | |
347 | assert.result 1 2 3 : sequence.merge 1 2 3 : ; | |
348 | assert.result 1 : sequence.merge 1 : 1 ; | |
349 | ||
350 | assert.result foo-bar-baz : sequence.join foo bar baz : - ; | |
351 | assert.result substandard : sequence.join sub stan dard ; | |
352 | assert.result 3.0.1 : sequence.join 3.0.1 : - ; | |
353 | ||
354 | assert.result 0 : sequence.length ; | |
355 | assert.result 3 : sequence.length a b c ; | |
356 | assert.result 17 : sequence.length 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 ; | |
357 | ||
358 | assert.result 1 : sequence.length a ; | |
359 | assert.result 10 : sequence.length a b c d e f g h i j ; | |
360 | assert.result 11 : sequence.length a b c d e f g h i j k ; | |
361 | assert.result 12 : sequence.length a b c d e f g h i j k l ; | |
362 | ||
363 | local p2 = x ; | |
364 | for local i in 1 2 3 4 5 6 7 8 | |
365 | { | |
366 | p2 = $(p2) $(p2) ; | |
367 | } | |
368 | assert.result 256 : sequence.length $(p2) ; | |
369 | ||
370 | assert.result 1 2 3 4 5 : sequence.unique 1 2 3 2 4 3 3 5 5 5 ; | |
371 | ||
372 | assert.result 5 : sequence.max-element 1 3 5 0 4 ; | |
373 | ||
374 | assert.result e-3 h-3 : sequence.select-highest-ranked e-1 e-3 h-3 m-2 : 1 3 3 2 ; | |
375 | ||
376 | assert.result 7 6 5 4 3 2 1 : sequence.reverse 1 2 3 4 5 6 7 ; | |
377 | } | |
378 | } |