guma Namespace Reference

00221 {
00222   int mid,right,left;
00223 
00224   if( nA == 0 ) 
00225   {
00226     *rleft = -1;
00227     *rright = -1;
00228     return -1;
00229   }
00230 
00231   if( A[0] >=  x )
00232   {
00233     *rright = 0;
00234 
00235     if( A[0] > x ) 
00236     {
00237       *rleft = -1; 
00238       return -1;
00239     }
00240     else
00241     {
00242       *rleft = 0;
00243       return 0;
00244     }
00245   }
00246 
00247   if( A[nA-1] <=  x )
00248   {
00249     *rleft = nA-1;
00250 
00251     if( A[nA-1] < x )
00252     {
00253       *rright = -1;
00254       return -1;
00255     }
00256     else
00257     {
00258       *rright = nA-1;
00259       return nA-1;
00260     }
00261   }
00262 
00263   left = 0;
00264   right = nA;
00265   mid = (left+right)/2;
00266 
00267   while( (mid!=left) && (mid!=right) )
00268   {  
00269     if( A[mid] == x  )
00270       break;
00271     else if( A[mid] > x )
00272     {
00273       right = mid;
00274       mid = (left+right)>>1;
00275     }
00276     else
00277     {
00278       left = mid;
00279       mid = (left+right)>>1;
00280     }
00281   }
00282   if( A[mid] != x )
00283   {
00284     *rleft = left;
00285     *rright = right;
00286     return -1;
00287   }
00288   else
00289   {
00290     *rleft = mid;
00291     *rright = mid;
00292   }
00293  
00294   return mid;
00295 }

00169 {
00170   int mid,right,left;
00171 
00172   if( nA == 0 ) return -1;
00173 
00174   if( A[0] >=  x )
00175   {
00176     if( A[0] > x ) return -1;
00177     return 0;
00178   }
00179   if( A[nA-1] <=  x )
00180   {
00181     if( A[nA-1] < x ) return -1;
00182     return nA-1;
00183   }
00184 
00185   left = 0;
00186   right = nA;
00187   mid = (left+right)/2;
00188 
00189   while( (mid!=left) && (mid!=right) )
00190   {  
00191     if( A[mid] == x  )
00192       break;
00193     else if( A[mid] > x )
00194     {
00195       right = mid;
00196       mid = (left+right)>>1;
00197     }
00198     else
00199     {
00200       left = mid;
00201       mid = (left+right)>>1;
00202     }
00203   }
00204   if( A[mid] != x ) return -1;
00205 
00206   return mid;
00207 }

00110 {
00111   gul::Ptr<T>& ra = A;
00112   T rra;
00113   int n = nA, l, ir, i, j;
00114 
00115   if( n < 2 ) return;
00116   l = (n >> 1) + 1;
00117   ir = n;
00118   
00119   for(;;)
00120   {
00121     if( l > 1 )
00122     {
00123       rra = ra[l-2];
00124       l--;    
00125     }
00126     else
00127     {
00128       rra = ra[ir-1];
00129       ra[ir-1] = ra[0];
00130       
00131       if( --ir == 1 )
00132       {
00133         ra[0] = rra;
00134         break;
00135       }
00136     }
00137     i = l;
00138     j = l+l;
00139 
00140     while( j <= ir )
00141     {
00142       if( (j < ir) && (ra[j-1] < ra[j]) )
00143         j++;
00144   
00145       if( rra < ra[j-1] )
00146       {
00147         ra[i-1] = ra[j-1];
00148         i = j;
00149         j <<= 1;
00150       }
00151       else
00152         j = ir + 1;
00153     }
00154 
00155     ra[i-1] = rra;
00156   }
00157 }

00396 {
00397   int i,k,l,mm;
00398   T dum;
00399 
00400   mm = m1 + m2 + 1;
00401   l = m1;
00402 
00403   for( k = 0; k < n; k++ ) /* Forward substitution */
00404   {
00405     i = index[k];
00406     if( i != k ) Swap( b[k], b[i] );
00407     if( l < n ) l++;
00408     for( i = k+1; i < l; i++ )
00409       b[i] -= L[k][i-k-1]*b[k];
00410   }
00411   l = 1;
00412   for( i = n-1; i >= 0; i-- ) /* Forward substitution */
00413   {
00414     dum = b[i];
00415     for( k = 1; k < l; k++ )
00416       dum -= A[i][k]*b[k+i];
00417     b[i] = dum/A[i][0];
00418     if( l < mm ) l++;
00419   }
00420 }

00323 {
00324   int i,j,k,l,mm,d;
00325   T dum;
00326 
00327   mm = m1 + m2 + 1;
00328   l = m1;
00329   for( i = 0; i < m1; i++ )
00330   {
00331     for( j = m1-i; j < mm; j++ )
00332       A[i][j-l] = A[i][j];
00333     l--;
00334     for( j = mm-l-1; j < mm; j++ )
00335       A[i][j] = 0.0;
00336   }
00337   d = 1;
00338   l = m1;
00339 
00340   for( k = 0; k < n; k++ )
00341   {
00342     dum = A[k][0];
00343     i = k;
00344 
00345     if( l < n ) l++;
00346     for( j = k+1; j < l; j++ )
00347     {
00348       if( rtr<T>::fabs(A[j][0]) > rtr<T>::fabs(dum) )
00349       {
00350         dum = A[j][0];
00351         i = j;
00352       }
00353     }
00354     index[k] = i;
00355 
00356     if( dum == 0.0 )     /* if algorithmically singular */
00357       A[k][0] = rtr<T>::tiny();
00358 
00359     if( i != k )         /* interchange rows */
00360     {
00361       d = -d;
00362       for( j = 0; j < mm; j++ )
00363         Swap( A[k][j], A[i][j] );
00364     }
00365     
00366     for( i = k+1; i < l; i++ )  // i = i'+1
00367     {
00368       dum = A[i][0]/A[k][0];
00369       L[k][i-k-1] = dum;
00370 
00371       for( j = 1; j < mm; j++ )
00372         A[i][j-1] = A[i][j] - dum*A[k][j];
00373 
00374       A[i][mm-1] = 0.0;
00375     }
00376   }
00377   *perm_sign = d;
00378 }

00288 {
00289   int i,k,j,m;
00290 
00291   for( i = 0; i < n; i++ )
00292   {
00293     k = i - m1;
00294 
00295     m = Min(m1+m2+1,n-k);
00296 
00297     b[i] = 0;
00298 
00299     for( j = Max(0,-k); j < m; j++ )
00300       b[i] += a[i][j] * x[j+k];
00301   }
00302 }

00154 { return _BinarySearch( x, nA, A); }

00152 { return _BinarySearch( x, nA, A); }

00052 {
00053   point<U> a1,a2,a3,b1,b2,b3;
00054   Ptr< Ptr<U> > Ta,Tb;
00055   int i;
00056 
00057   Ta.reserve_pool(3);
00058   Tb.reserve_pool(3);
00059   for( i = 0; i < 3; i++ )
00060   {
00061     Ta[i].reserve_pool(3);
00062     Tb[i].reserve_pool(3);
00063   }
00064 
00065   normalize( &a1, B );
00066   normalize( &a2, P-((P*a1)*a1) );
00067   normalize( &a3, cross_product(a1,a2) );
00068 
00069   normalize( &b1, -Ab );
00070   normalize( &b2, P-((P*b1)*b1) );
00071   normalize( &b3, cross_product(b1,b2) );
00072 
00073   Tb[0][0] = b1[0];   Tb[0][1] = b1[1];  Tb[0][2] = b1[2];
00074   Tb[1][0] = b2[0];   Tb[1][1] = b2[1];  Tb[1][2] = b2[2];
00075   Tb[2][0] = b3[0];   Tb[2][1] = b3[1];  Tb[2][2] = b3[2];
00076 
00077   GaussJordan( 3, 0, Tb, Tb ); 
00078 
00079   Ta[0][0] = a1[0];   Ta[0][1] = a1[1];  Ta[0][2] = a1[2];
00080   Ta[1][0] = a2[0];   Ta[1][1] = a2[1];  Ta[1][2] = a2[2];
00081   Ta[2][0] = a3[0];   Ta[2][1] = a3[1];  Ta[2][2] = a3[2];
00082 
00083   MMProduct( 3, 3, 3, Tb, Ta, T );  
00084 
00085   T[3][0] = B[0];  T[3][1] = B[1]; T[3][2] = B[2]; T[3][3] = (U)1; 
00086   T[0][3] = T[1][3] = T[2][3] = (U)0; 
00087 }

00602 {
00603   BBTNode *P,*Q,*Pk,*Pk_1,*A,*B,*X;
00604   int ak, ak_1, ak_ini;
00605   
00606   P = head->right;
00607   if( P == NULL ) return;
00608     
00609   P = Q = element;
00610 
00611   if( P->right == NULL )    /* Knoten suchen, bei dem rechter oder */
00612   {                         /* linker Ast = NULL:                  */
00613     Pk = P;
00614     ak = 1;
00615     Pk_1 = Pk->parent;
00616     ak_1 = ak_ini = Pk->F.l;
00617   }
00618   else if( P->left == NULL )
00619   {
00620     Pk = P;
00621     ak = -1;
00622     Pk_1 = Pk->parent;
00623     ak_1 = ak_ini = Pk->F.l;
00624   }
00625   else
00626   {
00627     P = P->right;                    /* nach rechts gehen */    
00628 
00629     if( P->left == NULL )
00630     {
00631       Pk = Q;
00632 
00633       if( Q->F.l == 1 )     
00634       {
00635         Q->parent->right = P;
00636         P->F.l = 1;
00637       }
00638       else
00639       {
00640         Q->parent->left = P;
00641         P->F.l = -1; 
00642       }       
00643       P->parent = Q->parent;
00644       P->F.b = Q->F.b;
00645 
00646       ak = 1;
00647       Pk_1 = P;
00648       ak_1 = -1;    
00649       ak_ini = 1;
00650     }
00651     else
00652     {
00653       do            /* suchen bis Nachfolger in symmetrischer */
00654       {             /* Ordnung gefunden                       */
00655         Pk = P;
00656         P = P->left;
00657       }
00658       while( P != NULL );
00659 
00660       ak = -1;
00661       Pk_1 = Pk->parent;
00662       ak_1 = ak_ini = Pk->F.l;
00663     }
00664   }            
00665 
00666 /* --- Knoten loeschen: -------------------------------------------- */
00667 
00668   if( ak_1 == -1 )                                /* wenn Pk linker Sohn */
00669   {
00670     Pk_1->left = (ak == -1 ? Pk->right : Pk->left);
00671     if( Pk_1->left != NULL )
00672     {
00673       Pk_1->left->parent = Pk_1;
00674       Pk_1->left->F.l = -1;
00675     }
00676   }    
00677   else
00678   {
00679     Pk_1->right = (ak == -1 ? Pk->right : Pk->left);
00680     if( Pk_1->right != NULL )
00681     {
00682       Pk_1->right->parent = Pk_1;
00683       Pk_1->right->F.l = 1;
00684     }
00685   }  
00686 
00687   if( Pk != Q )
00688   {
00689     Pk->left = Q->left;                /* Pk uebernimmt nun die Rolle von Q */
00690     if( Pk->left != NULL )
00691       Pk->left->parent = Pk;
00692     Pk->right = Q->right;
00693     if( Pk->right != NULL )
00694       Pk->right->parent = Pk;
00695 
00696     Pk->F.b = Q->F.b;
00697   
00698     Pk->parent = Q->parent;
00699     Pk->F.l = Q->F.l;
00700     if( Pk->F.l == -1 )
00701       Pk->parent->left = Pk;
00702     else
00703       Pk->parent->right = Pk;
00704   } 
00705                                      /* Q kann jetzt freigeben werden */
00706 
00707 /* --- Balance-Faktoren updaten ------------------------------------- */  
00708 
00709   ak = ak_ini;
00710   Pk = Pk_1;
00711 
00712   while( 1 )
00713   {
00714     if( Pk == head )                       /* Listenkopf */
00715     {
00716       (*((int *)&head->left))--;           /* Hoehe des Baums um 1 erniedrigen */
00717       break;                 /*** fertig ***/
00718     }
00719     else if( Pk->F.b == ak )
00720     {
00721       Pk->F.b = 0;
00722 
00723       ak = Pk->F.l;                       /* k-- */
00724       Pk = Pk->parent;
00725     }
00726     else if( Pk->F.b == 0 )
00727     {
00728       Pk->F.b = -ak;
00729       break;                  /*** fertig ***/
00730     }
00731     else                                 /* rebalancieren erforderlich, */
00732     {                                    /* da (Pk->B == -ak) */
00733       if( ak == -1 )          /*** Ausfuehrung fuer (ak == -1) ***/
00734       {
00735         A = Pk;
00736         ak_1 = Pk->F.l;
00737         Pk_1 = Pk->parent; 
00738 
00739         B = A->right;                     /* B = Zweig auf der anderen Seite */
00740       
00741         if( B->F.b == 1 )                 /* B->B == -ak => Single Rotation */
00742         {
00743           A->right = B->left;             /* LINK(A,-ak) = LINK(B,ak) */
00744           if( A->right != NULL )
00745           {
00746             A->right->parent = A;
00747             A->right->F.l = 1;
00748           }
00749 
00750           B->left = A;                    /* LINK(B,ak) = A */
00751           if( B->left != NULL )
00752           {
00753             B->left->parent = B;
00754             B->left->F.l = -1;
00755           }
00756 
00757           A->F.b = B->F.b = 0;
00758           
00759           ak = ak_1;                       /* k-- */
00760           Pk = Pk_1;
00761           
00762           if( ak == -1 )
00763           {
00764             Pk->left = B;
00765             if( Pk->left != NULL )
00766             {
00767               Pk->left->parent = Pk;
00768               Pk->left->F.l = -1;
00769             }
00770           }  
00771           else
00772           {
00773             Pk->right = B;  
00774             if( Pk->right != NULL )
00775             {
00776               Pk->right->parent = Pk;
00777               Pk->right->F.l = 1;
00778             }
00779           }
00780         }
00781         else if( B->F.b == -1 )           /* (B->B == ak) => Double Rotation */
00782         {
00783           X = B->left;                    /* X = LINK(B,ak) */
00784  
00785           A->right = X->left;             /* LINK(A,-ak) = LINK(X,ak) */
00786           if( A->right != NULL )
00787           {
00788             A->right->parent = A;
00789             A->right->F.l = 1;
00790           }
00791 
00792           B->left = X->right;             /* LINK(B,ak) = LINK(X,-ak) */
00793           if( B->left != NULL )
00794           {
00795             B->left->parent = B;
00796             B->left->F.l = -1;
00797           }
00798           
00799           X->left = A;                    /* LINK(X,ak) = A           */
00800           if( X->left != NULL )
00801           {
00802             X->left->parent = X;
00803             X->left->F.l = -1;
00804           }
00805 
00806           X->right = B;                   /* LINK(X,-ak) = B          */
00807           if( X->right != NULL )
00808           {
00809             X->right->parent = X;
00810             X->right->F.l = 1;
00811           }
00812           
00813           if( X->F.b == -1 )              /* (X->B == ak)             */
00814           {
00815             A->F.b = 0;                   /* A->B = 0                 */
00816             B->F.b = 1;                   /* B->B = -ak               */
00817           }
00818           else if( X->F.b == 1 )          /* (X->B == -ak)            */
00819           {
00820             A->F.b = -1;                  /* A->B = ak                */
00821             B->F.b = 0;                   /* B->B = 0                 */
00822           }
00823           else                            /* B->B = 0                 */
00824           {
00825             A->F.b = 0;
00826             B->F.b = 0;
00827           }
00828           X->F.b = 0; 
00829 
00830           ak = ak_1;                       /* k-- */
00831           Pk = Pk_1;
00832 
00833           if( ak == -1 )
00834           {
00835             Pk->left = X;
00836             if( Pk->left != NULL )
00837             {
00838               Pk->left->parent = Pk;
00839               Pk->left->F.l = -1;
00840             }
00841           }  
00842           else
00843           {
00844             Pk->right = X;  
00845             if( Pk->right != NULL )
00846             {
00847               Pk->right->parent = Pk;
00848               Pk->right->F.l = 1;
00849             }
00850           }
00851         }
00852         else                               /* (B->B == 0) => Single Rotation */
00853         {
00854           A->right = B->left;              /* LINK(A,-ak) = LINK(B,ak)     */
00855           if( A->right != NULL )
00856           {
00857             A->right->parent = A;
00858             A->right->F.l = 1;
00859           }
00860           
00861           B->left = A;                     /* LINK(B,ak) = A               */
00862           if( B->left != NULL )
00863           {
00864             B->left->parent = B;
00865             B->left->F.l = -1;
00866           }
00867 
00868           B->F.b = -1;                     /* B->B = ak                    */
00869 
00870           ak = ak_1;                    /* k-- */
00871           Pk = Pk_1;
00872 
00873           if( ak == -1 )
00874           {
00875             Pk->left = B;
00876             if( Pk->left != NULL )
00877             {
00878               Pk->left->parent = Pk;
00879               Pk->left->F.l = -1;
00880             }
00881           }  
00882           else
00883           {
00884             Pk->right = B;  
00885             if( Pk->right != NULL )
00886             {
00887               Pk->right->parent = Pk;
00888               Pk->right->F.l = 1;
00889             }
00890           }
00891 
00892           break;              /*** fertig ***/
00893         }
00894 
00895 
00896       }
00897       else                    /*** dasselbe nochmal fuer (ak == +1) ***/
00898       {
00899         A = Pk;
00900         ak_1 = Pk->F.l;
00901         Pk_1 = Pk->parent;
00902         
00903         B = A->left;                      /* B = Zweig auf der anderen Seite */
00904       
00905         if( B->F.b == -1 )                /* (B->B == -ak) => Single Rotation */
00906         {
00907           A->left = B->right;             /* LINK(A,-ak) = LINK(B,ak) */
00908           if( A->left != NULL )
00909           {
00910             A->left->parent = A;
00911             A->left->F.l = -1;
00912           }
00913                 
00914           B->right = A;
00915           if( B->right != NULL )
00916           {
00917             B->right->parent = B;
00918             B->right->F.l = 1;
00919           }
00920           
00921           A->F.b = B->F.b = 0;
00922           
00923           ak = ak_1;                       /* k-- */
00924           Pk = Pk_1;
00925         
00926           if( ak == -1 )
00927           {
00928             Pk->left = B;
00929             if( Pk->left != NULL )
00930             {
00931               Pk->left->parent = Pk;
00932               Pk->left->F.l = -1;
00933             }
00934           }  
00935           else
00936           {
00937             Pk->right = B;  
00938             if( Pk->right != NULL )
00939             {
00940               Pk->right->parent = Pk;
00941               Pk->right->F.l = 1;
00942             }
00943           }
00944         }
00945         else if( B->F.b == 1 )            /* (B->B == ak) => Double Rotation */
00946         {
00947           X = B->right;                   /* X = LINK(B,ak) */
00948  
00949           A->left = X->right;             /* LINK(A,-ak) = LINK(X,ak) */
00950           if( A->left != NULL )
00951           {
00952             A->left->parent = A;
00953             A->left->F.l = -1;
00954           }
00955           
00956           B->right = X->left;             /* LINK(B,ak) = LINK(X,-ak) */
00957           if( B->right != NULL )
00958           {
00959             B->right->parent = B;
00960             B->right->F.l = 1;
00961           }
00962 
00963           X->right = A;                   /* LINK(X,ak) = A           */
00964           if( X->right != NULL )
00965           {
00966             X->right->parent = X;
00967             X->right->F.l = 1;
00968           }
00969 
00970           X->left = B;                    /* LINK(X,-ak) = B          */
00971           if( X->left != NULL )
00972           {
00973             X->left->parent = X;
00974             X->left->F.l = -1;
00975           }
00976 
00977           if( X->F.b == 1 )               /* (X->B == ak)             */
00978           {
00979             A->F.b = 0;                   /* A->B = 0                 */
00980             B->F.b = -1;                  /* B->B = -ak               */
00981           }
00982           else if( X->F.b == -1 )         /* (X->B == -ak)            */
00983           {
00984             A->F.b = 1;                   /* A->B = ak                */
00985             B->F.b = 0;                   /* B->B = 0                 */
00986           }
00987           else                            /* B->B = 0                 */
00988           {
00989             A->F.b = 0;
00990             B->F.b = 0;
00991           }  
00992           X->F.b = 0;
00993 
00994           ak = ak_1;                       /* k-- */
00995           Pk = Pk_1;
00996         
00997           if( ak == -1 )
00998           {
00999             Pk->left = X;
01000             if( Pk->left != NULL )
01001             {
01002               Pk->left->parent = Pk;
01003               Pk->left->F.l = -1;
01004             }
01005           }  
01006           else
01007           {
01008             Pk->right = X;  
01009             if( Pk->right != NULL )
01010             {
01011               Pk->right->parent = Pk;
01012               Pk->right->F.l = 1;
01013             }
01014           }
01015         }
01016         else                               /* (B->B == 0) => Single Rotation */
01017         {
01018           A->left = B->right;              /* LINK(A,-ak) = LINK(B,ak)     */
01019           if( A->left != NULL )
01020           {
01021             A->left->parent = A;
01022             A->left->F.l = -1;
01023           }
01024 
01025           B->right = A;                    /* LINK(B,ak) = A               */
01026           if( B->right != NULL )
01027           {
01028             B->right->parent = B;
01029             B->right->F.l = 1;
01030           }
01031           
01032           B->F.b = 1;                      /* B->B = ak                    */
01033 
01034           ak = ak_1;                    /* k-- */
01035           Pk = Pk_1;
01036         
01037           if( ak == -1 )
01038           {
01039             Pk->left = B;
01040             if( Pk->left != NULL )
01041             {
01042               Pk->left->parent = Pk;
01043               Pk->left->F.l = -1;
01044             }
01045           }  
01046           else
01047           {
01048             Pk->right = B;  
01049             if( Pk->right != NULL )
01050             {
01051               Pk->right->parent = Pk;
01052               Pk->right->F.l = 1;
01053             }
01054           }
01055 
01056           break;              /*** fertig ***/
01057         }
01058       }
01059     }    /*** Ende "while"-Schleife ***/
01060   }
01061     
01062   return;
01063 }

01098 {
01099   int i;
01100 
01101   if( node == NULL )
01102     return;
01103     
01104   if( node->left != NULL )
01105     DumpBBTNode( node->left, level+4 );
01106 
01107   for( i = 0; i < level; i++ )
01108   {
01109     cout << " ";
01110   }
01111   cout << (void *)node << ":[b:" << node->F.b << ", l:" << node->F.l <<
01112        "] (l=" << (void *)node->left << ", r=" <<
01113        (void *)node->right << ", p=" << (void *)node->parent << ")\n";
01114 
01115   if( node->right != NULL )
01116     DumpBBTNode( node->right, level+4 );
01117 }

01071 {
01072   int i;
01073 
01074   if( node == NULL )
01075     return;
01076     
01077   if( node->left != NULL )
01078     DumpBBTTree( node->left, level+4, dumpkey_func );
01079 
01080   for( i = 0; i < level; i++ )
01081   {
01082     cout << " ";
01083   }
01084 
01085   if( node->key != NULL )
01086     dumpkey_func( node->key );
01087     cout << "\n";
01088 
01089   if( node->right != NULL )
01090     DumpBBTTree( node->right, level+4, dumpkey_func );
01091 }

00061 {
00062   Ptr<int> indexc,indexr;
00063   Ptr<T> ipivot;
00064   int icol,irow, n,i,j,k,l,ll,m;
00065   T big,pivotinv,dummy;
00066 
00067   n = nRowsCols - 1;
00068   m = nRightSides - 1;
00069 
00070   indexc.reserve_pool(n+1);
00071   indexr.reserve_pool(n+1);
00072   ipivot.reserve_pool(n+1);
00073   
00074   for( j = 0; j <= n; j++ )
00075     ipivot[j] = 0;
00076  
00077   for( i = 0; i <= n; i++ )
00078   {
00079     big = 0.0;
00080     
00081     for( j = 0; j <= n; j++ )
00082     {
00083       if( ipivot[j] != 1 )
00084       {
00085         for( k = 0; k <= n; k++ )
00086         {
00087           if( ipivot[k] == 0 )
00088           {
00089             if( rtr<T>::fabs( A[j][k] ) >= big )
00090             {
00091               big = rtr<T>::fabs( A[j][k] );
00092               irow = j;
00093               icol = k;
00094             }
00095           }
00096           else if( ipivot[k] > 1 )
00097             return false;
00098         }
00099       }
00100     } 
00101     ipivot[icol]++;
00102 
00103     if( irow != icol )
00104     {
00105       for( l = 0; l <= n; l++ )
00106         Swap( A[irow][l], A[icol][l] );
00107       for( l = 0; l <= m; l++ )
00108         Swap( b[irow][l], b[icol][l] ); 
00109     }
00110     indexr[i] = irow;
00111     indexc[i] = icol;
00112 
00113     if( A[icol][icol] == 0.0 )
00114       return false;
00115 
00116     pivotinv = (T)1 / A[icol][icol];
00117     A[icol][icol] = 1.0;
00118     for( l = 0; l <= n; l++ )
00119       A[icol][l] *= pivotinv;
00120     for( l = 0; l <= m; l++ )
00121       b[icol][l] *= pivotinv;
00122       
00123     for( ll = 0; ll <= n; ll++ )
00124     {
00125       if( ll != icol )
00126       {
00127         dummy = A[ll][icol];
00128         A[ll][icol] = 0.0;
00129         for( l = 0; l <= n; l++ )
00130           A[ll][l] -= A[icol][l] * dummy;
00131         for( l = 0; l <= m; l++ )
00132           b[ll][l] -= b[icol][l] * dummy;  
00133       }
00134     }
00135   }
00136   for( l = n; l >= 0; l-- )
00137   {
00138     if( indexr[l] != indexc[l] )
00139     {
00140       for( k = 0; k <= n; k++ )
00141         Swap( A[k][indexr[l]], A[k][indexc[l]] );
00142     }
00143   }
00144   return true;
00145 }

00092 {
00093   uint32 seed;
00094   int fd,n;
00095    
00096   fd = open( "/dev/random", O_RDONLY ); 
00097   if( fd < 0 )
00098   {
00099     cout << "GetSeed: Couldn't open \"/dev/random\"\n";
00100     return (uint32)time(0);
00101   } 
00102   n = read( fd, &seed, sizeof(seed) );
00103   if( n != sizeof(seed) )
00104   {
00105     close(fd);
00106 
00107     cout << "GetSeed: Couldn't read " << sizeof(seed) << "bytes\n";
00108     return (uint32)time(0);
00109   }  
00110 
00111   close(fd);
00112   return seed;
00113 }

00037 {
00038   T x0,x1,x2,x3,f1,f2;
00039   int iteration;
00040     
00041   x0 = ax;
00042   x3 = cx;
00043   
00044   if( rtr<T>::fabs(cx-bx) > rtr<T>::fabs(bx-ax) )
00045   {
00046     x1 = bx;
00047     x2 = bx + rtr<T>::golden_c()*(cx-bx);
00048   }
00049   else
00050   {
00051     x2 = bx;
00052     x1 = bx - rtr<T>::golden_c()*(bx-ax);
00053   }    
00054   f1 = func( x1, fdat );
00055   f2 = func( x2, fdat );
00056 
00057   for( iteration = 0; iteration < max_iterations; iteration++ )
00058   {
00059     if( f2 < f1 )
00060     {
00061       x0 = x1;
00062       x1 = x2;
00063       x2 = rtr<T>::golden_r() * x2 + rtr<T>::golden_c() * x3;
00064       f1 = f2;
00065       f2 = func( x2, fdat );
00066     }
00067     else
00068     {
00069       x3 = x2;
00070       x2 = x1;
00071       x1 = rtr<T>::golden_r() * x2 + rtr<T>::golden_c() * x0;
00072       f2 = f1;
00073       f1 = func( x1, fdat );
00074     }    
00075     if( rtr<T>::fabs(x3-x0) <= tol*(rtr<T>::fabs(x1)+rtr<T>::fabs(x2)) )
00076       break;
00077   }
00078   if( f1 < f2 )
00079   {
00080     *xmin = x1;
00081     *fmin = f1;  
00082   }
00083   else
00084   {
00085     *xmin = x2;
00086     *fmin = f2;
00087   }
00088   if( iteration == max_iterations ) return false;
00089   return true;
00090 }

00148 { _heapsort( nA, A ); }

00147 { _heapsort( nA, A ); }

00040 {
00041   char *ra, *rra;
00042   size_t n = nelem, l, ir, i, j;
00043 
00044   rra = (char *)alloca( elsize );
00045   if( rra == NULL ) return;
00046 
00047   ra = (char *)elptr;
00048 
00049   if( n < 2 ) return;
00050   l = (n >> 1) + 1;
00051   ir = n;
00052   
00053   for(;;)
00054   {
00055     if( l > 1 )
00056     {
00057       memcpy( rra, &ra[(l-2)*elsize], elsize );
00058       l--;    
00059     }
00060     else
00061     {
00062       memcpy( rra, &ra[(ir-1)*elsize], elsize );
00063       memcpy( &ra[(ir-1)*elsize], ra, elsize );
00064       if( --ir == 1 )
00065       {
00066         memcpy( ra, rra, elsize );
00067         break;
00068       }
00069     }
00070     i = l;
00071     j = l+l;
00072 
00073     while( j <= ir )
00074     {
00075       if( (j < ir) &&
00076           (usrfunc( &ra[(j-1)*elsize], &ra[j*elsize], usrdata ) < 0) )
00077         j++;
00078        
00079       if( usrfunc(rra, &ra[(j-1)*elsize], usrdata) < 0 )
00080       {
00081         memcpy( &ra[(i-1)*elsize], &ra[(j-1)*elsize], elsize );
00082         i = j;
00083         j <<= 1;
00084       }
00085       else
00086         j = ir + 1;
00087     }
00088     memcpy( &ra[(i-1)*elsize], rra, elsize );
00089   }
00090   return;
00091 }

00167 {
00168   head->F.b = 1;
00169   head->F.l = 0;
00170  
00171   (*((int *)(&head->left))) = 0;  /* height = 0 */
00172   head->right = NULL;
00173 }

00283 {
00284   BBTNode *Q, *Pk, *Pk_1, *A, *B, *X;
00285   int ak, ak_1;
00286 
00287   Q = element;                    /* neuen Knoten initialisieren */
00288   Q->left = Q->right = NULL;    
00289   Q->F.b = 0;
00290 
00291   Pk = where;
00292   ak = side;
00293 
00294   if( ak == -1 )
00295   {
00296     Pk->left = Q;
00297     if( Pk->left != NULL )
00298     {
00299       Pk->left->parent = Pk;
00300       Pk->left->F.l = -1;
00301     }
00302   }  
00303   else
00304   {
00305     Pk->right = Q;  
00306     if( Pk->right != NULL )
00307     {
00308       Pk->right->parent = Pk;
00309       Pk->right->F.l = 1;
00310     }
00311   }  
00312   
00313   while( (Pk->F.b == 0) && (Pk != head) )  /* Balance Faktoren aktualisieren */
00314   {
00315     Pk->F.b = ak;
00316     ak = Pk->F.l;                 /* k-- */
00317     Pk = Pk->parent;
00318   }
00319 
00320   if( Pk == head )
00321   {
00322     (*((int *)(&head->left)))++;  /* Baumhoehe im Headerknoten erhoehen */
00323     return;                      /*** fertig ***/
00324   }
00325 
00326   if( ak == -1 ) /*** eventuell Rebalancieren, Ausfuehrung fuer (ak == -1) ***/
00327   {
00328     A = Pk;
00329     Pk_1 = Pk->parent;
00330     ak_1 = Pk->F.l;
00331     
00332     if( A->F.b == 1 )             /* (A->B == -ak)   */    
00333     {
00334       A->F.b = 0;
00335       return;                    /*** fertig ***/
00336     }
00337     else                          /* A->B == ak      */
00338     {
00339       B = Pk->left;               /* B = LINK(A,ak)  */
00340 
00341       if( B->F.b == -1 )          /* (B->B == ak) => Single Rotation */
00342       {
00343         A->left = B->right;       /* LINK(A,ak) = LINK(B,-ak) */     
00344         if( A->left != NULL )
00345         {
00346           A->left->parent = A;
00347           A->left->F.l = -1;
00348         }
00349             
00350         B->right = A;             /* LINK(B,-ak) = A  */
00351         if( B->right != NULL )
00352         {
00353           B->right->parent = B;
00354           B->right->F.l = 1;
00355         }
00356             
00357         A->F.b = B->F.b = 0;
00358 
00359         ak

Compounds
struct	guma::bbt_node
class	guma::kdnnrec
class	guma::kdrec
class	guma::kdtnode
class	guma::kdtsearch
class	guma::kdtsnode
class	guma::newton_info
class	guma::random_des
class	guma::rkdtree
class	guma::rkdtree_base
Typedefs
typedef guma::bbt_node	BBTNode
Functions
template<class T> GULAPI bool	GaussJordan (int nRowsCols, int nRightSides, Ptr< Ptr< T > > &A, Ptr< Ptr< T > > &b)
	Solve systems of linear equations with Gauss Jordan Elimination. More...
template GULAPI bool	GaussJordan (int nRowsCols, int m, Ptr< Ptr< float > > &A, Ptr< Ptr< float > > &b)
template GULAPI bool	GaussJordan (int nRowsCols, int m, Ptr< Ptr< double > > &A, Ptr< Ptr< double > > &b)
template<class T> GULAPI bool	LUDecomposition (int nRowsCols, Ptr< Ptr< T > > &A, int *perm_sign, Ptr< int > &index)
	Decompose a matrix into lower and upper triangular matrix. More...
template GULAPI bool	LUDecomposition (int nRowsCols, Ptr< Ptr< float > > &A, int *perm_sign, Ptr< int > &index)
template GULAPI bool	LUDecomposition (int nRowsCols, Ptr< Ptr< double > > &A, int *perm_sign, Ptr< int > &index)
template<class T> GULAPI void	LUBackSubstitution (int nRowsCols, Ptr< int > &index, Ptr< Ptr< T > > &A, Ptr< T > &b)
	Solve system of linear equations with help of LU-Decomposition (given in A). More...
template GULAPI void	LUBackSubstitution (int nRowsCols, Ptr< int > &index, Ptr< Ptr< float > > &A, Ptr< float > &b)
template GULAPI void	LUBackSubstitution (int nRowsCols, Ptr< int > &index, Ptr< Ptr< double > > &A, Ptr< double > &b)
template<class T> GULAPI void	BandMVProduct (int n, int m1, int m2, Ptr< Ptr< T > > a, Ptr< T > x, Ptr< T > b)
	Multiply a band matrix and a vector: b = Ax, m1 = number of subdiagonal elements, m2 = number of superdiagonal elements, n = number of rows.* More...
template GULAPI void	BandMVProduct (int n, int m1, int m2, Ptr< Ptr< float > > a, Ptr< float > x, Ptr< float > b)
template GULAPI void	BandMVProduct (int n, int m1, int m2, Ptr< Ptr< double > > a, Ptr< double > x, Ptr< double > b)
template<class T> GULAPI void	BandDecomposition (int n, int m1, int m2, Ptr< Ptr< T > > &A, Ptr< Ptr< T > > &L, int *perm_sign, Ptr< int > &index)
	Decompose a band matrix into lower and upper triangular matrix: A = LU.* More...
template GULAPI void	BandDecomposition (int n, int m1, int m2, Ptr< Ptr< float > > &A, Ptr< Ptr< float > > &L, int *perm_sign, Ptr< int > &index)
template GULAPI void	BandDecomposition (int n, int m1, int m2, Ptr< Ptr< double > > &A, Ptr< Ptr< double > > &L, int *perm_sign, Ptr< int > &index)
template<class T> GULAPI void	BandBackSubstitution (int n, int m1, int m2, const Ptr< Ptr< T > > &A, const Ptr< Ptr< T > > &L, const Ptr< int > &index, Ptr< T > &b)
	Solve system of linear equations with help of LU-Decomposition of a band matrix (given by L and A). More...
template GULAPI void	BandBackSubstitution (int n, int m1, int m2, const Ptr< Ptr< float > > &A, const Ptr< Ptr< float > > &L, const Ptr< int > &index, Ptr< float > &b)
template GULAPI void	BandBackSubstitution (int n, int m1, int m2, const Ptr< Ptr< double > > &A, const Ptr< Ptr< double > > &L, const Ptr< int > &index, Ptr< double > &b)
template<class T> GULAPI void	SVDecomposition (int m, int n, Ptr< Ptr< T > > &a, Ptr< T > &w, Ptr< Ptr< T > > &v)
	Singular Value Decomposition. More...
template GULAPI void	SVDecomposition (int m, int n, Ptr< Ptr< float > > &a, Ptr< float > &w, Ptr< Ptr< float > > &v)
template GULAPI void	SVDecomposition (int m, int n, Ptr< Ptr< double > > &a, Ptr< double > &w, Ptr< Ptr< double > > &v)
template<class T> GULAPI void	SVBackSubstitution (int m, int n, Ptr< Ptr< T > > &u, Ptr< T > &w, Ptr< Ptr< T > > &v, Ptr< T > &b, Ptr< T > &x)
	Solve system of linear equations, when a Singular Value Decomposition is given. More...
template GULAPI void	SVBackSubstitution (int m, int n, Ptr< Ptr< float > > &u, Ptr< float > &w, Ptr< Ptr< float > > &v, Ptr< float > &b, Ptr< float > &x)
template GULAPI void	SVBackSubstitution (int m, int n, Ptr< Ptr< double > > &u, Ptr< double > &w, Ptr< Ptr< double > > &v, Ptr< double > &b, Ptr< double > &x)
template<class T> GULAPI void	SVBackSubstitution (int m, int n, Ptr< Ptr< T > > &u, Ptr< T > &w, Ptr< Ptr< T > > &v, Ptr< T > &b)
	Solve system of linear equations, when a Singular Value Decomposition is given. More...
template GULAPI void	SVBackSubstitution (int m, int n, Ptr< Ptr< float > > &u, Ptr< float > &w, Ptr< Ptr< float > > &v, Ptr< float > &b)
template GULAPI void	SVBackSubstitution (int m, int n, Ptr< Ptr< double > > &u, Ptr< double > &w, Ptr< Ptr< double > > &v, Ptr< double > &b)
template<class T> GULAPI bool	SVZero (int n, Ptr< T > &w)
	Sets very small singular values to zero. More...
template GULAPI bool	SVZero (int n, Ptr< float > &w)
template GULAPI bool	SVZero (int n, Ptr< double > &w)
template<class T> int	SVDIntersectLines (point< T > P1, point< T > T1, point< T > P2, point< T > T2, T alpha1, T alpha2, point< T > *P)
	Intersect two lines in 3-dimensions, using singular decomposition. More...
template int	SVDIntersectLines (point< float > P1, point< float > T1, point< float > P2, point< float > T2, float alpha1, float alpha2, point< float > *P)
template int	SVDIntersectLines (point< double > P1, point< double > T1, point< double > P2, point< double > T2, double alpha1, double alpha2, point< double > *P)
template<class T> T	Pythagoras (const T &a, const T &b)
	Calculate (a^2 + b^2)^{1/2}, with precautions to avoid destructive over- or underflow. More...
template<class T> bool	GoldenSectionSearch (T ax, T bx, T cx, T(func)(T, void ), void fdat, T tol, int max_iterations, T xmin, T *fmin)
	Searches the minimum of a function, defined over an intervall. More...
template bool	GoldenSectionSearch (float ax, float bx, float cx, float(func)(float, void ), void , float tol, int max_iterations, float xmin, float *fmin)
template bool	GoldenSectionSearch (double ax, double bx, double cx, double(func)(double, void ), void , double tol, int max_iterations, double xmin, double *fmin)
template<class T> bool	LinearSearch (const Ptr< T > &p, const Ptr< T > &xold, T fold, const Ptr< T > &g, const Ptr< T > &x1, const Ptr< T > &x2, newton_info< T > &I, bool &found, bool &check, Ptr< T > &x, T *fx)
template bool	LinearSearch (const Ptr< float > &p, const Ptr< float > &xold, float fold, const Ptr< float > &g, const Ptr< float > &x1, const Ptr< float > &x2, newton_info< float > &I, bool &found, bool &check, Ptr< float > &x, float *fx)
template<class T> bool	Newton (Ptr< T > &x, const Ptr< T > &x1, const Ptr< T > &x2, newton_info< T > &I, int maxits)
template bool	Newton (Ptr< float > &x, const Ptr< float > &x1, const Ptr< float > &x2, newton_info< float > &I, int maxits)
template bool	Newton (Ptr< double > &x, const Ptr< double > &x1, const Ptr< double > &x2, newton_info< double > &I, int maxits)
GULAPI uint32	GetSeed ()
GULAPI void	PseudoDes (uint32 lword, uint32 irword)
GULAPI void	HeapSort (size_t nelem, size_t elsize, void elptr, int(usrfunc)(void , void , void ), void usrdata)
GULAPI void	PtrHeapSort (size_t nelem, void *elptr, int(usrfunc)(void , void , void ), void usrdata)
GULAPI void	heapsort (int nA, Ptr< void *> &A)
GULAPI void	heapsort (int nA, Ptr< int > &A)
GULAPI int	BinarySearch (int x, int nA, const gul::Ptr< int > &A)
GULAPI int	BinarySearch (void x, int nA, const gul::Ptr< void > &A)
GULAPI void	InitBBT (BBTNode *head)
GULAPI int	SearchElementInBBT (BBTNode head, void key, int compare(void , void ), BBTNode **element)
GULAPI BBTNode *	SearchSuccessorInBBT (BBTNode element, BBTNode head)
GULAPI BBTNode *	SearchPredecessorInBBT (BBTNode element, BBTNode head)
GULAPI void	InsertElementIntoBBT (BBTNode element, BBTNode where, int side, BBTNode *head)
GULAPI void	DeleteElementFromBBT (BBTNode element, BBTNode head)
GULAPI void	DumpBBTTree (BBTNode node, int level, void dumpkey_func(void ))
GULAPI void	DumpBBTNode (BBTNode *node, int level)
template<class T> void	_heapsort (int nA, gul::Ptr< T > &A)
template<class T> int	_BinarySearch (T x, int nA, const gul::Ptr< T > &A)
template<class T> int	_BinarySearch (T x, int nA, const gul::Ptr< T > &A, int rleft, int rright)
template<class U> void	CommonCoordinateSystem (const point< U > &B, const point< U > &P, const point< U > &Ab, const point< U > &Pb, Ptr< Ptr< U > > &T)
template void	CommonCoordinateSystem (const point< float > &B, const point< float > &P, const point< float > &Ab, const point< float > &Pb, Ptr< Ptr< float > > &T)
template void	CommonCoordinateSystem (const point< double > &B, const point< double > &P, const point< double > &Ab, const point< double > &Pb, Ptr< Ptr< double > > &T)
template<class U> void	CommonCoordinateSystem (const gul::point< U > &B, const gul::point< U > &P, const gul::point< U > &Ab, const gul::point< U > &Pb, gul::Ptr< gul::Ptr< U > > &T)

guma Namespace Reference

Compounds

Typedefs

Functions

Typedef Documentation

Function Documentation