1 /* 2 lsystem.js - An L-system library 3 [The "BSD licence"] 4 Copyright (c) 2008, John Snyders 5 All rights reserved. 6 7 Redistribution and use in source and binary forms, with or without 8 modification, are permitted provided that the following conditions 9 are met: 10 1. Redistributions of source code must retain the above copyright 11 notice, this list of conditions and the following disclaimer. 12 2. Redistributions in binary form must reproduce the above copyright 13 notice, this list of conditions and the following disclaimer in the 14 documentation and/or other materials provided with the distribution. 15 3. The name of the author may not be used to endorse or promote products 16 derived from this software without specific prior written permission. 17 18 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 19 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 */ 29 var jjs = window.jjs || {}; // my namespace 30 jjs.Lsystem = (function () 31 { 32 33 /** 34 * @fileoverview 35 * 36 * <p>L-system library</p> 37 * <p>For background information see <a href="http://en.wikipedia.org/wiki/L-system">this</a> 38 * and "The Algorithmic Beauty of Plants" available 39 * <a href="http://algorithmicbotany.org/papers/#abop">here</a></p> 40 * 41 * <p>An L-system is a production system that repeatedly rewrites symbols according to 42 * a set of rules. It is used to draw or model organic systems and fractals. 43 * An L-system takes an initial list of symbols and iteratively produces a new list of 44 * symbols based on a set of production rules. It can also operate on lists with 45 * structure - lists of lists. These are called branching or tree L-systems.</p> 46 * 47 * <p>L-systems come in a few different varieties and each is supported by this library. 48 * They can be:</p> 49 * <ul> 50 * <li>parametric or non-parametric,</li> 51 * <li>deterministic or non-deterministic,</li> 52 * <li>context-free or context-sensitive,</li> 53 * <li>branching (tree) or non-branching (flat)</li> 54 * </ul> 55 * <p>Each L-system is a combination of one of each of the four options above. 56 * For example non-parametric, context-sensitive, non-deterministic, and branching.</p> 57 * 58 * <p>A parametric L-system has parameters, (also called arguments) associated with the 59 * symbols and a non-parametric one does not. The symbol plus its parameters is called a module. 60 * Typically parametric L-systems restrict the parameters to be numbers. This 61 * library allows parameters to be any JavaScript type.</p> 62 * 63 * <p>A deterministic L-system will have at most one rule that can match a given input module (symbol). 64 * A non-deterministic L-system can have more than one rule that matches and a particular rule 65 * is selected randomly based on probabilities assigned to each matching rule.</p> 66 * 67 * <p>A context-free L-system matches a single input module. A context-sensitive L-system matches 68 * based on an input module and its neighbors.</p> 69 * 70 * <p>A branching L-system has structure in its list. Each item in the list may be itself a list. 71 * A non-branching L-system has a flat list. It seems that this is usually implemented by introducing 72 * structural symbols [ and ] but the list remains flat. This library uses a nested list for the 73 * branch. Strictly speaking the tree structure implementation is only useful for context-sensitive 74 * matching.</p> 75 * 76 * <p>An L-system consists of:</p> 77 * <ul> 78 * <li>a set of symbols denoted V (traditionally the symbols are single characters such as A or + but 79 * extended here to any unique identifying string). For the L-system to do something useful the symbols 80 * need to have some kind of semantics or behavior. Here the behavior is given by a function associated 81 * with each symbol. A symbol can have zero or one functions associated with it. Think of this function 82 * along with the symbol name as the definition of the symbol. The functions can take arguments. The 83 * symbols processed by the L-system can have any number of arguments associated with them. 84 * The symbol along with its arguments is called a module. Think of the module as an instance of a symbol. 85 * 86 * <p>Note: The terms symbol and module are often used interchangeably. The only difference is that a module 87 * includes any arguments that go with the symbol. In non-parametric L-systems they are truly the same.</p> 88 * </li> 89 * <li>an initial (starting) non empty list of modules. Each module consists of a symbol from the above 90 * set V and zero or more actual arguments. This initial list is the axiom and is denoted w.</li> 91 * 92 * <li>a current list of modules (the current generation) which the L-system is working on. Each 93 * iteration (generation) the L-system reads the current list and replaces it with a new list as 94 * determined by a set of production rules. The current list is initialized with the axiom. 95 * 96 * <p>Note: Often the term string is used rather than list. This comes from a simple implementation where 97 * the single character symbols are stored in a string. This library uses arrays to implement the 98 * lists of modules. This allows easier processing of modules that have parameters or if the symbol is 99 * more than one character. It also makes it easier and more efficient to deal with tree structures.</p> 100 * </li> 101 * <li>a set of production rules denoted P. The production rules define how the current list of symbols 102 * starting with the axiom is turned into the next list of symbols. The matching production rules are 103 * applied to each symbol in the current list. A rule consist of: 104 * <ul> 105 * <li>a predecessor that matches one or more modules in the current generation. A context free L-system 106 * has a single predecessor. A context sensitive L-system matches the current module in the current 107 * generation as well as its neighbors. A predecessor has to have the same symbol and same number 108 * of arguments to match.</li> 109 * 110 * <li>an optional condition which determines if the rule fires, The condition is a Boolean function 111 * which can use any of the arguments in the predecessor. The value of the arguments comes from the 112 * actual arguments in the module matched.</li> 113 * 114 * <li>one or more successors. A successor specifies what set of modules will be added to the next 115 * generation when the predecessor is matched in the current generation. 116 * If there is one successor for each rule then the L-system is deterministic. 117 * If there is more than one then it is stochastic or non-deterministic and a specific 118 * successor is chosen randomly according to its probability. 119 * The successor consists of a probability and a function that returns a list of modules. 120 * The function can set the actual arguments in each module using arbitrary expressions involving the 121 * actual arguments from the predecessor. The probability is used to determine the chance of this 122 * successor being used. The probabilities must sum to 1.</li> 123 * 124 * <p>Note: It is possible that more than one rule will match a given input module. This is more common 125 * for parametric L-systems where the condition would apply in one case and not another. The first 126 * rule that matches is always used. The only way to get stochastic behavior is to specify multiple 127 * successors in a single rule.</p> 128 * </ul> 129 * </li> 130 * <li>A set of skip symbols. These are symbols to ignore while matching context predecessors.</li> 131 * </ul> 132 * <p>In some descriptions of L-systems a distinction is made between terminal (constant) and 133 * non-terminal (variable) symbols. No such distinction is made here. If you want a symbol to be a 134 * constant then don't use it on the left hand side of a production rule.</p> 135 * 136 * <h2>General Processing:</h2> 137 * 138 * <p>There are two phases in working with an L-system: generation and rendering.</p> 139 * 140 * <p>Generation is the process of turning the initial or current generation into the next generation.</p> 141 * 142 * <p>Rendering is also known as interpretation. Rendering applies some meaning to the list of 143 * modules in the current generation and generates some kind of output. Typically the output 144 * is in the form of a visual interpretation of the module list. Rendering is up to you. 145 * You provide a function for each symbol that you want to render. That function is given the 146 * arguments of the module if the system is parametric and the module has arguments.</p> 147 * 148 * <p>The current generation is also called the input list and the next generation is called the 149 * output list. This is from the point of view of the production system.</p> 150 * <p>The generation phase works like this:</p> 151 * <pre> 152 * for each module in the current generation 153 * find the first rule that matches 154 * if (a match is found) 155 * invoke the successor function and append the resulting list to the next generation 156 * else 157 * when no rule matches the module from the current generation is copied to the next generation</pre> 158 * 159 * <p>There are two reserved symbols that are always used for a specific purpose. They are 160 * [ and ]. Open square bracket ([) begins a branch point. The close square bracket (]) ends a branch level.</p> 161 * 162 * @name lsystem 163 * @author John Snyders 164 * @license BSD 165 * @version 0.1 166 */ 167 168 /** 169 * <p>Object Lsystem implements an L-system production system.</p> 170 * 171 * <h2>Example:</h2> 172 * <p>This shows how to translate a traditional symbolic expression of an L-system into 173 * the JavaScript of this library.</p> 174 * <pre> 175 * Fr 176 * Fl --> Fr + Fl + Fr 177 * Fr --> Fl - Fr - Fl</pre> 178 * <p>becomes</p> 179 * <pre> 180 * var ls = new jjs.Lsystem( 181 * { // define the symbols and what they do 182 * Fl: function() { t.forward(d); }, 183 * Fr: function() { t.forward(d); }, 184 * "+": function() { t.left(60); }, 185 * "-": function() { t.right(60); } 186 * }, // the axiom 187 * [ {id: "Fr"} ], 188 * [ // the rules 189 * { p: [ {id: "Fl"} ], 190 * s: function() { return [{id:"Fr"},{id:"+"},{id:"Fl"},{id:"+"},{id:"Fr"}];} }, 191 * { p: [ {id: "Fr"} ], 192 * s: function() { return [{id:"Fl"},{id:"-"},{id:"Fr"},{id:"-"},{id:"Fl"}];} } 193 * ] 194 * );</pre> 195 * 196 * <p>This assumes a object <code>t</code> in scope that implements turtle graphic functionality and a variable 197 * <code>d</codde> that provides a distance to move forward.</p> 198 * 199 * @param vars - defines the set of symbols (V) and their behaviors. If a symbol has no behavior then 200 * it can be omitted from vars or the function can do nothing. This is an object where the 201 * symbol names are the object properties and the value of each property is a function that 202 * is called during rendering with the actual arguments of the module. The function's this 203 * variable is the Lsystem object. 204 * <p>Example: { "<i>symbol-id</i>": function (<i>args</i>) { <i>behavior</i> },... }</p> 205 * 206 * <p>It is possible but not very useful for vars to be an object with no properties. You might 207 * do this if some other program consumed the current generation list directly.</p> 208 * 209 * @param start - an array of modules that will be used for the initial generation. A module is 210 * an object with properties "id" and "args". Id is the symbol and args is an array of 211 * arguments. If there are no arguments then the args property can be omitted. 212 * <p>Example: [ { id: "<i>symbol-id</i>", args: [<i>arg-values</i>] },... ]</p> 213 * 214 * @param rules - a list of rules. Each rule contains a predecessor match pattern p and one or more 215 * successors functions which return the modules for the next generation. 216 * <p>Example: [ <i>rule</i>,... ]<p> 217 * <p>A rule is a predecessor list, an optional condition and a list of successors 218 * as follows:</p> 219 * <pre>Example: 220 * { p: [ { dir: <i>direction</i>, id: "<i>symbol-id</i>", a: <i>number-of-args</i> },... ], 221 * condition: function(<i>args</i>) { <i>return-boolean-expression</i> }, 222 * s: [ {p: <i>probability</i> f: function(<i>args</i>) { <i>return-modules-array</i> } },...] 223 * }</pre> 224 * <p>The first predecessor matches the current module. It is the strict predecessor. 225 * The direction must be omitted on the first predecessor and must be present on 226 * all the others. The direction is the axis along which to match the symbol. It can 227 * be one of:</p> 228 * <ul> 229 * <li>"^" previous sibling or parent</li> 230 * <li>"<" previous sibling</li> 231 * <li>">" following sibling</li> 232 * <li>"]" parent</li> 233 * <li>"[" child</li> 234 * </ul> 235 * <p>Any one of the directions can be preceeded with "." to return the starting context 236 * to the current module.</p> 237 * <p>Example: {id:"Q"},{dir:"<", id:"X"},{dir:".>",id:"Y"} will match symbol Q with a 238 * preceding sibling X and a following sibling Y. After the X is matched the current matching 239 * position is at the X so the "." prefix is used to set the context back to the Q before 240 * looking for the following sibling.</p> 241 * <p>Note: in descriptions I have seen there are just two directions that can be matched 242 * preceeding (<) and following (>). I choose to get a little more specific. So in examples 243 * where you see < used you should translate that to ^. Also make sure that the strict predecessor 244 * comes first.</p> 245 * <p>id is the symbol to match and a is the arity of the module (number of arguments). 246 * A predecessor matches when the ids are equal and the number of arguments (a) matches 247 * the number of actual arguments in the module. Example: predecessor { id: "X", a: 3 } 248 * matches module { id: "X", args: [1, "seven", {x: 2, y:3}] } because the symbol X 249 * is the same and the module has 3 arguments.</p> 250 * <p>If there is a single predecessor then the array can be omitted. 251 * Ex: p: {id: "A", a: 1}</p> 252 * 253 * <p>The condition is optional. If present it is a Boolean function 254 * which can use any of the arguments in the predecessor. Arguments are passed to this function 255 * in the same order as the predecessors that they come from. For example: If there are two predecessors, 256 * and the first one has 2 arguments and the second one has 1 argument and the condition takes arguments 257 * X, Y, Z then X gets the value of the first argument of the first predecessor, Y gets the second 258 * argument of the first predecessor and Z gets the argument of the second predecessor. 259 * The <code>this<code> reference in the condition function is the Lsystem object.</p> 260 * 261 * <p>The successor defines the modules that go into the next generation. The function f 262 * must return an array of modules. The function can take arguments from the predecessor modules in 263 * the same way as the condition function. The <code>this</code> reference in function f is the 264 * Lsystem object. Example: function() { return [ {id:"b"},{id:"c"} ];}.</p> 265 * For a branching L-system there are two choices. The reserved symbols [ and ] can be used as 266 * symbols (Ex: return [ {id:"+"},{id:"["},{id:"f"},{id:"]"}];) or you can use nested arrays 267 * (Ex: return [ {id:"+"},[{id:"f"}] ]). The only functional difference is that the first (flat) 268 * option can only use the < and > directions when doing context sensitive matches. You can effectively 269 * delete a symbol by returning an empty array.</p> 270 * <p>If there is more than one successor then the probability p is used to select one.</p> 271 * <p>If there is a single successor then the probability and array can be omitted. 272 * Ex: s: function() {...}</p> 273 * 274 * <p>The rules for each strict predecessor will be evaluated in ranked order. Having a condition 275 * is worth a 1000 points and there is one point for each predecessor. The rules are matched from 276 * highest to lowest. The first match found is used.</p> 277 * 278 * @param ignore - a map of symbols that should be ignored when context matching. this 279 * is optional and can be omitted for a context free L-system. The keys are symbols 280 * and the values are not important. 281 * <p>Example { X: "", Y: "" }</p> 282 * 283 * @constructor 284 */ 285 function Lsystem(vars, start, rules, ignore) 286 { 287 this.vars = vars; 288 this.start = start; 289 this.setRules(rules); 290 this.ignore = ignore; 291 /** 292 * Array of modules. The current generation. 293 */ 294 this.curgen = start; 295 /** 296 * Number of modules in the current generation. This includes all modules in a tree. 297 */ 298 this.moduleCount = 0; 299 /* 300 * The generation number. Starts at zero and increments each time a new generation 301 * is calculated with generate (or generateBegin/generateNext) 302 */ 303 this.generation = 0; 304 /* implementation */ 305 this.reset(); 306 this.renderIterator = null; 307 this.generateIterator = null; 308 this.nextgen = null; 309 this.stack = null; 310 } 311 312 Lsystem.prototype = { 313 314 /** 315 * Render the whole current generation. If rendering is going to take a long time 316 * then consider using renderBegin, renderHasNext, renderNext[N] methods. 317 */ 318 render: function() 319 { 320 // for each module in the current generation 321 this.renderBegin(); 322 while (this.renderHasNext()) 323 { 324 this.renderNext(); 325 } 326 }, 327 328 /** 329 * Begin the render process. Call before renderHasNext, renderNext[N]. 330 */ 331 renderBegin: function() 332 { 333 this.renderIterator = new TreeIterator(this.curgen); 334 }, 335 336 /** 337 * Determine if there are more modules in the current generation to render. 338 * @returns true if there are more modules to render. 339 * @type boolean 340 */ 341 renderHasNext: function() 342 { 343 return this.renderIterator.hasNext(); 344 }, 345 346 /** 347 * Render the next module in the current generation. 348 */ 349 renderNext: function() 350 { 351 // call the render function if there is one 352 var m = this.renderIterator.next(); 353 if (m === '[' || m === ']') 354 { 355 m = { id: m }; 356 } 357 var f = this.vars[m.id]; 358 if (f && typeof f == "function") 359 { 360 f.apply(this, m.args ? m.args : []); 361 } 362 }, 363 364 /** 365 * Render the next N modules in the current generation. 366 * @param n the number of modules to render. May be more than the actual number of 367 * modules left in the list. 368 * @returns the number of modules actually rendered. 369 */ 370 renderNextN: function(n) 371 { 372 var i = 0; 373 while (i < n && this.renderHasNext()) 374 { 375 this.renderNext(); 376 i++; 377 } 378 return i; 379 }, 380 381 /** 382 * Return the Lsystem to the initial state by assigning the start list to the 383 * current generation (curgen). The generation count is reset to zero. 384 */ 385 reset: function() 386 { 387 this.curgen = this.start; 388 this.generation = 0; 389 this.moduleCount = countTreeNodes(this.curgen, 0); 390 }, 391 392 /** 393 * Produce the next N generations. Use this method when you don't care about 394 * rendering the intermediate generations. If this could take a long time you 395 * may want to consider using generateBegin/generateNext. 396 * @param n the number of generations to produce. 397 */ 398 generateN: function(n) 399 { 400 for(var i = 0; i < n; i++) 401 { 402 this.generate(); 403 } 404 }, 405 406 /** 407 * Produce the next generation. This could take a long time. 408 */ 409 generate: function() 410 { 411 // for each module in the current generation 412 this.generateBegin(); 413 while (this.generateHasNext()) 414 { 415 this.generateNext(); 416 } 417 }, 418 419 /** 420 * Begin the generate process. Call before generateHasNext, generateNext[N]. 421 */ 422 generateBegin: function() 423 { 424 this.generateIterator = new TreeIterator(this.curgen, this.ignore); 425 this.nextgen = []; 426 this.moduleCount = 0; 427 this.stack = [ this.nextgen ]; 428 }, 429 430 /** 431 * Return true when there are more modules to generate. 432 * @return true if more modules 433 * @type boolean 434 */ 435 generateHasNext: function() 436 { 437 return this.generateIterator.hasNext(); 438 }, 439 440 /** 441 * Generate the next generation output for the next module in this current generation. 442 */ 443 generateNext: function() 444 { 445 var module = this.generateIterator.next(); 446 if (module === '[') 447 { 448 this.stack.push([]); 449 this.moduleCount++; 450 } 451 else if (module === ']') 452 { 453 var top = this.stack.pop(); 454 this.stack[this.stack.length-1].push(top); 455 this.moduleCount++; 456 } 457 else if (module.id !== '!') // ! never gets copied or matched 458 { 459 var successors = this.getSuccessors(module, this.generateIterator); 460 if (successors !== null) 461 { 462 // add the modules to the next generation 463 for (var j = 0; j < successors.length; j++) 464 { 465 this.stack[this.stack.length-1].push(successors[j]); 466 if (isArray(successors[j])) 467 { 468 this.moduleCount += countTreeNodes(successors[j], 0) + 2; 469 } 470 else 471 { 472 this.moduleCount++; 473 } 474 } 475 } 476 else 477 { 478 // if no rules match then just copy module to next generation 479 this.stack[this.stack.length-1].push(module); 480 this.moduleCount++; 481 } 482 } 483 // check if done 484 if (!this.generateIterator.hasNext()) 485 { 486 this.curgen = this.nextgen; 487 this.generation++; 488 } 489 }, 490 491 /** 492 * Generate output for the next n modules. If there are fewer than n modules remaining 493 * to process then it stops early. 494 * @param n the number of modules to process. May be more than the actual number of 495 * modules left in the current generation. 496 * @return number of modules processed. 497 */ 498 generateNextN: function(n) 499 { 500 var i = 0; 501 while (i < n && this.generateHasNext()) 502 { 503 this.generateNext(); 504 i++; 505 } 506 return i; 507 }, 508 509 /** 510 * Set the rules. Usually the rules are set in the constructor but this can 511 * be used to change the rules after the fact. 512 */ 513 setRules: function(rules) 514 { 515 var ruleMap = {}; 516 // for each rule 517 for (var r = 0; r < rules.length; r++) 518 { 519 var rule = rules[r]; 520 // put the rules in normal form 521 522 // first the predecsssor 523 if (typeof rule.p == "object" && !isArray(rule.p)) 524 { 525 rule.p = [ rule.p ]; 526 } 527 528 for (var i = 0; i < rule.p.length; i++) 529 { 530 var p = rule.p[i]; 531 if (i === 0 && p.dir) 532 { 533 throw "Strict predecessor must not specify a direction."; 534 } 535 else if (i > 0 && !p.dir) 536 { 537 throw "Context predecessor must specify a direction."; 538 } 539 if (!p.a) 540 { 541 p.a = 0; 542 } 543 if (i === 0) 544 { 545 var key = p.id + p.a; 546 if (!ruleMap[key]) 547 { 548 ruleMap[key] = []; 549 } 550 ruleMap[key].push(rule); 551 } 552 } 553 // next the successor 554 if (typeof rule.s == "function") 555 { 556 rule.s = [ {p: 1, f: rule.s} ]; 557 } 558 else 559 { 560 var s = rule.s; 561 var sum = 0; 562 // check probabilities 563 for (var j = 0; j < s.length; j++) 564 { 565 sum += s[j].p; 566 } 567 if (sum != 1.0) 568 { 569 throw "Probabilities must sum to 1."; 570 } 571 // change probabilities to sum of probability and previous probabilities. 572 sum = 0; 573 for (j = 0; j < s.length; j++) 574 { 575 sum += s[j].p; 576 s[j].p = sum; 577 } 578 } 579 this.rules = rules; 580 this.ruleMap = ruleMap; 581 } 582 // order rules from most specific to least. 583 // conditions have the ability to be most specific 584 // then the more predecessors to match the more specific. 585 for (var rm in this.ruleMap) if (this.ruleMap.hasOwnProperty(rm)) 586 { 587 this.ruleMap[rm].sort(function (r1, r2) { 588 function rank(r) { 589 var i = r.p.length; 590 if (r.condition) 591 { 592 i += 1000; 593 } 594 return i; 595 } 596 return rank(r2) - rank(r1); 597 }); 598 } 599 }, 600 601 /** 602 * Return a string representation of the current generation 603 */ 604 curgenToString: function(sep, indent, wrap) 605 { 606 var curIndent = ""; 607 var it = new TreeIterator(this.curgen); 608 var i = 0; // keep track of commas, and new lines 609 var dedent = false; 610 var out = "["; 611 while (it.hasNext()) 612 { 613 var module = it.next(); 614 if (module === '[' || module === ']') 615 { 616 module = { id: module }; 617 } 618 if (indent) 619 { 620 if (module.id == "[") 621 { 622 if (i > 0) 623 { 624 out += sep; 625 } 626 curIndent += indent; 627 out += "\r\n" + curIndent; 628 i = 0; 629 } 630 if (module.id == "]") 631 { 632 curIndent = curIndent.substring(0, curIndent.length - indent.length); 633 } 634 } 635 if (wrap && i > wrap) 636 { 637 out += sep + "\r\n" + curIndent; 638 i = 0; 639 } 640 if (i > 0 && module.id != ']') 641 { 642 out += sep; 643 } 644 if (dedent) 645 { 646 out += "\r\n" + curIndent; 647 dedent = false; 648 } 649 650 out += module.id; 651 652 if (module.args && module.args.length > 0) 653 { 654 out += "("; 655 for (var j = 0; j < module.args.length; j++) 656 { 657 if (j > 0) 658 { 659 out += ", "; 660 } 661 out += this.valueToString(module.args[j]); 662 } 663 out += ")"; 664 } 665 if (module.id == "[") 666 { 667 i = 0; 668 } 669 else 670 { 671 i++; 672 } 673 if (indent && module.id == "]") 674 { 675 dedent = true; 676 } 677 } 678 679 out += "]"; 680 return out; 681 }, 682 683 toString: function(indent, sep, wrap) 684 { 685 return this.curgenToString(", "); 686 }, 687 688 /* 689 ** Implementation 690 */ 691 692 valueToString: function(val) 693 { 694 var out = ""; 695 var prop; 696 var i; 697 if (isArray(val)) 698 { 699 out += "["; 700 for (i = 0; i < val.length; i++) 701 { 702 if (i > 0) 703 { 704 out += ", "; 705 } 706 out += this.valueToString(val[i]); 707 } 708 out += "]"; 709 } 710 else if (typeof val === 'object') 711 { 712 out += "{"; 713 i = 0; 714 for (prop in val) if (val.hasOwnProperty(prop)) 715 { 716 if (i > 0) 717 { 718 out += ", "; 719 } 720 out += prop + ": "; 721 out += this.valueToString(val[prop]); 722 i++; 723 } 724 out += "}"; 725 } 726 else 727 { 728 out += val; 729 } 730 return out; 731 }, 732 733 getSuccessors: function(module, it) 734 { 735 // Look up possible matching rules by module 736 var moduleArgsLen = module.args ? module.args.length : 0; 737 var key = module.id + moduleArgsLen; 738 var rules = this.ruleMap[key]; 739 if (!rules) 740 { 741 return null; 742 } 743 // for now linear search and use first found 744 for (var i = 0; i < rules.length; i++) 745 { 746 var rule = rules[i]; 747 var args = this.matchRule(rule, module, it); 748 if (args !== null) 749 { 750 // a match was found 751 // fire the production rule to get a new list of modules to substitute 752 if (rule.s.length == 1) 753 { 754 return rule.s[0].f.apply(this, args); 755 } 756 // if more than one choose according to probabilities 757 var choice = Math.random(); 758 for (var j = 0; j < rule.s.length; j++) 759 { 760 if (choice < rule.s[j].p) 761 { 762 return rule.s[j].f.apply(this, args); 763 } 764 } 765 throw "Internal error. Probabilities don't make sense."; 766 } 767 } 768 return null; 769 }, 770 771 /* 772 Attempt to match a rule with a particular module at position it 773 774 Return an array of argument values if there is a match and null if there is no match 775 the argument array may be empty if there are no arguments in any of the predecessors 776 */ 777 matchRule: function(rule, module, it) 778 { 779 var ruleArgs = []; 780 var curModule = module; 781 it.resetContext(); 782 783 // for each predecessor 784 for (var i = 0; i < rule.p.length; i++) 785 { 786 var p = rule.p[i]; 787 // the first rule matches with the strict predecessor (module) 788 if (i > 0) 789 { 790 // after that the direction determines the context module to match 791 var dir = p.dir; 792 if (dir[0] == ".") 793 { 794 it.resetContext(); 795 dir = dir[1]; 796 } 797 switch (dir[0]) 798 { 799 case "^": 800 curModule = it.previousSiblingOrParent(); 801 break; 802 case "<": 803 curModule = it.previousSibling(); 804 break; 805 case ">": 806 curModule = it.nextSibling(); 807 break; 808 case "[": 809 curModule = it.child(); 810 break; 811 case "]": 812 curModule = it.parent(); 813 break; 814 default: 815 throw "Invalid direction '" + dir + "'"; 816 } 817 if (!curModule) 818 { 819 return null; // no match 820 } 821 } 822 if (this.matchModule(p, curModule)) 823 { 824 // if there are any args 825 if (curModule.args) 826 { 827 // update ruleArgs with actual arg values from module 828 for (var j = 0; j < curModule.args.length; j++) 829 { 830 // add actual arg value 831 ruleArgs.push(curModule.args[j]); 832 } 833 } 834 } 835 else 836 { 837 return null; // no match 838 } 839 } 840 // all the predecessors matched and all arg values have been gathered 841 // now evaluate the condition if there is one 842 if (rule.condition) 843 { 844 if (!rule.condition.apply(this, ruleArgs)) 845 { 846 return null; // no match 847 } 848 } 849 return ruleArgs; 850 }, 851 852 /* 853 Match a single predecessor item (match) in a rule with a single module. 854 A predecessor matches a module if the ids are the same and the number 855 of arguments matches the actual number of arguments in the module. 856 857 match - the rule predecessor item to match 858 module - the module to match with 859 860 Return true if they match false otherwise. 861 */ 862 matchModule: function(match, module) 863 { 864 if (match.id == module.id) 865 { 866 var matchArgsLen = match.a ? match.a : 0; 867 var moduleArgsLen = module.args ? module.args.length : 0; 868 if (matchArgsLen == moduleArgsLen) 869 { 870 return true; 871 } 872 } 873 return false; 874 } 875 876 }; 877 878 // utility functions 879 function isArray(a) 880 { 881 return typeof a === 'object' && a.constructor === Array; 882 } 883 884 function countTreeNodes(t, c) 885 { 886 for (var i = 0; i < t.length; i++) 887 { 888 if (isArray(t[i])) 889 { 890 // the brackets count too 891 c += countTreeNodes(t[i], c) + 2; 892 } 893 else 894 { 895 c++; 896 } 897 } 898 return c; 899 } 900 901 /* 902 Used internally by Lsystem for traversing a potentially 903 recursive module list. 904 Has 2 functions. 905 1) iterate over the tree 906 methods: hasNext and next 907 2) at any point (context) in the iteration of the tree allow finding nodes from the current context 908 all the other public methods 909 @constructor 910 @private 911 */ 912 function TreeIterator(tree, ignore) 913 { 914 this.stack = [{ i: 0, ci: -1, a: tree }]; 915 // i is current iteration position in a 916 // ci is current context position in a 917 this.depth = 1; // track depth for iterating because stack may get changed during context operations 918 this.clevel = 0; // current context level 919 this.ignore = ignore || { }; 920 } 921 922 TreeIterator.prototype = { 923 hasNext: function() 924 { 925 return !this.empty(); 926 }, 927 928 next: function() 929 { 930 var m; 931 if (!this.empty()) 932 { 933 var top = this.peek(); 934 if (top.i < top.a.length) 935 { 936 m = top.a[top.i]; 937 top.ci = top.i; 938 top.i++; 939 if (isArray(m)) 940 { 941 this.push(m); 942 return "["; 943 } 944 return m; 945 } 946 this.pop(); 947 return "]"; 948 } 949 throw "No next."; 950 }, 951 952 resetContext: function () 953 { 954 var level; 955 while (this.stack.length > this.depth) 956 { 957 this.clevel--; 958 this.stack.pop(); 959 } 960 if (this.clevel < 0) 961 { 962 this.clevel = 0; 963 } 964 level = this.stack[this.clevel]; 965 for (var l = this.clevel; l < this.stack.length; l++) 966 { 967 level = this.stack[l]; 968 level.ci = level.i - 1; 969 } 970 this.clevel = this.stack.length - 1; 971 }, 972 973 previousSiblingOrParent: function () 974 { 975 var level; 976 var m; 977 978 while (this.clevel >= 0) 979 { 980 level = this.stack[this.clevel]; 981 for (level.ci--; level.ci >= 0; level.ci--) 982 { 983 m = level.a[level.ci]; 984 if (!this.skip(m)) 985 { 986 return m; 987 } 988 } 989 this.clevel--; 990 } 991 return null; 992 }, 993 994 previousSibling: function () 995 { 996 var level; 997 var m; 998 if (this.clevel < 0) 999 { 1000 return null; 1001 } 1002 level = this.stack[this.clevel]; 1003 1004 for (level.ci--; level.ci >= 0; level.ci--) 1005 { 1006 m = level.a[level.ci]; 1007 if (!this.skip(m)) 1008 { 1009 return m; 1010 } 1011 } 1012 return null; 1013 }, 1014 1015 nextSibling: function() 1016 { 1017 var level; 1018 var m; 1019 if (this.clevel < 0) 1020 { 1021 return null; 1022 } 1023 level = this.stack[this.clevel]; 1024 1025 for (level.ci++; level.ci < level.a.length; level.ci++) 1026 { 1027 m = level.a[level.ci]; 1028 if (!this.skip(m)) 1029 { 1030 return m; 1031 } 1032 } 1033 return null; 1034 }, 1035 1036 parent: function() 1037 { 1038 var level; 1039 var m; 1040 var atLeastOneArray = false; 1041 1042 while (this.clevel >= 0) 1043 { 1044 level = this.stack[this.clevel]; 1045 for (level.ci--; level.ci >= 0; level.ci--) 1046 { 1047 m = level.a[level.ci]; 1048 if (isArray(m)) 1049 { 1050 atLeastOneArray = true; 1051 } 1052 else 1053 { 1054 if (atLeastOneArray) 1055 { 1056 return m; 1057 } 1058 return null; 1059 } 1060 } 1061 atLeastOneArray = true; 1062 this.clevel--; 1063 } 1064 return null; 1065 }, 1066 1067 // p is predicate function that takes a module as input and returns true if it is a matching child 1068 findChild: function(p) 1069 { 1070 var level; 1071 var m; 1072 var atLeastOneArray = false; 1073 1074 if (this.clevel < 0) 1075 { 1076 return null; 1077 } 1078 level = this.stack[this.clevel]; 1079 1080 for (level.ci++; level.ci < level.a.length; level.ci++) 1081 { 1082 m = level.a[level.ci]; 1083 if (isArray(m)) 1084 { 1085 atLeastOneArray = true; 1086 if (p(m[0])) 1087 { 1088 // establish context 1089 if (this.clevel == this.stack.length - 1) 1090 { 1091 this.stack.push({i: 0, ci: 0, a: m}); 1092 } 1093 this.clevel++; 1094 return m[0]; 1095 } 1096 } 1097 else 1098 { 1099 if (atLeastOneArray) 1100 { 1101 if (p(m)) 1102 { 1103 return m; 1104 } 1105 } 1106 return null; 1107 } 1108 } 1109 return null; 1110 }, 1111 1112 /* 1113 Implementation 1114 */ 1115 peek: function() 1116 { 1117 return this.stack[this.stack.length - 1]; 1118 }, 1119 1120 empty: function() 1121 { 1122 while (this.stack.length > this.depth) 1123 { 1124 this.stack.pop(); 1125 } 1126 return this.stack.length === 0 || this.stack.length === 1 && 1127 this.stack[0].i >= this.stack[0].a.length; 1128 }, 1129 1130 pop: function() 1131 { 1132 this.depth--; 1133 return this.stack.pop(); 1134 }, 1135 1136 push: function(sub) 1137 { 1138 this.depth++; 1139 this.stack.push({i: 0, ci: -1, a: sub}); 1140 }, 1141 1142 skip: function(m) 1143 { 1144 return isArray(m) || this.ignore[m.id] !== undefined; 1145 } 1146 1147 }; 1148 // for testing 1149 window.TreeIterator = TreeIterator; 1150 1151 return Lsystem; 1152 })(); 1153