chiark / gitweb /
d5a97a488604fb74db3f5c6ceaa7c686ef2613ed
[ypp-sc-tools.web-live.git] / yarrg / rssearch.c
1 /**/
2
3 #include "rscommon.h"
4
5 DEBUG_DEFINE_DEBUGF(search);
6
7 typedef struct Neighbour {
8   struct Neighbour *next;
9   int islandid;
10   int dist;
11 } Neighbour;
12
13 static Neighbour **neighbours; /* neighbours[islandid]->islandid etc. */
14 static sqlite3_stmt *ss_neigh;
15
16 static int ports[MAX_ROUTELEN];
17
18 static Neighbour *get_neighbours(int isle) {
19   Neighbour **np= &neighbours[isle];
20   Neighbour *head= *np;
21   if (head) return head;
22
23   SQL_BIND(ss_neigh, 1, isle);
24   while (SQL_STEP(ss_neigh)) {
25     Neighbour *add= mmalloc(sizeof(*add));
26     add->islandid= sqlite3_column_int(ss_neigh, 0);
27     add->dist= sqlite3_column_int(ss_neigh, 1);
28     add->next= head;
29     head= add;
30   }
31   SQL_MUST( sqlite3_reset(ss_neigh) );
32
33   *np= head;
34   return head;
35 }
36
37 static double best_absolute, best_perleague;
38
39 static double process_route(int nports, int totaldist,
40                             double overestimate_excepting_tail) {
41   int i;
42   int leagues_divisor= totaldist + nports;
43
44   debugf("========== ROUTE");
45   for (i=0; i<nports; i++)
46     debugf(" %d",ports[i]);
47   debugf("\n");
48
49   if (nports>=2) {
50     int pair[2], i;
51     pair[1]= ports[nports-1];
52     double guess_absolute= overestimate_excepting_tail;
53     
54     for (i=0; i<nports; i++) {
55       pair[0]= ports[i];
56       IslandPair *ip= ipair_get_maybe(pair[0], pair[1]);
57       if (!ip) continue;
58       if (ip->route_tail_value < 0)
59         ip->route_tail_value= value_route(2, pair, pair[0]!=pair[1]);
60       guess_absolute += ip->route_tail_value;
61     }
62     double guess_perleague= guess_absolute / leagues_divisor;
63
64     if (guess_absolute <= best_absolute && guess_perleague <= best_perleague) {
65       debugf(" ELIM %f %f\n", guess_absolute, guess_perleague);
66       return guess_absolute;
67     }
68     debugf(" COMPUTE %f %f\n", guess_absolute, guess_perleague);
69   }
70
71   double absolute= value_route(nports, ports, 0);
72   double perleague= absolute / leagues_divisor;
73
74   if (absolute <= best_absolute && perleague <= best_perleague)
75     return absolute;
76
77   debugf(" SOMEHOW BEST\n");
78
79 #define CHK(absperl)                                    \
80   fprintf(stderr,#absperl " %15f", absperl);            \
81   if (absperl < best_##absperl) fputs("   ",stderr);    \
82   else { best_##absperl= absperl; fputs("** ",stderr); }
83
84   CHK(absolute)
85   CHK(perleague)
86
87   fputs(" route",stderr);
88
89   for (i=0; i<nports; i++)
90     fprintf(stderr," %d",ports[i]);
91   putc('\n',stderr);
92
93   return absolute;
94 }
95
96 static void recurse(int last_isle,
97                     int nports, /* excluding last_isle */
98                     int totaldist /* including last_isle */,
99                     double last_estimate) {
100   ports[nports++]= last_isle;
101   double estimate= process_route(nports, totaldist, last_estimate);
102   if (nports >= MAX_ROUTELEN) return;
103
104   Neighbour *add;
105   for (add= get_neighbours(last_isle); add; add=add->next) {
106     int newdist= totaldist + add->dist;
107     if (newdist > max_dist) continue;
108
109     recurse(add->islandid, nports, newdist, estimate);
110   }
111 }
112
113 void search(int start_isle) {
114   recurse(start_isle,0,0,1e6);
115 }
116
117 void setup_search(void) {
118   neighbours= mcalloc(sizeof(*neighbours) * islandtablesz);
119
120   SQL_PREPARE(ss_neigh,
121               "SELECT biid, dist FROM routes WHERE aiid=?");
122 }