+ /* `i' represents the vpos among new frame contents.
+ `j' represents the vpos among the old frame contents. */
+ p = matrix + window_size + 2; /* matrix [1, 1] */
+
+ for (i = 1; i <= window_size; i++, p++)
+ for (j = 1; j <= window_size; j++, p++)
+ {
+ /* p contains the address of matrix [i, j] */
+
+ /* First calculate the cost assuming we do
+ not insert or delete above this line.
+ That is, if we update through line i-1
+ based on old lines through j-1,
+ and then just change old line j to new line i.
+
+ Depending on which choice gives the lower cost,
+ this usually involves either scrolling a single line
+ or extending a sequence of scrolled lines, but
+ when i == j, no scrolling is required. */
+ p1 = p - window_size - 2; /* matrix [i-1, j-1] */
+ cost = p1->insertcost;
+ if (cost > p1->deletecost)
+ cost = p1->deletecost;
+ cost1 = p1->writecost;
+ if (i == j)
+ {
+ if (cost > cost1)
+ {
+ cost = cost1;
+ p->writecount = p1->writecount + 1;
+ }
+ else
+ p->writecount = 1;
+ if (old_hash[j] != new_hash[i])
+ {
+ cost += draw_cost[i];
+ }
+ }
+ else
+ {
+ if (i > j)
+ {
+ delta = i - j;
+
+ /* The cost added here for scrolling the first line by
+ a distance N includes the overhead of setting the
+ scroll window, the cost of inserting N lines at a
+ position N lines above the bottom line of the window,
+ and an extra cost which is proportional to N. */
+ cost += scroll_overhead + first_insert_cost[-delta] +
+ (delta-1) * (next_insert_cost[-delta] + extra_cost);
+
+ /* In the most general case, the insertion overhead and
+ the multiply factor can grow linearly as the distance
+ from the bottom of the window increases. The incremental
+ cost of scrolling an additional line depends upon the
+ rate of change of these two parameters. Each of these
+ growth rates can be determined by a simple difference.
+ To reduce the cumulative effects of rounding error, we
+ vary the position at which the difference is computed. */
+ cost1 += first_insert_cost[-j] - first_insert_cost[1-j] +
+ (delta-1) * (next_insert_cost[-j] - next_insert_cost[1-j]);
+ }
+ else
+ {
+ delta = j - i;
+ cost += scroll_overhead + first_delete_cost[-delta] +
+ (delta-1) * (next_delete_cost[-delta] + extra_cost);
+ cost1 += first_delete_cost[-i] - first_delete_cost[1-i] +
+ (delta-1) * ( next_delete_cost[-i] - next_delete_cost[1-i]);
+ }
+ if (cost1 < cost)
+ {
+ cost = cost1;
+ p->writecount = p1->writecount + 1;
+ }
+ else
+ p->writecount = 1;
+ if (old_hash[j] != new_hash[i])
+ {
+ cost += draw_cost[i] + old_draw_cost[j];
+ }
+ }
+ p->writecost = cost;
+
+ /* Calculate the cost if we do an insert-line
+ before outputting this line.
+ That is, we update through line i-1
+ based on old lines through j,
+ do an insert-line on line i,
+ and then output line i from scratch,
+ leaving old lines starting from j for reuse below. */
+ p1 = p - window_size - 1; /* matrix [i-1, j] */
+ cost = p1->writecost;
+ /* If i > j, an insert is allowed after a delete. */
+ if (i > j && p1->deletecost < cost)
+ cost = p1->deletecost;
+ if (p1->insertcost <= cost)
+ {
+ cost = p1->insertcost;
+ p->insertcount = p1->insertcount + 1;
+ }
+ else
+ p->insertcount = 1;
+ cost += draw_cost[i];
+ p->insertcost = cost;
+
+ /* Calculate the cost if we do a delete line after
+ outputting this line.
+ That is, we update through line i
+ based on old lines through j-1,
+ and throw away old line j. */
+ p1 = p - 1; /* matrix [i, j-1] */
+ cost = p1->writecost;
+ /* If i < j, a delete is allowed after an insert. */
+ if (i < j && p1->insertcost < cost)
+ cost = p1->insertcost;
+ cost1 = p1->deletecost;
+ if (p1->deletecost <= cost)
+ {
+ cost = p1->deletecost;
+ p->deletecount = p1->deletecount + 1;
+ }
+ else
+ p->deletecount = 1;
+ p->deletecost = cost;
+ }
+}
+
+
+\f
+/* Perform insert-lines and delete-lines operations on CURRENT_MATRIX
+ according to the costs in MATRIX, using the direct scrolling method
+ which is used when the terminal supports setting a scroll window
+ (scroll_region_ok).
+
+ WINDOW_SIZE is the number of lines being considered for scrolling
+ and UNCHANGED_AT_TOP is the vpos of the first line being
+ considered. These two arguments can specify any contiguous range
+ of lines.
+
+ In the direct scrolling method, a new scroll window is selected
+ before each insertion or deletion, so that groups of lines can be
+ scrolled directly to their final vertical positions. This method
+ is described in more detail in calculate_direct_scrolling, where
+ the cost matrix for this approach is constructed. */
+
+static void
+do_direct_scrolling (current_matrix, cost_matrix, window_size,
+ unchanged_at_top)
+ struct glyph_matrix *current_matrix;
+ struct matrix_elt *cost_matrix;
+ int window_size;
+ int unchanged_at_top;
+{
+ struct matrix_elt *p;
+ int i, j;
+
+ /* A queue of deletions and insertions to be performed. */
+ struct alt_queue { int count, pos, window; };
+ struct alt_queue *queue_start = (struct alt_queue *)
+ alloca (window_size * sizeof *queue_start);
+ struct alt_queue *queue = queue_start;
+
+ /* Set to 1 if a terminal window has been set with
+ set_terminal_window: */
+ int terminal_window_p = 0;
+
+ /* A nonzero value of write_follows indicates that a write has been
+ selected, allowing either an insert or a delete to be selected
+ next. When write_follows is zero, a delete cannot be selected
+ unless j < i, and an insert cannot be selected unless i < j.
+ This corresponds to a similar restriction (with the ordering
+ reversed) in calculate_direct_scrolling, which is intended to
+ ensure that lines marked as inserted will be blank. */
+ int write_follows_p = 1;
+
+ /* For each row in the new matrix what row of the old matrix it is. */
+ int *copy_from = (int *) alloca (window_size * sizeof (int));
+
+ /* Non-zero for each row in the new matrix that is retained from the
+ old matrix. Lines not retained are empty. */
+ char *retained_p = (char *) alloca (window_size * sizeof (char));
+
+ bzero (retained_p, window_size * sizeof (char));
+
+ /* Perform some sanity checks when GLYPH_DEBUG is on. */
+ CHECK_MATRIX (current_matrix);
+
+ /* We are working on the line range UNCHANGED_AT_TOP ...
+ UNCHANGED_AT_TOP + WINDOW_SIZE (not including) in CURRENT_MATRIX.
+ We step through lines in this range from the end to the start. I
+ is an index into new lines, j an index into old lines. The cost
+ matrix determines what to do for ranges of indices.
+
+ If i is decremented without also decrementing j, this corresponds
+ to inserting empty lines in the result. If j is decremented
+ without also decrementing i, this corresponds to omitting these
+ lines in the new rows, i.e. rows are deleted. */
+ i = j = window_size;
+
+ while (i > 0 || j > 0)
+ {
+ p = cost_matrix + i * (window_size + 1) + j;
+
+ if (p->insertcost < p->writecost
+ && p->insertcost < p->deletecost
+ && (write_follows_p || i < j))
+ {
+ /* Insert is cheaper than deleting or writing lines. Leave
+ a hole in the result display that will be filled with
+ empty lines when the queue is emptied. */
+ queue->count = 0;
+ queue->window = i;
+ queue->pos = i - p->insertcount;
+ ++queue;