www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Fun With Generics, Class Templates and Static Ifs

reply eris <jvburnes gmail.com> writes:
Greetings D People

I've been building some support code for my new app and decided to take
advantage of the generic support available in D.  What follows is my
implementation of a generic support class.  It's really the first I've done, so
if you could give it a quick once-over I'd appreciate it.  If it's the correct
way to implement this, perhaps the D newbies could use it as an example.

Problem: Develop a class that maintains a  ranked list of the top 'n' values. 
Write it so that it's easily maintainable in a library and useful for more than
one type.  It would be better if the class could track minimum or maximum
values with little to no performance impact.

Solution:

1. Templates can be used to provide type-independent implementations.
2. A template class (and interface) should provide a clean library definition
3. Since ranking behavior for min and max only differs by a single comparison,
some sort of template flag should allow the behavior to change at compile-time.

Implementation:

First, a definition of the interface for our library:

public interface Ranker(T) {
	bool submit(T value); // submits value to test for inclusion.  True if in top
values, false otherwise
	bool expire(T value);  // removes a current member. False if not present, true
otherwise
	T extreme();                // returns the largest magnitude member
}

Note: Since our interface contains an argument T, the interface is a generic
and can be used for any type.

Okay, lets create a class for the implementation:

class Rank(T, A...) : Ranker!(T) {

That's a mouthful.  Let's take it one piece at a time.  

Internally a class template is represented like this:

template Rank(T): {
   class Rank(T)
...
}

But the short form for this is:

class Rank(T)
{
...
}

We want our template class to implement the Ranker interface.  We have to make
sure that we include the exclamation point when we use our interface template. 
Now we have:

class Rank(T): Ranker!(T) 
{
...
}

Almost done, but we need to be able to pass a compile-time flag to our template
so it can compile-in the slight change needed to compare against minimums or
maximums.  This could probably be implemented using some sort of delegate
pattern, but including the proper behavior with a compile-time switch would
avoid the possible function call overhead.

So let's try passing a flag to the template at compile time and using the
'static if' inside the critical method to decide which comparison to use (<= or
>=).

Here, I'm passing flags to the template using a variadic argument list.  It's
indicated by the parameter A followed by an ellipsis (...).  The individual
flags passed in this way can be accessed as if A were an array of the arguments
passed.

So, let's look at the updated declaration:

class Rank(T, A...) : Ranker!(T) {

I'm going to use the first element of A to indicate what kind of Ranker I want.
 If A[0] < 0 then we compile a minimum ranker, else we compile a max ranker. 
I'm also going to create an alias so our template is easier to use, like this:

alias Rank!(int, -1) IntMinRank;
alias Rank!(double,  1) DblMaxRank;

(Note: the complete type independence of this class assumes that proper
underlying operators have been implemented for comparison etc).

So, a skeleton version of the class looks like this:

-----
import tango.io.Stdout;

public interface Ranker(T) {
	bool submit(T value);	// submits a value of type T to be included in top 'n'
values, true if added or already present 
	bool expire(T value);	// removes a previously included value of type T from
top 'n' values, false if non-existant
	T extreme();		// returns the value of type T from Ranker which is the current
top value
}

class Rank(T, A...) : Ranker!(T)
{
	struct RANK {
		T value;
		int occurs;
	}
	
	RANK members[];
	
	int len;
	
	this(int size) {
		auto members = new RANK[size];
		
		// some other init code
	}
	
	bool submit(T value) {
		int i;
		// insert loop
		for (i=0; i<len; i++) {
			static if (A[0]>=0) {  // dev wants max ranker
				// test for one of 'n' top values
				if (value <= members[i].value) break;
			}
			else {  // dev wants min ranker
				// test for one of 'n' bottom values
				if (value >= members[i].value) break;
			}
			// rest of insertion logic, return true or false
		}
		return true;
	}
	
	bool expire(T value) {
		// remove value from list 
		return true;
	}
	
	T extreme() { return members[len-1].value; }
}

alias Rank!(int, -1) IntMinRank;
alias Rank!(int, 1) IntMaxRank;
alias Rank!(double, -1) DblMinRank;
alias Rank!(double,  1) DblMaxRank;

int main() {

	auto top32 = new DblMaxRank(32);	// max rank, 32 members 
	auto bottom16 = new IntMinRank(16);	// min rank, 16 members
	
	return 0;
}

---

That should do what I want.  I do have a question for the experienced
templaters out there:

Is there any way to parameterize the alias statement so I can pass the type of
the generic I want?

In other words, rather than having to create a separate alias for each type
create an alias like this:

alias Rank!(T,-1) MinRank(T);
alias Rank!(T, 1) MaxRank(T);

I tried using this form, but I don't think the syntax is valid.

Thanks,

eris
Jun 04 2009
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
eris:


 class Rank(T, A...) : Ranker!(T) {


Better something like:
class Rank(TyItem, bool ascending=true) : Ranker!(TyItem) {
or something like that.
You have a single type, so the following too may be OK:
class Rank(T, bool ascending=true) : Ranker!(T) {
Using single upper case letters (as often done in C++) when you have more than
one type is bad practice for me (yes, this is true for Phobos too). It's better
the Pascal usage of giving them a meaningful name that starts with an upper
case letter.



 In other words, rather than having to create a separate alias for each type
create an alias like this:
 alias Rank!(T,-1) MinRank(T);
 alias Rank!(T, 1) MaxRank(T);
 I tried using this form, but I don't think the syntax is valid.


I think this works in D1:

template MinRank(T) {
    alias Rank!(T, true) MinRank;
}

template MaxRank(T) {
    alias Rank!(T, true) MaxRank;
}

Bye,
bearophile
Jun 04 2009
prev sibling parent reply "Denis Koroskin" <2korden gmail.com> writes:
On Thu, 04 Jun 2009 20:35:13 +0400, eris <jvburnes gmail.com> wrote:


 Greetings D People

 I've been building some support code for my new app and decided to take  
 advantage of the generic support available in D.  What follows is my  
 implementation of a generic support class.  It's really the first I've  
 done, so if you could give it a quick once-over I'd appreciate it.  If  
 it's the correct way to implement this, perhaps the D newbies could use  
 it as an example.

 Problem: Develop a class that maintains a  ranked list of the top 'n'  
 values.  Write it so that it's easily maintainable in a library and  
 useful for more than one type.  It would be better if the class could  
 track minimum or maximum values with little to no performance impact.

 Solution:

 1. Templates can be used to provide type-independent implementations.
 2. A template class (and interface) should provide a clean library  
 definition
 3. Since ranking behavior for min and max only differs by a single  
 comparison, some sort of template flag should allow the behavior to  
 change at compile-time.

 Implementation:

 First, a definition of the interface for our library:

 public interface Ranker(T) {
 	bool submit(T value); // submits value to test for inclusion.  True if  
 in top values, false otherwise
 	bool expire(T value);  // removes a current member. False if not  
 present, true otherwise
 	T extreme();                // returns the largest magnitude member
 }

 Note: Since our interface contains an argument T, the interface is a  
 generic and can be used for any type.

 Okay, lets create a class for the implementation:

 class Rank(T, A...) : Ranker!(T) {

 That's a mouthful.  Let's take it one piece at a time.

 Internally a class template is represented like this:

 template Rank(T): {
    class Rank(T)
 ...
 }

 But the short form for this is:

 class Rank(T)
 {
 ...
 }

 We want our template class to implement the Ranker interface.  We have  
 to make sure that we include the exclamation point when we use our  
 interface template.  Now we have:

 class Rank(T): Ranker!(T)
 {
 ...
 }

 Almost done, but we need to be able to pass a compile-time flag to our  
 template so it can compile-in the slight change needed to compare  
 against minimums or maximums.  This could probably be implemented using  
 some sort of delegate pattern, but including the proper behavior with a  
 compile-time switch would avoid the possible function call overhead.

 So let's try passing a flag to the template at compile time and using  
 the 'static if' inside the critical method to decide which comparison to  
 use (<= or >=).

 Here, I'm passing flags to the template using a variadic argument list.   
 It's indicated by the parameter A followed by an ellipsis (...).  The  
 individual flags passed in this way can be accessed as if A were an  
 array of the arguments passed.

 So, let's look at the updated declaration:

 class Rank(T, A...) : Ranker!(T) {

 I'm going to use the first element of A to indicate what kind of Ranker  
 I want.  If A[0] < 0 then we compile a minimum ranker, else we compile a  
 max ranker.  I'm also going to create an alias so our template is easier  
 to use, like this:

 alias Rank!(int, -1) IntMinRank;
 alias Rank!(double,  1) DblMaxRank;

 (Note: the complete type independence of this class assumes that proper  
 underlying operators have been implemented for comparison etc).

 So, a skeleton version of the class looks like this:

 -----
 import tango.io.Stdout;

 public interface Ranker(T) {
 	bool submit(T value);	// submits a value of type T to be included in  
 top 'n' values, true if added or already present
 	bool expire(T value);	// removes a previously included value of type T  
 from top 'n' values, false if non-existant
 	T extreme();		// returns the value of type T from Ranker which is the  
 current top value
 }

 class Rank(T, A...) : Ranker!(T)
 {
 	struct RANK {
 		T value;
 		int occurs;
 	}
 	
 	RANK members[];
 	
 	int len;
 	
 	this(int size) {
 		auto members = new RANK[size];
 		
 		// some other init code
 	}
 	
 	bool submit(T value) {
 		int i;
 		// insert loop
 		for (i=0; i<len; i++) {
 			static if (A[0]>=0) {  // dev wants max ranker
 				// test for one of 'n' top values
 				if (value <= members[i].value) break;
 			}
 			else {  // dev wants min ranker
 				// test for one of 'n' bottom values
 				if (value >= members[i].value) break;
 			}
 			// rest of insertion logic, return true or false
 		}
 		return true;
 	}
 	
 	bool expire(T value) {
 		// remove value from list
 		return true;
 	}
 	
 	T extreme() { return members[len-1].value; }
 }

 alias Rank!(int, -1) IntMinRank;
 alias Rank!(int, 1) IntMaxRank;
 alias Rank!(double, -1) DblMinRank;
 alias Rank!(double,  1) DblMaxRank;

 int main() {

 	auto top32 = new DblMaxRank(32);	// max rank, 32 members
 	auto bottom16 = new IntMinRank(16);	// min rank, 16 members
 	
 	return 0;
 }

 ---


Your ideas are right, but code smells a bit :) Just a few comments:

- what's len? It's never initialized. There's no need to have it, because  
you can use "members.length" property instead.
Second, make sure you make your fields private.

- I'd use an enumeration to specify minimum or maximum:
enum StorePolicy { Minumum, Maximum }
class Rank(T, StorePolicy policy) { ... }

- Don't use "members[len-1]", use "members[$-1]" instead.

- I don't see any reason not to declare "i" inside a for loop ("bool  
submit(T value)" method):

for (int i = 0; ...) { ... }

- There is no need for a loop at all!

bool submit(T value) {
     static if (policy == StorePolicy.Minimum) {
         if (members[$-1] < value) {
             return false;
         }
         members[$-1] = value;
    } else {
         if (members[0] > value) {
             return false;
         }
         members[0] = value;
     }

     bubbleSort(members);
     return true;
}

Alternative implementation (should be slightly faster):

bool submit(T value) {
     static if (policy == StorePolicy.Minimum) {
         int insertIndex = upperBound(members, value);
         if (insertIndex == members.length) {
             return false;
         }

         // move elements (memmove is faster but less safe)
         for (int i = insertIndex+1; i < members.length; ++i) {
             members[i] = members[i-1];
         }

         // store it
         members[insertIndex] = value;
     } else {
         int insertIndex = lowerBound(members, value);
         if (insertIndex == 0) {
             return false;
         }

         // move elements (memmove is faster but less safe)
         for (int i = 0; i < insertIndex; ++i) {
             members[i] = members[i+1];
         }

         // store it
         members[insertIndex] = value;
     }

     return true;
}

(code not tested)


 That should do what I want.  I do have a question for the experienced  
 templaters out there:

 Is there any way to parameterize the alias statement so I can pass the  
 type of the generic I want?

 In other words, rather than having to create a separate alias for each  
 type create an alias like this:

 alias Rank!(T,-1) MinRank(T);
 alias Rank!(T, 1) MaxRank(T);

 I tried using this form, but I don't think the syntax is valid.


It is done slightly different:

template MinRank(T) {
     alias Rank!(T, -1) MinRank;
}

template MaxRank(T) {
     alias Rank!(T, 1) MaxRank;
}


 Thanks,

 eris
Jun 04 2009
parent eris <jvburnes gmail.com> writes:
Denis Koroskin Wrote:


 On Thu, 04 Jun 2009 20:35:13 +0400, eris <jvburnes gmail.com> wrote:
 

 Greetings D People





 ---


 
 Your ideas are right, but code smells a bit :) Just a few comments:
 
 - what's len? It's never initialized. There's no need to have it, because  
 you can use "members.length" property instead.
 Second, make sure you make your fields private.
 


Hehe.  Thanks.   Sure.  This code wasn't meant as a final form in any sense. 
As you and bearophile point out, it's better to use a more sophisticated way of
indicating or including the alternate storage behavior.  You're correct.  Len
isn't initialized, and the current form of the algo already corrects this.
 

 - I'd use an enumeration to specify minimum or maximum:
 enum StorePolicy { Minumum, Maximum }
 class Rank(T, StorePolicy policy) { ... }
 
 - Don't use "members[len-1]", use "members[$-1]" instead.
 


Good idea on storage policy.  Much better than a -1,0,+1 hack and much more
readable.  


 - I don't see any reason not to declare "i" inside a for loop ("bool  
 submit(T value)" method):
 
 for (int i = 0; ...) { ... }
 


Because I need its value outside the loop after break.   The code you see is
just enough to get the compiler to accept it and doesn't show algorithm details.


 - There is no need for a loop at all!


Actually the loop implements a single insertion pass.  The object is optimized
for access frequency.
 

 bool submit(T value) {
      static if (policy == StorePolicy.Minimum) {
          if (members[$-1] < value) {
              return false;
          }
          members[$-1] = value;
     } else {
          if (members[0] > value) {
              return false;
          }
          members[0] = value;
      }
 
      bubbleSort(members);
      return true;
 }
 
 Alternative implementation (should be slightly faster):
 
 bool submit(T value) {
      static if (policy == StorePolicy.Minimum) {


Yep.  Thanks.   I've implemented an algo similar to yours and optimized for a
slightly different performance profile.


 Is there any way to parameterize the alias statement so I can pass the  
 type of the generic I want?




...

 
 It is done slightly different:
 
 template MinRank(T) {
      alias Rank!(T, -1) MinRank;
 }
 
 template MaxRank(T) {
      alias Rank!(T, 1) MaxRank;
 }


Cool.  Exactly what I needed.  Thanks to you and Bearophile.
Jun 04 2009