[#396] da_is_included questionable

Date:
2013-04-02 18:44

Priority:
3

State:
Open

Submitted by:
Raymond Dubler (remozis)

Assigned to:
Stéphane ROUGES (srouges)

Target Fix Version:
Unassigned

Product:
none

Operating System:
none

Component:
none

Version:
none

Severity:
trivial

Resolution:
Fixed

Hardware:
none

URL:

Summary:
da_is_included questionable

Detailed description
da_is_included has a return value of DC_TRUE "if a is included in b", else DC_FALSE. If you assume that this means every value of set A has to be present in set B, then the current implementation of da_is_included does not work. A workaround for da_is_included that adheres to the above statement could look as follows: DC_BOOL da_is_included(dyn_array_t a, dyn_array_t b, da_cmp_cbk compare) { int i, j; if (a == NULL \|\| a->nb == 0) return DC_TRUE; if (b == NULL \|\| b->nb == 0) return DC_FALSE; for (i = 0; i < a->nb; i++) { int present = 0; for (j = 0; j < b->nb ; j++ ) { if ( 0 == compare(GET_ENTRY(a, i), GET_ENTRY(b, j)) ) { present = 1; break; } } if (0 == present) return DC_FALSE; } return DC_TRUE; } Is my understanding of "is included" correct? -Remo-
da_is_included has a return value of DC_TRUE "if a is included in b", else DC_FALSE. If you assume that this means every value of set A has to be present in set B, then the current implementation of da_is_included does not work. A workaround for da_is_included that adheres to the above statement could look as follows: DC_BOOL da_is_included(dyn_array_t a, dyn_array_t b, da_cmp_cbk compare) { int i, j; if (a == NULL \|\| a->nb == 0) return DC_TRUE; if (b == NULL \|\| b->nb == 0) return DC_FALSE; for (i = 0; i < a->nb; i++) { int present = 0; for (j = 0; j < b->nb ; j++ ) { if ( 0 == compare(GET_ENTRY(a, i), GET_ENTRY(b, j)) ) { present = 1; break; } } if (0 == present) return DC_FALSE; } return DC_TRUE; } Is my understanding of "is included" correct? -Remo-

Comments
Attachments
Changes

Message
Date: 2013-04-08 13:05 Sender: Stéphane ROUGES Fixed in trunk.
Date: 2013-04-08 12:46 Sender: Stéphane ROUGES Sorry, you were right... The trick is that that da_is_included() was made a reusable tool used especially for discovery but the semantics of the comparator should be in fact a boolean in case of equality (this is what is still expecting the code using it). I'm going to create a new callback type with the right semantics. I did not check carefully enough what you said because neither our tests, neither our users did detect any problem of this kind in discovery. Thank you, Stéphane
Date: 2013-04-05 19:00 Sender: Raymond Dubler To shed some more light on this, consider the following: I assume compare works like strcmp; if the values are not the same you get a 0> or <0 back, and if they match you get a 0 back. In the inner loop when compare returns 0 (due to match), that gets negated and turns into a 1, which keeps the loop running.
Date: 2013-04-05 18:08 Sender: Raymond Dubler I tested the loop with a disjoint set and still got true back, which made me suspicious. The problem is that the inner loop breaks on the 1st occurence of a non true element, but will only return false if it made it to the end of the inner loop.
Date: 2013-04-04 08:44 Sender: Stéphane ROUGES Hi, I think your understanding of the function is OK but I don't see how your code is different ? For me, you do the same as the original does, except that you use an intermediate variable that we spare. You exit the inner loop when the "a" element is found and set "present" while we exit when found and check we exhausted the "b" set because the bound was reached to detect failure of inclusion. Did you get to inspect this code because you faced a misbehavior of the software ? BR, Stéphane

Field	Old Value	Date	By
assigned_to	none	2013-04-08 13:05	srouges
Severity	None	2013-04-08 13:05	srouges
Resolution	Accepted As Bug	2013-04-08 13:05	srouges
Resolution	Works For Me	2013-04-08 12:46	srouges
Resolution	None	2013-04-04 08:44	srouges