/***********************************************************************

                      CSDB Library, Free Evaluation Version 2.2.0 
                                           Release: June 9th 1997 

       BTREE classes.

                                           Copyright(c) 1994-1997 
                                                          ComBits 
                                                  The Netherlands 
***********************************************************************/

#ifndef __CSBTREE_H
#define __CSBTREE_H

#include "cstbase.h"
#include "cscopton.h"



////////////////////////////////////////////////////////////////////////////
// The Class used by the BTREE to store its data.
// We can use TBASE or RBASE.
//

class BBASE: public TBASE {};
//#define BBASE TBASE

/////////////////////////////////////////////////////////////////////////////////
/////////////////////////// Btree POINTER. //////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////


typedef U32 BPOINT;


/////////////////////////////////////////////////////////////////////////////////
/////////////////////////// Functions for comparing keys. //////////////////////////
/////////////////////////////////////////////////////////////////////////////////


inline int cs_comp_bin(void *a,void *b,int len)
{
   return memcmp(a,b,len);
}

inline int cs_comp_int(void *a,void *b)
{
  if(*(int *)a < *(int *)b) return -1;
  if(*(int *)a > *(int *)b) return  1;
  return 0;
}

inline int cs_comp_cha(void *a,void *b)
{
  return ((int)*(S8 *)a)-((int)*(S8 *)b);
}

inline int cs_comp_lon(void *a,void *b)
{
  if(*(long *)a < *(long *)b) return -1;
  if(*(long *)a > *(long *)b) return  1;
  return 0;
}

inline int cs_comp_flo(void *a,void *b)
{
  if(*(float *)a < *(float *)b) return -1;
  if(*(float *)a > *(float *)b) return	1;
  return 0;
}


inline int cs_comp_dou(void *a,void *b)
{
  if(*(double *)a < *(double *)b) return -1;
  if(*(double *)a > *(double *)b) return  1;
  return 0;
}

inline int cs_comp_asc(void *a,void *b,int len)
{
   return pStrnicmp((csCHAR *)a,(csCHAR *)b,len);
}




/////////////////////////////////////////////////////////////////////////////////
/////////////////////////// Current Pointer structure. //////////////////////////
/////////////////////////////////////////////////////////////////////////////////


typedef struct
{
   int	  nr;	 // The current number in the block
   int	  mk_n;  // The current number in the frame
   BPOINT block; // The current block
   BPOINT mk_f;  // The current frame
} BTCP; 	 // BTree Current Pointer



/////////////////////////////////////////////////////////////////////////////////
/////////////////////////// Generic BTREE class. ////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////


class BTREE: public BBASE
{

   protected:

       typedef struct
       {
	  BPOINT rnr;	// .................right .........
	  BPOINT tr;	// This Record
	  BPOINT up;	// Up pointer
	  BPOINT lnr;	// Record number of left neighbour
	  U8	 nr;	// Number of keys
       } d_block;

       typedef struct
       {
	  BPOINT lnr;	// Record number of left neighbour (Previous)
	  BPOINT rnr;	// .................right ......... (Next)
	  U8	 nr;	// Number of data elements
       } m_block;



    protected:

      BPOINT root;	 // Root of the btree.
      BPOINT empt;	 // Empty block chain.
      BPOINT *paal;	 // PAth ALlocation.
      BPOINT *path;	 // Path from the root to the leave.
      BPOINT mk_empt;	 // mk_ Empty data frames.
      int    levels;	 // Number of levels in the btree, including DATA layer
      int    datlen;	 // Length of data field.
      int    keylen;	 // Length of key field.
      int    kdlen;	 // Length of key- and data field combined.
      int    kdmklen;	 // Length of key- + data field + mk.
      int    kplen;	 // Length of keyfield and BPOINT combined.
      int    pml;	 // Path Max Length.
      int    mulkey;	 // Multiple keys allowed.
      void   *tmp_key;	 // Storage for temporary keys.
      long   num_key;	 // Number of Keys in Btree.
      BPOINT curr_block; // The current block.
      int    curr_nr;	 // The current number in the block.
      BPOINT curr_mk_f;  // The current frame.
      int    curr_mk_n;  // The current number in the frame.


    protected:

    /////////////////////// Multiple Key Support //////////////////////
    //	mdf:	Multiple Data Frame

      int   nimdf;     // Number of data elements In a mdf.
      int   mkop;      // Number of Multiple data frames on a page.
      int   somdf;     // Size Of a mdf. (Number of bytes in a mdf.)
      int   mk_shift;
      int   mk_and;

      int   mk_oib_a;
      int   mk_oimdf_a;

      int   mk_oib(int n)	   { return mk_oib_a+n*somdf; }
      int   mk_oimdf(int n)	   { return mk_oimdf_a+n*datlen; }

      csCHAR *mk_p2cp(void *p,int n) { return (csCHAR *)p+mk_oib(n); }

      BPOINT &mk_n_mdf(void *p)   { return (((m_block *)p)->rnr); }
      BPOINT  mk_n_mdf(BPOINT b)  { return mk_n_mdf(mk_p2mdf(b)); }
      BPOINT &mk_n_mdfd(BPOINT b) { return mk_n_mdf(mk_p2mdfd(b)); }
      BPOINT &mk_p_mdf(void *p)   { return (((m_block *)p)->lnr); }
      BPOINT  mk_p_mdf(BPOINT b)  { return mk_p_mdf(mk_p2mdf(b)); }
      BPOINT &mk_p_mdfd(BPOINT b) { return mk_p_mdf(mk_p2mdfd(b)); }

      void   mk_connect(BPOINT l,BPOINT r)
	       { if(l) mk_n_mdfd(l)=r; if(r) mk_p_mdfd(r)=l; }
      void   mk_empty(BPOINT b);
      void   mk_new_page(void);

      BPOINT  mk_new_frame(void);
      BPOINT  mk_2mkp(BPOINT b,int i)	{ return ((b<<mk_shift)|i); }

      csCHAR  *mk_p2mdf(BPOINT b)  { return p2cp(b>>mk_shift)+mk_oib(b&mk_and);  }
      csCHAR  *mk_p2mdfd(BPOINT b) { return p2cpd(b>>mk_shift)+mk_oib(b&mk_and); }

      csCHAR  *mk_dataif(void *p,int i) { return (csCHAR *)p+mk_oimdf(i); }
      csCHAR  *mk_data_l(void *p)	{ return mk_dataif(p,mk_nr(p)); }
      csCHAR  *mk_search(BPOINT &b,void *dat, int &nr);
      csCHAR  *mk_insert(BPOINT &b,void *dat);

      int   mk_delet(BPOINT &b,void *dat);

      void  mk_free_chain(BPOINT b);
      void  mk_zap(void);
      void  mk_define(void);
      void  mk_close(void);
      void  mk_open(void);
      void  mk_last(BPOINT b)	 { curr_mk_n=mk_nr(mk_p2mdf(curr_mk_f=mk_p_mdf(b))); }
      void *mk_last_p(BPOINT b);

      U8    &mk_nr(void *p)	 { return (((m_block *)p)->nr); }


    /////////////////////// Accessing Header Block ////////////////////

	 U8 &DNR(void *p)  { return (((d_block *)(p))->nr);  }
     BPOINT &DLNR(void *p) { return (((d_block *)(p))->lnr); }
     BPOINT &DRNR(void *p) { return (((d_block *)(p))->rnr); }
     BPOINT &BTR(void *p)  { return (((d_block *)(p))->tr);  }

    /////////////////////// Splitting Data Block //////////////////////

      int   dmnk;      // Data Max Number of Keys
      int   dnbc;      // Data Number of Bytes Copied
      int   dsco;      // Data Source Copy Offset
      int   ddco;      // Data Destination Copy Offset
      U8    dnnr;      // Data New NumbeR; the higher keys
      U8    donr;      // Data Old NumbeR; the lower keys

    /////////////////////// Splitting Index Block //////////////////////

      int   imnk;      // Index Max Number of Keys
      int   inbc;      // Index Number of Bytes Copied
      int   isco;      // Index Source Copy Offset
      int   idco;      // Index Destination Copy Offset
      U8    innr;      // Index New NumbeR; the higher keys
      U8    ionr;      // Index Old NumbeR; the lower keys

      int a_oiib;      // Offset in indexblock calculation
      int b_oiib;

      int a_oidb;      // Offset in datablock calculation
      int b_oidb;

 protected:

     int  moving_min(BPOINT &b,int &n,int delta,void *&bp);
     int  moving_plus(BPOINT &b,int &n,int delta,void *&bp);

     int  moving_plus(void *&bp,int &n);
     int  moving_min(void *&bp,int &n);

     int  prev_u(int n,void *&key,void *&data);
     int  prev(int n,void *&bp);
     int  next(int n,void *&bp);
     int  next_u(int n,void *&key,void *&data);

    /////////////////////// Skipping fields  within a Block //////////////////
      csCHAR   *skfidb(void *p)      { return (((csCHAR *)p)+keylen); }
      BPOINT   *s2fidb(void *p)      { return (BPOINT *)(((csCHAR *)p)+kdlen); }
      csCHAR   *skfiib(void *p)      { return (((csCHAR *)p)+keylen); }
      csCHAR   *spfiib(void *p)      { return (((csCHAR *)p)+sizeof(BPOINT));  }
      csCHAR   *fkiib(void *p)	     { return (((csCHAR *)p)+sizeof(d_block)); }
      csCHAR   *lkiib(void *p)	     { return (((csCHAR *)p)+oiib(DNR(p)));    }
      csCHAR   *nkiib(void *p,int n) { return (csCHAR *)p+oiib(n); }

      csCHAR   *lkidb(void *p)	     { return (csCHAR *)p+oidb(DNR(p)); }
      csCHAR   *nkidb(void *p,int n) { return (csCHAR *)p+oidb(n);}
      csCHAR   *fkidb(void *p)	     { return (csCHAR *)p+sizeof(d_block); }

    ///////////////////////// DB Header ///////////////////////////////////
      virtual int read_header(void);
      virtual int write_header(void);


    /////////////////////// type of database ////////////////////////////////
      virtual int check_id(U32 id);
      virtual void set_id(void);

    /////////////////////// Copying /////////////////////////////////////////
      void  copy_dat(void *d,void *s)	      { memcpy(d,s,datlen); }
      void  copy_poi(void *d,BPOINT &s)       { *(BPOINT *)d=s; }
      virtual void copy_key(void *d,void *s)  { memcpy(d,s,keylen); }

    /////////////////////// Delete Aid //////////////////////////////////////
      void  delet(void *b,void *KeyPos,int KeyNr);

    /////////////////////// Create/Free Block //////////////////////////////////
      void  c_root(void *keyl,BPOINT l,void *keyr,BPOINT r);
      void  c_root(void *keyl,BPOINT l);
    csCHAR *c_block(void);
      void  f_block(void *p);

    /////////////////////// Connecting blocks //////////////////////////////
      void  connect(void *l,void *r)   { DRNR(l)=BTR(r); DLNR(r)=BTR(l); }
      void  connect(BPOINT l,void *r);
      void  connect(void *l,BPOINT p);
      void  connect(BPOINT l,BPOINT p);

    /////////////////////// Splitting blocks ////////////////////////////////
      void  calc_split_info(int ig,int dg);
      void  split_data(void *lb,csCHAR *&hb);
      void  split_index(void *b,csCHAR *&c);

    /////////////////////// Removing key from block /////////////////////////
      int   rkajib(void *b,void *KeyPos,int KeyNr);
      void  rkajdb(void *b,void *KeyPos,int KeyNr);
      void  rkfib(void *block,void *KeyPos,int KeyNr);
      void  rkfdb(void *block,void *KeyPos,int KeyNr);

    /////////////////////// Insert key in block ////////////////////////////////
      void  ikasdb(void *b,csCHAR *kp,int nr,void *key,void *data);
      void  ikiib(void *b,csCHAR *kp,int nr,void *key,BPOINT dat);
      void  ikidb(void *b,csCHAR *kp,int nr,void *key,void *data);
      void  insert_index(void *key,BPOINT dow);

    /////////////////////// Searching for a key ////////////////////////////////
      csCHAR *ski2ib(void *b,void *key,int &nr);
      csCHAR *skiib(void *b,void *key,int &nr);
      csCHAR *ski2ib(void *b,void *key) { int nr; return ski2ib(b,key,nr); }
      csCHAR *skiib(void *b,void *key)	{ int nr; return skiib(b,key,nr);  }
      csCHAR *skidb(void *b,void *key)	{ int nr; return skidb(b,key,nr);  }
      csCHAR *skidb(void *b,void *key,int &nr);

    /////////////////////// Reading from file //////////////////////////////////
      csCHAR *p2cpd(BPOINT p)	      { return (csCHAR *)locate_rec_d(p); }
      csCHAR *p2cp(BPOINT p)	      { return (csCHAR *)locate_rec(p); }
      csCHAR *p2cpl(BPOINT p)	      { return (csCHAR *)locate_rec_l(p); }

    /////////////////////// Comparing keys /////////////////////////////////////////////
      virtual int t_key(void *a,void *b)=0;
      int  t_dat(void *a,void *b) { return memcmp(a,b,datlen); }

    /////////////////////// Dirty /////////////////////////////////////////////
      void  block_dirty(void *block) { BBASE::dirty(block); }

    /////////////////////// Miscellaneous /////////////////////////////////////
      void   reporter(FILE *fp,BPOINT p,int lev);
      void   expand(void *key,void *data);

      int    oiib(int n)	 { return a_oiib+n*b_oiib; }
      int    oidb(int n)	 { return a_oidb+n*b_oidb; }

      int    nill(BPOINT &p)	 { return !p; }
      int    index_full(void *p) { return (DNR(p)==imnk); }
      int    data_full(void *p)  { return (DNR(p)==dmnk); }
      int    data_low(void *p)	 { return (DNR(p)<=donr); }
      int    index_low(void *p)  { return (DNR(p)<=ionr); }
      BPOINT set_nill(BPOINT &p) { return (p=0); }
      BPOINT sdb(void *key);

      void   nill_mk(void *kp)	 { if(multiple_keys()) set_nill(*s2fidb(kp)); }

      int    search_gt(void *key,void *&kp);
      int    search_ge(void *key,void *&kp);
      int    search_le_u(void *key,void *&kp,void *&da);
      int    search_lt_u(void *key,void *&kp,void *&da);



////////////////////////////////////////////////////////////////////////
////////////////////// PUBLIC FUNCTIONS ////////////////////////////////
////////////////////////////////////////////////////////////////////////

    public:


      BTREE(void );
      virtual
     ~BTREE(void );


//////////////////////// Definition //////////////////////////////////////////
      int   define(csCHAR *name, int key_l,int dat_l);

//////////////////////// Open & Close ////////////////////////////////////////
      int   open(csCHAR *name, int kb_buff=32);
      int   open(void)	  { return already_open(); }
      int   close(void);

////////////////////////// Deleting ////////////////////////////////////////////
      int   delet(void *key);
      int   delet(void *key,void *data);

////////////////////////// Inserting ///////////////////////////////////////////
      int   insert(void *key,void *data);

////////////////////////  Testing Begin & End /////////////////////////////////
      int   tBOF(void);    // test Begin Of BTREE
      int   tEOF(void);    // test End	 Of BTREE

////////////////////////  First and Last entries //////////////////////////////
      int   csmin(void);
      int   csmin(void *Key,void *Data);
      int   min_dat(void *Data);
      int   min_key(void *Key);

      int   first(void) 		 { return csmin(); }
      int   first(void *Key,void *Data)  { return csmin(Key,Data); }
      int   first_dat(void *Data)	 { return min_dat(Data);  }
      int   first_key(void *Key)	 { return min_key(Key);   }

      int   csmax(void);
      int   csmax(void *Key,void *Data);
      int   max_dat(void *Data);
      int   max_key(void *Key);

      int   last(void)		       { return csmax(); }
      int   last(void *Key,void *Data) { return csmax(Key,Data); }
      int   last_dat(void *Data)       { return max_dat(Data); }
      int   last_key(void *Key)        { return max_key(Key);  }

//////////////////////// Checking for Existence //////////////////////////////
      int   find(void *key,void *data);
      int   find(void *key);

//////////////////////// Searching ////////////////////////////////////////////

      int   search(void *key,void *Data);

      int   search_gt(void *key,void *Key,void *Data);
      int   search_ge(void *key,void *Key,void *Data);
      int   search_lt(void *key,void *Key,void *Data);
      int   search_le(void *key,void *Key,void *Data);

      int   search_dat_gt(void *key,void *Data);
      int   search_dat_ge(void *key,void *Data);
      int   search_dat_lt(void *key,void *Data);
      int   search_dat_le(void *key,void *Data);

      int   search_key_gt(void *key,void *Key);
      int   search_key_ge(void *key,void *Key);
      int   search_key_lt(void *key,void *Key);
      int   search_key_le(void *key,void *Key);


//////////////////////// Skipping /////////////////////////////////////////////

      int   prev(void);
      int   prev(int n);
      int   prev_key(int n,void *Key);
      int   prev_dat(int n,void *Data);
      int   prev(int n,void *Key,void *Data);

      int   next(void);
      int   next(int n);
      int   next_key(int n,void *Key);
      int   next_dat(int n,void *Data);
      int   next(int n,void *Key,void *Data);

      int   skip(int n) { return ((n>0) ? next(n): -prev(-n)); }

      int   skip(int n,void *Key,void *Data)
	    {  if(n>0) return  next( n,Key,Data);
	       else    return -prev(-n,Key,Data); }
      int   skip_key(int n,void *Key)
	    {  if(n>0) return  next_key( n,Key);
	       else    return -prev_key(-n,Key); }
      int   skip_dat(int n,void *Dat)
	    {  if(n>0) return  next_dat( n,Dat);
	       else    return -prev_dat(-n,Dat); }

//////////////////////// Current location /////////////////////////////////////
      int   current(void *Key,void *Data);
      int   current_key(void *Key);
      int   current_dat(void *Data);

      int   save_current(BTCP &b);
      void  restore_current(BTCP &b);

//////////////////////// Report Writing //////////////////////////////////////
      void  report(csCHAR *rname,int sub=1);
      void  report(FILE *fp,int sub=1);

//////////////////////// Number of Keys //////////////////////////////////////
      long  numkey(void)  { return num_key; }

////////////////////////// Miscellaneous ///////////////////////////////////////
      int   pack(void);
      void  zap(void);
      void  info(void );
      void  empty(void);
      int   key_length(void)		   { return keylen; }
      int   data_length(void)		   { return datlen; }
      void  multiple_keys(int TrueOrFalse);
      void  multiple_keys_YES(void)	   { multiple_keys(TRUE);  }
      void  multiple_keys_NO(void)	   { multiple_keys(FALSE); }
      int   multiple_keys(void	)	   { return mulkey; }
      virtual int class_ID(void)	   { return CS_CLID_BTREE; }


};






/////////////////////////////////////////////////////////////////////////////////
/////////////////////////// 'Specialised' BTREEs. ////////////////////////////
/////////////////////////////////////////////////////////////////////////////////
//
//   Mainly, these BTREE's differ only in the function used to
//   compare keys: t_key().
//
//
//
//

/////////////////////////////////////////////////////////////////////////////////
/////////////////////////// BTREE for binary data ///////////////////////////////

class BTREEb: public BTREE
{
    virtual int t_key(void *a,void *b) { return cs_comp_bin(a,b,keylen); }
    virtual int class_ID(void)	       { return CS_CLID_BTREEb; }
};

/////////////////////////////////////////////////////////////////////////////////
/////////////////////////// BTREE for integers //////////////////////////////////

class BTREEi: public BTREE
{
   virtual int t_key(void *a,void *b) { return cs_comp_int(a,b); }
   virtual int class_ID(void)	      { return CS_CLID_BTREEi; }
};

/////////////////////////////////////////////////////////////////////////////////
/////////////////////////// BTREE for characters ////////////////////////////////

class BTREEc: public BTREE
{
    virtual int t_key(void *a,void *b) { return cs_comp_cha(a,b); }
    virtual int class_ID(void)	       { return CS_CLID_BTREEc; }
};

/////////////////////////////////////////////////////////////////////////////////
/////////////////////////// BTREE for longs /////////////////////////////////////

class BTREEl: public BTREE
{
   virtual int t_key(void *a,void *b) { return cs_comp_lon(a,b); }
   virtual int class_ID(void)	      { return CS_CLID_BTREEl; }

};

/////////////////////////////////////////////////////////////////////////////////
/////////////////////////// BTREE for floating points ///////////////////////////

class BTREEf: public BTREE
{
    virtual int t_key(void *a,void *b) { return cs_comp_flo(a,b); }
    virtual int class_ID(void)	       { return CS_CLID_BTREEf; }
};

/////////////////////////////////////////////////////////////////////////////////
/////////////////////////// BTREE for doubles ///////////////////////////////////

class BTREEd: public BTREE
{
    virtual int t_key(void *a,void *b) { return cs_comp_dou(a,b); }
    virtual int class_ID(void)	       { return CS_CLID_BTREEd; }
};

/////////////////////////////////////////////////////////////////////////////////
/////////////////////////// BTREE for strings ///////////////////////////////////

class BTREEa: public BTREE
{
    virtual void copy_key(void *d,void *s);
    virtual int t_key(void *a,void *b) { return cs_comp_asc(a,b,keylen-1); }
    virtual int class_ID(void)	       { return CS_CLID_BTREEa; }
};




#include "cscoptof.h"

#endif
