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
  38 #ifndef __SIM_LINEAR_SOLVER_HH__
  39 #define __SIM_LINEAR_SOLVER_HH__
  40
  41 #include <cassert>
  42 #include <sstream>
  43 #include <string>
  44 #include <vector>
  45
  46 /**
  47  * This class describes a linear equation with constant coefficients.
  48  * The equation has a certain (variable) number of unkowns and it can hold
  49  * N+1 coefficients.
  50  */
  51
  52 class LinearEquation {
  53   public:
  54     LinearEquation(unsigned unknowns) {
  55         eq = std::vector <double> (unknowns + 1, 0);
  56     }
  57
  58     // Add two equations
  59     LinearEquation operator+ (const LinearEquation& rhs) {
  60         assert(this->eq.size() == rhs.eq.size());
  61
  62         LinearEquation res(this->eq.size() - 1);
  63
  64         for (unsigned i = 0; i < res.eq.size(); i++)
  65             res.eq[i] = this->eq[i] + rhs.eq[i];
  66
  67         return res;
  68     }
  69
  70     // Multiply the equation by a constant
  71     LinearEquation & operator*= (const double cnt) {
  72         for (auto & c: eq)
  73             c *= cnt;
  74
  75         return *this;
  76     }
  77
  78     // Access a certain equation coefficient
  79     double & operator[] (unsigned unkw) {
  80         assert(unkw < eq.size());
  81         return eq[unkw];
  82     }
  83
  84     // Get a string representation
  85     std::string toStr() const {
  86         std::ostringstream oss;
  87         for (unsigned i = 0; i < eq.size(); i++) {
  88             if (i)
  89                 oss << " + ";
  90             oss << eq[i];
  91             if (i != eq.size() - 1)
  92                 oss << "*x" << i;
  93         }
  94         oss << " = 0";
  95         return oss.str();
  96     }
  97
  98     // Index for the constant term
  99     unsigned cnt() const { return eq.size() - 1; }
 100
 101   private:
 102
 103     /** Coefficients */
 104     std::vector <double> eq;
 105 };
 106
 107 class LinearSystem {
 108   public:
 109     LinearSystem(unsigned unknowns) {
 110         for (unsigned i = 0; i < unknowns; i++)
 111             matrix.push_back(LinearEquation(unknowns));
 112     }
 113
 114     LinearEquation & operator[] (unsigned eq) {
 115         assert(eq < matrix.size());
 116         return matrix[eq];
 117     }
 118
 119     std::string toStr() const {
 120         std::string r;
 121         for (auto & eq: matrix)
 122             r += eq.toStr() + "\n";
 123         return r;
 124     }
 125
 126     std::vector <double> solve() const;
 127
 128   private:
 129     std::vector < LinearEquation > matrix;
 130 };
 131
 132 #endif