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_properties<unsigned int>,
i get a compiler-error, complaining about the template-recursion of
__index_properties__. 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_properties {
enum { entries_in_layer = nth_power<level,2>::value };
enum { number_entries = nth_power<level+1,2>::value-1 };
enum { index_first_element = number_entries - entries_in_layer };
};

template< int index , int level >
struct __index_properties__ {
typedef level_properties<level> this_level;
enum { level = (this_level::number_entries>index)? level :
__index_properties__<index,level+1>::level };
};

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


template < int index >
struct index_properties
{ enum { level = __index_properties__<index,0>::level }; };

 

[eriwik]

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_properties<unsigned int>,
i get a compiler-error, complaining about the template-recursion of
__index_properties__. 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_properties {
enum { entries_in_layer = nth_power<level,2>::value };
enum { number_entries = nth_power<level+1,2>::value-1 };
enum { index_first_element = number_entries - entries_in_layer };

};template< int index , int level >
struct __index_properties__ {
typedef level_properties<level> this_level;
enum { level = (this_level::number_entries>index)? level :
__index_properties__<index,level+1>::level };
};

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

template < int index >
struct index_properties
{ enum { level = __index_properties__<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_properties. 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?

 

[Andre Kempe]

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_properties. 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?

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:

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_properties__<index, level> is dependent on
__index_properties__<index, level + 1>. So if you declare

index_properties<2> iprop;

You need __index_properties__<2,0>::level. That depends on
__index_properties__<2,1>::level, which depends on
__index_properties__<2,2>::level, depends on
__index_properties__<2,3>::level .... etc.

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

template < int index, int limit = 100>
struct index_properties
{
enum { level = __index_properties__<index,0, limit>::level };
};

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

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

 

[Andre Kempe]

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_properties__<index, level> is dependent on
__index_properties__<index, level + 1>. So if you declare

index_properties<2> iprop;

You need __index_properties__<2,0>::level. That depends on
__index_properties__<2,1>::level, which depends on
__index_properties__<2,2>::level, depends on
__index_properties__<2,3>::level .... etc.

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

template < int index, int limit = 100>
struct index_properties
{
enum { level = __index_properties__<index,0, limit>::level };
};

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

Even better solution, which does not need to add new parameter to
__index_properties__ is to rewrite __index_properties__ 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
uncondintionally, 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]

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_properties {
enum { entries_in_layer = nth_power<level,2>::value };
enum { number_entries = nth_power<level+1,2>::value-1 };
enum { index_first_element = number_entries - entries_in_layer };
};

template< int index , int level >
struct __index_properties__ {
typedef level_properties<level> this_level;
enum { level = (this_level::number_entries>index)? level :
__index_properties__<index,level+1>::level };
};

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


template < int index >
struct index_properties
{ enum { level = __index_properties__<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_properties {
enum { entries_in_layer = nth_power<level,2>::value };
enum { number_entries = nth_power<level+1,2>::value-1 };
enum { index_first_element = number_entries - entries_in_layer };
};


template < bool condition, typename S, typename T >
struct conditional;

template < typename S, typename T >
struct conditional<true,S,T> {

typedef S value;

};

template < typename S, typename T >
struct conditional<false,S,T> {

typedef T value;

};



template< int index , int the_level >
struct __index_properties__ {
typedef level_properties<the_level> this_level;
struct dummy {
enum { level = the_level };
};
enum { level
=
conditional< ( this_level::number_entries > index ),
dummy, __index_properties__<index,the_level+1> >::value::level };
};


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

#include <iostream>

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


Best

Kai-Uwe Bux

 

[Kai-Uwe Bux]

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_properties {
enum { entries_in_layer = nth_power<level,2>::value };
enum { number_entries = nth_power<level+1,2>::value-1 };
enum { index_first_element = number_entries - entries_in_layer };
};


template < bool condition, typename S, typename T >
struct conditional;

template < typename S, typename T >
struct conditional<true,S,T> {

typedef S value;

};

template < typename S, typename T >
struct conditional<false,S,T> {

typedef T value;

};



template< int index , int the_level >
struct __index_properties__ {

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

typedef level_properties<the_level> this_level;
struct dummy {
enum { level = the_level };
};
enum { level
=
conditional< ( this_level::number_entries > index ),
dummy, __index_properties__<index,the_level+1> >::value::level };
};


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

#include <iostream>

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

Best

Kai-Uwe Bux