diff options
| -rw-r--r-- | Makefile | 10 | ||||
| -rw-r--r-- | a5/Makefile | 4 | ||||
| -rw-r--r-- | a5/exercise.tex | 63 | ||||
| -rw-r--r-- | a5/imatrix.h | 204 | ||||
| -rw-r--r-- | a5/imatrix_nm.h | 182 | ||||
| -rw-r--r-- | a5/matrix.cc | 27 | ||||
| -rw-r--r-- | a5/matrix.h | 182 |
7 files changed, 671 insertions, 1 deletions
@@ -1,5 +1,5 @@ PRE=au_BentBisballeNyeng_ -all: A4 Tour3_Log +all: A5 Tour3_Log A1: zip ${PRE}$@.zip a1/hello.cc @@ -35,6 +35,14 @@ A4: a4/insert.pdf a4/insert-padded.pdf a4/remove.pdf a4/remove-padded.pdf xelatex -halt-on-error -jobname=${PRE}$@ a4/exercise.tex rm -f ${PRE}$@.aux ${PRE}$@.log +A5: + zip ${PRE}$@.zip a5/Makefile + zip ${PRE}$@.zip a5/*.cc + zip ${PRE}$@.zip a5/*.h + xelatex -halt-on-error -jobname=${PRE}$@ a5/exercise.tex + xelatex -halt-on-error -jobname=${PRE}$@ a5/exercise.tex + rm -f ${PRE}$@.aux ${PRE}$@.log + Tour3_Log: xelatex -halt-on-error -jobname=${PRE}$@ tour3_log/tour3_log.tex rm -f ${PRE}$@.aux ${PRE}$@.log 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 +}; |