Merge branch 'master' into stable-5.x

[ypp-sc-tools.db-live.git] / yarrg / rssearch.c

diff --git a/yarrg/rssearch.c b/yarrg/rssearch.c
index 9676640aafc9e3a28a14b2374660d777e5806c55..1dd29e5bfa2dc23293b640b41a44186851f96b3f 100644 (file)
--- a/yarrg/rssearch.c
+++ b/yarrg/rssearch.c
@@ -38,12 +38,12 @@ static Neighbour *get_neighbours(int isle) {
 }
 
 
 }
 
 

-static PotentialResult ***buckets_base[GRANUS];
+static Bucket ***buckets_base[GRANUS];

 
 
 static double process_route(int nports, int totaldist,
                            double overestimate_excepting_tail) {
 
 
 static double process_route(int nports, int totaldist,
                            double overestimate_excepting_tail) {

-  int i, ap;
+  int i, ap, granui;

   int leagues_divisor= totaldist + nports;
 
   ctr_routes_considered++;
   int leagues_divisor= totaldist + nports;
 
   ctr_routes_considered++;


@@ -79,12 +79,15 @@ static double process_route(int nports, int totaldist,
       return guess[A];
     }
 
       return guess[A];
     }
 

-    if (guess[A] <= highscores[GRANUS-1][A][0].value &&
-       guess[P] <= highscores[GRANUS-1][P][0].value) {
-      ctr_routes_quickelim++;
-      debugf(" QELIM %f %f\n", guess[A], guess[P]);
-      return guess[A];
+    for (granui=0; granui<granus; granui++) {
+      if (guess[A] > highscores[granui][A][0].value ||
+         guess[P] > highscores[granui][P][0].value)
+       goto not_quickelim;

     }
     }

+    ctr_routes_quickelim++;
+    debugf(" QELIM %f %f\n", guess[A], guess[P]);
+    return guess[A];
+  not_quickelim:;

   }
 
   int finisle= ports[nports-1];
   }
 
   int finisle= ports[nports-1];


@@ -93,10 +96,9 @@ static double process_route(int nports, int totaldist,
   int midisle= ports[nports/2];
   int midarch= route2midarch(ports,nports);
 
   int midisle= ports[nports/2];
   int midarch= route2midarch(ports,nports);
 

-  PotentialResult *buckets[GRANUS];
-  int granui;
+  Bucket *buckets[GRANUS];

   for (granui=0; granui<granus; granui++) {
   for (granui=0; granui<granus; granui++) {

-    PotentialResult **buckets_fin;
+    Bucket **buckets_fin;

     int mid, fin;
     switch (granui) {
     case 0: fin=finarch; mid=midarch; break;
     int mid, fin;
     switch (granui) {
     case 0: fin=finarch; mid=midarch; break;


@@ -109,12 +111,15 @@ static double process_route(int nports, int totaldist,
   }
 
   if (nports>=2) {
   }
 
   if (nports>=2) {

-    if (guess[A] <= buckets[0]->value[A] &&
-       guess[P] <= buckets[0]->value[P]) {
-      ctr_routes_bucketelim++;
-      debugf(" ELIM %f %f\n", guess[A], guess[P]);
-      return guess[A];
-    }
+    for (granui=0; granui<granus; granui++)
+      for (ap=0; ap<AP; ap++)
+       if (guess[ap] > buckets[granui]->prs[ap].value[ap] &&
+           guess[ap] > highscores[granui][ap][0].value)
+         goto not_bucketelim;
+    ctr_routes_bucketelim++;
+    debugf(" ELIM %f %f\n", guess[A], guess[P]);
+    return guess[A];
+  not_bucketelim:

     debugf(" COMPUTE %f %f\n", guess[A], guess[P]);
   }
 
     debugf(" COMPUTE %f %f\n", guess[A], guess[P]);
   }
 


@@ -130,38 +135,40 @@ static double process_route(int nports, int totaldist,
   }
 
   for (granui=granus-1; granui>=0; granui--) {
   }
 
   for (granui=granus-1; granui>=0; granui--) {

-    PotentialResult *bucket= buckets[granui];
+    Bucket *bucket= buckets[granui];

 
 

-    if (value[A] <= bucket->value[A] &&
-       value[P] <= bucket->value[P])
+    if (value[A] <= bucket->prs[A].value[A] &&
+       value[P] <= bucket->prs[P].value[P])

       continue;
 
     debugf(" SOMEHOW %d BEST\n",granui);
 
       continue;
 
     debugf(" SOMEHOW %d BEST\n",granui);
 

-    fildebugf("final %d:%3d mid %d ",finarch,finisle,midarch);
+    fildebugf("granu %d f%d:%3d mid%d:%3d ",granui,
+             finarch,finisle,midarch,midisle);

 
     for (ap=0; ap<AP; ap++) {
       HighScoreEntry *scores= highscores[granui][ap];
 
     for (ap=0; ap<AP; ap++) {
       HighScoreEntry *scores= highscores[granui][ap];

-      int *nscores= &nhighscores[granui][ap];
+      int nscores= nhighscores[granui][ap];

 
       fildebugf("ap=%d %15f", ap, value[ap]);
 
       fildebugf("ap=%d %15f", ap, value[ap]);

-      if (value[ap] < bucket->value[ap]) {
+      if (value[ap] < bucket->prs[ap].value[ap]) {

        debugf("      ");
       } else {
        int pos;
        ctr_newbests_granu[granui*AP+ap]++;
        debugf("      ");
       } else {
        int pos;
        ctr_newbests_granu[granui*AP+ap]++;

-       bucket->value[ap]= value[ap];
-       memcpy(bucket->ports[ap], ports, sizeof(*ports) * nports);
-       if (nports < MAX_ROUTELEN-1) bucket->ports[ap][nports]= -1;
+       bucket->prs[ap].length= totaldist;
+       memcpy(bucket->prs[ap].value, value, sizeof(value));
+       memcpy(bucket->prs[ap].ports, ports, sizeof(*ports) * nports);
+       if (nports < MAX_ROUTELEN-1) bucket->prs[ap].ports[nports]= -1;

        fildebugf("** ");
        fildebugf("** ");

-       for (pos=0; pos < *nscores; pos++)
-         if (scores[pos].pr == bucket) goto found;
+       for (pos=0; pos < nscores; pos++)
+         if (scores[pos].bucket == bucket) goto found;

        /* not found */
        pos= -1;
       found:
        for (;;) {
          pos++;
        /* not found */
        pos= -1;
       found:
        for (;;) {
          pos++;

-         if (pos >= *nscores-1) break; /* new top */
+         if (pos >= nscores) break; /* new top */

          if (scores[pos].value >= value[ap]) break; /* found spot */
          if (pos>0)
            scores[pos-1]= scores[pos];
          if (scores[pos].value >= value[ap]) break; /* found spot */
          if (pos>0)
            scores[pos-1]= scores[pos];


@@ -169,12 +176,20 @@ static double process_route(int nports, int totaldist,
        pos--;
        if (pos>0) {
          scores[pos].value= value[ap];
        pos--;
        if (pos>0) {
          scores[pos].value= value[ap];

-         scores[pos].pr= bucket;
+         scores[pos].bucket= bucket;
+         if (granui < granus-1 &&
+             highscores[granui][A][0].bucket &&
+             highscores[granui][P][0].bucket) {
+           /* both absolute and perleague are full at this granularity,
+            * so we don't care about anything more granular */
+           fildebugf("\n                STOP-GRANU            ");
+           granus= granui+1;
+         }

        }
        }

-       fildebugf("@%2d", pos);
-      }
-    }
-  }
+       fildebugf("@%2d/%2d ", pos, nscores);
+      } /* new best */
+    } /* ap */
+  } /* granui */

 
   fildebugf(" route");
 
 
   fildebugf(" route");
 


@@ -203,7 +218,7 @@ static void recurse(int last_isle,
 }
 
 void search(int start_isle, int final_isle_spec,
 }
 
 void search(int start_isle, int final_isle_spec,

-           PotentialResult ****buckets_base_io[GRANUS]) {
+           Bucket ****buckets_base_io[GRANUS]) {

   int granui;
   for (granui=0; granui<GRANUS; granui++)
     buckets_base[granui]=
   int granui;
   for (granui=0; granui<GRANUS; granui++)
     buckets_base[granui]=