/*
 * l-system representation and evaluation
 */

#include "config.h"

#include <algorithm>
#include <iterator>
#include <iostream>
#include <sstream>

#include <cstdlib>
#include <cmath>

#include "tokens.h"
#include "DLGLexer.h"
#include "Parser.h"

#include "lsys.h"

#ifndef M_PI
# define M_PI           3.14159265358979323846  /* pi */
#endif

bool operator <(const lsys::arg_spec &a, const lsys::arg_spec &b) t_no
{
  return a.nargs < b.nargs
         || (a.nargs == b.nargs && a.arg < b.arg)
         || (a.arg == b.arg && a.str < b.str);
}

ostream &operator <<(ostream &o, const file_pos &p) t_no
{
  return o << p.path << ":" << p.line << ", column " << p.col;
}

ostream &operator <<(ostream &o, const module_vec &v) t_no
{
//  o << "[" << hex << (long)&v << " " << (long)v.s << dec << "|";//D
  
  for (module_pos i = v.begin (); i != v.end (); ++i)
     o << *i << " ";
  
//  o << "]";
  
  return o;
}

ostream &operator <<(ostream &o, const module &m) t_no
{
  static const char *delim[2][2] = {
    { ",", ")" },
    { " ", ""  }
  };
  
//  if (m.is_expr) o << "E:";
//  if (m.is_num) o << "N:";
  
  o << m.str;
  
  if (!m.empty ())
    {
      o << (m.str.size () ? "(" : "'");
      
      for (module_pos i = m.begin (); i != m.end (); )
        {
          o << *i;
          o << delim[!m.str.size ()][++i == m.end ()];
        }
    }
  
  return o;
}

ostream &operator <<(ostream &o, const rule &r) t_no
{
  if (r.pre.size ())
    o << r.pre  << " < ";
  
  o << (module)r << " ";
  if (r.post.size ())
    o << "> " << r.post << " ";
  
  if (r.constraint.is_expr)
    o << " '"  << r.constraint << "' ";
  
  o << "=> " << r.repl;
  o << ", "  << r.iterations;
  return o;
}

static ostream &operator <<(ostream &o, const lsys::arg_spec &a) t_no
{
  return o << "<" << a.str << "/" << a.nargs << ", " << a.arg << ">";
}

ostream &operator <<(ostream &o, const lsys &l) t_no
{
  for (module_map::const_iterator i = l.defines.begin (); i != l.defines.end (); ++i)
    o << "DEFINE: " << i->first << " = " << i->second << endl;
  
  o << "PARENT: " << (l.parent ? l.parent->str : "(none)") << endl;
  
  o << "CHILDREN:";
  for (hash_map<string, lsys *>::const_iterator i = l.sub_lsys.begin (); i != l.sub_lsys.end (); ++i)
    o << " " << i->second->str;
  o << endl;
  
  o << "IGNORE: ";
  copy (l.ignore_module.begin (), l.ignore_module.end (), ostream_iterator<const string>(o, " "));
  o << endl;
  
  for (rule_map::const_iterator i = l.rules.begin (); i != l.rules.end (); ++i)
    for (rule_map::mapped_type::const_iterator j = i->second.begin (); j != i->second.end (); ++j)
      o << "RULE " << i->first << "/" << j->size () << ": " << *j << endl;
  
  o << "ARG_IS_NUMERIC:";
  for (set<lsys::arg_spec>::const_iterator i = l.arg_is_numeric.begin ();
       i != l.arg_is_numeric.end ();
       ++i)
    o << " " << *i;
  o << endl;
  
  return o;
}

lsys::lsys () t_no
{
  parent = 0;
  
  arg_spec s;
  s.str = "f";  s.nargs = 1; s.arg = 0; arg_is_numeric.insert (s);
  s.str = "F";  s.nargs = 1; s.arg = 0; arg_is_numeric.insert (s);
  s.str = "+";  s.nargs = 1; s.arg = 0; arg_is_numeric.insert (s);
  s.str = "-";  s.nargs = 1; s.arg = 0; arg_is_numeric.insert (s);
  s.str = "^";  s.nargs = 1; s.arg = 0; arg_is_numeric.insert (s);
  s.str = "&";  s.nargs = 1; s.arg = 0; arg_is_numeric.insert (s);
  s.str = "/";  s.nargs = 1; s.arg = 0; arg_is_numeric.insert (s);
  s.str = "\\"; s.nargs = 1; s.arg = 0; arg_is_numeric.insert (s);
  
  ignore_module.insert ("attr");
}

lsys::~lsys () t_no
{
  hash_map<string, lsys*>::iterator i;
  
  while ((i = sub_lsys.begin ()) != sub_lsys.end ())
    {
      delete i->second;
      sub_lsys.erase (i);
    }
}

void lsys::mark_numeric (const map<string, arg_spec> &which, const module &v) t_no
{
  for (module_pos i = v.begin (); i != v.end (); ++i)
    {
      map<string,arg_spec>::const_iterator d = which.find (i->str);
      
      if (d != which.end ())
        arg_is_numeric.insert (d->second);
      else
        for (module_pos a = i->begin (); a != i->end (); a++)
          mark_numeric (which, *a);
    }
}

void lsys::add_lsys (lsys *l) t_err
{
  if (!l->str.size ())
    {
      delete l;
      throw error ("unable to determine ruleset name", *l);
    }
  
  l->parent = this;
  sub_lsys [l->str] = l;
}

void lsys::add_rule (rule r) t_err
{
  map<string,arg_spec> which;
  arg_spec spec;
  
  spec.str   = r.str;
  spec.nargs = r.size ();
  spec.arg   = 0;
  
  for (rule::iterator i = r.begin (); i != r.end (); ++i, spec.arg++)
    if (i->size () != 0)
      throw error("rule parameter too complex", *i);
    else if (i->is_expr)
      {
        if (i->is_num)
          {
            char arg[30];
            sprintf (arg, "_arg%d", spec.arg);
            
            module m(arg);          m.is_expr = 1;
            module eq("==", m, *i); eq.is_expr = 1;
            
            r.constraint = r.constraint.empty ()
                           ? eq
                           : module ("&&", r.constraint, eq);
            *i = m;
          }
        which.insert (pair<string, arg_spec>(i->str, spec));
      }
  
  mark_numeric (which, r.constraint);
  
  if (rules.size () == 0)
    module::operator =((module)r);
  
  rules[r.str].push_back (r);
}

static double eval_expr_2 (const module &m, const module_map &l, const module_map &g) t_err
{
  switch (m.size ())
    {
    case 0:
      {
        if (m.is_num)
          return m.num;
        else
          {
            module_map::const_iterator i;
            
            if ((i = l.find (m.str)) != l.end ()
                || (i = g.find (m.str)) != g.end ())
              return eval_expr (i->second, g, module_map ());
            
            throw error ("undefined identifier in expression", m);
          }
      }
    
    case 1:
      if (m.str == "!" )	return !eval_expr_2 (m.first (), l, g);
      if (m.str == "sin" )	return sin  (eval_expr_2 (m.first (), l, g));
      if (m.str == "cos" )	return cos  (eval_expr_2 (m.first (), l, g));
      if (m.str == "tan" )	return tan  (eval_expr_2 (m.first (), l, g));
      if (m.str == "asin" )	return asin (eval_expr_2 (m.first (), l, g));
      if (m.str == "acos" )	return acos (eval_expr_2 (m.first (), l, g));
      if (m.str == "atan" )	return atan (eval_expr_2 (m.first (), l, g));
      if (m.str == "int" )	return int  (eval_expr_2 (m.first (), l, g));
      if (m.str == "ceil" )	return ceil (eval_expr_2 (m.first (), l, g));
      if (m.str == "floor" )	return floor(eval_expr_2 (m.first (), l, g));
      if (m.str == "rand" )	return      (eval_expr_2 (m.first (), l, g)) * rand () / RAND_MAX;
      if (m.str == "irand" )	return int ((eval_expr_2 (m.first (), l, g)) * rand () / RAND_MAX);
      if (m.str == "log" )	return log  (eval_expr_2 (m.first (), l, g));
      if (m.str == "abs" )	return abs  (eval_expr_2 (m.first (), l, g));
      if (m.str == "deg" )	return      (eval_expr_2 (m.first (), l, g)) * 180.0 / M_PI;
      if (m.str == "rad" )	return      (eval_expr_2 (m.first (), l, g)) * M_PI / 180.0;
      if (m.str == "sqrt" )	return sqrt (eval_expr_2 (m.first (), l, g));
      
      throw error ("unknown unary function in expression", m);
    
    case 2:
      if (m.str == "+" )	return eval_expr_2 (m.first (), l, g) +  eval_expr_2 (m.second (), l, g);
      if (m.str == "-" )	return eval_expr_2 (m.first (), l, g) -  eval_expr_2 (m.second (), l, g);
      if (m.str == "*" )	return eval_expr_2 (m.first (), l, g) *  eval_expr_2 (m.second (), l, g);
      if (m.str == "/" )	return eval_expr_2 (m.first (), l, g) /  eval_expr_2 (m.second (), l, g);
      if (m.str == "<" )	return eval_expr_2 (m.first (), l, g) <  eval_expr_2 (m.second (), l, g);
      if (m.str == "<=")	return eval_expr_2 (m.first (), l, g) <= eval_expr_2 (m.second (), l, g);
      if (m.str == "==")	return equal (eval_expr_2 (m.first (), l, g), eval_expr_2 (m.second (), l, g));
      if (m.str == "!=")	return eval_expr_2 (m.first (), l, g) != eval_expr_2 (m.second (), l, g);
      if (m.str == ">" )	return eval_expr_2 (m.first (), l, g) >  eval_expr_2 (m.second (), l, g);
      if (m.str == ">=")	return eval_expr_2 (m.first (), l, g) >= eval_expr_2 (m.second (), l, g);
      if (m.str == "&&")	return eval_expr_2 (m.first (), l, g) && eval_expr_2 (m.second (), l, g);
      if (m.str == "||")	return eval_expr_2 (m.first (), l, g) || eval_expr_2 (m.second (), l, g);
      if (m.str == "%" )	return fmod (eval_expr_2 (m.first (), l, g), eval_expr_2 (m.second (), l, g));
      if (m.str == "^" )	return pow  (eval_expr_2 (m.first (), l, g), eval_expr_2 (m.second (), l, g));
      
      throw error ("unknown binary function in expression", m);
    
    default:
      throw error ("can only evaluate modules with 0, 1 or 2 arguments", m);
    }
  
  throw error("reached end of non-void function eval_expr_2", m);
}

double eval_expr (const module &expr, const module_map &locals, const module_map &globals) t_err
{
  return eval_expr_2 (expr, locals, globals);
}

double lsys::eval_numeric (const module &expr, module_map context) const t_err
{
  return eval_expr (expr, context, defines);
}

static void get_vars (const module_vec &par, const module_vec &arg, module_map &vars) t_no
{
  for (module_pos a = arg.begin (), b = par.begin ();
       a != arg.end ();
       ++a, ++b)
    vars [b->str] = *a;
}

bool lsys::match_rule (const rule &r, const module_vec &v, module_pos i, module_map &vars) const t_err
{
  int nested = 0;
  
  if (r.module::match (*i))
    {
      module_pos j;
      
      // match heading context
      j = i;
      for (module_pos z = r.pre.end ();
           z != r.pre.begin ();
           )
        {
          if (j == v.begin ())
            return false;
          
          --j;
          if (j->str == "]")
            nested++;
          else if (j->str == "[")
            nested = nested ? nested-1 : nested;
          else if (!nested && ignore_module.find (j->str) == ignore_module.end ())
            {
              --z;
              if (!z->match (*j))
                return false;
              
              get_vars (*z, *j, vars);
            }
        }
      
      // match trailing context
      j = i;
      for (module_pos z = r.post.begin ();
           z != r.post.end ();
           )
        {
          ++j;
          if (j == v.end ())
            return false;
          
          if (j->str == "[")
            nested++;
          else if (j->str == "]")
            nested = nested ? nested-1 : nested;
          else if (!nested && ignore_module.find (j->str) == ignore_module.end ())
            {
              if (!z->match (*j))
                return false;
              
              get_vars (*z, *j, vars);
              ++z;
            }
        }
      
      get_vars (r, *i, vars);
      //FIXME: add pattern matching ???
      return eval_numeric (r.constraint, vars);
    }
  
  return false;
}

module lsys::expand (const module_map &c, const module &m) const t_err
{
  module_map::const_iterator n;
  
  if ((n = c.find (m.str)) != c.end ())
    return n->second;
  else
    {
      arg_spec spec;
      spec.str   = m.str;
      spec.nargs = m.size ();
      spec.arg   = 0;
      
      module k;
      k.str	= m.str;
      k.num	= m.num;
      k.is_num	= m.is_num;
      k.is_expr	= m.is_expr;
      k.where	= m.where;
      
      for (module_pos i = m.begin (); i != m.end (); ++i, spec.arg++)
        if (arg_is_numeric.find (spec) != arg_is_numeric.end ())
          k.push_back (eval_numeric (*i, c));
        else
          k.push_back (expand (c, *i));
      
      return k;
    }
}

static void replace_modules(module_vec &v, const module_map &m) t_no
{
  module_map::const_iterator c;
  
  for (module::iterator i = v.begin (); i != v.end (); ++i)
    if (i->empty () && (c = m.find (i->str)) != m.end ())
      *i = c->second;
    else
      replace_modules (*i, m);
}

bool operator <(const module &a, const module &b) t_no
{
  if ((module_vec)a < (module_vec)b)
    return true;
  else
    return a.str < b.str;
}

struct lsys_module {
	const lsys *sys;
	module_vec v;
};

static bool operator <(const lsys_module &a, const lsys_module &b)
{
  if (a.v < b.v)
    return true;
  else
    return (long)a.sys < (long)b.sys;
}

bool lsys::eval (module_vec &v) const t_err
{
#if 0
  typedef map<lsys_module, pair<bool, module_vec> > eval_cache;
  static eval_cache cache;
  
  eval_cache::iterator ci;
  
  { //FIXME, why can't I just re-use "ck" later??
    lsys_module ck;
    ck.sys = this;
    ck.v   = v;
    
    if ((ci = cache.find (ck)) != cache.end ())
      {
        if (ci->second.first)
          v = ci->second.second;
        
        return ci->second.first;
      }
  }
#endif
  
  bool changed = false;
  module_vec res;
  module_map vars;
  
  for (module_pos i = v.begin (); i != v.end (); ++i)
    {
      rule_map::const_iterator r = rules.find (i->str);
      
      if (r != rules.end ())
        for (rule_map::mapped_type::const_iterator j = r->second.begin (); j != r->second.end (); ++j)
          {
            vars.erase (vars.begin (), vars.end ());
            
            if (match_rule (*j, v, i, vars))
              {
                double it = eval_numeric (j->iterations, vars);
                
                changed = true;
                
                if (it >= 1.0)
                  {
                    module_vec x;
                    
                    for (module_pos i = j->repl.begin (); i != j->repl.end (); ++i)
                      x.push_back (expand (vars, *i));
                    
                    do {
                      eval (x);
                      it--;
                    } while (it > 0);
                      
                    res.insert (res.end (), x.begin (), x.end ());
                  }
                else
                  for (module_pos i = j->repl.begin (); i != j->repl.end (); ++i)
                    res.push_back (expand (vars, *i));
                
                goto skip;
              }
          }
      
      // no rule matched..
      res.push_back (*i);
      skip:;
    }
  
  replace_modules (res, defines);
#if 0
  if ((!changed && v.size () < 10) || res.size () < 20)
    {
      eval_cache::mapped_type ce(changed, changed ? res : module_vec ());
      lsys_module ck;
      ck.sys = this;
      ck.v   = v; //FIXME not even this works
      cache.insert (ci, eval_cache::value_type (ck, ce));
    }
#endif
  
  v.erase ();
  
  for (module_pos i = res.begin (); i != res.end (); )
    {
      if (i->str == "%")
        {
          int nested = 1;
          
          while (++i != res.end ())
            if (i->str == "[")
              nested++;
            else if (i->str == "]" && !(--nested))
              break;
        }
      else
        v.push_back (*i++);
    }
  
  return changed;
}

bool module::is_func (const string &func) const t_no
{
  return str == func && size () == 0;
}

bool module::is_func (const string &func, double &arg1) const t_no
{
  if (str == func && size () == 1)
    {
      arg1 = eval_expr (first ());
      return true;
    }
  return false;
}

bool module::is_func (const string &func, string &arg1, module &arg2) const t_no
{
  if (str == func && size () == 2 && first().is_expr)
    {
      arg1 = first ().str;
      arg2 = second ();
      return true;
    }
  
  return false;
}

bool module::is_func (const string &func, string &arg1, double &arg2) const t_no
{
  if (str == func && size () == 2 && first().is_expr)
    {
      arg1 = first ().str;
      arg2 = eval_expr (second ());
      return true;
    }
  
  return false;
}

bool module::is_func (const string &func, string &arg1, string &arg2) const t_no
{
  if (str == func && size () == 2 && first().is_expr)
    {
      arg1 = first ().str;
      arg2 = (string) second ();
      return true;
    }
  
  return false;
}