[gnugo-devel] add comments in readconnect.c

[Arend Bayer]

- add comments explaining heap of postponed decisions used in
  spread_connection_distances

I hope the author of this code at least feels somewhat guilty for
not adding comments there in the first place :)

Btw, Paul, I tried to get on good terms with your change of the connection
queue logic (only storing the origin instead of each stone of a string)
and failed badly. So I hope you won't be too upset in case I revert that
change soon...

Arend


Index: engine/readconnect.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/readconnect.c,v
retrieving revision 1.67
diff -u -p -r1.67 readconnect.c
--- engine/readconnect.c        31 Jan 2004 12:50:13 -0000      1.67
+++ engine/readconnect.c        3 Feb 2004 01:28:56 -0000
@@ -3151,6 +3151,16 @@ block_off(int str, const char goal[BOARD
 }


+/* Store a possibly expensive decision for later evaluation. The
+ * data getting stored should be self-explanatory.
+ * The job of the helper function is to
+ * - decide whether the spreading step will be allowed (typically
+ *   depending on a latter)
+ * - add the relevant positions to the connection queue in case the test
+ *   was successful.
+ *
+ * Elements in the heap are kept sorted according to smallest distance.
+ */
 static void
 push_connection_heap_entry(struct connection_data *conn, float distance,
                           int coming_from, int target,
@@ -3184,6 +3194,9 @@ push_connection_heap_entry(struct connec
 }


+/* Delete the first entry from the heap. It must have been used resp.
+ * discarded previously by the calling function.
+ */
 static void
 pop_connection_heap_entry(struct connection_data *conn)
 {
@@ -3373,6 +3386,12 @@ case_16_17_18_helper(struct connection_d
  * (cutoff_distance) is the highest distance before we give up,
  * (speculative) controls some special cases in the propagation rules
  * below.
+ *
+ * As an optimization, new points are either added directly via the ENQUEUE
+ * macro if the necessary test is an immediate (usually purely geometric)
+ * check, or if the decision is more expensive (usually depending on a
+ * ladder), it gets postponed and stored via push_connection_heap_entry()
+ * for later evaluation.
  */

 void
@@ -3389,6 +3408,9 @@ spread_connection_distances(int color, s
     int pos;
     float distance;

+    /* Delete heap entries for positions that have already been reached
+     * with smaller distance.
+     */
     while (conn->heap_size > 0
           && conn->heap[0]->distance >= conn->distances[conn->heap[0]->target])
       pop_connection_heap_entry(conn);
@@ -3423,6 +3445,10 @@ spread_connection_distances(int color, s
        conn->queue[best_index] = temp;
       }

+      /* If the first element in heap has smaller distance than the
+       * smallest we have found so far, call the relevant helper function
+       * now, and delete the heap entry.
+       */
       if (conn->heap_size > 0 && conn->heap[0]->distance < smallest_dist) {
        conn->heap[0]->helper(conn, color);
        pop_connection_heap_entry(conn);
Index: engine/readconnect.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/readconnect.h,v
retrieving revision 1.4
diff -u -p -r1.4 readconnect.h
--- engine/readconnect.h        24 Jan 2004 04:04:56 -0000      1.4
+++ engine/readconnect.h        3 Feb 2004 01:28:56 -0000
@@ -24,9 +24,17 @@
 struct heap_entry;
 struct connection_data;

+/* Expensive functions that we try to evaluate as late as possible
+ * when spreading connection distances.
+ */
 typedef void (*connection_helper_fn_ptr) (struct connection_data *conn,
                                          int color);

+/* This heap contains a list of positions where we have delayed a
+ * decision whether to "spread a connection distance". The function
+ * helper() will be called when we finally need the decision. See
+ * push_connection_heap_entry() for organization of the heap.
+ */
 struct heap_entry {
   float distance;
   int coming_from;