Re: [Boost-users] Needs advices on design ( mpl or processor )

Subject: Re: [Boost-users] Needs advices on design ( mpl or processor )
From: Larry Evans (cppljevans_at_[hidden])
Date: 2012-01-10 16:35:18

On 01/10/12 14:42, Larry Evans wrote:
> On 01/10/12 14:08, Allan Nielsen wrote:
> [snip]
>>> the largest enumeration.  However, in the case of StructModel_r, I
>>> don't understand:
>>>
>>>    static const size_t size = head::size * _tail::size;
>>>
>>> around line 200.  I would think that there would just be additions
>>> since you want to store one value after another.  That's why, in my
>>> previous post, in template sum_bits, there's:
>>>
>>>      , integral_c<unsigned,Bits+enum_bits<Enum>::size>
>>>
>>> Could you explain why multiplication instead of addition is used to
>>> calculate the size in StructModel_r?
>>
>> This is because the offset is not really an offset, I just could not
>> come up with a better name. Here is the explanation:
>>
>> Assume we need to store 5 different enumerated types which each
>> represents 3 different values ( like the A, B C).
>>
>> These 5 enums can all together represent 3^5 = 243 different values (
>> AAAAA, AAAAB, AAAAC, AAABA, AAABB ...).
>>
>> As 243 is less than 256 ( all the different values in a char), it is
>> possible to store the values in a char. But in a binary number system
>> 2 bits are required to store one tri-state value. If we use 3 * 5 bits
>> we end up with 15 bits ( more than one char) which is not the most
>> efficient encoding.
>>
>> Therefore we encode this in a base_3 number system which is defined
>> by: ... d_2 * n^2 + d_1 * n^1 + d_0 * n^0, where d is the digits we
>> want to encode, and n is 3 because all the enums are tri-states.
>>
>> Example: Encode BCACB  -> 12021
>>
>> 1*3^4 + 2*3^3 + 0*3^2 + 2*3^1 + 1*3^0 = 142
>>
>> To extract enum number 4 the reverse operation must be done: (142 / 3^3) % 3 = 2
>>
>> If different enums are with different sizes are used then n in the
>> equation above will be different for each digit. Then to set digit
>> number 4 one has to multiply n_0 * n_1 * n_2 * n_3 and then use this
>> as base. Therefore the multiplications.
> 
> Ah!  Now I see.  This reminds me of apl decode and encode:
> 
> http://www.sigapl.org/encode.htm
> 
> the radix vector mentioned there represents the sizes (=max value+1)
> of the enums to be stored.  For example, let:
> 
>   enum E_0{e0_0,e0_1,e0_2,...,e0_n0};
>   enum E_1{e1_0,e1_1,...,e1_n1};
>   ...
>   enum E_m{em_0,em_1,...,em_nm};
> 
> then the radix vector, rv, would be:
> 
>   unsigned rv[m+1]={n0+1,n1+2,...,nm+1};
> 
> and to encode the enum values:
> 
>   struct Ev
>   { E_0 e0;
>     E_1 e1;
>     ...
>     E_m em;
>   };
>   Ev ev={e0_i0, e1_i1, ..., em_im};
> 
> decode would be used:
> 
>   unsigned dv=decode(rv,ev)
> 
> where decode is the c++ equivalent of the decode described on encode.htm.
> 
> Is that about right?
> 
> -regards,
> Larry
Also, something similar is done for multidimensional array classes.
for example, given an m-dimensional array, a, the array index
expression:

  a[i0][i1]...[im],

accesses some element in internal data array:

  Type data[(n0+1)*(n1+1)*...*(nm+1)];

where ni, for i=1...m, is the max index for the i-th dimension.

The offset value into data for the is given by:

  i0*s0+i1*s1+...+im*sm

where s0,...sm are the strides of the array, and the strides are just
the partial products of the ni's.  IOW, for fortran storage order:

  s0=1;
  s1=s0*(n0+1);
  s2=s1*(n1+1);
  ...

I think indices_at_offset here:

http://svn.boost.org/svn/boost/sandbox/variadic_templates/sandbox/stepper/boost/array_stepper/indices_at_offset.hpp

which returns the array indices corresponding to some offset into
the array, is doing something similar to what your get<Tag>() is doing.
However, get<Tag> just returns 1 index where Tag corresponds to some
dimension in the array and indices_at_offset resturns all the
indices.

Sound right?

-regards,
Larry