1 | // This file is a part of Framsticks SDK. http://www.framsticks.com/ |
---|
2 | // Copyright (C) 1999-2023 Maciej Komosinski and Szymon Ulatowski. |
---|
3 | // See LICENSE.txt for details. |
---|
4 | |
---|
5 | // Copyright (C) 1999,2000 Adam Rotaru-Varga (adam_rotaru@yahoo.com), GNU LGPL |
---|
6 | // 2018, Grzegorz Latosinski, added development checkpoints and support for new API for neuron types |
---|
7 | |
---|
8 | #include "f4_general.h" |
---|
9 | #include "../genooperators.h" // for GENOPER_ constants |
---|
10 | #include <common/nonstd_stl.h> |
---|
11 | #include <common/log.h> |
---|
12 | #include <frams/model/model.h> // for min and max attributes |
---|
13 | #include <common/nonstd_math.h> |
---|
14 | #include <algorithm> // std::min, std::max |
---|
15 | |
---|
16 | #ifdef DMALLOC |
---|
17 | #include <dmalloc.h> |
---|
18 | #endif |
---|
19 | |
---|
20 | |
---|
21 | #define BREAK_WHEN_REP_COUNTER_NULL //see comments where it is used |
---|
22 | #define TREAT_BAD_CONNECTIONS_AS_INVALID_GENO //see comments where it is used |
---|
23 | |
---|
24 | |
---|
25 | void rolling_dec(double *v) |
---|
26 | { |
---|
27 | *v -= 0.7853; // 0.7853981 45 degrees = pi/4 like in f1 |
---|
28 | } |
---|
29 | |
---|
30 | void rolling_inc(double *v) |
---|
31 | { |
---|
32 | *v += 0.7853; // 0.7853981 45 degrees |
---|
33 | } |
---|
34 | |
---|
35 | |
---|
36 | f4_Cell::f4_Cell(int nnr, f4_Cell *ndad, int nangle, GeneProps newP) |
---|
37 | { |
---|
38 | nr = nnr; |
---|
39 | type = CELL_UNDIFF; |
---|
40 | dadlink = ndad; |
---|
41 | org = NULL; |
---|
42 | genot = NULL; |
---|
43 | gcur = old_gcur = NULL; |
---|
44 | repeat.clear(); |
---|
45 | //genoRange.clear(); -- implicit |
---|
46 | |
---|
47 | anglepos = nangle; |
---|
48 | commacount = 0; |
---|
49 | stickchildcount = 0; |
---|
50 | P = newP; |
---|
51 | rolling = 0; |
---|
52 | xrot = 0; |
---|
53 | zrot = 0; |
---|
54 | //OM = Orient_1; |
---|
55 | inertia = 0.8; |
---|
56 | force = 0.04; |
---|
57 | sigmo = 2; |
---|
58 | conns_count = 0; |
---|
59 | |
---|
60 | // adjust firstend and OM if there is a stick dad |
---|
61 | if (ndad != NULL) |
---|
62 | { |
---|
63 | // make sure it is a stick (and not a stick f4_Cell!) |
---|
64 | if (ndad->type == CELL_STICK) |
---|
65 | { |
---|
66 | //firstend = ndad->lastend; |
---|
67 | //OM = ndad->OM; |
---|
68 | ndad->stickchildcount++; |
---|
69 | } |
---|
70 | if (ndad->type == CELL_NEURON) |
---|
71 | { |
---|
72 | inertia = ndad->inertia; |
---|
73 | force = ndad->force; |
---|
74 | sigmo = ndad->sigmo; |
---|
75 | } |
---|
76 | } |
---|
77 | // adjust lastend |
---|
78 | //lastend = firstend + ((Orient)OM * (Pt3D(1,0,0) * P.len)); |
---|
79 | P.muscle_bend_range = 1; |
---|
80 | } |
---|
81 | |
---|
82 | |
---|
83 | f4_Cell::f4_Cell(f4_Cells *nO, int nnr, f4_Node *ngeno, f4_Node *ngcur, f4_Cell *ndad, int nangle, GeneProps newP) |
---|
84 | { |
---|
85 | nr = nnr; |
---|
86 | type = CELL_UNDIFF; |
---|
87 | dadlink = ndad; |
---|
88 | org = nO; |
---|
89 | genot = ngeno; |
---|
90 | gcur = old_gcur = ngcur; |
---|
91 | repeat.clear(); |
---|
92 | //genoRange.clear(); -- implicit |
---|
93 | // preserve geno range of parent cell |
---|
94 | if (NULL != ndad) |
---|
95 | genoRange.add(ndad->genoRange); |
---|
96 | |
---|
97 | anglepos = nangle; |
---|
98 | commacount = 0; |
---|
99 | stickchildcount = 0; |
---|
100 | P = newP; |
---|
101 | rolling = 0; |
---|
102 | xrot = 0; |
---|
103 | zrot = 0; |
---|
104 | //OM = Orient_1; |
---|
105 | inertia = 0.8; |
---|
106 | force = 0.04; |
---|
107 | sigmo = 2; |
---|
108 | conns_count = 0; |
---|
109 | |
---|
110 | // adjust firstend and OM if there is a stick dad |
---|
111 | if (ndad != NULL) |
---|
112 | { |
---|
113 | // make sure it is a stick (and not a stick f4_Cell!) |
---|
114 | if (ndad->type == CELL_STICK) |
---|
115 | { |
---|
116 | //firstend = ndad->lastend; |
---|
117 | //OM = ndad->OM; |
---|
118 | ndad->stickchildcount++; |
---|
119 | } |
---|
120 | if (ndad->type == CELL_NEURON) |
---|
121 | { |
---|
122 | inertia = ndad->inertia; |
---|
123 | force = ndad->force; |
---|
124 | sigmo = ndad->sigmo; |
---|
125 | } |
---|
126 | } |
---|
127 | // adjust lastend |
---|
128 | //lastend = firstend + ((Orient)OM * (Pt3D(1,0,0) * P.len)); |
---|
129 | P.muscle_bend_range = 1; |
---|
130 | } |
---|
131 | |
---|
132 | |
---|
133 | f4_Cell::~f4_Cell() |
---|
134 | { |
---|
135 | // remove connections |
---|
136 | if (conns_count) |
---|
137 | { |
---|
138 | int i; |
---|
139 | for (i = conns_count - 1; i >= 0; i--) |
---|
140 | delete conns[i]; |
---|
141 | conns_count = 0; |
---|
142 | } |
---|
143 | } |
---|
144 | |
---|
145 | void f4_Cell::oneStep() |
---|
146 | { |
---|
147 | while (gcur != NULL) |
---|
148 | { |
---|
149 | //DB( printf(" %d (%d) executing '%c' %d\n", name, type, gcur->name, gcur->pos); ) |
---|
150 | // currently this is the last one processed |
---|
151 | // the current genotype code is processed |
---|
152 | //genoRange.add(gcur->pos,gcur->pos+gcur->name.length()-1); |
---|
153 | |
---|
154 | // To detect what genes are valid neuroclass names, but do NOT have is_neuroclass==true |
---|
155 | // (just as a curiosity to ensure we properly distinguish between, for example, the "G" neuron and the "G" modifier): |
---|
156 | //char *TMP = (char*)gcur->name.c_str(); |
---|
157 | //if (gcur->is_neuroclass==false && GenoOperators::parseNeuroClass(TMP, ModelEnum::SHAPETYPE_BALL_AND_STICK)) |
---|
158 | // printf("Could be a valid neuroclass, but is_neuroclass==false: %s\n", gcur->name.c_str()); |
---|
159 | |
---|
160 | if (gcur->neuclass == NULL) //not a neuron |
---|
161 | { |
---|
162 | if (gcur->name.length() > 1) |
---|
163 | logPrintf("f4_Cell", "oneStep", LOG_WARN, "Multiple-character code that is not a neuron class name: '%s'", gcur->name.c_str()); //let's see an example of such a code... |
---|
164 | |
---|
165 | genoRange.add(gcur->pos, gcur->pos); |
---|
166 | char name = gcur->name[0]; |
---|
167 | switch (name) |
---|
168 | { |
---|
169 | case '<': |
---|
170 | { |
---|
171 | // cell division! |
---|
172 | //DB( printf(" div! %d\n", name); ) |
---|
173 | |
---|
174 | // error: sticks cannot divide |
---|
175 | if (type == CELL_STICK) |
---|
176 | { |
---|
177 | // cannot fix |
---|
178 | org->setError(gcur->pos); |
---|
179 | return; // error code set -> stop further cells development |
---|
180 | } |
---|
181 | |
---|
182 | // undiff divides |
---|
183 | if (type == CELL_UNDIFF) |
---|
184 | { |
---|
185 | // commacount is set only when daughter turns into X |
---|
186 | // daughter cell |
---|
187 | // adjust new len |
---|
188 | GeneProps newP = P; |
---|
189 | newP.propagateAlong(false); |
---|
190 | f4_Cell *tmp = new f4_Cell(org, org->cell_count, genot, gcur->child2, this, commacount, newP); |
---|
191 | tmp->repeat = repeat; |
---|
192 | repeat.clear(); |
---|
193 | org->addCell(tmp); |
---|
194 | } |
---|
195 | // a neuron divides: create a new, duplicate connections |
---|
196 | if (type == CELL_NEURON) |
---|
197 | { |
---|
198 | // daughter cell |
---|
199 | f4_Cell *tmp = new f4_Cell(org, org->cell_count, genot, gcur->child2, |
---|
200 | // has the same dadlink |
---|
201 | this->dadlink, commacount, P); |
---|
202 | tmp->repeat = repeat; |
---|
203 | repeat.clear(); |
---|
204 | // it is a neuron from start |
---|
205 | tmp->type = CELL_NEURON; |
---|
206 | // it has the same type as the parent neuron |
---|
207 | tmp->neuclass = neuclass; |
---|
208 | // duplicate connections |
---|
209 | f4_CellConn *conn; |
---|
210 | for (int i = 0; i < conns_count; i++) |
---|
211 | { |
---|
212 | conn = conns[i]; |
---|
213 | tmp->addConnection(conn->from, conn->weight); |
---|
214 | } |
---|
215 | org->addCell(tmp); |
---|
216 | } |
---|
217 | // adjustments for this cell |
---|
218 | gcur = gcur->child; |
---|
219 | return; // error code not set -> halt this development and yield to other cells to develop |
---|
220 | } |
---|
221 | case '>': |
---|
222 | { |
---|
223 | // finish |
---|
224 | // see if there is a repeat count |
---|
225 | if (repeat.top > 0) |
---|
226 | { // there is a repeat counter |
---|
227 | if (!repeat.first()->isNull()) |
---|
228 | { // repeat counter is not null |
---|
229 | repeat.first()->dec(); |
---|
230 | if (repeat.first()->count > 0) |
---|
231 | { |
---|
232 | // return to repeat |
---|
233 | gcur = repeat.first()->node->child; |
---|
234 | } |
---|
235 | else |
---|
236 | { |
---|
237 | // continue |
---|
238 | gcur = repeat.first()->node->child2; |
---|
239 | repeat.pop(); |
---|
240 | } |
---|
241 | break; |
---|
242 | } |
---|
243 | else |
---|
244 | { |
---|
245 | repeat.pop(); |
---|
246 | // MacKo 2023-04: originally, there was no "break" nor "return" here (hence [[fallthrough]]; needed below for modern compilers) - not sure if this was intentional or overlooking. |
---|
247 | // This case can be tested with "#0" in the genotype. Anyway, there seems to be no difference in outcomes with and without "break". |
---|
248 | // However, falling through [[fallthrough]] below for count==0 causes performing repeat.push(repeat_ptr(gcur, 0)) while the very reason |
---|
249 | // we are here is that repeat count==0 (one of the conditions for isNull()), so I opted to add "break", but marked this tentative decision using #define. |
---|
250 | // The ultimate informed decision would require understanding all the logic and testing all the edge cases. |
---|
251 | #ifdef BREAK_WHEN_REP_COUNTER_NULL |
---|
252 | break; |
---|
253 | #endif |
---|
254 | } |
---|
255 | } |
---|
256 | else |
---|
257 | { |
---|
258 | // error: still undiff |
---|
259 | if (type == CELL_UNDIFF) |
---|
260 | { |
---|
261 | // fix it: insert an 'X' |
---|
262 | f4_Node *insertnode = new f4_Node("X", NULL, gcur->pos); |
---|
263 | if (org->setRepairInsert(gcur->pos, gcur, insertnode)) // not in repair mode, release |
---|
264 | delete insertnode; |
---|
265 | return; // error code set -> stop further cells development |
---|
266 | } |
---|
267 | repeat.clear(); |
---|
268 | // eat up rest |
---|
269 | int remaining_nodes = gcur->count() - 1; |
---|
270 | if (remaining_nodes > 0) |
---|
271 | logPrintf("f4_Cell", "oneStep", LOG_WARN, "Ignoring junk genetic code: %d node(s) at position %d", remaining_nodes, gcur->child->pos); //let's see an example of such a genotype... |
---|
272 | gcur = NULL; |
---|
273 | return; // done development |
---|
274 | } |
---|
275 | } |
---|
276 | #ifndef BREAK_WHEN_REP_COUNTER_NULL |
---|
277 | [[fallthrough]]; |
---|
278 | #endif |
---|
279 | case '#': |
---|
280 | { |
---|
281 | // repetition marker |
---|
282 | if (repeat.top >= repeat_stack::stackSize) |
---|
283 | { |
---|
284 | // repeat pointer stack is full, cannot remember this one. |
---|
285 | // fix: delete it |
---|
286 | org->setRepairRemove(gcur->pos, gcur); |
---|
287 | return; // error code set -> stop further cells development |
---|
288 | } |
---|
289 | repeat.push(repeat_ptr(gcur, gcur->reps)); |
---|
290 | gcur = gcur->child; |
---|
291 | break; |
---|
292 | } |
---|
293 | case ',': |
---|
294 | { |
---|
295 | commacount++; |
---|
296 | gcur = gcur->child; |
---|
297 | break; |
---|
298 | } |
---|
299 | case 'r': |
---|
300 | case 'R': |
---|
301 | { |
---|
302 | // error: if neuron |
---|
303 | if (type == CELL_NEURON) |
---|
304 | { |
---|
305 | // fix: delete it |
---|
306 | org->setRepairRemove(gcur->pos, gcur); |
---|
307 | return; // error code set -> stop further cells development |
---|
308 | } |
---|
309 | switch (name) |
---|
310 | { |
---|
311 | case 'r': rolling_dec(&rolling); break; |
---|
312 | case 'R': rolling_inc(&rolling); break; |
---|
313 | } |
---|
314 | gcur = gcur->child; |
---|
315 | break; |
---|
316 | } |
---|
317 | case 'l': case 'L': |
---|
318 | case 'c': case 'C': |
---|
319 | case 'q': case 'Q': |
---|
320 | case 'a': case 'A': |
---|
321 | case 'i': case 'I': |
---|
322 | case 's': case 'S': |
---|
323 | case 'm': case 'M': |
---|
324 | case 'f': case 'F': |
---|
325 | case 'w': case 'W': |
---|
326 | case 'e': case 'E': |
---|
327 | case 'd': case 'D': |
---|
328 | case 'g': case 'G': |
---|
329 | case 'b': case 'B': |
---|
330 | case 'h': case 'H': |
---|
331 | { |
---|
332 | // error: if neuron |
---|
333 | if (type == CELL_NEURON) //some neurons have the same single-letter names as modifiers (for example G,S,D), but they are supposed to have is_neuroclass==true so they should indeed not be handled here |
---|
334 | {//however, what we see here is actually modifiers such as IdqEbWL (so not valid neuroclasses) that occurred within an already differentiated cell of type==CELL_NEURON. |
---|
335 | //printf("Handled as a modifier, but type==CELL_NEURON: '%c'\n", name); |
---|
336 | // fix: delete it |
---|
337 | org->setRepairRemove(gcur->pos, gcur); |
---|
338 | return; // error code set -> stop further cells development |
---|
339 | } |
---|
340 | P.executeModifier(name); |
---|
341 | gcur = gcur->child; |
---|
342 | break; |
---|
343 | } |
---|
344 | case 'X': |
---|
345 | { |
---|
346 | // turn undiff. cell into a stick |
---|
347 | // error: already differentiated |
---|
348 | if (type != CELL_UNDIFF) |
---|
349 | { |
---|
350 | // fix: delete this node |
---|
351 | org->setRepairRemove(gcur->pos, gcur); |
---|
352 | return; // error code set -> stop further cells development |
---|
353 | } |
---|
354 | type = CELL_STICK; |
---|
355 | // fix dad commacount and own anglepos |
---|
356 | if (dadlink != NULL) |
---|
357 | { |
---|
358 | dadlink->commacount++; |
---|
359 | anglepos = dadlink->commacount; |
---|
360 | } |
---|
361 | // change of type halts developments, see comment at 'neuclasshandler' below |
---|
362 | gcur = gcur->child; |
---|
363 | return; // error code not set -> halt this development and yield to other cells to develop |
---|
364 | } |
---|
365 | case '[': |
---|
366 | { |
---|
367 | // connection to neuron |
---|
368 | // error: not a neuron |
---|
369 | if (type != CELL_NEURON) |
---|
370 | { |
---|
371 | // fix: delete it |
---|
372 | org->setRepairRemove(gcur->pos, gcur); |
---|
373 | return; // error code set -> stop further cells development |
---|
374 | } |
---|
375 | // input [%d:%g] |
---|
376 | int relfrom = gcur->conn_from; |
---|
377 | double weight = gcur->conn_weight; |
---|
378 | f4_Cell *neu_from = NULL; |
---|
379 | |
---|
380 | // input from other neuron |
---|
381 | // find neuron at relative i |
---|
382 | // find own index |
---|
383 | int this_index = 0, neu_counter = 0; |
---|
384 | for (int i = 0; i < org->cell_count; i++) |
---|
385 | { |
---|
386 | if (org->C[i]->type == CELL_NEURON) neu_counter++; |
---|
387 | if (org->C[i] == this) { this_index = neu_counter - 1; break; } |
---|
388 | } |
---|
389 | // find index of incoming |
---|
390 | int from_index = this_index + relfrom; |
---|
391 | |
---|
392 | if (from_index < 0) goto wait_conn; |
---|
393 | if (from_index >= org->cell_count) goto wait_conn; |
---|
394 | |
---|
395 | // find that neuron |
---|
396 | neu_counter = 0; |
---|
397 | int from; |
---|
398 | for (from = 0; from < org->cell_count; from++) |
---|
399 | { |
---|
400 | if (org->C[from]->type == CELL_NEURON) neu_counter++; |
---|
401 | if (from_index == (neu_counter - 1)) break; |
---|
402 | } |
---|
403 | if (from >= org->cell_count) goto wait_conn; |
---|
404 | neu_from = org->C[from]; |
---|
405 | |
---|
406 | // add connection |
---|
407 | // error: could not add connection (too many?) |
---|
408 | if (addConnection(neu_from, weight)) |
---|
409 | { |
---|
410 | // cannot fix |
---|
411 | org->setError(gcur->pos); |
---|
412 | return; // error code set -> stop further cells development |
---|
413 | } |
---|
414 | gcur = gcur->child; |
---|
415 | break; |
---|
416 | } |
---|
417 | wait_conn: |
---|
418 | { |
---|
419 | // wait for other neurons to develop |
---|
420 | |
---|
421 | if (!org->development_stagnation) // other cells are developing, the situation is changing, we may continue waiting... |
---|
422 | return; // error code not set -> halt this development and yield to other cells to develop |
---|
423 | |
---|
424 | //no cells are developing and we are waiting, but there is no chance other cells will create neurons we are waiting for, so we are forced to move on. |
---|
425 | |
---|
426 | #ifdef TREAT_BAD_CONNECTIONS_AS_INVALID_GENO // MacKo 2023-04: there were so many invalid connections accumulating in the genotype (and stopping processing of the chain of gcur->child) that it looks like treating them as errors is better... in 2000's, Framsticks neurons were flexible when it comes to inputs and outputs (for example, when asked, muscles would provide an output too, and neurons that ignored inputs would still accept them when connected) so f4 could create connections pretty randomly, but after 2000's we attempt to respect neurons' getPreferredInputs() and getPreferredOutput() so the network of connections has more constraints. |
---|
427 | if (gcur->parent->name == "#") |
---|
428 | { |
---|
429 | // MacKo 2023-04: Unfortunately the logic of multiplicating connections is not ideal... |
---|
430 | //TREAT_BAD_CONNECTIONS_AS_INVALID_GENO without this "#" exception would break /*4*/<X>N:N#5<[1:1]> |
---|
431 | // because every neuron wants to get an input from the neuron that will be created next |
---|
432 | // and all is fine until the last created neuron, which wants to get an input from another one which will not be created |
---|
433 | // (3 gets from 4, 4 gets from 5, 5 wants to get from 6 (relative connection offset for each of them is 1), |
---|
434 | // but 6 will not get created and if we want to TREAT_BAD_CONNECTIONS_AS_INVALID_GENO, we produce an error... |
---|
435 | // We would like to have this multiplication working, but OTAH we don't want to accept bad connections because then they tend to multiply as junk genes and bloat the genotype also causing more and more neutral mutations... |
---|
436 | //so this condition and checking for "#" is a simple way to be kind to some, but not all, bad connections, and not raise errors. Perhaps too kind and we open the door for too many cases with invalid connections. |
---|
437 | //Maybe it would be better to perform this check before addConnection(), seeing that for example we process the last iteration of the repetition counter? But how would we know that the (needed here) input neuron will not be developed later by other dividing cells... |
---|
438 | |
---|
439 | gcur = gcur->child; |
---|
440 | org->development_stagnation = false; //do not force other potentially waiting cells to hurry and act in this development cycle (which would be the last cycle if development_stagnation stayed true); we just acted and because of this the situation may change, so they can wait until another development_stagnation is detected |
---|
441 | return; // error code not set -> halt this development and yield to other cells to develop |
---|
442 | } |
---|
443 | else |
---|
444 | { |
---|
445 | //org->setError(gcur->pos); //in case setRepairRemove() would not always produce reasonable results |
---|
446 | org->setRepairRemove(gcur->pos, gcur); //produces unexpected results? or NOT? TODO verify, some genotypes earlier produced strange outcomes of this repair (produced a valid genotype, but some neurons were multiplied/copied after repair - maybe because when a branch of '<' (or something else) is missing, the other branch is copied?) |
---|
447 | return; // error code set -> stop further cells development |
---|
448 | } |
---|
449 | #else |
---|
450 | // no more actives, cannot add connection, ignore, but treat not as an error - before 2023-04 |
---|
451 | gcur = gcur->child; |
---|
452 | #endif |
---|
453 | } |
---|
454 | break; |
---|
455 | case ':': |
---|
456 | { |
---|
457 | // neuron parameter |
---|
458 | // error: not a neuron |
---|
459 | if (type != CELL_NEURON) |
---|
460 | { |
---|
461 | // fix: delete it |
---|
462 | org->setRepairRemove(gcur->pos, gcur); |
---|
463 | return; // error code set -> stop further cells development |
---|
464 | } |
---|
465 | switch (gcur->prop_symbol) |
---|
466 | { |
---|
467 | case '!': |
---|
468 | if (gcur->prop_increase) |
---|
469 | force += (1.0 - force) * 0.2; |
---|
470 | else |
---|
471 | force -= force * 0.2; |
---|
472 | break; |
---|
473 | case '=': |
---|
474 | if (gcur->prop_increase) |
---|
475 | inertia += (1.0 - inertia) * 0.2; |
---|
476 | else |
---|
477 | inertia -= inertia * 0.2; |
---|
478 | break; |
---|
479 | case '/': |
---|
480 | if (gcur->prop_increase) |
---|
481 | sigmo *= 1.4; |
---|
482 | else |
---|
483 | sigmo /= 1.4; |
---|
484 | break; |
---|
485 | default: |
---|
486 | org->setRepairRemove(gcur->pos, gcur); |
---|
487 | return; // error code set -> stop further cells development |
---|
488 | } |
---|
489 | gcur = gcur->child; |
---|
490 | break; |
---|
491 | } |
---|
492 | case ' ': |
---|
493 | case '\t': |
---|
494 | case '\n': |
---|
495 | case '\r': |
---|
496 | { |
---|
497 | // whitespace has no effect, should not occur |
---|
498 | // fix: delete it |
---|
499 | org->setRepairRemove(gcur->pos, gcur); |
---|
500 | return; // error code set -> stop further cells development |
---|
501 | } |
---|
502 | default: |
---|
503 | { |
---|
504 | // error: unknown code |
---|
505 | string buf = "Unknown code '" + gcur->name + "'"; |
---|
506 | logMessage("f4_Cell", "oneStep", LOG_ERROR, buf.c_str()); |
---|
507 | org->setRepairRemove(gcur->pos, gcur); |
---|
508 | return; // error code set -> stop further cells development |
---|
509 | } |
---|
510 | } |
---|
511 | } |
---|
512 | else |
---|
513 | { |
---|
514 | genoRange.add(gcur->pos, gcur->pos + int(gcur->name.length()) + 2 - 1); // +2 for N: |
---|
515 | if (type != CELL_UNDIFF) |
---|
516 | { |
---|
517 | // fix: delete this node |
---|
518 | org->setRepairRemove(gcur->pos, gcur); |
---|
519 | return; // error code set -> stop further cells development |
---|
520 | } |
---|
521 | // error: if no previous |
---|
522 | if (dadlink == NULL) |
---|
523 | { |
---|
524 | // fix: delete it |
---|
525 | org->setRepairRemove(gcur->pos, gcur); |
---|
526 | return; // error code set -> stop further cells development |
---|
527 | } |
---|
528 | neuclass = gcur->neuclass; |
---|
529 | type = CELL_NEURON; |
---|
530 | // change of type also halts development, to give other |
---|
531 | // cells a chance for adjustment. Namely, it is important |
---|
532 | // to wait for other cells to turn to neurons before adding connections |
---|
533 | gcur = gcur->child; |
---|
534 | return; // error code not set -> halt this development and yield to other cells to develop |
---|
535 | } |
---|
536 | } |
---|
537 | } |
---|
538 | |
---|
539 | |
---|
540 | int f4_Cell::addConnection(f4_Cell *nfrom, double nweight) |
---|
541 | { |
---|
542 | if (nfrom->neuclass->getPreferredOutput() == 0) return -1; // if incoming neuron does not produce output, return error |
---|
543 | if (neuclass->getPreferredInputs() != -1 && conns_count >= neuclass->getPreferredInputs()) return -1; //cannot add more inputs to this neuron |
---|
544 | if (conns_count >= F4_MAX_CELL_INPUTS - 1) return -1; // over hardcoded limit |
---|
545 | conns[conns_count] = new f4_CellConn(nfrom, nweight); |
---|
546 | conns_count++; |
---|
547 | return 0; |
---|
548 | } |
---|
549 | |
---|
550 | |
---|
551 | void f4_Cell::adjustRecur() |
---|
552 | { |
---|
553 | if (recurProcessedFlag) |
---|
554 | // already processed |
---|
555 | return; |
---|
556 | |
---|
557 | // mark it processed |
---|
558 | recurProcessedFlag = true; |
---|
559 | |
---|
560 | // make sure its parent is processed first |
---|
561 | if (dadlink != NULL) |
---|
562 | dadlink->adjustRecur(); |
---|
563 | |
---|
564 | // count children |
---|
565 | stickchildcount = 0; |
---|
566 | for (int i = 0; i < org->cell_count; i++) |
---|
567 | { |
---|
568 | if (org->C[i]->dadlink == this) |
---|
569 | if (org->C[i]->type == CELL_STICK) |
---|
570 | stickchildcount++; |
---|
571 | } |
---|
572 | |
---|
573 | if (dadlink == NULL) |
---|
574 | P.muscle_bend_range = 1.0; |
---|
575 | else |
---|
576 | P.muscle_bend_range = 1.0 / std::max(1, dadlink->stickchildcount); //bend range in f1: 0, 1 (line XX[|]) -> 100%, 2 (Y-shape X(X[|],X)) -> 50%, 3 (cross X(X[|],X,X)) -> 33% |
---|
577 | //MacKo 2023-05: but shouldn't this formula ^^ also take commacount into consideration, like in f1? |
---|
578 | |
---|
579 | if (type == CELL_STICK) |
---|
580 | { |
---|
581 | if (dadlink == NULL) |
---|
582 | { |
---|
583 | //firstend = Pt3D_0; |
---|
584 | // rotation due to rolling |
---|
585 | xrot = rolling; |
---|
586 | } |
---|
587 | else |
---|
588 | { |
---|
589 | //firstend = dadlink->lastend; |
---|
590 | GeneProps Pdad = dadlink->P; |
---|
591 | GeneProps Padj = Pdad; |
---|
592 | Padj.propagateAlong(false); |
---|
593 | |
---|
594 | //f4_OrientMat rot = Orient_1; |
---|
595 | |
---|
596 | // rotation due to rolling |
---|
597 | xrot = rolling + |
---|
598 | // rotation due to twist |
---|
599 | Pdad.twist; |
---|
600 | if (dadlink->commacount <= 1) |
---|
601 | { |
---|
602 | // rotation due to curvedness |
---|
603 | zrot = Padj.curvedness; |
---|
604 | } |
---|
605 | else |
---|
606 | { |
---|
607 | zrot = Padj.curvedness + (anglepos * 1.0 / (dadlink->commacount + 1) - 0.5) * M_PI * 2.0; |
---|
608 | } |
---|
609 | |
---|
610 | //rot = rot * f4_OrientMat(yOz, xrot); |
---|
611 | //rot = rot * f4_OrientMat(xOy, zrot); |
---|
612 | // rotation relative to parent stick |
---|
613 | //OM = rot * OM; |
---|
614 | |
---|
615 | // rotation in world coordinates |
---|
616 | //OM = ((f4_OrientMat)dadlink->OM) * OM; |
---|
617 | } |
---|
618 | //Pt3D lastoffset = (Orient)OM * (Pt3D(1,0,0)*P.len); |
---|
619 | //lastend = firstend + lastoffset; |
---|
620 | } |
---|
621 | } |
---|
622 | |
---|
623 | |
---|
624 | |
---|
625 | f4_CellConn::f4_CellConn(f4_Cell *nfrom, double nweight) |
---|
626 | { |
---|
627 | from = nfrom; |
---|
628 | weight = nweight; |
---|
629 | } |
---|
630 | |
---|
631 | |
---|
632 | |
---|
633 | f4_Cells::f4_Cells(f4_Node *genome, bool nrepair) |
---|
634 | { |
---|
635 | repair = nrepair; |
---|
636 | errorcode = GENOPER_OK; |
---|
637 | errorpos = -1; |
---|
638 | repair_remove = NULL; |
---|
639 | repair_parent = NULL; |
---|
640 | repair_insert = NULL; |
---|
641 | tmpcel = NULL; |
---|
642 | |
---|
643 | // create ancestor cell |
---|
644 | C[0] = new f4_Cell(this, 0, genome, genome, NULL, 0, GeneProps::standard_values); |
---|
645 | cell_count = 1; |
---|
646 | development_stagnation = false; |
---|
647 | } |
---|
648 | |
---|
649 | |
---|
650 | |
---|
651 | f4_Cells::~f4_Cells() |
---|
652 | { |
---|
653 | // release cells |
---|
654 | if (cell_count) |
---|
655 | { |
---|
656 | for (int i = cell_count - 1; i >= 0; i--) |
---|
657 | delete C[i]; |
---|
658 | cell_count = 0; |
---|
659 | } |
---|
660 | } |
---|
661 | |
---|
662 | |
---|
663 | bool f4_Cells::oneStep() |
---|
664 | { |
---|
665 | int old_cell_count = cell_count; //cell_count may change in the loop as new cells may be appended because cells may be dividing |
---|
666 | for (int i = 0; i < old_cell_count; i++) |
---|
667 | C[i]->old_gcur = C[i]->gcur; |
---|
668 | |
---|
669 | for (int i = 0; i < old_cell_count; i++) |
---|
670 | { |
---|
671 | C[i]->oneStep(); |
---|
672 | if (errorcode != GENOPER_OK) |
---|
673 | return false; // error -> end development |
---|
674 | } |
---|
675 | |
---|
676 | if (cell_count != old_cell_count) //the number of cells changed - something is going on! |
---|
677 | return true; //so continue development! |
---|
678 | |
---|
679 | for (int i = 0; i < old_cell_count; i++) |
---|
680 | if (C[i]->old_gcur != C[i]->gcur) // genotype execution pointer changed - something is going on! |
---|
681 | return true; //so continue development! |
---|
682 | |
---|
683 | //the same number of cells, no progress in development in any cell -> stagnation! |
---|
684 | |
---|
685 | if (development_stagnation) // stagnation was already detected in the previous step, so end development! |
---|
686 | { |
---|
687 | for (int i = 0; i < cell_count; i++) |
---|
688 | if (C[i]->gcur != NULL) // genotype execution pointer did not reach the end |
---|
689 | logPrintf("f4_Cells", "oneStep", LOG_WARN, "Finishing the development of cells due to stagnation, but cell %d did not reach the end of development", i); //let's see an example of such a genotype and investigate... |
---|
690 | return false; //end development |
---|
691 | } |
---|
692 | else |
---|
693 | { |
---|
694 | development_stagnation = true; //signal (force) f4_Cell's that wait for neural connection development to make a step, because all cells stagnated and waiting cells cannot hope for new neurons to be created |
---|
695 | return true; //one grace step. If there are some waiting cells, they must move on in the next step and set development_stagnation=false or set error. If development_stagnation is not set to false, we will finish development in the next step. This grace step may be unnecessary if there are no waiting cells, but we have no easy way to check this from here (although we could check if all cells' gcur==NULL... would this be always equivalent? Maybe some cells may stagnate with gcur!=NULL and they are not waiting for neural connections to develop and this does not mean an error? Added LOG_WARN above to detect such cases. Anyway, for gcur==NULL, f4_Cell.oneStep() exits immediately, so one grace step is not a big overhead.) |
---|
696 | } |
---|
697 | } |
---|
698 | |
---|
699 | |
---|
700 | int f4_Cells::simulate() |
---|
701 | { |
---|
702 | const bool PRINT_CELLS_DEVELOPMENT = false; //print the state of cells |
---|
703 | errorcode = GENOPER_OK; |
---|
704 | development_stagnation = false; //will be detected by oneStep() |
---|
705 | |
---|
706 | if (PRINT_CELLS_DEVELOPMENT) f4_Node::print_tree(C[0]->genot, 0); |
---|
707 | if (PRINT_CELLS_DEVELOPMENT) print_cells("Initialization"); |
---|
708 | |
---|
709 | // execute oneStep() in a cycle |
---|
710 | while (oneStep()) if (PRINT_CELLS_DEVELOPMENT) print_cells("Development step"); |
---|
711 | if (PRINT_CELLS_DEVELOPMENT) print_cells("After last development step"); |
---|
712 | |
---|
713 | if (errorcode != GENOPER_OK) return errorcode; |
---|
714 | |
---|
715 | // fix neuron attachements |
---|
716 | for (int i = 0; i < cell_count; i++) |
---|
717 | { |
---|
718 | if (C[i]->type == CELL_NEURON) |
---|
719 | { |
---|
720 | while (C[i]->dadlink->type == CELL_NEURON) |
---|
721 | { |
---|
722 | C[i]->dadlink = C[i]->dadlink->dadlink; |
---|
723 | } |
---|
724 | } |
---|
725 | } |
---|
726 | |
---|
727 | // there should be no undiff. cells |
---|
728 | // make undifferentiated cells sticks |
---|
729 | for (int i = 0; i < cell_count; i++) |
---|
730 | { |
---|
731 | if (C[i]->type == CELL_UNDIFF) |
---|
732 | { |
---|
733 | C[i]->type = CELL_STICK; |
---|
734 | //setError(); |
---|
735 | } |
---|
736 | } |
---|
737 | |
---|
738 | // recursive adjust |
---|
739 | // reset recursive traverse flags |
---|
740 | for (int i = 0; i < cell_count; i++) |
---|
741 | C[i]->recurProcessedFlag = false; |
---|
742 | // process every cell |
---|
743 | for (int i = 0; i < cell_count; i++) |
---|
744 | C[i]->adjustRecur(); |
---|
745 | |
---|
746 | //DB( printf("Cell simulation done, %d cells. \n", nc); ) |
---|
747 | |
---|
748 | if (PRINT_CELLS_DEVELOPMENT) print_cells("Final"); |
---|
749 | if (PRINT_CELLS_DEVELOPMENT) |
---|
750 | for (int i = 0; i < cell_count; i++) |
---|
751 | printf("%d,%d,dad=%d\tstick_children=%d\tcommas=%d\t|:range=%g\n", i, C[i]->nr, C[i]->dadlink ? C[i]->dadlink->nr : -1, C[i]->stickchildcount, C[i]->commacount, C[i]->P.muscle_bend_range); |
---|
752 | |
---|
753 | return errorcode; |
---|
754 | } |
---|
755 | |
---|
756 | |
---|
757 | void f4_Cells::print_cells(const char* description) |
---|
758 | { |
---|
759 | printf("------ %-55s ------ errorcode=%d, errorpos=%d\n", description, getErrorCode(), getErrorPos()); |
---|
760 | for (int i = 0; i < cell_count; i++) |
---|
761 | { |
---|
762 | f4_Cell *c = C[i]; |
---|
763 | string type; |
---|
764 | switch (c->type) |
---|
765 | { |
---|
766 | case CELL_UNDIFF: type = "undiff"; break; |
---|
767 | case CELL_STICK: type = "STICK"; break; |
---|
768 | case CELL_NEURON: type = string("NEURON:") + c->neuclass->name.c_str(); break; |
---|
769 | default: type = std::to_string(c->type); |
---|
770 | } |
---|
771 | const char *status = c->gcur == c->old_gcur ? (c->gcur != NULL ? "no progress" : "") : (c->gcur != NULL ? "progress" : "finished"); //progress or no progress means the cell is yielding = not finished but decided to halt development and wait for other cells. New cells may be created in case of "no progress" status. |
---|
772 | printf("%2d(%-8s) nr=%d \t type=%-15s \t genot=%s \t gcurrent=%s", i, status, c->nr, type.c_str(), c->genot->name.c_str(), c->gcur ? c->gcur->name.c_str() : "null"); |
---|
773 | if (c->gcur && c->gcur->name == "[") |
---|
774 | printf("\tfrom=%d weight=%g", c->gcur->conn_from, c->gcur->conn_weight); |
---|
775 | printf("\n"); |
---|
776 | for (int l = 0; l < c->conns_count; l++) |
---|
777 | printf("\tconn:%d from=%d weight=%g\n", l, c->conns[l]->from->nr, c->conns[l]->weight); |
---|
778 | } |
---|
779 | printf("\n"); |
---|
780 | } |
---|
781 | |
---|
782 | |
---|
783 | void f4_Cells::addCell(f4_Cell *newcell) |
---|
784 | { |
---|
785 | if (cell_count >= F4_MAX_CELLS - 1) |
---|
786 | { |
---|
787 | delete newcell; |
---|
788 | return; |
---|
789 | } |
---|
790 | C[cell_count] = newcell; |
---|
791 | cell_count++; |
---|
792 | } |
---|
793 | |
---|
794 | |
---|
795 | void f4_Cells::setError(int nerrpos) |
---|
796 | { |
---|
797 | errorcode = GENOPER_OPFAIL; |
---|
798 | errorpos = nerrpos; |
---|
799 | } |
---|
800 | |
---|
801 | void f4_Cells::setRepairRemove(int nerrpos, f4_Node *to_remove) |
---|
802 | { |
---|
803 | errorcode = GENOPER_REPAIR; |
---|
804 | errorpos = nerrpos; |
---|
805 | if (!repair) |
---|
806 | { |
---|
807 | // not in repair mode, treat as repairable error |
---|
808 | } |
---|
809 | else |
---|
810 | { |
---|
811 | repair_remove = to_remove; |
---|
812 | } |
---|
813 | } |
---|
814 | |
---|
815 | int f4_Cells::setRepairInsert(int nerrpos, f4_Node *parent, f4_Node *to_insert) |
---|
816 | { |
---|
817 | errorcode = GENOPER_REPAIR; |
---|
818 | errorpos = nerrpos; |
---|
819 | if (!repair) |
---|
820 | { |
---|
821 | // not in repair mode, treat as repairable error |
---|
822 | return -1; |
---|
823 | } |
---|
824 | else |
---|
825 | { |
---|
826 | repair_parent = parent; |
---|
827 | repair_insert = to_insert; |
---|
828 | return 0; |
---|
829 | } |
---|
830 | } |
---|
831 | |
---|
832 | void f4_Cells::repairGeno(f4_Node *geno, int whichchild) |
---|
833 | { |
---|
834 | // assemble repaired geno, if the case |
---|
835 | if (!repair) return; |
---|
836 | if ((repair_remove == NULL) && (repair_insert == NULL)) return; |
---|
837 | // traverse genotype tree, remove / insert node |
---|
838 | f4_Node *g2; |
---|
839 | if (whichchild == 1) |
---|
840 | g2 = geno->child; |
---|
841 | else |
---|
842 | g2 = geno->child2; |
---|
843 | if (g2 == NULL) |
---|
844 | return; |
---|
845 | if (g2 == repair_remove) |
---|
846 | { |
---|
847 | f4_Node *oldgeno; |
---|
848 | geno->removeChild(g2); |
---|
849 | if (g2->child) |
---|
850 | { |
---|
851 | // add g2->child as child to geno |
---|
852 | if (whichchild == 1) |
---|
853 | geno->child = g2->child; |
---|
854 | else |
---|
855 | geno->child2 = g2->child; |
---|
856 | g2->child->parent = geno; |
---|
857 | } |
---|
858 | oldgeno = g2; |
---|
859 | oldgeno->child = NULL; |
---|
860 | delete oldgeno; |
---|
861 | if (geno->child == NULL) return; |
---|
862 | // check this new |
---|
863 | repairGeno(geno, whichchild); |
---|
864 | return; |
---|
865 | } |
---|
866 | if (g2 == repair_parent) |
---|
867 | { |
---|
868 | geno->removeChild(g2); |
---|
869 | geno->addChild(repair_insert); |
---|
870 | repair_insert->parent = geno; |
---|
871 | repair_insert->child = g2; |
---|
872 | repair_insert->child2 = NULL; |
---|
873 | g2->parent = repair_insert; |
---|
874 | } |
---|
875 | // recurse |
---|
876 | if (g2->child) repairGeno(g2, 1); |
---|
877 | if (g2->child2) repairGeno(g2, 2); |
---|
878 | } |
---|
879 | |
---|
880 | |
---|
881 | void f4_Cells::toF1Geno(SString &out) |
---|
882 | { |
---|
883 | if (tmpcel) delete tmpcel; |
---|
884 | tmpcel = new f4_Cell(-1, NULL, 0, GeneProps::standard_values); |
---|
885 | out = ""; |
---|
886 | toF1GenoRec(0, out); |
---|
887 | delete tmpcel; |
---|
888 | } |
---|
889 | |
---|
890 | |
---|
891 | void f4_Cells::toF1GenoRec(int curc, SString &out) |
---|
892 | { |
---|
893 | if (curc >= cell_count) return; |
---|
894 | |
---|
895 | if (C[curc]->type != CELL_STICK) return; |
---|
896 | |
---|
897 | f4_Cell *thisti = C[curc]; |
---|
898 | if (thisti->dadlink != NULL) |
---|
899 | *tmpcel = *(thisti->dadlink); |
---|
900 | |
---|
901 | // adjust length, curvedness, etc. |
---|
902 | tmpcel->P.propagateAlong(false); |
---|
903 | while (tmpcel->P.length > thisti->P.length) |
---|
904 | { |
---|
905 | tmpcel->P.executeModifier('l'); |
---|
906 | out += "l"; |
---|
907 | } |
---|
908 | while (tmpcel->P.length < thisti->P.length) |
---|
909 | { |
---|
910 | tmpcel->P.executeModifier('L'); |
---|
911 | out += "L"; |
---|
912 | } |
---|
913 | while (tmpcel->P.curvedness > thisti->P.curvedness) |
---|
914 | { |
---|
915 | tmpcel->P.executeModifier('c'); |
---|
916 | out += "c"; |
---|
917 | } |
---|
918 | while (tmpcel->P.curvedness < thisti->P.curvedness) |
---|
919 | { |
---|
920 | tmpcel->P.executeModifier('C'); |
---|
921 | out += "C"; |
---|
922 | } |
---|
923 | while (thisti->rolling > 0.0f) |
---|
924 | { |
---|
925 | rolling_dec(&(thisti->rolling)); |
---|
926 | out += "R"; |
---|
927 | } |
---|
928 | while (thisti->rolling < 0.0f) |
---|
929 | { |
---|
930 | rolling_inc(&(thisti->rolling)); |
---|
931 | out += "r"; |
---|
932 | } |
---|
933 | |
---|
934 | // output X for this stick |
---|
935 | out += "X"; |
---|
936 | |
---|
937 | // neurons attached to it |
---|
938 | for (int i = 0; i < cell_count; i++) |
---|
939 | { |
---|
940 | if (C[i]->type == CELL_NEURON) |
---|
941 | { |
---|
942 | if (C[i]->dadlink == thisti) |
---|
943 | { |
---|
944 | f4_Cell *thneu = C[i]; |
---|
945 | out += "["; |
---|
946 | out += thneu->neuclass->name.c_str(); |
---|
947 | if (thneu->conns_count > 0) |
---|
948 | out += ", "; |
---|
949 | // connections |
---|
950 | for (int j = 0; j < thneu->conns_count; j++) |
---|
951 | { |
---|
952 | if (j > 0) out += ", "; |
---|
953 | char buf[100]; |
---|
954 | sprintf(buf, "%d", thneu->conns[j]->from->nr - thneu->nr); |
---|
955 | out += buf; |
---|
956 | out += ":"; |
---|
957 | // connection weight |
---|
958 | sprintf(buf, "%g", thneu->conns[j]->weight); |
---|
959 | out += buf; |
---|
960 | } |
---|
961 | out += "]"; |
---|
962 | } |
---|
963 | } |
---|
964 | } |
---|
965 | |
---|
966 | // sticks connected to it |
---|
967 | if (thisti->commacount >= 2) |
---|
968 | out += "("; |
---|
969 | |
---|
970 | int ccount = 1; |
---|
971 | for (int i = 0; i < cell_count; i++) |
---|
972 | { |
---|
973 | if (C[i]->type == CELL_STICK) |
---|
974 | { |
---|
975 | if (C[i]->dadlink == thisti) |
---|
976 | { |
---|
977 | while (ccount < (C[i])->anglepos) |
---|
978 | { |
---|
979 | ccount++; |
---|
980 | out += ","; |
---|
981 | } |
---|
982 | toF1GenoRec(i, out); |
---|
983 | } |
---|
984 | } |
---|
985 | } |
---|
986 | |
---|
987 | while (ccount < thisti->commacount) |
---|
988 | { |
---|
989 | ccount++; |
---|
990 | out += ","; |
---|
991 | } |
---|
992 | |
---|
993 | if (thisti->commacount >= 2) |
---|
994 | out += ")"; |
---|
995 | } |
---|
996 | |
---|
997 | |
---|
998 | |
---|
999 | // to organize an f4 genotype in a tree structure |
---|
1000 | |
---|
1001 | f4_Node::f4_Node() |
---|
1002 | { |
---|
1003 | name = "?"; |
---|
1004 | parent = NULL; |
---|
1005 | child = NULL; |
---|
1006 | child2 = NULL; |
---|
1007 | pos = -1; |
---|
1008 | |
---|
1009 | reps = 0; |
---|
1010 | prop_symbol = '\0'; |
---|
1011 | prop_increase = false; |
---|
1012 | conn_from = 0; |
---|
1013 | conn_weight = 0.0; |
---|
1014 | neuclass = NULL; |
---|
1015 | } |
---|
1016 | |
---|
1017 | f4_Node::f4_Node(string nname, f4_Node *nparent, int npos) |
---|
1018 | { |
---|
1019 | name = nname; |
---|
1020 | parent = nparent; |
---|
1021 | child = NULL; |
---|
1022 | child2 = NULL; |
---|
1023 | pos = npos; |
---|
1024 | if (parent) parent->addChild(this); |
---|
1025 | |
---|
1026 | reps = 0; |
---|
1027 | prop_symbol = '\0'; |
---|
1028 | prop_increase = false; |
---|
1029 | conn_from = 0; |
---|
1030 | conn_weight = 0.0; |
---|
1031 | neuclass = NULL; |
---|
1032 | } |
---|
1033 | |
---|
1034 | f4_Node::f4_Node(char nname, f4_Node *nparent, int npos) |
---|
1035 | { |
---|
1036 | name = nname; |
---|
1037 | parent = nparent; |
---|
1038 | child = NULL; |
---|
1039 | child2 = NULL; |
---|
1040 | pos = npos; |
---|
1041 | if (parent) parent->addChild(this); |
---|
1042 | |
---|
1043 | reps = 0; |
---|
1044 | prop_symbol = '\0'; |
---|
1045 | prop_increase = false; |
---|
1046 | conn_from = 0; |
---|
1047 | conn_weight = 0.0; |
---|
1048 | neuclass = NULL; |
---|
1049 | } |
---|
1050 | |
---|
1051 | f4_Node::~f4_Node() |
---|
1052 | { |
---|
1053 | destroy(); |
---|
1054 | } |
---|
1055 | |
---|
1056 | void f4_Node::print_tree(const f4_Node *root, int indent) |
---|
1057 | { |
---|
1058 | for (int i = 0; i < indent; i++) printf(" "); |
---|
1059 | printf("%s%s%s (%d)", root->neuclass != NULL ? "N:" : "", root->name.c_str(), root->name == "#" ? std::to_string(root->reps).c_str() : "", root->count() - 1); |
---|
1060 | if (root->name == "[") |
---|
1061 | printf(" from=%-3d weight=%g", root->conn_from, root->conn_weight); |
---|
1062 | printf("\n"); |
---|
1063 | if (root->child) print_tree(root->child, indent + 1); |
---|
1064 | if (root->child2) print_tree(root->child2, indent + 1); |
---|
1065 | } |
---|
1066 | |
---|
1067 | int f4_Node::addChild(f4_Node *nchi) |
---|
1068 | { |
---|
1069 | if (child == NULL) |
---|
1070 | { |
---|
1071 | child = nchi; |
---|
1072 | return 0; |
---|
1073 | } |
---|
1074 | if (child2 == NULL) |
---|
1075 | { |
---|
1076 | child2 = nchi; |
---|
1077 | return 0; |
---|
1078 | } |
---|
1079 | return -1; |
---|
1080 | } |
---|
1081 | |
---|
1082 | int f4_Node::removeChild(f4_Node *nchi) |
---|
1083 | { |
---|
1084 | if (nchi == child2) |
---|
1085 | { |
---|
1086 | child2 = NULL; |
---|
1087 | return 0; |
---|
1088 | } |
---|
1089 | if (nchi == child) |
---|
1090 | { |
---|
1091 | child = NULL; |
---|
1092 | return 0; |
---|
1093 | } |
---|
1094 | return -1; |
---|
1095 | } |
---|
1096 | |
---|
1097 | int f4_Node::childCount() |
---|
1098 | { |
---|
1099 | return int(child != NULL) + int(child2 != NULL); //0, 1 or 2 |
---|
1100 | } |
---|
1101 | |
---|
1102 | int f4_Node::count() const |
---|
1103 | { |
---|
1104 | int c = 1; |
---|
1105 | if (child != NULL) c += child->count(); |
---|
1106 | if (child2 != NULL) c += child2->count(); |
---|
1107 | return c; |
---|
1108 | } |
---|
1109 | |
---|
1110 | f4_Node* f4_Node::ordNode(int n) |
---|
1111 | { |
---|
1112 | int n1; |
---|
1113 | if (n == 0) return this; |
---|
1114 | n--; |
---|
1115 | if (child != NULL) |
---|
1116 | { |
---|
1117 | n1 = child->count(); |
---|
1118 | if (n < n1) return child->ordNode(n); |
---|
1119 | n -= n1; |
---|
1120 | } |
---|
1121 | if (child2 != NULL) |
---|
1122 | { |
---|
1123 | n1 = child2->count(); |
---|
1124 | if (n < n1) return child2->ordNode(n); |
---|
1125 | n -= n1; |
---|
1126 | } |
---|
1127 | return NULL; |
---|
1128 | } |
---|
1129 | |
---|
1130 | f4_Node* f4_Node::randomNode() |
---|
1131 | { |
---|
1132 | int n = count(); |
---|
1133 | // pick a random node between 0 and n-1 |
---|
1134 | return ordNode(rndUint(n)); |
---|
1135 | } |
---|
1136 | |
---|
1137 | f4_Node* f4_Node::randomNodeWithSize(int mn, int mx) |
---|
1138 | { |
---|
1139 | // try random nodes, and accept if size in range |
---|
1140 | // limit to maxlim tries |
---|
1141 | int i, n, maxlim; |
---|
1142 | f4_Node *nod = NULL; |
---|
1143 | maxlim = count(); |
---|
1144 | for (i = 0; i < maxlim; i++) |
---|
1145 | { |
---|
1146 | nod = randomNode(); |
---|
1147 | n = nod->count(); |
---|
1148 | if ((n >= mn) && (n <= mx)) return nod; |
---|
1149 | } |
---|
1150 | // failed, doesn't matter |
---|
1151 | return nod; |
---|
1152 | } |
---|
1153 | |
---|
1154 | void f4_Node::sprint(SString& out) |
---|
1155 | { |
---|
1156 | char buf2[20]; |
---|
1157 | // special case: repetition code |
---|
1158 | if (name == "#") |
---|
1159 | { |
---|
1160 | out += "#"; |
---|
1161 | sprintf(buf2, "%d", reps); |
---|
1162 | out += buf2; |
---|
1163 | } |
---|
1164 | else { |
---|
1165 | // special case: neuron connection |
---|
1166 | if (name == "[") |
---|
1167 | { |
---|
1168 | out += "["; |
---|
1169 | sprintf(buf2, "%d", conn_from); |
---|
1170 | out += buf2; |
---|
1171 | sprintf(buf2, ":%g]", conn_weight); |
---|
1172 | out += buf2; |
---|
1173 | } |
---|
1174 | else if (name == ":") |
---|
1175 | { |
---|
1176 | sprintf(buf2, ":%c%c:", prop_increase ? '+' : '-', prop_symbol); |
---|
1177 | out += buf2; |
---|
1178 | } |
---|
1179 | else if (neuclass != NULL) |
---|
1180 | { |
---|
1181 | out += "N:"; |
---|
1182 | out += neuclass->name.c_str(); |
---|
1183 | } |
---|
1184 | else |
---|
1185 | { |
---|
1186 | out += name.c_str(); |
---|
1187 | } |
---|
1188 | } |
---|
1189 | |
---|
1190 | if (child != NULL) |
---|
1191 | child->sprint(out); |
---|
1192 | // if two children, make sure last char is a '>' |
---|
1193 | if (childCount() == 2) |
---|
1194 | if (out[0] == 0) out += ">"; else |
---|
1195 | if (out[out.length() - 1] != '>') out += ">"; |
---|
1196 | |
---|
1197 | if (child2 != NULL) |
---|
1198 | child2->sprint(out); |
---|
1199 | // make sure last char is a '>' |
---|
1200 | if (out[0] == 0) out += ">"; else |
---|
1201 | if (out[out.length() - 1] != '>') out += ">"; |
---|
1202 | } |
---|
1203 | |
---|
1204 | void f4_Node::sprintAdj(char *& buf) |
---|
1205 | { |
---|
1206 | unsigned int len; |
---|
1207 | // build in a SString, with initial size |
---|
1208 | SString out; |
---|
1209 | out.reserve(int(strlen(buf)) + 2000); |
---|
1210 | |
---|
1211 | sprint(out); |
---|
1212 | len = out.length(); |
---|
1213 | |
---|
1214 | // very last '>' can be omitted |
---|
1215 | // MacKo 2023-05: after tightening parsing and removing a silent repair for missing '>' after '#', this is no longer always the case. |
---|
1216 | // For genotypes using '#', removing trailing >'s makes them invalid: /*4*/<X><N:N>X#1>> or /*4*/<X><N:N>X#1#2>>> or /*4*/<X><N:N>X#1#2#3>>>> etc. |
---|
1217 | // Such invalid genotypes with missing >'s would then require silently adding >'s, but now stricter parsing and clear information about invalid syntax is preferred. |
---|
1218 | // See also comments in f4_processRecur() case '#'. |
---|
1219 | //if (len > 1) |
---|
1220 | // if (out[len - 1] == '>') { (out.directWrite())[len - 1] = 0; out.endWrite(); }; //Macko 2023-04 "can be omitted" => was always removed in generated genotypes. |
---|
1221 | |
---|
1222 | // copy back to string |
---|
1223 | // if new is longer, reallocate buf |
---|
1224 | if (len + 1 > strlen(buf)) |
---|
1225 | { |
---|
1226 | buf = (char*)realloc(buf, len + 1); |
---|
1227 | } |
---|
1228 | strcpy(buf, out.c_str()); |
---|
1229 | } |
---|
1230 | |
---|
1231 | f4_Node* f4_Node::duplicate() |
---|
1232 | { |
---|
1233 | f4_Node *copy; |
---|
1234 | copy = new f4_Node(*this); |
---|
1235 | copy->parent = NULL; // set later |
---|
1236 | copy->child = NULL; |
---|
1237 | copy->child2 = NULL; |
---|
1238 | if (child != NULL) |
---|
1239 | { |
---|
1240 | copy->child = child->duplicate(); |
---|
1241 | copy->child->parent = copy; |
---|
1242 | } |
---|
1243 | if (child2 != NULL) |
---|
1244 | { |
---|
1245 | copy->child2 = child2->duplicate(); |
---|
1246 | copy->child2->parent = copy; |
---|
1247 | } |
---|
1248 | return copy; |
---|
1249 | } |
---|
1250 | |
---|
1251 | |
---|
1252 | void f4_Node::destroy() |
---|
1253 | { |
---|
1254 | // children are destroyed (recursively) through the destructor |
---|
1255 | if (child2 != NULL) delete child2; |
---|
1256 | if (child != NULL) delete child; |
---|
1257 | } |
---|
1258 | |
---|
1259 | // scan genotype string and build a tree |
---|
1260 | // return >1 for error (errorpos) |
---|
1261 | int f4_processRecur(const char* genot, const int genot_len, int &pos_inout, f4_Node *parent) |
---|
1262 | { |
---|
1263 | static const char *all_modifiers_no_comma = F14_MODIFIERS; //I did experiments with added comma (see all_modifiers_for_simplify below) which had the advantage of commas not breaking sequences of modifiers, thus longer sequences of modifiers (including commas) could be simplified and genetic bloat was further reduced. But since we impose a limit on the number of modifier chars in GenoOperators::simplifiedModifiers(), it would also influence commas (e.g. no more than 8 commas per sequence), so in order to leave commas entirely unlimited let's exclude them from simplification. Note that currently 'X' or any other non-F14_MODIFIERS char also separates the sequence to be simplified, so if we wanted a really intensive simplification, it should occur during development, when we know precisely which genes influence each f4_Cell. |
---|
1264 | //const char *Geno_f4::all_modifiers_for_simplify = F14_MODIFIERS ",\1"; //'\1' added to keep the number of chars even, avoid exceptions in logic and save the simple rule that the sequence is made of pairs (gene,contradictory gene), where a comma has no contradictory gene and \1 is unlikely to occur in the f4 genotype (and not allowed), so no risk it will cancel out a comma during simplification. |
---|
1265 | |
---|
1266 | |
---|
1267 | f4_Node *par = parent; |
---|
1268 | |
---|
1269 | if (pos_inout >= genot_len) |
---|
1270 | return genot_len + 1; |
---|
1271 | |
---|
1272 | while (pos_inout < genot_len) |
---|
1273 | { |
---|
1274 | const bool PRINT_PARSING_LOCATION = false; |
---|
1275 | if (PRINT_PARSING_LOCATION) |
---|
1276 | { |
---|
1277 | printf("%s\n", genot); |
---|
1278 | for (int i = 0; i < pos_inout; i++) printf(" "); |
---|
1279 | printf("^\n"); |
---|
1280 | } |
---|
1281 | switch (genot[pos_inout]) |
---|
1282 | { |
---|
1283 | case '<': |
---|
1284 | { |
---|
1285 | f4_Node *node = new f4_Node("<", par, pos_inout); |
---|
1286 | par = node; |
---|
1287 | pos_inout++; //move after '<' |
---|
1288 | int res = f4_processRecur(genot, genot_len, pos_inout, par); |
---|
1289 | if (res) return res; |
---|
1290 | if (pos_inout < genot_len) |
---|
1291 | { |
---|
1292 | res = f4_processRecur(genot, genot_len, pos_inout, par); |
---|
1293 | if (res) return res; |
---|
1294 | } |
---|
1295 | else // ran out |
---|
1296 | { |
---|
1297 | //MacKo 2023-04, more strict behavior: instead of silent repair (no visible effect to the user, genotype stays invalid but is interpreted and reported as valid), we now point out where the error is. For example <X> or <X><X or <X><N:N> |
---|
1298 | return genot_len + 1; |
---|
1299 | //old silent repair: |
---|
1300 | //node = new f4_Node(">", par, genot_len - 1); |
---|
1301 | } |
---|
1302 | return 0; // OK |
---|
1303 | } |
---|
1304 | case '>': |
---|
1305 | { |
---|
1306 | new f4_Node(">", par, pos_inout); |
---|
1307 | pos_inout++; //move after '>' |
---|
1308 | return 0; // OK |
---|
1309 | } |
---|
1310 | case '#': |
---|
1311 | { |
---|
1312 | // repetition marker |
---|
1313 | ExtValue reps; |
---|
1314 | const char* end = reps.parseNumber(genot + pos_inout + 1, ExtPType::TInt); |
---|
1315 | if (end == NULL) |
---|
1316 | return pos_inout + 1; //error |
---|
1317 | f4_Node *node = new f4_Node("#", par, pos_inout); //TODO here or elsewhere: gene mapping seems to map '#' but not the following number |
---|
1318 | node->reps = reps.getInt(); |
---|
1319 | // skip number |
---|
1320 | pos_inout += end - (genot + pos_inout); |
---|
1321 | int res = f4_processRecur(genot, genot_len, pos_inout, node); |
---|
1322 | if (res) return res; |
---|
1323 | if (pos_inout < genot_len) |
---|
1324 | { |
---|
1325 | res = f4_processRecur(genot, genot_len, pos_inout, node); |
---|
1326 | if (res) return res; |
---|
1327 | } |
---|
1328 | else // ran out |
---|
1329 | { |
---|
1330 | return genot_len + 1; //MacKo 2023-04: report an error, better to be more strict instead of a silent repair (genotype stays invalid but is interpreted and reported as valid) with non-obvious consequences? |
---|
1331 | //earlier approach - silently treating this problem (we don't ever see where the error is because it gets corrected in some way here, while parsing the genotype, and error location in the genotype is never reported): |
---|
1332 | //node = new f4_Node(">", par, genot_len - 1); // Maybe TODO: check if this was needed and if this was really the best repair operation; could happen many times in succession for some genotypes even though they were only a result of f4 operators, not manually created... and the operators should not generate invalid genotypes, right? Or maybe crossover does? Seemed like too many #n's for closing >'s; removing #n or adding > helped. Examples (remove trailing >'s to make invalid): /*4*/<X><N:N>X#1>> or /*4*/<X><N:N>X#1#2>>> or /*4*/<X><N:N>X#1#2#3>>>> etc. |
---|
1333 | // So operators somehow don't do it properly sometimes? But F4_ADD_REP adds '>'... Maybe the rule to always remove final trailing '>' was responsible? (now commented out). Since the proper syntax for # is #n ...repcode... > ...endcode..., perhaps endcode also needs '>' as the final delimiter. If we have many #'s in the genotype and the final >'s are missing, in the earlier approach we would keep adding them here as needed to ensure the syntax is valid. If we don't add '>' here silently, they must be explicitly added or else the genotype is invalid. BUT this earlier approach here only handled the situation where the genotype ended prematurely; what about cases where '>' may be needed as delimiters for # in the middle of the genotype? Or does # always concern all genes until the end, unless explicitly delimited earlier? Perhaps, if the '>' endcode delimiters are not present in the middle of the genotype, we don't know where they should be so the earlier approach would always add them only at the end of the genotype? |
---|
1334 | } |
---|
1335 | return 0; // OK |
---|
1336 | } |
---|
1337 | case ' ': |
---|
1338 | case '\n': |
---|
1339 | case '\r': |
---|
1340 | case '\t': |
---|
1341 | { |
---|
1342 | // whitespace: ignore |
---|
1343 | pos_inout++; |
---|
1344 | break; |
---|
1345 | } |
---|
1346 | case 'N': |
---|
1347 | { |
---|
1348 | int forgenorange = pos_inout; |
---|
1349 | if (genot[pos_inout + 1] != ':') |
---|
1350 | return pos_inout + 1; //error |
---|
1351 | pos_inout += 2; //skipping "N:" |
---|
1352 | unsigned int neuroclass_begin = pos_inout; |
---|
1353 | char* neuroclass_end = (char*)genot + neuroclass_begin; |
---|
1354 | NeuroClass *neuclass = GenoOperators::parseNeuroClass(neuroclass_end, ModelEnum::SHAPETYPE_BALL_AND_STICK); //advances neuroclass_end |
---|
1355 | if (neuclass == NULL) |
---|
1356 | return pos_inout + 1; //error |
---|
1357 | pos_inout += neuroclass_end - genot - neuroclass_begin; |
---|
1358 | string neutype = string(genot + neuroclass_begin, genot + pos_inout); |
---|
1359 | f4_Node *node = new f4_Node(neutype, par, forgenorange); |
---|
1360 | node->neuclass = neuclass; |
---|
1361 | par = node; |
---|
1362 | // if it continues with a colon that determines a neuron parameter (e.g. N:N:+=: ), then let the switch case for colon handle this |
---|
1363 | break; |
---|
1364 | } |
---|
1365 | case ':': |
---|
1366 | { |
---|
1367 | // neuron parameter +! -! += -= +/ or -/ |
---|
1368 | // in the future this could be generalized to all neuron properties, for example N:|:power:0.6:range:1.4, or can even use '=' or ',' instead of ':' if no ambiguity |
---|
1369 | char prop_dir, prop_symbol, prop_end[2]; // prop_end is only to ensure that neuron parameter definition is completed |
---|
1370 | if (sscanf(genot + pos_inout, ":%c%c%1[:]", &prop_dir, &prop_symbol, prop_end) != 3) |
---|
1371 | // error: incorrect format |
---|
1372 | return pos_inout + 1 + 1; |
---|
1373 | if (prop_dir != '-' && prop_dir != '+') |
---|
1374 | return pos_inout + 1 + 1; //error |
---|
1375 | switch (prop_symbol) |
---|
1376 | { |
---|
1377 | case '!': case '=': case '/': break; |
---|
1378 | default: |
---|
1379 | return pos_inout + 1 + 1; //error |
---|
1380 | } |
---|
1381 | f4_Node *node = new f4_Node(":", par, pos_inout); |
---|
1382 | node->prop_symbol = prop_symbol; |
---|
1383 | node->prop_increase = prop_dir == '+' ? true : false; // + or - |
---|
1384 | par = node; |
---|
1385 | pos_inout += 4; //skipping :ds: |
---|
1386 | break; |
---|
1387 | } |
---|
1388 | case '[': |
---|
1389 | { |
---|
1390 | double weight = 0; |
---|
1391 | int relfrom; |
---|
1392 | const char *end = parseConnection(genot + pos_inout, relfrom, weight); |
---|
1393 | if (end == NULL) |
---|
1394 | return pos_inout + 1; //error |
---|
1395 | |
---|
1396 | f4_Node *node = new f4_Node("[", par, pos_inout); |
---|
1397 | node->conn_from = relfrom; |
---|
1398 | node->conn_weight = weight; |
---|
1399 | par = node; |
---|
1400 | pos_inout += end - (genot + pos_inout); |
---|
1401 | break; |
---|
1402 | } |
---|
1403 | default: // 'X' and ',' and all modifiers and also invalid symbols - add a node. For symbols that are not valid in f4, the cell development process will give the error or repair |
---|
1404 | { |
---|
1405 | //printf("any regular character '%c'\n", genot[pos_inout]); |
---|
1406 | #define F4_SIMPLIFY_MODIFIERS //avoid long, redundant sequences like ...<X>llmlIilImmimiimmimifmfl<fifmmimilimmmiimiliffmfliIfififlliflimfliffififmiffmflllfflimlififfiiffifIr<r<... |
---|
1407 | #ifdef F4_SIMPLIFY_MODIFIERS |
---|
1408 | char *ptr = (char*)(genot + pos_inout); |
---|
1409 | string original = ""; |
---|
1410 | while (GenoOperators::strchrn0(all_modifiers_no_comma, *ptr)) //only processes a section of chars known in all_modifiers_no_comma, other characters will exit the loop |
---|
1411 | { |
---|
1412 | original += *ptr; |
---|
1413 | GenoOperators::skipWS(++ptr); //advance and ignore whitespace |
---|
1414 | } |
---|
1415 | int advanced = ptr - (genot + pos_inout); |
---|
1416 | if (advanced > 0) //found modifiers |
---|
1417 | { |
---|
1418 | string simplified = GenoOperators::simplifiedModifiers(original); |
---|
1419 | // add a node for each char in "simplified" |
---|
1420 | for (size_t i = 0; i < simplified.length(); i++) |
---|
1421 | { |
---|
1422 | int pos = GenoOperators::strchrn0(genot + pos_inout, simplified[i]) - genot; //unnecessarily finding the same char, if it occurrs multiple times in simplified |
---|
1423 | f4_Node *node = new f4_Node(simplified[i], par, pos); //location is approximate. In the simplification process we don't trace where the origin(s) of the simplified[i] gene were. We provide 'pos' as the first occurrence of simplified[i] (for example, all 'L' will have the same location assigned, but at least this is where 'L' occurred in the genotype, so in case of any modification of a node (repair, removal, whatever... even mapping of genes) the indicated gene will be one of the responsible ones) |
---|
1424 | par = node; |
---|
1425 | } |
---|
1426 | pos_inout += advanced; |
---|
1427 | } |
---|
1428 | else // genot[pos_inout] is a character not present in all_modifiers_no_comma, so treat it as a regular individual char just as it would be without simplification |
---|
1429 | { |
---|
1430 | f4_Node *node = new f4_Node(genot[pos_inout], par, pos_inout); |
---|
1431 | par = node; |
---|
1432 | pos_inout++; |
---|
1433 | } |
---|
1434 | #else |
---|
1435 | f4_Node *node = new f4_Node(genot[pos_inout], par, pos_inout); |
---|
1436 | par = node; |
---|
1437 | pos_inout++; |
---|
1438 | #endif // F4_SIMPLIFY_MODIFIERS |
---|
1439 | break; |
---|
1440 | } |
---|
1441 | } |
---|
1442 | } |
---|
1443 | |
---|
1444 | // should end with a '>' |
---|
1445 | if (par && par->name != ">") |
---|
1446 | { |
---|
1447 | //happens when pos_inout == genot_len |
---|
1448 | //return pos_inout; //MacKo 2023-04: could report an error instead of silent repair, but repair operators only work in Cells (i.e., after the f4_Node tree has been parsed without errors and Cells can start developing) so we don't want to make a fatal error because of missing '>' here. Also after conversions from Cells to text, trailing '>' is deliberately removed... and also the simplest genotype is officially X, not X>. |
---|
1449 | new f4_Node('>', par, genot_len - 1); |
---|
1450 | } |
---|
1451 | |
---|
1452 | return 0; // OK |
---|
1453 | } |
---|
1454 | |
---|
1455 | int f4_process(const char *genot, f4_Node *root) |
---|
1456 | { |
---|
1457 | int pos = 0; |
---|
1458 | int res = f4_processRecur(genot, (int)strlen(genot), pos, root); |
---|
1459 | if (res > 0) |
---|
1460 | return res; //parsing error |
---|
1461 | else if (genot[pos] != 0) |
---|
1462 | return pos + 1; //parsing OK but junk, unparsed genes left, for example /*4*/<X>N:N>whatever or /*4*/<X>X>>> |
---|
1463 | else |
---|
1464 | return 0; //parsing OK and parsed until the end |
---|
1465 | } |
---|
1466 | |
---|
1467 | const char* parseConnection(const char *fragm, int& relfrom, double &weight) |
---|
1468 | { |
---|
1469 | const char *parser = fragm; |
---|
1470 | if (*parser != '[') return NULL; |
---|
1471 | parser++; |
---|
1472 | ExtValue val; |
---|
1473 | parser = val.parseNumber(parser, ExtPType::TInt); |
---|
1474 | if (parser == NULL) return NULL; |
---|
1475 | relfrom = val.getInt(); |
---|
1476 | if (*parser != ':') return NULL; |
---|
1477 | parser++; |
---|
1478 | parser = val.parseNumber(parser, ExtPType::TDouble); |
---|
1479 | if (parser == NULL) return NULL; |
---|
1480 | weight = val.getDouble(); |
---|
1481 | if (*parser != ']') return NULL; |
---|
1482 | parser++; |
---|
1483 | return parser; |
---|
1484 | } |
---|
1485 | |
---|
1486 | /* |
---|
1487 | f4_Node* f4_processTree(const char* geno) |
---|
1488 | { |
---|
1489 | f4_Node *root = new f4_Node(); |
---|
1490 | int res = f4_processRecur(geno, 0, root); |
---|
1491 | if (res) return NULL; |
---|
1492 | //DB( printf("test f4 "); ) |
---|
1493 | DB( |
---|
1494 | if (root->child) |
---|
1495 | { |
---|
1496 | char* buf = (char*)malloc(300); |
---|
1497 | DB(printf("(%d) ", root->child->count());) |
---|
1498 | buf[0] = 0; |
---|
1499 | root->child->sprintAdj(buf); |
---|
1500 | DB(printf("%s\n", buf);) |
---|
1501 | free(buf); |
---|
1502 | } |
---|
1503 | ) |
---|
1504 | return root->child; |
---|
1505 | } |
---|
1506 | */ |
---|