---

dsBintree.h

Go to the documentation of this file.

/*
 * $Id: dsBintree.h,v 1.9 2003/09/09 12:29:51 dsamersoff Exp $
 */

#ifndef dsBintree_h 
#define dsBintree_h 

#ifdef HAVE_CONFIG_H
# include <config.h>
#endif

#include <dsSmartException.h>
#include <dsDataAccessor.h>

DECLARE_EXCEPTION2(dsBinTree, dsDataAccessor);


class dsBinTreeItem : dsDataAccessorItem 
{
    dsBinTreeItem *left, *right;

public:  
    dsBinTreeItem():
       dsDataAccessorItem(){ left = 0; right =0; }

    dsBinTreeItem(void *xval):
       dsDataAccessorItem(xval){ left = 0; right = 0; }

   friend class dsBinTreeGeneric;
};


class dsBinTreeGeneric : public dsDataAccessor
{
protected:

    dsBinTreeItem* _root; 

    void cleanup(dsBinTreeItem* n = NULL, int first = 1);

    virtual int cf(void * a, void *b) = 0;

    virtual void visit(void *){};


public:

    dsBinTreeGeneric(DACleanupMode purge = cmPURGE);

    virtual ~dsBinTreeGeneric(){ cleanup(); }

    void *insert(void * a, bool replace = false);
    
    void *remove(void * a);
    
    void* seek(void *a);

   void walk(dsBinTreeItem* n = NULL, int first = 1);

};

class dsBinTree : public dsBinTreeGeneric
{
protected:
   virtual int cf(void * a, void *b)         { return strcmp(key(a), key(b));  }
   const char   *key(void *a)                { return (((dsDataPair *)a)->key);  }

public:
   dsBinTree(DACleanupMode purge = cmPURGE):
                  dsBinTreeGeneric(purge){}

   /* convenience interfaces */
   dsDataPair *seek(dsDataPair *dp);
   char * seek(const char *key);

   dsDataPair *insert(dsDataPair *dp, bool replace);
   char *insert(const char *key, char * value, bool replace = false);
};

inline  dsDataPair * dsBinTree::seek(dsDataPair *dp)
{
  return  (dsDataPair *) dsBinTreeGeneric::seek( (void *) dp ); 
}

inline dsDataPair *dsBinTree::insert(dsDataPair *dp, bool replace)
{
   return (dsDataPair *) dsBinTreeGeneric::insert((void *)dp, replace);
}

inline  char * dsBinTree::seek(const char *key)
{
  dsDataPair dp(key); 
  dsDataPair *tmp = seek(&dp); 
  return (tmp) ? (char *) tmp->val : 0; 
}

inline char *dsBinTree::insert(const char *key, char * value, bool replace)
{
    dsDataPair *dp = new dsDataPair(key, value);
    dsDataPair *tmp = insert(dp, replace);
    if (tmp && !replace)
                delete dp;
   return (char *)tmp->val;
}


#endif

---