src/sim/linear_solver.hh

   1 /*
   2  * Copyright (c) 2015 ARM Limited
   3  * All rights reserved
   4  *
   5  * The license below extends only to copyright in the software and shall
   6  * not be construed as granting a license to any other intellectual
   7  * property including but not limited to intellectual property relating
   8  * to a hardware implementation of the functionality of the software
   9  * licensed hereunder.  You may use the software subject to the license
  10  * terms below provided that you ensure that this notice is replicated
  11  * unmodified and in its entirety in all distributions of the software,
  12  * modified or unmodified, in source code or in binary form.
  13  *
  14  * Redistribution and use in source and binary forms, with or without
  15  * modification, are permitted provided that the following conditions are
  16  * met: redistributions of source code must retain the above copyright
  17  * notice, this list of conditions and the following disclaimer;
  18  * redistributions in binary form must reproduce the above copyright
  19  * notice, this list of conditions and the following disclaimer in the
  20  * documentation and/or other materials provided with the distribution;
  21  * neither the name of the copyright holders nor the names of its
  22  * contributors may be used to endorse or promote products derived from
  23  * this software without specific prior written permission.
  24  *
  25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  26  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  27  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  28  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  29  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  30  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  31  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  32  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  33  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  34  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  35  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  36  *
  37  * Authors: David Guillen Fandos
  38  */
  39
  40 #ifndef __SIM_LINEAR_SOLVER_HH__
  41 #define __SIM_LINEAR_SOLVER_HH__
  42
  43 #include <cassert>
  44 #include <sstream>
  45 #include <string>
  46 #include <vector>
  47
  48 /**
  49  * This class describes a linear equation with constant coefficients.
  50  * The equation has a certain (variable) number of unkowns and it can hold
  51  * N+1 coefficients.
  52  */
  53
  54 class LinearEquation {
  55   public:
  56     LinearEquation(unsigned unknowns) {
  57         eq = std::vector <double> (unknowns + 1, 0);
  58     }
  59
  60     // Add two equations
  61     LinearEquation operator+ (const LinearEquation& rhs) {
  62         assert(this->eq.size() == rhs.eq.size());
  63
  64         LinearEquation res(this->eq.size() - 1);
  65
  66         for (unsigned i = 0; i < res.eq.size(); i++)
  67             res.eq[i] = this->eq[i] + rhs.eq[i];
  68
  69         return res;
  70     }
  71
  72     // Multiply the equation by a constant
  73     LinearEquation & operator*= (const double cnt) {
  74         for (auto & c: eq)
  75             c *= cnt;
  76
  77         return *this;
  78     }
  79
  80     // Access a certain equation coefficient
  81     double & operator[] (unsigned unkw) {
  82         assert(unkw < eq.size());
  83         return eq[unkw];
  84     }
  85
  86     // Get a string representation
  87     std::string toStr() const {
  88         std::ostringstream oss;
  89         for (unsigned i = 0; i < eq.size(); i++) {
  90             if (i)
  91                 oss << " + ";
  92             oss << eq[i];
  93             if (i != eq.size() - 1)
  94                 oss << "*x" << i;
  95         }
  96         oss << " = 0";
  97         return oss.str();
  98     }
  99
 100     // Index for the constant term
 101     unsigned cnt() const { return eq.size() - 1; }
 102
 103   private:
 104
 105     /** Coefficients */
 106     std::vector <double> eq;
 107 };
 108
 109 class LinearSystem {
 110   public:
 111     LinearSystem(unsigned unknowns) {
 112         for (unsigned i = 0; i < unknowns; i++)
 113             matrix.push_back(LinearEquation(unknowns));
 114     }
 115
 116     LinearEquation & operator[] (unsigned eq) {
 117         assert(eq < matrix.size());
 118         return matrix[eq];
 119     }
 120
 121     std::string toStr() const {
 122         std::string r;
 123         for (auto & eq: matrix)
 124             r += eq.toStr() + "\n";
 125         return r;
 126     }
 127
 128     std::vector <double> solve() const;
 129
 130   private:
 131     std::vector < LinearEquation > matrix;
 132 };
 133
 134 #endif