00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #ifndef _BISECTION_H
00019 #define _BISECTION_H
00020
00021 namespace LA {
00022
00023
00024
00025
00026
00027 template<typename INDEX, typename COMPAR, typename SUBJECT>
00028 INDEX bisection_find(INDEX dm, INDEX hm, const SUBJECT *key, const SUBJECT *base , unsigned int lead_dimension_base, COMPAR (*cmp)(const SUBJECT *, const SUBJECT *))
00029 {
00030 if(dm>hm) return(dm-1);
00031 if(dm==hm) return (*cmp)(base+dm*lead_dimension_base,key)? dm-1 :dm;
00032 INDEX sm;
00033 INDEX dm0=dm;
00034 --dm;
00035 ++hm;
00036 do
00037 {
00038 sm = (dm+hm)/2;
00039 COMPAR q = (*cmp)(base+sm*lead_dimension_base,key);
00040 if (!q) return(sm);
00041 else if (q<0) dm = sm; else hm = sm;
00042 }
00043 while (hm > dm+1);
00044 return(dm0-1);
00045 }
00046
00047
00048
00049
00050
00051 template<typename INDEX, typename DISTANCE, typename SUBJECT>
00052 int interpolation_find(INDEX dm0, INDEX high, const SUBJECT *x, const SUBJECT *base , unsigned int lead_dimension_base, DISTANCE (*dist)(const SUBJECT *, const SUBJECT *))
00053 {
00054 INDEX low = dm0;
00055 INDEX mid;
00056 DISTANCE d1,d2,d3,d4;
00057
00058 while(1)
00059 {
00060 d1=(*dist)(x,base+low*lead_dimension_base);
00061 d2=(*dist)(base+high*lead_dimension_base,x);
00062 if(d1<=0 || d2 <=0) break;
00063 d3=(*dist)(base+high*lead_dimension_base,base+low*lead_dimension_base);
00064 mid = low + (int)((d1 * (high-low)) / d3);
00065 if(mid<low||mid>high) laerror("interpolation_find: error in distance function");
00066 d4=(*dist)(x,base+mid*lead_dimension_base);
00067 if(d4>0)
00068 low = mid + 1;
00069 else if(d4<0)
00070 high = mid - 1;
00071 else
00072 return mid;
00073 }
00074
00075 if (d1==0) return low;
00076 if (d2==0) return high;
00077 return dm0-1;
00078 }
00079
00080
00081 }
00082 #endif