Ads

  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