yarrg/rssearch.c

   1 /**/
   2
   3 #include "rscommon.h"
   4
   5 DEBUG_DEFINE_DEBUGF(search);
   6
   7 typedef struct Neighbour {
   8   struct Neighbour *next;
   9   int islandid;
  10   int dist;
  11 } Neighbour;
  12
  13 static Neighbour **neighbours; /* neighbours[islandid]->islandid etc. */
  14 static sqlite3_stmt *ss_neigh;
  15
  16 static int ports[MAX_ROUTELEN];
  17
  18 static Neighbour *get_neighbours(int isle) {
  19   Neighbour **np= &neighbours[isle];
  20   Neighbour *head= *np;
  21   if (head) return head;
  22
  23   SQL_BIND(ss_neigh, 1, isle);
  24   while (SQL_STEP(ss_neigh)) {
  25     Neighbour *add= mmalloc(sizeof(*add));
  26     add->islandid= sqlite3_column_int(ss_neigh, 0);
  27     add->dist= sqlite3_column_int(ss_neigh, 1);
  28     add->next= head;
  29     head= add;
  30   }
  31   SQL_MUST( sqlite3_reset(ss_neigh) );
  32
  33   *np= head;
  34   return head;
  35 }
  36
  37 static double best_absolute, best_perleague;
  38
  39 static void process_route(int nports, int totaldist) {
  40   int i;
  41
  42   debugf("========== ROUTE");
  43   for (i=0; i<nports; i++)
  44     debugf(" %d",ports[i]);
  45   debugf("\n");
  46
  47   double absolute= value_route(nports, ports);
  48   double perleague= absolute / (totaldist + nports);
  49
  50   if (absolute < best_absolute && perleague < best_perleague) return;
  51
  52 #define CHK(absperl)                                    \
  53   fprintf(stderr,#absperl " %15f", absperl);            \
  54   if (absperl < best_##absperl) fputs("   ",stderr);    \
  55   else { best_##absperl= absperl; fputs("** ",stderr); }
  56
  57   CHK(absolute)
  58   CHK(perleague)
  59
  60   fputs(" route",stderr);
  61
  62   for (i=0; i<nports; i++)
  63     fprintf(stderr," %d",ports[i]);
  64   putc('\n',stderr);
  65 }
  66
  67 static void recurse(int last_isle,
  68                     int nports, /* excluding last_isle */
  69                     int totaldist /* including last_isle */) {
  70   ports[nports++]= last_isle;
  71   process_route(nports, totaldist);
  72   if (nports >= MAX_ROUTELEN) return;
  73
  74   Neighbour *add;
  75   for (add= get_neighbours(last_isle); add; add=add->next) {
  76     int newdist= totaldist + add->dist;
  77     if (newdist > max_dist) continue;
  78
  79     recurse(add->islandid, nports, newdist);
  80   }
  81 }
  82
  83 void search(int start_isle) {
  84   recurse(start_isle,0,0);
  85 }
  86
  87 void setup_search(void) {
  88   neighbours= mcalloc(sizeof(*neighbours) * islandtablesz);
  89
  90   SQL_PREPARE(ss_neigh,
  91               "SELECT biid, dist FROM routes WHERE aiid=?");
  92 }