template recursion

[Andre Kempe]

hej folks.

i have a heap with fixed size and want to determine the depth of a
element with given index at compile-time. therefore i wrote some
templates. however, when i use template index_propertie s<unsigned int>,
i get a compiler-error, complaining about the template-recursion of
__index_propert ies__. when i add a partially specialized template (the
three commented lines) to stop the template-recursion, it works.

does anyone how to make it work without this partial specialization? ??

my compiler is microsoft visual studio 2005

thanks in advance
andre
=============== =============== ========
template < unsigned int power , int base >
struct nth_power
{ enum { value = nth_power<power-1,base>::value* base }; };

template < int base >
struct nth_power< 0 , base >
{ enum { value = 1 }; };

template< unsigned int level >
struct level_propertie s {
enum { entries_in_laye r = nth_power<level ,2>::value };
enum { number_entries = nth_power<level +1,2>::value-1 };
enum { index_first_ele ment = number_entries - entries_in_laye r };
};

template< int index , int level >
struct __index_propert ies__ {
typedef level_propertie s<levelthis_lev el;
enum { level = (this_level::nu mber_entries>in dex)? level :
__index_propert ies__<index,lev el+1>::level };
};

// template< int index >
// struct __index_propert ies__<index,20>
// { enum { level = 20 }; };
template < int index >
struct index_propertie s
{ enum { level = __index_propert ies__<index,0>: :level }; };

[eriwik]

On Dec 12, 11:31 pm, "Andre Kempe" <[e-mail]:

hej folks.

i have a heap with fixed size and want to determine the depth of a
element with given index at compile-time. therefore i wrote some
templates. however, when i use template index_propertie s<unsigned int>,
i get a compiler-error, complaining about the template-recursion of
__index_propert ies__. when i add a partially specialized template (the
three commented lines) to stop the template-recursion, it works.

does anyone how to make it work without this partial specialization? ??

my compiler is microsoft visual studio 2005

thanks in advance
andre

=============== =============== ========
template < unsigned int power , int base >
struct nth_power
{ enum { value = nth_power<power-1,base>::value* base }; };

template < int base >
struct nth_power< 0 , base >
{ enum { value = 1 }; };

template< unsigned int level >
struct level_propertie s {
enum { entries_in_laye r = nth_power<level ,2>::value };
enum { number_entries = nth_power<level +1,2>::value-1 };
enum { index_first_ele ment = number_entries - entries_in_laye r };

};template< int index , int level >
struct __index_propert ies__ {
typedef level_propertie s<levelthis_lev el;
enum { level = (this_level::nu mber_entries>in dex)? level :
__index_propert ies__<index,lev el+1>::level };
};

// template< int index >
// struct __index_propert ies__<index,20>
// { enum { level = 20 }; };

template < int index >
struct index_propertie s
{ enum { level = __index_propert ies__<index,0>: :level }; };

I'm not claiming to fully understand you code but it seems to me like
you are trying to use recursion to determine the level_propertie s. When
using recursion you must have a base-case somewhere or you'll end up
recursing(?) forever. Is there something wrong with the partial
specialization?

--
Erik Wikström

[Andre Kempe]

er****@student. chalmers.se schrieb:

>
I'm not claiming to fully understand you code but it seems to me like
you are trying to use recursion to determine the level_propertie s. When
using recursion you must have a base-case somewhere or you'll end up
recursing(?) forever. Is there something wrong with the partial
specialization?

--
Erik Wikström

heij.

well, i simply do not consider the partial specialization a very
elegant solution, as it restricts the maximum recursion level to some
artificial value that has nothing to do with the compiler in use or the
problem being solved.

and as i remember, template should not be evaluated when it is not
used. therefore i thought that the ? would be enough to stop an endless
template-recursion.

andre

[Ondra Holub]

Andre Kempe napsal:

er****@student. chalmers.se schrieb:

I'm not claiming to fully understand you code but it seems to me like
you are trying to use recursion to determine the level_propertie s. When
using recursion you must have a base-case somewhere or you'll end up
recursing(?) forever. Is there something wrong with the partial
specialization?

--
Erik Wikström

heij.

well, i simply do not consider the partial specialization a very
elegant solution, as it restricts the maximum recursion level to some
artificial value that has nothing to do with the compiler in use or the
problem being solved.

and as i remember, template should not be evaluated when it is not
used. therefore i thought that the ? would be enough to stop an endless
template-recursion.

andre

Well, for recursion (either function recursion or template recursion)
you need some condition, which ends the recursion. For templates is
such condition usualy made with partial specialization (or with full
specialization) .

You mentioned, that only templates, which are instantiated, are used.
That's right. But you need infinite number of templates, because
__index_propert ies__<index, levelis dependent on
__index_propert ies__<index, level + 1>. So if you declare

index_propertie s<2iprop;

You need __index_propert ies__<2,0>::lev el. That depends on
__index_propert ies__<2,1>::lev el, which depends on
__index_propert ies__<2,2>::lev el, depends on
__index_propert ies__<2,3>::lev el .... etc.

You definitely need to pass limit to index_propertie s. It may be
optional parameter, something like

template < int index, int limit = 100>
struct index_propertie s
{
enum { level = __index_propert ies__<index,0, limit>::level };
};

And then write partial specialization of __index_propert ies__:
template< int index, int LEVEL >
struct __index_propert ies__<index,LEV EL, LEVEL>
{ enum { level = LEVEL };
};

Even better solution, which does not need to add new parameter to
__index_propert ies__ is to rewrite __index_propert ies__ to start with
given limit and make it dependent on it's predecessor. Than write
specialization for value 0.

[Andre Kempe]

Ondra Holub schrieb:

>
Well, for recursion (either function recursion or template recursion)
you need some condition, which ends the recursion. For templates is
such condition usualy made with partial specialization (or with full
specialization) .

You mentioned, that only templates, which are instantiated, are used.
That's right. But you need infinite number of templates, because
__index_propert ies__<index, levelis dependent on
__index_propert ies__<index, level + 1>. So if you declare

index_propertie s<2iprop;

You need __index_propert ies__<2,0>::lev el. That depends on
__index_propert ies__<2,1>::lev el, which depends on
__index_propert ies__<2,2>::lev el, depends on
__index_propert ies__<2,3>::lev el .... etc.

You definitely need to pass limit to index_propertie s. It may be
optional parameter, something like

template < int index, int limit = 100>
struct index_propertie s
{
enum { level = __index_propert ies__<index,0, limit>::level };
};

And then write partial specialization of __index_propert ies__:
template< int index, int LEVEL >
struct __index_propert ies__<index,LEV EL, LEVEL>
{ enum { level = LEVEL };
};

Even better solution, which does not need to add new parameter to
__index_propert ies__ is to rewrite __index_propert ies__ to start with
given limit and make it dependent on it's predecessor. Than write
specialization for value 0.

jepps, this is exactly what i've been trying to avoid, making any
asumptions on the limit. because the template is not recursed
uncondintionall y, but only when the limit has not been reached yet, i
thought that this is enough to stop recursion.

ok, thanks to eveyone. i'll go and see what i can do.
andre

[Kai-Uwe Bux]

Andre Kempe wrote:

template < unsigned int power , int base >
struct nth_power
{ enum { value = nth_power<power-1,base>::value* base }; };

template < int base >
struct nth_power< 0 , base >
{ enum { value = 1 }; };

template< unsigned int level >
struct level_propertie s {
enum { entries_in_laye r = nth_power<level ,2>::value };
enum { number_entries = nth_power<level +1,2>::value-1 };
enum { index_first_ele ment = number_entries - entries_in_laye r };
};

template< int index , int level >
struct __index_propert ies__ {
typedef level_propertie s<levelthis_lev el;
enum { level = (this_level::nu mber_entries>in dex)? level :
__index_propert ies__<index,lev el+1>::level };
};

// template< int index >
// struct __index_propert ies__<index,20>
// { enum { level = 20 }; };
template < int index >
struct index_propertie s
{ enum { level = __index_propert ies__<index,0>: :level }; };

What about:

template < unsigned int power , int base >
struct nth_power
{ enum { value = nth_power<power-1,base>::value* base }; };

template < int base >
struct nth_power< 0 , base >
{ enum { value = 1 }; };

template< unsigned int level >
struct level_propertie s {
enum { entries_in_laye r = nth_power<level ,2>::value };
enum { number_entries = nth_power<level +1,2>::value-1 };
enum { index_first_ele ment = number_entries - entries_in_laye r };
};
template < bool condition, typename S, typename T >
struct conditional;

template < typename S, typename T >
struct conditional<tru e,S,T{

typedef S value;

};

template < typename S, typename T >
struct conditional<fal se,S,T{

typedef T value;

};

template< int index , int the_level >
struct __index_propert ies__ {
typedef level_propertie s<the_levelthis _level;
struct dummy {
enum { level = the_level };
};
enum { level
=
conditional< ( this_level::num ber_entries index ),
dummy, __index_propert ies__<index,the _level+1::value ::level };
};
// template< int index >
// struct __index_propert ies__<index,20>
// { enum { level = 20 }; };

#include <iostream>

template < int index >
struct index_propertie s
{ enum { level = __index_propert ies__<index,0>: :level }; };
int main ( void ) {
std::cout << index_propertie s< 15 >::level << '\n';
}
Best

Kai-Uwe Bux

[Kai-Uwe Bux]

Kai-Uwe Bux wrote:

Andre Kempe wrote:

>template < unsigned int power , int base >
struct nth_power
{ enum { value = nth_power<power-1,base>::value* base }; };

template < int base >
struct nth_power< 0 , base >
{ enum { value = 1 }; };

template< unsigned int level >
struct level_propertie s {
enum { entries_in_laye r = nth_power<level ,2>::value };
enum { number_entries = nth_power<level +1,2>::value-1 };
enum { index_first_ele ment = number_entries - entries_in_laye r };
};

template< int index , int level >
struct __index_propert ies__ {
typedef level_propertie s<levelthis_lev el;
enum { level = (this_level::nu mber_entries>in dex)? level :
__index_proper ties__<index,le vel+1>::level };
};

// template< int index >
// struct __index_propert ies__<index,20>
// { enum { level = 20 }; };
template < int index >
struct index_propertie s
{ enum { level = __index_propert ies__<index,0>: :level }; };

What about:

template < unsigned int power , int base >
struct nth_power
{ enum { value = nth_power<power-1,base>::value* base }; };

template < int base >
struct nth_power< 0 , base >
{ enum { value = 1 }; };

template< unsigned int level >
struct level_propertie s {
enum { entries_in_laye r = nth_power<level ,2>::value };
enum { number_entries = nth_power<level +1,2>::value-1 };
enum { index_first_ele ment = number_entries - entries_in_laye r };
};
template < bool condition, typename S, typename T >
struct conditional;

template < typename S, typename T >
struct conditional<tru e,S,T{

typedef S value;

};

template < typename S, typename T >
struct conditional<fal se,S,T{

typedef T value;

};

template< int index , int the_level >
struct __index_propert ies__ {

I forgot to mention this: names that contain "__" are reserved. So this code
has undefined behavior.

typedef level_propertie s<the_levelthis _level;
struct dummy {
enum { level = the_level };
};
enum { level
=
conditional< ( this_level::num ber_entries index ),
dummy, __index_propert ies__<index,the _level+1::value ::level };
};
// template< int index >
// struct __index_propert ies__<index,20>
// { enum { level = 20 }; };

#include <iostream>

template < int index >
struct index_propertie s
{ enum { level = __index_propert ies__<index,0>: :level }; };
int main ( void ) {
std::cout << index_propertie s< 15 >::level << '\n';
}

Best

Kai-Uwe Bux