COIN-OR::LEMON - Graph Library

source: glemon-0.x/new_map_win.cc

Last change on this file was 174:95872af46fc4, checked in by Alpar Juttner, 17 years ago

Add copyright headers

File size: 11.2 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
21bool NewMapWin::closeIfEscapeIsPressed(GdkEventKey* e)
22{
23  if(e->keyval==GDK_Escape)
24  {
25    hide();
26  }
27  return true;
28}
29
30NewMapWin::NewMapWin(const std::string& title, NoteBookTab & mw, bool itisedge, bool edgenode):Gtk::Dialog(title, true, true),mytab(mw),node("Create NodeMap"),edge("Create EdgeMap")
31{
32  set_default_size(200, 50);
33
34  signal_key_press_event().connect(sigc::mem_fun(*this, &NewMapWin::closeIfEscapeIsPressed));
35
36  Gtk::VBox * vbox=get_vbox();
37
38  //entries
39  table=new Gtk::Table(3, 2, false);
40
41  label=new Gtk::Label;
42  label->set_text("Name of new map:");
43  name.set_text("");
44
45  (*table).attach(*label,0,1,0,1,Gtk::SHRINK,Gtk::SHRINK,10,3);
46  (*table).attach(name,1,2,0,1,Gtk::SHRINK,Gtk::SHRINK,10,3);
47
48  label=new Gtk::Label;
49  label->set_text("Default value in the map:");
50  default_value.set_text("0");
51
52  (*table).attach(*label,0,1,1,2,Gtk::SHRINK,Gtk::SHRINK,10,3);
53  (*table).attach(default_value,1,2,1,2,Gtk::SHRINK,Gtk::SHRINK,10,3);
54
55  //node vs. edge map selector
56  Gtk::RadioButton::Group group = node.get_group();
57  edge.set_group(group);
58 
59  if(edgenode)
60    {
61      (*table).attach(node,0,1,2,3,Gtk::SHRINK,Gtk::SHRINK,10,3);
62      (*table).attach(edge,1,2,2,3,Gtk::SHRINK,Gtk::SHRINK,10,3);
63    }
64  else
65    {
66      if(itisedge)
67        {
68          edge.set_active();
69        }
70      else
71        {
72          node.set_active();
73        }
74    }
75
76  vbox->pack_start(*table);
77
78  //OK button
79  add_button(Gtk::Stock::OK, Gtk::RESPONSE_OK);
80
81  show_all_children();
82
83}
84
85void NewMapWin::on_response(int response_id)
86{
87  if(response_id==Gtk::RESPONSE_OK)
88    {
89      double def_val=0;
90
91      //get and formulate text
92      std::string def_val_str=default_value.get_text();
93
94      bool only_nums=true;
95      for(int i=0;i<(int)def_val_str.size() && only_nums;i++)
96        {
97          if( def_val_str[i]<'0' || def_val_str[i]>'9' )
98            {
99              only_nums=false;
100            }
101        }
102      std::string polishform;
103
104      if(only_nums)
105        {
106          def_val=atof(def_val_str.c_str());
107        }
108      else
109        {
110          polishform=string2Polishform(def_val_str,edge.get_active());
111        }
112
113      //get name of text
114      std::string mapname=name.get_text();
115     
116      if(!mapname.empty()&&(!polishform.empty()||only_nums))
117        {
118          int abortion=0;
119          if(edge.get_active())
120            {
121              //create the new map
122              Graph::EdgeMap<double> * emptr=new Graph::EdgeMap<double> (mytab.mapstorage.graph, def_val);
123             
124              if(!only_nums)
125                {
126                  std::stack<double> polishstack;
127                 
128                  for(EdgeIt k(mytab.mapstorage.graph); k!=INVALID; ++k)
129                    {
130                      for(int i=0;i<(int)polishform.size();i++)
131                        {
132                          double op1=0, op2=0;
133                          bool operation=true;
134                          switch(polishform[i])
135                            {
136                            case '+':
137                            case '-':
138                            case '/':
139                            case '*':
140                              op1=polishstack.top();
141                              polishstack.pop();
142                              op2=polishstack.top();
143                              polishstack.pop();
144                              break;
145                            default:
146                              //substitute variable
147                              std::map< std::string,Graph::EdgeMap<double> * > ems=mytab.mapstorage.edgemap_storage;
148                              bool itisvar=(ems.find(ch2var[ polishform[i] ])!=ems.end());
149                              if(itisvar)
150                                {
151                                  polishstack.push( (*(mytab.mapstorage.edgemap_storage[ ch2var[ polishform[i] ] ]))[k]);
152                                }
153                              else
154                                {
155                                  polishstack.push(atof(ch2var[ polishform[i] ].c_str()));
156                                }
157                              operation=false;
158                              break;
159                            }
160                          if(operation)
161                            {
162                              double res;
163                              switch(polishform[i])
164                                {
165                                case '+':
166                                  res=op1+op2;
167                                  break;
168                                case '-':
169                                  res=op2-op1;
170                                  break;
171                                case '/':
172                                  res=op2/op1;
173                                  break;
174                                case '*':
175                                  res=op1*op2;
176                                  break;
177                                default:
178                                  std::cout << "How could we get here?" << std::endl;
179                                  break;
180                                }
181                              polishstack.push(res);
182                            }
183                        }//foreach letter in polishform
184                      (*emptr)[k]=polishstack.top();
185                    }//foreach edge
186                }//!only_nums
187
188              //if addition was not successful addEdgeMap returns one.
189              //cause can be that there is already a map named like the new one
190              if(mytab.mapstorage.addEdgeMap(mapname, emptr, def_val))
191                {
192                  abortion=1;
193                }
194
195              //add it to the list of the displayable maps
196              //furthermore it is done by signals
197              //mytab.registerNewEdgeMap(mapname);
198
199              //display it
200              //gdc.changeEdgeText(mapname);
201            }
202          else //!edge.get_active()
203            {
204              //create the new map
205              Graph::NodeMap<double> * emptr=new Graph::NodeMap<double> (mytab.mapstorage.graph, def_val);
206
207              if(!only_nums)
208                {
209                  std::stack<double> polishstack;
210 
211                  for(NodeIt k(mytab.mapstorage.graph); k!=INVALID; ++k)
212                    {
213                      for(int i=0;i<(int)polishform.size();i++)
214                        {
215                          double op1=0, op2=0;
216                          bool operation=true;
217                          switch(polishform[i])
218                            {
219                            case '+':
220                            case '-':
221                            case '/':
222                            case '*':
223                              op1=polishstack.top();
224                              polishstack.pop();
225                              op2=polishstack.top();
226                              polishstack.pop();
227                              break;
228                            default:
229                              std::map< std::string,Graph::NodeMap<double> * > nms=mytab.mapstorage.nodemap_storage;
230                              bool itisvar=(nms.find(ch2var[ polishform[i] ])!=nms.end());
231                              if(itisvar)
232                                {
233                                  polishstack.push( (*(mytab.mapstorage.nodemap_storage[ ch2var[ polishform[i] ] ]))[k]);
234                                }
235                              else
236                                {
237                                  polishstack.push(atof(ch2var[ polishform[i] ].c_str()));
238                                }
239                              operation=false;
240                              break;
241                            }
242                          if(operation)
243                            {
244                              double res;
245                              switch(polishform[i])
246                                {
247                                case '+':
248                                  res=op1+op2;
249                                  break;
250                                case '-':
251                                  res=op2-op1;
252                                  break;
253                                case '/':
254                                  res=op2/op1;
255                                  break;
256                                case '*':
257                                  res=op1*op2;
258                                  break;
259                                default:
260                                  std::cout << "How could we get here?" << std::endl;
261                                  break;
262                                }
263                              polishstack.push(res);
264                            }
265                        }
266                      (*emptr)[k]=polishstack.top();
267                    }
268                }
269              //if addition was not successful addNodeMap returns one.
270              //cause can be that there is already a map named like the new one
271              if(mytab.mapstorage.addNodeMap(mapname,emptr, def_val))
272                {
273                  abortion=1;
274                }
275
276              //add it to the list of the displayable maps
277              //furthermore it is done by signals
278              //mytab.registerNewNodeMap(mapname);
279
280              //display it
281              //gdc.changeNodeText(mapname);
282            }
283          if(!abortion)
284            {
285              name.set_text("");
286              default_value.set_text("0");
287              edge.show();
288              node.show();
289              hide();
290            }
291        }
292    }
293}
294
295
296std::string NewMapWin::string2Polishform(std::string rawcommand, bool itisedge)
297{
298  bool valid_entry=true;
299
300  std::map<std::string, int> str2i;
301
302  std::string command;
303
304  std::string variable;
305
306  char index='a';
307
308  for(int i=0;(valid_entry&&(i<(int)rawcommand.size()));i++)
309    {
310      switch(rawcommand[i])
311        {
312        case '+':
313        case '-':
314        case '*':
315        case '/':
316        case ')':
317        case '(':
318          if(!variable.empty())
319            {
320              valid_entry=validVariable(variable, itisedge);
321              ch2var[index]=variable;
322              command+=index;
323              index++;
324              variable.erase(0,variable.size());         
325            }
326          command+=rawcommand[i];
327          break;
328        default:
329          variable+=rawcommand[i];
330          break;
331        }
332    }
333
334  if(!variable.empty()&&valid_entry)
335    {
336      valid_entry=validVariable(variable, itisedge);
337      ch2var[index]=variable;
338      command+=index;
339      index++;
340      variable.erase(0,variable.size());         
341    }
342
343  if(valid_entry)
344    {
345      unsigned int pr=10000;
346      bool prevmult=false;
347      unsigned int prev_change=pr;
348      unsigned int prev_br=pr;
349      int counter=0;
350      std::string comm_nobr="";
351      std::vector<unsigned int> p;
352      p.resize(counter+1);
353     
354      //limits
355      //6 brackets embedded
356      //100 operation in a row from the same priority
357     
358      for(int i=0;i<(int)command.size();i++)
359        {
360          bool put_in_string=true;
361          switch(command[i])
362            {
363            case '(':
364              pr=prev_br+10000;
365              prev_br=pr;
366              prevmult=false;
367              put_in_string=false;
368              break;
369            case ')':
370              pr=prev_br-10000;
371              prev_br=pr;
372              prevmult=false;
373              put_in_string=false;
374              break;
375            case '+':
376            case '-':
377              if(prevmult)
378                {
379                  pr=prev_change;
380                }
381              p[counter]=pr;
382              pr-=100;
383
384              prevmult=false;
385              break;
386            case '/':
387            case '*':
388              if(!prevmult)
389                {
390                  prev_change=pr;
391                  pr+=200;
392                  pr-=1;
393                }
394              p[counter]=pr;
395              pr-=1;
396              prevmult=true;
397              break;
398            default:
399              p[counter]=65000;
400              break;
401            }
402          if(put_in_string)
403            {
404              counter++;
405              p.resize(counter+1);
406              comm_nobr=comm_nobr+command[i];
407            }
408        }
409
410      tree_node * root=weightedString2Tree(comm_nobr, p, 0);
411
412      std::string polishform=postOrder(root);
413
414      deleteTree(root);
415
416      return polishform;
417    }
418  return "";
419}
420
421void NewMapWin::deleteTree(NewMapWin::tree_node * node)
422{
423  if(node->left_child!=NULL)
424    {
425      deleteTree(node->left_child);
426    }
427  if(node->right_child!=NULL)
428    {
429      deleteTree(node->right_child);
430    }
431  delete node;
432}
433
434NewMapWin::tree_node * NewMapWin::weightedString2Tree(std::string to_tree, std::vector<unsigned int> & p, int offset)
435{
436  unsigned int min=p[offset];
437  int minplace=0;
438  for(int i=0;i<(int)to_tree.size();i++)
439    {
440      if(min>p[offset+i])
441        {
442          min=p[offset+i];
443          minplace=i;
444        }
445    }
446  tree_node * act_node=new tree_node;
447  act_node->ch=to_tree[minplace];
448  if(to_tree.size()>=3)
449    {
450      act_node->left_child=weightedString2Tree(to_tree.substr(0,minplace), p, offset);
451      act_node->right_child=weightedString2Tree(to_tree.substr(minplace+1,to_tree.size()-minplace-1), p, offset+minplace+1);
452    }
453  else
454    {
455      act_node->left_child=NULL;
456      act_node->right_child=NULL;
457    }
458  return act_node;
459}
460
461std::string NewMapWin::postOrder(tree_node * subtree)
462{
463  std::string subtree_to_string;
464  if(subtree->left_child)
465    {
466      subtree_to_string=postOrder(subtree->left_child);
467    }
468  if(subtree->right_child)
469    {
470      subtree_to_string=subtree_to_string+postOrder(subtree->right_child);
471    }
472  subtree_to_string=subtree_to_string+subtree->ch;
473  return subtree_to_string;
474}
475
476bool NewMapWin::validVariable(std::string variable, bool itisedge)
477{
478  bool cancel;
479  //is it mapname?
480  if(itisedge)
481    {
482      cancel=(mytab.mapstorage.edgemap_storage.find(variable)==mytab.mapstorage.edgemap_storage.end());
483    }
484  else
485    {
486      cancel=(mytab.mapstorage.nodemap_storage.find(variable)==mytab.mapstorage.nodemap_storage.end());
487    }
488  //maybe it is number
489  int point_num=0;
490  if(cancel)
491    {
492      cancel=false;
493      for(int j=0;(!cancel)&&(j<(int)variable.size());j++)
494        {
495          if(((variable[j]<'0')||(variable[j]>'9'))&&(variable[j]!='.'))
496            {
497              cancel=true;
498            }
499          else
500            {
501              if(variable[j]=='.')
502                {
503                  point_num++;
504                  if(point_num>1)
505                    {
506                      cancel=true;
507                    }
508                }
509            }
510        }
511    }
512  if(cancel)
513    {
514      return false;
515    }
516  return true;
517}
Note: See TracBrowser for help on using the repository browser.