home *** CD-ROM | disk | FTP | other *** search
/ Graphics 16,000 / graphics-16000.iso / msdos / utils / graphtal.lzh / Graphtal.Amiga / LSystem.C < prev    next >
C/C++ Source or Header  |  1992-11-17  |  7KB  |  299 lines
  1. /*
  2.  * LSystem.C - methods for classes ProductionSlot, Table and LSystem.
  3.  *
  4.  * Copyright (C) 1992, Christoph Streit (streit@iam.unibe.ch)
  5.  *                     University of Berne, Switzerland
  6.  * All rights reserved.
  7.  *
  8.  * This software may be freely copied, modified, and redistributed
  9.  * provided that this copyright notice is preserved on all copies.
  10.  *
  11.  * You may not distribute this software, in whole or in part, as part of
  12.  * any commercial product without the express consent of the authors.
  13.  *
  14.  * There is no warranty or other guarantee of fitness of this software
  15.  * for any purpose.  It is provided solely "as is".
  16.  *
  17.  */
  18.  
  19. #include "LSystem.h"
  20. #include "Options.h"
  21.  
  22. implementList(TableList, TablePtr);
  23. implementList(DerivationList, DerivationItemPtr);
  24.  
  25. //___________________________________________________________ Table Hashing
  26.  
  27. unsigned int modHash(const char* aString, long arg) { 
  28.   return (hash(aString, arg) % HASH_ARRAY_SIZE); 
  29. }
  30.  
  31. static inline unsigned int rehash(int place) {
  32.   return (place + 17) % HASH_ARRAY_SIZE; 
  33. }
  34.  
  35. //___________________________________________________________ Production
  36.  
  37. ProductionSlot::ProductionSlot(Production* p)
  38. : name(p->name())
  39. {
  40.   argCount = p->argCount();
  41.  
  42.   productions = new ProductionList(1);
  43.   productions->append(p);
  44.  
  45. }
  46.  
  47. ProductionSlot::~ProductionSlot()
  48. {
  49.   delete productions;
  50. }
  51.  
  52. void ProductionSlot::append(Production* p)
  53. {
  54.   productions->append(p);
  55. }
  56.  
  57. int ProductionSlot::match(Production* p) const
  58. {
  59.   return (name == p->name()) && (argCount == p->argCount());
  60. }
  61.  
  62. int ProductionSlot::match(Module* m) const
  63. {
  64.   return (name == m->name()) && (argCount == m->argCount());
  65. }
  66.  
  67. //___________________________________________________________ Table
  68.  
  69. /*
  70.  * Takes a list of productions and stores them in a hashed array
  71.  * to achieve fast access.
  72.  */
  73.  
  74. Table::Table(const Name& n, ProductionList* plist)
  75. : _name(n), productions(plist)
  76. {
  77.   register long i;
  78.   int hashvalue;
  79.  
  80.   /*
  81.    * Initialize the array.
  82.    */
  83.   for (i=0; i<HASH_ARRAY_SIZE; i++)
  84.     pslots[i] = NULL;
  85.  
  86.   for (i=0; i<plist->count(); i++) {
  87.     hashvalue = plist->item(i)->hashValue();
  88.  
  89.     /*
  90.      * Try to find a slot to store the production; a infinite loop can
  91.      * occur, if we need more than HASH_ARRAY_SIZE ProductionSlots, 
  92.      * which will rarely happen!
  93.      */
  94.     while(1) {
  95.       /*
  96.        * No ProductionSlot yet -> instantiate a new one.
  97.        */
  98.       if (pslots[hashvalue] == NULL) {
  99.     pslots[hashvalue] = new ProductionSlot(plist->item(i));
  100.     break;
  101.       }
  102.       /*
  103.        * ProductionSlot is present, but is it the right on for the
  104.        * production.
  105.        */
  106.       else if (pslots[hashvalue]->match(plist->item(i))) {
  107.     pslots[hashvalue]->append(plist->item(i));
  108.     break;
  109.       }
  110.       /*
  111.        * Not lucky yet, try another place.
  112.        */
  113.       else
  114.     hashvalue = rehash(hashvalue);
  115.     }
  116.   }
  117. }
  118.  
  119. Table::~Table()
  120. {
  121.   long i;
  122.  
  123.   for (i=0; i<productions->count(); i++)
  124.     delete productions->item(i);
  125.   delete productions;
  126.  
  127.   for (i=0; i<HASH_ARRAY_SIZE; i++)
  128.     if (pslots[i])
  129.       delete pslots[i];
  130. }
  131.  
  132. /*
  133.  * Apply steps-times the productions of the table to the given list of
  134.  * modules.
  135.  */
  136.  
  137. ModuleList* Table::execute(ModuleList* m, int steps)
  138. {
  139.   result = new ModuleList(1000); 
  140.  
  141.   for (register long i=0; i<m->count(); i++)
  142.     rexecute(m->item(i), steps);
  143.   delete m;
  144.  
  145.   return result;
  146. }
  147.  
  148. /*
  149.  * Recursively apply the productions of the table to the given module.
  150.  */
  151.  
  152. void Table::rexecute(Module* m, int steps)
  153. {
  154.   ModuleList* r;
  155.   if (steps != 0)  // -1 = INFINITY, STOP when 0
  156.     if (r = apply(m)) {
  157.       for (register long i=0; i<r->count(); i++)
  158.     rexecute(r->item(i), steps-1);
  159.       delete m; 
  160.       delete r;
  161.     }
  162.     else
  163.       result->append(m);
  164.   else
  165.     result->append(m);
  166. }
  167.  
  168. /*
  169.  * Look for a matching production and evaluate the replacement for
  170.  * the module m.
  171.  */
  172.  
  173. ModuleList* Table::apply(Module* m)
  174. {
  175.   int hashvalue = m->hashValue();
  176.  
  177.   while(1) {
  178.     /*
  179.      * Is there a production which matches the module name and the 
  180.      * number number of arguments of the module m.
  181.      */
  182.     if (pslots[hashvalue])
  183.       if (pslots[hashvalue]->match(m)) {
  184.     /*
  185.      * Yes: bind the actual parameters of the module to the formal
  186.      *      ones of the productions stored in the ProductionSlot.
  187.      */
  188.     m->bind();
  189.     break;
  190.       }
  191.       else
  192.     hashvalue = rehash(hashvalue);
  193.     else
  194.       return NULL; // no production could be applied
  195.   }
  196.  
  197.   /*
  198.    * Clone the successor of the first production in the ProductionSlot
  199.    * which condition evaluates to TRUE.
  200.    */
  201.   ProductionList* pl = pslots[hashvalue]->productions;
  202.   for (register long i=0; i<pl->count(); i++)
  203.     if (pl->item(i)->evalCondition())
  204.       return pl->item(i)->cloneSuccessor();
  205.  
  206.   /*
  207.    * No production could be applied.
  208.    */
  209.   return NULL;
  210. }
  211.  
  212. ostream& operator<<(ostream& os, const Table& t)
  213. {
  214.   os << "table " << t._name << '\n';
  215.   for (long i=0; i<t.productions->count(); i++)
  216.     os << "  " << *t.productions->item(i);
  217.        
  218.   return os;
  219. }
  220.  
  221. //___________________________________________________________ LSystem
  222.  
  223. ostream& operator<<(ostream& os, const DerivationItem& d)
  224. {
  225.   os <<  d.table->name() << '(';
  226.   if (d.steps < 0) 
  227.     os << "infinity";
  228.   else
  229.     os << d.steps;
  230.   os << ')';
  231.  
  232.   return os;
  233. }
  234.  
  235. LSystem::LSystem(const Name& n, TableList* t, ProdModuleList* a,
  236.          DerivationList* d)
  237. : name(n), tables(t), axiom(a), derivation(d)
  238. {}
  239.  
  240. LSystem::~LSystem()
  241. { 
  242.   long i;
  243.   for (i=0; i<tables->count(); i++)
  244.     delete tables->item(i);
  245.   delete tables;
  246.   for (i=0; i<axiom->count(); i++)
  247.     delete axiom->item(i);
  248.   delete axiom;
  249.   for (i=0; i<derivation->count(); i++)
  250.     delete derivation->item(i);
  251.   delete derivation;
  252. }
  253.  
  254. ModuleList* LSystem::execute()
  255. {
  256.   ModuleList* result;
  257.   DerivationItem* d;
  258.   register long i;
  259.  
  260.   /*
  261.    * Replace the ProdModuleList by a ModuleList -> 0. iteration step.
  262.    */
  263.   result = new ModuleList(axiom->count());
  264.   for (i=0; i<axiom->count(); i++)
  265.     result->append(new Module(axiom->item(i)));
  266.  
  267.   if (!theOptions.quiet) cerr << "\nExecution:\n";
  268.  
  269.   for (i=0; i<derivation->count(); i++) {
  270.     d = derivation->item(i);
  271.     if (!theOptions.quiet) cerr << "\tTable " << *d << '\n';
  272.     result = d->table->execute(result, d->steps);
  273.   }
  274.   if (theOptions.verbose)
  275.     cerr << "\n\n#Modules: " << result->count() << "\n\n";
  276.  
  277.   return result;
  278. }
  279.  
  280. ostream& operator<<(ostream& os, const LSystem& lsys)
  281. {
  282.   os << "lsystem " << lsys.name << "\n\n";
  283.  
  284.   for (long i=0; i<lsys.tables->count(); i++)
  285.     os << *lsys.tables->item(i) << '\n';
  286.  
  287.   os << "Axiom ";
  288.   for (i=0; i<lsys.axiom->count(); i++)
  289.     os << *lsys.axiom->item(i) << ' ';
  290.   os << '\n';
  291.  
  292.   os << "Derivation ";
  293.   for (i=0; i<lsys.derivation->count(); i++)
  294.     os << *lsys.derivation->item(i) << ' ';
  295.   os << '\n';
  296.   
  297.   return os;
  298. }
  299.