[GRASS-dev] bug in Vect_cidx_find_next() ?

GRASS GIS GRASS GIS developer
1

Hello,

Trying to rework d.vect.chart I am using the Vect_cidx_find_next() function.

However, using a map with areas I get behaviour which seems incorrect and which I cannot explain.

I have the following category index (result of Vect_cidx_dump(Map, stdout)):

.
[Field 0]
.
Field 1 number of unique cats: 589 number of cats: 1185 number of types: 3
------------------------------------------------------------------------------------------
             type | count
                8 | 592
                4 | 1
               64 | 592
  category | type | line/area
     11001 | 8 | 1895
     11001 | 64 | 127
     11002 | 8 | 1810
     11002 | 64 | 42
     11004 | 8 | 1874
     11004 | 64 | 106
     11005 | 8 | 1923
     11005 | 64 | 155
     11007 | 8 | 1866

etc.

Now, when I launch

Vect_cidx_find_next( Map, field_index=1, cat=11002, type=15, start_index=3, &stype, &sid )

it returns 4 and line id=1874.

This is wrong as the fourth item in the index, which does have line id 1874, has cat 11004 and not cat 11002. This is confirmed by launching

Vect_cidx_get_cat_by_index ( Map, field_index, 4, &testcat, &testtype, &testid)

which returns testcat = 11004.

Am I right in assuming that there is a bug in Vect_cidx_find_next, or am I misunderstanding something here ?

I don't have this problem with a pure point file, which only has one type:

Field 1 number of unique cats: 589 number of cats: 593 number of types: 1
------------------------------------------------------------------------------------------
             type | count
                1 | 593
  category | type | line/area
     11001 | 1 | 97
     11002 | 1 | 12
     11002 | 1 | 593
     11004 | 1 | 76
     11005 | 1 | 125
     11007 | 1 | 68

So this seems to be linked to the type handling.

Any ideas,

Moritz

2

Yes,
it seems to be bug, I think that on row 296 in cindex.c
the requested cat should also be checked, not only the type.
But I am tired now, please check it twice.
Bravo Moritz!

Radim

On 9/28/06, Moritz Lennert <mlennert@club.worldonline.be> wrote:

Hello,

Trying to rework d.vect.chart I am using the Vect_cidx_find_next() function.

However, using a map with areas I get behaviour which seems incorrect
and which I cannot explain.

I have the following category index (result of Vect_cidx_dump(Map, stdout)):

.
[Field 0]
.
Field 1 number of unique cats: 589 number of cats: 1185
number of types: 3
------------------------------------------------------------------------------------------
             type | count
                8 | 592
                4 | 1
               64 | 592
  category | type | line/area
     11001 | 8 | 1895
     11001 | 64 | 127
     11002 | 8 | 1810
     11002 | 64 | 42
     11004 | 8 | 1874
     11004 | 64 | 106
     11005 | 8 | 1923
     11005 | 64 | 155
     11007 | 8 | 1866

etc.

Now, when I launch

Vect_cidx_find_next( Map, field_index=1, cat=11002, type=15,
start_index=3, &stype, &sid )

it returns 4 and line id=1874.

This is wrong as the fourth item in the index, which does have line id
1874, has cat 11004 and not cat 11002. This is confirmed by launching

Vect_cidx_get_cat_by_index ( Map, field_index, 4, &testcat, &testtype,
&testid)

which returns testcat = 11004.

Am I right in assuming that there is a bug in Vect_cidx_find_next, or am
I misunderstanding something here ?

I don't have this problem with a pure point file, which only has one type:

Field 1 number of unique cats: 589 number of cats: 593
number of types: 1
------------------------------------------------------------------------------------------
             type | count
                1 | 593
  category | type | line/area
     11001 | 1 | 97
     11002 | 1 | 12
     11002 | 1 | 593
     11004 | 1 | 76
     11005 | 1 | 125
     11007 | 1 | 68

So this seems to be linked to the type handling.

Any ideas,

Moritz

3

Radim Blazek wrote:

Yes,
it seems to be bug, I think that on row 296 in cindex.c
the requested cat should also be checked, not only the type.
But I am tired now, please check it twice.

Changing that line into

if ( ci->cat[cat_index][0] == cat && ci->cat[cat_index][1] & type_mask )

works. Thanks !

But I don't really understand how this could happen, as I thought the following lines (286-288) should take care of this before:

while ( cat_index > start_index ) {
     if ( ci->cat[cat_index-1][0] != cat ) {
        break;

So it might actually be a problem in the determination of cat_index which is higher than it should be.

But just as you, I'm too tired now to look any deeper into this...
:wink:

Moritz

Bravo Moritz!

Radim

On 9/28/06, Moritz Lennert <mlennert@club.worldonline.be> wrote:

Hello,

Trying to rework d.vect.chart I am using the Vect_cidx_find_next() function.

However, using a map with areas I get behaviour which seems incorrect
and which I cannot explain.

I have the following category index (result of Vect_cidx_dump(Map, stdout)):

.
[Field 0]
.
Field 1 number of unique cats: 589 number of cats: 1185
number of types: 3
------------------------------------------------------------------------------------------

             type | count
                8 | 592
                4 | 1
               64 | 592
  category | type | line/area
     11001 | 8 | 1895
     11001 | 64 | 127
     11002 | 8 | 1810
     11002 | 64 | 42
     11004 | 8 | 1874
     11004 | 64 | 106
     11005 | 8 | 1923
     11005 | 64 | 155
     11007 | 8 | 1866

etc.

Now, when I launch

Vect_cidx_find_next( Map, field_index=1, cat=11002, type=15,
start_index=3, &stype, &sid )

it returns 4 and line id=1874.

This is wrong as the fourth item in the index, which does have line id
1874, has cat 11004 and not cat 11002. This is confirmed by launching

Vect_cidx_get_cat_by_index ( Map, field_index, 4, &testcat, &testtype,
&testid)

which returns testcat = 11004.

Am I right in assuming that there is a bug in Vect_cidx_find_next, or am
I misunderstanding something here ?

I don't have this problem with a pure point file, which only has one type:

Field 1 number of unique cats: 589 number of cats: 593
number of types: 1
------------------------------------------------------------------------------------------

             type | count
                1 | 593
  category | type | line/area
     11001 | 1 | 97
     11002 | 1 | 12
     11002 | 1 | 593
     11004 | 1 | 76
     11005 | 1 | 125
     11007 | 1 | 68

So this seems to be linked to the type handling.

Any ideas,

Moritz

_______________________________________________
grass-dev mailing list
grass-dev@grass.itc.it
http://grass.itc.it/mailman/listinfo/grass-dev

4

On 9/29/06, Moritz Lennert <mlennert@club.worldonline.be> wrote:

Radim Blazek wrote:
> Yes,
> it seems to be bug, I think that on row 296 in cindex.c
> the requested cat should also be checked, not only the type.
> But I am tired now, please check it twice.

Changing that line into

if ( ci->cat[cat_index][0] == cat && ci->cat[cat_index][1] & type_mask )

works. Thanks !

But I don't really understand how this could happen, as I thought the
following lines (286-288) should take care of this before:

while ( cat_index > start_index ) {
     if ( ci->cat[cat_index-1][0] != cat ) {
        break;

No, this goes down to lowes index of this cat because bsearch
does not return the first item.

To simplify use of cat index in modules I would suggest 2 new functions
(not tested/compiled):

void Vect_cidx_find_lines ( struct Map_info *Map, int layer, int cat,
                                 struct ilist *lines )
{
      int type, line;
      struct Cat_index *ci;

      Vect_reset_list ( lines );
      int field_index = Vect_cidx_get_field_index ( Map, layer );
      ci = &(Map->plus.cidx[field_index]);

      int idx = Vect_cidx_find_next ( Map, field_index, cat, 0,
                                  GV_LINES|GV_POINTS, &type, &line );

      if ( idx == -1 ) return;

      do {
          if ( !(ci->cat[idx][1] & GV_LINES|GV_POINTS)
               || ci->cat[idx][0] != cat )
          {
               break;
           }
           Vect_list_append ( lines, ci->cat[idx][2] );
           idx++;
       } while ( idx < ci->n_cats );
       return;
}

and similarly Vect_cidx_find_areas, then in module:

struct ilist *lines = Vect_new_list();

Vect_cidx_find_lines ( Map, layer, cat, lines );
for ( i = 0; i < lines->n_values; i++ )
{
    line = lines->value[i];
    Vect_read_line ( Map, Points, NULL, line );
}

Radim

So it might actually be a problem in the determination of cat_index
which is higher than it should be.

But just as you, I'm too tired now to look any deeper into this...
:wink:

Moritz

> Bravo Moritz!
>
> Radim
>
> On 9/28/06, Moritz Lennert <mlennert@club.worldonline.be> wrote:
>> Hello,
>>
>> Trying to rework d.vect.chart I am using the Vect_cidx_find_next()
>> function.
>>
>> However, using a map with areas I get behaviour which seems incorrect
>> and which I cannot explain.
>>
>> I have the following category index (result of Vect_cidx_dump(Map,
>> stdout)):
>>
>> .
>> [Field 0]
>> .
>> Field 1 number of unique cats: 589 number of cats: 1185
>> number of types: 3
>> ------------------------------------------------------------------------------------------
>>
>> type | count
>> 8 | 592
>> 4 | 1
>> 64 | 592
>> category | type | line/area
>> 11001 | 8 | 1895
>> 11001 | 64 | 127
>> 11002 | 8 | 1810
>> 11002 | 64 | 42
>> 11004 | 8 | 1874
>> 11004 | 64 | 106
>> 11005 | 8 | 1923
>> 11005 | 64 | 155
>> 11007 | 8 | 1866
>>
>> etc.
>>
>> Now, when I launch
>>
>> Vect_cidx_find_next( Map, field_index=1, cat=11002, type=15,
>> start_index=3, &stype, &sid )
>>
>> it returns 4 and line id=1874.
>>
>> This is wrong as the fourth item in the index, which does have line id
>> 1874, has cat 11004 and not cat 11002. This is confirmed by launching
>>
>> Vect_cidx_get_cat_by_index ( Map, field_index, 4, &testcat, &testtype,
>> &testid)
>>
>> which returns testcat = 11004.
>>
>> Am I right in assuming that there is a bug in Vect_cidx_find_next, or am
>> I misunderstanding something here ?
>>
>> I don't have this problem with a pure point file, which only has one
>> type:
>>
>> Field 1 number of unique cats: 589 number of cats: 593
>> number of types: 1
>> ------------------------------------------------------------------------------------------
>>
>> type | count
>> 1 | 593
>> category | type | line/area
>> 11001 | 1 | 97
>> 11002 | 1 | 12
>> 11002 | 1 | 593
>> 11004 | 1 | 76
>> 11005 | 1 | 125
>> 11007 | 1 | 68
>>
>> So this seems to be linked to the type handling.
>>
>> Any ideas,
>>
>> Moritz
>>
>
> _______________________________________________
> grass-dev mailing list
> grass-dev@grass.itc.it
> http://grass.itc.it/mailman/listinfo/grass-dev

5

And BTW with the fix, people should get (QGIS/v.digit)
more messages:
"Orphan record was left in attribute table. Delete the record?"

Radim

On 9/29/06, Radim Blazek <radim.blazek@gmail.com> wrote:

On 9/29/06, Moritz Lennert <mlennert@club.worldonline.be> wrote:
> Radim Blazek wrote:
> > Yes,
> > it seems to be bug, I think that on row 296 in cindex.c
> > the requested cat should also be checked, not only the type.
> > But I am tired now, please check it twice.
>
> Changing that line into
>
> if ( ci->cat[cat_index][0] == cat && ci->cat[cat_index][1] & type_mask )
>
> works. Thanks !
>
> But I don't really understand how this could happen, as I thought the
> following lines (286-288) should take care of this before:
>
> while ( cat_index > start_index ) {
> if ( ci->cat[cat_index-1][0] != cat ) {
> break;

No, this goes down to lowes index of this cat because bsearch
does not return the first item.

To simplify use of cat index in modules I would suggest 2 new functions
(not tested/compiled):

void Vect_cidx_find_lines ( struct Map_info *Map, int layer, int cat,
                                 struct ilist *lines )
{
      int type, line;
      struct Cat_index *ci;

      Vect_reset_list ( lines );
      int field_index = Vect_cidx_get_field_index ( Map, layer );
      ci = &(Map->plus.cidx[field_index]);

      int idx = Vect_cidx_find_next ( Map, field_index, cat, 0,
                                  GV_LINES|GV_POINTS, &type, &line );

      if ( idx == -1 ) return;

      do {
          if ( !(ci->cat[idx][1] & GV_LINES|GV_POINTS)
               || ci->cat[idx][0] != cat )
          {
               break;
           }
           Vect_list_append ( lines, ci->cat[idx][2] );
           idx++;
       } while ( idx < ci->n_cats );
       return;
}

and similarly Vect_cidx_find_areas, then in module:

struct ilist *lines = Vect_new_list();

Vect_cidx_find_lines ( Map, layer, cat, lines );
for ( i = 0; i < lines->n_values; i++ )
{
    line = lines->value[i];
    Vect_read_line ( Map, Points, NULL, line );
}

Radim

> So it might actually be a problem in the determination of cat_index
> which is higher than it should be.
>
> But just as you, I'm too tired now to look any deeper into this...
> :wink:
>
> Moritz
>
> > Bravo Moritz!
> >
> > Radim
> >
> > On 9/28/06, Moritz Lennert <mlennert@club.worldonline.be> wrote:
> >> Hello,
> >>
> >> Trying to rework d.vect.chart I am using the Vect_cidx_find_next()
> >> function.
> >>
> >> However, using a map with areas I get behaviour which seems incorrect
> >> and which I cannot explain.
> >>
> >> I have the following category index (result of Vect_cidx_dump(Map,
> >> stdout)):
> >>
> >> .
> >> [Field 0]
> >> .
> >> Field 1 number of unique cats: 589 number of cats: 1185
> >> number of types: 3
> >> ------------------------------------------------------------------------------------------
> >>
> >> type | count
> >> 8 | 592
> >> 4 | 1
> >> 64 | 592
> >> category | type | line/area
> >> 11001 | 8 | 1895
> >> 11001 | 64 | 127
> >> 11002 | 8 | 1810
> >> 11002 | 64 | 42
> >> 11004 | 8 | 1874
> >> 11004 | 64 | 106
> >> 11005 | 8 | 1923
> >> 11005 | 64 | 155
> >> 11007 | 8 | 1866
> >>
> >> etc.
> >>
> >> Now, when I launch
> >>
> >> Vect_cidx_find_next( Map, field_index=1, cat=11002, type=15,
> >> start_index=3, &stype, &sid )
> >>
> >> it returns 4 and line id=1874.
> >>
> >> This is wrong as the fourth item in the index, which does have line id
> >> 1874, has cat 11004 and not cat 11002. This is confirmed by launching
> >>
> >> Vect_cidx_get_cat_by_index ( Map, field_index, 4, &testcat, &testtype,
> >> &testid)
> >>
> >> which returns testcat = 11004.
> >>
> >> Am I right in assuming that there is a bug in Vect_cidx_find_next, or am
> >> I misunderstanding something here ?
> >>
> >> I don't have this problem with a pure point file, which only has one
> >> type:
> >>
> >> Field 1 number of unique cats: 589 number of cats: 593
> >> number of types: 1
> >> ------------------------------------------------------------------------------------------
> >>
> >> type | count
> >> 1 | 593
> >> category | type | line/area
> >> 11001 | 1 | 97
> >> 11002 | 1 | 12
> >> 11002 | 1 | 593
> >> 11004 | 1 | 76
> >> 11005 | 1 | 125
> >> 11007 | 1 | 68
> >>
> >> So this seems to be linked to the type handling.
> >>
> >> Any ideas,
> >>
> >> Moritz
> >>
> >
> > _______________________________________________
> > grass-dev mailing list
> > grass-dev@grass.itc.it
> > http://grass.itc.it/mailman/listinfo/grass-dev
>

6

Coming back to this discussion...

Radim Blazek wrote:

On 9/29/06, Moritz Lennert <mlennert@club.worldonline.be> wrote:

Radim Blazek wrote:
> Yes,
> it seems to be bug, I think that on row 296 in cindex.c
> the requested cat should also be checked, not only the type.
> But I am tired now, please check it twice.

Changing that line into

if ( ci->cat[cat_index][0] == cat && ci->cat[cat_index][1] & type_mask )

works. Thanks !

But I don't really understand how this could happen, as I thought the
following lines (286-288) should take care of this before:

while ( cat_index > start_index ) {
     if ( ci->cat[cat_index-1][0] != cat ) {
        break;

No, this goes down to lowest index of this cat because bsearch
does not return the first item.

But what I don't understand is how we even get to a cat_index value which corresponds to a feature with the wrong cat ?

The bsearch should find an object with the right cat and since the cat index is sorted everything below that object should have the right cat until we reach a wrong cat through above while loop.

I have no problem just committing above fix and using your suggestions below, but I would like to understand how the problem could come about.

See below for similar question.

To simplify use of cat index in modules I would suggest 2 new functions
(not tested/compiled):

void Vect_cidx_find_lines ( struct Map_info *Map, int layer, int cat,
                                struct ilist *lines )
{
     int type, line;
     struct Cat_index *ci;

     Vect_reset_list ( lines );
     int field_index = Vect_cidx_get_field_index ( Map, layer );
     ci = &(Map->plus.cidx[field_index]);

     int idx = Vect_cidx_find_next ( Map, field_index, cat, 0,
                                 GV_LINES|GV_POINTS, &type, &line );

     if ( idx == -1 ) return;

     do {
         if ( !(ci->cat[idx][1] & GV_LINES|GV_POINTS)
              || ci->cat[idx][0] != cat )

Again, if Vect_cidx_find_next works correctly, how could this happen ? If it does this would be a bug in Vect_cidx_find_next, or ?

         {
              break;
          }
          Vect_list_append ( lines, ci->cat[idx][2] );
          idx++;
      } while ( idx < ci->n_cats );
      return;
}

and similarly Vect_cidx_find_areas, then in module:

struct ilist *lines = Vect_new_list();

Vect_cidx_find_lines ( Map, layer, cat, lines );
for ( i = 0; i < lines->n_values; i++ )
{
   line = lines->value[i];
   Vect_read_line ( Map, Points, NULL, line );
}

Radim

Thanks !

Moritz

7

Radim,

Radim Blazek wrote:

To simplify use of cat index in modules I would suggest 2 new functions
(not tested/compiled):

void Vect_cidx_find_lines ( struct Map_info *Map, int layer, int cat,
                                struct ilist *lines )
{
     int type, line;
     struct Cat_index *ci;

     Vect_reset_list ( lines );
     int field_index = Vect_cidx_get_field_index ( Map, layer );
     ci = &(Map->plus.cidx[field_index]);

     int idx = Vect_cidx_find_next ( Map, field_index, cat, 0,
                                 GV_LINES|GV_POINTS, &type, &line );

This should be

int idx = Vect_cidx_find_next ( Map, field_index, cat, GV_LINES|GV_POINTS,
                               0,&type, &line );

     if ( idx == -1 ) return;

     do {
         if ( !(ci->cat[idx][1] & GV_LINES|GV_POINTS)
              || ci->cat[idx][0] != cat )

Again, if Vect_cidx_find_next works correctly, how could this happen ?
If it does this would be a bug in Vect_cidx_find_next, or ?

I understand now that this question was nonsense, please forget.

         {
              break;
          }
          Vect_list_append ( lines, ci->cat[idx][2] );
          idx++;
      } while ( idx < ci->n_cats );
      return;
}

I have tested above function and it seems to work well. Helps simplifying
my code...

and similarly Vect_cidx_find_areas

Would this similar function look like below ? If yes, why make this into a
separate function and not simply add a 'type' parameter to above function
which we could then call Vect_cidx_find_ojects_by_cat or something like
that ?

***proposal for Vect_cidx_find_areas**********

void Vect_cidx_find_areas ( struct Map_info *Map, int layer, int cat,
                                 struct ilist *areas )
{
      int type, line;
      struct Cat_index *ci;

      Vect_reset_list ( areas );
      int field_index = Vect_cidx_get_field_index ( Map, layer );
      ci = &(Map->plus.cidx[field_index]);

      int idx = Vect_cidx_find_next ( Map, field_index, cat,
                                  GV_AREA, 0, &type, &line );

      if ( idx == -1 )
       {
        return;
       }

      do {
          if ( !(ci->cat[idx][1] & GV_AREA)
               || ci->cat[idx][0] != cat )
          {
               break;
           }
           Vect_list_append ( areas, ci->cat[idx][2] );
           idx++;
       } while ( idx < ci->n_cats );
       return;
}

Moritz

8

On 10/10/06, Moritz Lennert <mlennert@club.worldonline.be> wrote:

Would this similar function look like below ? If yes, why make this into a
separate function and not simply add a 'type' parameter to above function
which we could then call Vect_cidx_find_ojects_by_cat or something like
that ?

Yes, you are right, it can be one function, it is your
decision.

Radim

***proposal for Vect_cidx_find_areas**********

void Vect_cidx_find_areas ( struct Map_info *Map, int layer, int cat,
                                 struct ilist *areas )
{
      int type, line;
      struct Cat_index *ci;

      Vect_reset_list ( areas );
      int field_index = Vect_cidx_get_field_index ( Map, layer );
      ci = &(Map->plus.cidx[field_index]);

      int idx = Vect_cidx_find_next ( Map, field_index, cat,
                                  GV_AREA, 0, &type, &line );

      if ( idx == -1 )
       {
        return;
       }

      do {
          if ( !(ci->cat[idx][1] & GV_AREA)
               || ci->cat[idx][0] != cat )
          {
               break;
           }
           Vect_list_append ( areas, ci->cat[idx][2] );
           idx++;
       } while ( idx < ci->n_cats );
       return;
}

Moritz

9

Radim Blazek wrote:

On 10/10/06, Moritz Lennert <mlennert@club.worldonline.be> wrote:

Would this similar function look like below ? If yes, why make this into a
separate function and not simply add a 'type' parameter to above function
which we could then call Vect_cidx_find_ojects_by_cat or something like
that ?

Yes, you are right, it can be one function, it is your
decision.

Ok, just committed as Vect_cidx_find_all().

Moritz