home *** CD-ROM | disk | FTP | other *** search
/ The CDPD Public Domain Collection for CDTV 4 / CDPD_IV.bin / fish / 911-930 / ff926 / treetool / treetool.doc < prev    next >
Text File  |  1994-05-04  |  8KB  |  255 lines
  1. TreeTool link library 1.0 (Public Domain).
  2. ------------------------------------------
  3. Jean-Christophe Clement, Summer 1993.
  4.  
  5. Introduction:
  6.  
  7.   This library implements some functions to make working with acyclic, n-ary
  8. tree a breeze. This documentation will give you some information on how to
  9. use it but will assume some working knowledge of tree concept and, of
  10. course, a good understanding of 'C'. Some example of usage are given at
  11. end of this file.
  12.  
  13. Some background:
  14.  
  15.   I designed this library mainly for a project I was working on at
  16. University of Sherbrooke and, after looking in the Fish disk lib, I found
  17. that no generic tool like this one was available for the Amiga. It's not
  18. that it is very hard or long to code (It took me less than a day to do so)
  19. but it is done and tested (The project was relying heavily on TreeTool) so
  20. you can use it and work on more important problem in you own code. By the
  21. way, the 'C' code is VERY portable and can be used with any ANSI C
  22. compiler (my project was running on Unix). No special consideration on
  23. performance issue has been given other than the double-link on the child
  24. list.
  25.  
  26. The Aplication Programmer Interface (API):
  27.  
  28.   I took several "object-oriented" approach when designing TreeTool and
  29. I think it reflects in the API. These are: data abstraction, information
  30. hiding and methods. Of course, it means that, to make an usefull use of the
  31. TreeTool lib, you must use ONLY the supplied function to acces the tree
  32. structure.
  33.  
  34. Available functions are:
  35.  
  36. NODE_HANDLE tt_NewNode(NODE_HANDLE nodeHandle,void *data);
  37. void        tt_KillNode(NODE_HANDLE nodeHandle,void (*killFunc)() );
  38. NODE_HANDLE tt_GetLeftBrother(NODE_HANDLE nodeHandle);
  39. NODE_HANDLE tt_GetRightBrother(NODE_HANDLE nodeHandle);
  40. void        tt_GetSuperMariosBrother();
  41. NODE_HANDLE tt_GetFirstSon(NODE_HANDLE nodeHandle);
  42. NODE_HANDLE tt_GetLastSon(NODE_HANDLE nodeHandle);
  43. NODE_HANDLE tt_GetFather(NODE_HANDLE nodeHandle);
  44. void *      tt_SetNodeData(NODE_HANDLE nodeHandle,void *data);
  45. void *      tt_GetNodeData(NODE_HANDLE nodeHandle);
  46. void          tt_ApplyFunction(NODE_HANDLE nodeHandle, void (*oneFunc)());
  47.  
  48.  
  49. tt_NewNode:
  50.  
  51. Function: Allocate memory for a new node. Will make the new
  52.           node a son of the NODE_HANDLE passed if a non-NULL value
  53.           is given. Pointer to user data passed is kept internally.
  54.  
  55.     Note: If NULL is passed as 'nodeHandle', the function
  56.           will return a node linked to nothing (Be aware to
  57.           use it carefully). If NULL is passed as 'data', a
  58.           NULL data pointer will be put in the node but the
  59.           node will still be created.
  60.           Return NULL is no new node has been allocated (if
  61.           no memory is free for use). All the nodes created
  62.           must be deallocated with tt_KillNode().
  63.  
  64.  
  65. tt_KillNode:
  66.  
  67. Function: Deallocate all the memory for the specified node
  68.           and all of it's child's node memory. Frees data
  69.           too using the passed function (of course, we
  70.           assume that the client will de-allocate the data
  71.           correctly!)
  72.  
  73.     Note: Instead of keeping pointers to all of the allocated
  74.           node for an eventual deletion on quit, you can use
  75.           tt_KillNode on the root node. tt_KillNode will
  76.           recursively delete all of the nodes and will call
  77.           back your destruction function to free the contained
  78.           data at each node. Your call-back function must have
  79.           only one parameter, a data pointer, that will correspond
  80.           to the user data pointer of the node to be deleted.
  81.           You can pass a NULL function pointer as call-back, in
  82.           wich case nothing will be called.
  83.  
  84. tt_GetLeftBrother:
  85.  
  86. Function: Returns the left brother of the passed node if
  87.           they both exist.
  88.  
  89.     Note: Returns NULL otherwise. In the current implementation,
  90.           the left brother access time is O(1).
  91.  
  92.  
  93. tt_GetRightBrother:
  94.  
  95. Function: Returns the right brother of the passed node if
  96.           they both exist.
  97.  
  98.     Note: Returns NULL otherwise. In the current implementation,
  99.           the right brother access time is O(1).
  100.  
  101.  
  102. tt_GetSuperMariosBrother:
  103.  
  104. Function: To prove that there is still place for fun in
  105.           computer sciences.
  106.  
  107.     Note: Is harmless actually.
  108.  
  109.  
  110. tt_GetFirstSon:
  111.  
  112. Function: Returns the first left son of the specified node.
  113.  
  114.     Note: Returns NULL is there is not such a son. In the current
  115.           implementation, the first son access is O(1).
  116.  
  117.  
  118. tt_GetLastSon:
  119.  
  120. Function: Returns the rightmost son of the specified node.
  121.  
  122.     Note: Returns NULL is there is no such son. Access time is O(n).
  123.  
  124.  
  125. tt_GetFather:
  126.  
  127. Function: Returns the father node associated with the passed
  128.           one.
  129.  
  130.     Note: NULL if at top of tree or a NULL NODE_HANDLE is passed.
  131.           At worst, access time is O(n).
  132.  
  133.  
  134. tt_SetNodeData
  135.  
  136. Function: Will link the passed data pointer to the pased node.
  137.  
  138.     Note: If there is already a data pointer in this node,
  139.           it will be replaced (you must destroy it first!).
  140.           Returns a void pointer where the client
  141.           can write to modify the node content
  142.           directly.
  143.  
  144.  
  145. tt_ApplyFunction:
  146.  
  147. Function: Recursively apply a passed function on every node of the Tree
  148.           that is a child (sub-child, etc...) of NODE_HANDLE and
  149.           to NODE_HANDLE itself.
  150.  
  151.     Note: Your call-back function will receive one
  152.           parameter which will be the NODE_HANDLE of the
  153.           current node you want your function to be used on.
  154.           Function will be applied on the prefix path.
  155.  
  156. Voila! let's hope everything is clear...
  157.  
  158. To compile your program using TreeTool, consult your compiler manual
  159. on linking. See the example script for SAS/C.
  160.  
  161. To compile TreeTool using SAS/C (5.1 in my case), nothing more
  162. than "lc -O treetool.c" is necessary.
  163.  
  164. Now, one example:
  165. We construct a tree with a child that has one child itself, use them a
  166. bit and kill the tree before quitting. This is quite straightforward, I
  167. doubt anybody will need more info.
  168.  
  169.  
  170. #include "TreeTool.h"
  171. #include <stdio.h>
  172.  
  173. /* Some prototypes. */
  174. void displayFunc(NODE_HANDLE);
  175. void mkillFunc(struct someData *);
  176.  
  177. struct someData
  178. {
  179.   int   a,b,c;
  180.   char  *string;
  181. }
  182.  
  183. main()
  184. {
  185.   NODE_HANDLE         a_tree=NULL;
  186.   struct someData     data1={1,2,3,"Root node."},data2,data3={7,8,9,"Sub-child node."};
  187.   struct someData     *ptrDat2;
  188.  
  189.   /* We create our tree root. */
  190.   a_tree=tt_NewNode(NULL,NULL);
  191.  
  192.   /* Let's create a child.    */
  193.   tt_NewNode(a_tree,&data2);
  194.  
  195.   /* Create a child of the child. */
  196.   tt_NewNode(tt_GetFirstSon(a_tree),&data3);
  197.  
  198.   /* Set the root node pointer. */
  199.   tt_SetNodeData(a_tree,&data1);
  200.  
  201.   /* Get the user data pointer to the child node. */
  202.   ptrDat2=tt_GetNodeData(tt_GetFirstSon(a_tree));
  203.  
  204.   /* We can now fill it with "meaningfull" information. */
  205.   if( ptrDat2 )
  206.   {
  207.     ptrDat2->a=4;
  208.     ptrDat2->b=5;
  209.     ptrDat2->c=6;
  210.     ptrDat2->string="Child node.";
  211.   }
  212.  
  213.   /* We will use our displayFunc to recursively display the message */
  214.   /* in each node.                                                  */
  215.   tt_ApplyFunction(a_tree,displayFunc);
  216.  
  217.   printf("\n");
  218.  
  219.   /* We kill all the allocated nodes before quitting.                 */
  220.   /* We could just have used tt_KillNode(a_tree,NULL) because data is */
  221.   /* static.                                                          */
  222.   tt_KillNode(a_tree,mkillFunc);
  223. }
  224.  
  225. void displayFunc(NODE_HANDLE node)
  226. {
  227.   struct someData *ptrData;
  228.  
  229.   if( ptrData=tt_GetNodeData(node) )
  230.   {
  231.     printf("This node contains the message: %s\n",ptrData->string);
  232.   }
  233. }
  234.  
  235. void mkillFunc(struct someData *ptrData)
  236. {
  237.  
  238.    /* Actually does nothing but could do something if dynamic data was  */
  239.    /* used.                                                             */
  240.    printf("Killing the node containing message: %s\n",ptrData->string);
  241. }
  242.  
  243.  
  244. The final word:
  245.  
  246. If you like it and use it, that's great!
  247.  
  248. If you want to contact me:
  249.  
  250. Jean-Christophe Clement
  251. 921 rang 3, St-Simon
  252. Quebec, CANADA
  253. J0H-1Y0
  254.  
  255. Internet: clemj00@dmi.usherb.ca