COIN-OR::LEMON - Graph Library

source: glemon/new_map_win.cc @ 1:67188bd752db

Last change on this file since 1:67188bd752db was 1:67188bd752db, checked in by Peter Hegyi <hegyi@…>, 16 years ago

SVN revision 3500 made compilable with Lemon 1.0.

File size: 13.1 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#include <new_map_win.h>
20#include <nbtab.h>
21#include <mapstorage.h>
22
23bool NewMapWin::closeIfEscapeIsPressed(GdkEventKey* e)
24{
25  if(e->keyval==GDK_Escape)
26  {
27    hide();
28  }
29  return true;
30}
31
32NewMapWin::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)
33{
34  set_default_size(200, 50);
35
36  signal_key_press_event().connect(sigc::mem_fun(*this, &NewMapWin::closeIfEscapeIsPressed));
37
38  Gtk::VBox * vbox=get_vbox();
39
40  //entries
41  table=new Gtk::Table(5, 2, false);
42
43  label=new Gtk::Label;
44  label->set_text("Name of new map:");
45  name.set_text("");
46
47  (*table).attach(*label,0,1,0,1,Gtk::SHRINK,Gtk::SHRINK,10,3);
48  (*table).attach(name,1,2,0,1,Gtk::SHRINK,Gtk::SHRINK,10,3);
49
50  lblType.set_label("Element type:");
51  if (map_type & NUM)
52    cbType.append_text("Numeric");
53  if (map_type & STR)
54    cbType.append_text("String");
55  cbType.set_active(0);
56
57  (*table).attach(lblType,0,1,1,2,Gtk::SHRINK,Gtk::SHRINK,10,3);
58  (*table).attach(cbType, 1,2,1,2,Gtk::SHRINK,Gtk::SHRINK,10,3);
59
60  label=new Gtk::Label;
61  label->set_text("Default value in the map:");
62  default_value.set_text("0");
63
64  (*table).attach(*label,0,1,2,3,Gtk::SHRINK,Gtk::SHRINK,10,3);
65  (*table).attach(default_value,1,2,2,3,Gtk::SHRINK,Gtk::SHRINK,10,3);
66
67  //node vs. arc map selector
68  Gtk::RadioButton::Group group = node.get_group();
69  arc.set_group(group);
70
71  if(arcnode)
72  {
73    (*table).attach(node,0,1,3,4,Gtk::SHRINK,Gtk::SHRINK,10,3);
74    (*table).attach(arc,1,2,3,4,Gtk::SHRINK,Gtk::SHRINK,10,3);
75  }
76  else
77  {
78    if(itisarc)
79    {
80      arc.set_active();
81    }
82    else
83    {
84      node.set_active();
85    }
86  }
87
88  (*table).attach(lblErrorMsg,0,2,4,5,Gtk::SHRINK,Gtk::SHRINK,10,3);
89
90  vbox->pack_start(*table);
91
92  //OK button
93  add_button(Gtk::Stock::OK, Gtk::RESPONSE_OK);
94
95  show_all_children();
96
97}
98
99void NewMapWin::setErrorMsg(const Glib::ustring& msg)
100{
101  lblErrorMsg.set_markup("<i><small>" + msg + "</small></i>");
102}
103
104std::vector<double>* NewMapWin::evaluate_expr(const std::string polishform, bool itisarc)
105{
106  MapStorage& ms = *mytab.mapstorage;
107
108  std::vector<double>* ret = new std::vector<double>;
109  std::stack<double> polishstack;
110
111  if (itisarc)
112  {
113    for(ArcIt k(ms.digraph); k!=INVALID; ++k)
114    {
115      for(int i=0;i<(int)polishform.size();i++)
116      {
117        double op1=0, op2=0;
118        bool operation=true;
119        switch(polishform[i])
120        {
121          case '+':
122          case '-':
123          case '/':
124          case '*':
125            op1=polishstack.top();
126            polishstack.pop();
127            op2=polishstack.top();
128            polishstack.pop();
129            break;
130          default:
131            //substitute variable
132            std::vector<std::string> maps = ms.getArcMapList(NUM);
133            bool itisvar=(std::find(maps.begin(), maps.end(), ch2var[ polishform[i] ]) != maps.end());
134            if(itisvar)
135            {
136              polishstack.push(ms.get(ch2var[ polishform[i] ], k));
137            }
138            else
139            {
140              polishstack.push(atof(ch2var[ polishform[i] ].c_str()));
141            }
142            operation=false;
143            break;
144        }
145        if(operation)
146        {
147          double res;
148          switch(polishform[i])
149          {
150            case '+':
151              res=op1+op2;
152              break;
153            case '-':
154              res=op2-op1;
155              break;
156            case '/':
157              res=op2/op1;
158              break;
159            case '*':
160              res=op1*op2;
161              break;
162            default:
163              std::cout << "How could we get here?" << std::endl;
164              break;
165          }
166          polishstack.push(res);
167        }
168      }//foreach letter in polishform
169      ret->push_back(polishstack.top());
170    }//foreach arc
171  }
172  else
173  {
174    for(NodeIt k(ms.digraph); k!=INVALID; ++k)
175    {
176      for(int i=0;i<(int)polishform.size();i++)
177      {
178        double op1=0, op2=0;
179        bool operation=true;
180        switch(polishform[i])
181        {
182          case '+':
183          case '-':
184          case '/':
185          case '*':
186            op1=polishstack.top();
187            polishstack.pop();
188            op2=polishstack.top();
189            polishstack.pop();
190            break;
191          default:
192            //substitute variable
193            std::vector<std::string> maps = ms.getNodeMapList(NUM);
194            bool itisvar=(std::find(maps.begin(), maps.end(), ch2var[ polishform[i] ]) != maps.end());
195            if(itisvar)
196            {
197              polishstack.push(ms.get(ch2var[ polishform[i] ], k));
198            }
199            else
200            {
201              polishstack.push(atof(ch2var[ polishform[i] ].c_str()));
202            }
203            operation=false;
204            break;
205        }
206        if(operation)
207        {
208          double res;
209          switch(polishform[i])
210          {
211            case '+':
212              res=op1+op2;
213              break;
214            case '-':
215              res=op2-op1;
216              break;
217            case '/':
218              res=op2/op1;
219              break;
220            case '*':
221              res=op1*op2;
222              break;
223            default:
224              std::cout << "How could we get here?" << std::endl;
225              break;
226          }
227          polishstack.push(res);
228        }
229      }//foreach letter in polishform
230      ret->push_back(polishstack.top());
231    }//foreach arc
232  }
233  return ret;
234}
235
236void NewMapWin::on_response(int response_id)
237{
238  MapStorage& ms = *mytab.mapstorage;
239
240  if(response_id==Gtk::RESPONSE_OK)
241  {
242    std::string map_name = name.get_text();
243    std::string def_val = default_value.get_text();
244
245    if (map_name.empty())
246    {
247      setErrorMsg("No map name given.");
248      return;
249    }
250
251    // check whether the map already exists
252    if (arc.get_active())
253    {
254      if (ms.arcMapExists(map_name))
255      {
256        setErrorMsg("Map '" + map_name + "' already exists.");
257        return;
258      }
259    }
260    else
261    {
262      if (ms.nodeMapExists(map_name))
263      {
264        setErrorMsg("Map '" + map_name + "' already exists.");
265        return;
266      }
267    }
268
269    Glib::ustring text = cbType.get_active_text();
270    if (text == "Numeric")
271    {
272      double d;
273      char *endptr;
274      d = strtod(def_val.c_str(), &endptr);
275      if (def_val.c_str() + def_val.length() == endptr)
276      {
277        // the full string was a number
278        if (arc.get_active())
279          ms.createArcMap(map_name, MapValue::NUMERIC,
280              MapValue(d));
281        else
282          ms.createNodeMap(map_name, MapValue::NUMERIC,
283              MapValue(d));
284      }
285      else
286      {
287        // let't try to evaluate the string as an arithmetic expression
288        std::string polishform =
289          string2Polishform(def_val, arc.get_active());
290        if (polishform.empty())
291          return;
292        std::vector<double>* values =
293          evaluate_expr(polishform, arc.get_active());
294        if (arc.get_active())
295        {
296          ms.createArcMap(map_name, MapValue::NUMERIC,
297              MapValue(0.0));
298          std::vector<double>::const_iterator vit = values->begin();
299          for (ArcIt it(ms.digraph); it != INVALID; ++it)
300          {
301            ms.set(map_name, it, MapValue(*vit));
302            ++vit;
303          }
304        }
305        else
306        {
307          ms.createNodeMap(map_name, MapValue::NUMERIC,
308              MapValue(0.0));
309          std::vector<double>::const_iterator vit = values->begin();
310          for (NodeIt it(ms.digraph); it != INVALID; ++it)
311          {
312            ms.set(map_name, it, MapValue(*vit));
313            ++vit;
314          }
315        }
316        delete values;
317      }
318    }
319    else if (text == "String")
320    {
321      if (arc.get_active())
322        ms.createArcMap(map_name, MapValue::STRING,
323            MapValue(def_val));
324      else
325        ms.createNodeMap(map_name, MapValue::STRING,
326            MapValue(def_val));
327    }
328
329    name.set_text("");
330    default_value.set_text("0");
331    arc.show();
332    node.show();
333    hide();
334  }
335}
336
337
338std::string NewMapWin::string2Polishform(std::string rawcommand, bool itisarc)
339{
340  bool valid_entry=true;
341
342  std::map<std::string, int> str2i;
343
344  std::string command;
345
346  std::string variable;
347
348  char index='a';
349
350  for(int i=0;(valid_entry&&(i<(int)rawcommand.size()));i++)
351  {
352    switch(rawcommand[i])
353    {
354      case '+':
355      case '-':
356      case '*':
357      case '/':
358      case ')':
359      case '(':
360        if(!variable.empty())
361        {
362          valid_entry=validVariable(variable, itisarc);
363          ch2var[index]=variable;
364          command+=index;
365          index++;
366          variable.erase(0,variable.size());     
367        }
368        command+=rawcommand[i];
369        break;
370      default:
371        variable+=rawcommand[i];
372        break;
373    }
374  }
375
376  if(!variable.empty()&&valid_entry)
377  {
378    valid_entry=validVariable(variable, itisarc);
379    ch2var[index]=variable;
380    command+=index;
381    index++;
382    variable.erase(0,variable.size());   
383  }
384
385  if(valid_entry)
386  {
387    unsigned int pr=10000;
388    bool prevmult=false;
389    unsigned int prev_change=pr;
390    unsigned int prev_br=pr;
391    int counter=0;
392    std::string comm_nobr="";
393    std::vector<unsigned int> p;
394    p.resize(counter+1);
395
396    //limits
397    //6 brackets embedded
398    //100 operation in a row from the same priority
399
400    for(int i=0;i<(int)command.size();i++)
401    {
402      bool put_in_string=true;
403      switch(command[i])
404      {
405        case '(':
406          pr=prev_br+10000;
407          prev_br=pr;
408          prevmult=false;
409          put_in_string=false;
410          break;
411        case ')':
412          pr=prev_br-10000;
413          prev_br=pr;
414          prevmult=false;
415          put_in_string=false;
416          break;
417        case '+':
418        case '-':
419          if(prevmult)
420          {
421            pr=prev_change;
422          }
423          p[counter]=pr;
424          pr-=100;
425
426          prevmult=false;
427          break;
428        case '/':
429        case '*':
430          if(!prevmult)
431          {
432            prev_change=pr;
433            pr+=200;
434            pr-=1;
435          }
436          p[counter]=pr;
437          pr-=1;
438          prevmult=true;
439          break;
440        default:
441          p[counter]=65000;
442          break;
443      }
444      if(put_in_string)
445      {
446        counter++;
447        p.resize(counter+1);
448        comm_nobr=comm_nobr+command[i];
449      }
450    }
451
452    tree_node * root=weightedString2Tree(comm_nobr, p, 0);
453
454    std::string polishform=postOrder(root);
455
456    deleteTree(root);
457
458    return polishform;
459  }
460  return "";
461}
462
463void NewMapWin::deleteTree(NewMapWin::tree_node * node)
464{
465  if(node->left_child!=NULL)
466  {
467    deleteTree(node->left_child);
468  }
469  if(node->right_child!=NULL)
470  {
471    deleteTree(node->right_child);
472  }
473  delete node;
474}
475
476NewMapWin::tree_node * NewMapWin::weightedString2Tree(std::string to_tree, std::vector<unsigned int> & p, int offset)
477{
478  unsigned int min=p[offset];
479  int minplace=0;
480  for(int i=0;i<(int)to_tree.size();i++)
481  {
482    if(min>p[offset+i])
483    {
484      min=p[offset+i];
485      minplace=i;
486    }
487  }
488  tree_node * act_node=new tree_node;
489  act_node->ch=to_tree[minplace];
490  if(to_tree.size()>=3)
491  {
492    act_node->left_child=weightedString2Tree(to_tree.substr(0,minplace), p, offset);
493    act_node->right_child=weightedString2Tree(to_tree.substr(minplace+1,to_tree.size()-minplace-1), p, offset+minplace+1);
494  }
495  else
496  {
497    act_node->left_child=NULL;
498    act_node->right_child=NULL;
499  }
500  return act_node;
501}
502
503std::string NewMapWin::postOrder(tree_node * subtree)
504{
505  std::string subtree_to_string;
506  if(subtree->left_child)
507  {
508    subtree_to_string=postOrder(subtree->left_child);
509  }
510  if(subtree->right_child)
511  {
512    subtree_to_string=subtree_to_string+postOrder(subtree->right_child);
513  }
514  subtree_to_string=subtree_to_string+subtree->ch;
515  return subtree_to_string;
516}
517
518bool NewMapWin::validVariable(std::string variable, bool itisarc)
519{
520  MapStorage& ms = *mytab.mapstorage;
521
522  bool cancel;
523  //is it mapname?
524  if(itisarc)
525  {
526    std::vector<std::string> arc_maps =
527      ms.getArcMapList(NUM);
528    cancel=(std::find(arc_maps.begin(), arc_maps.end(), variable)==arc_maps.end());
529  }
530  else
531  {
532    std::vector<std::string> node_maps =
533      ms.getNodeMapList(NUM);
534    cancel=(std::find(node_maps.begin(), node_maps.end(), variable)==node_maps.end());
535  }
536  //maybe it is number
537  int point_num=0;
538  if(cancel)
539  {
540    cancel=false;
541    for(int j=0;(!cancel)&&(j<(int)variable.size());j++)
542    {
543      if(((variable[j]<'0')||(variable[j]>'9'))&&(variable[j]!='.'))
544      {
545        cancel=true;
546      }
547      else
548      {
549        if(variable[j]=='.')
550        {
551          point_num++;
552          if(point_num>1)
553          {
554            cancel=true;
555          }
556        }
557      }
558    }
559  }
560  if(cancel)
561  {
562    return false;
563  }
564  return true;
565}
Note: See TracBrowser for help on using the repository browser.