summaryrefslogtreecommitdiff
path: root/a5
diff options
context:
space:
mode:
authorBent Bisballe Nyeng <deva@aasimon.org>2023-08-03 08:06:18 +0200
committerBent Bisballe Nyeng <deva@aasimon.org>2023-08-03 08:06:18 +0200
commitd8fea7f2b4abda430ebfe65aa65002cab2e9ce42 (patch)
tree41075b16543f9dcf3af200bdc0f26571c7e83f1f /a5
parentab7c4c2c2ccf7809e84df4a67dd55eb949f5a780 (diff)
A5: WIP
Diffstat (limited to 'a5')
-rw-r--r--a5/Makefile4
-rw-r--r--a5/exercise.tex63
-rw-r--r--a5/imatrix.h204
-rw-r--r--a5/imatrix_nm.h182
-rw-r--r--a5/matrix.cc27
-rw-r--r--a5/matrix.h182
6 files changed, 662 insertions, 0 deletions
diff --git a/a5/Makefile b/a5/Makefile
new file mode 100644
index 0000000..282dfa9
--- /dev/null
+++ b/a5/Makefile
@@ -0,0 +1,4 @@
+all: matrix
+
+matrix: matrix.cc Makefile imatrix.h imatrix_nm.h matrix.h
+ g++ -O2 -Wall -Werror -Wextra -Wconversion -std=c++20 $< -o $@
diff --git a/a5/exercise.tex b/a5/exercise.tex
new file mode 100644
index 0000000..6889950
--- /dev/null
+++ b/a5/exercise.tex
@@ -0,0 +1,63 @@
+\title{A5: Generic Programming}
+\input{preamble.tex}
+
+I decided to use std container for the elements of the matrix and
+initially went with \texttt{std::vector<int>}. But since we were going
+to do arithmentics on the data, and no requirements were made as to
+the arithmentics actually being those of a real matrix, I figure why
+not use \texttt{std::valarray<int>} and have all arithmentic
+operations be per-entry, re-suing the behaviour of
+\texttt{std::valarray} directly.
+
+In the change I discovered that \texttt{std::valarray} and
+\texttt{std::vector} ctor args for creating with a size and a default
+value for all items are reversed, which would not be caught by the
+compiler with both of them being integral:
+\footnotesize\begin{lstlisting}[language=C++]
+explicit vector( size_type count,
+ const T& value = T(),
+ const Allocator& alloc = Allocator() );
+
+valarray( const T& val, std::size_t count );
+\end{lstlisting}\normalsize
+That, I think, is rather unfortunate.
+
+When using a std container, all memory managing is handled by the
+container, even when throwing an exception inside the constructor, so
+no need to do anything clever inside the matrix implementation itself.
+
+I first wrote the entire \texttt{Imatrix} class with the values
+dynamically allocated inside the \texttt{std::valarray} but wanted to
+explore having the matrix dimenions available at compile-time
+(matrices doesn't have the habit of changing their sizes dynamically,
+so they should be checkable at compile-time). I did this with template
+size arguments.
+
+This removed a lot of error checks on matrix dimension matching, which
+is part of the type itself - nice!
+
+It also removed the need for the two integer members carrying the
+width and height - we now also saved 16 bytes of memory!
+
+... and we get a compile error if for example we try multiplying two
+matrices where their dimensions doesn't adhere to the algebraic rules!
+
+Final step is to templatize the underlying typeof the matrix. Done so
+by simply replacing int with T and all the places where 0 is assigned
+to the value type, replacing it with the default value T{}
+
+When instantiating a template only the required/used functions are
+generated (or so it appears).
+In other words, I can instante a \texttt{Matrix<Chess\_piece,2,2> c1}
+without getting any compile errors because I don't actually call
+anything on it.
+If I add a \texttt{c1 + 1} somewhere it will complain about not being
+able to add, but not any of the other unused operations.
+When adding the requirements of concepts, I will get errors for all
+the uses, not just the ones I use. In other words, concepts might end
+up requirering more work to be done by a developer than strictly
+needed. This I think is actually not that good.
+Adding the requirement to each of the member functions might be
+better.
+
+\end{document}
diff --git a/a5/imatrix.h b/a5/imatrix.h
new file mode 100644
index 0000000..f96cb0c
--- /dev/null
+++ b/a5/imatrix.h
@@ -0,0 +1,204 @@
+// -*- c++ -*-
+#pragma once
+
+#include <utility>
+#include <valarray>
+#include <stdexcept>
+
+class Imatrix
+{
+public:
+ Imatrix() = default;
+
+ explicit Imatrix(std::size_t w, std::size_t h)
+ : data(0, w * h)
+ , w(w)
+ , h(h)
+ {
+ }
+
+ Imatrix(Imatrix&& other)
+ {
+ *this = std::move(other);
+ }
+
+ Imatrix(const Imatrix& other)
+ {
+ *this = other;
+ }
+
+ Imatrix& operator=(Imatrix&& other)
+ {
+ w = other.w;
+ other.w = 0;
+ h = other.h;
+ other.h = 0;
+ data = std::move(other.data);
+ return *this;
+ }
+
+ Imatrix& operator=(const Imatrix& other)
+ {
+ w = other.w;
+ h = other.h;
+ data = other.data;
+ return *this;
+ }
+
+ int& m(std::size_t x, std::size_t y)
+ {
+ if(x >= w || y >= h) throw std::out_of_range("Subscript out of range.");
+ return data[x + y * w];
+ }
+
+ const int& m(std::size_t x, std::size_t y) const
+ {
+ if(x >= w || y >= h) throw std::out_of_range("Subscript out of range.");
+ return data[x + y * w];
+ }
+
+
+ Imatrix operator+(const Imatrix& other) const
+ {
+ if(w != other.w || h != other.h)
+ throw std::invalid_argument("Dimension mismatch");
+ Imatrix m(*this);
+ m.data += other.data;
+ return m;
+ }
+
+ Imatrix operator+(int val) const
+ {
+ Imatrix m(*this);
+ m.data += val;
+ return m;
+ }
+
+ Imatrix operator-(const Imatrix& other) const
+ {
+ if(w != other.w || h != other.h)
+ throw std::invalid_argument("Dimension mismatch");
+ Imatrix m(*this);
+ m.data -= other.data;
+ return m;
+ }
+
+ Imatrix operator-(int val)
+ {
+ Imatrix m(*this);
+ m.data -= val;
+ return m;
+ }
+
+ Imatrix operator%(const Imatrix& other) const
+ {
+ if(w != other.w || h != other.h)
+ throw std::invalid_argument("Dimension mismatch");
+ Imatrix m(*this);
+ m.data %= other.data;
+ return m;
+ }
+
+ Imatrix operator%(int val) const
+ {
+ Imatrix m(*this);
+ m.data %= val;
+ return m;
+ }
+
+ Imatrix operator*(const Imatrix& other) const
+ {
+ if(w != other.h || h != other.w)
+ throw std::invalid_argument("Dimension mismatch");
+
+ Imatrix out(w, other.h);
+ for(std::size_t i = 0; i < w; ++i)
+ {
+ for(std::size_t j = 0; j < other.h; ++j)
+ {
+ out.m(i,j) = 0;
+ for(std::size_t k = 0; k < other.w; ++k)
+ {
+ out.m(i,j) += m(i, j) * other.m(k, j);
+ }
+ }
+ }
+
+ return out;
+ }
+
+ Imatrix operator*(int val) const
+ {
+ Imatrix m(*this);
+ m.data *= val;
+ return m;
+ }
+
+ Imatrix operator/(const Imatrix& other) const
+ {
+ if(w != other.h || h != other.w)
+ throw std::invalid_argument("Dimension mismatch");
+
+ Imatrix out(w, other.h);
+ for(std::size_t i = 0; i < w; ++i)
+ {
+ for(std::size_t j = 0; j < other.h; ++j)
+ {
+ out.m(i,j) = 0;
+ for(std::size_t k = 0; k < other.w; ++k)
+ {
+ out.m(i,j) += m(i, j) / other.m(k, j);
+ }
+ }
+ }
+
+ return out;
+ }
+
+ Imatrix operator/(int val) const
+ {
+ Imatrix m(*this);
+ m.data /= val;
+ return m;
+ }
+
+ struct pos_t
+ {
+ std::size_t x;
+ std::size_t y;
+ };
+
+ void Move(pos_t from, pos_t to)
+ {
+ m(to.x, to.x) = m(from.x, from.x);
+ m(from.x, from.y) = 0;
+ }
+
+ std::vector<int> Row(std::size_t n) const
+ {
+ if(n >= h) throw std::out_of_range("Subscript out of range.");
+ std::vector<int> out;
+ for(std::size_t x = 0; x < w; ++x)
+ {
+ out.push_back(m(x, n));
+ }
+ return out;
+ }
+
+ std::vector<int> Column(std::size_t n) const
+ {
+ if(n >= w) throw std::out_of_range("Subscript out of range.");
+ std::vector<int> out;
+ for(std::size_t y = 0; y < h; ++y)
+ {
+ out.push_back(m(n, y));
+ }
+ return out;
+ }
+
+private:
+ // Invariant; at all times data contains w * h initialized data members
+ std::valarray<int> data; // default initialized to empty
+ std::size_t w{}; // default initialized to 0
+ std::size_t h{}; // default initialized to 0
+};
diff --git a/a5/imatrix_nm.h b/a5/imatrix_nm.h
new file mode 100644
index 0000000..970031a
--- /dev/null
+++ b/a5/imatrix_nm.h
@@ -0,0 +1,182 @@
+// -*- c++ -*-
+#pragma once
+
+#include <utility>
+#include <valarray>
+#include <stdexcept>
+
+template<std::size_t W, std::size_t H>
+class ImatrixNM
+{
+public:
+ ImatrixNM()
+ : data(0, W * H)
+ {
+ }
+
+ ImatrixNM(ImatrixNM<W, H>&& other)
+ {
+ *this = std::move(other);
+ }
+
+ ImatrixNM(const ImatrixNM<W, H>& other)
+ {
+ *this = other;
+ }
+
+ ImatrixNM& operator=(ImatrixNM<W, H>&& other)
+ {
+ data = std::move(other.data);
+ return *this;
+ }
+
+ ImatrixNM& operator=(const ImatrixNM<W, H>& other)
+ {
+ data = other.data;
+ return *this;
+ }
+
+ int& m(std::size_t x, std::size_t y)
+ {
+ if(x >= W || y >= H) throw std::out_of_range("Subscript out of range.");
+ return data[x + y * W];
+ }
+
+ const int& m(std::size_t x, std::size_t y) const
+ {
+ if(x >= W || y >= H) throw std::out_of_range("Subscript out of range.");
+ return data[x + y * W];
+ }
+
+ ImatrixNM<W, H> operator+(const ImatrixNM<W, H>& other) const
+ {
+ ImatrixNM m(*this);
+ m.data += other.data;
+ return m;
+ }
+
+ ImatrixNM<W, H> operator+(int val)
+ {
+ ImatrixNM<W, H> m(*this);
+ m.data += val;
+ return m;
+ }
+
+ ImatrixNM<W, H> operator-(const ImatrixNM<W, H>& other) const
+ {
+ ImatrixNM<W, H> m(*this);
+ m.data -= other.data;
+ return m;
+ }
+
+ ImatrixNM <W, H>operator-(int val)
+ {
+ ImatrixNM<W, H> m(*this);
+ m.data -= val;
+ return m;
+ }
+
+ ImatrixNM<W, H> operator%(const ImatrixNM<W, H>& other) const
+ {
+ ImatrixNM<W, H> m(*this);
+ m.data %= other.data;
+ return m;
+ }
+
+ ImatrixNM<W, H> operator%(int val)
+ {
+ ImatrixNM m(*this);
+ m.data %= val;
+ return m;
+ }
+
+ template<std::size_t N>
+ ImatrixNM<W, N> operator*(const ImatrixNM<H, N>& other) const
+ {
+ ImatrixNM<W, N> out;
+ for(std::size_t i = 0; i < W; ++i)
+ {
+ for(std::size_t j = 0; j < N; ++j)
+ {
+ out.m(i,j) = 0;
+ for(std::size_t k = 0; k < H; ++k)
+ {
+ out.m(i,j) += m(i, j) * other.m(k, j);
+ }
+ }
+ }
+
+ return out;
+ }
+
+ ImatrixNM<W, H> operator*(int val) const
+ {
+ ImatrixNM<W, H> m(*this);
+ m.data *= val;
+ return m;
+ }
+
+ template<std::size_t N>
+ ImatrixNM<W, N> operator/(const ImatrixNM<H, N>& other) const
+ {
+ ImatrixNM<W, N> out;
+ for(std::size_t i = 0; i < W; ++i)
+ {
+ for(std::size_t j = 0; j < N; ++j)
+ {
+ out.m(i,j) = 0;
+ for(std::size_t k = 0; k < H; ++k)
+ {
+ out.m(i,j) += m(i, j) / other.m(k, j);
+ }
+ }
+ }
+
+ return out;
+ }
+
+ ImatrixNM<W, H> operator/(int val) const
+ {
+ ImatrixNM<W, H> m(*this);
+ m.data /= val;
+ return m;
+ }
+
+ struct pos_t
+ {
+ std::size_t x;
+ std::size_t y;
+ };
+
+ void Move(pos_t from, pos_t to)
+ {
+ m(to.x, to.x) = m(from.x, from.x);
+ m(from.x, from.y) = 0;
+ }
+
+ std::vector<int> Row(std::size_t n) const
+ {
+ if(n >= H) throw std::out_of_range("Subscript out of range.");
+ std::vector<int> out;
+ for(std::size_t x = 0; x < W; ++x)
+ {
+ out.push_back(m(x, n));
+ }
+ return out;
+ }
+
+ std::vector<int> Column(std::size_t n) const
+ {
+ if(n >= W) throw std::out_of_range("Subscript out of range.");
+ std::vector<int> out;
+ for(std::size_t y = 0; y < H; ++y)
+ {
+ out.push_back(m(n, y));
+ }
+ return out;
+ }
+
+private:
+ // Invariant; at all times data contains w * h initialized data members
+ std::valarray<int> data; // default initialized to empty
+};
diff --git a/a5/matrix.cc b/a5/matrix.cc
new file mode 100644
index 0000000..01744fa
--- /dev/null
+++ b/a5/matrix.cc
@@ -0,0 +1,27 @@
+#include "imatrix.h"
+#include "imatrix_nm.h"
+#include "matrix.h"
+
+struct Chess_piece
+{
+};
+
+int main()
+{
+ Matrix<double, 3, 5> m1;
+ m1 = m1 + 2;
+ m1.m(2,2) = 42;
+ try
+ {
+ m1.m(6,6) = 0;
+ }
+ catch(...)
+ {
+ // expected
+ }
+ Matrix<double, 5, 2> m2;
+ auto m3 = m1 * m2;
+
+ Matrix<Chess_piece, 2, 2> c1;
+ auto c2 = c1 + 42;
+}
diff --git a/a5/matrix.h b/a5/matrix.h
new file mode 100644
index 0000000..af83683
--- /dev/null
+++ b/a5/matrix.h
@@ -0,0 +1,182 @@
+// -*- c++ -*-
+#pragma once
+
+#include <utility>
+#include <valarray>
+#include <stdexcept>
+
+template<typename T, std::size_t W, std::size_t H>
+class Matrix
+{
+public:
+ Matrix()
+ : data(T{}, W * H)
+ {
+ }
+
+ Matrix(Matrix<T, W, H>&& other)
+ {
+ *this = std::move(other);
+ }
+
+ Matrix(const Matrix<T, W, H>& other)
+ {
+ *this = other;
+ }
+
+ Matrix& operator=(Matrix<T, W, H>&& other)
+ {
+ data = std::move(other.data);
+ return *this;
+ }
+
+ Matrix& operator=(const Matrix<T, W, H>& other)
+ {
+ data = other.data;
+ return *this;
+ }
+
+ T& m(std::size_t x, std::size_t y)
+ {
+ if(x >= W || y >= H) throw std::out_of_range("Subscript out of range.");
+ return data[x + y * W];
+ }
+
+ const T& m(std::size_t x, std::size_t y) const
+ {
+ if(x >= W || y >= H) throw std::out_of_range("Subscript out of range.");
+ return data[x + y * W];
+ }
+
+ Matrix<T, W, H> operator+(const Matrix<T, W, H>& other) const
+ {
+ Matrix m(*this);
+ m.data += other.data;
+ return m;
+ }
+
+ Matrix<T, W, H> operator+(T val)
+ {
+ Matrix<T, W, H> m(*this);
+ m.data += val;
+ return m;
+ }
+
+ Matrix<T, W, H> operator-(const Matrix<T, W, H>& other) const
+ {
+ Matrix<T, W, H> m(*this);
+ m.data -= other.data;
+ return m;
+ }
+
+ Matrix <T, W, H>operator-(T val)
+ {
+ Matrix<T, W, H> m(*this);
+ m.data -= val;
+ return m;
+ }
+
+ Matrix<T, W, H> operator%(const Matrix<T, W, H>& other) const
+ {
+ Matrix<T, W, H> m(*this);
+ m.data %= other.data;
+ return m;
+ }
+
+ Matrix<T, W, H> operator%(T val)
+ {
+ Matrix m(*this);
+ m.data %= val;
+ return m;
+ }
+
+ template<std::size_t N>
+ Matrix<T, W, N> operator*(const Matrix<T, H, N>& other) const
+ {
+ Matrix<T, W, N> out;
+ for(std::size_t i = 0; i < W; ++i)
+ {
+ for(std::size_t j = 0; j < N; ++j)
+ {
+ out.m(i,j) = {};
+ for(std::size_t k = 0; k < H; ++k)
+ {
+ out.m(i,j) += m(i, j) * other.m(k, j);
+ }
+ }
+ }
+
+ return out;
+ }
+
+ Matrix<T, W, H> operator*(T val)
+ {
+ Matrix<T, W, H> m(*this);
+ m.data *= val;
+ return m;
+ }
+
+ template<std::size_t N>
+ Matrix<T, W, N> operator/(const Matrix<T, H, N>& other) const
+ {
+ Matrix<T, W, N> out;
+ for(std::size_t i = 0; i < W; ++i)
+ {
+ for(std::size_t j = 0; j < N; ++j)
+ {
+ out.m(i,j) = {};
+ for(std::size_t k = 0; k < H; ++k)
+ {
+ out.m(i,j) += m(i, j) / other.m(k, j);
+ }
+ }
+ }
+
+ return out;
+ }
+
+ Matrix<T, W, H> operator/(T val) const
+ {
+ Matrix<T, W, H> m(*this);
+ m.data /= val;
+ return m;
+ }
+
+ struct pos_t
+ {
+ std::size_t x;
+ std::size_t y;
+ };
+
+ void Move(pos_t from, pos_t to)
+ {
+ m(to.x, to.x) = m(from.x, from.x);
+ m(from.x, from.y) = {};
+ }
+
+ std::vector<T> Row(std::size_t n) const
+ {
+ if(n >= H) throw std::out_of_range("Subscript out of range.");
+ std::vector<T> out;
+ for(std::size_t x = 0; x < W; ++x)
+ {
+ out.push_back(m(x, n));
+ }
+ return out;
+ }
+
+ std::vector<T> Column(std::size_t n) const
+ {
+ if(n >= W) throw std::out_of_range("Subscript out of range.");
+ std::vector<T> out;
+ for(std::size_t y = 0; y < H; ++y)
+ {
+ out.push_back(m(n, y));
+ }
+ return out;
+ }
+
+private:
+ // Invariant; at all times data contains w * h initialized data members
+ std::valarray<T> data; // default initialized to empty
+};