A5: WIP

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
+};