1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/new_map_win.cc Mon Jul 07 08:10:39 2008 -0500
1.3 @@ -0,0 +1,565 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2006
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#include <new_map_win.h>
1.23 +#include <nbtab.h>
1.24 +#include <mapstorage.h>
1.25 +
1.26 +bool NewMapWin::closeIfEscapeIsPressed(GdkEventKey* e)
1.27 +{
1.28 + if(e->keyval==GDK_Escape)
1.29 + {
1.30 + hide();
1.31 + }
1.32 + return true;
1.33 +}
1.34 +
1.35 +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)
1.36 +{
1.37 + set_default_size(200, 50);
1.38 +
1.39 + signal_key_press_event().connect(sigc::mem_fun(*this, &NewMapWin::closeIfEscapeIsPressed));
1.40 +
1.41 + Gtk::VBox * vbox=get_vbox();
1.42 +
1.43 + //entries
1.44 + table=new Gtk::Table(5, 2, false);
1.45 +
1.46 + label=new Gtk::Label;
1.47 + label->set_text("Name of new map:");
1.48 + name.set_text("");
1.49 +
1.50 + (*table).attach(*label,0,1,0,1,Gtk::SHRINK,Gtk::SHRINK,10,3);
1.51 + (*table).attach(name,1,2,0,1,Gtk::SHRINK,Gtk::SHRINK,10,3);
1.52 +
1.53 + lblType.set_label("Element type:");
1.54 + if (map_type & NUM)
1.55 + cbType.append_text("Numeric");
1.56 + if (map_type & STR)
1.57 + cbType.append_text("String");
1.58 + cbType.set_active(0);
1.59 +
1.60 + (*table).attach(lblType,0,1,1,2,Gtk::SHRINK,Gtk::SHRINK,10,3);
1.61 + (*table).attach(cbType, 1,2,1,2,Gtk::SHRINK,Gtk::SHRINK,10,3);
1.62 +
1.63 + label=new Gtk::Label;
1.64 + label->set_text("Default value in the map:");
1.65 + default_value.set_text("0");
1.66 +
1.67 + (*table).attach(*label,0,1,2,3,Gtk::SHRINK,Gtk::SHRINK,10,3);
1.68 + (*table).attach(default_value,1,2,2,3,Gtk::SHRINK,Gtk::SHRINK,10,3);
1.69 +
1.70 + //node vs. arc map selector
1.71 + Gtk::RadioButton::Group group = node.get_group();
1.72 + arc.set_group(group);
1.73 +
1.74 + if(arcnode)
1.75 + {
1.76 + (*table).attach(node,0,1,3,4,Gtk::SHRINK,Gtk::SHRINK,10,3);
1.77 + (*table).attach(arc,1,2,3,4,Gtk::SHRINK,Gtk::SHRINK,10,3);
1.78 + }
1.79 + else
1.80 + {
1.81 + if(itisarc)
1.82 + {
1.83 + arc.set_active();
1.84 + }
1.85 + else
1.86 + {
1.87 + node.set_active();
1.88 + }
1.89 + }
1.90 +
1.91 + (*table).attach(lblErrorMsg,0,2,4,5,Gtk::SHRINK,Gtk::SHRINK,10,3);
1.92 +
1.93 + vbox->pack_start(*table);
1.94 +
1.95 + //OK button
1.96 + add_button(Gtk::Stock::OK, Gtk::RESPONSE_OK);
1.97 +
1.98 + show_all_children();
1.99 +
1.100 +}
1.101 +
1.102 +void NewMapWin::setErrorMsg(const Glib::ustring& msg)
1.103 +{
1.104 + lblErrorMsg.set_markup("<i><small>" + msg + "</small></i>");
1.105 +}
1.106 +
1.107 +std::vector<double>* NewMapWin::evaluate_expr(const std::string polishform, bool itisarc)
1.108 +{
1.109 + MapStorage& ms = *mytab.mapstorage;
1.110 +
1.111 + std::vector<double>* ret = new std::vector<double>;
1.112 + std::stack<double> polishstack;
1.113 +
1.114 + if (itisarc)
1.115 + {
1.116 + for(ArcIt k(ms.digraph); k!=INVALID; ++k)
1.117 + {
1.118 + for(int i=0;i<(int)polishform.size();i++)
1.119 + {
1.120 + double op1=0, op2=0;
1.121 + bool operation=true;
1.122 + switch(polishform[i])
1.123 + {
1.124 + case '+':
1.125 + case '-':
1.126 + case '/':
1.127 + case '*':
1.128 + op1=polishstack.top();
1.129 + polishstack.pop();
1.130 + op2=polishstack.top();
1.131 + polishstack.pop();
1.132 + break;
1.133 + default:
1.134 + //substitute variable
1.135 + std::vector<std::string> maps = ms.getArcMapList(NUM);
1.136 + bool itisvar=(std::find(maps.begin(), maps.end(), ch2var[ polishform[i] ]) != maps.end());
1.137 + if(itisvar)
1.138 + {
1.139 + polishstack.push(ms.get(ch2var[ polishform[i] ], k));
1.140 + }
1.141 + else
1.142 + {
1.143 + polishstack.push(atof(ch2var[ polishform[i] ].c_str()));
1.144 + }
1.145 + operation=false;
1.146 + break;
1.147 + }
1.148 + if(operation)
1.149 + {
1.150 + double res;
1.151 + switch(polishform[i])
1.152 + {
1.153 + case '+':
1.154 + res=op1+op2;
1.155 + break;
1.156 + case '-':
1.157 + res=op2-op1;
1.158 + break;
1.159 + case '/':
1.160 + res=op2/op1;
1.161 + break;
1.162 + case '*':
1.163 + res=op1*op2;
1.164 + break;
1.165 + default:
1.166 + std::cout << "How could we get here?" << std::endl;
1.167 + break;
1.168 + }
1.169 + polishstack.push(res);
1.170 + }
1.171 + }//foreach letter in polishform
1.172 + ret->push_back(polishstack.top());
1.173 + }//foreach arc
1.174 + }
1.175 + else
1.176 + {
1.177 + for(NodeIt k(ms.digraph); k!=INVALID; ++k)
1.178 + {
1.179 + for(int i=0;i<(int)polishform.size();i++)
1.180 + {
1.181 + double op1=0, op2=0;
1.182 + bool operation=true;
1.183 + switch(polishform[i])
1.184 + {
1.185 + case '+':
1.186 + case '-':
1.187 + case '/':
1.188 + case '*':
1.189 + op1=polishstack.top();
1.190 + polishstack.pop();
1.191 + op2=polishstack.top();
1.192 + polishstack.pop();
1.193 + break;
1.194 + default:
1.195 + //substitute variable
1.196 + std::vector<std::string> maps = ms.getNodeMapList(NUM);
1.197 + bool itisvar=(std::find(maps.begin(), maps.end(), ch2var[ polishform[i] ]) != maps.end());
1.198 + if(itisvar)
1.199 + {
1.200 + polishstack.push(ms.get(ch2var[ polishform[i] ], k));
1.201 + }
1.202 + else
1.203 + {
1.204 + polishstack.push(atof(ch2var[ polishform[i] ].c_str()));
1.205 + }
1.206 + operation=false;
1.207 + break;
1.208 + }
1.209 + if(operation)
1.210 + {
1.211 + double res;
1.212 + switch(polishform[i])
1.213 + {
1.214 + case '+':
1.215 + res=op1+op2;
1.216 + break;
1.217 + case '-':
1.218 + res=op2-op1;
1.219 + break;
1.220 + case '/':
1.221 + res=op2/op1;
1.222 + break;
1.223 + case '*':
1.224 + res=op1*op2;
1.225 + break;
1.226 + default:
1.227 + std::cout << "How could we get here?" << std::endl;
1.228 + break;
1.229 + }
1.230 + polishstack.push(res);
1.231 + }
1.232 + }//foreach letter in polishform
1.233 + ret->push_back(polishstack.top());
1.234 + }//foreach arc
1.235 + }
1.236 + return ret;
1.237 +}
1.238 +
1.239 +void NewMapWin::on_response(int response_id)
1.240 +{
1.241 + MapStorage& ms = *mytab.mapstorage;
1.242 +
1.243 + if(response_id==Gtk::RESPONSE_OK)
1.244 + {
1.245 + std::string map_name = name.get_text();
1.246 + std::string def_val = default_value.get_text();
1.247 +
1.248 + if (map_name.empty())
1.249 + {
1.250 + setErrorMsg("No map name given.");
1.251 + return;
1.252 + }
1.253 +
1.254 + // check whether the map already exists
1.255 + if (arc.get_active())
1.256 + {
1.257 + if (ms.arcMapExists(map_name))
1.258 + {
1.259 + setErrorMsg("Map '" + map_name + "' already exists.");
1.260 + return;
1.261 + }
1.262 + }
1.263 + else
1.264 + {
1.265 + if (ms.nodeMapExists(map_name))
1.266 + {
1.267 + setErrorMsg("Map '" + map_name + "' already exists.");
1.268 + return;
1.269 + }
1.270 + }
1.271 +
1.272 + Glib::ustring text = cbType.get_active_text();
1.273 + if (text == "Numeric")
1.274 + {
1.275 + double d;
1.276 + char *endptr;
1.277 + d = strtod(def_val.c_str(), &endptr);
1.278 + if (def_val.c_str() + def_val.length() == endptr)
1.279 + {
1.280 + // the full string was a number
1.281 + if (arc.get_active())
1.282 + ms.createArcMap(map_name, MapValue::NUMERIC,
1.283 + MapValue(d));
1.284 + else
1.285 + ms.createNodeMap(map_name, MapValue::NUMERIC,
1.286 + MapValue(d));
1.287 + }
1.288 + else
1.289 + {
1.290 + // let't try to evaluate the string as an arithmetic expression
1.291 + std::string polishform =
1.292 + string2Polishform(def_val, arc.get_active());
1.293 + if (polishform.empty())
1.294 + return;
1.295 + std::vector<double>* values =
1.296 + evaluate_expr(polishform, arc.get_active());
1.297 + if (arc.get_active())
1.298 + {
1.299 + ms.createArcMap(map_name, MapValue::NUMERIC,
1.300 + MapValue(0.0));
1.301 + std::vector<double>::const_iterator vit = values->begin();
1.302 + for (ArcIt it(ms.digraph); it != INVALID; ++it)
1.303 + {
1.304 + ms.set(map_name, it, MapValue(*vit));
1.305 + ++vit;
1.306 + }
1.307 + }
1.308 + else
1.309 + {
1.310 + ms.createNodeMap(map_name, MapValue::NUMERIC,
1.311 + MapValue(0.0));
1.312 + std::vector<double>::const_iterator vit = values->begin();
1.313 + for (NodeIt it(ms.digraph); it != INVALID; ++it)
1.314 + {
1.315 + ms.set(map_name, it, MapValue(*vit));
1.316 + ++vit;
1.317 + }
1.318 + }
1.319 + delete values;
1.320 + }
1.321 + }
1.322 + else if (text == "String")
1.323 + {
1.324 + if (arc.get_active())
1.325 + ms.createArcMap(map_name, MapValue::STRING,
1.326 + MapValue(def_val));
1.327 + else
1.328 + ms.createNodeMap(map_name, MapValue::STRING,
1.329 + MapValue(def_val));
1.330 + }
1.331 +
1.332 + name.set_text("");
1.333 + default_value.set_text("0");
1.334 + arc.show();
1.335 + node.show();
1.336 + hide();
1.337 + }
1.338 +}
1.339 +
1.340 +
1.341 +std::string NewMapWin::string2Polishform(std::string rawcommand, bool itisarc)
1.342 +{
1.343 + bool valid_entry=true;
1.344 +
1.345 + std::map<std::string, int> str2i;
1.346 +
1.347 + std::string command;
1.348 +
1.349 + std::string variable;
1.350 +
1.351 + char index='a';
1.352 +
1.353 + for(int i=0;(valid_entry&&(i<(int)rawcommand.size()));i++)
1.354 + {
1.355 + switch(rawcommand[i])
1.356 + {
1.357 + case '+':
1.358 + case '-':
1.359 + case '*':
1.360 + case '/':
1.361 + case ')':
1.362 + case '(':
1.363 + if(!variable.empty())
1.364 + {
1.365 + valid_entry=validVariable(variable, itisarc);
1.366 + ch2var[index]=variable;
1.367 + command+=index;
1.368 + index++;
1.369 + variable.erase(0,variable.size());
1.370 + }
1.371 + command+=rawcommand[i];
1.372 + break;
1.373 + default:
1.374 + variable+=rawcommand[i];
1.375 + break;
1.376 + }
1.377 + }
1.378 +
1.379 + if(!variable.empty()&&valid_entry)
1.380 + {
1.381 + valid_entry=validVariable(variable, itisarc);
1.382 + ch2var[index]=variable;
1.383 + command+=index;
1.384 + index++;
1.385 + variable.erase(0,variable.size());
1.386 + }
1.387 +
1.388 + if(valid_entry)
1.389 + {
1.390 + unsigned int pr=10000;
1.391 + bool prevmult=false;
1.392 + unsigned int prev_change=pr;
1.393 + unsigned int prev_br=pr;
1.394 + int counter=0;
1.395 + std::string comm_nobr="";
1.396 + std::vector<unsigned int> p;
1.397 + p.resize(counter+1);
1.398 +
1.399 + //limits
1.400 + //6 brackets embedded
1.401 + //100 operation in a row from the same priority
1.402 +
1.403 + for(int i=0;i<(int)command.size();i++)
1.404 + {
1.405 + bool put_in_string=true;
1.406 + switch(command[i])
1.407 + {
1.408 + case '(':
1.409 + pr=prev_br+10000;
1.410 + prev_br=pr;
1.411 + prevmult=false;
1.412 + put_in_string=false;
1.413 + break;
1.414 + case ')':
1.415 + pr=prev_br-10000;
1.416 + prev_br=pr;
1.417 + prevmult=false;
1.418 + put_in_string=false;
1.419 + break;
1.420 + case '+':
1.421 + case '-':
1.422 + if(prevmult)
1.423 + {
1.424 + pr=prev_change;
1.425 + }
1.426 + p[counter]=pr;
1.427 + pr-=100;
1.428 +
1.429 + prevmult=false;
1.430 + break;
1.431 + case '/':
1.432 + case '*':
1.433 + if(!prevmult)
1.434 + {
1.435 + prev_change=pr;
1.436 + pr+=200;
1.437 + pr-=1;
1.438 + }
1.439 + p[counter]=pr;
1.440 + pr-=1;
1.441 + prevmult=true;
1.442 + break;
1.443 + default:
1.444 + p[counter]=65000;
1.445 + break;
1.446 + }
1.447 + if(put_in_string)
1.448 + {
1.449 + counter++;
1.450 + p.resize(counter+1);
1.451 + comm_nobr=comm_nobr+command[i];
1.452 + }
1.453 + }
1.454 +
1.455 + tree_node * root=weightedString2Tree(comm_nobr, p, 0);
1.456 +
1.457 + std::string polishform=postOrder(root);
1.458 +
1.459 + deleteTree(root);
1.460 +
1.461 + return polishform;
1.462 + }
1.463 + return "";
1.464 +}
1.465 +
1.466 +void NewMapWin::deleteTree(NewMapWin::tree_node * node)
1.467 +{
1.468 + if(node->left_child!=NULL)
1.469 + {
1.470 + deleteTree(node->left_child);
1.471 + }
1.472 + if(node->right_child!=NULL)
1.473 + {
1.474 + deleteTree(node->right_child);
1.475 + }
1.476 + delete node;
1.477 +}
1.478 +
1.479 +NewMapWin::tree_node * NewMapWin::weightedString2Tree(std::string to_tree, std::vector<unsigned int> & p, int offset)
1.480 +{
1.481 + unsigned int min=p[offset];
1.482 + int minplace=0;
1.483 + for(int i=0;i<(int)to_tree.size();i++)
1.484 + {
1.485 + if(min>p[offset+i])
1.486 + {
1.487 + min=p[offset+i];
1.488 + minplace=i;
1.489 + }
1.490 + }
1.491 + tree_node * act_node=new tree_node;
1.492 + act_node->ch=to_tree[minplace];
1.493 + if(to_tree.size()>=3)
1.494 + {
1.495 + act_node->left_child=weightedString2Tree(to_tree.substr(0,minplace), p, offset);
1.496 + act_node->right_child=weightedString2Tree(to_tree.substr(minplace+1,to_tree.size()-minplace-1), p, offset+minplace+1);
1.497 + }
1.498 + else
1.499 + {
1.500 + act_node->left_child=NULL;
1.501 + act_node->right_child=NULL;
1.502 + }
1.503 + return act_node;
1.504 +}
1.505 +
1.506 +std::string NewMapWin::postOrder(tree_node * subtree)
1.507 +{
1.508 + std::string subtree_to_string;
1.509 + if(subtree->left_child)
1.510 + {
1.511 + subtree_to_string=postOrder(subtree->left_child);
1.512 + }
1.513 + if(subtree->right_child)
1.514 + {
1.515 + subtree_to_string=subtree_to_string+postOrder(subtree->right_child);
1.516 + }
1.517 + subtree_to_string=subtree_to_string+subtree->ch;
1.518 + return subtree_to_string;
1.519 +}
1.520 +
1.521 +bool NewMapWin::validVariable(std::string variable, bool itisarc)
1.522 +{
1.523 + MapStorage& ms = *mytab.mapstorage;
1.524 +
1.525 + bool cancel;
1.526 + //is it mapname?
1.527 + if(itisarc)
1.528 + {
1.529 + std::vector<std::string> arc_maps =
1.530 + ms.getArcMapList(NUM);
1.531 + cancel=(std::find(arc_maps.begin(), arc_maps.end(), variable)==arc_maps.end());
1.532 + }
1.533 + else
1.534 + {
1.535 + std::vector<std::string> node_maps =
1.536 + ms.getNodeMapList(NUM);
1.537 + cancel=(std::find(node_maps.begin(), node_maps.end(), variable)==node_maps.end());
1.538 + }
1.539 + //maybe it is number
1.540 + int point_num=0;
1.541 + if(cancel)
1.542 + {
1.543 + cancel=false;
1.544 + for(int j=0;(!cancel)&&(j<(int)variable.size());j++)
1.545 + {
1.546 + if(((variable[j]<'0')||(variable[j]>'9'))&&(variable[j]!='.'))
1.547 + {
1.548 + cancel=true;
1.549 + }
1.550 + else
1.551 + {
1.552 + if(variable[j]=='.')
1.553 + {
1.554 + point_num++;
1.555 + if(point_num>1)
1.556 + {
1.557 + cancel=true;
1.558 + }
1.559 + }
1.560 + }
1.561 + }
1.562 + }
1.563 + if(cancel)
1.564 + {
1.565 + return false;
1.566 + }
1.567 + return true;
1.568 +}