commit c9aac4dfc79e1d117ab056a34a2e196f55a3e4f4
parent 54aaca2d308e8b1f76356abb30bac35907f5de90
Author: Henry Wilson <henry@henryandlizzy.uk>
Date: Tue, 7 Feb 2023 22:59:21 +0000
list-composition: Add list_adapter type
Diffstat:
1 file changed, 124 insertions(+), 62 deletions(-)
diff --git a/src/list-composition.cpp b/src/list-composition.cpp
@@ -1,63 +1,118 @@
#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)
+template <typename T, T* T::*link>
+struct list_adapter
{
- while (head->*link)
- head = head->*link;
- return *head;
-}
+ using element_type = T;
+ using iterator_type = T*;
+
+ static void insert_front(T*& head, T* x)
+ {
+ x->*link = std::exchange(head, x);
+ }
+
+ static void insert_after(T* prev, T* x)
+ {
+ insert_front(prev->*link, x);
+ }
+
+ static T* split_front(T*& head)
+ {
+ return std::exchange(head, nullptr);
+ }
+
+ static T* split_after(T* prev)
+ {
+ return split_front(prev->*link);
+ }
+
+ static T* extract_front(T*& head)
+ {
+ auto node = split_front(head);
+ head = split_after(node);
+ return node;
+ }
+
+ static T* extract_after(T& prev)
+ {
+ return extract_front(prev.*link);
+ }
+
+ static T* tail(T* head)
+ {
+ while (head->*link)
+ head = head->*link;
+ return head;
+ }
+
+ static T* index(T* head, unsigned i)
+ {
+ while(i--)
+ head = head->*link;
+ return head;
+ }
+
+ static unsigned count_list(T const* head)
+ {
+ unsigned n = 0;
+ while (head)
+ {
+ head = head->*link;
+ ++n;
+ }
+ return n;
+ }
+
+ template <typename P>
+ static T*& find_before(T*& head, P predicate)
+ {
+ T** p = &head;
+ while (*p and not predicate(*p))
+ p = &((*p)->*link);
+ return *p;
+ }
+
+ template <typename U>
+ static void insert_sorted(T*& head, U T::*field, T* x)
+ {
+ //T** p = &head;
+ // while (*p and xx->*field > (*p)->*field)
+ // p = &((*p)->*link);
+ auto l = [x, field](T* y) {
+ return x->*field < y->*field;
+ };
+ T*& p = find_before(head, l);
+ insert_front(p, x);
+ }
-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)
+struct list_head : private T
{
- unsigned n = 0;
- while ((head = head->*link))
- ++n;
- return n;
-}
+ using typename T::iterator_type;
+ iterator_type head = nullptr;
+
+ unsigned count() const
+ {
+ return T::count_list(head);
+ }
+
+ template <typename U>
+ void insert_sorted(U T::element_type::*field, iterator_type x)
+ {
+ //T** p = &head;
+ // while (*p and xx->*field > (*p)->*field)
+ // p = &((*p)->*link);
+ auto l = [x, field](iterator_type y) {
+ return x->*field < y->*field;
+ };
+ iterator_type& p = T::find_before(head, l);
+ T::insert_front(p, x);
+ }
+};
-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
{
@@ -67,16 +122,20 @@ struct treenode
link first_child = nullptr;
link next_sibling = nullptr;
link next_sorted = nullptr;
+
+ using child_list = list_adapter<treenode, &treenode::first_child>;
+ using sibling_list = list_adapter<treenode, &treenode::next_sibling>;
+ using sorted_list = list_adapter<treenode, &treenode::next_sorted>;
};
void add_child(treenode& parent, treenode& child)
{
- insert_front(parent.first_child, &treenode::next_sibling, child);
+ treenode::sibling_list::insert_front(parent.first_child, &child);
}
-void insert_sorted(treenode*& head, treenode& x)
+void insert_sorted(list_head<treenode::sorted_list>& head, treenode& x)
{
- insert_sorted(head, &treenode::next_sorted, &treenode::name, x);
+ head.insert_sorted(&treenode::name, &x);
}
struct list_printer
@@ -104,16 +163,19 @@ int main()
add_child(b, c);
add_child(b, e);
- treenode* name_order_head = nullptr;
+ list_head<treenode::sorted_list> name_order;
- 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);
+ insert_sorted(name_order, b);
+ insert_sorted(name_order, d);
+ insert_sorted(name_order, c);
+ insert_sorted(name_order, f);
+ insert_sorted(name_order, a);
+ insert_sorted(name_order, 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;
+ cout << "All " << name_order.count() << " sorted by name: " << list_printer(name_order.head, &treenode::next_sorted) << endl;
+
+ treenode::sorted_list::extract_after(b);
+ cout << "Extract Charlie: " << list_printer{&c, &treenode::next_sorted} << list_printer{name_order.head, &treenode::next_sorted} << endl;
}
