1 /*
2     Copyright (C) 2017 Daniel Schultz
3 
4     This file is part of FLINT.
5 
6     FLINT is free software: you can redistribute it and/or modify it under
7     the terms of the GNU Lesser General Public License (LGPL) as published
8     by the Free Software Foundation; either version 2.1 of the License, or
9     (at your option) any later version.  See <http://www.gnu.org/licenses/>.
10 */
11 
12 #include <gmp.h>
13 #include "flint.h"
14 #include "mpoly.h"
15 
16 
mpoly_rbtree_init(mpoly_rbtree_t tree)17 void mpoly_rbtree_init(mpoly_rbtree_t tree)
18 {
19     tree->size = 0;
20     tree->head->up = tree->null;
21     tree->head->left = tree->null;
22     tree->head->right = tree->null;
23     tree->head->key = 0;
24     tree->head->col = 0;
25     tree->null->up = NULL;
26     tree->null->left = NULL;
27     tree->null->right = NULL;
28     tree->null->key = 0;
29     tree->null->col = 0;
30 }
31 
32 
_mpoly_rbnode_clear(mpoly_rbtree_t tree,mpoly_rbnode_t node,void ** dataout,slong * keysout,slong * idx)33 void _mpoly_rbnode_clear(mpoly_rbtree_t tree, mpoly_rbnode_t node,
34                                  void ** dataout, slong * keysout, slong * idx)
35 {
36     if (node->right != tree->null)
37         _mpoly_rbnode_clear(tree, node->right, dataout, keysout, idx);
38     dataout[*idx] = node->data;
39     keysout[*idx] = node->key;
40     (*idx)++;
41     if (node->left != tree->null)
42         _mpoly_rbnode_clear(tree, node->left, dataout, keysout, idx);
43     flint_free(node);
44 }
45 
46 
mpoly_rbtree_clear(mpoly_rbtree_t tree,void ** dataout,slong * keysout)47 void mpoly_rbtree_clear(mpoly_rbtree_t tree, void ** dataout, slong * keysout)
48 {
49     slong idx = 0;
50     if (tree->head->left != tree->null)
51         _mpoly_rbnode_clear(tree, tree->head->left, dataout, keysout, &idx);
52 }
53 
54 /*
55     get the node with key "rcx"
56     if such a node doesn't exist, one is created and "new" is set to 1
57 */
mpoly_rbtree_get(int * new,struct mpoly_rbtree * tree,slong rcx)58 mpoly_rbnode_struct * mpoly_rbtree_get(int * new, struct mpoly_rbtree * tree,
59                                                                      slong rcx)
60 {
61     mpoly_rbnode_struct * t, * head, * null;
62     mpoly_rbnode_struct * rax, * rdx, * r8, * r9, * r10, * r11;
63 
64     * new = 0;
65     head = tree->head;
66     null = tree->null;
67 
68     r10 = head->left;
69 
70     if (tree->size == 0)
71     {
72         rax = flint_malloc(sizeof(struct mpoly_rbnode));
73         rax->up = head;
74         rax->left = null;
75         rax->right = null;
76         rax->data = NULL;
77         rax->col = 0;
78         rax->key = rcx;
79         tree->size++;
80         * new = 1;
81         head->left = rax;
82         return rax;
83     }
84 
85 Compare:
86     r8 = r10->left;
87     r9 = r10->right;
88     if (rcx < r10->key)
89         goto GoLeft;
90     if (rcx > r10->key)
91         goto GoRight;
92 
93     rax = r10;
94     return rax;
95 
96 GoLeft:
97     if (r8 == null)
98         goto MakeNewLeft;
99     r10 = r8;
100     goto Compare;
101 
102 GoRight:
103     if (r9 == null)
104         goto MakeNewRight;
105     r10 = r9;
106     goto Compare;
107 
108 MakeNewLeft:
109     rdx = flint_malloc(sizeof(mpoly_rbnode_struct));
110     r10->left = rdx;
111     goto FixTree;
112 
113 MakeNewRight:
114     rdx = flint_malloc(sizeof(mpoly_rbnode_struct));
115     r10->right = rdx;
116 
117 FixTree:
118     rdx->up = r10;
119     rdx->left = null;
120     rdx->right = null;
121     rdx->data = NULL;
122     rdx->col = 1;
123     rdx->key = rcx;
124     tree->size++;
125     * new = 1;
126     rax = rdx;
127 
128 FixNode:
129 
130 /*Case1:*/
131     r8 = rdx->up;
132     if (r8 == head)
133     {
134         rdx->col = 0;
135         return rax;
136     }
137 
138 
139 /*Case2:*/
140     if (r8->col == 0)
141         return rax;
142 
143 /*Case3:*/
144     r9 = r8->up;
145     r10 = r9->left;
146     r11 = r9-> right;
147     if (r8 == r10)
148         r10 = r11;
149     if (r10 == null || r10->col == 0)
150         goto Case4;
151     rdx = r9;
152     r8->col = 0;
153     r9->col = 1;
154     r10->col = 0;
155     goto FixNode;
156 
157 Case4:
158     r10 = r9->up;
159 /*Case4A:*/
160     if (rdx != r8->right || r8 != r9->left)
161         goto Case4B;
162     r11 = rdx->left;
163     r9->left = rdx;
164     rdx->left = r8;
165     r8->right = r11;
166     r8->up = rdx;
167     rdx->up = r9;
168     r11->up = r8;
169     goto Case4Done;
170 
171 Case4B:
172     if (rdx != r8->left || r8 != r9->right)
173         goto Case5;
174     r11 = rdx->right;
175     r9->right = rdx;
176     rdx->right = r8;
177     r8->left = r11;
178     r8->up = rdx;
179     rdx->up = r9;
180     r11->up = r8;
181 
182 Case4Done:
183     t = rdx;
184     rdx = r8;
185     r8 = t;
186 
187 Case5:
188     if (r10->right == r9)
189         r10->right = r8;
190     if (r10->left == r9)
191         r10->left = r8;
192 
193     r8->up = r10;
194     r8->col = 0;
195     r9->up = r8;
196     r9->col = 1;
197 
198     r11 = r8->right;
199     r10 = r8->left;
200     if (rdx == r10)
201     {
202         r8->right = r9;
203         r9->left = r11;
204         r11->up = r9;
205     } else
206     {
207         r8->left = r9;
208         r9->right = r10;
209         r10->up = r9;
210     }
211 
212     return rax;
213 }
214 
215 /*
216     get the node with key "rcx"
217     if such a node doesn't exist, one is created and "new" is set to 1
218 */
mpoly_rbtree_get_fmpz(int * new,struct mpoly_rbtree * tree,fmpz_t rcx)219 mpoly_rbnode_struct * mpoly_rbtree_get_fmpz(int * new,
220                                          struct mpoly_rbtree * tree, fmpz_t rcx)
221 {
222     int cmp;
223     mpoly_rbnode_struct * t, * head, * null;
224     mpoly_rbnode_struct * rax, * rdx, * r8, * r9, * r10, * r11;
225     * new = 0;
226     head = tree->head;
227     null = tree->null;
228     r10 = head->left;
229     if (tree->size == 0)
230     {
231         rax = flint_malloc(sizeof(struct mpoly_rbnode));
232         rax->up = head;
233         rax->left = null;
234         rax->right = null;
235         rax->data = NULL;
236         rax->col = 0;
237         fmpz_init_set(&rax->key, rcx);
238         tree->size++;
239         * new = 1;
240         head->left = rax;
241         return rax;
242     }
243 Compare:
244     r8 = r10->left;
245     r9 = r10->right;
246     cmp = fmpz_cmp(rcx, &r10->key);
247     if (cmp < 0)
248         goto GoLeft;
249     if (cmp > 0)
250         goto GoRight;
251     rax = r10;
252     return rax;
253 GoLeft:
254     if (r8 == null)
255         goto MakeNewLeft;
256     r10 = r8;
257     goto Compare;
258 GoRight:
259     if (r9 == null)
260         goto MakeNewRight;
261     r10 = r9;
262     goto Compare;
263 MakeNewLeft:
264     rdx = flint_malloc(sizeof(mpoly_rbnode_struct));
265     r10->left = rdx;
266     goto FixTree;
267 MakeNewRight:
268     rdx = flint_malloc(sizeof(mpoly_rbnode_struct));
269     r10->right = rdx;
270 FixTree:
271     rdx->up = r10;
272     rdx->left = null;
273     rdx->right = null;
274     rdx->data = NULL;
275     rdx->col = 1;
276     fmpz_init_set(&rdx->key, rcx);
277     tree->size++;
278     * new = 1;
279     rax = rdx;
280 FixNode:
281 /*Case1:*/
282     r8 = rdx->up;
283     if (r8 == head)
284     {
285         rdx->col = 0;
286         return rax;
287     }
288 /*Case2:*/
289     if (r8->col == 0)
290         return rax;
291 /*Case3:*/
292     r9 = r8->up;
293     r10 = r9->left;
294     r11 = r9-> right;
295     if (r8 == r10)
296         r10 = r11;
297     if (r10 == null || r10->col == 0)
298         goto Case4;
299     rdx = r9;
300     r8->col = 0;
301     r9->col = 1;
302     r10->col = 0;
303     goto FixNode;
304 Case4:
305     r10 = r9->up;
306 /*Case4A:*/
307     if (rdx != r8->right || r8 != r9->left)
308         goto Case4B;
309     r11 = rdx->left;
310     r9->left = rdx;
311     rdx->left = r8;
312     r8->right = r11;
313     r8->up = rdx;
314     rdx->up = r9;
315     r11->up = r8;
316     goto Case4Done;
317 Case4B:
318     if (rdx != r8->left || r8 != r9->right)
319         goto Case5;
320     r11 = rdx->right;
321     r9->right = rdx;
322     rdx->right = r8;
323     r8->left = r11;
324     r8->up = rdx;
325     rdx->up = r9;
326     r11->up = r8;
327 Case4Done:
328     t = rdx;
329     rdx = r8;
330     r8 = t;
331 Case5:
332     if (r10->right == r9)
333         r10->right = r8;
334     if (r10->left == r9)
335         r10->left = r8;
336     r8->up = r10;
337     r8->col = 0;
338     r9->up = r8;
339     r9->col = 1;
340     r11 = r8->right;
341     r10 = r8->left;
342     if (rdx == r10)
343     {
344         r8->right = r9;
345         r9->left = r11;
346         r11->up = r9;
347     } else
348     {
349         r8->left = r9;
350         r9->right = r10;
351         r10->up = r9;
352     }
353     return rax;
354 }
355