mi32/btreefun.h

Go to the documentation of this file.

/**
 * \file btreefun.h <mi32/btreefun.h>
 * \brief Definitions for BTree functions
 *
 * \if NODOC
 * $Log: btreefun.h_v $
 * Revision 1.30  2006/09/18 14:35:27  scowan
 * Added necessary include file.
 *
 * Revision 1.29  2005/12/29 21:35:22  scowan
 * Removed the reference.
 *
 * Revision 1.28  2005/12/29 20:31:58  scowan
 * Added code to allocate a test and delete when done.
 *
 * Revision 1.27  2005/08/29 19:14:07  scowan
 * Fixed deprecated item.
 *
 * Revision 1.26  2003/12/18 13:59:55  mju
 * Remove deprecated items.
 *
 * Revision 1.25  2003/09/15 13:49:56  fileserver!dwilliss
 * Doxygen
 *
 * Revision 1.24  2003/09/08 20:33:39  dwilliss
 * Added doxygen tags for start/end of function groups
 *
 * Revision 1.23  2003/05/12 14:05:21  mju
 * Fix deprecated macro.
 *
 * Revision 1.22  2003/05/12 13:48:05  mju
 * Deprecate obsolete Init/Stop fns.
 *
 * Revision 1.21  2003/04/09 15:10:17  scowan
 * Fixed g++ 3.0 unix compiler error for mac osx.
 *
 * Revision 1.20  2003/03/20 15:48:17  scowan
 * Added is valid method.
 *
 * Revision 1.19  2003/01/27 17:16:22  scowan
 * Fixed more typo's.
 *
 * Revision 1.18  2003/01/27 16:44:56  scowan
 * Fixed wrapper class issues.
 *
 * Revision 1.17  2003/01/22 16:54:16  scowan
 * Fixed compile errors with wrapper class.
 *
 * Revision 1.16  2003/01/22 15:59:13  scowan
 * Added inline template wrapper, do not know if it works.
 *
 * Revision 1.15  2001/01/23 16:48:13  dwilliss
 * Had forgotten to export new function from the DLL
 * \endif
**/

#ifndef  INC_MI32_BTREEFUN_H
#define  INC_MI32_BTREEFUN_H

#ifndef  INC_MI32_STDDEFNS_H
#include <mi32/stddefns.h>
#endif

#ifndef  INC_MI32_ERRCODES_H
#include <mi32/errcodes.h>
#endif

#ifndef  INC_MI32_ERRHANDLER_H
#include <mi32/errhandler.h>
#endif

#ifdef GEOMDLL
   #define GEOMLIBEXPORT MI_DLLEXPORT
#else
   #define GEOMLIBEXPORT MI_DLLIMPORT
#endif

//----------------------------------------------------------------------------
//!      Function prototypes
//----------------------------------------------------------------------------

//!:Associate with "Btree Functions"
//!\addtogroup btree Btree Functions
//!@{

//! Tree comparison function used in searching/adding.
//!
//! @return >, ==, < 0.
typedef int (*BTreeTestFunc)(
   void*, 
   void*, 
   void*
   );

//! Callback used to return data. 
typedef int (*BTreeDumpFunc)(
   void *data,                         //!< Data stored in the tree
   INT32 *tagnum,                      //!< Pointer to tag number
   void *username                      //!< Pointer to sent data
   );

#if defined(__cplusplus)
extern "C" {
#endif

//! Allocate a "balanced tree".
//!
//! @return Handle to tree instance.                              
//!
//! Note.  At the current time, it is assumed that the test function may
//! modify the data, forcing the tree to do more work that it should
//! have to.  You should not rely on this assumption, as it was an obscure,
//! undocumented side effect and likely to change some day.  Instead, you
//! should call BTreeSetTestFunc() and tell it if your test function can
//! modify the data.
//!
GEOMLIBEXPORT void *BTreeAlloc (
   int numitems,                       //!< Number of items to store per node 
   int datasize,                       //!< Size of data to tree in bytes
   BTreeTestFunc testfunc,                      //!< Comparison function used in searching/adding
   void *userdata                      //!<  Data passed to comparison function
   );

//! Clears item from "balanced tree".
GEOMLIBEXPORT int BTreeClear (
   void *item                          //!<  Item to be cleared from tree
   );

//! Dump a "balanced tree" in "random" order.
//!
//! NOTE: This function transverses the tree as it is stored, no order is at all guaranteed!
GEOMLIBEXPORT int BTreeDump (
   void *tree,                         //!< Handle to tree instance
   BTreeDumpFunc,                      //!< Callback used to return data
   void *userdata                      //!< User data passed to Dump()
   );

//! Dump a "balanced tree" in "traversal" order.
//!
//! NOTE: This function transverses the tree and dumps the data in the
//!   order that the comparison function (see BTreeAlloc()) stipulated.
GEOMLIBEXPORT int BTreeDumpT (
   void *tree,                         //!< Handle to tree instance
   BTreeDumpFunc,                      //!< Callback used to return data
   void *userdata                      //!< User data passed to Dump()
   );

//! Search "balanced tree" for a specified key, add if no match found.
//!
//! @return tag number assigned to the data if (>=0), else error
GEOMLIBEXPORT INT32 BTreeFindKey (
   void *tree,                         //!< Handle to tree instance
   void *data,                         //!< Data to find and add if necessary
   INT32 tagnum,                       //!< Number to tag data with
   int *add                            //!< Set if data was added to tree
   );

//! Free a "balanced tree".
GEOMLIBEXPORT int BTreeFree (
   void *tree                          //!< Handle to tree instance
   );

//! Get the userdata associated with 'tree'
GEOMLIBEXPORT void* BTreeGetUserData (
   void *tree                          //!< Handle to tree instance
   );

//! Change test function for a "balanced tree".
GEOMLIBEXPORT int BTreeNewFunc (
   void *tree,                         //!< Handle to tree instance
   BTreeTestFunc,                      //!< Comparison function used in searching/adding
   void *userdata                      //!< Data passed to comparison function
   );

//! Search "balanced tree" for a specified key.
//!
//! @return -1 = Not found, < -1 Error, else the tag number associated with the data.
//!   See BTreeFindKey(). 
GEOMLIBEXPORT INT32 BTreeSearchKey (
   void *tree,                         //!< Handle to tree instance
   void *data                          //!< Data to find if exists
   );


//! Change test function for a "balanced tree".
//! This is similar to BTreeNewFunc, but allows you to tell the BTree that the
//! function won't modify the data it's passed.
//! The default behaviour for btrees is to assume that the test function
//! can modify the data passed.
GEOMLIBEXPORT void BTreeSetTestFunc (
   void *btree,
   BTreeTestFunc Test,
   void *userdata,
   bool TestFuncIsConst
   );

#if defined(__cplusplus)
} // extern "C"
#endif

//!@}

//! Wrapper class to the BTree API
template <typename _BT>
class BALANCEDTREE {
   public:
      //! Interface class to "dump" an item from the tree, used in DumpTree() and TraverseTree()
      class DUMP {
         public:
            virtual ERRVALUE v_DumpItem (const _BT& item, INT32 TagNum) = 0;
         };
   
      //! Interface class to test two tree items, can use default if _T::operator<() defined
      class TEST {
         public:
            virtual ~TEST () {}
            virtual int v_TestItems (const _BT& p1, const _BT& p2) { return ((p1 < p2) ? -1 : ((p2 < p1) ? 1 : 0)); }
         };
   
   private:
      #ifndef GENERATING_DOXYGEN_OUTPUT
      static int DumpFunc (void* p1, INT32* tagnum, void* ud) {
         return (static_cast<DUMP*>(ud)->v_DumpItem(*static_cast<_BT*>(p1), *tagnum));
         }
   
      static int TestFunc (void* p1, void* p2, void* ud) {
         return (static_cast<TEST*>(ud)->v_TestItems(*static_cast<_BT*>(p1), *static_cast<_BT*>(p2)));
         }
      #endif // GENERATING_DOXYGEN_OUTPUT
   
   public:

      //! Constructor   
      BALANCEDTREE (
         ) : m_BTreeHandle(0) {}
         
      //! Destructor 
      ~BALANCEDTREE (
         ) { 
         if (m_BTreeHandle != 0) {
            delete static_cast<TEST*>(BTreeGetUserData(m_BTreeHandle));
            BTreeFree(m_BTreeHandle); 
            }
         }

      //! Initialize the balanced tree giving an initial number of items
      ERRVALUE Allocate (
         INT32 InitialNumItems,
         TEST Test = TEST()
         ) {
         m_BTreeHandle = BTreeAlloc(InitialNumItems, sizeof(_BT), TestFunc, new TEST(Test));
         if (m_BTreeHandle == 0) return (SetErrPosnC(EOutOfMemory));
         return (0);
         }
         
      //! Clear the balanced tree of all items
      ERRVALUE Clear (
         ) { return (BTreeClear(m_BTreeHandle)); }
         
      //! Dump the balanced tree in no particular order
      ERRVALUE DumpTree (
         DUMP& Dump
         ) { return (BTreeDump(m_BTreeHandle, DumpFunc, &Dump)); }
         
      //! Locate an item in the tree and return its key value.
      //! If the item does not exist, add it to the tree
      INT32 FindAndInsertKey (
         _BT& Item,
         INT32 CurTagNum,        //!< Tag number to use if 'Item' is added to the tree
         bool& AddedItem         //!< Set to 'true' if 'Item' is added to the tree
         ) { 
         int add = 0;
         INT32 retval = BTreeFindKey(m_BTreeHandle, &Item, CurTagNum, &add);
         AddedItem = (add != 0);
         return (retval);
         }

      //! Determine if the balanced tree Allocate() method has been called
      bool IsAllocated (
         ) const { return (m_BTreeHandle != 0); }
         
      //! Locate an item in the tree and return its key value
      INT32 LocateKey (
         const _BT& Item
         ) { return (BTreeSearchKey(m_BTreeHandle, const_cast<_BT*>(&Item))); } 
         
      //! Set a new test function for locating tree items
      void SetTestFunc (
         TEST& NewTest
         ) { 
         delete static_cast<TEST*>(BTreeGetUserData(m_BTreeHandle));
         BTreeSetTestFunc(m_BTreeHandle, TestFunc, new TEST(NewTest), true); 
         }
         
      //! Dump the balanced tree in sorted order
      ERRVALUE TraverseTree (
         DUMP& Dump
         ) { return (BTreeDumpT(m_BTreeHandle, DumpFunc, &Dump)); }
         
   private:
      #ifndef GENERATING_DOXYGEN_OUTPUT
      void *m_BTreeHandle; 

      BALANCEDTREE (const BALANCEDTREE& rhs);
      BALANCEDTREE& operator=(const BALANCEDTREE& rhs);
      #endif // GENERATING_DOXYGEN_OUTPUT
   };

#endif

---