Fun With Generics, Class Templates and Static Ifs

[Denis Koroskin]

On Thu, 04 Jun 2009 20:35:13 +0400, eris <jvburnes at 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
>