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 static int final_isle;
  19
  20 static Neighbour *get_neighbours(int isle) {
  21   Neighbour **np= &neighbours[isle];
  22   Neighbour *head= *np;
  23   if (head) return head;
  24
  25   SQL_BIND(ss_neigh, 1, isle);
  26   while (SQL_STEP(ss_neigh)) {
  27     Neighbour *add;
  28     NEW(add);
  29     add->islandid= sqlite3_column_int(ss_neigh, 0);
  30     add->dist= sqlite3_column_int(ss_neigh, 1);
  31     add->next= head;
  32     head= add;
  33   }
  34   SQL_MUST( sqlite3_reset(ss_neigh) );
  35
  36   *np= head;
  37   return head;
  38 }
  39
  40
  41 static Bucket ***buckets_base[GRANUS];
  42
  43
  44 static double process_route(int nports, int totaldist,
  45                             double overestimate_excepting_tail) {
  46   int i, ap, granui;
  47   int leagues_divisor= totaldist + nports;
  48
  49   ctr_routes_considered++;
  50
  51   int wrong_final= final_isle && ports[nports-1] != final_isle;
  52
  53   debugf("========== ROUTE");
  54   for (i=0; i<nports; i++)
  55     debugf(" %d",ports[i]);
  56   debugf("\n");
  57
  58   double guess[AP]={0,0};
  59   if (nports>=2) {
  60     int pair[2], i;
  61     pair[1]= ports[nports-1];
  62     guess[A]= overestimate_excepting_tail;
  63
  64     for (i=0; i<nports; i++) {
  65       pair[0]= ports[i];
  66       IslandPair *ip= ipair_get_maybe(pair[0], pair[1]);
  67       if (!ip) continue;
  68       if (ip->route_tail_value < 0) {
  69         ctr_subroute_tails_valued++;
  70         ip->route_tail_value= value_route(2, pair, pair[0]!=pair[1]);
  71       }
  72       guess[A] += ip->route_tail_value;
  73     }
  74     guess[P]= guess[A] / leagues_divisor;
  75
  76     if (wrong_final) {
  77       ctr_routes_wrongfinalelim++;
  78       debugf(" WFELIM\n");
  79       return guess[A];
  80     }
  81
  82     for (granui=0; granui<granus; granui++) {
  83       if (guess[A] > highscores[granui][A][0].value ||
  84           guess[P] > highscores[granui][P][0].value)
  85         goto not_quickelim;
  86     }
  87     ctr_routes_quickelim++;
  88     debugf(" QELIM %f %f\n", guess[A], guess[P]);
  89     return guess[A];
  90   not_quickelim:;
  91   }
  92
  93   int finisle= ports[nports-1];
  94   int finarch= isle2arch(finisle);
  95
  96   int midisle= ports[nports/2];
  97   int midarch= route2midarch(ports,nports);
  98
  99   Bucket *buckets[GRANUS];
 100   for (granui=0; granui<granus; granui++) {
 101     Bucket **buckets_fin;
 102     int mid, fin;
 103     switch (granui) {
 104     case 0: fin=finarch; mid=midarch; break;
 105     case 1: fin=finisle; mid=midarch; break;
 106     case 2: fin=finisle; mid=midisle; break;
 107     default: abort();
 108     }
 109     buckets_fin= ONDEMAND(buckets_base[granui][fin], granusz_mid[granui]);
 110     buckets[granui]= ONDEMAND(buckets_fin[mid], 1);
 111   }
 112
 113   if (nports>=2) {
 114     for (granui=0; granui<granus; granui++)
 115       for (ap=0; ap<AP; ap++)
 116         if (guess[ap] > buckets[granui]->prs[ap].value[ap] &&
 117             guess[ap] > highscores[granui][ap][0].value)
 118           goto not_bucketelim;
 119     ctr_routes_bucketelim++;
 120     debugf(" ELIM %f %f\n", guess[A], guess[P]);
 121     return guess[A];
 122   not_bucketelim:
 123     debugf(" COMPUTE %f %f\n", guess[A], guess[P]);
 124   }
 125
 126   ctr_routes_valued++;
 127
 128   double value[AP];
 129   value[A]= value_route(nports, ports, 0);
 130   value[P]= value[A] / leagues_divisor;
 131
 132   if (wrong_final) {
 133     ctr_routes_wrongfinal++;
 134     return value[0];
 135   }
 136
 137   for (granui=granus-1; granui>=0; granui--) {
 138     Bucket *bucket= buckets[granui];
 139
 140     if (value[A] <= bucket->prs[A].value[A] &&
 141         value[P] <= bucket->prs[P].value[P])
 142       continue;
 143
 144     debugf(" SOMEHOW %d BEST\n",granui);
 145
 146     fildebugf("granu %d f%d:%3d mid%d:%3d ",granui,
 147               finarch,finisle,midarch,midisle);
 148
 149     for (ap=0; ap<AP; ap++) {
 150       HighScoreEntry *scores= highscores[granui][ap];
 151       int nscores= nhighscores[granui][ap];
 152
 153       fildebugf("ap=%d %15f", ap, value[ap]);
 154       if (value[ap] < bucket->prs[ap].value[ap]) {
 155         debugf("      ");
 156       } else {
 157         int pos;
 158         ctr_newbests_granu[granui*AP+ap]++;
 159         bucket->prs[ap].length= totaldist;
 160         memcpy(bucket->prs[ap].value, value, sizeof(value));
 161         memcpy(bucket->prs[ap].ports, ports, sizeof(*ports) * nports);
 162         if (nports < MAX_ROUTELEN-1) bucket->prs[ap].ports[nports]= -1;
 163         fildebugf("** ");
 164         for (pos=0; pos < nscores; pos++)
 165           if (scores[pos].bucket == bucket) goto found;
 166         /* not found */
 167         pos= -1;
 168       found:
 169         for (;;) {
 170           pos++;
 171           if (pos >= nscores) break; /* new top */
 172           if (scores[pos].value >= value[ap]) break; /* found spot */
 173           if (pos>0)
 174             scores[pos-1]= scores[pos];
 175         }
 176         pos--;
 177         if (pos>0) {
 178           scores[pos].value= value[ap];
 179           scores[pos].bucket= bucket;
 180           if (granui < granus-1 &&
 181               highscores[granui][A][0].bucket &&
 182               highscores[granui][P][0].bucket) {
 183             /* both absolute and perleague are full at this granularity,
 184              * so we don't care about anything more granular */
 185             fildebugf("\n                STOP-GRANU            ");
 186             granus= granui+1;
 187           }
 188         }
 189         fildebugf("@%2d/%2d ", pos, nscores);
 190       } /* new best */
 191     } /* ap */
 192   } /* granui */
 193
 194   fildebugf(" route");
 195
 196   for (i=0; i<nports; i++)
 197     fildebugf(" %d",ports[i]);
 198   fildebugf("\n");
 199
 200   return value[0];
 201 }
 202
 203 static void recurse(int last_isle,
 204                     int nports /* excluding last_isle */,
 205                     int totaldist /* including last_isle */,
 206                     double last_estimate) {
 207   ports[nports++]= last_isle;
 208   double estimate= process_route(nports, totaldist, last_estimate);
 209   if (nports >= MAX_ROUTELEN) return;
 210
 211   Neighbour *add;
 212   for (add= get_neighbours(last_isle); add; add=add->next) {
 213     int newdist= totaldist + add->dist;
 214     if (newdist > max_dist) continue;
 215
 216     recurse(add->islandid, nports, newdist, estimate);
 217   }
 218 }
 219
 220 void search(int start_isle, int final_isle_spec,
 221             Bucket ****buckets_base_io[GRANUS]) {
 222   int granui;
 223   for (granui=0; granui<GRANUS; granui++)
 224     buckets_base[granui]=
 225       ONDEMAND(*buckets_base_io[granui], granusz_fin[granui]);
 226
 227   final_isle= final_isle_spec <= 0 ? 0 : final_isle_spec;
 228   recurse(start_isle,0,0,1e6);
 229 }
 230
 231 int nhighscores[GRANUS][AP];
 232 HighScoreEntry *highscores[GRANUS][AP];
 233 int granus=GRANUS, granusz_fin[GRANUS], granusz_mid[GRANUS];
 234
 235 int narches;
 236 char **archnames;
 237 int *islandid2arch;
 238
 239 void setup_search(void) {
 240   MCALLOC(neighbours, islandtablesz);
 241
 242   SQL_PREPARE(ss_neigh,
 243               "SELECT biid, dist FROM routes WHERE aiid=?");
 244
 245   int max_narches=
 246     sql_single_int(" SELECT count(*) FROM (\n"
 247                    "  SELECT DISTINCT archipelago\n"
 248                    "   FROM islands\n"
 249                    "  )");
 250   MCALLOC(archnames, max_narches);
 251   MCALLOC_INITEACH(islandid2arch, islandtablesz, *this=-1);
 252
 253   sqlite3_stmt *archs;
 254   SQL_PREPARE(archs,
 255               " SELECT islandid, archipelago\n"
 256               "  FROM islands\n"
 257               "  ORDER BY archipelago");
 258   while (SQL_STEP(archs)) {
 259     int isle= sqlite3_column_int(archs,0);
 260     const char *archname= (const char*)sqlite3_column_text(archs,1);
 261     int arch;
 262     for (arch=0; arch<narches; arch++)
 263       if (!strcmp(archnames[arch], archname)) goto found;
 264     assert(narches < max_narches);
 265     arch= narches++;
 266     archnames[arch]= masprintf("%s",archname);
 267   found:
 268     islandid2arch[isle]= arch;
 269   }
 270   sqlite3_finalize(archs);
 271
 272   granusz_fin[0]=                granusz_mid[0]= narches;
 273   granusz_fin[1]= islandtablesz; granusz_mid[1]= narches;
 274   granusz_fin[2]=                granusz_mid[2]= islandtablesz;
 275 }