yarrg/rssearch.c

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