home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / cslio205.zip / INCLUDE / CSRAVL.H < prev    next >
C/C++ Source or Header  |  1997-01-21  |  3KB  |  114 lines
  1. /***********************************************************************
  2.  
  3.                       CSDB Library, Free Evaluation Version 2.0.5 
  4.                                        Release: January 22th 1997 
  5.  
  6.        AVL tree.
  7.  
  8.                                            Copyright(c) 1994-1997 
  9.                                                           ComBits 
  10.                                                   The Netherlands 
  11. ***********************************************************************/
  12.  
  13. #ifndef __CSAVLr_H
  14. #define __CSAVLr_H
  15.  
  16. #include "stdio.h"
  17. #include "csavl.h"
  18. #include "csstr.h"
  19. #include "csheap.h"
  20.  
  21.  
  22.  
  23.  
  24. class AVLr
  25. {
  26.  
  27.   public:
  28.  
  29.      typedef void * RPOINT;
  30.  
  31.   protected:
  32.      csSTR d_name;
  33.  
  34.  
  35.      typedef struct
  36.      {
  37.        S32 delta;
  38.        S8  balance;
  39.        RPOINT l;
  40.        RPOINT r;
  41.        RPOINT u;
  42.        avl_dat data;
  43.      } block;
  44.  
  45.      block *anchor;
  46.  
  47.      HEAP  data;
  48.  
  49.      block *alloc_data(S32 delta,avl_dat data);
  50.      void upd_delta(void *p,long add) { if(p!=NULL) ((block *)p)->delta+=add; }
  51.  
  52.      int  rotate(void **up,void *p);
  53.  
  54.  
  55. ////////////////////////// Support for delete //////////////////////////////
  56.  
  57.      int  sift_up(void *t);
  58.  
  59.  
  60. ////////////////////////// Import & Export /////////////////////////////////
  61. public:
  62.  
  63.      long import(FILE *fp,long num_bytes);
  64.      long export(FILE *fp)    { return export(fp,anchor,0); }
  65.      long export(FILE *fp,void *p,long pos);
  66.  
  67.  
  68. ////////////////////////// Rotations  //////////////////////////////////////
  69. protected:
  70.      void srr2(void **upd,void *a,void *b);
  71.      void slr2(void **upd,void *a,void *b);
  72.      void drr(void **up,void *a);
  73.      void dlr(void **up,void *a);
  74.      void srr(void **up,void *a)   { srr2(up,a,((block *)a)->l); }
  75.      void slr(void **up,void *a)   { slr2(up,a,((block *)a)->r); }
  76.  
  77.  
  78.  
  79.    public:
  80.        AVLr(void);
  81.        virtual
  82.       ~AVLr(void);
  83.  
  84.        int insert(U32 key, avl_dat data);
  85.        int insert(U32 key, void *p)  { avl_dat data; data.p=p; return insert(key,data); }
  86.        int insert(U32 key, long l )  { avl_dat data; data.l=l; return insert(key,data); }
  87.  
  88.        int delet( U32 key);
  89.  
  90.        int search(U32 key, avl_dat &data);
  91.        int search_ge(U32 key,U32 &nkey, U32 &data);
  92.        int search_ge(U32 key,U32 &nkey, avl_dat &data);
  93.        int search_gt(U32 key,U32 &nkey, avl_dat &data);
  94.        int search_le(U32 key,U32 &nkey, U32     &data);
  95.        int search_lt(U32 key,U32 &nkey, avl_dat &data);
  96.  
  97.        void zap(void );
  98.        void empty(void);
  99.        void close(void);
  100.        void open(void)   { data.open(); }
  101.  
  102.        int  report(csCHAR *name,int sub);
  103.        void report(FILE *fp,int sub);
  104.        void reporter(FILE *fp,void *,int );
  105.        void report_sum(FILE *fp,void *,U32 );
  106.  
  107.        csCHAR *e_name(void)  { return (csCHAR *)d_name; }
  108.        virtual int class_ID(void)  { return CS_CLID_RAVL; }
  109.  
  110. };
  111.  
  112.  
  113. #endif
  114.