1
#include <Rcpp.h>
2

3
#include <vector>
4
#include <algorithm>
5

6
namespace
7
{
8 1
	struct toi_data
9
	{
10
		std::vector<int> parent;
11
		std::vector<int> label;
12
		std::vector<std::vector<int> > children;
13
		const Rcpp::List &impred;
14

15

16 1
		toi_data(const Rcpp::List &impred) : impred(impred) {}
17
	};
18

19 1
	bool is_immediate_predecessor(int i, int val, const toi_data &d)
20
	{
21 1
		Rcpp::IntegerVector impredi = Rcpp::as<Rcpp::IntegerVector>(d.impred[i-1]);
22 1
		return std::find(impredi.begin(), impredi.end(), val) != impredi.end();
23
	}
24

25 1
	void add_child(int parent, int child, toi_data &d)
26
	{
27 1
		d.children[parent].push_back(child);
28
	}
29

30 1
	void right(int i, int r, int root, toi_data &d)
31
	{
32 1
		const auto &range = d.children[r];
33 1
		std::for_each(range.begin(), range.end(), [=,&d](const int child) {
34

35 1
		  int l = d.label[child];
36

37 1
			if (!is_immediate_predecessor(i, l, d))
38
			{
39 1
				int t = d.parent.size();
40 1
				d.parent.push_back(root);
41 1
				d.label.push_back(d.label[child]);
42 1
				d.children.push_back({});
43 1
				add_child(root, t, d);
44 1
				right(i, child, t, d);
45
			}
46
		});
47
	}
48

49 1
	int left(int i, toi_data &d)
50
	{
51 1
		int root = d.parent.size();
52 1
	  d.label.push_back(i);
53 1
	  d.parent.push_back(0);
54 1
	  d.children.push_back({});
55
	  
56 1
		if (i == 0)
57
		{
58 1
			return root;
59
		}
60

61 1
		int r = left(i - 1, d);
62

63 1
		d.parent[r] = root;
64

65 1
		add_child(root, r, d);
66 1
		right(i, r, root, d);
67
		
68

69 1
		return root;
70
	}
71
}
72

73
/**
74
* Computes the tree of ideals. Return values needs P to be sorted according to a topological sort!
75
**/
76

77
// [[Rcpp::export]]
78

79 1
Rcpp::List treeOfIdeals(Rcpp::List imPred)
80
{
81 1
	toi_data d(imPred);
82 1
	left(imPred.size(), d);
83 1
	return Rcpp::List::create(Rcpp::Named("label") = d.label, 
84 1
                           Rcpp::Named("parent") = d.parent,
85 1
                           Rcpp::Named("child")=d.children);
86
}

Read our documentation on viewing source code .

Loading