examples

commit b23dfab9bb09f383d02f1779393b7e1cd95bd8a9
parent aa87d30d453a620a258fe759445a5aa0b9b7bf9b
Author: Henry Wilson <henry@henryandlizzy.uk>
Date:   Mon,  6 Feb 2023 22:02:41 +0000

list-composition: Add example showing how embedded linked lists exhibit emergent behaviour

Diffstat:
M
.gitignore
 | 
1
+
A
src/list-composition.cpp
 | 
119
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 120 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -30,6 +30,7 @@
 /guess-number
 /hush
 /io_uring
+/list-composition
 /mmallocator
 /model
 /morse
diff --git a/src/list-composition.cpp b/src/list-composition.cpp
@@ -0,0 +1,119 @@
+#include <utility>
+#include <iostream>
+
+template <typename T>
+void insert_front(T*& head, T* T::*link, T& x)
+{
+	x.*link = std::exchange(head, &x);
+}
+
+template <typename T>
+void insert_after(T& prev, T* T::*link, T& x)
+{
+	insert_front(prev.*link, link, x);
+}
+
+template <typename T>
+T& split_after(T*& link)
+{
+	return std::exchange(nullptr, link);
+}
+
+template <typename T>
+T& split_after(T& prev, T* T::*link)
+{
+	return split_after(prev.*link);
+}
+
+template <typename T>
+T& tail(T* head, T* T::*link)
+{
+	while (head->*link)
+		head = head->*link;
+	return *head;
+}
+
+template <typename T>
+T& index(T* head, T* T::*link, unsigned i)
+{
+	while(i--)
+		head = head->*link;
+	return *head;
+}
+
+template <typename T>
+unsigned count_list(T const* head, T* T::*link)
+{
+	unsigned n = 0;
+	while ((head = head->*link))
+		++n;
+	return n;
+}
+
+template <typename T, typename U>
+void insert_sorted(T*& head, T* T::*link, U T::*field, T& x)
+{
+	T** p = &head;
+	while (*p and x.*field > (*p)->*field)
+		p = &((*p)->*link);
+	insert_front(*p, link, x);
+}
+
+struct treenode
+{
+	std::string_view name;
+
+	using link = treenode*;
+	link first_child = nullptr;
+	link next_sibling = nullptr;
+	link next_sorted = nullptr;
+};
+
+void add_child(treenode& parent, treenode& child)
+{
+	insert_front(parent.first_child, &treenode::next_sibling, child);
+}
+
+void insert_sorted(treenode*& head, treenode& x)
+{
+	insert_sorted(head, &treenode::next_sorted, &treenode::name, x);
+}
+
+struct list_printer
+{
+	treenode const* head;
+	treenode* treenode::*link;
+};
+
+std::ostream& operator <<(std::ostream& out, list_printer const& lp)
+{
+	out << "[ ";
+	for (auto p = lp.head; p; p = p->*lp.link)
+		std::cout << p->name << ' ';
+	return out << ']';
+}
+
+int main()
+{
+	using std::cout, std::endl;
+	treenode a{"Alice"}, b{"Bob"}, c{"Charlie"}, d{"Douglas"}, e{"Edward"}, f{"Fogarty"};
+
+	add_child(a, d);
+	add_child(d, f);
+	add_child(a, b);
+	add_child(b, c);
+	add_child(b, e);
+
+	treenode* name_order_head = nullptr;
+
+	insert_sorted(name_order_head, b);
+	insert_sorted(name_order_head, d);
+	insert_sorted(name_order_head, c);
+	insert_sorted(name_order_head, f);
+	insert_sorted(name_order_head, a);
+	insert_sorted(name_order_head, e);
+
+	cout << "Alice & lastborn descendents: " << list_printer{&a, &treenode::first_child} << endl;
+	cout << "Bob & siblings: " << list_printer{&b, &treenode::next_sibling} << endl;
+	cout << "All " << count_list(name_order_head, &treenode::next_sorted) << " sorted by name: " << list_printer(name_order_head, &treenode::next_sorted) << endl;
+}