Fun With Generics, Class Templates and Static Ifs

[eris]

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