Polymorphism

APM 50179 EP

Inheritance 


// In interpolation_impl.hpp

class interpolation_impl
{
  public:
};

class linear_interpolation : public interpolation_impl
{
};

class spline_interpolation : public interpolation_impl
{
};

Inheritance

  • Add a method interpolate to the interpolation_impl class.
  • This method should accept a double and return 0.
  • Uncomment the test_accessibility1 in main.cpp.
  • Uncomment the call to test_accessibility1 in main function.

Inheritance 


// intterpolation_impl.hpp
class interpolation_impl
{
  public:

    double interpolate(double x) const;
};


// interpolation_impl.cpp
double interpolation_impl::interpolate(double x) const
{
  return 0;
}

Inheritance

  • Add two members m_x and m_y of type std::vector<double> to the private section of interpolation_impl.
  • Add a constructor that accepts two vectors and initializes those data members.
  • Fix the constructor of the inheriting classes.
  • Use the get_test_spline_interpolation function in test_accessibility1 to fix the build.

Inheritance 


// interpolation_impl.hpp
class interpolation_impl
{
  public:

    interpolation_impl(const std::vector<double>& x,
    const std::vector<double>& y);

    double interpolate(double x) const;

  private:

    std::vector<double> m_x;
    std::vector<double> m_y;
};

class spline_interpolation : public interpolation_impl
{
  public:

    spline_interpolation(const std::vector<double>& x,
    const std::vector<double>& y);
};

Inheritance 


// interpolation_impl.cpp
interpolation_impl::interpolation_impl(const std::vector<double>& x,
const std::vector<double>& y)
: m_x(x)
, m_y(y)
{
}

spline_interpolation::spline_interpolation(const std::vector<double>& x,
const std::vector<double>& y)
: interpolation_impl(x, y)
{
}

Inheritance

  • Add a m_y2 vector member to the spline_interpolation class.
  • Initialize it in the constructor thanks to the spline_derivative method.
  • Try to use the data members of the mother class as arguments of spline_derivative.
  • What do you notice?

Inheritance 


// interpolation_impl.hpp
class spline_interpolation : public interpolation_impl
{
  public:

    spline_interpolation(const std::vector<double>& x,
    const std::vector<double>& y);

  private:

    std::vector<double> m_y2;
};
              

// interpolation_impl.cpp
spline_interpolation::spline_interpolation(const std::vector<double>& x,
const std::vector<double>& y)
: interpolation_impl(x, y)
, m_y2(x.size())
{
  spline_derivative(x, y, m_y2);       // OK
  //spline_derivative(m_x, m_y, m_y2); // Fails
}

Inheritance

  • public: access granted to everyone
  • private: access granted to class only
  • protected: access granted to class and inheriting classes

Avoid putting data in the protected section, prefer methods

Fix the interpolation_impl and spline_interpolation classes

Inheritance 


// interpolation_impl.hpp
class interpolation_impl
{
  public:

    interpolation_impl(const std::vector<double>& x,
    const std::vector<double>& y);

    double interpolate(double x) const;

  protected:

    const std::vector<double>& get_x() const;
    const std::vector<double>& get_y() const;

  private:

    std::vector<double> m_x;
    std::vector<double> m_y;
};

Inheritance 


// interpolation_impl.cpp
const std::vector<double>& interpolation_impl::get_x() const
{
  return m_x;
}

const std::vector<double>& interpolation_impl::get_y() const
{
  return m_y;
}

spline_interpolation::spline_interpolation(const std::vector<double>& x,
const std::vector<double>& y)
: interpolation_impl(x, y)
, m_y2(x.size())
{
  spline_derivative(get_x(), get_y(), m_y2);
}

Polymorphism

  • Override the interpolate method in the spline_interpolation class, it should return 1.
  • Uncomment the two test_polymorphism functions in main.cpp.
  • Uncomment the call to test_polymorphism from the main function.
  • Run the program.
  • What do you notice?

Polymorphism 


// inteprolation_impl.hpp
class spline_interpolation : public interpolation_impl
{
  public:

    spline_interpolation(const std::vector<double>& x,
    const std::vector<double>& y);

    double interpolate(double x) const;

  private:

    std::vector<double> m_y2;
};
              

// interpolation_impl.cpp
double spline_interpolation::interpolate(double x) const
{
  return 1.;
}

Polymorphism 


// interpolation_impl.hpp
class interpolation_impl
{
  public:

    interpolation_impl(const std::vector<double>& x,
    const std::vector<double>& y);

    virtual double interpolate(double x) const;

  // as before ...
};

Polymorphism

virtual

  • is not part of the signature,
  • implies each overload in inheriting classes is virtual too,
  • does not prevent to declare such overload as virtual,
  • does not force inheriting classes to declare such overload.

Polymorphism

Add a size_t argument to the overload method in spline_interpolation and run the program again:


// interpolation_impl.hpp
class spline_interpolation : public interpolation_impl
{
  public:

    spline_interpolation(const std::vector<double>& x,
    const std::vector<double>& y);

    // Defines a new method interpolate that is not an override of
    // interpolate declared in the base class
    double interpolate(double x, size_t i) const;

  // As before ...
};
                

// interpolation_impl.cpp
double spline_interpolation::interpolate(double x, size_t i) const
{
  return 1.;
}

Polymorphism 


// interpolation_impl.hpp
class spline_interpolation : public interpolation_impl
{
  public:

    spline_interpolation(const std::vector<double>& x,
    const std::vector<double>& y);

    // Error, no interpolate(double, size_t) declared in base class
    double interpolate(double x, size_t i) const override;
    // Ok, override interpolate(double) declared in base class
    double interpolate(double x) const override;

  // As before ...
};
  • Remove the size_t parameter in spline_interpolation::interpolate.
  • Use override to prevent future mistake.

Polymorphism

override

  • is not part of the signature,
  • requires the method to be declared in the base class with the same signature.

Polymorphism

  • Uncomment the get_test_interpolation function in main.cpp.
  • Remove the definition of interpolation_impl::interpolate from interpolation_impl.cpp.
  • Change the declaration of interpolation_impl::interpolate: 
    
// interpolation_impl.hpp
class interpolation_impl
{
  public:

    interpolation_impl(const std::vector<double>& x,
    const std::vector<double>& y);

    virtual double interpolate(double x) const = 0;

  // as before ...
};
  • Try to build.

Polymorphism

An abstract class

  • Has at least one pure virtual method.
  • Cannot be instantiated.
  • An inheriting class that does not implement all abstract methods is abstract.

Entity semantics

  • Add destructors to interpolation_impl and spline_interpolation.
  • Add logs (i.e. std::cout) in each constructor and destructor.
  • Uncomment the test_polymorphism1 function and its call in the main function.
  • Build and run.

Entity semantics 


// interpolation_impl.hpp
class interpolation_impl
{
  public:

    interpolation_impl(const std::vector<double>& x,
    const std::vector<double>& y);

    ~interpolation_impl();

  // ... as before
};

class spline_interpolation : public interpolation_impl
{
  public:

    spline_interpolation(const std::vector<double>& x,
    const std::vector<double>& y);

    ~spline_interpolation();

  // ... as before
};

Entity semantics 


// interpolation_impl.cpp
interpolation_impl::interpolation_impl(const std::vector<double>& x,
const std::vector<double>& y)
: m_x(x)
, m_y(y)
{
  std::cout << "interpolation_impl constructor" << std::endl;
}

interpolation_impl::~interpolation_impl()
{
  std::cout << "interpolation_impl destructor" << std::endl;
}

spline_interpolation::spline_interpolation(const std::vector<double>& x,
const std::vector<double>& y)
: interpolation_impl(x, y)
, m_y2(x.size())
{
  spline_derivative(get_x(), get_y(), m_y2);
  std::cout << "spline_interpolation constructor" << std::endl;
}

spline_interpolation::~splint_interpolation()
{
  std::cout << "spline_interplation destructor" << std::endl;
}

Entity semantics 


// interpolation_impl.hpp
class interpolation_impl
{
  public:

    interpolation_impl(const std::vector<double>& x,
    const std::vector<double>& y);

    virtual ~interpolation_impl();

  // ... as before
};

class spline_interpolation : public interpolation_impl
{
  public:

    spline_interpolation(const std::vector<double>& x,
    const std::vector<double>& y);

    virtual ~spline_interpolation();

  // ... as before
};

Entity semantics

  • Add a virtual method print to each class, that prints all the members.
  • You can use the print_vector function to implement it.
  • Uncomment the test_assign function and its call in main.
  • Build and run the program, what do you notice?

Entity semantics 


// interpolation_impl/hpp
class interpolation_impl
{
  public:

    virtual void print() const;
  // as before ...
};

class spline_interpolation : public interpolation_impl
{
  public:

    virtual void print() const;
  // as before ...
};
              

// interpolation_impl.cpp
void interpolation_impl::print() const
{
  print_vector("m_x", m_x);
  print_vector("m_y", m_y);
}

void spline_interpolation::print() const
{
  interpolation_impl::print();
  print_vector("m_y2", m_y2);
}

Entity semantics

  • Incomplete assignment due to inheritance is called slicing.
  • Constructors and assignment operators cannot be virtual.

Entity semantics 


class interpolation_impl
{
  public:

    interpolation_impl(const std::vector<double>& x,
    const std::vector<double>& y);
    virtual ~interpolation_impl() = default;

    interpolation_impl(const interpolation_impl&);
    interpolation_impl& operator=(const interpolation_impl&);
    interpolation_impl(interpolation_impl&&);
    interpolation_impl& operator=(interpolation_impl&&);
};

DON'T.DO.THAT

Entity semantics

Prevent users to call copy / move constructor / assign operator


class interpolation_impl
{
  public:

    interpolation_impl(const std::vector<double>& x,
    const std::vector<double>& y);
    virtual ~interpolation_impl() = default;

    interpolation_impl(const interpolation_impl&) = delete;
    interpolation_impl& operator=(const interpolation_impl&) = delete;
    interpolation_impl(interpolation_impl&&) = delete;
    interpolation_impl& operator=(interpolation_impl&&) = delete;

  // as before ...
};

Entity semantics

Prevent instantiation of base class


class interpolation_impl
{
  public:

    virtual ~interpolation_impl() = default;

    interpolation_impl(const interpolation_impl&) = delete;
    interpolation_impl& operator=(const interpolation_impl&) = delete;
    interpolation_impl(interpolation_impl&&) = delete;
    interpolation_impl& operator=(interpolation_impl&&) = delete;

  // as before ...

  protected:

    interpolation_impl(const std::vector<double>& x,
    const std::vector<double>& y);
};

Entity semantics

How to copy an instance of spline_interpolation


class interpolation_impl
{
  public:

  virtual interpolation_impl* clone() const = 0;
  // as before ...
};

class spline_interpolation : public interpolation_impl
{
  public:

  spline_interpolation* clone() const override;
};

Entity semantics 


spline_interplation* spline_interpolation::clone() const
{
  return new spline_interpolation(get_x(), get_y());
}
              

spline_interplation* spline_interpolation::clone() const
{
  // This actually needs the copy constructor
  return new spline_interpolation(*this);
}

Entity semantics 


class interpolation_impl
{
  public:

    virtual ~interpolation_impl() = default;

    interpolation_impl& operator=(const interpolation_impl&) = delete;
    interpolation_impl(interpolation_impl&&) = delete;
    interpolation_impl& operator=(interpolation_impl&&) = delete;

    virtual interpolation_impl* clone() const = 0;
    // as before ...

  protected:

    interpolation_impl(const std::vector<double>& x,
    const std::vector<double>& y);
    interpolation_impl(const interpolation_impl&);

    // as before ...
};

Entity semantics 


class spline_interpolation : public interpolation_impl
{
  public:

    spline_interpolation(const std::vector<double>& x,
    const std::vector<double>& y);
    virtual ~spline_interpolation();

    spline_interpolation* clone() const override;

    // as before ...

  protected:

    spline_interpolation(const spline_interpolation&);

    // as before ...
};

Entity semantics 


interpolation_impl::interpolation_impl(const interpolation_impl& rhs)
: m_x(rhs.m_x)
, m_y(rhs.m_y)
{
}

spline_interpolation::spline_interpolation(const spline_interpolation& rhs)
: interpolation_imp(rhs)
, m_y2(rhs.m_y2)
{
}

spline_interpolation* spline_interpolation::clone() const
{
  return new spline_interpolation(*this);
}

Design principles

  • B should inherit from A if B is a kind of A
  • B should inherit from A if there exists an "is-a" relation between A and B

That's WRONG

  • B should inherit from A if B behaves like A in the context of your program
  • B should inherit from A if you want A to be substitutable

Design principles

Liskov Substitution Principle (LSP)

If S is a subtype of T, then objects of type T in a program may be replaced with objects of type S without altering any of the desirable property of the propgram

Design principles 


class rectangle : public drawable
{
  public:

    virtual ~rectangle();
    virtual vod draw(canvas&) const;
    virtual void resize(size_t length, size_t width);
};

Should square inherit from rectangle?

Design principles 


class square: public rectangle
{
  public:

    virtual ~square();
    virtual vod draw(canvas&) const;
    virtual void resize(size_t length, size_t width); // ??
};

square should NOT inherit from rectangle

Design principles

Non virtual interface


class interpolation
{
  public:

    double interplate(double x) const;

  private:

    virtual double interpolate_impl(double x) const = 0;
};
              

double interpolation::interpolate(double x) const
{
  // add code that should be executed before any call to
  // interpolate_impl, whatever the inheriting class is.
  double res = interpolate_impl(x);
  // add code that should be executed after any call to
  // interpolate_impl, whatever the inheriting class is.
  return res;
}

Design principles

Template method (pattern)


class algo
{
  public:

    void run();

  private:

    virtual void first_step();
    virtual void second_step();
    virtual void third_step();
};
              

void algo::run()
{
  first_step();
  second_step();
  third_step();
}

non virtual interface

Implement a find_upper_bound method in interpolation_impl that:

  • returns the index of the abscissa greater than or equal to its argument,
  • throws an exception if the argument if out of the abscissa bounds.

non virtual interface 


class interpolation_impl
{
  protected:

    size_t find_upper_bound(double x) const;

  // as before ...
};
              

size_t interpolation_impl::find_upper_bound(double x) const
{
  if (x < m_x.front() || x > m_x.back())
  {
    throw std::runtime_error("x out of bounds");
  }
  auto iter = std::upper_bound(m_x.cbegin(), m_x.cend(), x);
  size_t index = static_cast<size_t>( iter - m_x.cbegin());
  return index;
}

non virtual interface

Implement the interpolate method of spline_interpolation:

  • use the find_upper_bound method previously defined,
  • use the spline_interpolate function provided in interpolation_impl.hpp.

double spline_interpolation::interpolate(double x) const
{
  size_t upper_bound = find_upper_bound(x);
  return spline_interpolate(get_x()[upper_bound-1], get_x()[upper_bound],
  get_y()[upper_bound-1], get_y()[upper_bound],
  m_y2[upper_bound-1], m_y2[upper_boud],
  x);
}

What is the issue with this implementation?

non virtual interface

Refactor the implementation to avoid code duplication when adding other interpolation methods:

  • Rename the current interpolate method into interpolate_impl.
  • interpolate_impl should be private and take the result of find_upper_bound as a additional parameter.
  • Add an interpolate method that acts as a NVI / template method.

non virtual interface 


class interpolation_impl
{
  public:

    // Not virtual anymore
    double interpolate(double x) const;

  private:

    size_t find_upper_bound(double x) const;
    virtual double interpolate_impl(double x, size_t upper_bound) const  = 0;

    // as before ...
};
              

class spline_interpolation : public interpolation_impl
{
  private:

    double interpolate_impl(double x, size_t upper_bound) const override;

    // as before ...
};

non virtual interface 


double interpolation_impl::interpolate(double x) const
{
  size_t upper_bound = find_upper_bound(x);
  return interpolate_impl(x, upper_bound);
}

double spline_interpolation::interpolate_impl(double x, size_t upper_bound) const
{
  return spline_interpolate(get_x()[upper_bound-1], get_x()[upper_bound],
  get_y()[upper_bound-1], get_y()[upper_bound],
  m_y2[upper_bound-1], m_y2[upper_boud],
  x);
}

Private inheritance 


class my_vector : public std::vector<double>
{
  public:

    explicit my_vector(const std::string& name);
    ~my_vector();

  private:

    std::string m_name;
};

DON'T.DO.THAT.

Private inheritance 


class my_vector
{
  public:

    double& operator[](size_t i) { return m_data[i]; }
    const double & operator[](size_t i) const { return m_data[i]; }
    // etc ...

  private:

    std::vector<double> m_data;
    std::string m_name;
};

Private inheritance 


class my_vector : private std::vector<double>
{
  public:

    using base_type = std::vector<doubl>

    using base_type::size;
    using base_type::empty;
    using base_type::operator[];

  private:

    std::vector<double> m_data;
    std::string m_name;
};

Private inheritance

If B is a private base of D:

  • All methods of B are private in D.
  • You cannot assign a D* to a B*.
  • Previous statements are not true for friend classes / functions.
  • D can only access public and protected sections of B.

Multiple inheritance 


class implementation : public interface1, public interface2
{
  public:

    virtual ~implementation() = default;
};
              

class root {};

class interface1 : public root {};
class interface2 : public root {};

// The following is problematic
class implementation : public interface1, public interface2 {}

Private implementation / enveloppe

Add a make_interpolation free function that:

  • takes two vectors and a enum parameter to choose the type of interpolation,
  • returns a unique pointer holding an interpolation_impl.

Private implementation / enveloppe 


// interpolation_impl.hpp
enum class interpolation_type
{
  linear,
  spline
};

using interpolation_ptr = std::unique_ptr<interpolation_impl>
interpolation_ptr make_interpolation(const std::vector<double>& x,
const std::vector<double>& y,
interplation_type it);
              

// interpolation_impl.cpp
interpolation_ptr make_interpolation(const std::vector<double>& x,
const std::vector<double>& y,
interplation_type it)
{
  switch(it)
  {
    case linear:
    return std::make_unique<linear_interpolation>(x, y);
    clase spline:
    return std::make_unique<spline_interpolation>(x, y);
    default:
    return std::make_unique<linear_interpolation>(x, y);
  }
}

Private implementation / enveloppe

Add an interpolation class that:

  • Holds a pointer to interpolation_impl.
  • Implements the value semantics.
  • Has an interpolate method that forwards the call to interpolation_impl.
  • Its constructor takes an enum parameter to choose the interpolation type.

Private implementation / enveloppe 


// interpolation.hpp
class interpolation
{
  public:

    interpolation(const std::vector<double>& x,
    const std::vector<double>& y,
    interpolation_type it);
    ~inteopolation_type() = default;

    interpolation(const interpolation&);
    interpolation& operator=(const interpolation&);

    interpolation(interpolation&&) = default;
    interpolation& operator=(interpolation&&) = default;

    double interpolate(double x) const;

  private:

    inteprolation_ptr p_impl;
};

Private implementation / enveloppe 


// interpolation.cpp
interpolation::interpolation(const std::vector<double>& x,
const std::vector<double>& y,
interpolation_type it)
: p_impl(make_interpolation(x, y, it);
{
}
interpolation::interpolation(const interpolation& rhs)
: p_impl(rhs.p_impl->clone())
{
}

interpolation& interpolation::operator=(const interpolation& rhs)
{
  interpolation_impl tmp = rhs.p_impl->clone();
  std::swap(tmp, p_impl);
  return *this;
}

double interpolation::interpolate(double x) const
{
  return p_impl->interpolate(x);
}

ODE Solver

You now have a good understanding of the concepts related to polymorphism and the C++ programming technique called Pimpl.

A colleague comes to you and says that he wants to build a user-friendly interface for his ODE solvers.

At the moment he has only two methods: explicit Euler and Runge-Kutta 2. But he hopes that with your help he will be able to add many more.

ODE Solver

The first application he has in mind is to solve the well-known Lorenz equations given by $$ \left\{ \begin{array}{l} \frac{dx}{dt} = \sigma(y-x), \\\\ \frac{dy}{dt} = x(\rho-z)-y, \\\\ \frac{dz}{dt} = xy-\beta z. \end{array} \right. $$

ODE API: usage example 


double T = 50, t = 0;
std::size_t nite = 20000;
double dt = T/nite;

Lorenz lo(28, 10, 8./3);
std::vector<double> x0{5, -8, 6};

ODE ode(x0, lo, method::euler);

for(std::size_t i = 0; i < nite; ++i)
{
  ode.one_step(t, dt);
  ode.print_sol();
  t += dt;
}

ODE API: Lorenz class 


class Lorenz
{
  public:

    Lorenz(double rho, double sigma, double beta)
    : m_rho(rho)
    , m_sigma(sigma)
    , m_beta(beta)
    {}

    std::vector<double> operator()(double t, const std::vector<double>& x) const
    {
      return {
        m_sigma*(x[1] - x[0]),
        x[0]*(m_rho - x[2]) - x[1],
        x[0]*x[1] - m_beta*x[2]
      };
    }

  private:

    double m_rho;
    double m_sigma;
    double m_beta;
};

Reminder

The Euler method is

$$ y_{n+1} = y_n + \Delta t f(t_n, y_n). $$

The Runge-Kutta method of order $2$ is

$$ y_{n+1} = y_n + \Delta t f\left(t_n + \frac{\Delta t}{2}, y_n + \frac{\Delta t}{2}f(t_n, y_n)\right). $$