1 /* justify.c */
2
3 #include "../Tree.h"
4
5 /*--------------------------------------------------------------------*/
6 /*
7 ------------------------------------------------------------
8 left-justify a tree by subtree size
9 children are linked in ascending order of their subtree size
10
11 created -- 96jun23, cca
12 ------------------------------------------------------------
13 */
14 void
Tree_leftJustify(Tree * tree)15 Tree_leftJustify (
16 Tree *tree
17 ) {
18 IV *tmetricIV, *vmetricIV ;
19 /*
20 ---------------
21 check the input
22 ---------------
23 */
24 if ( tree == NULL || tree->n < 1 ) {
25 fprintf(stderr, "\n fatal error in Tree_leftJustify(%p)"
26 "\n bad input\n", tree) ;
27 exit(-1) ;
28 }
29 /*
30 ------------------------------------------------------------------
31 set the subtree size metric, left justify and free working storage
32 ------------------------------------------------------------------
33 */
34 vmetricIV = IV_new() ;
35 IV_init(vmetricIV, tree->n, NULL) ;
36 IV_fill(vmetricIV, 1) ;
37 tmetricIV = Tree_setSubtreeImetric(tree, vmetricIV) ;
38 Tree_leftJustifyI(tree, tmetricIV) ;
39 IV_free(vmetricIV) ;
40 IV_free(tmetricIV) ;
41
42 return ; }
43
44 /*--------------------------------------------------------------------*/
45 /*
46 ------------------------------------------------------
47 left-justify a tree by a metric
48 children are linked in ascending order of their metric
49
50 created -- 96jun23, cca
51 ------------------------------------------------------
52 */
53 void
Tree_leftJustifyI(Tree * tree,IV * metricIV)54 Tree_leftJustifyI (
55 Tree *tree,
56 IV *metricIV
57 ) {
58 int i, j, k, n, nexti, prev ;
59 int *fch, *metric, *par, *sib ;
60 /*
61 ---------------
62 check the input
63 ---------------
64 */
65 if ( tree == NULL
66 || (n = tree->n) <= 0
67 || metricIV == NULL
68 || n != IV_size(metricIV)
69 || (metric = IV_entries(metricIV)) == NULL ) {
70 fprintf(stderr, "\n fatal error in Tree_leftJustifyI(%p,%p)"
71 "\n bad input\n", tree, metricIV) ;
72 exit(-1) ;
73 }
74 par = tree->par ;
75 fch = tree->fch ;
76 sib = tree->sib ;
77 /*
78 ----------------------------------------------------
79 sort all children in decreasing order of metric size
80 ----------------------------------------------------
81 */
82 for ( k = 0 ; k < n ; k++ ) {
83 for ( i = fch[k], fch[k] = -1 ; i != -1 ; i = nexti ) {
84 nexti = sib[i] ;
85 for ( j = fch[k], prev = -1 ; j != -1 ; j = sib[j] ) {
86 if ( metric[j] < metric[i] ) {
87 break ;
88 }
89 prev = j ;
90 }
91 if ( prev == -1 ) {
92 fch[k] = i ;
93 } else {
94 sib[prev] = i ;
95 }
96 sib[i] = j ;
97 }
98 }
99 /*
100 ---------------------------------------------
101 sort roots in decreasing order of metric size
102 ---------------------------------------------
103 */
104 for ( i = tree->root, tree->root = -1, prev = -1 ;
105 i != -1 ;
106 i = nexti ) {
107 nexti = sib[i] ;
108 for ( j = tree->root, prev = -1 ; j != -1 ; j = sib[j] ) {
109 if ( metric[j] < metric[i] ) {
110 break ;
111 }
112 prev = j ;
113 }
114 if ( prev == -1 ) {
115 tree->root = i ;
116 } else {
117 sib[prev] = i ;
118 }
119 sib[i] = j ;
120 }
121
122 return ; }
123
124 /*--------------------------------------------------------------------*/
125 /*
126 ------------------------------------------------------
127 left-justify a tree by a metric
128 children are linked in ascending order of their metric
129
130 created -- 96jun23, cca
131 ------------------------------------------------------
132 */
133 void
Tree_leftJustifyD(Tree * tree,DV * metricDV)134 Tree_leftJustifyD (
135 Tree *tree,
136 DV *metricDV
137 ) {
138 int i, j, k, n, nexti, prev ;
139 int *fch, *par, *sib ;
140 double *metric ;
141 /*
142 ---------------
143 check the input
144 ---------------
145 */
146 if ( tree == NULL
147 || (n = tree->n) <= 0
148 || metricDV == NULL
149 || n != DV_size(metricDV)
150 || (metric = DV_entries(metricDV)) == NULL ) {
151 fprintf(stderr, "\n fatal error in Tree_leftJustifyD(%p,%p)"
152 "\n bad input\n", tree, metricDV) ;
153 exit(-1) ;
154 }
155 par = tree->par ;
156 fch = tree->fch ;
157 sib = tree->sib ;
158 /*
159 ----------------------------------------------------
160 sort all children in decreasing order of metric size
161 ----------------------------------------------------
162 */
163 for ( k = 0 ; k < n ; k++ ) {
164 for ( i = fch[k], fch[k] = -1 ; i != -1 ; i = nexti ) {
165 nexti = sib[i] ;
166 for ( j = fch[k], prev = -1 ; j != -1 ; j = sib[j] ) {
167 if ( metric[j] < metric[i] ) {
168 break ;
169 }
170 prev = j ;
171 }
172 if ( prev == -1 ) {
173 fch[k] = i ;
174 } else {
175 sib[prev] = i ;
176 }
177 sib[i] = j ;
178 }
179 }
180 /*
181 ---------------------------------------------
182 sort roots in decreasing order of metric size
183 ---------------------------------------------
184 */
185 for ( i = tree->root, tree->root = -1, prev = -1 ;
186 i != -1 ;
187 i = nexti ) {
188 nexti = sib[i] ;
189 for ( j = tree->root, prev = -1 ; j != -1 ; j = sib[j] ) {
190 if ( metric[j] < metric[i] ) {
191 break ;
192 }
193 prev = j ;
194 }
195 if ( prev == -1 ) {
196 tree->root = i ;
197 } else {
198 sib[prev] = i ;
199 }
200 sib[i] = j ;
201 }
202
203 return ; }
204
205 /*--------------------------------------------------------------------*/
206