chiark / gitweb /
c2cab435f07e09f2ef17934d2b8ba2964e4d0cca
[ypp-sc-tools.db-live.git] / yarrg / rsvalue.c
1 /**/
2
3 #include "rscommon.h"
4
5 DEBUG_DEFINE_DEBUGF(value);
6
7 typedef struct {
8   int commodid, src_price, src_qty, dst_price, dst_qty;
9 } Trade;
10
11 #define TRADES_PER_BLOCK 10
12
13 typedef struct TradesBlock{
14   struct TradesBlock *next;
15   Trade t[TRADES_PER_BLOCK];
16 } TradesBlock;
17
18 typedef struct {
19   int ntrades;
20   TradesBlock *trades;
21 } IslandPair;
22
23 int nislands;
24 IslandPair ***ipairs; /* ipairs[sislandid][dislandid] */
25
26 static IslandPair *ipair_get(int si, int di) {
27   IslandPair *ip, **ipa;
28
29   assert(si < nislands);
30   assert(di < nislands);
31
32   if (!(ipa= ipairs[si])) {
33     ipa= ipairs[si]= mcalloc(sizeof(*ipa) * nislands);
34   }
35   if ((ip= ipa[di]))
36     return ip;
37   
38   ipa[di]= ip= mmalloc(sizeof(*ip));
39   ip->ntrades= 0;
40   ip->trades= 0;
41   int inblock= TRADES_PER_BLOCK;
42   TradesBlock *block= 0;
43
44   debugf("VALUE ipair_get(%d,%d) running...\n", si,di);
45   SQL_MUST( sqlite3_bind_int(ss_ipair, 1, si) );
46   SQL_MUST( sqlite3_bind_int(ss_ipair, 2, di) );
47
48   while (SQL_STEP(ss_ipair)) {
49     if (inblock == TRADES_PER_BLOCK) {
50       block= mmalloc(sizeof(*block));
51       block->next= ip->trades;
52       ip->trades= block;
53       inblock= 0;
54     }
55     int *irp, i;
56     for (i=0, irp=&block->t[inblock].commodid; i<5; i++, irp++)
57       *irp= sqlite3_column_int(ss_ipair, i);
58     ip->ntrades++;
59     inblock++;
60   }
61   if (inblock < TRADES_PER_BLOCK)
62     block->t[inblock].commodid= -1;
63
64   sqlite3_reset(ss_ipair);
65   
66   return ip;
67 }
68
69 void value_route(int nislands, const int *islands) {
70   int s,d;
71
72   /* We need to construct the LP problem.  GLPK talks
73    * about rows and columns, which are numbered from 1.
74    *
75    * Each column is a `structural variable' ie one of the entries in
76    * the objective function.  In our case the set of structural
77    * variable is, for each visit, the set of Trades which collect at
78    * that island.  (We use `visit' to mean `specific visit to an
79    * island' so if an island appears more than once so do its trades.)
80    * We don't need to worry about crossing with all the possible
81    * delivery locations as we always deliver on the first visit.
82    * We will call such a structural variable a Flow, for brevity.
83    *
84    * We iterate over the possible Flows adding them as columns as we
85    * go, and also adding their entries to the various constraints.
86    *
87    * Each row is an `auxiliary variable' ie one of the constraints.
88    * We have two kinds of constraint:
89    *   - mass/volume/capital: one constraint for each sailed leg
90    *       (unless relevant constraint is not satisfied)
91    *   - quantity of commodity available for collection
92    *       or delivery at particular price and island
93    * The former are numbered predictably: we have first all the mass
94    * limits, then all the volume limits, then all the capital limits
95    * (as applicable) - one for each leg, ie one for each entry
96    * in islands except the first.
97    *
98    * The latter are added as needed and the row numbers are stored in
99    * a data structure for later reuse.
100    */
101
102   for (s=0; s<nislands; s++) {
103     int si= islands[s];
104     for (d=s; d<nislands; d++) {
105       int di= islands[d];
106       int already_d;
107       for (already_d=s+1; already_d<d; already_d++)
108         if (islands[already_d] == di)
109           /* visited this island already since we left s */
110           goto next_d;
111       if (d>s && di==si)
112         /* route has returned to s, no need to think more about this */
113         goto next_d;
114       
115       IslandPair *ip= ipair_get(islands[s], islands[d]);
116       TradesBlock *block= ip->trades;
117       int ntrades= ip->ntrades;
118       int inblock= 0;
119       while (ntrades-- >0) {
120         if (inblock >= TRADES_PER_BLOCK) {
121           block= block->next;
122           inblock= 0;
123         }
124         Trade *t= &block->t[inblock++];
125
126         debugf("  TRADE %d#%d..%d#%d %d %d-%d\n",
127                si,s, di,d, t->commodid, t->src_price, t->dst_price);
128         
129       }
130     }
131     next_d:;
132   }
133 }
134
135 void setup_value(void) {
136   sqlite3_stmt *sst;
137
138   SQL_MUST( sqlite3_prepare(db, "SELECT max(islandid) FROM islands",
139                             -1,&sst,0) );
140   assert( SQL_STEP(sst) );
141   nislands= sqlite3_column_int(sst,0);
142   nislands++;
143   sqlite3_finalize(sst);
144   debugf("VALUE nislands=%d\n",nislands);
145
146   SQL_MUST( sqlite3_prepare(db,
147      "SELECT\n"
148      " sell.commodid            commodid,\n"
149      " sell.price               src_price,\n"
150      " sum(sell.qty)            src_qty,\n"
151      " buy.price                dst_price,\n"
152      " sum(buy.qty)             dst_qty\n"
153      " FROM sell JOIN buy\n"
154      "   ON sell.commodid = buy.commodid\n"
155      "  AND buy.price > sell.price\n"
156      " WHERE sell.islandid=?\n"
157      "   AND buy.islandid=?\n"
158      " GROUP BY sell.commodid, sell.price, buy.price",
159                             -1, &ss_ipair, 0) );
160
161   ipairs= mcalloc(sizeof(*ipairs) * nislands);
162 }