Rüdiger Plantiko - 2009-06-05

Now after the Range part being essentially completed, I am working on the Pattern part.

I didn't find any example of a pattern which cannot be handled with the following top-N-list strategy:

1.) For each horoscope that is carried from the Range to the Pattern, a score function is evaluated
2.) The horoscope is inserted into a sorted array with size limited to N entries. The sort order is descending by score value.

When the range is processed, the pattern will contain the N horoscopes with the highest values of the score function. These can be passed to the caller.

Degenerate cases:
a) the "BoolPattern" with no size limit: Instead of a score function, it returns a boolean value. Depending on that value, the record should be added to the result or not.
b) N = infinity. One could be interested in a list of the score values for *all* records of the range. This could be handled by setting the size parameter to 0 in the construction of the Pattern.

The following test program shows the ideas. It is based on the SGI STL, I need the vector class and the binary search algorithm from there.

I am using a get_instance() function with a character string as type specifier. The test output is generated with a boolean pattern and no size restriction:

p = Pattern::get_instance( "BoolPattern", 0 );

Therefore, all records with a positive value of the score function will be listed.

// Pattern / BoolPattern prototype
// Keep a list of the first N entries with the highest value of
// the score function

#include <math.h>
#include <algorithm>
#include <iterator>
#include <vector>

using namespace std;

typedef struct {
double jd_et;
double lon;
double lat; } t_horo;

const t_horo HORO_ZERO = {0.,0.,0.};

class PatternResultRecord {
public:
PatternResultRecord(const t_horo &h = HORO_ZERO, const double score = 0);
t_horo h;
double score;
bool operator<(const PatternResultRecord &b);
};

typedef vector<PatternResultRecord>::iterator t_result_iterator;

class Pattern {
public:
static Pattern* get_instance(char *type, size_t max_size = 10);
virtual double get_score( const t_horo &h );
virtual void apply( const t_horo &h );
void start_loop();
PatternResultRecord* get_next();
protected:
Pattern(size_t max_size);
size_t max_size;
vector<PatternResultRecord> list;
t_result_iterator gpos;
virtual bool applies( const PatternResultRecord &rec ) { return true; };
};

class BoolPattern : public Pattern {
public:
BoolPattern(size_t max_size) : Pattern(max_size) {};
virtual bool applies( const PatternResultRecord &rec );
};

Pattern* Pattern::get_instance(char * type, size_t max_size) {
if (strcmp(type,"BoolPattern") == 0)
return new BoolPattern(max_size);
else
return new Pattern(max_size);
};

PatternResultRecord::PatternResultRecord(const t_horo &h, const double score) {
this->h     = h;
this->score = score;
}

bool PatternResultRecord::operator<(const PatternResultRecord &b) {
return (this->score > b.score);
};

Pattern::Pattern(size_t max_size) {
this->max_size = max_size;
}

// Example function - will be extracted as C function pointer into the interface
// This allows to freely define arbitrary patterns in the calling environment,
// for example as VBA functions in Excel.
double Pattern::get_score(const t_horo &h) {
return sin( 143.576 * h.jd_et ); // for example
}

void Pattern::apply( const t_horo &h ) {
t_result_iterator pos;
PatternResultRecord lRecord(h,get_score(h));
if (applies(lRecord)) {
// Sorted insert
pos = lower_bound( list.begin( ),
list.end( ),
lRecord );
list.insert( pos, lRecord );
if ((max_size > 0) && (list.size() > max_size)) {
// Remove last element if max_size exceeded
list.resize( max_size );
}
}
}

bool BoolPattern::applies( const PatternResultRecord &rec ) {
return (rec.score > 0);
}

void Pattern::start_loop() {
gpos = list.begin();
}

PatternResultRecord* Pattern::get_next() {
t_result_iterator lpos = gpos;
gpos++;
if (lpos < list.end() )
// the * dereferences iterator to a PatternResultRecord object,
// the & then takes the address of this object
return &*lpos;
else
return NULL;
}

int main(int argc, char *argv[])
{
Pattern* p;
PatternResultRecord *rec;
t_horo h;

p = Pattern::get_instance( "BoolPattern", 0 );

// Apply pattern to some "horoscopes"
for (h.jd_et = 0; h.jd_et < 100; h.jd_et++) {
p->apply(h);
}

// Print result list
for (p->start_loop(); rec = p->get_next(); ) {
printf( "%10.3lf : %19.9lf\n", rec->h.jd_et, rec->score );
}

system("PAUSE");
return EXIT_SUCCESS;
}