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 bestsofar;
  36
  37 static void process_route(int nports) {
  38   double value= value_route(nports, ports);
  39   if (value < bestsofar) return;
  40
  41   fprintf(stderr,"value %20f route", value);
  42   int i;
  43   for (i=0; i<nports; i++)
  44     fprintf(stderr," %d",ports[i]);
  45   putc('\n',stderr);
  46
  47   bestsofar= value;
  48 }
  49
  50 static void recurse(int last_isle,
  51                     int nports, /* excluding last_isle */
  52                     int totaldist /* including last_isle */) {
  53   ports[nports++]= last_isle;
  54   process_route(nports);
  55   if (nports >= MAX_ROUTELEN) return;
  56
  57   Neighbour *add;
  58   for (add= get_neighbours(last_isle); add; add=add->next) {
  59     int newdist= totaldist + add->dist;
  60     if (newdist > max_dist) continue;
  61
  62     recurse(add->islandid, nports, newdist);
  63   }
  64 }
  65
  66 void search(int start_isle) {
  67   recurse(start_isle,0,0);
  68 }
  69
  70 void setup_search(void) {
  71   neighbours= mcalloc(sizeof(*neighbours) * islandtablesz);
  72
  73   SQL_PREPARE(ss_neigh,
  74               "SELECT biid, dist FROM routes WHERE aiid=?");
  75 }