Re: Algorithm for computing the cardinality of a simpleType?

Roger,

Computing cardinality of a pattern would be enough to scare me off. 
What is the cardinality of 
0*1*0*2*0*3*0*4*0*5*0*6*0*7*0*8*0*9*8*7*6*5*? If it weren't for leading 
zeros you could just try every possible lexical value and see if it's 
valid.

totalDigits is based on absolute values so it also applies to negative 
numbers. As a result totalDigits of 2 has cardinality 199, not 100.

I think you need to worry more about combinations of facets, such as 
min=75 and totalDigits=2. In the example you give,

> <simpleType name="foo">
>     <restriction base="byte">
>         <minInclusive value="0"/>
>         <maxInclusive value="3"/>
>         <enumeration value="1"/>
>         <enumeration value="2"/>
>     </restriction>
> </simpleType>
>
> My algorithm checks for the combination of minInclusive and 
> maxInclusive
> before it checks for enumerations.  For this example my algorithm 
> returns a
> cardinality of: 4 (which is correct).

Wouldn't 2 be the correct answer because of the enumeration facet?

Ignoring pattern (hard) and enumeration (easy), my approach would be to 
keep a running range while processing factes:

1. lo = -128, hi = 127
2. minInclusive present => lo = max(lo, minInclusive)
3. maxInclusive present => hi = min(hi, maxInclusive)
4. minExclusive present => lo = max(lo, minExclusive + 1)
5. maxExclusive present => hi = min(hi, maxExclusive - 1)
6. totalDigits present => lo = max(lo, -10^^totalDigits + 1); hi = 
min(hi, 10^^totalDigits - 1)
7. range cardinality = hi - lo + 1

Then apply pattern and enumeration info to compute actual cardinality.

xan

Received on Thursday, 21 July 2005 14:11:58 UTC