W3C home > Mailing lists > Public > xmlschema-dev@w3.org > July 2005

Re: Algorithm for computing the cardinality of a simpleType?

From: Xan Gregg <xan.gregg@jmp.com>
Date: Thu, 21 Jul 2005 13:33:46 -0400
Message-Id: <0fddad752d5e1e48f0c11763476dd68b@jmp.com>
Cc: <xmlschema-dev@w3.org>
To: "Roger L. Costello" <costello@mitre.org>

> Note that I am assuming that the enumeration facet takes precedence 
> over all
> other facets.  I believe that this is true, isn't it?

I don't think it is. Just because a value satisfies one facet doesn't 
give a free ride past the others.

I like your organization into three parts (pattern, enumerations, and 
range), but unfortunately you need the *intersection* of each part's 
value space. Consider this variation of your exanmple:

> <simpleType name="foo">
>     <restriction base="byte">
>         <pattern value=".*[13579]"/>  <!-- odd numbers -->
>         <minInclusive value="0"/>
>         <maxInclusive value="35"/>
>         <enumeration value="11"/>
>         <enumeration value="22"/>
>         <enumeration value="33"/>
>         <enumeration value="44"/>
>         <enumeration value="55"/>
>     </restriction>
> </simpleType>

The value space is {11, 33} with cardinality 2.

Algorithm becomes:

1. Compute range [lo..hi], as before.

2. If enumeration present,
        cardinality is number of enumeration values that are in [lo..hi] 
and satisfy any pattern values;
        done.

3. If pattern present,
        cardinality is number of values in [lo..hi] that satisfy pattern 
values;
        done.

3. Otherwise, cardinality is hi - lo + 1.

xan


On Jul 21, 2005, at 12:06 PM, Roger L. Costello wrote:
> Hi Xan,
>
> I like your algorithm!  I wonder if checking for enumerations 
> shouldn't be
> done first, and then patterns, and then the 7 steps you described?
>
> Algorithm for Computing the Cardinality of a byte simpleType (with 
> Xan's
> suggestions)
>
> 1. If there are enumeration facets then
>       cardinality = count the number of enumeration facets
>    Done.
>
> 2. If there are pattern facets then
>       cardinality = the maximum cardinality of all the pattern facets.
>    Done.
>
> 3. Otherwise:
>       3.1. lo = -128, hi = 127
>       3.2. minInclusive present => lo = max(lo, minInclusive)
>       3.3. maxInclusive present => hi = min(hi, maxInclusive)
>       3.4. minExclusive present => lo = max(lo, minExclusive + 1)
>       3.5. maxExclusive present => hi = min(hi, maxExclusive - 1)
>       3.6. totalDigits present => lo = max(lo, -10^^totalDigits + 1);
>                                   hi = min(hi, 10^^totalDigits - 1)
>       3.7. cardinality = hi - lo + 1
>
> Note that I am assuming that the enumeration facet takes precedence 
> over all
> other facets.  I believe that this is true, isn't it?
>
> Does this algorithm seem correct?   /Roger
Received on Thursday, 21 July 2005 17:33:50 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 11 January 2011 00:14:50 GMT