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