1 /************************************************************************/
2 /* */
3 /* Manage field hierarchy. */
4 /* */
5 /************************************************************************/
6
7 # include "docBaseConfig.h"
8
9 # include <stdlib.h>
10
11 # include <appDebugon.h>
12
13 # include "docDocumentField.h"
14
15 /************************************************************************/
16 /* */
17 /* Insert a child field into a field or into the root of a document */
18 /* tree. */
19 /* */
20 /************************************************************************/
21
docInsertFieldAt(DocumentField * parent,ChildFields * cf,DocumentField * df,int pos)22 static int docInsertFieldAt( DocumentField * parent,
23 ChildFields * cf,
24 DocumentField * df,
25 int pos )
26 {
27 DocumentField ** fresh;
28 int i;
29
30 fresh= (DocumentField **)realloc( cf->cfChildren,
31 ( cf->cfChildCount+ 1 )* sizeof(DocumentField *) );
32 if ( ! fresh )
33 { LXDEB(cf->cfChildCount,fresh); return -1; }
34 cf->cfChildren= fresh;
35
36 for ( i= cf->cfChildCount; i > pos; i-- )
37 {
38 cf->cfChildren[i]= cf->cfChildren[i-1];
39 cf->cfChildren[i]->dfNumberInParent= i;
40 }
41 cf->cfChildren[pos]= df;
42 cf->cfChildren[pos]->dfNumberInParent= pos;
43 df->dfParent= parent;
44
45 cf->cfChildCount++;
46
47 return 0;
48 }
49
docInsertChildField(DocumentField * parent,ChildFields * cf,DocumentField * df)50 int docInsertChildField( DocumentField * parent,
51 ChildFields * cf,
52 DocumentField * df )
53 {
54 int pos;
55
56 pos= cf->cfChildCount- 1;
57 while( pos >= 0 && docCompareEditPositions(
58 &(df->dfHeadPosition),
59 &(cf->cfChildren[pos]->dfTailPosition) ) < 0 )
60 { pos--; }
61 pos++;
62
63 return docInsertFieldAt( parent, cf, df, pos );
64 }
65
66 /************************************************************************/
67 /* */
68 /* Delete a field from its parent: Replace it with its children. */
69 /* */
70 /************************************************************************/
71
docDeleteChildField(ChildFields * cf,DocumentField * df)72 int docDeleteChildField( ChildFields * cf,
73 DocumentField * df )
74 {
75 int pos= df->dfNumberInParent;
76
77 if ( df->dfNumberInParent < 0 ||
78 df->dfNumberInParent >= cf->cfChildCount )
79 {
80 LLLDEB(df->dfFieldNumber,df->dfNumberInParent,cf->cfChildCount);
81 return -1;
82 }
83
84 if ( df->dfChildFields.cfChildCount >= 1 )
85 {
86 int i;
87 int step= df->dfChildFields.cfChildCount- 1;
88
89 if ( step > 0 )
90 {
91 DocumentField ** fresh;
92 int newCount;
93
94 newCount= cf->cfChildCount+ step;
95
96 fresh= (DocumentField **)realloc( cf->cfChildren,
97 newCount* sizeof(DocumentField *) );
98 if ( ! fresh )
99 { LXDEB(newCount,fresh); return -1; }
100 cf->cfChildren= fresh;
101
102 for ( i= cf->cfChildCount+ step- 1; i > pos+ step; i-- )
103 {
104 cf->cfChildren[i]= cf->cfChildren[i-step];
105 cf->cfChildren[i]->dfNumberInParent= i;
106 }
107 }
108
109 for ( i= 0; i <= step; i++ ) /* <= !! */
110 {
111 cf->cfChildren[pos+ i]= df->dfChildFields.cfChildren[i];
112 cf->cfChildren[pos+ i]->dfNumberInParent= pos+ i;
113 cf->cfChildren[pos+ i]->dfParent= df->dfParent;
114 }
115
116 cf->cfChildCount += step;
117 }
118 else{
119 int i;
120
121 cf->cfChildCount--;
122
123 for ( i= pos; i < cf->cfChildCount; i++ )
124 {
125 cf->cfChildren[i]= cf->cfChildren[i+1];
126 cf->cfChildren[i]->dfNumberInParent= i;
127 }
128 }
129
130 return 0;
131 }
132
133 /************************************************************************/
134 /* */
135 /* Return the innermost field for a position in the document tree. */
136 /* If at a certain position there is more than one field, the first */
137 /* one is returned. */
138 /* */
139 /* This function looks complicated, but is not: Start in the root */
140 /* fields of the document tree. As soon as you find a field that holds */
141 /* the position remember the field and look for a child that also */
142 /* holds the position. Eventually that returns the innermost field */
143 /* that contains the position. */
144 /* */
145 /************************************************************************/
146
docFindChildField(const ChildFields * cf,const EditPosition * ep,int lastOne)147 DocumentField * docFindChildField( const ChildFields * cf,
148 const EditPosition * ep,
149 int lastOne )
150 {
151 DocumentField * dfFound= (DocumentField *)0;
152
153 for (;;)
154 {
155 const int count= cf->cfChildCount;
156 int i;
157
158 if ( lastOne )
159 {
160 for ( i= count- 1; i >= 0; i-- )
161 {
162 DocumentField * df= cf->cfChildren[i];
163
164 if ( docEditPositionInField( df, ep ) )
165 {
166 dfFound= df;
167 cf= &(dfFound->dfChildFields);
168 break;
169 }
170 }
171
172 if ( i < 0 )
173 { break; }
174 }
175 else{
176 for ( i= 0; i < count; i++ )
177 {
178 DocumentField * df= cf->cfChildren[i];
179
180 if ( docEditPositionInField( df, ep ) )
181 {
182 dfFound= df;
183 cf= &(dfFound->dfChildFields);
184 break;
185 }
186 }
187
188 if ( i >= count )
189 { break; }
190 }
191 }
192
193 return dfFound;
194 }
195
docFindTypedChildField(const ChildFields * cf,const EditPosition * ep,int kind)196 DocumentField * docFindTypedChildField( const ChildFields * cf,
197 const EditPosition * ep,
198 int kind )
199 {
200 const int lastOne= 1;
201 DocumentField * df= docFindChildField( cf, ep, lastOne );
202
203 while( df && df->dfKind != kind )
204 { df= df->dfParent; }
205
206 return df;
207 }
208
209 /************************************************************************/
210 /* */
211 /* Find a field with a certain kind inside a range. */
212 /* */
213 /************************************************************************/
214
docFindFieldInRange(const EditRange * er,const ChildFields * cf,int lastOne,int kind)215 DocumentField * docFindFieldInRange( const EditRange * er,
216 const ChildFields * cf,
217 int lastOne,
218 int kind )
219 {
220 int pos;
221
222 if ( lastOne )
223 {
224 for ( pos= cf->cfChildCount- 1; pos >= 0; pos-- )
225 {
226 DocumentField * dfC= cf->cfChildren[pos];
227 const EditPosition * epHead= &(dfC->dfHeadPosition);
228 const EditPosition * epTail= &(dfC->dfTailPosition);
229 DocumentField * df;
230
231 if ( docCompareEditPositions( epHead, &(er->erTail) ) > 0 )
232 { continue; }
233 if ( docCompareEditPositions( epTail, &(er->erHead) ) < 0 )
234 { break; }
235
236 if ( docCompareEditPositions( epHead, &(er->erHead) ) >= 0 &&
237 docCompareEditPositions( epTail, &(er->erTail) ) <= 0 &&
238 ( dfC->dfKind == kind || kind < 0 ) )
239 { return dfC; }
240
241 df= docFindFieldInRange( er, &(dfC->dfChildFields), lastOne, kind );
242 if ( df )
243 { return df; }
244 }
245 }
246 else{
247 for ( pos= 0; pos < cf->cfChildCount; pos++ )
248 {
249 DocumentField * dfC= cf->cfChildren[pos];
250 const EditPosition * epHead= &(dfC->dfHeadPosition);
251 const EditPosition * epTail= &(dfC->dfTailPosition);
252 DocumentField * df;
253
254 if ( docCompareEditPositions( epTail, &(er->erHead) ) < 0 )
255 { continue; }
256 if ( docCompareEditPositions( epHead, &(er->erTail) ) > 0 )
257 { break; }
258
259 if ( docCompareEditPositions( epHead, &(er->erHead) ) >= 0 &&
260 docCompareEditPositions( epTail, &(er->erTail) ) <= 0 &&
261 ( dfC->dfKind == kind || kind < 0 ) )
262 { return dfC; }
263
264 df= docFindFieldInRange( er, &(dfC->dfChildFields), lastOne, kind );
265 if ( df )
266 { return df; }
267 }
268 }
269
270 return (DocumentField *)0;
271 }
272
273 /************************************************************************/
274 /* */
275 /* Remember the document position of the end of a field. */
276 /* */
277 /************************************************************************/
278
docSetFieldTail(DocumentField * dfPa,const EditPosition * epTail)279 void docSetFieldTail( DocumentField * dfPa,
280 const EditPosition * epTail )
281 {
282 dfPa->dfTailPosition= *epTail;
283
284 if ( dfPa->dfChildFields.cfChildCount > 0 )
285 {
286 DocumentField * dfCh;
287
288 dfCh= dfPa->dfChildFields.cfChildren[
289 dfPa->dfChildFields.cfChildCount- 1];
290
291 if ( docCompareEditPositions( &(dfCh->dfTailPosition),
292 &(dfPa->dfTailPosition) ) >= 0 )
293 { LDEB(1); }
294 }
295
296 return;
297 }
298
299 /************************************************************************/
300 /* */
301 /* Keep track of the hierarchy of fields. Do some elementary checks */
302 /* */
303 /* NOTE: The stacked construction of fields makes that children are */
304 /* added to the parent before the end position of the parent is */
305 /* set: Do not verify the end position. */
306 /* */
307 /************************************************************************/
308
docAddChildToField(DocumentField * dfCh,DocumentField * dfPa)309 int docAddChildToField( DocumentField * dfCh,
310 DocumentField * dfPa )
311 {
312 if ( ! docSelectionSameScope( &(dfCh->dfSelectionScope),
313 &(dfPa->dfSelectionScope) ) )
314 { LDEB(1); return -1; }
315
316 if ( docCompareEditPositions( &(dfCh->dfHeadPosition),
317 &(dfPa->dfHeadPosition) ) < 0 )
318 { LDEB(1); return -1; }
319 /* NO!
320 if ( docCompareEditPositions( &(dfCh->dfTailPosition),
321 &(dfPa->dfTailPosition) ) > 0 )
322 { LDEB(1); return -1; }
323 */
324
325 if ( docInsertChildField( dfPa, &(dfPa->dfChildFields), dfCh ) )
326 { LDEB(1); return -1; }
327 dfCh->dfParent= dfPa;
328
329 return 0;
330 }
331
docInsertFieldInTree(ChildFields * cf,DocumentField * df)332 int docInsertFieldInTree( ChildFields * cf,
333 DocumentField * df )
334 {
335 DocumentField * parent= (DocumentField *)0;
336
337 if ( df->dfChildFields.cfChildCount > 0 )
338 { LDEB(df->dfChildFields.cfChildCount); return -1; }
339
340 for (;;)
341 {
342 int i0;
343 int i1;
344 int i;
345 int pos;
346 int step;
347
348 /* Find the last field that is completely before the insert */
349 i0= 0;
350 while( i0 < cf->cfChildCount )
351 {
352 DocumentField * df0= cf->cfChildren[i0];
353
354 if ( docCompareEditPositions( &(df->dfTailPosition),
355 &(df0->dfHeadPosition) ) <= 0 )
356 { break; }
357
358 i0++;
359 }
360 i0--;
361
362 /* Find the first field that is completely after the insert */
363 i1= cf->cfChildCount- 1;
364 while( i1 >= 0 )
365 {
366 DocumentField * df1= cf->cfChildren[i1];
367
368 if ( docCompareEditPositions( &(df->dfHeadPosition),
369 &(df1->dfTailPosition) ) >= 0 )
370 { break; }
371
372 i1--;
373 }
374 i1++;
375
376 /* between fields */
377 if ( i1 == i0+ 1 )
378 {
379 return docInsertFieldAt( parent, cf, df, i1 );
380 }
381
382 /* inside a field: continue there */
383 if ( i0 == i1 )
384 {
385 DocumentField * df1= cf->cfChildren[i1];
386
387 if ( docCompareEditPositions( &(df->dfHeadPosition),
388 &(df1->dfHeadPosition) ) >= 0 &&
389 docCompareEditPositions( &(df->dfTailPosition),
390 &(df1->dfTailPosition) ) <= 0 )
391 {
392 cf= &(df1->dfChildFields);
393 parent= df1;
394 continue;
395 }
396 }
397
398 /* Surround the fields found with the insert */
399 if ( i1 <= i0 )
400 {
401 pos= 0;
402 for ( i= i1; i <= i0; i++ )
403 {
404 if ( docInsertFieldAt( df, &(df->dfChildFields),
405 cf->cfChildren[i], pos++ ) )
406 { LDEB(pos); return -1; }
407 }
408 step= i0- i1+ 1;
409 cf->cfChildCount -= step;
410 i= i1;
411 while( i < cf->cfChildCount )
412 { cf->cfChildren[i]= cf->cfChildren[i+ step]; i++; }
413
414 return docInsertFieldAt( parent, cf, df, i1 );
415 }
416
417 return docInsertFieldAt( parent, cf, df, i1 );
418 }
419 }
420
421 /************************************************************************/
422
docFieldPath(DocumentField *** pPath,DocumentField * dfTo)423 static int docFieldPath( DocumentField *** pPath,
424 DocumentField * dfTo )
425 {
426 DocumentField * df;
427 int deep= 0;
428 DocumentField ** path= (DocumentField **)0;
429
430 df= dfTo;
431 while( df )
432 { deep++; df= df->dfParent; }
433
434 if ( deep > 0 )
435 {
436 int d= deep;
437
438 path= (DocumentField **)malloc( deep* sizeof(DocumentField *) );
439 if ( ! path )
440 { LXDEB(deep,path); return -1; }
441
442 df= dfTo;
443 while( df )
444 { path[--d]= df; df= df->dfParent; }
445 }
446
447 *pPath= path;
448 return deep;
449 }
450
docFieldGetCommonParent(DocumentField * dfHead,DocumentField * dfTail)451 DocumentField * docFieldGetCommonParent( DocumentField * dfHead,
452 DocumentField * dfTail )
453 {
454 DocumentField * rval= (DocumentField *)0;
455 DocumentField ** pathHead= (DocumentField **)0;
456 DocumentField ** pathTail= (DocumentField **)0;
457
458 int deepHead;
459 int deepTail;
460 int deep;
461
462 deepHead= docFieldPath( &pathHead, dfHead );
463 deepTail= docFieldPath( &pathTail, dfTail );
464 if ( deepHead < 0 || deepTail < 0 )
465 { LLDEB(deepHead,deepTail); goto ready; }
466
467 for ( deep= 0; deep < deepHead && deep < deepTail; deep++ )
468 {
469 DocumentField * df;
470
471 if ( pathHead[deep] != pathTail[deep] )
472 { break; }
473
474 df= pathHead[deep];
475 if ( df == dfHead )
476 { break; }
477 if ( df == dfTail )
478 { break; }
479
480 rval= df;
481 }
482
483 ready:
484
485 if ( pathHead )
486 { free( pathHead ); }
487 if ( pathTail )
488 { free( pathTail ); }
489
490 return rval;
491 }
492
493