phylopomp
Phylodynamics for POMPs
All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
nodeseq.h
Go to the documentation of this file.
1// -*- C++ -*-
2// NODE SEQUENCE CLASS
3
4#ifndef _NODESEQ_H_
5#define _NODESEQ_H_
6
7#include <list>
8#include <unordered_map>
9#include <string>
10#include <cstring>
11#include "node.h"
12#include "internal.h"
13
14typedef typename std::list<node_t*>::const_iterator node_it;
15typedef typename std::list<node_t*>::iterator node_nit;
16typedef typename std::list<node_t*>::const_reverse_iterator node_rev_it;
17
19class nodeseq_t : public std::list<node_t*> {
20
21private:
22
24 void clean (void) {
25 for (node_t *p : *this) delete p;
26 clear();
27 };
28
29public:
30
32 ~nodeseq_t (void) {
33 clean();
34 };
35
36public:
37
38 // SERIALIZATION
40 size_t bytesize (void) const {
41 size_t s = sizeof(size_t);
42 for (node_t *p : *this)
43 s += p->bytesize();
44 return s;
45 };
46
47 friend raw_t* operator>> (const nodeseq_t& G, raw_t* o) {
48 size_t nnode = G.size();
49 memcpy(o,&nnode,sizeof(size_t)); o += sizeof(size_t);
50 for (node_t *p : G) {
51 o = (*p >> o);
52 }
53 return o;
54 };
55
56 friend raw_t* operator>> (raw_t* o, nodeseq_t& G) {
57 G.clean();
58 std::unordered_map<name_t,node_t*> node_names;
59 std::unordered_map<name_t,ball_t*> ball_names;
60 size_t nnode = 0;
61 memcpy(&nnode,o,sizeof(size_t)); o += sizeof(size_t);
62 node_names.reserve(nnode);
63 ball_names.reserve(nnode);
64 for (size_t i = 0; i < nnode; i++) {
65 node_t *p = new node_t();
66 o = (o >> *p);
67 G.push_back(p);
68 node_names.insert({p->uniq,p});
69 }
70 for (node_t *q : G) {
71 q->repair_owners(node_names,&ball_names);
72 }
73 G.repair_owners(ball_names);
75 return o;
76 };
77
78private:
79
82 void repair_owners (std::unordered_map<name_t,ball_t*>& names) {
83 std::unordered_map<name_t,ball_t*>::const_iterator n;
84 for (node_t *p : *this) {
85 n = names.find(p->uniq);
86 assert(n != names.end());
87 ball_t *b = n->second;
88 p->green_ball() = b;
89 }
90 };
91
92private:
93
96 static bool compare (node_t* p, node_t* q) {
97 return (p->slate < q->slate) ||
98 ((p->slate == q->slate) && (p->uniq < q->uniq));
99 };
100
101public:
102
105 merge(other,compare);
106 return *this;
107 };
108
110 void sort (void) {
111 std::list<node_t*>::sort(compare);
112 };
113
114private:
115
117 slate_t dawn (void) const {
118 return (empty()) ? R_NaReal : front()->slate;
119 };
120
121 slate_t dusk (void) const {
122 return (empty()) ? R_NaReal : back()->slate;
123 }
124
125public:
126
128 pocket_t* colored (color_t col) const {
129 pocket_t *p = new pocket_t;
130 for (node_t *q : *this) {
131 for (ball_t *b : *q ) {
132 if (b->is(col)) p->insert(b);
133 }
134 }
135 return p;
136 };
137
138 size_t ntime (slate_t t) const {
139 size_t count = 1;
140 for (node_t *p : *this) {
141 if (t < p->slate) {
142 t = p->slate;
143 count++;
144 }
145 }
146 return count;
147 };
148
149 size_t length (void) const {
150 return this->size();
151 };
152
154 int i = 0;
155 node_it k = cbegin();
156 while (i < n && k != cend()) {
157 i++; k++;
158 }
159 assert(k != cend());
160 return *k;
161 };
162
163public:
164
166 void swap (ball_t *a, ball_t *b) {
167 node_t *p = a->holder();
168 node_t *q = b->holder();
169 if (p != q) {
170 p->erase(a); q->insert(a); a->holder() = q;
171 q->erase(b); p->insert(b); b->holder() = p;
172 }
173 };
174
176 void add (node_t *p, ball_t *a) {
177 swap(a,p->green_ball());
178 p->deme() = a->deme();
179 push_back(p);
180 };
181
184 void drop (ball_t *a) {
185 assert(a->is(black));
186 node_t *p = a->holder();
187 if (p->size() > 1) {
188 p->erase(a);
189 delete a;
190 if (p->dead_root()) { // remove isolated root
191 destroy_node(p);
192 }
193 } else {
194 swap(a,p->green_ball());
195 destroy_node(p);
196 drop(a); // recurse
197 }
198 };
199
201 assert(p->dead_root());
202 remove(p);
203 delete p;
204 };
205
207 void comb (void) {
208 for (node_rev_it i = crbegin(); i != crend(); i++) {
209 if ((*i)->size() == 1 && (*i)->holds(green)) {
210 swap((*i)->last_ball(),(*i)->green_ball());
211 }
212 }
213 node_nit j = begin();
214 while (j != end()) {
215 if ((*j)->dead_root()) {
216 destroy_node(*(j++));
217 } else {
218 j++;
219 }
220 }
221 };
222
223private:
224
229 node_t *p = b->holder();
230 while (p->lineage() == null_lineage) {
231 p->lineage() = u;
232 p = p->parent();
233 }
234 };
235
236public:
237
241 void trace_lineages (void) {
242 // we trace each lineage in turn.
243 // because we move from early to late,
244 // the order is guaranteed to be valid.
245 name_t u = 0;
246 for (node_t *p : *this ) {
247 for (ball_t *b : *p) {
248 if (b->color==blue) {
249 trace_lineage(b,u);
250 u++;
251 }
252 }
253 }
254 };
255
256public:
257
259 std::string describe (void) const {
260 std::string o = "";
261 for (node_t *p : *this) {
262 o += p->describe();
263 }
264 return o;
265 };
266
267 virtual std::string yaml (std::string tab = "") const {
268 std::string o = "";
269 std::string t = tab + " ";
270 for (node_t *p : *this) {
271 o += tab + "- " + p->yaml(t);
272 }
273 return o;
274 };
275
276 SEXP structure (void) const {
277 SEXP Nodes;
278 PROTECT(Nodes = NEW_LIST(size()));
279 int k = 0;
280 for (node_t *p : *this) {
281 SET_ELEMENT(Nodes,k++,p->structure());
282 }
283 UNPROTECT(1);
284 return Nodes;
285 };
286
287 std::string newick (slate_t t) const {
288 slate_t te = dawn();
289 std::string o = "";
290 for (node_t *p : *this) {
291 if (p->is_root()) {
292 o += p->newick(t,te) + ";";
293 }
294 }
295 return o;
296 };
297};
298
299#endif
color_t
BALL COLORS.
Definition ball.h:14
@ green
Definition ball.h:14
@ black
Definition ball.h:14
@ blue
Definition ball.h:14
Balls function as pointers.
Definition ball.h:29
name_t deme(void) const
view deme
Definition ball.h:86
node_t * holder(void) const
in whose pocket do I lie?
Definition ball.h:109
bool is(color_t c) const
is a given ball of the given color?
Definition ball.h:117
Encodes a genealogical node.
Definition node.h:23
node_t * parent(void) const
Definition node.h:115
name_t lineage(void) const
view lineage
Definition node.h:104
size_t bytesize(void) const
size of binary serialization
Definition node.h:40
bool dead_root(void) const
Definition node.h:124
bool is_root(void) const
Definition node.h:121
std::string newick(const slate_t &tnow, const slate_t &tpar) const
Newick format.
Definition node.h:214
SEXP structure(void) const
R list description.
Definition node.h:201
std::string describe(void) const
human-readable info
Definition node.h:177
std::string yaml(std::string tab="") const
machine-readable info
Definition node.h:189
name_t deme(void) const
view deme
Definition node.h:96
name_t uniq
Definition node.h:34
ball_t * green_ball(void) const
pointer to my green ball
Definition node.h:88
slate_t slate
Definition node.h:35
A sequence of nodes.
Definition nodeseq.h:19
slate_t dawn(void) const
Earliest time in the sequence.
Definition nodeseq.h:117
std::string describe(void) const
human-readable info
Definition nodeseq.h:259
void clean(void)
clean up: delete all nodes, reset globals
Definition nodeseq.h:24
void trace_lineage(ball_t *b, name_t u)
Definition nodeseq.h:228
virtual std::string yaml(std::string tab="") const
human- & machine-readable info
Definition nodeseq.h:267
size_t ntime(slate_t t) const
Number of distinct timepoints.
Definition nodeseq.h:138
void comb(void)
Definition nodeseq.h:207
void sort(void)
order nodes in order of increasing time
Definition nodeseq.h:110
friend raw_t * operator>>(const nodeseq_t &G, raw_t *o)
binary serialization
Definition nodeseq.h:47
void destroy_node(node_t *p)
remove a dead root node
Definition nodeseq.h:200
nodeseq_t & operator+=(nodeseq_t &other)
merge two node sequences
Definition nodeseq.h:104
SEXP structure(void) const
R list description.
Definition nodeseq.h:276
size_t bytesize(void) const
size of serialized binary form
Definition nodeseq.h:40
void drop(ball_t *a)
Definition nodeseq.h:184
void repair_owners(std::unordered_map< name_t, ball_t * > &names)
Definition nodeseq.h:82
static bool compare(node_t *p, node_t *q)
Definition nodeseq.h:96
void swap(ball_t *a, ball_t *b)
swap balls a and b, wherever they lie
Definition nodeseq.h:166
size_t length(void) const
Number of nodes in the sequence.
Definition nodeseq.h:149
pocket_t * colored(color_t col) const
Get all balls of a color.
Definition nodeseq.h:128
void trace_lineages(void)
Definition nodeseq.h:241
slate_t dusk(void) const
Latest time in the sequence.
Definition nodeseq.h:121
node_t * position(int n)
traverse to nth node, retrieve pointer
Definition nodeseq.h:153
~nodeseq_t(void)
destructor
Definition nodeseq.h:32
std::string newick(slate_t t) const
put genealogy at time t into Newick format.
Definition nodeseq.h:287
void add(node_t *p, ball_t *a)
Definition nodeseq.h:176
A pocket is a set of balls.
Definition pocket.h:32
Rbyte raw_t
Definition internal.h:43
size_t name_t
Definition internal.h:45
double slate_t
Definition internal.h:44
#define n
Definition lbdp_pomp.c:8
static const name_t null_lineage
Definition node.h:13
std::list< node_t * >::const_reverse_iterator node_rev_it
Definition nodeseq.h:16
std::list< node_t * >::const_iterator node_it
Definition nodeseq.h:14
std::list< node_t * >::iterator node_nit
Definition nodeseq.h:15