git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
From: "Johannes Schindelin via GitGitGadget" <gitgitgadget@gmail.com>
To: git@vger.kernel.org
Cc: Junio C Hamano <gitster@pobox.com>,
	Johannes Schindelin <johannes.schindelin@gmx.de>
Subject: [PATCH v6 01/21] linear-assignment: a function to solve least-cost assignment problems
Date: Mon, 13 Aug 2018 04:33:00 -0700 (PDT)	[thread overview]
Message-ID: <f168da3a3c5d6ce9b7c1ea036ca184c20729153e.1534159977.git.gitgitgadget@gmail.com> (raw)
In-Reply-To: <pull.1.v6.git.gitgitgadget@gmail.com>

From: Johannes Schindelin <johannes.schindelin@gmx.de>

The problem solved by the code introduced in this commit goes like this:
given two sets of items, and a cost matrix which says how much it
"costs" to assign any given item of the first set to any given item of
the second, assign all items (except when the sets have different size)
in the cheapest way.

We use the Jonker-Volgenant algorithm to solve the assignment problem to
answer questions such as: given two different versions of a topic branch
(or iterations of a patch series), what is the best pairing of
commits/patches between the different versions?

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---
 Makefile            |   1 +
 linear-assignment.c | 201 ++++++++++++++++++++++++++++++++++++++++++++
 linear-assignment.h |  22 +++++
 3 files changed, 224 insertions(+)
 create mode 100644 linear-assignment.c
 create mode 100644 linear-assignment.h

diff --git a/Makefile b/Makefile
index bc4fc8eea..1af719b44 100644
--- a/Makefile
+++ b/Makefile
@@ -870,6 +870,7 @@ LIB_OBJS += gpg-interface.o
 LIB_OBJS += graph.o
 LIB_OBJS += grep.o
 LIB_OBJS += hashmap.o
+LIB_OBJS += linear-assignment.o
 LIB_OBJS += help.o
 LIB_OBJS += hex.o
 LIB_OBJS += ident.o
diff --git a/linear-assignment.c b/linear-assignment.c
new file mode 100644
index 000000000..9b3e56e28
--- /dev/null
+++ b/linear-assignment.c
@@ -0,0 +1,201 @@
+/*
+ * Based on: Jonker, R., & Volgenant, A. (1987). <i>A shortest augmenting path
+ * algorithm for dense and sparse linear assignment problems</i>. Computing,
+ * 38(4), 325-340.
+ */
+#include "cache.h"
+#include "linear-assignment.h"
+
+#define COST(column, row) cost[(column) + column_count * (row)]
+
+/*
+ * The parameter `cost` is the cost matrix: the cost to assign column j to row
+ * i is `cost[j + column_count * i].
+ */
+void compute_assignment(int column_count, int row_count, int *cost,
+			int *column2row, int *row2column)
+{
+	int *v, *d;
+	int *free_row, free_count = 0, saved_free_count, *pred, *col;
+	int i, j, phase;
+
+	memset(column2row, -1, sizeof(int) * column_count);
+	memset(row2column, -1, sizeof(int) * row_count);
+	ALLOC_ARRAY(v, column_count);
+
+	/* column reduction */
+	for (j = column_count - 1; j >= 0; j--) {
+		int i1 = 0;
+
+		for (i = 1; i < row_count; i++)
+			if (COST(j, i1) > COST(j, i))
+				i1 = i;
+		v[j] = COST(j, i1);
+		if (row2column[i1] == -1) {
+			/* row i1 unassigned */
+			row2column[i1] = j;
+			column2row[j] = i1;
+		} else {
+			if (row2column[i1] >= 0)
+				row2column[i1] = -2 - row2column[i1];
+			column2row[j] = -1;
+		}
+	}
+
+	/* reduction transfer */
+	ALLOC_ARRAY(free_row, row_count);
+	for (i = 0; i < row_count; i++) {
+		int j1 = row2column[i];
+		if (j1 == -1)
+			free_row[free_count++] = i;
+		else if (j1 < -1)
+			row2column[i] = -2 - j1;
+		else {
+			int min = COST(!j1, i) - v[!j1];
+			for (j = 1; j < column_count; j++)
+				if (j != j1 && min > COST(j, i) - v[j])
+					min = COST(j, i) - v[j];
+			v[j1] -= min;
+		}
+	}
+
+	if (free_count ==
+	    (column_count < row_count ? row_count - column_count : 0)) {
+		free(v);
+		free(free_row);
+		return;
+	}
+
+	/* augmenting row reduction */
+	for (phase = 0; phase < 2; phase++) {
+		int k = 0;
+
+		saved_free_count = free_count;
+		free_count = 0;
+		while (k < saved_free_count) {
+			int u1, u2;
+			int j1 = 0, j2, i0;
+
+			i = free_row[k++];
+			u1 = COST(j1, i) - v[j1];
+			j2 = -1;
+			u2 = INT_MAX;
+			for (j = 1; j < column_count; j++) {
+				int c = COST(j, i) - v[j];
+				if (u2 > c) {
+					if (u1 < c) {
+						u2 = c;
+						j2 = j;
+					} else {
+						u2 = u1;
+						u1 = c;
+						j2 = j1;
+						j1 = j;
+					}
+				}
+			}
+			if (j2 < 0) {
+				j2 = j1;
+				u2 = u1;
+			}
+
+			i0 = column2row[j1];
+			if (u1 < u2)
+				v[j1] -= u2 - u1;
+			else if (i0 >= 0) {
+				j1 = j2;
+				i0 = column2row[j1];
+			}
+
+			if (i0 >= 0) {
+				if (u1 < u2)
+					free_row[--k] = i0;
+				else
+					free_row[free_count++] = i0;
+			}
+			row2column[i] = j1;
+			column2row[j1] = i;
+		}
+	}
+
+	/* augmentation */
+	saved_free_count = free_count;
+	ALLOC_ARRAY(d, column_count);
+	ALLOC_ARRAY(pred, column_count);
+	ALLOC_ARRAY(col, column_count);
+	for (free_count = 0; free_count < saved_free_count; free_count++) {
+		int i1 = free_row[free_count], low = 0, up = 0, last, k;
+		int min, c, u1;
+
+		for (j = 0; j < column_count; j++) {
+			d[j] = COST(j, i1) - v[j];
+			pred[j] = i1;
+			col[j] = j;
+		}
+
+		j = -1;
+		do {
+			last = low;
+			min = d[col[up++]];
+			for (k = up; k < column_count; k++) {
+				j = col[k];
+				c = d[j];
+				if (c <= min) {
+					if (c < min) {
+						up = low;
+						min = c;
+					}
+					col[k] = col[up];
+					col[up++] = j;
+				}
+			}
+			for (k = low; k < up; k++)
+				if (column2row[col[k]] == -1)
+					goto update;
+
+			/* scan a row */
+			do {
+				int j1 = col[low++];
+
+				i = column2row[j1];
+				u1 = COST(j1, i) - v[j1] - min;
+				for (k = up; k < column_count; k++) {
+					j = col[k];
+					c = COST(j, i) - v[j] - u1;
+					if (c < d[j]) {
+						d[j] = c;
+						pred[j] = i;
+						if (c == min) {
+							if (column2row[j] == -1)
+								goto update;
+							col[k] = col[up];
+							col[up++] = j;
+						}
+					}
+				}
+			} while (low != up);
+		} while (low == up);
+
+update:
+		/* updating of the column pieces */
+		for (k = 0; k < last; k++) {
+			int j1 = col[k];
+			v[j1] += d[j1] - min;
+		}
+
+		/* augmentation */
+		do {
+			if (j < 0)
+				BUG("negative j: %d", j);
+			i = pred[j];
+			column2row[j] = i;
+			SWAP(j, row2column[i]);
+		} while (i1 != i);
+	}
+
+	free(col);
+	free(pred);
+	free(d);
+	free(v);
+	free(free_row);
+}
diff --git a/linear-assignment.h b/linear-assignment.h
new file mode 100644
index 000000000..1dfea7662
--- /dev/null
+++ b/linear-assignment.h
@@ -0,0 +1,22 @@
+#ifndef LINEAR_ASSIGNMENT_H
+#define LINEAR_ASSIGNMENT_H
+
+/*
+ * Compute an assignment of columns -> rows (and vice versa) such that every
+ * column is assigned to at most one row (and vice versa) minimizing the
+ * overall cost.
+ *
+ * The parameter `cost` is the cost matrix: the cost to assign column j to row
+ * i is `cost[j + column_count * i].
+ *
+ * The arrays column2row and row2column will be populated with the respective
+ * assignments (-1 for unassigned, which can happen only if column_count !=
+ * row_count).
+ */
+void compute_assignment(int column_count, int row_count, int *cost,
+			int *column2row, int *row2column);
+
+/* The maximal cost in the cost matrix (to prevent integer overflows). */
+#define COST_MAX (1<<16)
+
+#endif
-- 
gitgitgadget


  reply	other threads:[~2018-08-13 11:33 UTC|newest]

Thread overview: 387+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-05-03 15:30 [PATCH 00/18] Add `branch-diff`, a `tbdiff` lookalike Johannes Schindelin
2018-05-03 15:30 ` [PATCH 01/18] Add a function to solve least-cost assignment problems Johannes Schindelin
2018-05-13 18:19   ` Duy Nguyen
2018-05-21  9:52     ` Johannes Schindelin
2018-05-03 15:30 ` [PATCH 02/18] Add a new builtin: branch-diff Johannes Schindelin
2018-05-03 16:10   ` Ramsay Jones
2018-05-03 20:25     ` Johannes Schindelin
2018-05-03 23:20       ` Ramsay Jones
2018-05-04  6:40         ` Johannes Schindelin
2018-05-04 15:37           ` Ramsay Jones
2018-05-05 19:41             ` Johannes Schindelin
2018-05-09 16:24               ` Ramsay Jones
2018-06-01  8:23                 ` Johannes Schindelin
2018-05-04 16:34           ` Elijah Newren
2018-05-05 20:24             ` Johannes Schindelin
2018-05-03 16:41   ` Duy Nguyen
2018-05-03 20:30     ` Johannes Schindelin
2018-05-03 20:32       ` Johannes Schindelin
2018-05-04  5:15         ` Duy Nguyen
2018-05-04  7:23           ` Johannes Schindelin
2018-05-04 14:44             ` Duy Nguyen
2018-05-04 15:17               ` Duy Nguyen
2018-05-04 15:23               ` Johannes Schindelin
2018-05-04 15:29                 ` Duy Nguyen
2018-05-03 16:43   ` Stefan Beller
2018-05-03 20:42     ` Johannes Schindelin
2018-05-03 21:12       ` Stefan Beller
2018-05-03 21:49         ` Johannes Schindelin
2018-05-04  3:23           ` Junio C Hamano
2018-05-04  2:35   ` Eric Sunshine
2018-05-04  6:52     ` Johannes Schindelin
2018-05-04  7:27       ` Eric Sunshine
2018-05-03 15:30 ` [PATCH 03/18] branch-diff: first rudimentary implementation Johannes Schindelin
2018-05-03 16:30   ` Ramsay Jones
2018-05-03 20:44     ` Johannes Schindelin
2018-05-03 17:06   ` Stefan Beller
2018-05-03 21:01     ` Johannes Schindelin
2018-05-03 21:19       ` Stefan Beller
2018-05-03 22:00         ` Johannes Schindelin
2018-05-04  2:35   ` Eric Sunshine
2018-05-04  7:03     ` Johannes Schindelin
2018-05-04  4:56   ` Junio C Hamano
2018-05-04  7:18     ` Johannes Schindelin
2018-05-03 15:30 ` [PATCH 04/18] branch-diff: improve the order of the shown commits Johannes Schindelin
2018-05-03 15:30 ` [PATCH 05/18] branch-diff: also show the diff between patches Johannes Schindelin
2018-05-04  2:51   ` Eric Sunshine
2018-05-04  3:15     ` Eric Sunshine
2018-05-04  7:15     ` Johannes Schindelin
2018-05-03 15:30 ` [PATCH 06/18] branch-diff: right-trim commit messages Johannes Schindelin
2018-05-03 15:30 ` [PATCH 07/18] branch-diff: indent the diffs just like tbdiff Johannes Schindelin
2018-05-03 15:30 ` [PATCH 08/18] branch-diff: suppress the diff headers Johannes Schindelin
2018-05-03 15:30 ` [PATCH 09/18] branch-diff: adjust the output of the commit pairs Johannes Schindelin
2018-05-03 15:30 ` [PATCH 10/18] branch-diff: do not show "function names" in hunk headers Johannes Schindelin
2018-05-03 15:30 ` [PATCH 11/18] branch-diff: add tests Johannes Schindelin
2018-05-03 16:56   ` Ævar Arnfjörð Bjarmason
2018-05-03 21:03     ` Johannes Schindelin
2018-05-03 17:11   ` Stefan Beller
2018-05-03 21:05     ` Johannes Schindelin
2018-05-03 23:27   ` Philip Oakley
2018-05-04  6:42     ` Johannes Schindelin
2018-05-03 15:30 ` [PATCH 12/18] branch-diff: use color for the commit pairs Johannes Schindelin
2018-05-03 15:30 ` [PATCH 13/18] color: provide inverted colors, too Johannes Schindelin
2018-05-03 15:30 ` [PATCH 14/18] diff: add an internal option to dual-color diffs of diffs Johannes Schindelin
2018-05-03 15:31 ` [PATCH 15/18] branch-diff: offer to dual-color the diffs Johannes Schindelin
2018-05-03 15:31 ` [PATCH 16/18] branch-diff --dual-color: work around bogus white-space warning Johannes Schindelin
2018-05-03 15:31 ` [PATCH 17/18] branch-diff: add a man page Johannes Schindelin
2018-05-04  3:27   ` Eric Sunshine
2018-05-04  7:17     ` Johannes Schindelin
2018-05-03 15:31 ` [PATCH 18/18] completion: support branch-diff Johannes Schindelin
2018-05-03 18:05 ` [PATCH 00/18] Add `branch-diff`, a `tbdiff` lookalike Ævar Arnfjörð Bjarmason
2018-05-03 21:07   ` Johannes Schindelin
2018-05-03 21:50   ` Jacob Keller
2018-05-04  5:24 ` Junio C Hamano
2018-05-04  7:24   ` Johannes Schindelin
2018-05-04 15:34 ` [PATCH v2 " Johannes Schindelin
2018-05-04 15:34   ` [PATCH v2 01/18] Add a function to solve least-cost assignment problems Johannes Schindelin
2018-05-05 18:24     ` Jeff King
2018-05-05 21:55       ` Johannes Schindelin
2018-05-30 13:55     ` SZEDER Gábor
2018-05-30 16:14       ` Stefan Beller
2018-05-30 23:28         ` brian m. carlson
2018-05-31 12:19           ` Johannes Schindelin
2018-05-04 15:34   ` [PATCH v2 02/18] Add a new builtin: branch-diff Johannes Schindelin
2018-05-05 18:26     ` Jeff King
2018-05-05 21:57       ` Johannes Schindelin
2018-05-06  0:25         ` Todd Zullinger
2018-05-06  0:38           ` Todd Zullinger
2018-05-06 12:04             ` Johannes Schindelin
2018-05-06  1:05         ` Igor Djordjevic
2018-05-06  4:53           ` Jacob Keller
2018-05-06  8:32             ` Duy Nguyen
2018-05-06 12:08               ` Johannes Schindelin
2018-05-06 12:10           ` Johannes Schindelin
2018-05-06 13:37             ` Igor Djordjevic
2018-05-07  1:34               ` Johannes Schindelin
2018-05-07 22:05                 ` Igor Djordjevic
2018-05-07 22:24                   ` Stefan Beller
2018-05-07 23:39                     ` Igor Djordjevic
2018-05-08  3:44                     ` Jeff King
2018-05-08  3:48                       ` Jeff King
2018-05-22 11:38                       ` Ævar Arnfjörð Bjarmason
2018-05-25 22:06                         ` Stefan Beller
     [not found]                           ` <CAA8fPEkNjy+ETz4Mx+C2kUfLjLzR9uuOmO3GfN48ZH1SwyfE1A@mail.gmail.com>
2018-05-26  6:15                             ` Fwd: " Øyvind Rønningstad
2018-06-01  8:15                             ` Johannes Schindelin
2018-05-06  2:33         ` Junio C Hamano
2018-05-06 12:21           ` Johannes Schindelin
2018-05-06 20:51             ` Eric Sunshine
2018-05-07  2:04               ` Johannes Schindelin
2018-05-07  7:48                 ` Jeff King
2018-05-07 21:33                   ` Igor Djordjevic
2018-05-21 10:33                     ` Johannes Schindelin
2018-05-21 17:56                       ` Stefan Beller
2018-05-21 20:24                         ` Jeff King
2018-05-21 21:40                           ` Brandon Williams
2018-05-21 21:48                             ` Stefan Beller
2018-05-21 21:52                             ` Jeff King
2018-05-22  2:08                               ` Junio C Hamano
2018-05-08  0:30                   ` Junio C Hamano
2018-05-07  1:45             ` Junio C Hamano
2018-05-07  5:39               ` Johannes Schindelin
2018-05-07 15:12                 ` Junio C Hamano
2018-05-21 10:41                   ` Johannes Schindelin
2018-05-07  7:50         ` Jeff King
2018-05-07 15:28           ` Duy Nguyen
2018-05-07 19:58             ` Stefan Beller
2018-05-04 15:34   ` [PATCH v2 03/18] branch-diff: first rudimentary implementation Johannes Schindelin
2018-05-04 15:34   ` [PATCH v2 04/18] branch-diff: improve the order of the shown commits Johannes Schindelin
2018-05-04 15:34   ` [PATCH v2 05/18] branch-diff: also show the diff between patches Johannes Schindelin
2018-05-06  1:14     ` Igor Djordjevic
2018-05-06 12:18       ` Johannes Schindelin
2018-05-04 15:34   ` [PATCH v2 06/18] branch-diff: right-trim commit messages Johannes Schindelin
2018-05-04 15:34   ` [PATCH v2 07/18] branch-diff: indent the diffs just like tbdiff Johannes Schindelin
2018-05-06 14:15     ` Martin Ågren
2018-05-07  1:54       ` Johannes Schindelin
2018-05-04 15:34   ` [PATCH v2 08/18] branch-diff: suppress the diff headers Johannes Schindelin
2018-05-04 15:34   ` [PATCH v2 09/18] branch-diff: adjust the output of the commit pairs Johannes Schindelin
2018-05-04 16:25     ` Elijah Newren
2018-05-04 15:34   ` [PATCH v2 10/18] branch-diff: do not show "function names" in hunk headers Johannes Schindelin
2018-05-04 15:34   ` [PATCH v2 11/18] branch-diff: add tests Johannes Schindelin
2018-05-04 15:34   ` [PATCH v2 12/18] branch-diff: use color for the commit pairs Johannes Schindelin
2018-05-05 23:48     ` Todd Zullinger
2018-05-07  1:52       ` Johannes Schindelin
2018-05-08  2:10         ` Todd Zullinger
2018-06-01  8:17           ` Johannes Schindelin
2018-05-04 15:34   ` [PATCH v2 13/18] color: provide inverted colors, too Johannes Schindelin
2018-05-05 18:29     ` Jeff King
2018-05-05 22:03       ` Johannes Schindelin
2018-05-06  6:35         ` Jeff King
2018-05-06  6:41           ` Jeff King
2018-05-07  1:20             ` Johannes Schindelin
2018-05-07  7:37               ` Jeff King
2018-05-07  1:35             ` Junio C Hamano
2018-05-07  5:38               ` Johannes Schindelin
2018-05-07  7:40               ` Jeff King
2018-05-04 15:34   ` [PATCH v2 14/18] diff: add an internal option to dual-color diffs of diffs Johannes Schindelin
2018-05-04 15:35   ` [PATCH v2 15/18] branch-diff: offer to dual-color the diffs Johannes Schindelin
2018-05-04 15:35   ` [PATCH v2 16/18] branch-diff --dual-color: work around bogus white-space warning Johannes Schindelin
2018-05-04 15:35   ` [PATCH v2 17/18] branch-diff: add a man page Johannes Schindelin
2018-05-04 15:35   ` [PATCH v2 18/18] completion: support branch-diff Johannes Schindelin
2018-05-06  8:24     ` Duy Nguyen
2018-05-07  1:23       ` Johannes Schindelin
2018-05-04 16:21   ` [PATCH v2 00/18] Add `branch-diff`, a `tbdiff` lookalike Elijah Newren
2018-05-04 16:30     ` Elijah Newren
2018-05-05 20:03     ` Johannes Schindelin
2018-05-07 17:07       ` Elijah Newren
2018-05-07 17:50         ` SZEDER Gábor
2018-05-07 18:38           ` Elijah Newren
2018-05-06  5:22   ` Junio C Hamano
2018-05-06 12:23     ` Johannes Schindelin
2018-05-06 22:56   ` brian m. carlson
2018-05-07  2:05     ` Johannes Schindelin
2018-07-03 11:26   ` [PATCH v3 00/20] Add `range-diff`, " Johannes Schindelin via GitGitGadget
2018-04-30 21:54     ` [PATCH v3 01/20] linear-assignment: a function to solve least-cost assignment problems Johannes Schindelin via GitGitGadget
2018-07-06 22:43       ` Junio C Hamano
2018-07-07 11:34         ` Johannes Schindelin
2018-07-07 16:34           ` Junio C Hamano
2018-07-07 19:27             ` Johannes Schindelin
2018-07-07 22:23               ` Johannes Schindelin
2018-07-09 22:08                 ` refs/notes/amlog problems, was " Johannes Schindelin
2018-07-11 16:12                   ` Junio C Hamano
2018-07-12 15:23                     ` Johannes Schindelin
2018-07-12 16:59                       ` Junio C Hamano
2018-07-19 17:06                         ` Junio C Hamano
2018-07-20 18:51                           ` Johannes Schindelin
2018-07-20 19:34                             ` Junio C Hamano
2018-07-20 21:20                               ` Stefan Beller
2018-07-20 21:24                                 ` Junio C Hamano
     [not found]                                   ` <CAPc5daW-KoyUX3i7M5YbdQC2mFKAmVBS42-XT84hpm30VFcZ1g@mail.gmail.com>
2018-07-20 21:30                                     ` Stefan Beller
2018-07-21 22:02                                       ` Johannes Schindelin
2018-07-21 21:56                               ` Johannes Schindelin
2018-07-23  1:25                                 ` Jeff King
2018-07-24  1:50                                   ` Junio C Hamano
2018-07-24  9:45                                     ` Jeff King
2018-07-09 22:23                 ` Junio C Hamano
2018-07-10 10:47                   ` refs/notes/amlog woes, was " Johannes Schindelin
2018-07-11 10:07       ` SZEDER Gábor
2018-07-12 15:11         ` Johannes Schindelin
2018-05-01 19:42     ` [PATCH v3 02/20] Introduce `range-diff` to compare iterations of a topic branch Johannes Schindelin via GitGitGadget
2018-05-02  0:34     ` [PATCH v3 03/20] range-diff: first rudimentary implementation Johannes Schindelin via GitGitGadget
2018-07-16  6:55       ` Eric Sunshine
2018-07-17  9:53         ` Johannes Schindelin
2018-05-02 10:22     ` [PATCH v3 04/20] range-diff: improve the order of the shown commits Johannes Schindelin via GitGitGadget
2018-05-02 14:49     ` [PATCH v3 06/20] range-diff: right-trim commit messages Johannes Schindelin via GitGitGadget
2018-05-02 14:52     ` [PATCH v3 07/20] range-diff: indent the diffs just like tbdiff Johannes Schindelin via GitGitGadget
2018-05-02 14:53     ` [PATCH v3 08/20] range-diff: suppress the diff headers Johannes Schindelin via GitGitGadget
2018-05-02 15:19     ` [PATCH v3 11/20] range-diff: add tests Thomas Rast via GitGitGadget
2018-07-16  7:28       ` Eric Sunshine
2018-07-17 16:28         ` Johannes Schindelin
2018-05-02 21:35     ` [PATCH v3 09/20] range-diff: adjust the output of the commit pairs Johannes Schindelin via GitGitGadget
2018-07-16  7:21       ` Eric Sunshine
2018-07-17 16:24         ` Johannes Schindelin
2018-07-17 17:47           ` Stefan Beller
2018-07-20 18:57             ` Johannes Schindelin
2018-07-20 19:16               ` Stefan Beller
2018-07-21 22:07                 ` Johannes Schindelin
2018-05-02 23:32     ` [PATCH v3 12/20] range-diff: use color for " Johannes Schindelin via GitGitGadget
2018-05-03  0:14     ` [PATCH v3 13/20] color: add the meta color GIT_COLOR_REVERSE Johannes Schindelin via GitGitGadget
2018-05-03  0:17     ` [PATCH v3 14/20] diff: add an internal option to dual-color diffs of diffs Johannes Schindelin via GitGitGadget
2018-07-09 19:29       ` Stefan Beller
2018-07-10 17:45         ` [PATCH 0/2] " Stefan Beller
2018-07-10 17:45           ` [PATCH 1/2] diff.c: convert emit_line_ws_markup to take string for sign Stefan Beller
2018-07-10 17:45           ` [PATCH 2/2] WIP diff.c: clarify emit_line_0 Stefan Beller
2018-07-10 19:58             ` [PATCH 1/2] diff.c: convert emit_line_ws_markup to take string for sign Stefan Beller
2018-07-10 19:59             ` [PATCH] diff.c: clarify emit_line_0 Stefan Beller
2018-07-10 21:54               ` [PATCH] ws: do not reset and set color twice Stefan Beller
2018-07-21 21:13           ` [PATCH 0/2] Re: [PATCH v3 14/20] diff: add an internal option to dual-color diffs of diffs Johannes Schindelin
2018-05-03  1:01     ` [PATCH v3 15/20] range-diff: offer to dual-color the diffs Johannes Schindelin via GitGitGadget
2018-05-03  1:11     ` [PATCH v3 16/20] range-diff --dual-color: work around bogus white-space warning Johannes Schindelin via GitGitGadget
2018-07-09 19:34       ` Stefan Beller
2018-07-09 21:02         ` Junio C Hamano
2018-07-10 10:08           ` Johannes Schindelin
2018-07-10 15:50             ` Junio C Hamano
2018-07-10 16:32             ` Stefan Beller
2018-07-21 21:44               ` Johannes Schindelin
2018-05-03 13:50     ` [PATCH v3 17/20] range-diff: add a man page Johannes Schindelin via GitGitGadget
2018-07-09 18:20       ` Stefan Beller
2018-07-09 20:00         ` Johannes Schindelin
2018-07-09 20:25           ` Stefan Beller
2018-07-09 20:38             ` Johannes Schindelin
2018-07-16  8:01       ` Eric Sunshine
2018-07-17 16:39         ` Johannes Schindelin
2018-05-03 14:44     ` [PATCH v3 18/20] completion: support `git range-diff` Johannes Schindelin via GitGitGadget
2018-07-06 22:46       ` Junio C Hamano
2018-07-07 11:38         ` Johannes Schindelin
2018-05-05 19:52     ` [PATCH v3 19/20] range-diff: left-pad patch numbers Johannes Schindelin via GitGitGadget
2018-05-06 15:26     ` [PATCH v3 05/20] range-diff: also show the diff between patches Johannes Schindelin via GitGitGadget
2018-05-06 15:35     ` [PATCH v3 10/20] range-diff: do not show "function names" in hunk headers Johannes Schindelin via GitGitGadget
2018-06-30 20:41     ` [PATCH v3 20/20] range-diff: make --dual-color the default mode Johannes Schindelin via GitGitGadget
2018-07-16  8:06       ` Eric Sunshine
2018-07-17 16:40         ` Johannes Schindelin
2018-07-21 22:04     ` [PATCH v4 00/21] Add `range-diff`, a `tbdiff` lookalike Johannes Schindelin via GitGitGadget
2018-07-21 22:04       ` [PATCH v4 01/21] linear-assignment: a function to solve least-cost assignment problems Johannes Schindelin via GitGitGadget
2018-07-28  8:46         ` Thomas Gummerer
2018-07-30 15:59           ` Johannes Schindelin
2018-07-21 22:04       ` [PATCH v4 02/21] Introduce `range-diff` to compare iterations of a topic branch Johannes Schindelin via GitGitGadget
2018-07-21 22:04       ` [PATCH v4 03/21] range-diff: first rudimentary implementation Johannes Schindelin via GitGitGadget
2018-07-29 18:36         ` Thomas Gummerer
2018-07-30 16:21           ` Johannes Schindelin
2018-07-30 21:16             ` Thomas Gummerer
2018-08-10 20:50               ` Johannes Schindelin
2018-07-21 22:04       ` [PATCH v4 04/21] range-diff: improve the order of the shown commits Johannes Schindelin via GitGitGadget
2018-07-21 22:04       ` [PATCH v4 05/21] range-diff: also show the diff between patches Johannes Schindelin via GitGitGadget
2018-07-29 19:03         ` Thomas Gummerer
2018-07-29 19:22           ` Eric Sunshine
2018-07-29 21:45             ` Thomas Gummerer
2018-07-30 16:28               ` Johannes Schindelin
2018-07-30 21:26                 ` Thomas Gummerer
2018-07-30 21:51                   ` Eric Sunshine
2018-08-10 21:12                     ` Johannes Schindelin
2018-08-10 21:31                       ` Eric Sunshine
2018-08-10 22:02                         ` Johannes Schindelin
2018-08-10 20:36                   ` Johannes Schindelin
2018-07-21 22:04       ` [PATCH v4 06/21] range-diff: right-trim commit messages Johannes Schindelin via GitGitGadget
2018-07-21 22:04       ` [PATCH v4 07/21] range-diff: indent the diffs just like tbdiff Johannes Schindelin via GitGitGadget
2018-07-21 22:04       ` [PATCH v4 08/21] range-diff: suppress the diff headers Johannes Schindelin via GitGitGadget
2018-07-21 22:04       ` [PATCH v4 09/21] range-diff: adjust the output of the commit pairs Johannes Schindelin via GitGitGadget
2018-07-29 19:38         ` Thomas Gummerer
2018-08-10 21:01           ` Johannes Schindelin
2018-07-29 21:28         ` Thomas Gummerer
2018-07-21 22:04       ` [PATCH v4 10/21] range-diff: do not show "function names" in hunk headers Johannes Schindelin via GitGitGadget
2018-07-29 20:52         ` Thomas Gummerer
2018-08-10 21:03           ` Johannes Schindelin
2018-07-21 22:05       ` [PATCH v4 11/21] range-diff: add tests Thomas Rast via GitGitGadget
2018-07-22  5:04         ` Eric Sunshine
2018-07-30 16:30           ` Johannes Schindelin
2018-07-30 20:18             ` Junio C Hamano
2018-07-30 23:40               ` Stefan Beller
2018-07-31 15:19                 ` Junio C Hamano
2018-07-23 21:25         ` Stefan Beller
2018-07-21 22:05       ` [PATCH v4 12/21] range-diff: use color for the commit pairs Johannes Schindelin via GitGitGadget
2018-07-21 22:05       ` [PATCH v4 13/21] color: add the meta color GIT_COLOR_REVERSE Johannes Schindelin via GitGitGadget
2018-07-21 22:05       ` [PATCH v4 14/21] diff: add an internal option to dual-color diffs of diffs Johannes Schindelin via GitGitGadget
2018-07-23 22:27         ` Junio C Hamano
2018-07-23 22:48           ` Stefan Beller
2018-07-21 22:05       ` [PATCH v4 15/21] range-diff: offer to dual-color the diffs Johannes Schindelin via GitGitGadget
2018-07-21 22:05       ` [PATCH v4 16/21] range-diff --dual-color: fix bogus white-space warning Johannes Schindelin via GitGitGadget
2018-07-23 22:20         ` Stefan Beller
2018-08-10 21:05           ` Johannes Schindelin
2018-07-23 22:39         ` Junio C Hamano
2018-07-24  1:27           ` Junio C Hamano
2018-07-21 22:05       ` [PATCH v4 17/21] range-diff: populate the man page Johannes Schindelin via GitGitGadget
2018-07-29 21:23         ` Thomas Gummerer
2018-08-10 21:06           ` Johannes Schindelin
2018-07-21 22:05       ` [PATCH v4 18/21] completion: support `git range-diff` Johannes Schindelin via GitGitGadget
2018-07-22  5:49         ` Eric Sunshine
2018-08-10 20:24           ` Johannes Schindelin
2018-07-21 22:05       ` [PATCH v4 19/21] range-diff: left-pad patch numbers Johannes Schindelin via GitGitGadget
2018-07-21 22:05       ` [PATCH v4 20/21] range-diff: make --dual-color the default mode Johannes Schindelin via GitGitGadget
2018-07-29 21:33         ` Thomas Gummerer
2018-08-10 21:07           ` Johannes Schindelin
2018-07-21 22:05       ` [PATCH v4 21/21] range-diff: use dim/bold cues to improve dual color mode Johannes Schindelin via GitGitGadget
2018-07-23 21:03       ` [PATCH v4 00/21] Add `range-diff`, a `tbdiff` lookalike Stefan Beller
2018-07-23 21:49         ` Junio C Hamano
2018-07-25 17:44           ` Stefan Beller
2018-07-26  9:47         ` Johannes Schindelin
2018-08-08 13:05         ` Johannes Schindelin
2018-08-08 17:33           ` Stefan Beller
2018-08-10 21:18             ` Johannes Schindelin
2018-08-10 21:31               ` Junio C Hamano
2018-08-10 22:00                 ` Johannes Schindelin
2018-07-29 21:50       ` Thomas Gummerer
2018-08-10 22:14       ` [PATCH v5 00/21] Add range-diff, a tbdiff lookalike Johannes Schindelin via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 01/21] linear-assignment: a function to solve least-cost assignment problems Johannes Schindelin via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 02/21] Introduce `range-diff` to compare iterations of a topic branch Johannes Schindelin via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 03/21] range-diff: first rudimentary implementation Johannes Schindelin via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 04/21] range-diff: improve the order of the shown commits Johannes Schindelin via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 05/21] range-diff: also show the diff between patches Johannes Schindelin via GitGitGadget
2018-08-12 21:47           ` Thomas Gummerer
2018-08-13  9:46             ` Johannes Schindelin
2018-08-13 18:01               ` Thomas Gummerer
2018-08-10 22:14         ` [PATCH v5 06/21] range-diff: right-trim commit messages Johannes Schindelin via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 07/21] range-diff: indent the diffs just like tbdiff Johannes Schindelin via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 08/21] range-diff: suppress the diff headers Johannes Schindelin via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 09/21] range-diff: adjust the output of the commit pairs Johannes Schindelin via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 10/21] range-diff: do not show "function names" in hunk headers Johannes Schindelin via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 11/21] range-diff: add tests Thomas Rast via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 12/21] range-diff: use color for the commit pairs Johannes Schindelin via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 13/21] color: add the meta color GIT_COLOR_REVERSE Johannes Schindelin via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 14/21] diff: add an internal option to dual-color diffs of diffs Johannes Schindelin via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 15/21] range-diff: offer to dual-color the diffs Johannes Schindelin via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 16/21] range-diff --dual-color: skip white-space warnings Johannes Schindelin via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 17/21] range-diff: populate the man page Johannes Schindelin via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 18/21] completion: support `git range-diff` Johannes Schindelin via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 19/21] range-diff: left-pad patch numbers Johannes Schindelin via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 20/21] range-diff: make --dual-color the default mode Johannes Schindelin via GitGitGadget
2018-08-10 22:14         ` [PATCH v5 21/21] range-diff: use dim/bold cues to improve dual color mode Johannes Schindelin via GitGitGadget
2018-08-13 11:32         ` [PATCH v6 00/21] Add range-diff, a tbdiff lookalike Johannes Schindelin via GitGitGadget
2018-08-13 11:33           ` Johannes Schindelin via GitGitGadget [this message]
2018-08-13 11:33           ` [PATCH v6 02/21] Introduce `range-diff` to compare iterations of a topic branch Johannes Schindelin via GitGitGadget
2018-08-13 11:33           ` [PATCH v6 03/21] range-diff: first rudimentary implementation Johannes Schindelin via GitGitGadget
2019-03-05  6:29             ` Junio C Hamano
2018-08-13 11:33           ` [PATCH v6 04/21] range-diff: improve the order of the shown commits Johannes Schindelin via GitGitGadget
2018-08-13 11:33           ` [PATCH v6 05/21] range-diff: also show the diff between patches Johannes Schindelin via GitGitGadget
2018-08-13 11:33           ` [PATCH v6 06/21] range-diff: right-trim commit messages Johannes Schindelin via GitGitGadget
2018-08-13 11:33           ` [PATCH v6 07/21] range-diff: indent the diffs just like tbdiff Johannes Schindelin via GitGitGadget
2018-08-13 11:33           ` [PATCH v6 08/21] range-diff: suppress the diff headers Johannes Schindelin via GitGitGadget
2018-08-13 11:33           ` [PATCH v6 09/21] range-diff: adjust the output of the commit pairs Johannes Schindelin via GitGitGadget
2018-08-13 11:33           ` [PATCH v6 10/21] range-diff: do not show "function names" in hunk headers Johannes Schindelin via GitGitGadget
2018-08-13 11:33           ` [PATCH v6 11/21] range-diff: add tests Thomas Rast via GitGitGadget
2018-08-13 18:35             ` Thomas Gummerer
2018-08-14 14:53               ` Johannes Schindelin
2018-08-14 15:03                 ` Jeff King
2018-08-14 15:06                   ` Jeff King
2018-08-14 15:18                 ` Junio C Hamano
2018-08-13 11:33           ` [PATCH v6 12/21] range-diff: use color for the commit pairs Johannes Schindelin via GitGitGadget
2018-08-13 11:33           ` [PATCH v6 13/21] color: add the meta color GIT_COLOR_REVERSE Johannes Schindelin via GitGitGadget
2018-08-13 11:33           ` [PATCH v6 14/21] diff: add an internal option to dual-color diffs of diffs Johannes Schindelin via GitGitGadget
2018-08-13 11:33           ` [PATCH v6 15/21] range-diff: offer to dual-color the diffs Johannes Schindelin via GitGitGadget
2018-08-13 11:33           ` [PATCH v6 16/21] range-diff --dual-color: skip white-space warnings Johannes Schindelin via GitGitGadget
2018-08-13 17:48             ` Junio C Hamano
2018-08-13 11:33           ` [PATCH v6 17/21] range-diff: populate the man page Johannes Schindelin via GitGitGadget
2018-09-09 11:14             ` Ævar Arnfjörð Bjarmason
2018-09-09 16:54               ` SZEDER Gábor
2018-09-09 17:19                 ` Ævar Arnfjörð Bjarmason
2018-09-10 13:37                   ` Jeff King
2018-10-02 15:06                     ` Johannes Schindelin
2018-09-10 17:17                   ` Junio C Hamano
2018-08-13 11:33           ` [PATCH v6 18/21] completion: support `git range-diff` Johannes Schindelin via GitGitGadget
2018-08-13 11:33           ` [PATCH v6 19/21] range-diff: left-pad patch numbers Johannes Schindelin via GitGitGadget
2018-08-13 11:33           ` [PATCH v6 20/21] range-diff: make --dual-color the default mode Johannes Schindelin via GitGitGadget
2018-08-13 11:33           ` [PATCH v6 21/21] range-diff: use dim/bold cues to improve dual color mode Johannes Schindelin via GitGitGadget
2018-08-13 11:38           ` [PATCH v6 00/21] Add range-diff, a tbdiff lookalike Johannes Schindelin
2018-08-13 20:47             ` Thomas Gummerer
2018-05-21  4:48 ` [PATCH 00/18] Add `branch-diff`, a `tbdiff` lookalike Junio C Hamano
2018-05-21  9:51   ` Johannes Schindelin
2018-05-22  1:42     ` Junio C Hamano
2018-06-01  8:28       ` Johannes Schindelin

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=f168da3a3c5d6ce9b7c1ea036ca184c20729153e.1534159977.git.gitgitgadget@gmail.com \
    --to=gitgitgadget@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=johannes.schindelin@gmx.de \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).