On Thu, 04 Jun 2009 20:35:13 +0400, eris <[email protected]> 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
