yarrg/rssearch.c

   1 /**/
   2
   3 #include "rscommon.h"
   4
   5 DEBUG_DEFINE_DEBUGF(search);
   6 DEBUG_DEFINE_SOME_DEBUGF(filter,fildebugf);
   7
   8 typedef struct Neighbour {
   9   struct Neighbour *next;
  10   int islandid;
  11   int dist;
  12 } Neighbour;
  13
  14 static Neighbour **neighbours; /* neighbours[islandid]->islandid etc. */
  15 static sqlite3_stmt *ss_neigh;
  16
  17 static int ports[MAX_ROUTELEN];
  18
  19 static Neighbour *get_neighbours(int isle) {
  20   Neighbour **np= &neighbours[isle];
  21   Neighbour *head= *np;
  22   if (head) return head;
  23
  24   SQL_BIND(ss_neigh, 1, isle);
  25   while (SQL_STEP(ss_neigh)) {
  26     Neighbour *add= mmalloc(sizeof(*add));
  27     add->islandid= sqlite3_column_int(ss_neigh, 0);
  28     add->dist= sqlite3_column_int(ss_neigh, 1);
  29     add->next= head;
  30     head= add;
  31   }
  32   SQL_MUST( sqlite3_reset(ss_neigh) );
  33
  34   *np= head;
  35   return head;
  36 }
  37
  38
  39 static PotentialResult ***strat_base;
  40
  41
  42 static double process_route(int nports, int totaldist,
  43                             double overestimate_excepting_tail) {
  44   int i;
  45   int leagues_divisor= totaldist + nports;
  46
  47   ctr_routes_considered++;
  48
  49   debugf("========== ROUTE");
  50   for (i=0; i<nports; i++)
  51     debugf(" %d",ports[i]);
  52   debugf("\n");
  53
  54   int finalisle= ports[nports-1];
  55   int midisle= ports[nports/2];
  56
  57   PotentialResult **strat_fin= ONDEMAND(strat_base[finalisle], islandtablesz);
  58   PotentialResult *strat= ONDEMAND(strat_fin[midisle], 1);
  59
  60   if (nports>=2) {
  61     int pair[2], i;
  62     pair[1]= ports[nports-1];
  63     double guess_absolute= overestimate_excepting_tail;
  64
  65     for (i=0; i<nports; i++) {
  66       pair[0]= ports[i];
  67       IslandPair *ip= ipair_get_maybe(pair[0], pair[1]);
  68       if (!ip) continue;
  69       if (ip->route_tail_value < 0) {
  70         ctr_subroute_tails_valued++;
  71         ip->route_tail_value= value_route(2, pair, pair[0]!=pair[1]);
  72       }
  73       guess_absolute += ip->route_tail_value;
  74     }
  75     double guess_perleague= guess_absolute / leagues_divisor;
  76
  77     if (guess_absolute <= strat->absolute &&
  78         guess_perleague <= strat->perleague) {
  79       ctr_routes_eliminated++;
  80       debugf(" ELIM %f %f\n", guess_absolute, guess_perleague);
  81       return guess_absolute;
  82     }
  83     debugf(" COMPUTE %f %f\n", guess_absolute, guess_perleague);
  84   }
  85
  86   ctr_routes_valued++;
  87
  88   double absolute= value_route(nports, ports, 0);
  89   double perleague= absolute / leagues_divisor;
  90
  91   if (absolute <= strat->absolute &&
  92       perleague <= strat->perleague)
  93     return absolute;
  94
  95   debugf(" SOMEHOW BEST\n");
  96
  97   fildebugf("final %3d mid %3d ",finalisle,midisle);
  98
  99 #define CHK(absperl)                                                    \
 100   fildebugf(#absperl " %15f", absperl);                                 \
 101   if (absperl < strat->absperl) {                                       \
 102     debugf("   ");                                                      \
 103   } else {                                                              \
 104     strat->absperl= absperl;                                            \
 105     memcpy(strat->absperl##_ports, ports, sizeof(*ports) * nports);     \
 106     fildebugf("** ");                                                   \
 107   }
 108
 109   CHK(absolute)
 110   CHK(perleague)
 111
 112   fildebugf(" route");
 113
 114   for (i=0; i<nports; i++)
 115     fildebugf(" %d",ports[i]);
 116   fildebugf("\n");
 117
 118   return absolute;
 119 }
 120
 121 static void recurse(int last_isle,
 122                     int nports, /* excluding last_isle */
 123                     int totaldist /* including last_isle */,
 124                     double last_estimate) {
 125   ports[nports++]= last_isle;
 126   double estimate= process_route(nports, totaldist, last_estimate);
 127   if (nports >= MAX_ROUTELEN) return;
 128
 129   Neighbour *add;
 130   for (add= get_neighbours(last_isle); add; add=add->next) {
 131     int newdist= totaldist + add->dist;
 132     if (newdist > max_dist) continue;
 133
 134     recurse(add->islandid, nports, newdist, estimate);
 135   }
 136 }
 137
 138 void search(int start_isle, PotentialResult ****strat_base_io) {
 139   strat_base= ONDEMAND(*strat_base_io, islandtablesz);
 140   recurse(start_isle,0,0,1e6);
 141 }
 142
 143
 144 int narches;
 145 char **archnames;
 146 int *islandid2arch;
 147
 148 void setup_search(void) {
 149   neighbours= mcalloc(sizeof(*neighbours) * islandtablesz);
 150
 151   SQL_PREPARE(ss_neigh,
 152               "SELECT biid, dist FROM routes WHERE aiid=?");
 153
 154   int max_narches=
 155     sql_single_int(" SELECT count(*) FROM (\n"
 156                    "  SELECT DISTINCT archipelago\n"
 157                    "   FROM islands\n"
 158                    "  )");
 159   archnames= mcalloc(sizeof(*archnames) * max_narches);
 160   islandid2arch= mmalloc(sizeof(*islandid2arch) * islandtablesz);
 161   int i;
 162   for (i=0; i<islandtablesz; i++) islandid2arch[i]=-1;
 163
 164   sqlite3_stmt *archs;
 165   SQL_PREPARE(archs,
 166               " SELECT islandid, archipelago\n"
 167               "  FROM islands\n"
 168               "  ORDER BY archipelago");
 169   while (SQL_STEP(archs)) {
 170     int isle= sqlite3_column_int(archs,0);
 171     const char *archname= (const char*)sqlite3_column_text(archs,1);
 172     int arch;
 173     for (arch=0; arch<narches; arch++)
 174       if (!strcmp(archnames[arch], archname)) goto found;
 175     assert(narches < max_narches);
 176     arch= narches++;
 177     archnames[arch]= masprintf("%s",archname);
 178   found:
 179     islandid2arch[isle]= arch;
 180   }
 181   sqlite3_finalize(archs);
 182 }