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
