Reusable Code, Reusable Data Structures

Sebastian Theophil
stheophil@think-cell.com

Why this talk?
🛑
🔷
⚠️

// https://github.com/think-cell/think-cell-library
void vertical_center(WidgetContainer const& c) {
	auto rects = tc::make_vector(tc::transform(c, 
		[](widget const& w) { return w.bounding_box(); }
	));
	// 🧙 Magic happens
	tc::for_each(tc::zip(c, rects),
		[&](widget& w, rect r) { 
			widget.place(r);
		}
	);
}
🌇
🏙️
🌁

// https://github.com/think-cell/think-cell-library
void vertical_center(WidgetContainer const& c) {
	auto rects = tc::make_vector(tc::transform(c, 
		[](widget const& w) { return w.bounding_box(); }
	));
	// 🧙 Magic happens
	tc::for_each(tc::zip(c, rects),
		[&](widget& w, rect r) { 
			widget.place(r);
		}
	);
}
🌇
🏙️
🌁

// https://github.com/think-cell/think-cell-library
void vertical_center(WidgetContainer const& c) {
	auto rects = tc::make_vector(tc::transform(c, 
		[](widget const& w) { return w.bounding_box(); }
	));
	// 🧙 Magic happens
	tc::for_each(tc::zip(c, rects),
		[&](widget& w, rect r) { 
			widget.place(r);
		}
	);
}

void center_bitmaps() {
	std::array<bitmap, 3> = {🌇, 🏙️, 🌁};
	// What now?
}
	

void vertical_center(WidgetContainer const& c) {
	// 🧙 Magic happens
}

void center_bitmaps() {
	std::array<bitmap, 3> = {🌇, 🏙️, 🌁};
	// What now?
}
	

struct widget {
	rect bounding_box();
	void place(rect r);
};

struct bitmap {
	std::array<std::byte, N> data;
	int width, height;
};

void vertical_center(WidgetContainer const& c) {
	// 🧙 Magic happens
}

void center_bitmaps() {
	std::array<bitmap, 3> = {🌇, 🏙️, 🌁};
	// What now?
}
	

struct widget {
	rect bounding_box();
	void place(rect r);
};

struct bitmap {
	std::array<std::byte, N> data;
	int width, height;
};

void vertical_center(auto const& c) {
	// 🧙 Magic happens
}

void center_bitmaps() {
	std::array<bitmap, 3> = {🌇, 🏙️, 🌁};
	// What now?
}
	

struct widget {
	rect bounding_box();
	void place(rect r);
};

struct bitmap {
	std::array<std::byte, N> data;
	int width, height;
};

void vertical_center(auto const& c) {
	// 🧙 Magic happens
}

void center_bitmaps() {
	struct bitmap_widget : bitmap {
		rect bounding_box() { ... }
		void place(rect r) { ... }
	};
	std::array<bitmap_widget, 3> a = {🌇, 🏙️, 🌁};
	// What now?
}
	

struct widget {
	rect bounding_box();
	void place(rect r);
};

struct bitmap {
	std::array<std::byte, N> data;
	int width, height;
};

void vertical_center(auto const& c) {
	// 🧙 Magic happens
}

void center_bitmaps() {
	struct bitmap_widget : bitmap {
		rect bounding_box() { ... }
		void place(rect r) { ... }
	};
	std::array<bitmap_widget, 3> a = {🌇, 🏙️, 🌁 };
	vertical_center(a); // Boom! Code reused! 
}
🌇
🏙️
🌁
🌇
🏙️
🌁

Success!

Success?

Understanding code is hard,
writing code is easy

We love writing code!

We have tools!

Classes, inheritance, variant, optional, virtual functions!

How to generalize
  1. Understand your problems: What do you need?
  2. Understand available algorithm: What does it do?
  3. Describe both in terms of the problem, not C++ jargon!
  4. Generalize

	struct bitmap {
		std::array<std::byte, N> data;
		int width, height;
	};
	
	void vertical_center(WidgetContainer const& c) {
		auto rects = tc::make_vector(tc::transform(c, 
			[](widget const& w) { return w.bounding_box(); }
		));
		// 🧙 Magic happens
		tc::for_each(tc::zip(c, rects),
			[&](widget& w, rect r) { 
				widget.place(r);
			}
		);
	}


struct bitmap {
	std::array<std::byte, N> data;
	int width, height;
};

void vertical_center(ranges::forward_range auto rects) 
	requires is_same_v<
		ranges::range_reference_t<decltype(rects)>, 
		rect&
	> 
{
	// 🧙 Magic happens
 }
	

struct bitmap {
	std::array<std::byte, N> data;
	int width, height;
};

void vertical_center(ranges::forward_range auto rects) 
	requires is_same_v<
		ranges::range_reference_t<decltype(rects)>, 
		rect&
	> 
{
	// 🧙 Magic happens
 }

void center_bitmaps() {
	std::array<bitmap, 3> a = {🌇, 🏙️, 🌁};
	std::array<rect, 3> rects = { ... };
	vertical_center(rects); // Much better
}
Shared algorithm, different data:
Generic function
  • Define minimal required operations as concepts
  • Better: "requirements expressed in terms of fundamental and complete concepts."
    (Stroustrup, P0557r1)
  • Requires problem analysis!
  • Don't generalize from single use case
Customizing Generic Functions

Client code → generic library code → client code

1. Dispatch to Function Overloads

void place(rect r, great_widget);
void place(rect r, awesome_widget);

void place_items(rect bounds, forward_range auto rng) {
	auto const results = /* magic */;
	tc::for_each(
		tc::zip(results, rng), 
		[](rect r, auto& item) { place(r, item); }
	);
}

void main() {
	place_items(rect{}, std::vector<great_widget>());
	place_items(rect{}, std::vector<awesome_widget>());
}

e.g. std::size, std::begin, std::end

2. Output Functions

template<
	forward_range Rng, 
	invocable<rect, range_value_t<Rng>> F
>
void place_items(rect bounds, Rng const& rng, F func) {
	auto const results = /* 🧙 magic */;
	tc::for_each(
		tc::zip(results, rng), 
		func
	);
}

void main() {
	place_items(
		rect{}, 
		std::vector<great_widget>(),
		[](rect r, great_widget const& w) {}
	);
}
2. Output Functors

template<
	forward_range Rng, 
	invocable<rect, range_value_t<Rng>> F
>
void place_items(rect bounds, Rng const& rng, F func) {
	auto it = std::begin(rng);
	/* 🧙 magic */;
	func(*it, rect{});
	++it;
	/* 🧙 more magic */;
	func(*it, rect{});
}

void main() {
	place_items(
		rect{}, 
		std::vector<great_widget>(),
		[](rect r, great_widget const& w) {}
	);
}
3. Pass Functors

template<
	forward_range Rng, 
	predicate<range_value_t<Rng>> P,
	invocable<rect, range_value_t<Rng>> F
>
void place_items(rect bounds, Rng const& rng, P pred, F f) {
	auto it = std::begin(rng);
	/* 🧙 magic */;
	if(pred(*it)) {
		f(*it, rect{});
	}
	++it;
	/* 🧙 more magic */;
	if(pred(*it)) {
		f(*it, rect{});
	}
}
4. Command pattern

enum class match { skip_left, match, skip_right };	
vector dynamic_programming(
	forward_range auto first, 
	forward_range auto second
);
4. Command pattern

enum class match { skip_left, match, skip_right };

struct SMatcher {
	using cost = int;
	constexpr static cost initial = 0;

	cost accumulate_cost(cost prev, int i, int j, match m);
	bool better(cost lhs, cost rhs) { return lhs < rhs; }
};

vector dynamic_programming(
	forward_range auto first, 
	forward_range auto second,
	auto matcher
);
Generic Functions
  • Need clear requirements
  • expressed in well-known concepts
  • Reduce dependencies
  • Flexible and customizable through customization points

enum class match { skip_left, match, skip_right };

template<
	typename Derived, typename Cost, Cost c_costInitial
>
struct dynamic_programming {
private:
	vector<match> m_vecematch;

public:
	using const_iterator
		= typename vector<match>::const_reverse_iterator;
	using iterator = const_iterator;

	const_iterator begin() { return m_vecematch.rbegin(); }
	const_iterator end() { return m_vecematch.rend(); }
	
protected:
	void calculate(auto first, auto second);
};
Curiously Recurring Template Pattern

enum class match { skip_left, match, skip_right };

template<
	typename Derived, typename Cost, Cost c_costInitial
>
struct dynamic_programming {
	// ...
};

struct string_match 
	: dynamic_programming<string_match, int, 0> 
{
	bool better(int lhs, int rhs) { return lhs < rhs; }
	int accumulate(int costPrev, int i, int j, match m) {
		// ...
	}
};
Sharing code and data: Generic Classes
  • Curiously Recurring Template Pattern (CRTP)
  • Compile-time polymorphism
  • Generic interface, algorithms, data in templated base class
  • Customization points in derived class
Templated Base Class

template<typename base>
redirected_process : base { 
	redirected_process& operator<<(std::string const& s)
};

struct async_base {
	void write(std::string const& s);
};

struct sync_base {
	void write(std::string const& s);
};
When to use which?
  • Often a question of convenience
  • Who owns data? Initialization order?
  • What creates less friction, less casts?
Mixin Class

struct widget_base {
	void mouse_move(point const& pt);
};

struct button : widget_base {};
struct dropdown : widget_base {};

template<typename base>
struct beep : base {
	void mouse_move(point const& pt) {
		base::mouse_move(pt);
		beep();
	}
};

struct annoying_button : beep<button> {};
struct sane_button : button {};
struct annoying_dropdown : beep<dropdown> {};

What about inheritance and virtual functions?

What about std::variant?

Code Reuse

Code Reuse
  • Implementation decision: DRY
  • Reusing algorithm: Generic Function
  • Reusing interface and data: Generic Classes
  • We reuse in unrelated contexts
  • Out of convenience, not design decision

Runtime Polymorphism

Runtime Polymorphism
  • Design decision!
  • Strong coupling between types
  • Share base classes and common interface
  • Interface must have same meaning for all types
  • Implementation must be correct for all types
Runtime Polymorphism

"The requirement of a polymorphic type, by definition, comes from its use. There are no polymorphic types, only polymorphic uses of similar types."

Runtime Polymorphism
Runtime Polymorphism
		
class object {
	rect r;
	bool dirty;

	virtual void build_context_menu();
	virtual void on_context_menu_click();

	virtual void draw() = 0;
};
Runtime Polymorphism

class object {
	rect r;
	bool dirty;

	virtual void build_context_menu();
	virtual void on_context_menu_click();

	virtual void draw() = 0;
}; 

class document {
	vector<std::unique_ptr<object>> objects;

	void select_all();
	void group_all();
};
Runtime Polymorphism
Runtime Polymorphism

class dialog_widget {
	virtual size min_size();
	virtual void add_constraints(solver& s);
	virtual void place(solver_result const& r);
}; 

class button : dialog_widget { /* ... */ };
class textbox : dialog_widget { /* ... */ };
Runtime Polymorphism

class dialog_widget {
	virtual size min_size();
	virtual void add_constraints(solver& s);
	virtual void place(solver_result const& r);
}; 

class button : dialog_widget { /* ... */ };
class textbox : dialog_widget { /* ... */ };

class dialog {
	void on_resize() { 
		// collect widget constraints
		// solve
		// place widgets
	}
};
Runtime Polymorphism

class my_dialog : dialog {
	textbox txtbox;
	button btn;

	my_dialog()
		: txtbox(*this, "Enter your text")
		, btn(*this, []() { do_something(tb.text()); })
	{}
};
Runtime Polymorphism

class my_dialog : dialog {
	textbox txtbox;
	button btn;

	my_dialog()
		: txtbox(*this, "Enter your text")
		, btn(*this, []() { do_something(tb.text()); })
	{}

	void for_each(std::function<dialog_widget&> f) {
		f(textbox);
		f(btn);
	}
};
Runtime Polymorphism

class dialog_widget
{
	dialog_widget(dialog& parent) {
	}
}; 

class button : dialog_widget { /* ... */ };
class textbox : dialog_widget { /* ... */ };

class dialog { 
};
Runtime Polymorphism

using bi = boost::intrusive;
class dialog_widget
: bi::list_base_hook<bi::link_mode<bi::auto_unlink>> 
{
	dialog_widget(dialog& parent) {
		parent.widgets.insert(this); 
	}
}; 

class button : dialog_widget { /* ... */ };
class textbox : dialog_widget { /* ... */ };

class dialog { 
	bi::list<dialog_widget> widgets;
};
Runtime Polymorphism
Runtime Polymorphism

		struct object_t {
		};

		using document_t = vector<object_t>;

		void draw(document_t const& d) {
			tc::for_each(d, [](auto const& o) {
				draw(o);
			});
		}

		void main() {
			document_t d;
			d.emplace_back(5);
			d.emplace_back("Hello World");
			draw(d);
		}
Runtime Polymorphism

		struct object_t {
			template<typename T>
			object_t(T t) : self_(make_unique<model<T>>(move(t)) {}
			// + move, copy & assignment

			friend void draw(object_t const& o) { o.self_->draw_(); }

		private:
			struct concept_t {
				virtual concept_t() = default;
				virtual void draw_() = 0;
			};

			template<typename T>
			struct model final : concept_t {
				model(T t) : data_(move(t)) {}
				void draw_() final {
					draw(data_);
				}
				T data_;
			};
			unique_ptr<concept_t> self_;
		};
Runtime Polymorphism

		void draw(int i) {}
		void draw(std::string s) {}

		using document_t = vector<object_t>;

		void draw(document_t const& d) {
			tc::for_each(d, [](auto const& o) {
				draw(o);
			});
		}

		void main() {
			document_t d;
			d.emplace_back(5);
			d.emplace_back("Hello World");
			draw(d);
		}
Runtime Polymorphism

Pre: Polymorphic use of stateful objects

  1. Interchangeable objects: Owning base class pointer
  2. Objects with identity: Intrusive containers
  3. Extensibility: Hidden polymorphism
(When to Avoid) Runtime Polymorphism
(When to Avoid) Runtime Polymorphism

		void update_data_model() {
			uiobjects.emplace_back(drag_handle{ corner_rect() });
		}

		void mouse_move() {
			// Check if mouse hovers! State! 
			tc::for_each(uiobjects, [](auto& o) { o.mouse_move(); });
		}

		void draw() {	
			// Draw hover texture 
			tc::for_each(uiobjects, [](auto& o) { o.draw(); });
		}
(When to Avoid) Runtime Polymorphism

		void mouse_move() {
			set_dirty(); // trigger redraw
		}

		void draw() {	
			if(corner_rect().contains(mouse_position())) {
				draw(hover_texture(), corner_rect());
			} else {
				draw(normal_texture(), corner_rect());
			}
		}
Finally ...
std::variant 

		struct result {};
		using errormsg = std::string;

		variant<result, errormsg> 
		search_img(std::string query);
variant

		struct result {};
		using errormsg = std::string;

		variant<result, errormsg> 
		search_img(std::string query);

		void main() {
			tc::fn_visit(
				[](errormsg const& msg) {},
				[](result const& s) {}
			)(search_img("cat"));
		}
variant

		struct result {};
		using errormsg = std::string;

		variant<result, errormsg> 
		search_img(std::string query);

		void main() {
			tc::fn_visit(
				[](errormsg const& msg) {
					ShowAlert(msg);
				},
				[](result const& s) {
					std::cout << "I have found something.";
				}
			)(search_img("cat"));
		}
variant

		struct result {};
		struct result2 {};
		using errormsg = std::string;

		variant<result, result2, errormsg> 
		search_img(std::string query);

		void main() {
			tc::fn_visit(
				[](errormsg const& msg) {
					ShowAlert(msg);
				},
				[](result const& s) {
					std::cout << "I have found something.";
				},
				[](result2 const& s) {
					std::cout << "I have found something different.";
				}
			)(search_img("cat"));
		}
variant

		struct result {};
		struct result2 {};
		struct result3 {};

		void download(
			variant<result, result2, result3> const& t
		) {
			tc::fn_visit(
				[](result const& s) {},
				[](result2 const& s) {},
				[](result3 const& s) {}
			)(t);
		}
variant

		struct result {};
		struct result2 {};
		struct result3 {};

		void download_thumbnail(
			variant<result, result2, result3> const& t
		) {
			tc::fn_visit(
				[](result const& s) {},
				[](result2 const& s) {},
				[](result3 const& s) {}
			)(t);
		}
variant

		struct result {};
		struct result2 {};
		struct result3 {};

		void authenticate(
			variant<result, result2, result3> const& t
		) {
			tc::fn_visit(
				[](result const& s) {},
				[](result2 const& s) {},
				[](result3 const& s) {}
			)(t);
		}
variant

		struct result_t {
			template<typename T>
			result_t(T t) /* ... */

			void authenticate();
			void download_image();
			void download_thumbnail();

		private:
			struct concept_t;
			/* ... */
			std::unique_ptr<concept_t> self_;
		};
Conclusion
  • Build generic library to maximize code reuse
  • Choose abstractions carefully
  • Different abstractions are interchangeable
  • But they don't have the same cost
  • Revisit your choices occasionally
  • Your code may have "evolved"

Thank You