By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
459,289 Members | 1,457 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 459,289 IT Pros & Developers. It's quick & easy.

template recursion

P: n/a
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<levelthis_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 }; };

Dec 12 '06 #1
Share this Question
Share on Google+
6 Replies


P: n/a
On Dec 12, 11:31 pm, "Andre Kempe" <AKe...@the-map.dewrote:
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<levelthis_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?

--
Erik Wikström

Dec 13 '06 #2

P: n/a
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_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?

--
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

Dec 13 '06 #3

P: n/a

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_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?

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

index_properties<2iprop;

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.

Dec 13 '06 #4

P: n/a

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

index_properties<2iprop;

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

Dec 13 '06 #5

P: n/a
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_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<levelthis_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_levelthis_level;
struct dummy {
enum { level = the_level };
};
enum { level
=
conditional< ( this_level::number_entries index ),
dummy, __index_properties__<index,the_level+1::value::lev el };
};
// 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
Dec 13 '06 #6

P: n/a
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_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<levelthis_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__ {
I forgot to mention this: names that contain "__" are reserved. So this code
has undefined behavior.
typedef level_properties<the_levelthis_level;
struct dummy {
enum { level = the_level };
};
enum { level
=
conditional< ( this_level::number_entries index ),
dummy, __index_properties__<index,the_level+1::value::lev el };
};
// 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

Dec 13 '06 #7

This discussion thread is closed

Replies have been disabled for this discussion.