#include "rscommon.h"
-static void ipair_gettrades(int si, int di) {
- char *stmt= masprintf
- ("SELECT\n"
- " sell.price src_price,\n"
- " sum(sell.qty) src_qty,\n"
- " buy.price dst_price,\n"
- " sum(buy.qty) dst_qty,\n"
- " commods.commodid commodid,\n"
- " commods.unitmass unitmass,\n"
- " commods.unitvolume unitvolume\n"
- " FROM commods\n"
- " JOIN sell ON commods.commodid = sell.commodid\n"
- " JOIN buy ON commods.commodid = buy.commodid\n"
- " WHERE buy.price > sell.price\n"
- " AND sell.islandid=%d\n"
- " AND buy.islandid=%d\n"
- " GROUP BY commods.commodid, sell.price, buy.price\n",
- si, di);
+DEBUG_DEFINE_DEBUGF(value);
+
+typedef struct {
+ int commodid, src_price, src_qty, dst_price, dst_qty;
+} Trade;
+
+#define TRADES_PER_BLOCK 10
+
+typedef struct TradesBlock{
+ struct TradesBlock *next;
+ Trade t[TRADES_PER_BLOCK];
+} TradesBlock;
+
+typedef struct {
+ int ntrades;
+ TradesBlock *trades;
+} IslandPair;
+
+int nislands;
+IslandPair ***ipairs; /* ipairs[sislandid][dislandid] */
+
+static IslandPair *ipair_get(int si, int di) {
+ IslandPair *ip, **ipa;
+
+ assert(si < nislands);
+ assert(di < nislands);
+
+ if (!(ipa= ipairs[si])) {
+ ipa= ipairs[si]= mcalloc(sizeof(*ipa) * nislands);
+ }
+ if ((ip= ipa[di]))
+ return ip;
- printf("SQL\n[\n%s\n]\n", stmt);
+ ipa[di]= ip= mmalloc(sizeof(*ip));
+ ip->ntrades= 0;
+ ip->trades= 0;
+ int inblock= TRADES_PER_BLOCK;
+ TradesBlock *block= 0;
+
+ debugf("VALUE ipair_get(%d,%d) running...\n", si,di);
+ SQL_MUST( sqlite3_bind_int(ss_ipair, 1, si) );
+ SQL_MUST( sqlite3_bind_int(ss_ipair, 2, di) );
+
+ while (SQL_STEP(ss_ipair)) {
+ if (inblock == TRADES_PER_BLOCK) {
+ block= mmalloc(sizeof(*block));
+ block->next= ip->trades;
+ ip->trades= block;
+ inblock= 0;
+ }
+ int *irp, i;
+ for (i=0, irp=&block->t[inblock].commodid; i<5; i++, irp++)
+ *irp= sqlite3_column_int(ss_ipair, i);
+ ip->ntrades++;
+ inblock++;
+ }
+ if (inblock < TRADES_PER_BLOCK)
+ block->t[inblock].commodid= -1;
- free(stmt);
+ sqlite3_reset(ss_ipair);
+
+ return ip;
}
void value_route(int nislands, const int *islands) {
int s,d;
-
+
+ /* We need to construct the LP problem. GLPK talks
+ * about rows and columns, which are numbered from 1.
+ *
+ * Each column is a `structural variable' ie one of the entries in
+ * the objective function. In our case the set of structural
+ * variable is, for each visit, the set of Trades which collect at
+ * that island. (We use `visit' to mean `specific visit to an
+ * island' so if an island appears more than once so do its trades.)
+ * We don't need to worry about crossing with all the possible
+ * delivery locations as we always deliver on the first visit.
+ * We will call such a structural variable a Flow, for brevity.
+ *
+ * We iterate over the possible Flows adding them as columns as we
+ * go, and also adding their entries to the various constraints.
+ *
+ * Each row is an `auxiliary variable' ie one of the constraints.
+ * We have two kinds of constraint:
+ * - mass/volume/capital: one constraint for each sailed leg
+ * (unless relevant constraint is not satisfied)
+ * - quantity of commodity available for collection
+ * or delivery at particular price and island
+ * The former are numbered predictably: we have first all the mass
+ * limits, then all the volume limits, then all the capital limits
+ * (as applicable) - one for each leg, ie one for each entry
+ * in islands except the first.
+ *
+ * The latter are added as needed and the row numbers are stored in
+ * a data structure for later reuse.
+ */
+
for (s=0; s<nislands; s++) {
+ int si= islands[s];
for (d=s; d<nislands; d++) {
- ipair_gettrades(islands[s], islands[d]);
+ int di= islands[d];
+ int already_d;
+ for (already_d=s+1; already_d<d; already_d++)
+ if (islands[already_d] == di)
+ /* visited this island already since we left s */
+ goto next_d;
+ if (d>s && di==si)
+ /* route has returned to s, no need to think more about this */
+ goto next_d;
+
+ IslandPair *ip= ipair_get(islands[s], islands[d]);
+ TradesBlock *block= ip->trades;
+ int ntrades= ip->ntrades;
+ int inblock= 0;
+ while (ntrades-- >0) {
+ if (inblock >= TRADES_PER_BLOCK) {
+ block= block->next;
+ inblock= 0;
+ }
+ Trade *t= &block->t[inblock++];
+
+ debugf(" TRADE %d#%d..%d#%d %d %d-%d\n",
+ si,s, di,d, t->commodid, t->src_price, t->dst_price);
+
+ }
}
+ next_d:;
}
+}
+
+void setup_value(void) {
+ sqlite3_stmt *sst;
+
+ SQL_MUST( sqlite3_prepare(db, "SELECT max(islandid) FROM islands",
+ -1,&sst,0) );
+ assert( SQL_STEP(sst) );
+ nislands= sqlite3_column_int(sst,0);
+ nislands++;
+ sqlite3_finalize(sst);
+ debugf("VALUE nislands=%d\n",nislands);
+
+ SQL_MUST( sqlite3_prepare(db,
+ "SELECT\n"
+ " sell.commodid commodid,\n"
+ " sell.price src_price,\n"
+ " sum(sell.qty) src_qty,\n"
+ " buy.price dst_price,\n"
+ " sum(buy.qty) dst_qty\n"
+ " FROM sell JOIN buy\n"
+ " ON sell.commodid = buy.commodid\n"
+ " AND buy.price > sell.price\n"
+ " WHERE sell.islandid=?\n"
+ " AND buy.islandid=?\n"
+ " GROUP BY sell.commodid, sell.price, buy.price",
+ -1, &ss_ipair, 0) );
- //char *tail;
- //struct sqlite_vm *sth;
- //r= sqlite_compile(db, stmt, &tail, &sth,
+ ipairs= mcalloc(sizeof(*ipairs) * nislands);
}