ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/lsys/lsys.cpp
Revision: 1.1
Committed: Thu Nov 6 14:31:24 2008 UTC (15 years, 5 months ago) by root
Branch: MAIN
CVS Tags: HEAD
Log Message:
*** empty log message ***

File Contents

# Content
1 /*
2 * l-system representation and evaluation
3 */
4
5 #include "config.h"
6
7 #include <algorithm>
8 #include <iterator>
9 #include <iostream>
10 #include <sstream>
11
12 #include <cstdlib>
13 #include <cmath>
14
15 #include "tokens.h"
16 #include "DLGLexer.h"
17 #include "Parser.h"
18
19 #include "lsys.h"
20
21 #ifndef M_PI
22 # define M_PI 3.14159265358979323846 /* pi */
23 #endif
24
25 bool operator <(const lsys::arg_spec &a, const lsys::arg_spec &b) t_no
26 {
27 return a.nargs < b.nargs
28 || (a.nargs == b.nargs && a.arg < b.arg)
29 || (a.arg == b.arg && a.str < b.str);
30 }
31
32 ostream &operator <<(ostream &o, const file_pos &p) t_no
33 {
34 return o << p.path << ":" << p.line << ", column " << p.col;
35 }
36
37 ostream &operator <<(ostream &o, const module_vec &v) t_no
38 {
39 // o << "[" << hex << (long)&v << " " << (long)v.s << dec << "|";//D
40
41 for (module_pos i = v.begin (); i != v.end (); ++i)
42 o << *i << " ";
43
44 // o << "]";
45
46 return o;
47 }
48
49 ostream &operator <<(ostream &o, const module &m) t_no
50 {
51 static const char *delim[2][2] = {
52 { ",", ")" },
53 { " ", "" }
54 };
55
56 // if (m.is_expr) o << "E:";
57 // if (m.is_num) o << "N:";
58
59 o << m.str;
60
61 if (!m.empty ())
62 {
63 o << (m.str.size () ? "(" : "'");
64
65 for (module_pos i = m.begin (); i != m.end (); )
66 {
67 o << *i;
68 o << delim[!m.str.size ()][++i == m.end ()];
69 }
70 }
71
72 return o;
73 }
74
75 ostream &operator <<(ostream &o, const rule &r) t_no
76 {
77 if (r.pre.size ())
78 o << r.pre << " < ";
79
80 o << (module)r << " ";
81 if (r.post.size ())
82 o << "> " << r.post << " ";
83
84 if (r.constraint.is_expr)
85 o << " '" << r.constraint << "' ";
86
87 o << "=> " << r.repl;
88 o << ", " << r.iterations;
89 return o;
90 }
91
92 static ostream &operator <<(ostream &o, const lsys::arg_spec &a) t_no
93 {
94 return o << "<" << a.str << "/" << a.nargs << ", " << a.arg << ">";
95 }
96
97 ostream &operator <<(ostream &o, const lsys &l) t_no
98 {
99 for (module_map::const_iterator i = l.defines.begin (); i != l.defines.end (); ++i)
100 o << "DEFINE: " << i->first << " = " << i->second << endl;
101
102 o << "PARENT: " << (l.parent ? l.parent->str : "(none)") << endl;
103
104 o << "CHILDREN:";
105 for (hash_map<string, lsys *>::const_iterator i = l.sub_lsys.begin (); i != l.sub_lsys.end (); ++i)
106 o << " " << i->second->str;
107 o << endl;
108
109 o << "IGNORE: ";
110 copy (l.ignore_module.begin (), l.ignore_module.end (), ostream_iterator<const string>(o, " "));
111 o << endl;
112
113 for (rule_map::const_iterator i = l.rules.begin (); i != l.rules.end (); ++i)
114 for (rule_map::mapped_type::const_iterator j = i->second.begin (); j != i->second.end (); ++j)
115 o << "RULE " << i->first << "/" << j->size () << ": " << *j << endl;
116
117 o << "ARG_IS_NUMERIC:";
118 for (set<lsys::arg_spec>::const_iterator i = l.arg_is_numeric.begin ();
119 i != l.arg_is_numeric.end ();
120 ++i)
121 o << " " << *i;
122 o << endl;
123
124 return o;
125 }
126
127 lsys::lsys () t_no
128 {
129 parent = 0;
130
131 arg_spec s;
132 s.str = "f"; s.nargs = 1; s.arg = 0; arg_is_numeric.insert (s);
133 s.str = "F"; s.nargs = 1; s.arg = 0; arg_is_numeric.insert (s);
134 s.str = "+"; s.nargs = 1; s.arg = 0; arg_is_numeric.insert (s);
135 s.str = "-"; s.nargs = 1; s.arg = 0; arg_is_numeric.insert (s);
136 s.str = "^"; s.nargs = 1; s.arg = 0; arg_is_numeric.insert (s);
137 s.str = "&"; s.nargs = 1; s.arg = 0; arg_is_numeric.insert (s);
138 s.str = "/"; s.nargs = 1; s.arg = 0; arg_is_numeric.insert (s);
139 s.str = "\\"; s.nargs = 1; s.arg = 0; arg_is_numeric.insert (s);
140
141 ignore_module.insert ("attr");
142 }
143
144 lsys::~lsys () t_no
145 {
146 hash_map<string, lsys*>::iterator i;
147
148 while ((i = sub_lsys.begin ()) != sub_lsys.end ())
149 {
150 delete i->second;
151 sub_lsys.erase (i);
152 }
153 }
154
155 void lsys::mark_numeric (const map<string, arg_spec> &which, const module &v) t_no
156 {
157 for (module_pos i = v.begin (); i != v.end (); ++i)
158 {
159 map<string,arg_spec>::const_iterator d = which.find (i->str);
160
161 if (d != which.end ())
162 arg_is_numeric.insert (d->second);
163 else
164 for (module_pos a = i->begin (); a != i->end (); a++)
165 mark_numeric (which, *a);
166 }
167 }
168
169 void lsys::add_lsys (lsys *l) t_err
170 {
171 if (!l->str.size ())
172 {
173 delete l;
174 throw error ("unable to determine ruleset name", *l);
175 }
176
177 l->parent = this;
178 sub_lsys [l->str] = l;
179 }
180
181 void lsys::add_rule (rule r) t_err
182 {
183 map<string,arg_spec> which;
184 arg_spec spec;
185
186 spec.str = r.str;
187 spec.nargs = r.size ();
188 spec.arg = 0;
189
190 for (rule::iterator i = r.begin (); i != r.end (); ++i, spec.arg++)
191 if (i->size () != 0)
192 throw error("rule parameter too complex", *i);
193 else if (i->is_expr)
194 {
195 if (i->is_num)
196 {
197 char arg[30];
198 sprintf (arg, "_arg%d", spec.arg);
199
200 module m(arg); m.is_expr = 1;
201 module eq("==", m, *i); eq.is_expr = 1;
202
203 r.constraint = r.constraint.empty ()
204 ? eq
205 : module ("&&", r.constraint, eq);
206 *i = m;
207 }
208 which.insert (pair<string, arg_spec>(i->str, spec));
209 }
210
211 mark_numeric (which, r.constraint);
212
213 if (rules.size () == 0)
214 module::operator =((module)r);
215
216 rules[r.str].push_back (r);
217 }
218
219 static double eval_expr_2 (const module &m, const module_map &l, const module_map &g) t_err
220 {
221 switch (m.size ())
222 {
223 case 0:
224 {
225 if (m.is_num)
226 return m.num;
227 else
228 {
229 module_map::const_iterator i;
230
231 if ((i = l.find (m.str)) != l.end ()
232 || (i = g.find (m.str)) != g.end ())
233 return eval_expr (i->second, g, module_map ());
234
235 throw error ("undefined identifier in expression", m);
236 }
237 }
238
239 case 1:
240 if (m.str == "!" ) return !eval_expr_2 (m.first (), l, g);
241 if (m.str == "sin" ) return sin (eval_expr_2 (m.first (), l, g));
242 if (m.str == "cos" ) return cos (eval_expr_2 (m.first (), l, g));
243 if (m.str == "tan" ) return tan (eval_expr_2 (m.first (), l, g));
244 if (m.str == "asin" ) return asin (eval_expr_2 (m.first (), l, g));
245 if (m.str == "acos" ) return acos (eval_expr_2 (m.first (), l, g));
246 if (m.str == "atan" ) return atan (eval_expr_2 (m.first (), l, g));
247 if (m.str == "int" ) return int (eval_expr_2 (m.first (), l, g));
248 if (m.str == "ceil" ) return ceil (eval_expr_2 (m.first (), l, g));
249 if (m.str == "floor" ) return floor(eval_expr_2 (m.first (), l, g));
250 if (m.str == "rand" ) return (eval_expr_2 (m.first (), l, g)) * rand () / RAND_MAX;
251 if (m.str == "irand" ) return int ((eval_expr_2 (m.first (), l, g)) * rand () / RAND_MAX);
252 if (m.str == "log" ) return log (eval_expr_2 (m.first (), l, g));
253 if (m.str == "abs" ) return abs (eval_expr_2 (m.first (), l, g));
254 if (m.str == "deg" ) return (eval_expr_2 (m.first (), l, g)) * 180.0 / M_PI;
255 if (m.str == "rad" ) return (eval_expr_2 (m.first (), l, g)) * M_PI / 180.0;
256 if (m.str == "sqrt" ) return sqrt (eval_expr_2 (m.first (), l, g));
257
258 throw error ("unknown unary function in expression", m);
259
260 case 2:
261 if (m.str == "+" ) return eval_expr_2 (m.first (), l, g) + eval_expr_2 (m.second (), l, g);
262 if (m.str == "-" ) return eval_expr_2 (m.first (), l, g) - eval_expr_2 (m.second (), l, g);
263 if (m.str == "*" ) return eval_expr_2 (m.first (), l, g) * eval_expr_2 (m.second (), l, g);
264 if (m.str == "/" ) return eval_expr_2 (m.first (), l, g) / eval_expr_2 (m.second (), l, g);
265 if (m.str == "<" ) return eval_expr_2 (m.first (), l, g) < eval_expr_2 (m.second (), l, g);
266 if (m.str == "<=") return eval_expr_2 (m.first (), l, g) <= eval_expr_2 (m.second (), l, g);
267 if (m.str == "==") return equal (eval_expr_2 (m.first (), l, g), eval_expr_2 (m.second (), l, g));
268 if (m.str == "!=") return eval_expr_2 (m.first (), l, g) != eval_expr_2 (m.second (), l, g);
269 if (m.str == ">" ) return eval_expr_2 (m.first (), l, g) > eval_expr_2 (m.second (), l, g);
270 if (m.str == ">=") return eval_expr_2 (m.first (), l, g) >= eval_expr_2 (m.second (), l, g);
271 if (m.str == "&&") return eval_expr_2 (m.first (), l, g) && eval_expr_2 (m.second (), l, g);
272 if (m.str == "||") return eval_expr_2 (m.first (), l, g) || eval_expr_2 (m.second (), l, g);
273 if (m.str == "%" ) return fmod (eval_expr_2 (m.first (), l, g), eval_expr_2 (m.second (), l, g));
274 if (m.str == "^" ) return pow (eval_expr_2 (m.first (), l, g), eval_expr_2 (m.second (), l, g));
275
276 throw error ("unknown binary function in expression", m);
277
278 default:
279 throw error ("can only evaluate modules with 0, 1 or 2 arguments", m);
280 }
281
282 throw error("reached end of non-void function eval_expr_2", m);
283 }
284
285 double eval_expr (const module &expr, const module_map &locals, const module_map &globals) t_err
286 {
287 return eval_expr_2 (expr, locals, globals);
288 }
289
290 double lsys::eval_numeric (const module &expr, module_map context) const t_err
291 {
292 return eval_expr (expr, context, defines);
293 }
294
295 static void get_vars (const module_vec &par, const module_vec &arg, module_map &vars) t_no
296 {
297 for (module_pos a = arg.begin (), b = par.begin ();
298 a != arg.end ();
299 ++a, ++b)
300 vars [b->str] = *a;
301 }
302
303 bool lsys::match_rule (const rule &r, const module_vec &v, module_pos i, module_map &vars) const t_err
304 {
305 int nested = 0;
306
307 if (r.module::match (*i))
308 {
309 module_pos j;
310
311 // match heading context
312 j = i;
313 for (module_pos z = r.pre.end ();
314 z != r.pre.begin ();
315 )
316 {
317 if (j == v.begin ())
318 return false;
319
320 --j;
321 if (j->str == "]")
322 nested++;
323 else if (j->str == "[")
324 nested = nested ? nested-1 : nested;
325 else if (!nested && ignore_module.find (j->str) == ignore_module.end ())
326 {
327 --z;
328 if (!z->match (*j))
329 return false;
330
331 get_vars (*z, *j, vars);
332 }
333 }
334
335 // match trailing context
336 j = i;
337 for (module_pos z = r.post.begin ();
338 z != r.post.end ();
339 )
340 {
341 ++j;
342 if (j == v.end ())
343 return false;
344
345 if (j->str == "[")
346 nested++;
347 else if (j->str == "]")
348 nested = nested ? nested-1 : nested;
349 else if (!nested && ignore_module.find (j->str) == ignore_module.end ())
350 {
351 if (!z->match (*j))
352 return false;
353
354 get_vars (*z, *j, vars);
355 ++z;
356 }
357 }
358
359 get_vars (r, *i, vars);
360 //FIXME: add pattern matching ???
361 return eval_numeric (r.constraint, vars);
362 }
363
364 return false;
365 }
366
367 module lsys::expand (const module_map &c, const module &m) const t_err
368 {
369 module_map::const_iterator n;
370
371 if ((n = c.find (m.str)) != c.end ())
372 return n->second;
373 else
374 {
375 arg_spec spec;
376 spec.str = m.str;
377 spec.nargs = m.size ();
378 spec.arg = 0;
379
380 module k;
381 k.str = m.str;
382 k.num = m.num;
383 k.is_num = m.is_num;
384 k.is_expr = m.is_expr;
385 k.where = m.where;
386
387 for (module_pos i = m.begin (); i != m.end (); ++i, spec.arg++)
388 if (arg_is_numeric.find (spec) != arg_is_numeric.end ())
389 k.push_back (eval_numeric (*i, c));
390 else
391 k.push_back (expand (c, *i));
392
393 return k;
394 }
395 }
396
397 static void replace_modules(module_vec &v, const module_map &m) t_no
398 {
399 module_map::const_iterator c;
400
401 for (module::iterator i = v.begin (); i != v.end (); ++i)
402 if (i->empty () && (c = m.find (i->str)) != m.end ())
403 *i = c->second;
404 else
405 replace_modules (*i, m);
406 }
407
408 bool operator <(const module &a, const module &b) t_no
409 {
410 if ((module_vec)a < (module_vec)b)
411 return true;
412 else
413 return a.str < b.str;
414 }
415
416 struct lsys_module {
417 const lsys *sys;
418 module_vec v;
419 };
420
421 static bool operator <(const lsys_module &a, const lsys_module &b)
422 {
423 if (a.v < b.v)
424 return true;
425 else
426 return (long)a.sys < (long)b.sys;
427 }
428
429 bool lsys::eval (module_vec &v) const t_err
430 {
431 #if 0
432 typedef map<lsys_module, pair<bool, module_vec> > eval_cache;
433 static eval_cache cache;
434
435 eval_cache::iterator ci;
436
437 { //FIXME, why can't I just re-use "ck" later??
438 lsys_module ck;
439 ck.sys = this;
440 ck.v = v;
441
442 if ((ci = cache.find (ck)) != cache.end ())
443 {
444 if (ci->second.first)
445 v = ci->second.second;
446
447 return ci->second.first;
448 }
449 }
450 #endif
451
452 bool changed = false;
453 module_vec res;
454 module_map vars;
455
456 for (module_pos i = v.begin (); i != v.end (); ++i)
457 {
458 rule_map::const_iterator r = rules.find (i->str);
459
460 if (r != rules.end ())
461 for (rule_map::mapped_type::const_iterator j = r->second.begin (); j != r->second.end (); ++j)
462 {
463 vars.erase (vars.begin (), vars.end ());
464
465 if (match_rule (*j, v, i, vars))
466 {
467 double it = eval_numeric (j->iterations, vars);
468
469 changed = true;
470
471 if (it >= 1.0)
472 {
473 module_vec x;
474
475 for (module_pos i = j->repl.begin (); i != j->repl.end (); ++i)
476 x.push_back (expand (vars, *i));
477
478 do {
479 eval (x);
480 it--;
481 } while (it > 0);
482
483 res.insert (res.end (), x.begin (), x.end ());
484 }
485 else
486 for (module_pos i = j->repl.begin (); i != j->repl.end (); ++i)
487 res.push_back (expand (vars, *i));
488
489 goto skip;
490 }
491 }
492
493 // no rule matched..
494 res.push_back (*i);
495 skip:;
496 }
497
498 replace_modules (res, defines);
499 #if 0
500 if ((!changed && v.size () < 10) || res.size () < 20)
501 {
502 eval_cache::mapped_type ce(changed, changed ? res : module_vec ());
503 lsys_module ck;
504 ck.sys = this;
505 ck.v = v; //FIXME not even this works
506 cache.insert (ci, eval_cache::value_type (ck, ce));
507 }
508 #endif
509
510 v.erase ();
511
512 for (module_pos i = res.begin (); i != res.end (); )
513 {
514 if (i->str == "%")
515 {
516 int nested = 1;
517
518 while (++i != res.end ())
519 if (i->str == "[")
520 nested++;
521 else if (i->str == "]" && !(--nested))
522 break;
523 }
524 else
525 v.push_back (*i++);
526 }
527
528 return changed;
529 }
530
531 bool module::is_func (const string &func) const t_no
532 {
533 return str == func && size () == 0;
534 }
535
536 bool module::is_func (const string &func, double &arg1) const t_no
537 {
538 if (str == func && size () == 1)
539 {
540 arg1 = eval_expr (first ());
541 return true;
542 }
543 return false;
544 }
545
546 bool module::is_func (const string &func, string &arg1, module &arg2) const t_no
547 {
548 if (str == func && size () == 2 && first().is_expr)
549 {
550 arg1 = first ().str;
551 arg2 = second ();
552 return true;
553 }
554
555 return false;
556 }
557
558 bool module::is_func (const string &func, string &arg1, double &arg2) const t_no
559 {
560 if (str == func && size () == 2 && first().is_expr)
561 {
562 arg1 = first ().str;
563 arg2 = eval_expr (second ());
564 return true;
565 }
566
567 return false;
568 }
569
570 bool module::is_func (const string &func, string &arg1, string &arg2) const t_no
571 {
572 if (str == func && size () == 2 && first().is_expr)
573 {
574 arg1 = first ().str;
575 arg2 = (string) second ();
576 return true;
577 }
578
579 return false;
580 }
581
582
583
584
585