COPASI API  4.16.103
CNormalLogical.h
Go to the documentation of this file.
1 // Begin CVS Header
2 // $Source: /Volumes/Home/Users/shoops/cvs/copasi_dev/copasi/compareExpressions/CNormalLogical.h,v $
3 // $Revision: 1.22 $
4 // $Name: $
5 // $Author: shoops $
6 // $Date: 2011/03/07 19:26:19 $
7 // End CVS Header
8 
9 // Copyright (C) 2011 - 2010 by Pedro Mendes, Virginia Tech Intellectual
10 // Properties, Inc., University of Heidelberg, and The University
11 // of Manchester.
12 // All rights reserved.
13 
14 // Copyright (C) 2008 by Pedro Mendes, Virginia Tech Intellectual
15 // Properties, Inc., EML Research, gGmbH, University of Heidelberg,
16 // and The University of Manchester.
17 // All rights reserved.
18 
19 // Copyright (C) 2001 - 2007 by Pedro Mendes, Virginia Tech Intellectual
20 // Properties, Inc. and EML Research, gGmbH.
21 // All rights reserved.
22 
23 #ifndef CNormalLogical_H__
24 #define CNormalLogical_H__
25 
26 #include <string>
27 #include <iostream>
28 #include <set>
29 #include <map>
30 #include <utility>
31 
35 
37 {
38 public:
39  template<typename TYPE>
40  class SetSorter
41  {
42  public:
43  /**
44  * This routine compares a set and returns true if the first
45  * argument is smaller than the second.
46  */
47  bool operator()(const std::pair<TYPE*, bool>& lhs,
48  const std::pair<TYPE*, bool>& rhs) const
49  {
50  bool result = false;
51 
52  // the compiler warnings about broken strict aliasing rules
53  // that are issued by e.g. gcc 4.4.5 on linux are bogus
54  // see GCC Bug 39390
55  if (lhs.second == rhs.second)
56  {
57  result = ((*lhs.first) < (*rhs.first));
58  }
59  else if (lhs.second == true)
60  {
61  result = true;
62  }
63 
64  return result;
65  }
66 
67  /**
68  * This routine compares a set and returns true if the first
69  * argument is equal to the second.
70  */
71  bool isEqual(const std::pair<TYPE*, bool>& lhs,
72  const std::pair<TYPE*, bool>& rhs) const
73  {
74  bool result = true;
75 
76  if (!(lhs.second == rhs.second && (*lhs.first) == (*rhs.first)))
77  {
78  result = false;
79  }
80 
81  return result;
82  }
83  };
84 
85  template<typename TYPE> class TemplateSet:
86  public std::set< std::pair< TYPE *, bool >, SetSorter< TYPE > > {};
87 
88  template<typename TYPE>
90  {
91  public:
92  /**
93  * This routine compares a set of sets and returns true if the first
94  * argument is smaller than the second.
95  */
96  bool operator()(const std::pair<TemplateSet<TYPE>, bool>& lhs, const std::pair<TemplateSet<TYPE>, bool>& rhs) const
97  {
98  bool result = false;
99 
100  if (lhs.second == rhs.second)
101  {
102  if (lhs.first.size() == rhs.first.size())
103  {
104  typename std::set<std::pair<TYPE*, bool>, CNormalLogical::SetSorter<TYPE> >::const_iterator it = lhs.first.begin(), endit = lhs.first.end(), it2 = rhs.first.begin();
105  SetSorter<TYPE> sorter;
106 
107  while (it != endit && result == false)
108  {
109  // first test the other way round because if
110  // it2 is less then it, we can already stop
111  if (sorter(*it2, *it) == true)
112  {
113  break;
114  }
115 
116  result = sorter(*it, *it2);
117  ++it;
118  ++it2;
119  }
120  }
121  else if (lhs.first.size() < rhs.first.size())
122  {
123  result = true;
124  }
125  }
126  else if (lhs.second == true)
127  {
128  result = true;
129  }
130 
131  return result;
132  }
133 
134  /**
135  * This routine compares a set of sets and returns true if the first
136  * argument is smaller than the second.
137  */
138  bool isEqual(const std::pair<TemplateSet<TYPE>, bool>& lhs,
139  const std::pair<TemplateSet<TYPE>, bool>& rhs) const
140  {
141  bool result = true;
142 
143  if (lhs.second == rhs.second)
144  {
145  if (lhs.first.size() == rhs.first.size())
146  {
147  typename std::set<std::pair<TYPE*, bool>, CNormalLogical::SetSorter <TYPE> >::const_iterator
148  it = lhs.first.begin(),
149  endit = lhs.first.end(),
150  it2 = rhs.first.begin();
151 
152  SetSorter<TYPE> sorter;
153 
154  while (it != endit && result == true)
155  {
156  result = sorter.isEqual(*it, *it2);
157  ++it;
158  ++it2;
159  }
160  }
161  else
162  {
163  result = false;
164  }
165  }
166  else
167  {
168  result = false;
169  }
170 
171  return result;
172  }
173  };
174 
175  template<typename TYPE> class TemplateSetOfSets:
176  public std::set< std::pair< TemplateSet< TYPE >, bool >, SetOfSetsSorter< TYPE > > {};
177 
182 
183 protected:
184  /**
185  * Flag to specify whether the whole logical expression has to be
186  * negated.
187  */
188  bool mNot;
189 
190  // this is a set of sets.
191  // all sets are combined by OR and all items within the sets are
192  // combined by AND
193  // the boolean value represents negation (NOT)
194  // in the normlized form all NOT flags should be false
196 
197  // this is a set of sets.
198  // all sets are combined by OR and all items within the sets are
199  // combined by AND
200  // the boolean value represents negation (NOT)
201  // in the normlized form the set should be empty
203 
204 public:
205  CNormalLogical();
206  CNormalLogical(const CNormalLogical& src);
207  virtual ~CNormalLogical();
208 
210  bool operator==(const CNormalLogical& rhs) const;
211  bool operator<(const CNormalLogical& rhs) const;
212 
213  virtual CNormalBase * copy() const;
214 
215  virtual std::string toString() const;
216  virtual bool simplify();
217 
218  bool isNegated() const;
219 
220  void setIsNegated(bool negate);
221 
222  void negate();
223 
225  const ChoiceSetOfSets& getChoices() const;
226 
228  const ItemSetOfSets& getAndSets() const;
229 
230  void setAndSets(const ItemSetOfSets& set);
231  void setChoices(const ChoiceSetOfSets& set);
232 
233  /**
234  * This routine calls cleanSet on all inner sets.
235  */
236  template<typename TYPE>
238  {
239  typename TemplateSetOfSets<TYPE>::iterator it = s.begin(), endit = s.end();
240 
241  while (it != endit)
242  {
243  //TemplateSet<TYPE> tmpSet=it->first;
244  cleanSet(/*tmpSet*/it->first);
245  ++it;
246  }
247 
248  s.clear();
249  }
250 
251  /**
252  * This routine makes a deep copy of all elements in the souce set and
253  * appends them to the target set.
254  */
255  template<typename TYPE>
256  static void copySet(const TemplateSet<TYPE> & source, TemplateSet<TYPE> & target)
257  {
258  typename TemplateSet<TYPE>::const_iterator it = source.begin(), endit = source.end();
259 
260  while (it != endit)
261  {
262  bool tmpRes = target.insert(std::make_pair(new TYPE(*it->first), it->second)).second;
263  assert(tmpRes == true);
264  ++it;
265  }
266  }
267 
268  /**
269  * This routine calls delete an all pointers in the set.
270  */
271  template<typename TYPE>
272  static void cleanSet(const TemplateSet<TYPE> & s)
273  {
274  typename TemplateSet<TYPE>::const_iterator it = s.begin(), endit = s.end();
275 
276  while (it != endit)
277  {
278  delete it->first;
279  ++it;
280  }
281  }
282 
283 protected:
284  /**
285  * Negates a set of elements.
286  * The result of the operation is returned in target.
287  * The type of result depends on the source. If the source was a set of AND
288  * combined elements, the result is a set of OR combined elements and vice versa.
289  * target set.
290  */
291  template<typename TYPE>
292  static bool negateSets(const TemplateSet<TYPE> & source,
293  TemplateSet<TYPE> & target)
294  {
295  bool result = true;
296  typename TemplateSet<TYPE>::const_iterator it = source.begin(), endit = source.end();
297 
298  while (it != endit)
299  {
300  if (it->second == false)
301  {
302  TYPE* pItem = new TYPE(*it->first);
303  pItem->negate();
304  target.insert(std::make_pair(pItem, false));
305  }
306  else
307  {
308  target.insert(std::make_pair(new TYPE(*it->first), false));
309  }
310 
311  ++it;
312  }
313 
314  return result;
315  }
316 
317  /**
318  * Negates a set of sets with elements.
319  * The result of the operation is returned in target.
320  * The type of the result depends on the source.
321  * If the source was a set of AND combined sets of OR combined
322  * elements, the rersult will be a set of OR combined sets with AND combined
323  * elements.
324  */
325  template<typename TYPE>
326  static bool negateSetOfSets(const TemplateSetOfSets<TYPE> & source,
327  TemplateSetOfSets<TYPE> & target)
328  {
329  bool result = true;
330  typename TemplateSetOfSets<TYPE>::const_iterator it = source.begin(), endit = source.end();
331 
332  while (it != endit && result == true)
333  {
334  TemplateSet<TYPE> tmpTarget;
335 
336  if (it->second == false)
337  {
338  result = negateSets(it->first, tmpTarget);
339  }
340  else
341  {
342  typename std::set<std::pair<TYPE*, bool>, CNormalLogical::SetSorter<TYPE> >::const_iterator it2 = it->first.begin(), endit2 = it->first.end();
343 
344  while (it2 != endit2)
345  {
346  tmpTarget.insert(std::make_pair(new TYPE(*it2->first), it2->second));
347  ++it2;
348  }
349  }
350 
351  target.insert(std::make_pair(tmpTarget, false));
352  ++it;
353  }
354 
355  if (result == false)
356  {
357  // cleanup target
358  it = target.begin(), endit = target.end();
359 
360  while (it != endit)
361  {
362  typename TemplateSet<TYPE>::const_iterator it2 = it->first.begin(), endit2 = it->first.end();
363 
364  while (it2 != endit2)
365  {
366  delete it2->first;
367  ++it2;
368  }
369 
370  ++it;
371  }
372 
373  target.clear();
374  }
375 
376  return result;
377  }
378 
379  /**
380  * Converts a set of AND combined sets of OR combined elements into a
381  * target set of OR combined sets of AND combined elements.
382  */
383  template<typename TYPE>
384  static bool convertAndOrToOrAnd(const TemplateSetOfSets<TYPE> & source,
385  TemplateSetOfSets<TYPE> & target)
386  {
387  bool result = true;
388 
389  if (source.size() > 1)
390  {
391  TemplateSetOfSets<TYPE> tmpSourceSet(source);
392  tmpSourceSet.erase(tmpSourceSet.begin());
393 
394  TemplateSetOfSets<TYPE> tmpTargetSet;
395  result = ((*source.begin()).second == false);
396 
397  if (result == true)
398  {
399  // recursively call this function
400  // the result returned in tmpTargetSet is a combination of and combined sets of or combined items
401  result = convertAndOrToOrAnd(tmpSourceSet, tmpTargetSet);
402 
403  if (result == true)
404  {
405  // for each item in source.begin().first go through all sets in
406  // tmpTarget
407  typename TemplateSet<TYPE>::const_iterator it = (*source.begin()).first.begin(), endit = (*source.begin()).first.end();
408 
409  while (it != endit)
410  {
411  typename TemplateSetOfSets<TYPE>::const_iterator it2 = tmpTargetSet.begin(), endit2 = tmpTargetSet.end();
412 
413  while (it2 != endit2)
414  {
415  TemplateSet<TYPE> tmpSet;
416  TYPE* pNewItem = new TYPE(*it->first);
417 
418  if (tmpSet.insert(std::make_pair(pNewItem, false)).second == false)
419  {
420  delete pNewItem;
421  }
422 
423  typename TemplateSet<TYPE>::const_iterator it3 = it2->first.begin(), endit3 = it2->first.end();
424 
425  while (it3 != endit3)
426  {
427  pNewItem = new TYPE(*(*it3).first);
428 
429  if (tmpSet.insert(std::make_pair(pNewItem, false)).second == false)
430  {
431  delete pNewItem;
432  }
433 
434  ++it3;
435  }
436 
437  ++it2;
438 
439  if (target.insert(std::make_pair(tmpSet, false)).second == false)
440  {
441  cleanSet(tmpSet);
442  }
443  }
444 
445  ++it;
446  }
447  }
448  }
449 
450  // cleanup tmpTarget
451  cleanSetOfSets(tmpTargetSet);
452  }
453  else if (source.size() == 1)
454  {
455  // all not flags have to be eliminated at this point
456  if ((*source.begin()).second == true)
457  {
458  result = false;
459  }
460  else
461  {
462  // we have a set of and combined elements in (*source.begin()).first
463  // and we convert them to a set of or combined items
464  // So one set of n items becomes n sets of one item each.
465  const TemplateSet<TYPE> item = (*source.begin()).first;
466  typename TemplateSet<TYPE>::const_iterator it = item.begin(), endit = item.end();
467 
468  while (it != endit && result == true)
469  {
470  if (it->second == true)
471  {
472  result = false;
473  }
474  else
475  {
476  TemplateSet<TYPE> tmpSet;
477  TYPE* pNewItem = new TYPE(*it->first);
478  tmpSet.insert(std::make_pair(pNewItem, false));
479 
480  if (target.insert(std::make_pair(tmpSet, false)).second == false)
481  {
482  // clean up if the insert failed.
483  delete pNewItem;
484  }
485  }
486 
487  ++it;
488  }
489  }
490  }
491 
492  if (result == false)
493  {
494  // delete all elements in target
495  typename TemplateSetOfSets<TYPE>::iterator it = target.begin(), endit = target.end();
496 
497  while (it != endit)
498  {
499  typename TemplateSet<TYPE>::iterator it2 = it->first.begin(), endit2 = it->first.end();
500 
501  while (it2 != endit2)
502  {
503  delete it2->first;
504  ++it2;
505  }
506 
507  ++it;
508  }
509 
510  target.clear();
511  }
512 
513  return result;
514  }
515 
516  /**
517  * This routine makes deep copies of all inner sets and appends them to
518  * the target set.
519  */
520  template<typename TYPE>
521  static void copySetOfSets(const TemplateSetOfSets<TYPE> & source,
522  TemplateSetOfSets<TYPE> & target)
523  {
524  typename TemplateSetOfSets<TYPE>::const_iterator it = source.begin(), endit = source.end();
525 
526  while (it != endit)
527  {
528  TemplateSet<TYPE> tmpSet;
529  copySet(it->first, tmpSet);
530  bool tmpRes = target.insert(std::make_pair(tmpSet, it->second)).second;
531  assert(tmpRes == true);
532  ++it;
533  }
534  }
535 
536  /**
537  * This method creates the canonical disjunctive normalform for a logical
538  * expression. The expression must not contain choices and no negated item
539  * sets or items. Since the method scales with exponentially, the number of
540  * logical individual logical items in the expression is limited to 16.
541  * The return value is true if the call succeeded and false otherwise.
542  */
543  bool generateCanonicalDNF(ItemSetOfSets& tmpAndSet) const;
544 
545  /**
546  * Given a map that associates each logical element with a truth value,
547  * this method evaluates the whole logical expression.
548  */
549  bool evaluateExpression(const std::map<CNormalLogicalItem, bool>& truthValueMap) const;
550 
551  /**
552  * This methods checks wether there is something like A and !A in a set, if
553  * such an occurance is found, the whole set is converted to a set with either a false or a true item.
554  * For or combined items, this would be true, for and combined
555  * sets, it would be false.
556  * If there already are sets in the outer set, this set could be eliminated
557  * altogether.
558  */
559  static void eliminateNullItems(const ItemSetOfSets& source, ItemSetOfSets& target, bool orSet);
560 
561 #ifdef COPASI_DEBUG
562  static void printSetOfSets(const ItemSetOfSets& set);
563  static void printSetSizes(const ItemSetOfSets& set);
564  static void printSetElement(const ItemSetOfSets& set, unsigned int index1, unsigned int index2);
565 #endif // COPASI_DEBUG
566 };
567 
568 std::ostream& operator<<(std::ostream& os, const CNormalLogical& logical);
569 
570 #endif /* CNormalLogical */
bool operator()(const std::pair< TemplateSet< TYPE >, bool > &lhs, const std::pair< TemplateSet< TYPE >, bool > &rhs) const
bool isEqual(const std::pair< TYPE *, bool > &lhs, const std::pair< TYPE *, bool > &rhs) const
static bool negateSets(const TemplateSet< TYPE > &source, TemplateSet< TYPE > &target)
ChoiceSetOfSets & getChoices()
static void eliminateNullItems(const ItemSetOfSets &source, ItemSetOfSets &target, bool orSet)
TemplateSet< CNormalLogicalItem > ItemSet
CNormalLogical & operator=(const CNormalLogical &src)
static void cleanSetOfSets(TemplateSetOfSets< TYPE > &s)
TemplateSetOfSets< CNormalChoiceLogical > ChoiceSetOfSets
bool evaluateExpression(const std::map< CNormalLogicalItem, bool > &truthValueMap) const
virtual bool simplify()
C_LOGICAL logical
Definition: f2c.h:18
TemplateSetOfSets< CNormalLogicalItem > ItemSetOfSets
ItemSetOfSets mAndSets
bool isNegated() const
bool generateCanonicalDNF(ItemSetOfSets &tmpAndSet) const
virtual std::string toString() const
virtual ~CNormalLogical()
void setAndSets(const ItemSetOfSets &set)
static bool negateSetOfSets(const TemplateSetOfSets< TYPE > &source, TemplateSetOfSets< TYPE > &target)
static bool convertAndOrToOrAnd(const TemplateSetOfSets< TYPE > &source, TemplateSetOfSets< TYPE > &target)
void setChoices(const ChoiceSetOfSets &set)
static void cleanSet(const TemplateSet< TYPE > &s)
std::ostream & operator<<(std::ostream &os, const CNormalLogical &logical)
bool isEqual(const std::pair< TemplateSet< TYPE >, bool > &lhs, const std::pair< TemplateSet< TYPE >, bool > &rhs) const
static void copySetOfSets(const TemplateSetOfSets< TYPE > &source, TemplateSetOfSets< TYPE > &target)
bool operator<(const CNormalLogical &rhs) const
bool operator()(const std::pair< TYPE *, bool > &lhs, const std::pair< TYPE *, bool > &rhs) const
void setIsNegated(bool negate)
virtual CNormalBase * copy() const
static void copySet(const TemplateSet< TYPE > &source, TemplateSet< TYPE > &target)
TemplateSet< CNormalChoiceLogical > ChoiceSet
bool operator==(const CNormalLogical &rhs) const
ChoiceSetOfSets mChoices
ItemSetOfSets & getAndSets()