Dan wrote:
> On Jul 12, 2008, at 2:42 AM, Steve Friedman wrote:
>
>>
>> Filip Navara wrote:
>>> how about actually attaching the patch? :)
>>>
>>> - Filip
>>>
>>> On Fri, Jul 11, 2008 at 9:23 PM, Steve Friedman
>>> <[EMAIL PROTECTED]> wrote:
>>>> I've just started using the rtree extension, and have found that
>>>> the 32-bit
>>>> float for the range keys is not appropriate for me. Please find
>>>> attached a
>>>> patch for rtree.c (based on v1.5) that allows for int -OR-
>>>> unsigned int -OR-
>>>> float operation.
>
> What kind of advantages does using int over float have here?
>
> With a little work it might be possible to select int or float at
> runtime. Do other people who know about such things think that this
> would be a good option to have?
Dan,
I think the need for integer support is to avoid floating point rounding
errors that might cause you to miss a key otherwise.
I think this would be a nice feature to have. I think it should be
implemented at runtime because if I ever have an application that need
both say time (int) and spatial rtrees (floats) then it puts me into a
problem of not being able to support both in a single build.
-Steve
>>>> Steve Friedman
>> Not sure where it got deleted (since my inbox shows the attachment).
>> Included inline...
>>
>> --- rtree.c 2008-07-11 15:04:42.000000000 -0400
>> +++ rtreemod.c 2008-07-11 15:04:31.000000000 -0400
>> @@ -149,13 +149,36 @@
>> RtreeConstraint *aConstraint; /* Search constraints. */
>> };
>>
>> +#if defined( SQLITE_RTREE_TYPE_INT)
>> +typedef int ConstraintType;
>> +# define sqlite3_result_ConstraintType sqlite3_result_int
>> +# define sqlite3_value_ConstraintType(x) ((int) sqlite3_value_int
>> ((x)))
>> +# define sqlite3_snprintf_ConstraintType( a, b, c) \
>> + sqlite3_snprintf( (a), (b), " %d", (c))
>> +
>> +#elif defined(SQLITE_RTREE_TYPE_UINT)
>> +typedef u32 ConstraintType;
>> +# define sqlite3_result_ConstraintType sqlite3_result_int64
>> +# define sqlite3_value_ConstraintType(x) ((u32)
>> sqlite3_value_int64((x)))
>> +# define sqlite3_snprintf_ConstraintType( a, b, c) \
>> + sqlite3_snprintf( (a), (b), " %u", (c))
>> +
>> +#else
>> +typedef float ConstraintType;
>> +# define sqlite3_result_ConstraintType sqlite3_result_double
>> +# define sqlite3_value_ConstraintType(x) ((float)
>> sqlite3_value_double((x)))
>> +# define sqlite3_snprintf_ConstraintType( a, b, c) \
>> + sqlite3_snprintf( (a), (b), " %f", (double) (c))
>> +#endif
>> +
>> +
>> /*
>> ** A search constraint.
>> */
>> struct RtreeConstraint {
>> int iCoord; /* Index of constrained
>> coordinate */
>> int op; /* Constraining operation */
>> - float rValue; /* Constraint value. */
>> + ConstraintType rValue; /* Constraint value. */
>> };
>>
>> /* Possible values for RtreeConstraint.op */
>> @@ -198,7 +221,7 @@
>> */
>> struct RtreeCell {
>> i64 iRowid;
>> - float aCoord[RTREE_MAX_DIMENSIONS*2];
>> + ConstraintType aCoord[RTREE_MAX_DIMENSIONS*2];
>> };
>>
>> #define MAX(x,y) ((x) < (y) ? (y) : (x))
>> @@ -211,14 +234,14 @@
>> static int readInt16(u8 *p){
>> return (p[0]<<8) + p[1];
>> }
>> -static float readReal32(u8 *p){
>> +static ConstraintType readReal32(u8 *p){
>> u32 i = (
>> (((u32)p[0]) << 24) +
>> (((u32)p[1]) << 16) +
>> (((u32)p[2]) << 8) +
>> (((u32)p[3]) << 0)
>> );
>> - return *(float *)&i;
>> + return *(ConstraintType *)&i;
>> }
>> static i64 readInt64(u8 *p){
>> return (
>> @@ -243,9 +266,9 @@
>> p[1] = (i>> 0)&0xFF;
>> return 2;
>> }
>> -static int writeReal32(u8 *p, float f){
>> +static int writeReal32(u8 *p, ConstraintType f){
>> u32 i;
>> - assert( sizeof(float)==4 );
>> + assert( sizeof(ConstraintType)==4 );
>> assert( sizeof(u32)==4 );
>> i = *(u32 *)&f;
>> p[0] = (i>>24)&0xFF;
>> @@ -543,7 +566,7 @@
>> /*
>> ** Return coordinate iCoord from cell iCell in node pNode.
>> */
>> -static float nodeGetCoord(
>> +static ConstraintType nodeGetCoord(
>> Rtree *pRtree,
>> RtreeNode *pNode,
>> int iCell,
>> @@ -721,8 +744,8 @@
>> for(ii=0; ii<pCursor->nConstraint; ii++){
>> RtreeConstraint *p = &pCursor->aConstraint[ii];
>>
>> - float cell_min = cell.aCoord[(p->iCoord>>1)*2];
>> - float cell_max = cell.aCoord[(p->iCoord>>1)*2+1];
>> + ConstraintType cell_min = cell.aCoord[(p->iCoord>>1)*2];
>> + ConstraintType cell_max = cell.aCoord[(p->iCoord>>1)*2+1];
>> assert( cell_min<=cell_max );
>>
>> switch( p->op ){
>> @@ -769,7 +792,7 @@
>> nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
>> for(ii=0; ii<pCursor->nConstraint; ii++){
>> RtreeConstraint *p = &pCursor->aConstraint[ii];
>> - float cell_val = cell.aCoord[p->iCoord];
>> + ConstraintType cell_val = cell.aCoord[p->iCoord];
>> int res;
>> switch( p->op ){
>> case RTREE_LE: res = (cell_val<=p->rValue); break;
>> @@ -935,8 +958,8 @@
>> i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
>> sqlite3_result_int64(ctx, iRowid);
>> }else{
>> - float fCoord = nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell,
>> i-1);
>> - sqlite3_result_double(ctx, fCoord);
>> + ConstraintType fCoord = nodeGetCoord(pRtree, pCsr->pNode,
>> pCsr->iCell, i-1);
>> + sqlite3_result_ConstraintType(ctx, fCoord);
>> }
>>
>> return SQLITE_OK;
>> @@ -1009,7 +1032,7 @@
>> RtreeConstraint *p = &pCsr->aConstraint[ii];
>> p->op = idxStr[ii*2];
>> p->iCoord = idxStr[ii*2+1]-'a';
>> - p->rValue = sqlite3_value_double(argv[ii]);
>> + p->rValue = sqlite3_value_ConstraintType(argv[ii]);
>> }
>> }
>> }
>> @@ -1157,8 +1180,8 @@
>> /*
>> ** Return the N-dimensional volumn of the cell stored in *p.
>> */
>> -static float cellArea(Rtree *pRtree, RtreeCell *p){
>> - float area = 1.0;
>> +static ConstraintType cellArea(Rtree *pRtree, RtreeCell *p){
>> + ConstraintType area = 1.0;
>> int ii;
>> for(ii=0; ii<(pRtree->nDim*2); ii+=2){
>> area = area * (p->aCoord[ii+1] - p->aCoord[ii]);
>> @@ -1170,8 +1193,8 @@
>> ** Return the margin length of cell p. The margin length is the sum
>> ** of the objects size in each dimension.
>> */
>> -static float cellMargin(Rtree *pRtree, RtreeCell *p){
>> - float margin = 0.0;
>> +static ConstraintType cellMargin(Rtree *pRtree, RtreeCell *p){
>> + ConstraintType margin = 0.0;
>> int ii;
>> for(ii=0; ii<(pRtree->nDim*2); ii+=2){
>> margin += (p->aCoord[ii+1] - p->aCoord[ii]);
>> @@ -1193,8 +1216,8 @@
>> /*
>> ** Return the amount cell p would grow by if it were unioned with
>> pCell.
>> */
>> -static float cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell
>> *pCell){
>> - float area;
>> +static ConstraintType cellGrowth(Rtree *pRtree, RtreeCell *p,
>> RtreeCell
>> *pCell){
>> + ConstraintType area;
>> RtreeCell cell;
>> memcpy(&cell, p, sizeof(RtreeCell));
>> area = cellArea(pRtree, &cell);
>> @@ -1203,7 +1226,7 @@
>> }
>>
>> #if VARIANT_RSTARTREE_CHOOSESUBTREE || VARIANT_RSTARTREE_SPLIT
>> -static float cellOverlap(
>> +static ConstraintType cellOverlap(
>> Rtree *pRtree,
>> RtreeCell *p,
>> RtreeCell *aCell,
>> @@ -1211,15 +1234,15 @@
>> int iExclude
>> ){
>> int ii;
>> - float overlap = 0.0;
>> + ConstraintType overlap = 0.0;
>> for(ii=0; ii<nCell; ii++){
>> if( ii!=iExclude ){
>> int jj;
>> - float o = 1.0;
>> + ConstraintType o = 1.0;
>> for(jj=0; jj<(pRtree->nDim*2); jj+=2){
>>
>> - float x1 = MAX(p->aCoord[jj], aCell[ii].aCoord[jj]);
>> - float x2 = MIN(p->aCoord[jj+1], aCell[ii].aCoord[jj+1]);
>> + ConstraintType x1 = MAX(p->aCoord[jj], aCell[ii].aCoord[jj]);
>> + ConstraintType x2 = MIN(p->aCoord[jj+1], aCell[ii].aCoord
>> [jj+1]);
>>
>> if( x2<x1 ){
>> o = 0.0;
>> @@ -1236,7 +1259,7 @@
>> #endif
>>
>> #if VARIANT_RSTARTREE_CHOOSESUBTREE
>> -static float cellOverlapEnlargement(
>> +static ConstraintType cellOverlapEnlargement(
>> Rtree *pRtree,
>> RtreeCell *p,
>> RtreeCell *pInsert,
>> @@ -1244,8 +1267,8 @@
>> int nCell,
>> int iExclude
>> ){
>> - float before;
>> - float after;
>> + ConstraintType before;
>> + ConstraintType after;
>> before = cellOverlap(pRtree, p, aCell, nCell, iExclude);
>> cellUnion(pRtree, p, pInsert);
>> after = cellOverlap(pRtree, p, aCell, nCell, iExclude);
>> @@ -1273,9 +1296,9 @@
>> int iCell;
>> sqlite3_int64 iBest;
>>
>> - float fMinGrowth;
>> - float fMinArea;
>> - float fMinOverlap;
>> + ConstraintType fMinGrowth;
>> + ConstraintType fMinArea;
>> + ConstraintType fMinOverlap;
>>
>> int nCell = NCELL(pNode);
>> RtreeCell cell;
>> @@ -1304,9 +1327,9 @@
>> ** the smallest area.
>> */
>> for(iCell=0; iCell<nCell; iCell++){
>> - float growth;
>> - float area;
>> - float overlap = 0.0;
>> + ConstraintType growth;
>> + ConstraintType area;
>> + ConstraintType overlap = 0.0;
>> nodeGetCell(pRtree, pNode, iCell, &cell);
>> growth = cellGrowth(pRtree, &cell, pCell);
>> area = cellArea(pRtree, &cell);
>> @@ -1418,7 +1441,7 @@
>> int i;
>> int iLeftSeed = 0;
>> int iRightSeed = 1;
>> - float maxNormalInnerWidth = 0.0;
>> + ConstraintType maxNormalInnerWidth = 0.0;
>>
>> /* Pick two "seed" cells from the array of cells. The algorithm
>> used
>> ** here is the LinearPickSeeds algorithm from Gutman[1984]. The
>> @@ -1426,18 +1449,18 @@
>> ** variables iLeftSeek and iRightSeed.
>> */
>> for(i=0; i<pRtree->nDim; i++){
>> - float x1 = aCell[0].aCoord[i*2];
>> - float x2 = aCell[0].aCoord[i*2+1];
>> - float x3 = x1;
>> - float x4 = x2;
>> + ConstraintType x1 = aCell[0].aCoord[i*2];
>> + ConstraintType x2 = aCell[0].aCoord[i*2+1];
>> + ConstraintType x3 = x1;
>> + ConstraintType x4 = x2;
>> int jj;
>>
>> int iCellLeft = 0;
>> int iCellRight = 0;
>>
>> for(jj=1; jj<nCell; jj++){
>> - float left = aCell[jj].aCoord[i*2];
>> - float right = aCell[jj].aCoord[i*2+1];
>> + ConstraintType left = aCell[jj].aCoord[i*2];
>> + ConstraintType right = aCell[jj].aCoord[i*2+1];
>>
>> if( left<x1 ) x1 = left;
>> if( right>x4 ) x4 = right;
>> @@ -1452,7 +1475,7 @@
>> }
>>
>> if( x4!=x1 ){
>> - float normalwidth = (x3 - x2) / (x4 - x1);
>> + ConstraintType normalwidth = (x3 - x2) / (x4 - x1);
>> if( normalwidth>maxNormalInnerWidth ){
>> iLeftSeed = iCellLeft;
>> iRightSeed = iCellRight;
>> @@ -1481,13 +1504,13 @@
>> #define FABS(a) ((a)<0.0?-1.0*(a):(a))
>>
>> int iSelect = -1;
>> - float fDiff;
>> + ConstraintType fDiff;
>> int ii;
>> for(ii=0; ii<nCell; ii++){
>> if( aiUsed[ii]==0 ){
>> - float left = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
>> - float right = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
>> - float diff = FABS(right-left);
>> + ConstraintType left = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
>> + ConstraintType right = cellGrowth(pRtree, pLeftBox, &aCell
>> [ii]);
>> + ConstraintType diff = FABS(right-left);
>> if( iSelect<0 || diff>fDiff ){
>> fDiff = diff;
>> iSelect = ii;
>> @@ -1514,13 +1537,13 @@
>>
>> int iLeftSeed = 0;
>> int iRightSeed = 1;
>> - float fWaste = 0.0;
>> + ConstraintType fWaste = 0.0;
>>
>> for(ii=0; ii<nCell; ii++){
>> for(jj=ii+1; jj<nCell; jj++){
>> - float right = cellArea(pRtree, &aCell[jj]);
>> - float growth = cellGrowth(pRtree, &aCell[ii], &aCell[jj]);
>> - float waste = growth - right;
>> + ConstraintType right = cellArea(pRtree, &aCell[jj]);
>> + ConstraintType growth = cellGrowth(pRtree, &aCell[ii], &aCell
>> [jj]);
>> + ConstraintType waste = growth - right;
>>
>> if( waste>fWaste ){
>> iLeftSeed = ii;
>> @@ -1555,7 +1578,7 @@
>> static void SortByDistance(
>> int *aIdx,
>> int nIdx,
>> - float *aDistance,
>> + ConstraintType *aDistance,
>> int *aSpare
>> ){
>> if( nIdx>1 ){
>> @@ -1581,8 +1604,8 @@
>> aIdx[iLeft+iRight] = aLeft[iLeft];
>> iLeft++;
>> }else{
>> - float fLeft = aDistance[aLeft[iLeft]];
>> - float fRight = aDistance[aRight[iRight]];
>> + ConstraintType fLeft = aDistance[aLeft[iLeft]];
>> + ConstraintType fRight = aDistance[aRight[iRight]];
>> if( fLeft<fRight ){
>> aIdx[iLeft+iRight] = aLeft[iLeft];
>> iLeft++;
>> @@ -1598,8 +1621,8 @@
>> {
>> int jj;
>> for(jj=1; jj<nIdx; jj++){
>> - float left = aDistance[aIdx[jj-1]];
>> - float right = aDistance[aIdx[jj]];
>> + ConstraintType left = aDistance[aIdx[jj-1]];
>> + ConstraintType right = aDistance[aIdx[jj]];
>> assert( left<=right );
>> }
>> }
>> @@ -1641,10 +1664,10 @@
>> memcpy(aSpare, aLeft, sizeof(int)*nLeft);
>> aLeft = aSpare;
>> while( iLeft<nLeft || iRight<nRight ){
>> - float xleft1 = aCell[aLeft[iLeft]].aCoord[iDim*2];
>> - float xleft2 = aCell[aLeft[iLeft]].aCoord[iDim*2+1];
>> - float xright1 = aCell[aRight[iRight]].aCoord[iDim*2];
>> - float xright2 = aCell[aRight[iRight]].aCoord[iDim*2+1];
>> + ConstraintType xleft1 = aCell[aLeft[iLeft]].aCoord[iDim*2];
>> + ConstraintType xleft2 = aCell[aLeft[iLeft]].aCoord[iDim*2+1];
>> + ConstraintType xright1 = aCell[aRight[iRight]].aCoord[iDim*2];
>> + ConstraintType xright2 = aCell[aRight[iRight]].aCoord[iDim*2
>> +1];
>>
>> if( (iLeft!=nLeft) && ((iRight==nRight)
>> || (xleft1<xright1)
>> @@ -1663,10 +1686,10 @@
>> {
>> int jj;
>> for(jj=1; jj<nIdx; jj++){
>> - float xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2];
>> - float xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1];
>> - float xright1 = aCell[aIdx[jj]].aCoord[iDim*2];
>> - float xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1];
>> + ConstraintType xleft1 = aCell[aIdx[jj-1]].aCoord[iDim*2];
>> + ConstraintType xleft2 = aCell[aIdx[jj-1]].aCoord[iDim*2+1];
>> + ConstraintType xright1 = aCell[aIdx[jj]].aCoord[iDim*2];
>> + ConstraintType xright2 = aCell[aIdx[jj]].aCoord[iDim*2+1];
>> assert( xleft1<=xright1 && (xleft1<xright1 ||
>> xleft2<=xright2) );
>> }
>> }
>> @@ -1693,7 +1716,7 @@
>>
>> int iBestDim;
>> int iBestSplit;
>> - float fBestMargin;
>> + ConstraintType fBestMargin;
>>
>> int nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int));
>>
>> @@ -1714,9 +1737,9 @@
>> }
>>
>> for(ii=0; ii<pRtree->nDim; ii++){
>> - float margin = 0.0;
>> - float fBestOverlap;
>> - float fBestArea;
>> + ConstraintType margin = 0.0;
>> + ConstraintType fBestOverlap;
>> + ConstraintType fBestArea;
>> int iBestLeft;
>> int nLeft;
>>
>> @@ -1728,8 +1751,8 @@
>> RtreeCell left;
>> RtreeCell right;
>> int kk;
>> - float overlap;
>> - float area;
>> + ConstraintType overlap;
>> + ConstraintType area;
>>
>> memcpy(&left, &aCell[aaSorted[ii][0]], sizeof(RtreeCell));
>> memcpy(&right, &aCell[aaSorted[ii][nCell-1]], sizeof
>> (RtreeCell));
>> @@ -1809,7 +1832,7 @@
>> for(i=nCell-2; i>0; i--){
>> RtreeCell *pNext;
>> pNext = PickNext(pRtree, aCell, nCell, pBboxLeft, pBboxRight,
>> aiUsed);
>> - float diff =
>> + ConstraintType diff =
>> cellGrowth(pRtree, pBboxLeft, pNext) -
>> cellGrowth(pRtree, pBboxRight, pNext)
>> ;
>> @@ -2099,14 +2122,14 @@
>> int *aOrder;
>> int *aSpare;
>> RtreeCell *aCell;
>> - float *aDistance;
>> + ConstraintType *aDistance;
>> int nCell;
>> - float aCenterCoord[RTREE_MAX_DIMENSIONS];
>> + ConstraintType aCenterCoord[RTREE_MAX_DIMENSIONS];
>> int iDim;
>> int ii;
>> int rc = SQLITE_OK;
>>
>> - memset(aCenterCoord, 0, sizeof(float)*RTREE_MAX_DIMENSIONS);
>> + memset(aCenterCoord, 0, sizeof(ConstraintType)
>> *RTREE_MAX_DIMENSIONS);
>>
>> nCell = NCELL(pNode)+1;
>>
>> @@ -2117,14 +2140,14 @@
>> sizeof(RtreeCell) + /* aCell array */
>> sizeof(int) + /* aOrder array */
>> sizeof(int) + /* aSpare array */
>> - sizeof(float) /* aDistance array */
>> + sizeof(ConstraintType) /* aDistance array */
>> ));
>> if( !aCell ){
>> return SQLITE_NOMEM;
>> }
>> aOrder = (int *)&aCell[nCell];
>> aSpare = (int *)&aOrder[nCell];
>> - aDistance = (float *)&aSpare[nCell];
>> + aDistance = (ConstraintType *)&aSpare[nCell];
>>
>> for(ii=0; ii<nCell; ii++){
>> if( ii==(nCell-1) ){
>> @@ -2139,13 +2162,13 @@
>> }
>> }
>> for(iDim=0; iDim<pRtree->nDim; iDim++){
>> - aCenterCoord[iDim] = aCenterCoord[iDim]/((float)nCell*2.0);
>> + aCenterCoord[iDim] = aCenterCoord[iDim]/((ConstraintType)
>> nCell*2.0);
>> }
>>
>> for(ii=0; ii<nCell; ii++){
>> aDistance[ii] = 0.0;
>> for(iDim=0; iDim<pRtree->nDim; iDim++){
>> - float coord = aCell[ii].aCoord[iDim*2+1] - aCell[ii].aCoord
>> [iDim*2];
>> + ConstraintType coord = aCell[ii].aCoord[iDim*2+1] -
>> aCell[ii].aCoord[iDim*2];
>> aDistance[ii] +=
>> (coord-aCenterCoord[iDim])*(coord-aCenterCoord[iDim]);
>> }
>> }
>> @@ -2388,8 +2411,8 @@
>> /* Populate the cell.aCoord[] array. The first coordinate is
>> azData[3]. */
>> assert( nData==(pRtree->nDim*2 + 3) );
>> for(ii=0; ii<(pRtree->nDim*2); ii+=2){
>> - cell.aCoord[ii] = (float)sqlite3_value_double(azData[ii+3]);
>> - cell.aCoord[ii+1] = (float)sqlite3_value_double(azData[ii+4]);
>> + cell.aCoord[ii] = sqlite3_value_ConstraintType(azData[ii+3]);
>> + cell.aCoord[ii+1] = sqlite3_value_ConstraintType(azData[ii+4]);
>> if( cell.aCoord[ii]>cell.aCoord[ii+1] ){
>> rc = SQLITE_CONSTRAINT;
>> goto constraint;
>> @@ -2716,7 +2739,7 @@
>> sqlite3_snprintf(512-nCell,&zCell[nCell],"%d", cell.iRowid);
>> nCell = strlen(zCell);
>> for(jj=0; jj<tree.nDim*2; jj++){
>> - sqlite3_snprintf(512-nCell,&zCell[nCell],"
>> %f",(double)cell.aCoord[jj]);
>> + sqlite3_snprintf_ConstraintType(512-nCell,&zCell[nCell],
>> cell.aCoord[jj]);
>> nCell = strlen(zCell);
>> }
>>
>>
>>
>> _______________________________________________
>> sqlite-users mailing list
>> [email protected]
>> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>
> _______________________________________________
> sqlite-users mailing list
> [email protected]
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[email protected]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
