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