hegyi@1: /* -*- C++ -*-
hegyi@1:  *
hegyi@1:  * This file is a part of LEMON, a generic C++ optimization library
hegyi@1:  *
hegyi@1:  * Copyright (C) 2003-2006
hegyi@1:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
hegyi@1:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
hegyi@1:  *
hegyi@1:  * Permission to use, modify and distribute this software is granted
hegyi@1:  * provided that this copyright notice appears in all copies. For
hegyi@1:  * precise terms see the accompanying LICENSE file.
hegyi@1:  *
hegyi@1:  * This software is provided "AS IS" with no warranty of any kind,
hegyi@1:  * express or implied, and with no claim as to its suitability for any
hegyi@1:  * purpose.
hegyi@1:  *
hegyi@1:  */
hegyi@1: 
hegyi@1: #include <new_map_win.h>
hegyi@1: #include <nbtab.h>
hegyi@1: #include <mapstorage.h>
hegyi@1: 
hegyi@1: bool NewMapWin::closeIfEscapeIsPressed(GdkEventKey* e)
hegyi@1: {
hegyi@1:   if(e->keyval==GDK_Escape)
hegyi@1:   {
hegyi@1:     hide();
hegyi@1:   }
hegyi@1:   return true;
hegyi@1: }
hegyi@1: 
hegyi@1: NewMapWin::NewMapWin(const std::string& title, NoteBookTab & mw, bool itisarc, bool arcnode, MapType type):Gtk::Dialog(title, true, true),mytab(mw),node("Create NodeMap"),arc("Create ArcMap"),map_type(type)
hegyi@1: {
hegyi@1:   set_default_size(200, 50);
hegyi@1: 
hegyi@1:   signal_key_press_event().connect(sigc::mem_fun(*this, &NewMapWin::closeIfEscapeIsPressed));
hegyi@1: 
hegyi@1:   Gtk::VBox * vbox=get_vbox();
hegyi@1: 
hegyi@1:   //entries
hegyi@1:   table=new Gtk::Table(5, 2, false);
hegyi@1: 
hegyi@1:   label=new Gtk::Label;
hegyi@1:   label->set_text("Name of new map:");
hegyi@1:   name.set_text("");
hegyi@1: 
hegyi@1:   (*table).attach(*label,0,1,0,1,Gtk::SHRINK,Gtk::SHRINK,10,3);
hegyi@1:   (*table).attach(name,1,2,0,1,Gtk::SHRINK,Gtk::SHRINK,10,3);
hegyi@1: 
hegyi@1:   lblType.set_label("Element type:");
hegyi@1:   if (map_type & NUM)
hegyi@1:     cbType.append_text("Numeric");
hegyi@1:   if (map_type & STR)
hegyi@1:     cbType.append_text("String");
hegyi@1:   cbType.set_active(0);
hegyi@1: 
hegyi@1:   (*table).attach(lblType,0,1,1,2,Gtk::SHRINK,Gtk::SHRINK,10,3);
hegyi@1:   (*table).attach(cbType, 1,2,1,2,Gtk::SHRINK,Gtk::SHRINK,10,3);
hegyi@1: 
hegyi@1:   label=new Gtk::Label;
hegyi@1:   label->set_text("Default value in the map:");
hegyi@1:   default_value.set_text("0");
hegyi@1: 
hegyi@1:   (*table).attach(*label,0,1,2,3,Gtk::SHRINK,Gtk::SHRINK,10,3);
hegyi@1:   (*table).attach(default_value,1,2,2,3,Gtk::SHRINK,Gtk::SHRINK,10,3);
hegyi@1: 
hegyi@1:   //node vs. arc map selector
hegyi@1:   Gtk::RadioButton::Group group = node.get_group();
hegyi@1:   arc.set_group(group);
hegyi@1: 
hegyi@1:   if(arcnode)
hegyi@1:   {
hegyi@1:     (*table).attach(node,0,1,3,4,Gtk::SHRINK,Gtk::SHRINK,10,3);
hegyi@1:     (*table).attach(arc,1,2,3,4,Gtk::SHRINK,Gtk::SHRINK,10,3);
hegyi@1:   }
hegyi@1:   else
hegyi@1:   {
hegyi@1:     if(itisarc)
hegyi@1:     {
hegyi@1:       arc.set_active();
hegyi@1:     }
hegyi@1:     else
hegyi@1:     {
hegyi@1:       node.set_active();
hegyi@1:     }
hegyi@1:   }
hegyi@1: 
hegyi@1:   (*table).attach(lblErrorMsg,0,2,4,5,Gtk::SHRINK,Gtk::SHRINK,10,3);
hegyi@1: 
hegyi@1:   vbox->pack_start(*table);
hegyi@1: 
hegyi@1:   //OK button
hegyi@1:   add_button(Gtk::Stock::OK, Gtk::RESPONSE_OK);
hegyi@1: 
hegyi@1:   show_all_children();
hegyi@1: 
hegyi@1: }
hegyi@1: 
hegyi@1: void NewMapWin::setErrorMsg(const Glib::ustring& msg)
hegyi@1: {
hegyi@1:   lblErrorMsg.set_markup("<i><small>" + msg + "</small></i>");
hegyi@1: }
hegyi@1: 
hegyi@1: std::vector<double>* NewMapWin::evaluate_expr(const std::string polishform, bool itisarc)
hegyi@1: {
hegyi@1:   MapStorage& ms = *mytab.mapstorage;
hegyi@1: 
hegyi@1:   std::vector<double>* ret = new std::vector<double>;
hegyi@1:   std::stack<double> polishstack;
hegyi@1: 
hegyi@1:   if (itisarc)
hegyi@1:   {
hegyi@1:     for(ArcIt k(ms.digraph); k!=INVALID; ++k)
hegyi@1:     {
hegyi@1:       for(int i=0;i<(int)polishform.size();i++)
hegyi@1:       {
hegyi@1:         double op1=0, op2=0;
hegyi@1:         bool operation=true;
hegyi@1:         switch(polishform[i])
hegyi@1:         {
hegyi@1:           case '+':
hegyi@1:           case '-':
hegyi@1:           case '/':
hegyi@1:           case '*':
hegyi@1:             op1=polishstack.top();
hegyi@1:             polishstack.pop();
hegyi@1:             op2=polishstack.top();
hegyi@1:             polishstack.pop();
hegyi@1:             break;
hegyi@1:           default:
hegyi@1:             //substitute variable
hegyi@1:             std::vector<std::string> maps = ms.getArcMapList(NUM);
hegyi@1:             bool itisvar=(std::find(maps.begin(), maps.end(), ch2var[ polishform[i] ]) != maps.end());
hegyi@1:             if(itisvar)
hegyi@1:             {
hegyi@1:               polishstack.push(ms.get(ch2var[ polishform[i] ], k));
hegyi@1:             }
hegyi@1:             else
hegyi@1:             {
hegyi@1:               polishstack.push(atof(ch2var[ polishform[i] ].c_str()));
hegyi@1:             }
hegyi@1:             operation=false;
hegyi@1:             break;
hegyi@1:         }
hegyi@1:         if(operation)
hegyi@1:         {
hegyi@1:           double res;
hegyi@1:           switch(polishform[i])
hegyi@1:           {
hegyi@1:             case '+':
hegyi@1:               res=op1+op2;
hegyi@1:               break;
hegyi@1:             case '-':
hegyi@1:               res=op2-op1;
hegyi@1:               break;
hegyi@1:             case '/':
hegyi@1:               res=op2/op1;
hegyi@1:               break;
hegyi@1:             case '*':
hegyi@1:               res=op1*op2;
hegyi@1:               break;
hegyi@1:             default:
hegyi@1:               std::cout << "How could we get here?" << std::endl;
hegyi@1:               break;
hegyi@1:           }
hegyi@1:           polishstack.push(res);
hegyi@1:         }
hegyi@1:       }//foreach letter in polishform
hegyi@1:       ret->push_back(polishstack.top());
hegyi@1:     }//foreach arc
hegyi@1:   }
hegyi@1:   else
hegyi@1:   {
hegyi@1:     for(NodeIt k(ms.digraph); k!=INVALID; ++k)
hegyi@1:     {
hegyi@1:       for(int i=0;i<(int)polishform.size();i++)
hegyi@1:       {
hegyi@1:         double op1=0, op2=0;
hegyi@1:         bool operation=true;
hegyi@1:         switch(polishform[i])
hegyi@1:         {
hegyi@1:           case '+':
hegyi@1:           case '-':
hegyi@1:           case '/':
hegyi@1:           case '*':
hegyi@1:             op1=polishstack.top();
hegyi@1:             polishstack.pop();
hegyi@1:             op2=polishstack.top();
hegyi@1:             polishstack.pop();
hegyi@1:             break;
hegyi@1:           default:
hegyi@1:             //substitute variable
hegyi@1:             std::vector<std::string> maps = ms.getNodeMapList(NUM);
hegyi@1:             bool itisvar=(std::find(maps.begin(), maps.end(), ch2var[ polishform[i] ]) != maps.end());
hegyi@1:             if(itisvar)
hegyi@1:             {
hegyi@1:               polishstack.push(ms.get(ch2var[ polishform[i] ], k));
hegyi@1:             }
hegyi@1:             else
hegyi@1:             {
hegyi@1:               polishstack.push(atof(ch2var[ polishform[i] ].c_str()));
hegyi@1:             }
hegyi@1:             operation=false;
hegyi@1:             break;
hegyi@1:         }
hegyi@1:         if(operation)
hegyi@1:         {
hegyi@1:           double res;
hegyi@1:           switch(polishform[i])
hegyi@1:           {
hegyi@1:             case '+':
hegyi@1:               res=op1+op2;
hegyi@1:               break;
hegyi@1:             case '-':
hegyi@1:               res=op2-op1;
hegyi@1:               break;
hegyi@1:             case '/':
hegyi@1:               res=op2/op1;
hegyi@1:               break;
hegyi@1:             case '*':
hegyi@1:               res=op1*op2;
hegyi@1:               break;
hegyi@1:             default:
hegyi@1:               std::cout << "How could we get here?" << std::endl;
hegyi@1:               break;
hegyi@1:           }
hegyi@1:           polishstack.push(res);
hegyi@1:         }
hegyi@1:       }//foreach letter in polishform
hegyi@1:       ret->push_back(polishstack.top());
hegyi@1:     }//foreach arc
hegyi@1:   }
hegyi@1:   return ret;
hegyi@1: }
hegyi@1: 
hegyi@1: void NewMapWin::on_response(int response_id)
hegyi@1: {
hegyi@1:   MapStorage& ms = *mytab.mapstorage;
hegyi@1: 
hegyi@1:   if(response_id==Gtk::RESPONSE_OK)
hegyi@1:   {
hegyi@1:     std::string map_name = name.get_text();
hegyi@1:     std::string def_val = default_value.get_text();
hegyi@1: 
hegyi@1:     if (map_name.empty())
hegyi@1:     {
hegyi@1:       setErrorMsg("No map name given.");
hegyi@1:       return;
hegyi@1:     }
hegyi@1: 
hegyi@1:     // check whether the map already exists
hegyi@1:     if (arc.get_active())
hegyi@1:     {
hegyi@1:       if (ms.arcMapExists(map_name))
hegyi@1:       {
hegyi@1:         setErrorMsg("Map '" + map_name + "' already exists.");
hegyi@1:         return;
hegyi@1:       }
hegyi@1:     }
hegyi@1:     else
hegyi@1:     {
hegyi@1:       if (ms.nodeMapExists(map_name))
hegyi@1:       {
hegyi@1:         setErrorMsg("Map '" + map_name + "' already exists.");
hegyi@1:         return;
hegyi@1:       }
hegyi@1:     }
hegyi@1: 
hegyi@1:     Glib::ustring text = cbType.get_active_text();
hegyi@1:     if (text == "Numeric")
hegyi@1:     {
hegyi@1:       double d;
hegyi@1:       char *endptr;
hegyi@1:       d = strtod(def_val.c_str(), &endptr);
hegyi@1:       if (def_val.c_str() + def_val.length() == endptr)
hegyi@1:       {
hegyi@1:         // the full string was a number
hegyi@1:         if (arc.get_active())
hegyi@1:           ms.createArcMap(map_name, MapValue::NUMERIC,
hegyi@1:               MapValue(d));
hegyi@1:         else
hegyi@1:           ms.createNodeMap(map_name, MapValue::NUMERIC,
hegyi@1:               MapValue(d));
hegyi@1:       }
hegyi@1:       else
hegyi@1:       {
hegyi@1:         // let't try to evaluate the string as an arithmetic expression
hegyi@1:         std::string polishform =
hegyi@1:           string2Polishform(def_val, arc.get_active());
hegyi@1:         if (polishform.empty())
hegyi@1:           return;
hegyi@1:         std::vector<double>* values =
hegyi@1:           evaluate_expr(polishform, arc.get_active());
hegyi@1:         if (arc.get_active())
hegyi@1:         {
hegyi@1:           ms.createArcMap(map_name, MapValue::NUMERIC,
hegyi@1:               MapValue(0.0));
hegyi@1:           std::vector<double>::const_iterator vit = values->begin();
hegyi@1:           for (ArcIt it(ms.digraph); it != INVALID; ++it)
hegyi@1:           {
hegyi@1:             ms.set(map_name, it, MapValue(*vit));
hegyi@1:             ++vit;
hegyi@1:           }
hegyi@1:         }
hegyi@1:         else
hegyi@1:         {
hegyi@1:           ms.createNodeMap(map_name, MapValue::NUMERIC,
hegyi@1:               MapValue(0.0));
hegyi@1:           std::vector<double>::const_iterator vit = values->begin();
hegyi@1:           for (NodeIt it(ms.digraph); it != INVALID; ++it)
hegyi@1:           {
hegyi@1:             ms.set(map_name, it, MapValue(*vit));
hegyi@1:             ++vit;
hegyi@1:           }
hegyi@1:         }
hegyi@1:         delete values;
hegyi@1:       }
hegyi@1:     }
hegyi@1:     else if (text == "String")
hegyi@1:     {
hegyi@1:       if (arc.get_active())
hegyi@1:         ms.createArcMap(map_name, MapValue::STRING,
hegyi@1:             MapValue(def_val));
hegyi@1:       else
hegyi@1:         ms.createNodeMap(map_name, MapValue::STRING,
hegyi@1:             MapValue(def_val));
hegyi@1:     }
hegyi@1: 
hegyi@1:     name.set_text("");
hegyi@1:     default_value.set_text("0");
hegyi@1:     arc.show();
hegyi@1:     node.show();
hegyi@1:     hide();
hegyi@1:   }
hegyi@1: }
hegyi@1: 
hegyi@1: 
hegyi@1: std::string NewMapWin::string2Polishform(std::string rawcommand, bool itisarc)
hegyi@1: {
hegyi@1:   bool valid_entry=true;
hegyi@1: 
hegyi@1:   std::map<std::string, int> str2i;
hegyi@1: 
hegyi@1:   std::string command;
hegyi@1: 
hegyi@1:   std::string variable;
hegyi@1: 
hegyi@1:   char index='a';
hegyi@1: 
hegyi@1:   for(int i=0;(valid_entry&&(i<(int)rawcommand.size()));i++)
hegyi@1:   {
hegyi@1:     switch(rawcommand[i])
hegyi@1:     {
hegyi@1:       case '+':
hegyi@1:       case '-':
hegyi@1:       case '*':
hegyi@1:       case '/':
hegyi@1:       case ')':
hegyi@1:       case '(':
hegyi@1:         if(!variable.empty())
hegyi@1:         {
hegyi@1:           valid_entry=validVariable(variable, itisarc);
hegyi@1:           ch2var[index]=variable;
hegyi@1:           command+=index;
hegyi@1:           index++;
hegyi@1:           variable.erase(0,variable.size());	  
hegyi@1:         }
hegyi@1:         command+=rawcommand[i];
hegyi@1:         break;
hegyi@1:       default:
hegyi@1:         variable+=rawcommand[i];
hegyi@1:         break;
hegyi@1:     }
hegyi@1:   }
hegyi@1: 
hegyi@1:   if(!variable.empty()&&valid_entry)
hegyi@1:   {
hegyi@1:     valid_entry=validVariable(variable, itisarc);
hegyi@1:     ch2var[index]=variable;
hegyi@1:     command+=index;
hegyi@1:     index++;
hegyi@1:     variable.erase(0,variable.size());	  
hegyi@1:   }
hegyi@1: 
hegyi@1:   if(valid_entry)
hegyi@1:   {
hegyi@1:     unsigned int pr=10000;
hegyi@1:     bool prevmult=false;
hegyi@1:     unsigned int prev_change=pr;
hegyi@1:     unsigned int prev_br=pr;
hegyi@1:     int counter=0;
hegyi@1:     std::string comm_nobr="";
hegyi@1:     std::vector<unsigned int> p;
hegyi@1:     p.resize(counter+1);
hegyi@1: 
hegyi@1:     //limits
hegyi@1:     //6 brackets embedded
hegyi@1:     //100 operation in a row from the same priority
hegyi@1: 
hegyi@1:     for(int i=0;i<(int)command.size();i++)
hegyi@1:     {
hegyi@1:       bool put_in_string=true;
hegyi@1:       switch(command[i])
hegyi@1:       {
hegyi@1:         case '(':
hegyi@1:           pr=prev_br+10000;
hegyi@1:           prev_br=pr;
hegyi@1:           prevmult=false;
hegyi@1:           put_in_string=false;
hegyi@1:           break;
hegyi@1:         case ')':
hegyi@1:           pr=prev_br-10000;
hegyi@1:           prev_br=pr;
hegyi@1:           prevmult=false;
hegyi@1:           put_in_string=false;
hegyi@1:           break;
hegyi@1:         case '+':
hegyi@1:         case '-':
hegyi@1:           if(prevmult)
hegyi@1:           {
hegyi@1:             pr=prev_change;
hegyi@1:           }
hegyi@1:           p[counter]=pr;
hegyi@1:           pr-=100;
hegyi@1: 
hegyi@1:           prevmult=false;
hegyi@1:           break;
hegyi@1:         case '/':
hegyi@1:         case '*':
hegyi@1:           if(!prevmult)
hegyi@1:           {
hegyi@1:             prev_change=pr;
hegyi@1:             pr+=200;
hegyi@1:             pr-=1;
hegyi@1:           }
hegyi@1:           p[counter]=pr;
hegyi@1:           pr-=1;
hegyi@1:           prevmult=true;
hegyi@1:           break;
hegyi@1:         default:
hegyi@1:           p[counter]=65000;
hegyi@1:           break;
hegyi@1:       }
hegyi@1:       if(put_in_string)
hegyi@1:       {
hegyi@1:         counter++;
hegyi@1:         p.resize(counter+1);
hegyi@1:         comm_nobr=comm_nobr+command[i];
hegyi@1:       }
hegyi@1:     }
hegyi@1: 
hegyi@1:     tree_node * root=weightedString2Tree(comm_nobr, p, 0);
hegyi@1: 
hegyi@1:     std::string polishform=postOrder(root);
hegyi@1: 
hegyi@1:     deleteTree(root);
hegyi@1: 
hegyi@1:     return polishform;
hegyi@1:   }
hegyi@1:   return "";
hegyi@1: }
hegyi@1: 
hegyi@1: void NewMapWin::deleteTree(NewMapWin::tree_node * node)
hegyi@1: {
hegyi@1:   if(node->left_child!=NULL)
hegyi@1:   {
hegyi@1:     deleteTree(node->left_child);
hegyi@1:   }
hegyi@1:   if(node->right_child!=NULL)
hegyi@1:   {
hegyi@1:     deleteTree(node->right_child);
hegyi@1:   }
hegyi@1:   delete node;
hegyi@1: }
hegyi@1: 
hegyi@1: NewMapWin::tree_node * NewMapWin::weightedString2Tree(std::string to_tree, std::vector<unsigned int> & p, int offset)
hegyi@1: {
hegyi@1:   unsigned int min=p[offset];
hegyi@1:   int minplace=0;
hegyi@1:   for(int i=0;i<(int)to_tree.size();i++)
hegyi@1:   {
hegyi@1:     if(min>p[offset+i])
hegyi@1:     {
hegyi@1:       min=p[offset+i];
hegyi@1:       minplace=i;
hegyi@1:     }
hegyi@1:   }
hegyi@1:   tree_node * act_node=new tree_node;
hegyi@1:   act_node->ch=to_tree[minplace];
hegyi@1:   if(to_tree.size()>=3)
hegyi@1:   {
hegyi@1:     act_node->left_child=weightedString2Tree(to_tree.substr(0,minplace), p, offset);
hegyi@1:     act_node->right_child=weightedString2Tree(to_tree.substr(minplace+1,to_tree.size()-minplace-1), p, offset+minplace+1);
hegyi@1:   }
hegyi@1:   else
hegyi@1:   {
hegyi@1:     act_node->left_child=NULL;
hegyi@1:     act_node->right_child=NULL;
hegyi@1:   }
hegyi@1:   return act_node;
hegyi@1: }
hegyi@1: 
hegyi@1: std::string NewMapWin::postOrder(tree_node * subtree)
hegyi@1: {
hegyi@1:   std::string subtree_to_string;
hegyi@1:   if(subtree->left_child)
hegyi@1:   {
hegyi@1:     subtree_to_string=postOrder(subtree->left_child);
hegyi@1:   }
hegyi@1:   if(subtree->right_child)
hegyi@1:   {
hegyi@1:     subtree_to_string=subtree_to_string+postOrder(subtree->right_child);
hegyi@1:   }
hegyi@1:   subtree_to_string=subtree_to_string+subtree->ch;
hegyi@1:   return subtree_to_string;
hegyi@1: }
hegyi@1: 
hegyi@1: bool NewMapWin::validVariable(std::string variable, bool itisarc)
hegyi@1: {
hegyi@1:   MapStorage& ms = *mytab.mapstorage;
hegyi@1: 
hegyi@1:   bool cancel;
hegyi@1:   //is it mapname?
hegyi@1:   if(itisarc)
hegyi@1:   {
hegyi@1:     std::vector<std::string> arc_maps =
hegyi@1:       ms.getArcMapList(NUM);
hegyi@1:     cancel=(std::find(arc_maps.begin(), arc_maps.end(), variable)==arc_maps.end());
hegyi@1:   }
hegyi@1:   else
hegyi@1:   {
hegyi@1:     std::vector<std::string> node_maps =
hegyi@1:       ms.getNodeMapList(NUM);
hegyi@1:     cancel=(std::find(node_maps.begin(), node_maps.end(), variable)==node_maps.end());
hegyi@1:   }
hegyi@1:   //maybe it is number
hegyi@1:   int point_num=0;
hegyi@1:   if(cancel)
hegyi@1:   {
hegyi@1:     cancel=false;
hegyi@1:     for(int j=0;(!cancel)&&(j<(int)variable.size());j++)
hegyi@1:     {
hegyi@1:       if(((variable[j]<'0')||(variable[j]>'9'))&&(variable[j]!='.'))
hegyi@1:       {
hegyi@1:         cancel=true;
hegyi@1:       }
hegyi@1:       else
hegyi@1:       {
hegyi@1:         if(variable[j]=='.')
hegyi@1:         {
hegyi@1:           point_num++;
hegyi@1:           if(point_num>1)
hegyi@1:           {
hegyi@1:             cancel=true;
hegyi@1:           }
hegyi@1:         }
hegyi@1:       }
hegyi@1:     }
hegyi@1:   }
hegyi@1:   if(cancel)
hegyi@1:   {
hegyi@1:     return false;
hegyi@1:   }
hegyi@1:   return true;
hegyi@1: }