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