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