koldfront

Emarcheology #emacs #dynamic programming

I randomly ended up reading the comments on this 6 year old blog post: export TERM=aaa-60 which sent me on to an archeology archive site of Emacs sources.

Paradoxically, or not, hosted on Microsoft GitHub.

Anyway, the blog comment referenced the top of the Gosling Emacs' display.c:

			 /-------------\
			/		\
		       /		 \
		      /			  \
		      |	  XXXX	   XXXX	  |
		      |	  XXXX	   XXXX	  |
		      |	  XXX	    XXX	  |
		      \		X	  /
		       --\     XXX     /--
			| |    XXX    | |
			| |	      | |
			| I I I I I I I |
			|  I I I I I I	|
			 \	       /
			  --	     --
			    \-------/
		    XXX			   XXX
		   XXXXX		  XXXXX
		   XXXXXXXXX	     XXXXXXXXXX
			  XXXXX	  XXXXX
			     XXXXXXX
			  XXXXX	  XXXXX
		   XXXXXXXXX	     XXXXXXXXXX
		   XXXXX		  XXXXX
		    XXX			   XXX

			  **************
			  *  BEWARE!!  *
			  **************

			All ye who enter here:
		    Most of the code in this module
		       is twisted beyond belief!

			   Tread carefully.

		    If you think you understand it,
			      You Don't,
			    So Look Again.

To optimize the number of changes done to update the screen a dynamic programming algorithm was used; here is another comment later in the file:

/*	1   2   3   4   ....	Each Mij represents the minumum cost of
      +---+---+---+---+-----	rearranging the first i lines to map onto
    1 |   |   |   |   |		the first j lines (the j direction
      +---+---+---+---+-----	represents the desired contents of a line,
    2 |   |  \| ^ |   |		i the current contents).  The algorithm
      +---+---\-|-+---+-----	used is a dynamic programming one, where
    3 |   | <-+Mij|   |		M[i,j] = min( M[i-1,j],
      +---+---+---+---+-----		      M[i,j-1]+redraw cost for j,2
    4 |   |   |   |   |			      M[i-1,j-1]+the cost of
      +---+---+---+---+-----			converting line i to line j);
    . |   |   |   |   |		Line i can be converted to line j by either
    .				just drawing j, or if they match, by moving
    .				line i to line j (with insert/delete line)
 */

Quite neat.