1 // -*- c++ -*- |
|
2 #ifndef LEMON_EXPRESSION_H |
|
3 #define LEMON_EXPRESSION_H |
|
4 |
|
5 #include <iostream> |
|
6 #include <map> |
|
7 #include <limits> |
|
8 |
|
9 namespace lemon { |
|
10 |
|
11 /*! \brief Linear expression |
|
12 |
|
13 \c Expr<_Col,_Value> implements a class of linear expressions with the |
|
14 operations of addition and multiplication with scalar. |
|
15 |
|
16 \author Marton Makai |
|
17 */ |
|
18 template <typename _Col, typename _Value> |
|
19 class Expr; |
|
20 |
|
21 template <typename _Col, typename _Value> |
|
22 class Expr { |
|
23 // protected: |
|
24 public: |
|
25 typedef |
|
26 typename std::map<_Col, _Value> Data; |
|
27 Data data; |
|
28 public: |
|
29 void simplify() { |
|
30 for (typename Data::iterator i=data.begin(); |
|
31 i!=data.end(); ++i) { |
|
32 if ((*i).second==0) data.erase(i); |
|
33 } |
|
34 } |
|
35 Expr() { } |
|
36 Expr(_Col _col) { |
|
37 data.insert(std::make_pair(_col, 1)); |
|
38 } |
|
39 Expr& operator*=(_Value _value) { |
|
40 for (typename Data::iterator i=data.begin(); |
|
41 i!=data.end(); ++i) { |
|
42 (*i).second *= _value; |
|
43 } |
|
44 simplify(); |
|
45 return *this; |
|
46 } |
|
47 Expr& operator+=(const Expr<_Col, _Value>& expr) { |
|
48 for (typename Data::const_iterator j=expr.data.begin(); |
|
49 j!=expr.data.end(); ++j) { |
|
50 typename Data::iterator i=data.find((*j).first); |
|
51 if (i==data.end()) { |
|
52 data.insert(std::make_pair((*j).first, (*j).second)); |
|
53 } else { |
|
54 (*i).second+=(*j).second; |
|
55 } |
|
56 } |
|
57 simplify(); |
|
58 return *this; |
|
59 } |
|
60 Expr& operator-=(const Expr<_Col, _Value>& expr) { |
|
61 for (typename Data::const_iterator j=expr.data.begin(); |
|
62 j!=expr.data.end(); ++j) { |
|
63 typename Data::iterator i=data.find((*j).first); |
|
64 if (i==data.end()) { |
|
65 data.insert(std::make_pair((*j).first, -(*j).second)); |
|
66 } else { |
|
67 (*i).second+=-(*j).second; |
|
68 } |
|
69 } |
|
70 simplify(); |
|
71 return *this; |
|
72 } |
|
73 template <typename _C, typename _V> |
|
74 friend std::ostream& operator<<(std::ostream& os, |
|
75 const Expr<_C, _V>& expr); |
|
76 }; |
|
77 |
|
78 template <typename _Col, typename _Value> |
|
79 Expr<_Col, _Value> operator*(_Value _value, _Col _col) { |
|
80 Expr<_Col, _Value> tmp(_col); |
|
81 tmp*=_value; |
|
82 tmp.simplify(); |
|
83 return tmp; |
|
84 } |
|
85 |
|
86 template <typename _Col, typename _Value> |
|
87 Expr<_Col, _Value> operator*(_Value _value, |
|
88 const Expr<_Col, _Value>& expr) { |
|
89 Expr<_Col, _Value> tmp(expr); |
|
90 tmp*=_value; |
|
91 tmp.simplify(); |
|
92 return tmp; |
|
93 } |
|
94 |
|
95 template <typename _Col, typename _Value> |
|
96 Expr<_Col, _Value> operator+(const Expr<_Col, _Value>& expr1, |
|
97 const Expr<_Col, _Value>& expr2) { |
|
98 Expr<_Col, _Value> tmp(expr1); |
|
99 tmp+=expr2; |
|
100 tmp.simplify(); |
|
101 return tmp; |
|
102 } |
|
103 |
|
104 template <typename _Col, typename _Value> |
|
105 Expr<_Col, _Value> operator-(const Expr<_Col, _Value>& expr1, |
|
106 const Expr<_Col, _Value>& expr2) { |
|
107 Expr<_Col, _Value> tmp(expr1); |
|
108 tmp-=expr2; |
|
109 tmp.simplify(); |
|
110 return tmp; |
|
111 } |
|
112 |
|
113 template <typename _Col, typename _Value> |
|
114 std::ostream& operator<<(std::ostream& os, |
|
115 const Expr<_Col, _Value>& expr) { |
|
116 for (typename Expr<_Col, _Value>::Data::const_iterator i= |
|
117 expr.data.begin(); |
|
118 i!=expr.data.end(); ++i) { |
|
119 os << (*i).second << "*" << (*i).first << " "; |
|
120 } |
|
121 return os; |
|
122 } |
|
123 |
|
124 template <typename _Col, typename _Value> |
|
125 class LConstr { |
|
126 // protected: |
|
127 public: |
|
128 Expr<_Col, _Value> expr; |
|
129 _Value lo; |
|
130 public: |
|
131 LConstr(const Expr<_Col, _Value>& _expr, _Value _lo) : |
|
132 expr(_expr), lo(_lo) { } |
|
133 }; |
|
134 |
|
135 template <typename _Col, typename _Value> |
|
136 LConstr<_Col, _Value> |
|
137 operator<=(_Value lo, const Expr<_Col, _Value>& expr) { |
|
138 return LConstr<_Col, _Value>(expr, lo); |
|
139 } |
|
140 |
|
141 template <typename _Col, typename _Value> |
|
142 class UConstr { |
|
143 // protected: |
|
144 public: |
|
145 Expr<_Col, _Value> expr; |
|
146 _Value up; |
|
147 public: |
|
148 UConstr(const Expr<_Col, _Value>& _expr, _Value _up) : |
|
149 expr(_expr), up(_up) { } |
|
150 }; |
|
151 |
|
152 template <typename _Col, typename _Value> |
|
153 UConstr<_Col, _Value> |
|
154 operator<=(const Expr<_Col, _Value>& expr, _Value up) { |
|
155 return UConstr<_Col, _Value>(expr, up); |
|
156 } |
|
157 |
|
158 template <typename _Col, typename _Value> |
|
159 class Constr { |
|
160 // protected: |
|
161 public: |
|
162 Expr<_Col, _Value> expr; |
|
163 _Value lo, up; |
|
164 public: |
|
165 Constr(const Expr<_Col, _Value>& _expr, _Value _lo, _Value _up) : |
|
166 expr(_expr), lo(_lo), up(_up) { } |
|
167 Constr(const LConstr<_Col, _Value>& _lconstr) : |
|
168 expr(_lconstr.expr), |
|
169 lo(_lconstr.lo), |
|
170 up(std::numeric_limits<_Value>::infinity()) { } |
|
171 Constr(const UConstr<_Col, _Value>& _uconstr) : |
|
172 expr(_uconstr.expr), |
|
173 lo(-std::numeric_limits<_Value>::infinity()), |
|
174 up(_uconstr.up) { } |
|
175 }; |
|
176 |
|
177 template <typename _Col, typename _Value> |
|
178 Constr<_Col, _Value> |
|
179 operator<=(const LConstr<_Col, _Value>& lconstr, _Value up) { |
|
180 return Constr<_Col, _Value>(lconstr.expr, lconstr.lo, up); |
|
181 } |
|
182 |
|
183 template <typename _Col, typename _Value> |
|
184 Constr<_Col, _Value> |
|
185 operator<=(_Value lo, const UConstr<_Col, _Value>& uconstr) { |
|
186 return Constr<_Col, _Value>(uconstr.expr, lo, uconstr.up); |
|
187 } |
|
188 |
|
189 template <typename _Col, typename _Value> |
|
190 Constr<_Col, _Value> |
|
191 operator==(const Expr<_Col, _Value>& expr, _Value value) { |
|
192 return Constr<_Col, _Value>(expr, value, value); |
|
193 } |
|
194 |
|
195 } //namespace lemon |
|
196 |
|
197 #endif //LEMON_EXPRESSION_H |
|