Changeset 13577

Timestamp:

10/10/12 07:39:19 (12 years ago)

Author:

Mathieu Morlighem

Message:

CHG: even simpler binary_search for doubles: return segment number

Location:

issm/trunk-jpl/src/c

Files:

• classes/objects/Inputs/TransientInput.cpp (modified) (3 diffs)
• shared/Sorting/binary_search.cpp (modified) (2 diffs)

issm/trunk-jpl/src/c/classes/objects/Inputs/TransientInput.cpp

@@ -426 +426 @@
 Input* TransientInput::GetTimeInput(IssmDouble intime){
 
-        IssmDouble  deltat;
-        IssmDouble  alpha1,alpha2;
+        IssmDouble deltat;
+        IssmDouble alpha1,alpha2;
+        int        found;
+        int        offset;
         
         Input *input  = NULL;
@@ -433 +435 @@
         Input *input2 = NULL;
         
-        bool    found=false;
-        int     found_offset=0;
-        int     offset;
-
-        /*Ok, we have the time, go through the timesteps, and figure out which interval we 
+        /*go through the timesteps, and figure out which interval we 
          *fall within. Then interpolate the values on this interval: */
-        found_offset=binary_search(&offset,intime,this->timesteps,this->numtimesteps);
-        if (found_offset==0) _error_("Input not found (is TransientInput sorted ?)");
-
-        if (found_offset==-1){
+        found=binary_search(&offset,intime,this->timesteps,this->numtimesteps);
+        if(!found) _error_("Input not found (is TransientInput sorted ?)");
+
+        if (offset==-1){
                 /*get values for the first time: */
                 _assert_(intime<this->timesteps[0]);
                 input=(Input*)((Input*)this->inputs->GetObjectByOffset(0))->copy();
-                found=true;
-        }
-        else if(found_offset==3){
+        }
+        else if(offset==(this->numtimesteps-1)){
                 /*get values for the last time: */
-                _assert_(intime>=this->timesteps[this->numtimesteps-1]);
-                input=(Input*)((Input*)this->inputs->GetObjectByOffset(this->numtimesteps-1))->copy();
-                found=true;
-        }
-        else if(found_offset==2){
-                /*get values for this time: */
-                _assert_(intime==this->timesteps[offset]);
+                _assert_(intime>=this->timesteps[offset]);
                 input=(Input*)((Input*)this->inputs->GetObjectByOffset(offset))->copy();
-                found=true;
         }
         else{
-                /*get values between two times ]offset:offset+1[, Interpolate linearly*/
-                _assert_(intime>this->timesteps[offset] && intime<this->timesteps[offset+1]);
+                /*get values between two times [offset:offset+1[, Interpolate linearly*/
+                _assert_(intime>=this->timesteps[offset] && intime<this->timesteps[offset+1]);
                 deltat=this->timesteps[offset+1]-this->timesteps[offset];
                 alpha2=(intime-this->timesteps[offset])/deltat;
@@ -473 +463 @@
                 input->Scale(alpha1);
                 input->AXPY(input2,alpha2);
-
-                found=true;
         }
 

issm/trunk-jpl/src/c/shared/Sorting/binary_search.cpp

@@ -64 +64 @@
         return found;
 } /*}}}*/
-int binary_search(int* poffset,double target,double* list,int num_doubles){ /*{{{*/
+int binary_search(int* poffset,double target,double* list,int length){ /*{{{*/
+        /*
+         *             l[0]  l[1]  l[2]        l[n]  l[n+1]   l[length-1]
+         *     <-------+-----+-----+-----+ ... +-----+........+-------------->
+         * offset: -1     0     1     2           n              length -1
+         *  
+         *  offset = -1        target < list[0]
+         *  offset = n         list[n] <= target < list[n+1]
+         *  offset = length-1  list[length-1] <= target
+         */
 
         /*output: */
         int offset = 0;
-        int found  = 0; /*found =  0: not found.
-                                                        found = -1: found, and target is < first element
-                                                        found =  1: found, and target is == to value at offset 
-                                                        found =  2: found, and target is > to value at offset  and < to value at offset+1
-                                                        found =  3: found, and target is >= last value */
+        int found  = 0;
 
         /*intermediary: */
         int n0 = 0;
-        int n1 = int(num_doubles/2);
-        int n2 = num_doubles-1;
+        int n1 = int(length/2);
+        int n2 = length-1;
 
         if(target<list[n0]){
-                found  = -1;
+                found  = 1;
                 offset = -1;
         }
         else if(target>=list[n2]){
-                found  = 3;
-                offset = n2-1;
+                found  = 1;
+                offset = length-1;
         }
         else{
-                while(!found){
+                for(;;){
                         /*did we find the target?*/
                         if(list[n1]<=target && list[n1+1]>target){
-                                found = 1;
+                                found  = 1;
                                 offset = n1;
                                 break;
                         }
-                        if(target < list[n1]){
+                        else if(target < list[n1]){
                                 n2 = n1;
                                 n1 = n0 + int((n2-n0)/2);
@@ -104 +109 @@
                         }
                 }
-
-                //did we find an exact target?
-                if(list[n1]==target) found = 2;
         }
 
-        /*Assign output pointers:*/
+        /*Assign output pointer and return*/
         *poffset=offset;
-        
-        /*Return result: */
         return found;
 } /*}}}*/