home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 25 / nopv25.iso / 040A / PBL30DOC.ZIP / BINTREE.TXT next >
Encoding:
Text File  |  1997-04-08  |  9.2 KB  |  237 lines
  1. zBinTree
  2. =============================================================================
  3.  
  4.     This class provides a simple and efficient binary tree implementation
  5.     with several traversal methods. The info is stored with pointers to
  6.     void, so there is no type-checking.
  7.  
  8.     Very flexible implementation allows for painless usage without the
  9.     need for excessive derivations. (Yes, not very OOP, I'm afraid!)
  10.  
  11.  
  12.     ZBINTREE::ZBINTREE
  13.     -------------------------------------------------------------------------
  14.  
  15.         Summary   Constructs the binary tree object
  16.  
  17.         Syntax    zBinTree(fpCompFunc compare, Boolean shouldPurge = False);
  18.  
  19.         Remarks   This is the only available constructor. It will create
  20.                   an empty tree. The 'compare' argument specifies a pointer
  21.                   to the function used to compare two elements. This routine
  22.                   is defined as follows:
  23.  
  24.                     int (*fpCompFunc)(const void *item1, const void *item2);
  25.  
  26.                   The function should return a value <0 if item1 is less
  27.                   than item2; 0 if item1 == item2; >0 if item1 > item2. This
  28.                   routine will be called with pointers to the items as the
  29.                   two parameters.
  30.  
  31.                   The 'shouldPurge' parameter specifies whether the special
  32.                   cleanup routine should be called when destroying a node
  33.                   in the tree. If this is False, the caller is responsible
  34.                   for freeing the memory used by the elements. If this is
  35.                   True (and a cleanup routine has been specified with a call
  36.                   to the setCleanup() method), the user routine will be
  37.                   invoked with a pointer to the element to destroy as the
  38.                   argument.
  39.  
  40.  
  41.  
  42.     ZBINTREE::~ZBINTREE
  43.     -------------------------------------------------------------------------
  44.  
  45.         Summary   Destroys the binary tree
  46.  
  47.         Syntax    virtual ~zBinTree();
  48.  
  49.         Remarks   The destructor destroys the binary tree object and frees
  50.                   all internally allocated memory. If the user has specified
  51.                   'setPurge' to be True (constructor) and there exists a
  52.                   cleanup routine (see the setCleanup() method), this will
  53.                   also free the memory allocated for the element data itself.
  54.  
  55.  
  56.     ZBINTREE::INSERT
  57.     -------------------------------------------------------------------------
  58.  
  59.         Summary   Inserts a node into the tree
  60.  
  61.         Syntax    Boolean insert(void *p);
  62.  
  63.         Remarks   This function inserts a node into the tree. It uses the
  64.                   user-supplied comparison function to determine where to
  65.                   place the new node. Duplicates are not allowed. Note that
  66.                   the class will only store a copy of the pointer it is
  67.                   passed, it will not copy any data.
  68.  
  69.         Return    True if the insertion was successful
  70.                   False if out of memory or a duplicate found
  71.  
  72.  
  73.     ZBINTREE::REMOVE
  74.     -------------------------------------------------------------------------
  75.  
  76.         Summary   Removes an existing node from the tree
  77.  
  78.         Syntax    void remove(void *p);
  79.                   void remove();
  80.  
  81.         Remarks      There are two versions of the remove() method. The first
  82.                   one will find and remove the element with data 'p'. The
  83.                   second version will remove the element previously located
  84.                   by the find() method. The purging options described in
  85.                   the constructor text apply.
  86.  
  87.         Return    Nothing
  88.  
  89.  
  90.     ZBINTREE::SIZE
  91.     -------------------------------------------------------------------------
  92.  
  93.         Summary   Return the number of elements in the tree
  94.  
  95.         Syntax    int size() const;
  96.  
  97.         Remarks   This function returns the number of elements currently
  98.                   linked in the tree.
  99.  
  100.         Return    Number of elements
  101.  
  102.  
  103.     ZBINTREE::GET
  104.     -------------------------------------------------------------------------
  105.  
  106.         Summary   Retrieve the data from the current node
  107.  
  108.         Syntax    void* get();
  109.  
  110.         Remarks   This function can be used after a call to find() to
  111.                   retrieve the data from a specific node. Note that
  112.                   you must call find() first or this routine will fail. Note
  113.                   that since we are only storing pointers to void, you will
  114.                   need to typecast it to the appropriate type before trying
  115.                   to dereference it.
  116.  
  117.         Return    On success, returns the data
  118.                   On failure, returns NULL
  119.  
  120.  
  121.     ZBINTREE::UPDATE
  122.     -------------------------------------------------------------------------
  123.  
  124.         Summary   Updates the current node
  125.  
  126.         Syntax    void update(void *p);
  127.  
  128.         Remarks   This function updates the current node (located with a call
  129.                   to the find() member routine) with the new data 'p'. If
  130.                   the 'shouldPurge' is True, the old data will be destroyed
  131.                   with a call to the user-supplied cleanup function. You have
  132.                   to call find() before using this method or it will fail.
  133.  
  134.         Return    Nothing
  135.  
  136.  
  137.     ZBINTREE::FIND
  138.     -------------------------------------------------------------------------
  139.  
  140.         Summary   Locates a specific node
  141.  
  142.         Syntax    void* find(void *arg);
  143.  
  144.         Remarks   This method scans the tree to find a node with data equal
  145.                   to 'arg'. It calls the user-supplied comparison function
  146.                   (see the constructor) to do the actual comparisons. Each
  147.                   call starts searching from the root of the tree. There is
  148.                   no provision for resuming a search at a specific location.
  149.  
  150.         Return    On success, returns non-NULL value
  151.                   On error (not found), returns NULL
  152.  
  153.  
  154.     ZBINTREE::FOREACH
  155.     -------------------------------------------------------------------------
  156.  
  157.         Summary   Tree iterator with an action function
  158.  
  159.         Syntax    void forEach(fpAppFunc app, void *arg = 0,
  160.                                tree_order order = in);
  161.  
  162.         Remarks   This iterator will traverse the tree in the specified order
  163.                   and apply the action function 'app' to each node it visits.
  164.                   The action function is defined as:
  165.  
  166.                     typedef void (*fpAppFunc)(void *item, void *arg);
  167.  
  168.                   where 'item' is the node data and 'arg' is the parameter
  169.                   'arg' passed to the iterator (defaults to NULL). This
  170.                   additional argument allows you to pass optional data to
  171.                   the action function.
  172.  
  173.                   All classic traversal modes are available. You can use
  174.                   any of the following enumerated constants as the third
  175.                   parameter to the iterator:
  176.  
  177.                          enum tree_order { pre, post, in, rev };
  178.  
  179.                   'pre' specifies pre-order traversal (current, left, right)
  180.                   'post' specifies post-order mode (left, right, current)
  181.                   'in' specifies in-order traversal (left, current, right)
  182.                   'rev' specifies reversed-order mode (right, current, left)
  183.  
  184.                   Each mode will produce different results. For example,
  185.                   in-order will visit the nodes in ascending order, while
  186.                   reverse-order will visit them in descending order.
  187.  
  188.         Return    Nothing
  189.  
  190.  
  191.     ZBINTREE::OPERATOR()
  192.     -------------------------------------------------------------------------
  193.  
  194.         Summary   Retrieve the data for the current node
  195.  
  196.         Syntax    void* operator()();
  197.  
  198.         Remarks   Same as the get() method.
  199.  
  200.  
  201.     ZBINTREE::SETCLEANUP
  202.     -------------------------------------------------------------------------
  203.  
  204.         Summary   Sets the user-definable cleanup function
  205.  
  206.         Syntax    void setCleanup(fpCleanupFunc cf);
  207.  
  208.         Remarks   This routine must be used to specify a function which is
  209.                   to be used when items are destroyed (if and only if the
  210.                   'shouldPurge' parameter in the constructor is True). The
  211.                   cleanup function is defined as follows:
  212.  
  213.                           typedef void (*fpCleanupFunc)(void*);
  214.  
  215.                   It will be passed the pointer to the user data and it
  216.                   must dispose of the memory in the proper way. Having a
  217.                   routine like this obviates the need to derive special
  218.                   classes to handle different data.
  219.  
  220.         Return    Nothing
  221.  
  222.  
  223.     ZBINTREE::PURGE
  224.     -------------------------------------------------------------------------
  225.  
  226.         Summary   Removes all nodes from the tree
  227.  
  228.         Syntax    void purge();
  229.  
  230.         Remarks   This method simply removes all nodes from the tree. Note
  231.                   that all specifications regarding the purging of nodes
  232.                   listed above apply. Refer to the setCleanup() method
  233.                   description and the constructor text for more information.
  234.  
  235.         Return    Nothing
  236.  
  237.