Subject: [RFC/PATCH v2] graph API: Use horizontal lines for more compact graphs

From: Allan Caffee <[email-masked]>
Date: Tue, 21 Apr 2009 08:47:01 -0400

Use horizontal lines instead of long diagonal during graph collapsing
and precommit for more compact and legible graphs.

Signed-off-by: Allan Caffee <[email-masked]>
---
 graph.c        |   63 ++++++++++++++++++++++++++++++++++++++++++-------------
 t/t4202-log.sh |    6 +---
 2 files changed, 50 insertions(+), 19 deletions(-)

On Tue, 21 Apr 2009, Johannes Schindelin wrote:
> Hi,
> 
> On Mon, 20 Apr 2009, Allan Caffee wrote:
> 
> > On Mon, Apr 20, 2009 at 8:56 PM, Johannes Schindelin
> > <[email-masked]> wrote:
> >
> > > On Mon, 20 Apr 2009, Allan Caffee wrote:
> > >
> > >> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? for (j = (target * 2)+3; j < (i - 2); j += 2)
> > >
> > > This (target*2)+3 is a bit too magical for me to understand. ?But 
> > > maybe I am just too tired?
> > 
> > It is a little magical.  Here target is an index into
> > graph->new_columns so we double that to get the actual location of the
> > edge in the string for this line.
> 
> Ah.  So how about
> 				 /*
> 				  * The variable target is the index of the graph
> 				  * column, and therefore target*2+3 is the actual
> 				  * screen column of the first horizontal line.
> 				  */

Sounds good to me.  Everything else look good?  

Actually now that I look at it, it might be a good idea to put an assert
statement in that for loop like `assert(graph->new_mapping[j] < 0)' to
make sure we don't clobber any existing lines.  But that seems like
overkill since we're already assured to be the first collapsing edge at
that point, which would imply that all previous odd indeces are empty.
WDYT?

diff --git a/graph.c b/graph.c
index d4571cf..86577b4 100644
--- a/graph.c
+++ b/graph.c
@@ -47,20 +47,6 @@ static void graph_show_strbuf(struct git_graph *graph, struct strbuf const *sb);
  * - Limit the number of columns, similar to the way gitk does.
  *   If we reach more than a specified number of columns, omit
  *   sections of some columns.
- *
- * - The output during the GRAPH_PRE_COMMIT and GRAPH_COLLAPSING states
- *   could be made more compact by printing horizontal lines, instead of
- *   long diagonal lines.  For example, during collapsing, something like
- *   this:          instead of this:
- *   | | | | |      | | | | |
- *   | |_|_|/       | | | |/
- *   |/| | |        | | |/|
- *   | | | |        | |/| |
- *                  |/| | |
- *                  | | | |
- *
- *   If there are several parallel diagonal lines, they will need to be
- *   replaced with horizontal lines on subsequent rows.
  */
 
 struct column {
@@ -982,6 +968,9 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 {
 	int i;
 	int *tmp_mapping;
+	short used_horizontal = 0;
+	int horizontal_edge = -1;
+	int horizontal_edge_target = -1;
 
 	/*
 	 * Clear out the new_mapping array
@@ -1019,6 +1008,23 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 			 * Move to the left by one
 			 */
 			graph->new_mapping[i - 1] = target;
+			/*
+			 * If there isn't already an edge moving horizontally
+			 * select this one.
+			 */
+			if (horizontal_edge == -1) {
+				int j;
+				horizontal_edge = i;
+				horizontal_edge_target = target;
+				/*
+				 * The variable target is the index of the graph
+				 * column, and therefore target*2+3 is the
+				 * actual screen column of the first horizontal
+				 * line.
+				 */
+				for (j = (target * 2)+3; j < (i - 2); j += 2)
+					graph->new_mapping[j] = target;
+			}
 		} else if (graph->new_mapping[i - 1] == target) {
 			/*
 			 * There is a branch line to our left
@@ -1039,10 +1045,21 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 			 *
 			 * The space just to the left of this
 			 * branch should always be empty.
+			 *
+			 * The branch to the left of that space
+			 * should be our eventual target.
 			 */
 			assert(graph->new_mapping[i - 1] > target);
 			assert(graph->new_mapping[i - 2] < 0);
+			assert(graph->new_mapping[i - 3] == target);
 			graph->new_mapping[i - 2] = target;
+			/*
+			 * Mark this branch as the horizontal edge to
+			 * prevent any other edges from moving
+			 * horizontally.
+			 */
+			if (horizontal_edge == -1)
+				horizontal_edge = i;
 		}
 	}
 
@@ -1061,8 +1078,24 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 			strbuf_addch(sb, ' ');
 		else if (target * 2 == i)
 			strbuf_write_column(sb, &graph->new_columns[target], '|');
-		else
+		else if (target == horizontal_edge_target &&
+			 i != horizontal_edge - 1) {
+				/*
+				 * Set the mappings for all but the
+				 * first segment to -1 so that they
+				 * won't continue into the next line.
+				 */
+				if (i != (target * 2)+3)
+					graph->new_mapping[i] = -1;
+				used_horizontal = 1;
+			strbuf_write_column(sb, &graph->new_columns[target], '_');
+		}
+		else {
+			if (used_horizontal && i < horizontal_edge)
+				graph->new_mapping[i] = -1;
 			strbuf_write_column(sb, &graph->new_columns[target], '/');
+
+		}
 	}
 
 	graph_pad_horizontally(graph, sb, graph->mapping_size);
diff --git a/t/t4202-log.sh b/t/t4202-log.sh
index b986190..a3b0cb8 100755
--- a/t/t4202-log.sh
+++ b/t/t4202-log.sh
@@ -298,14 +298,12 @@ cat > expect <<\EOF
 * | | |   Merge branch 'side'
 |\ \ \ \
 | * | | | side-2
-| | | |/
-| | |/|
+| | |_|/
 | |/| |
 | * | | side-1
 * | | | Second
 * | | | sixth
-| | |/
-| |/|
+| |_|/
 |/| |
 * | | fifth
 * | | fourth
-- 
1.5.6.3