Mercuriallemon-0.x / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/marci/lp/expression.h
author alpar
Sat, 29 Jan 2005 23:22:56 +0000
changeset 1109 5222b3d588c3
parent 1097 c91e765266d7
child 1144 1cfabf245433
permissions -rw-r--r--
- Fix missing file (max_matching.h) 
     1 // -*- c++ -*-

     2 #ifndef LEMON_EXPRESSION_H

     3 #define LEMON_EXPRESSION_H

     4 

     5 #include <iostream>

     6 #include <map>

     7 

     8 namespace lemon {

     9 

    10   /*! \brief Linear expression

    11 

    12     \c Expr<_Col,_Value> implements a class of linear expressions with the 

    13     operations of addition and multiplication with scalar. 

    14 

    15     \author Marton Makai

    16    */

    17   template <typename _Col, typename _Value>

    18   class Expr;

    19 

    20   template <typename _Col, typename _Value>

    21   class Expr {

    22 //  protected:

    23   public:

    24     typedef 

    25     typename std::map<_Col, _Value> Data; 

    26     Data data;

    27   public:

    28     void simplify() {

    29       for (typename Data::iterator i=data.begin(); 

    30 	   i!=data.end(); ++i) {

    31 	if ((*i).second==0) data.erase(i);

    32       }

    33     }

    34     Expr() { }

    35     Expr(_Col _col) { 

    36       data.insert(std::make_pair(_col, 1));

    37     }

    38     Expr& operator*=(_Value _value) {

    39       for (typename Data::iterator i=data.begin(); 

    40 	   i!=data.end(); ++i) {

    41 	(*i).second *= _value;

    42       }

    43       simplify();

    44       return *this;

    45     }

    46     Expr& operator+=(const Expr<_Col, _Value>& expr) {

    47       for (typename Data::const_iterator j=expr.data.begin(); 

    48 	   j!=expr.data.end(); ++j) {

    49 	typename Data::iterator i=data.find((*j).first);

    50 	if (i==data.end()) {

    51 	  data.insert(std::make_pair((*j).first, (*j).second));

    52 	} else {

    53 	  (*i).second+=(*j).second;

    54 	}

    55       }

    56       simplify();

    57       return *this;

    58     }

    59     Expr& operator-=(const Expr<_Col, _Value>& expr) {

    60       for (typename Data::const_iterator j=expr.data.begin(); 

    61 	   j!=expr.data.end(); ++j) {

    62 	typename Data::iterator i=data.find((*j).first);

    63 	if (i==data.end()) {

    64 	  data.insert(std::make_pair((*j).first, -(*j).second));

    65 	} else {

    66 	  (*i).second+=-(*j).second;

    67 	}

    68       }

    69       simplify();

    70       return *this;

    71     }

    72     template <typename _C, typename _V> 

    73     friend std::ostream& operator<<(std::ostream& os, 

    74 				    const Expr<_C, _V>& expr);

    75   };

    76 

    77   template <typename _Col, typename _Value>

    78   Expr<_Col, _Value> operator*(_Value _value, _Col _col) {

    79     Expr<_Col, _Value> tmp(_col);

    80     tmp*=_value;

    81     tmp.simplify();

    82     return tmp;

    83   }

    84 

    85   template <typename _Col, typename _Value>

    86   Expr<_Col, _Value> operator*(_Value _value, 

    87 			       const Expr<_Col, _Value>& expr) {

    88     Expr<_Col, _Value> tmp(expr);

    89     tmp*=_value;

    90     tmp.simplify();

    91     return tmp;

    92   }

    93 

    94   template <typename _Col, typename _Value>

    95   Expr<_Col, _Value> operator+(const Expr<_Col, _Value>& expr1, 

    96 			       const Expr<_Col, _Value>& expr2) {

    97     Expr<_Col, _Value> tmp(expr1);

    98     tmp+=expr2;

    99     tmp.simplify();

   100     return tmp;

   101   }

   102 

   103   template <typename _Col, typename _Value>

   104   Expr<_Col, _Value> operator-(const Expr<_Col, _Value>& expr1, 

   105 			       const Expr<_Col, _Value>& expr2) {

   106     Expr<_Col, _Value> tmp(expr1);

   107     tmp-=expr2;

   108     tmp.simplify();

   109     return tmp;

   110   }

   111 

   112   template <typename _Col, typename _Value>

   113   std::ostream& operator<<(std::ostream& os, 

   114 			   const Expr<_Col, _Value>& expr) {

   115     for (typename Expr<_Col, _Value>::Data::const_iterator i=

   116 	   expr.data.begin(); 

   117 	 i!=expr.data.end(); ++i) {

   118       os << (*i).second << "*" << (*i).first << " ";

   119     }

   120     return os;

   121   }

   122   

   123 } //namespace lemon

   124 

   125 #endif //LEMON_EXPRESSION_H
lemon-0.x