1#ifndef RNAPUZZLER_CONFIGTREE_H
2#define RNAPUZZLER_CONFIGTREE_H
3
4/*
5 *      RNApuzzler configtree
6 *
7 *      c  Daniel Wiegreffe, Daniel Alexander, Dirk Zeckzer
8 *      ViennaRNA package
9 */
10
11#include <stdlib.h>
12#include <math.h>
13
14#include "ViennaRNA/utils/basic.h"
15
16#include "boundingBoxes.inc"
17#include "drawingconfig.inc"
18#include "vector_math.inc"
19#include "definitions.inc"
20#include "../headers/tBaseInformation_struct.h"
21#include "../headers/config_struct.h"
22#include "../headers/AABB_struct.h"
23#include "../headers/boundingBoxes_struct.h"
24#include "../headers/configtree_struct.h"
25
26/*--------------------------------------------------------------------------*/
27
28PRIVATE void
29updateAABB(AABB     *aabb,
30           stemBox  *sBox,
31           loopBox  *lBox);
32
33
34PRIVATE short
35isExterior(const treeNode *node);
36
37
38PRIVATE treeNode *
39getExterior(treeNode *node);
40
41
42PRIVATE short
43isInteriorLoop(const treeNode *node);
44
45
46PRIVATE short
47isMultiLoop(const treeNode *node);
48
49
50/**
51 * @brief buildConfigtree
52 * @param pair_table
53 *      - definition of the RNAs pairing
54 * @param baseInformation
55 *      - array of tBaseInformation that grants information about the RNA
56 *        (only config is needed here)
57 * @param x
58 * @param y
59 * @param bulge
60 *      - distance between regular stem and bulge base
61 * @return
62 *      - a configtree build from the given RNA pairing.
63 *        gives information about all configurations (config) applied to the RNA.
64 */
65PRIVATE treeNode *
66buildConfigtree(const short *const      pair_table,
67                const tBaseInformation  *baseInformation,
68                const double            *x,
69                const double            *y,
70                const double            bulge);
71
72
73PRIVATE void
74updateBoundingBoxes(treeNode                          *node,
75                    const vrna_plot_options_puzzler_t *puzzler);
76
77
78/**
79 * @brief applyChangesToConfigAndBoundingBoxes
80 *      Function to apply a set of config changes to the given treenode.
81 *
82 *      By passing -1.0 to radiusNew you will apply the minimum possible radius for this loop while not allowing to shrink the loop.
83 *      In case it would actually shrink a default relative increase is applied to the radius.
84 *
85 *      By passing 0.0 to radiusNew you set the minimum possible radius no matter if there would be some shrinking or not.
86 * @param tree the node to change
87 * @param deltaCfg array of angles to change (in degree)
88 * @param radiusNew desired radius to set while applying deltas
89 * @param puzzler
90 * @return 1 if the changes were applied, 0 otherwise
91 */
92PRIVATE void
93applyChangesToConfigAndBoundingBoxes(treeNode                           *tree,
94                                     const double                       *deltaCfg,
95                                     const double                       radiusNew,
96                                     const vrna_plot_options_puzzler_t  *puzzler);
97
98
99/**
100 * @brief translateBoundingBoxes
101 *      - Performs a translation of a whole branch by a given vector.
102 *        Used to apply changes in config to the tree and its bounding boxes.
103 * @param tree
104 *      - tree that is being translated
105 * @param vector
106 *      - translation vector as double array[2]
107 */
108PRIVATE void
109translateBoundingBoxes(treeNode     *tree,
110                       const double *vector);
111
112
113/**
114 * @brief getChildIndex
115 *      - gets the index of child node where to find the node with given ID.
116 * @param tree
117 *      - configtree you want to search in.
118 * @param childID
119 *      - ID of childnode you are looking for.
120 * @return
121 *      - child index or -1 if tree does not contain such a childnode.
122 */
123PRIVATE int
124getChildIndex(const treeNode  *tree,
125              const int       childID);
126
127
128/**
129 * @brief getChildAngle
130 *      - Calculates the angle of a given child node (given by ID) at a loop.
131 *        This child does not need to be a direct child node but can be any sort of grand child.
132 *        If the given node is a child of the loop, the rotation angle of its center node
133 *        will be calculated.
134 * @param root
135 *      - tree node acting as parent loop
136 * @param node
137 *      - child node of which you want to know the angle
138 * @return
139 *      - angle of child node
140 *        the resulting angle might be smaller than 0° or greater than 360°
141 */
142PRIVATE double
143getChildAngle(const treeNode  *root,
144              const treeNode  *child);
145
146
147/**
148 * @brief getChildAngleByIndex
149 *      - Calculates the clockwise angle of a given child node (given by name) at a loop.
150 *        This child needs to be a direct child node
151 *        The rotation angle of its center node will be calculated.
152 * @param parentNode
153 *      - tree node acting as parent loop
154 * @param childIndex
155 *      - index of child node of which you want to know the angle
156 * @return
157 *      - angle of child node
158 *        the resulting angle might be smaller than 0° or greater than 360°
159 */
160PRIVATE double
161getChildAngleByIndex(const treeNode *parentNode,
162                     const int      childIndex);
163
164
165/**
166 * @brief getLoopCenter
167 *      - Getter for the center coordinates of a tree node's loop.
168 * @param node
169 *      - your tree node
170 * @param p
171 *      - double[2] return value for the loop's center coordinates
172 */
173PRIVATE void
174getLoopCenter(const treeNode  *node,
175              double          p[2]);
176
177
178/**
179 * @brief getStemCenter
180 *      - Getter for the center coordinates of a tree node's stem.
181 * @param node
182 *      - your tree node
183 * @param p
184 *      - double[2] return value for the stem's center coordinates
185 */
186PRIVATE void
187getStemCenter(const treeNode  *node,
188              double          p[2]);
189
190
191/**
192 * @brief getChildNode
193 *      - searches for the node with given childID in a configtree.
194 * @param tree
195 *      - configtree you want to search in.
196 * @param childID
197 *      - ID of childnode you are looking for.
198 * @return
199 *      - ptr to node or NULL if tree does not contain such a childnode.
200 */
201PRIVATE treeNode *
202getChildNode(treeNode   *tree,
203             const int  childID);
204
205
206PRIVATE treeNode *
207getParent(const treeNode *node);
208
209
210PRIVATE treeNode *
211getChild(const treeNode *node,
212         const int      index);
213
214
215PRIVATE char
216getNodeName(const treeNode *node);
217
218
219PRIVATE int
220getNodeID(const treeNode *node);
221
222
223PRIVATE void
224printTree(const treeNode  *node,
225          const int       level);
226
227
228PRIVATE int
229countSubtreeNodes(const treeNode *node);
230
231
232PRIVATE int
233collectSubtreeNodes(treeNode          *node,
234                    treeNode **const  allNodes,
235                    const int         index);
236
237
238PRIVATE int
239countAncestorNodes(const treeNode *node);
240
241
242PRIVATE void
243collectAncestorNodes(const treeNode   *node,
244                     treeNode **const ancestorList);
245
246
247PRIVATE double
248getPairedAngle(const treeNode *node);
249
250
251PRIVATE void
252freeTree(treeNode *node);
253
254
255PRIVATE void
256updateAABB(AABB     *aabb,
257           stemBox  *sBox,
258           loopBox  *lBox)
259{
260  const double  stem_ea[2] = {
261    sBox->e[0] * sBox->a[0],
262    sBox->e[0] * sBox->a[1]
263  };
264  const double  stem_eb[2] = {
265    sBox->e[1] * sBox->b[0],
266    sBox->e[1] * sBox->b[1]
267  };
268
269  int           numPoints = 6 + sBox->bulgeCount;
270
271  /* array of relevant points */
272  double        **p = (double **)vrna_alloc(numPoints * sizeof(double *));
273
274  for (int i = 0; i < numPoints; i++)
275
276    p[i] = (double *)vrna_alloc(2 * sizeof(double));
277
278  /* corners of stem */
279  p[0][0] = sBox->c[0] - stem_ea[0] + stem_eb[0];
280  p[0][1] = sBox->c[1] - stem_ea[1] + stem_eb[1];
281  p[1][0] = sBox->c[0] + stem_ea[0] + stem_eb[0];
282  p[1][1] = sBox->c[1] + stem_ea[1] + stem_eb[1];
283  p[2][0] = sBox->c[0] + stem_ea[0] - stem_eb[0];
284  p[2][1] = sBox->c[1] + stem_ea[1] - stem_eb[1];
285  p[3][0] = sBox->c[0] - stem_ea[0] - stem_eb[0];
286  p[3][1] = sBox->c[1] - stem_ea[1] - stem_eb[1];
287
288  /* lower left of loop AABB */
289  p[4][0] = lBox->c[0] - lBox->r;
290  p[4][1] = lBox->c[1] - lBox->r;
291  /* upper right of loop AABB */
292  p[5][0] = lBox->c[0] + lBox->r;
293  p[5][1] = lBox->c[1] + lBox->r;
294
295  /* bulge points */
296  double pPrev[2], pNext[2];
297  for (int i = 0; i < sBox->bulgeCount; i++)
298
299    getBulgeCoordinates(sBox, i, pPrev, p[6 + i], pNext);
300
301  /* set aabb */
302  aabb->min[0]  = p[0][0];
303  aabb->min[1]  = p[0][1];
304  aabb->max[0]  = p[0][0];
305  aabb->max[1]  = p[0][1];
306  for (int i = 1; i < numPoints; i++) {
307    if (aabb->min[0] > p[i][0])
308      aabb->min[0] = p[i][0];
309
310    if (aabb->min[1] > p[i][1])
311      aabb->min[1] = p[i][1];
312
313    if (aabb->max[0] < p[i][0])
314      aabb->max[0] = p[i][0];
315
316    if (aabb->max[1] < p[i][1])
317      aabb->max[1] = p[i][1];
318  }
319
320  /* free allocated memory */
321  for (int i = 0; i < numPoints; i++)
322
323    free(p[i]);
324  free(p);
325}
326
327
328PRIVATE void
329updateBoundingBoxes(treeNode                          *node,
330                    const vrna_plot_options_puzzler_t *puzzler)
331{
332  /*
333   * fix this node's loop
334   * then for each child fix the stem and bulges
335   * and call recursively
336   */
337
338  if (!isExterior(node)) {
339    long    numStemBackBones            = lround((2.0 * node->sBox->e[0]) / puzzler->unpaired);
340    double  stemLength                  = puzzler->unpaired * numStemBackBones;
341    double  distanceStemEndToLoopCenter = sqrt(
342      node->cfg->radius * node->cfg->radius - 0.25 * puzzler->paired * puzzler->paired);
343    double  distanceStemCenterToLoopCenter = 0.5 * stemLength + distanceStemEndToLoopCenter;
344    node->lBox->c[0]  = node->sBox->c[0] + distanceStemCenterToLoopCenter * node->sBox->a[0];
345    node->lBox->c[1]  = node->sBox->c[1] + distanceStemCenterToLoopCenter * node->sBox->a[1];
346    node->lBox->r     = node->cfg->radius;
347
348    updateAABB(&(node->aabb), node->sBox, node->lBox);
349  }
350
351  double childAngleRad = 0.0;
352
353  for (int i = 0; i < node->childCount; i++) {
354    treeNode  *child  = getChild(node, i);
355    stemBox   *sBox   = child->sBox;
356    loopBox   *lBox   = child->lBox;
357
358    double    parentLoopCenter[2];
359    if (isExterior(node)) {
360      parentLoopCenter[0] = lBox->c[0];
361      parentLoopCenter[1] = EXTERIOR_Y;
362    } else {
363      getLoopCenter(node, parentLoopCenter);
364    }
365
366    /* fix the stem's extensions */
367    long    numStemBackBones  = lround((2.0 * sBox->e[0]) / puzzler->unpaired);
368    double  stemLength        = puzzler->unpaired * numStemBackBones;
369    sBox->e[0]  = 0.5 * stemLength;
370    sBox->e[1]  = 0.5 * puzzler->paired;
371
372    /* fix the stem's directions */
373    if (isExterior(node))
374      childAngleRad = MATH_PI;
375    else
376      childAngleRad += getArcAngle(node->cfg, i);
377
378    double aFixed[2];
379    if (isExterior(node)) {
380      aFixed[0] = 0.0;
381      aFixed[1] = 1.0;
382    } else {
383      double gamma = childAngleRad - MATH_PI;
384      rotateVectorByAngle(node->sBox->a, gamma, aFixed);
385    }
386
387    sBox->a[0]  = aFixed[0];
388    sBox->a[1]  = aFixed[1];
389
390    double bFixed[2];
391    normal(aFixed, bFixed);
392    bFixed[0]   *= -1;
393    bFixed[1]   *= -1;
394    sBox->b[0]  = bFixed[0];
395    sBox->b[1]  = bFixed[1];
396
397    double  s0 = 0;
398    if (!isExterior(node))
399
400      s0 = sqrt(node->cfg->radius * node->cfg->radius - 0.25 * puzzler->paired * puzzler->paired);
401
402    double  distanceStemCenter = s0 + 0.5 * stemLength;
403
404    /* fix the stem's position */
405    sBox->c[0]  = parentLoopCenter[0] + distanceStemCenter * aFixed[0];
406    sBox->c[1]  = parentLoopCenter[1] + distanceStemCenter * aFixed[1];
407
408    if (stemLength == 0)
409
410      sBox->e[0] = EPSILON_7;
411  }
412
413  for (int i = 0; i < node->childCount; i++)
414
415    updateBoundingBoxes(getChild(node, i), puzzler);
416}
417
418
419PRIVATE void
420applyChangesToConfigAndBoundingBoxes(treeNode                           *tree,
421                                     const double                       *deltaCfg,
422                                     const double                       radiusNew,
423                                     const vrna_plot_options_puzzler_t  *puzzler)
424{
425  /* Apply all changes to config */
426  config *cfg = tree->cfg;
427
428  /* start with adjusting config radius and angles */
429  cfgApplyChanges(cfg, getNodeName(tree), deltaCfg, radiusNew, puzzler);
430
431  /* apply changes of config to bounding boxes */
432  updateBoundingBoxes(tree, puzzler);
433}
434
435
436PRIVATE void
437freeBulges(stemBox *sBox)
438{
439  if (sBox->bulges != NULL) {
440    for (int currentBulge = 0; currentBulge < sBox->bulgeCount; currentBulge++)
441
442      free(sBox->bulges[currentBulge]);
443    free(sBox->bulges);
444  }
445}
446
447
448PRIVATE void
449freeTree(treeNode *node)
450{
451  for (int currentChild = 0; currentChild < node->childCount; currentChild++)
452
453    freeTree(getChild(node, currentChild));
454
455  if (node->cfg)
456
457    cfgFreeConfig(node->cfg);
458
459  if (node->children)
460
461    free(node->children);
462
463  if (node->lBox)
464
465    free(node->lBox);
466
467  if (node->sBox) {
468    freeBulges(node->sBox);
469    free(node->sBox);
470  }
471
472  free(node);
473}
474
475
476PRIVATE int
477countSubtreeNodes(const treeNode *node)
478{
479  int count = 1;   /* count this node */
480
481  for (int currentChild = 0; currentChild < node->childCount; currentChild++)
482    /* count children and add child count */
483    count += countSubtreeNodes(getChild(node, currentChild));
484
485  return count;
486}
487
488
489PRIVATE int
490countAncestorNodes(const treeNode *node)
491{
492  int       count = 0;
493
494  treeNode  *ancestor = getParent(node);
495
496  while (ancestor != NULL) {
497    ++count;
498    ancestor = getParent(ancestor);
499  }
500
501  return count;
502}
503
504
505PRIVATE int
506collectSubtreeNodes(treeNode          *node,
507                    treeNode **const  allNodes,
508                    const int         currentIndex)
509{
510  allNodes[currentIndex] = node;
511  int nextIndex = currentIndex + 1;   /* increase index as this one was just taken */
512
513  for (int currentChild = 0; currentChild < node->childCount; currentChild++)
514
515    nextIndex = collectSubtreeNodes(getChild(node, currentChild), allNodes, nextIndex);
516
517  return nextIndex;
518}
519
520
521PRIVATE void
522collectAncestorNodes(const treeNode   *node,
523                     treeNode **const ancestorList)
524{
525  int       currentIndex  = 0;
526  treeNode  *ancestor     = getParent(node);
527
528  while (ancestor != NULL) {
529    ancestorList[currentIndex] = ancestor;
530    ++currentIndex;
531    ancestor = getParent(ancestor);
532  }
533}
534
535
536PRIVATE double
537getPairedAngle(const treeNode *node)
538{
539  /* get the current node's stem's bounding wedge */
540  stemBox *sBox = node->sBox;
541  double  pStemTopCorner[2];
542
543  pStemTopCorner[0] = sBox->c[0] + sBox->e[0] * sBox->a[0] + sBox->e[1] * sBox->b[0];
544  pStemTopCorner[1] = sBox->c[1] + sBox->e[0] * sBox->a[1] + sBox->e[1] * sBox->b[1];
545  double  pLoopCenter[2];
546  getLoopCenter(node, pLoopCenter);
547  double  vLoopCenterToStemTopCorner[2];
548  vector(pLoopCenter, pStemTopCorner, vLoopCenterToStemTopCorner);
549  double  vLoopCenterToStemCenter[2] = {
550    (-1) * sBox->a[0], (-1) * sBox->a[1]
551  };
552  double  minOuterAngle =
553    angleBetweenVectors2D(vLoopCenterToStemCenter, vLoopCenterToStemTopCorner);
554
555  /* all arcs share the same stem angle */
556  double  stemAngle = 2 * minOuterAngle;
557  return stemAngle;
558}
559
560
561PRIVATE short
562isExterior(const treeNode *node)
563{
564  return getNodeID(node) == 0;
565}
566
567
568treeNode *
569getExterior(treeNode *node)
570{
571  treeNode *exteriorCandidate = node;
572
573  while (!isExterior(exteriorCandidate))
574
575    exteriorCandidate = getParent(exteriorCandidate);
576
577  return exteriorCandidate;
578}
579
580
581PRIVATE short
582isInteriorLoop(const treeNode *node)
583{
584  return
585    !isExterior(node)
586    && node->childCount == 1;
587}
588
589
590PRIVATE short
591isMultiLoop(const treeNode *node)
592{
593  return
594    !isExterior(node)
595    && node->childCount > 1;
596}
597
598
599PRIVATE int
600getNodeID(const treeNode *node)
601{
602  if (node != NULL)
603    return node->id;
604  else
605    return -1;
606}
607
608
609PRIVATE char
610getNodeName(const treeNode *node)
611{
612  /**
613   * @brief cfgMotivBlank
614   *      - name of exterior loops and small bulge loops
615   *        initialized at cfgGenerateMotivs
616   */
617  const char  cfgMotivBlank = '_';
618
619  int         id = getNodeID(node);
620
621  if (id == -1)
622
623    return cfgMotivBlank;
624
625  int   motivId = (id + 33) % 128;
626  while (motivId < 33)
627
628    motivId = (motivId + 33) % 128;
629  char  motiv = (char)motivId;
630
631  return motiv;
632}
633
634
635PRIVATE void
636setChild(treeNode   *parent,
637         const int  index,
638         treeNode   *child)
639{
640  if (0 <= index && index < parent->childCount)
641
642    parent->children[index] = child;
643}
644
645
646/**
647 * @brief treeGetChildCount
648 *      - counts the number of children this loop will have in the configtree
649 * @param loopStart
650 *      - index of the loops first base
651 * @param pair_table
652 *      - the RNA's pairing information
653 * @return
654 *      - number of child nodes
655 */
656PRIVATE int
657treeGetChildCount(const int           loopStart,
658                  const short *const  pair_table)
659{
660  int childCount = 0;
661
662  int end = pair_table[loopStart];
663
664  for (int i = loopStart + 1; i < end; ++i) {
665    if (pair_table[i] > i) {
666      /* found new stem */
667      childCount++;
668      i = pair_table[i];
669    }
670  }
671  return childCount;
672}
673
674
675/**
676 * @brief createTreeNode
677 *      - this method can be referred to as a constructor method for configtree nodes.
678 * @param parent
679 *      - parent node (the prior loop), NULL for the root node
680 * @param loopStart
681 *      - index of the loops first node, 1 for root node
682 * @param stemStart
683 *      - index of the prior stems first node, -1 for root node
684 * @param pair_table
685 *      - the RNA's pairing information
686 * @param cfg
687 *      - the configuration found in baseInformation for that loop.
688 *        NULL for exterior loop (root node)
689 * @return
690 *      - an initialized configtree tBaseInformation with set parent, loopStart, cfg, childCount and initialized children array
691 */
692PRIVATE treeNode *
693createTreeNode(const int          id,
694               treeNode           *parent,
695               const int          loopStart,
696               const int          stemStart,
697               const short *const pair_table,
698               config             *cfg)
699{
700  /* allocate children array */
701  int childCount;
702
703  if (cfg == NULL)
704    childCount = treeGetChildCount(0, pair_table);
705  else
706    childCount = treeGetChildCount(loopStart, pair_table);
707
708  treeNode  **children = (childCount > 0) ? (treeNode **)vrna_alloc(childCount * sizeof(treeNode *))
709                         : NULL;
710
711  treeNode  *node = (treeNode *)vrna_alloc(1 * sizeof(treeNode));
712
713  node->id = id;
714
715  node->parent      = parent;
716  node->children    = children;
717  node->childCount  = childCount;
718
719  node->cfg         = cfg;
720  node->loop_start  = loopStart;
721  node->stem_start  = stemStart;
722
723  node->lBox  = NULL;
724  node->sBox  = NULL;
725
726  return node;
727}
728
729
730/* stem - loop recursion */
731PRIVATE treeNode *
732treeHandleStem(treeNode               *parent,
733               int                    *nodeID,
734               const int              stemStart,
735               const short *const     pair_table,
736               const tBaseInformation *baseInformation);
737
738
739/**
740 * @brief treeHandleLoop
741 *      - method for configtree construction.
742 *        uses recursive calls alternating with treeHandleStem method to get the whole RNA
743 * @param parent
744 *      - parent node of the current loop in configtree
745 * @param loopStart
746 *      - index of the loop's first base
747 * @param stemStart
748 *      - index of the prior stem's first base
749 * @param pairTable
750 *      - the RNA's pairing information
751 * @param baseInformation
752 *      - array of tBaseInformation annotations (grants config)
753 * @return
754 *      - pointer to the subtree (configtree) that has this loop as root
755 */
756PRIVATE treeNode *
757treeHandleLoop(treeNode               *parent,
758               int                    *nodeID,
759               const int              loopStart,
760               const int              stemStart,
761               const short *const     pair_table,
762               const tBaseInformation *baseInformation)
763{
764  int       addedChildren = 0;
765
766  treeNode  *subtree = createTreeNode(
767    *nodeID,
768    parent,
769    loopStart,
770    stemStart,
771    pair_table,
772    baseInformation[loopStart].config);
773
774  int end = pair_table[loopStart];
775
776  for (int i = loopStart + 1; i < end; ++i) {
777    if (pair_table[i] > i) {
778      /* found new stem */
779      treeNode *child = treeHandleStem(subtree, nodeID, i, pair_table, baseInformation);
780      child->parent = subtree;
781      setChild(subtree, addedChildren, child);
782      addedChildren++;
783
784      i = pair_table[i];
785    }
786  }
787
788  return subtree;
789}
790
791
792/**
793 * @brief treeHandleStem
794 *      - method for configtree construction.
795 *        uses recursive calls alternating with treeHandleLoop method to get the whole RNA
796 * @param parent
797 *      - parent node of the current loop in configtree
798 * @param stemStart
799 *      - index of the stem's first base
800 * @param pair_table
801 *      - the RNA's pairing information
802 * @param baseInformation
803 *      - array of tBaseInformation annotations (grants config)
804 * @return
805 *      - pointer to the cunsecutive subtree (configtree) that is created from the consecutive loop
806 */
807PRIVATE treeNode *
808treeHandleStem(treeNode               *parent,
809               int                    *nodeID,
810               const int              stemStart,
811               const short *const     pair_table,
812               const tBaseInformation *baseInformation)
813{
814  ++(*nodeID);
815  int       i = stemStart;
816  while (baseInformation[i].config == NULL)
817
818    ++i;
819
820  treeNode  *child = treeHandleLoop(parent, nodeID, i, stemStart, pair_table, baseInformation);
821  return child;
822}
823
824
825/**
826 * @brief buildBoundingBoxes
827 * @param tree
828 * @param pair_table
829 * @param baseInformation
830 * @param x
831 * @param y
832 * @param bulge
833 *      - distance between regular stem and bulge base
834 */
835PRIVATE void
836buildBoundingBoxes(treeNode               *tree,
837                   const short *const     pair_table,
838                   const tBaseInformation *baseInformation,
839                   const double           *x,
840                   const double           *y,
841                   const double           bulge)
842{
843  short isRoot = (tree->parent == NULL);
844
845  if (!isRoot) {
846    loopBox *lBox = buildLoopBox(tree->loop_start, pair_table, baseInformation, x, y);
847    stemBox *sBox = buildStemBox(tree->stem_start, tree->loop_start, pair_table, x, y, bulge);
848
849    lBox->parent  = tree;
850    sBox->parent  = tree;
851
852    tree->lBox  = lBox;
853    tree->sBox  = sBox;
854
855    updateAABB(&(tree->aabb), sBox, lBox);
856  }
857
858  for (int currentChild = 0; currentChild < tree->childCount; currentChild++) {
859    treeNode *child = getChild(tree, currentChild);
860    buildBoundingBoxes(child, pair_table, baseInformation, x, y, bulge);
861  }
862}
863
864
865/* documentation at header file */
866PRIVATE treeNode *
867buildConfigtree(const short *const      pair_table,
868                const tBaseInformation  *baseInformation,
869                const double            *x,
870                const double            *y,
871                const double            bulge)
872{
873  /* create root */
874  int       nodeID  = 0;
875  treeNode  *root   = createTreeNode(nodeID, NULL, 1, -1, pair_table, NULL);
876
877  int       addedChildren = 0;
878  int       length        = pair_table[0];
879
880  for (int i = 1; i < length; ++i) {
881    if (pair_table[i] > i) {
882      /* found stem */
883      treeNode *child = treeHandleStem(root, &nodeID, i, pair_table, baseInformation);
884      setChild(root, addedChildren, child);
885      addedChildren++;
886
887      i = pair_table[i];
888    }
889  }
890
891  buildBoundingBoxes(root, pair_table, baseInformation, x, y, bulge);
892
893  return root;
894}
895
896
897/**
898 * @brief translateBoundingBoxesByVector
899 *      - Performs a translation of a whole branch by a given vector.
900 *        Used to apply changes in config to the tree and its bounding boxes.
901 * @param tree
902 *      - tree that is being translated
903 * @param vector
904 *      - translation vector as double array[2]
905 */
906PRIVATE void
907translateBoundingBoxes(treeNode     *tree,
908                       const double *vector)
909{
910  translateStemBox(tree->sBox, vector);
911  translateLoopBox(tree->lBox, vector);
912  updateAABB(&(tree->aabb), tree->sBox, tree->lBox);
913
914  for (int currentChild = 0; currentChild < tree->childCount; currentChild++)
915
916    translateBoundingBoxes(getChild(tree, currentChild), vector);
917}
918
919
920/**
921 * @brief getChildIndex
922 *      - gets the index of child node where to find the node with given name.
923 * @param tree
924 *      - configtree you want to search in.
925 * @param childID
926 *      - ID of childnode you are looking for.
927 * @return
928 *      - child index or -1 if tree does not contain such a childnode.
929 */
930PRIVATE int
931getChildIndex(const treeNode  *tree,
932              const int       childID)
933{
934  /* check if there are further nodes to check */
935  int childIndex = tree->childCount - 1;
936
937  for (int currentChild = 0;
938       currentChild < tree->childCount;
939       ++currentChild) {
940    treeNode *child = getChild(tree, currentChild);
941
942    if (getNodeID(child) > childID) {
943      childIndex = currentChild - 1;
944      break;
945    }
946  }
947
948  return childIndex;
949}
950
951
952/**
953 * @brief getChildAngle
954 *      - Calculates the clockwise angle of a given child node (given by name) at a loop.
955 *        This child needs to be a direct child node
956 *        The rotation angle of its center node will be calculated.
957 * @param parentNode
958 *      - tree node acting as parent loop
959 * @param childNode
960 *      - child node of which you want to know the angle
961 * @return
962 *      - angle of child node
963 *        the resulting angle might be smaller than 0° or greater than 360°
964 */
965PRIVATE double
966getChildAngle(const treeNode  *parentNode,
967              const treeNode  *childNode)
968{
969  double  parentLoopCenter[2] = {
970    parentNode->lBox->c[0], parentNode->lBox->c[1]
971  };
972  double  parentStemCenter[2] = {
973    parentNode->sBox->c[0], parentNode->sBox->c[1]
974  };
975  double  parentLoopStemVector[2];
976
977  vector(parentLoopCenter, parentStemCenter, parentLoopStemVector);
978
979  double  childLoopCenter[2] = {
980    childNode->lBox->c[0], childNode->lBox->c[1]
981  };
982  double  angle = anglePtPtPt2D(parentStemCenter, parentLoopCenter, childLoopCenter);
983
984  if (!isToTheRightPointVector(parentLoopCenter, parentLoopStemVector, childLoopCenter))
985
986    angle = MATH_TWO_PI - angle;
987
988  return angle;
989}
990
991
992/**
993 * @brief getChildAngleByIndex
994 *      - Calculates the clockwise angle of a given child node (given by name) at a loop.
995 *        This child needs to be a direct child node
996 *        The rotation angle of its center node will be calculated.
997 * @param parentNode
998 *      - tree node acting as parent loop
999 * @param childIndex
1000 *      - index of child node of which you want to know the angle
1001 * @return
1002 *      - angle of child node
1003 *        the resulting angle might be smaller than 0° or greater than 360°
1004 */
1005PRIVATE double
1006getChildAngleByIndex(const treeNode *parentNode,
1007                     const int      childIndex)
1008{
1009  return getChildAngle(parentNode, getChild(parentNode, childIndex));
1010}
1011
1012
1013/**
1014 * @brief getLoopCenter
1015 *      - Getter for the center coordinates of a tree node's loop.
1016 * @param node
1017 *      - your tree node
1018 * @param p
1019 *      - double[2] return value for the loop's center coordinates
1020 */
1021PRIVATE void
1022getLoopCenter(const treeNode  *node,
1023              double          p[2])
1024{
1025  getLBoxCenter(node->lBox, p);
1026}
1027
1028
1029/**
1030 * @brief getStemCenter
1031 *      - Getter for the center coordinates of a tree node's stem.
1032 * @param node
1033 *      - your tree node
1034 * @param p
1035 *      - double[2] return value for the stem's center coordinates
1036 */
1037PRIVATE void
1038getStemCenter(const treeNode  *node,
1039              double          p[2])
1040{
1041  getSBoxCenter(node->sBox, p);
1042}
1043
1044
1045/**
1046 * @brief getChildNode
1047 *      - searches for the node with given childname in a configtree.
1048 * @param tree
1049 *      - configtree you want to search in.
1050 * @param childID
1051 *      - ID of childnode you are looking for.
1052 * @return
1053 *      - ptr to node or NULL if tree does not contain such a childnode.
1054 */
1055PRIVATE treeNode *
1056getChildNode(treeNode   *tree,
1057             const int  childID)
1058{
1059  short treeIsRoot = isExterior(tree);
1060
1061  /* check if this is the wanted node */
1062  if (!treeIsRoot) {
1063    if (getNodeID(tree) == childID)
1064
1065      return tree;
1066  }
1067
1068  /* get index of next child on our path */
1069  treeNode *child = getChild(tree, getChildIndex(tree, childID));
1070
1071  if (child == NULL)
1072    return NULL;
1073  else
1074    return getChildNode(child, childID);
1075}
1076
1077
1078PRIVATE treeNode *
1079getChild(const treeNode *node,
1080         const int      index)
1081{
1082  if (node == NULL)
1083    return NULL;
1084  else if (index < 0)
1085    return NULL;
1086  else if (index >= node->childCount)
1087    return NULL;
1088  else
1089    return node->children[index];
1090}
1091
1092
1093PRIVATE treeNode *
1094getParent(const treeNode *node)
1095{
1096  if (node == NULL)
1097    return NULL;
1098  else
1099    return node->parent;
1100}
1101
1102
1103#endif
1104