1 /******************************************************************************
2 *
3 * Copyright (C) 2006-2008, The Gentee Group. All rights reserved.
4 * This file is part of the Gentee open source project - http://www.gentee.com.
5 *
6 * THIS FILE IS PROVIDED UNDER THE TERMS OF THE GENTEE LICENSE ("AGREEMENT").
7 * ANY USE, REPRODUCTION OR DISTRIBUTION OF THIS FILE CONSTITUTES RECIPIENTS
8 * ACCEPTANCE OF THE AGREEMENT.
9 *
10 * Author: Alexey Krivonogov ( gentee )
11 *
12 ******************************************************************************/
13 /*-----------------------------------------------------------------------------
14 * Id: tree L "Tree"
15 *
16 * Summary: Tree object. The each node of tree object can have a lot of childs.
17 It is required to include tree.g.#srcg[
18 |include : $"...\gentee\lib\tree\tree.g"]
19 *
20 * List: *#lng/opers#,tree_opof,tree_oplen,treeitem_oplen,treeitem_opfor,
21 *#lng/methods#,tree_clear,tree_del,tree_leaf,tree_node,tree_root,
22 *Treeitem methods,treeitem_changenode,treeitem_child,treeitem_data,
23 treeitem_getnext,treeitem_getprev,treeitem_isleaf,treeitem_isnode,
24 treeitem_isroot,treeitem_lastchild,treeitem_move,treeitem_parent
25 *
26 -----------------------------------------------------------------------------*/
27
28 type treeitem //< index = treeitem >
29 {
30 uint node // 1 if a group
31 uint parent // The pointer to the owner
32 uint child // The pointer to the first child
33 uint next // The pointer to the next item
34 }
35 // После этой структуры идут данные
36
37 type tree
38 {
39 uint rooti // The root item
40 uint count // The count of items
41 uint itype // The type of items
42 uint isize // The size of item
43 }
44
45 define
46 {
47 /*-----------------------------------------------------------------------------
48 * Id: treeflags D
49 *
50 * Summary: Flags for tree.move.
51 *
52 -----------------------------------------------------------------------------*/
53 TREE_FIRST = 0x0001 // The first child item of the same parent.
54 TREE_LAST = 0x0002 // The last child item of the same parent.
55 TREE_AFTER = 0x0004 // After this item.
56 TREE_BEFORE = 0x0008 // Before this item.
57 //-----------------------------------------------------------------
58 }
59
60 /*-----------------------------------------------------------------------------
61 * Id: treeitem_isleaf F3
62 *
63 * Summary: Check if it is a leaf. The method checks if an item is a "leaf"
64 (if it cannot have child items).
65 *
66 * Return: Returns 1 if this item is a tree "leaf" and 0 otherwise.
67 *
68 -----------------------------------------------------------------------------*/
69
70 method uint treeitem.isleaf
71 {
72 return !this.node
73 }
74
75 /*-----------------------------------------------------------------------------
76 * Id: treeitem_isnode F3
77 *
78 * Summary: Check if it is a node. The method checks is an item can have
79 child items.
80 *
81 * Return: Returns 1 if this item is a tree "node" and 0 otherwise.
82 *
83 -----------------------------------------------------------------------------*/
84
85 method uint treeitem.isnode
86 {
87 return this.node
88 }
89
90 /*-----------------------------------------------------------------------------
91 * Id: treeitem_isroot F3
92 *
93 * Summary: Check if it is a root item. The method checks if an item is a
94 root one.
95 *
96 * Return: Returns 1 if this item is a root one and 0 otherwise.
97 *
98 -----------------------------------------------------------------------------*/
99
100 method uint treeitem.isroot
101 {
102 return !this.parent
103 }
104
105 /*-----------------------------------------------------------------------------
106 * Id: treeitem_oplen F4
107 *
108 * Summary: Get the count of childs in the tree item.
109 *
110 * Return: The count of childs in the tree item.
111 *
112 -----------------------------------------------------------------------------*/
113
114 operator uint *( treeitem treei )
115 {
116 uint result
117 uint child = treei.child
118
119 while child
120 {
121 result++
122 child = child->treeitem.next
123 }
124 return result
125 }
126
127 /*-----------------------------------------------------------------------------
128 * Id: treeitem_parent F3
129 *
130 * Summary: Get the parent of an item.
131 *
132 * Return: Returns the parent of this item.
133 *
134 -----------------------------------------------------------------------------*/
135
136 method treeitem treeitem.parent()
137 {
138 return this.parent->treeitem
139 }
140
141 /*-----------------------------------------------------------------------------
142 * Id: treeitem_child F3
143 *
144 * Summary: Get the first child of an item.
145 *
146 * Return: Returns the first child item or 0 if there is none.
147 *
148 -----------------------------------------------------------------------------*/
149
150 method treeitem treeitem.child()
151 {
152 return this.child->treeitem
153 }
154
155 /*-----------------------------------------------------------------------------
156 * Id: treeitem_data F3
157 *
158 * Summary: Get the pointer to the data stored in an object.
159 *
160 * Return: Returns the pointer to the data.
161 *
162 -----------------------------------------------------------------------------*/
163
164 method uint treeitem.data()
165 {
166 if !&this : return 0
167 return &this + sizeof( treeitem )
168 }
169
170 /*-----------------------------------------------------------------------------
171 * Id: tree_root_1 FB
172 *
173 * Summary: Get the root item of a tree.
174 *
175 * Return: Returns the root item of the tree.
176 *
177 -----------------------------------------------------------------------------*/
178
179 method treeitem treeitem.getroot()
180 {
181 uint result = &this
182
183 while result->treeitem.parent
184 {
185 result = result->treeitem.parent
186 }
187
188 return result->treeitem
189 }
190
191 /*-----------------------------------------------------------------------------
192 * Id: treeitem_getnext F3
193 *
194 * Summary: Getting the next item to the current tree item.
195 *
196 * Return: Returns the next item.
197 *
198 -----------------------------------------------------------------------------*/
199
200 method treeitem treeitem.getnext()
201 {
202 return this.next->treeitem
203 }
204
205 /*-----------------------------------------------------------------------------
206 * Id: treeitem_getprev F3
207 *
208 * Summary: Getting the previous item to the current tree item.
209 *
210 * Return: Returns the previous item.
211 *
212 -----------------------------------------------------------------------------*/
213
214 method treeitem treeitem.getprev()
215 {
216 uint parent = this.parent
217
218 if !parent : return 0->treeitem
219
220 uint result = parent->treeitem.child
221
222 if result == &this : return 0->treeitem
223
224 while result
225 {
226 if result->treeitem.next == &this : return result->treeitem
227
228 result = result->treeitem.next
229 }
230 return 0->treeitem
231 }
232
233 /*-----------------------------------------------------------------------------
234 * Id: treeitem_lastchild F3
235 *
236 * Summary: Get the last child item of the tree item.
237 *
238 * Return: Returns the last child item or 0 if there is none.
239 *
240 -----------------------------------------------------------------------------*/
241
242 method treeitem treeitem.lastchild()
243 {
244 uint result = this.child
245
246 while result
247 {
248 if !result->treeitem.next : break
249
250 result = result->treeitem.next
251 }
252
253 return result->treeitem
254 }
255
256 /*-----------------------------------------------------------------------------
257 * Id: treeitem_changenode F2
258 *
259 * Summary: Change the parent node of an item.
260 *
261 * Params: treei - New parent node.
262 *
263 * Return: #lng/retf#
264 *
265 -----------------------------------------------------------------------------*/
266
267 method uint treeitem.changenode( treeitem treei )
268 {
269 if !this.parent || !treei.node ||
270 &this.getroot() != &treei.getroot() : return 0
271
272 uint curnext = this.next
273 uint curprev
274 curprev as this.getprev()
275
276 if &curprev
277 {
278 curprev.next = curnext
279 }
280 else
281 {
282 this.parent->treeitem.child = curnext
283 }
284
285 this.next = treei.child
286 treei.child = &this
287 this.parent = &treei
288
289 return 1
290 }
291
292 /*-----------------------------------------------------------------------------
293 * Id: tree_oplen F4
294 *
295 * Summary: Get the count of items in a tree.
296 *
297 * Return: The count of childs in the tree.
298 *
299 -----------------------------------------------------------------------------*/
300
301 operator uint *( tree itree )
302 {
303 return itree.count
304 }
305
306 /*-----------------------------------------------------------------------------
307 * Id: tree_opof F4
308 *
309 * Summary: Specifying the type of items. You can specify #b(of) type when you
310 describe #b(tree) variable. In default, the type of the items
311 is #b(uint).
312 *
313 * Title: tree of type
314 *
315 -----------------------------------------------------------------------------*/
316
317 method tree.oftype( uint itype )
318 {
319 if this.rooti
320 {
321 if type_hasdelete( this.itype )
322 {
323 type_delete( this.rooti + sizeof( treeitem ), this.itype )
324 }
325 mfree( this.rooti )
326 }
327 this.itype = itype
328 this.isize = sizeof( treeitem ) + sizeof( itype )
329
330 this.rooti = malloc( this.isize )
331 mzero( this.rooti, sizeof( treeitem ))
332 this.rooti->treeitem.node = 1
333 type_init( this.rooti + sizeof( treeitem ), this.itype )
334 }
335
336 /*-----------------------------------------------------------------------------
337 * Id: tree_root F3
338 *
339 * Summary: Get the root item of a tree.
340 *
341 * Return: Returns the root item of the tree.
342 *
343 -----------------------------------------------------------------------------*/
344
345 method treeitem tree.root
346 {
347 return this.rooti->treeitem
348 }
349
350 method tree tree.init
351 {
352 this.oftype( uint )
353 return this
354 }
355
356 /*-----------------------------------------------------------------------------
357 * Id: tree_leaf F2
358 *
359 * Summary: Adding a "leaf". Add a "leaf" to the specified node. You can not add
360 items to a "leaf".
361 *
362 * Params: parent - Parent node. If it is 0->treeitem then the item will be /
363 added to the root.
364 after - Insert an item after this tree item. If it is /
365 0->treeitem then the item will be the first child.
366 *
367 * Return: The added item or 0 in case of an error.
368 *
369 -----------------------------------------------------------------------------*/
370
371 method treeitem tree.leaf( treeitem parent, treeitem after )
372 {
373 uint treei
374 uint item
375 uint owner
376
377 // owner = ?( &parent, &parent, &this.rooti )
378 owner = ?( &parent, &parent, this.rooti )
379 owner as treeitem
380
381 if !owner.node : return 0->treeitem
382
383 treei = malloc( this.isize )
384 treei as treeitem
385 treei.parent = &owner
386 treei.child = 0
387 treei.node = 0
388 treei.next = 0 //owner.child
389 treei as uint
390 if !owner.child : owner.child = treei
391 elif &after
392 {
393 uint next = owner.child
394
395 while next != &after && next->treeitem.next
396 {
397 next = next->treeitem.next
398 }
399 treei->treeitem.next = next->treeitem.next
400 next->treeitem.next = treei
401 }
402 else
403 {
404 treei->treeitem.next = owner.child
405 owner.child = treei
406 }
407
408 item = treei + sizeof( treeitem )
409 type_init( item, this.itype )
410 this.count++
411
412 return treei->treeitem
413 }
414
415 /*-----------------------------------------------------------------------------
416 * Id: tree_leaf_1 FA
417 *
418 * Summary: Add a "leaf" to the specified node. An item will be the last child
419 item.
420 *
421 * Params: parent - Parent node. If it is 0->treeitem then the item will be /
422 added to the root.
423 *
424 * Return: The added item or 0 in case of an error.
425 *
426 -----------------------------------------------------------------------------*/
427
428 method treeitem tree.leaf( treeitem parent )
429 {
430 // return this.leaf( parent, 0->treeitem )//0xFFFFFFFF->treeitem )
431 return this.leaf( parent, 0xFFFFFFFF->treeitem )
432 }
433
434 /*-----------------------------------------------------------------------------
435 * Id: tree_node F2
436 *
437 * Summary: Adding a "node". Add a "node" to the specified node. You can add
438 items to a "node".
439 *
440 * Params: parent - Parent node. If it is 0->treeitem then the item will be /
441 added to the root.
442 after - Insert an item after this tree item. If it is /
443 0->treeitem then the item will be the first child.
444 *
445 * Return: The added item or 0 in case of an error.
446 *
447 -----------------------------------------------------------------------------*/
448
449 method treeitem tree.node( treeitem parent, treeitem after )
450 {
451 uint result
452
453 result as this.leaf( parent, after )
454 result.node = 1
455
456 return result
457 }
458
459 /*-----------------------------------------------------------------------------
460 * Id: tree_node_1 FA
461 *
462 * Summary: Add a "node" to the specified node. An item will be the last child
463 item.
464 *
465 * Params: parent - Parent node. If it is 0->treeitem then the item will be /
466 added to the root.
467 *
468 * Return: The added item or 0 in case of an error.
469 *
470 -----------------------------------------------------------------------------*/
471
472 method treeitem tree.node( treeitem parent )
473 {
474 // return this.node( parent, 0->treeitem )//0xFFFFFFFF->treeitem )
475 return this.node( parent, 0xFFFFFFFF->treeitem )
476 }
477
478 /*-----------------------------------------------------------------------------
479 * Id: tree_del F2
480 *
481 * Summary: Deleting an item. Delete an item together with all its child items.
482 *
483 * Params: item - The item being deleted.
484 funcdel - The custom function that will be called before deleting /
485 the each item. It can be 0.
486 *
487 -----------------------------------------------------------------------------*/
488
489 method tree.del( treeitem item, uint funcdel )
490 {
491 // Удаляем всех детей
492 while item.child : this.del( item.child->treeitem, funcdel )
493
494 if funcdel : funcdel->func( item )
495
496 if item.parent
497 {
498 uint prev
499
500 prev as item.getprev()
501
502 if &prev : prev.next = item.next
503 else : item.parent->treeitem.child = item.next
504 this.count--
505 }
506
507 // Удаляем объект
508 if type_hasdelete( this.itype )
509 {
510 type_delete( &item + sizeof( treeitem ), this.itype )
511 }
512 mfree( &item )
513 }
514
515 /*-----------------------------------------------------------------------------
516 * Id: tree_del_1 FA
517 *
518 * Summary: Delete an item together with all its child items.
519 *
520 * Params: item - The item being deleted.
521 *
522 -----------------------------------------------------------------------------*/
523
524 method tree.del( treeitem item )
525 {
526 .del( item, 0 )
527 }
528
529 method tree.delete
530 {
531 this.del( this.rooti->treeitem )
532 }
533
534 /*-----------------------------------------------------------------------------
535 * Id: tree_clear F2
536 *
537 * Summary: Delete all items in the tree.
538 *
539 * Return: #lng/retobj#
540 *
541 -----------------------------------------------------------------------------*/
542
543 method tree tree.clear()
544 {
545 uint ti
546
547 ti as this.rooti->treeitem
548 // Удаляем всех детей
549 while ti.child : this.del( ti.child->treeitem )
550 return this
551 }
552
553 /*-----------------------------------------------------------------------------
554 * Id: treeitem_move F2
555 *
556 * Summary: Move an item.
557 *
558 * Params: after - The node to insert the item after. Specify 0 if it should /
559 be made the first item.
560 *
561 * Return: #lng/retf#
562 *
563 -----------------------------------------------------------------------------*/
564
565 method uint treeitem.move( treeitem after )
566 {
567 uint parent
568 uint curnext = this.next
569 uint curprev
570
571 if !this.parent : return 0
572 /*|| ( &after > 1 &&
573 this.parent != after.parent ) : return 0*/
574
575 parent as this.parent()
576 curprev as this.getprev()
577
578 if curprev : curprev.next = curnext
579 else : parent.child = curnext
580 if !&after
581 {
582 this.next = parent.child
583 parent.child = &this
584 return 1
585 }
586 elif &after == 1
587 {
588 this.next = 0
589 curprev as parent.lastchild()
590 if curprev : curprev.next = &this
591 else : parent.child = &this
592 }
593 else
594 {
595 if &after == &this || after.next == &this : return 1
596 this.parent = after.parent
597 this.next = after.next
598 after.next = &this
599 }
600 return 1
601 }
602
603 /*-----------------------------------------------------------------------------
604 * Id: treeitem_move_1 FA
605 *
606 * Summary: Move an item.
607 *
608 * Params: target - The node to insert the item after or before depending on /
609 the flag.
610 flag - Move flag.$$[treeflags]
611 *
612 * Return: #lng/retf#
613 *
614 -----------------------------------------------------------------------------*/
615
616 method uint treeitem.move( treeitem target, uint flag )
617 {
618 switch flag
619 {
620 case $TREE_FIRST
621 {
622 this.changenode( target )
623 this.move( 0->treeitem )
624 }
625 case $TREE_LAST
626 {
627 this.changenode( target )
628 this.move( 1->treeitem )
629 }
630 case $TREE_AFTER
631 {
632 this.move( target )
633 }
634 case $TREE_BEFORE
635 {
636 uint prev
637 prev as target.getprev()
638 if !&prev
639 {
640 this.changenode( target.parent->treeitem )
641 this.move( 0->treeitem )
642 }
643 else : this.move( prev )
644 }
645 }
646
647 return 1
648 }
649
650 /*-----------------------------------------------------------------------------
651 ** Id: treeitem_opfor F5
652 *
653 * Summary: Foreach operator. You can use #b(foreach) operator to look over all
654 items of the treeitem. #b(Variable) is a pointer to the child tree
655 item.
656 *
657 * Title: foreach var,treeitem
658 *
659 * Define: foreach variable,treeitem {...}
660 *
661 -----------------------------------------------------------------------------*/
662 /*
663 method treeitems treeitem.items( treeitems items )
664 {
665 items.parent = &this
666 items.cur = 0
667 return items
668 }
669 */
670 method uint treeitem.eof( fordata tfd )
671 {
672 return !tfd.icur
673 }
674
675 method uint treeitem.next( fordata tfd )
676 {
677 if !tfd.icur : return 0
678
679 tfd.icur = tfd.icur->treeitem.next
680 return tfd.icur
681 }
682
683 method uint treeitem.first( fordata tfd )
684 {
685 tfd.icur = this.child
686 return tfd.icur
687 }
688
689