examples

Toy examples in single C files.
git clone git://henryandlizzy.uk/examples
Log | Files | Refs

list-composition.cpp (3783B)

      1 #include <utility>
      2 #include <iostream>
      3 
      4 template <typename T, T* T::*link>
      5 struct list_adapter
      6 {
      7 	using element_type = T;
      8 	using iterator_type = T*;
      9 
     10 	static void insert_front(T*& head, T* x)
     11 	{
     12 		x->*link = std::exchange(head, x);
     13 	}
     14 
     15 	static void insert_after(T* prev, T* x)
     16 	{
     17 		insert_front(prev->*link, x);
     18 	}
     19 
     20 	static T* split_front(T*& head)
     21 	{
     22 		return std::exchange(head, nullptr);
     23 	}
     24 
     25 	static T* split_after(T* prev)
     26 	{
     27 		return split_front(prev->*link);
     28 	}
     29 
     30 	static T* extract_front(T*& head)
     31 	{
     32 		auto node = split_front(head);
     33 		head = split_after(node);
     34 		return node;
     35 	}
     36 
     37 	static T* extract_after(T& prev)
     38 	{
     39 		return extract_front(prev.*link);
     40 	}
     41 
     42 	static T* tail(T* head)
     43 	{
     44 		while (head->*link)
     45 			head = head->*link;
     46 		return head;
     47 	}
     48 
     49 	static T* index(T* head, unsigned i)
     50 	{
     51 		while(i--)
     52 			head = head->*link;
     53 		return head;
     54 	}
     55 
     56 	static unsigned count_list(T const* head)
     57 	{
     58 		unsigned n = 0;
     59 		while (head)
     60 		{
     61 			head = head->*link;
     62 			++n;
     63 		}
     64 		return n;
     65 	}
     66 
     67 	template <typename P>
     68 	static T*& find_before(T*& head, P predicate)
     69 	{
     70 		T** p = &head;
     71 		while (*p and not predicate(*p))
     72 			p = &((*p)->*link);
     73 		return *p;
     74 	}
     75 
     76 	template <typename U>
     77 	static void insert_sorted(T*& head, U T::*field, T* x)
     78 	{
     79 		//T** p = &head;
     80 	//	while (*p and xx->*field > (*p)->*field)
     81 	//		p = &((*p)->*link);
     82 		auto l = [x, field](T* y) {
     83 			return x->*field < y->*field;
     84 		};
     85 		T*& p = find_before(head, l);
     86 		insert_front(p, x);
     87 	}
     88 
     89 };
     90 
     91 template <typename T>
     92 struct list_head : private T
     93 {
     94 	using typename T::iterator_type;
     95 	iterator_type head = nullptr;
     96 
     97 	unsigned count() const
     98 	{
     99 		return T::count_list(head);
    100 	}
    101 
    102 	template <typename U>
    103 	void insert_sorted(U T::element_type::*field, iterator_type x)
    104 	{
    105 		//T** p = &head;
    106 	//	while (*p and xx->*field > (*p)->*field)
    107 	//		p = &((*p)->*link);
    108 		auto l = [x, field](iterator_type y) {
    109 			return x->*field < y->*field;
    110 		};
    111 		iterator_type& p = T::find_before(head, l);
    112 		T::insert_front(p, x);
    113 	}
    114 };
    115 
    116 
    117 struct treenode
    118 {
    119 	std::string_view name;
    120 
    121 	using link = treenode*;
    122 	link first_child = nullptr;
    123 	link next_sibling = nullptr;
    124 	link next_sorted = nullptr;
    125 
    126 	using child_list = list_adapter<treenode, &treenode::first_child>;
    127 	using sibling_list = list_adapter<treenode, &treenode::next_sibling>;
    128 	using sorted_list =  list_adapter<treenode, &treenode::next_sorted>;
    129 };
    130 
    131 void add_child(treenode& parent, treenode& child)
    132 {
    133 	treenode::sibling_list::insert_front(parent.first_child, &child);
    134 }
    135 
    136 void insert_sorted(list_head<treenode::sorted_list>& head, treenode& x)
    137 {
    138 	head.insert_sorted(&treenode::name, &x);
    139 }
    140 
    141 struct list_printer
    142 {
    143 	treenode const* head;
    144 	treenode* treenode::*link;
    145 };
    146 
    147 std::ostream& operator <<(std::ostream& out, list_printer const& lp)
    148 {
    149 	out << "[ ";
    150 	for (auto p = lp.head; p; p = p->*lp.link)
    151 		std::cout << p->name << ' ';
    152 	return out << ']';
    153 }
    154 
    155 int main()
    156 {
    157 	using std::cout, std::endl;
    158 	treenode a{"Alice"}, b{"Bob"}, c{"Charlie"}, d{"Douglas"}, e{"Edward"}, f{"Fogarty"};
    159 
    160 	add_child(a, d);
    161 	add_child(d, f);
    162 	add_child(a, b);
    163 	add_child(b, c);
    164 	add_child(b, e);
    165 
    166 	list_head<treenode::sorted_list> name_order;
    167 
    168 	insert_sorted(name_order, b);
    169 	insert_sorted(name_order, d);
    170 	insert_sorted(name_order, c);
    171 	insert_sorted(name_order, f);
    172 	insert_sorted(name_order, a);
    173 	insert_sorted(name_order, e);
    174 
    175 	cout << "Alice & lastborn descendents: " << list_printer{&a, &treenode::first_child} << endl;
    176 	cout << "Bob & siblings: " << list_printer{&b, &treenode::next_sibling} << endl;
    177 	cout << "All " << name_order.count() << " sorted by name: " << list_printer(name_order.head, &treenode::next_sorted) << endl;
    178 
    179 	treenode::sorted_list::extract_after(b);
    180 	cout << "Extract Charlie: " << list_printer{&c, &treenode::next_sorted} << list_printer{name_order.head, &treenode::next_sorted} << endl;
    181 }