# HG changeset patch
# User Chris Cannam
# Date 1289409101 0
# Node ID bd3accba9b3f44b08def5c38746b9cca42c8b620
# Parent  4286836bb3c90aa80bdb66e7bec0a8d93a4f30b4
* Better layout for branches; spline connection paths

diff -r 4286836bb3c9 -r bd3accba9b3f changesetitem.cpp
--- a/changesetitem.cpp	Wed Nov 10 12:44:11 2010 +0000
+++ b/changesetitem.cpp	Wed Nov 10 17:11:41 2010 +0000
@@ -6,7 +6,6 @@
 QRectF
 ChangesetItem::boundingRect() const
 {
-    int n = m_changeset->number();
     return QRectF(0, 0, 250, 50);
 }
 
diff -r 4286836bb3c9 -r bd3accba9b3f changesetitem.h
--- a/changesetitem.h	Wed Nov 10 12:44:11 2010 +0000
+++ b/changesetitem.h	Wed Nov 10 17:11:41 2010 +0000
@@ -15,8 +15,8 @@
 
     int column() const { return m_column; }
     int row() const { return m_row; }
-    void setColumn(int c) { m_column = c; }
-    void setRow(int r) { m_row = r; }
+    void setColumn(int c) { m_column = c; setX(c * 100); }
+    void setRow(int r) { m_row = r; setY(r * 100); }
 
 private:
     Changeset *m_changeset;
diff -r 4286836bb3c9 -r bd3accba9b3f connectionitem.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/connectionitem.cpp	Wed Nov 10 17:11:41 2010 +0000
@@ -0,0 +1,48 @@
+
+
+#include "connectionitem.h"
+
+#include "changesetitem.h"
+
+#include <QPainter>
+
+QRectF
+ConnectionItem::boundingRect() const
+{
+    if (!m_parent || !m_child) return QRectF();
+    float scale = 100;
+    float size = 50;
+    return QRectF(scale * m_child->column() + size/2 - 2,
+		  scale * m_child->row() + size - 2,
+		  scale * m_parent->column() - scale * m_child->column() + 4,
+		  scale * m_parent->row() - scale * m_child->row() - size + 4)
+	.normalized();
+}
+
+void
+ConnectionItem::paint(QPainter *paint, const QStyleOptionGraphicsItem *, QWidget *)
+{
+    QPainterPath p;
+    float scale = 100;
+    float size = 50;
+    p.moveTo(scale * m_child->column() + size/2,
+	     scale * m_child->row() + size);
+    if (m_parent->column() == m_child->column()) {
+	p.lineTo(scale * m_parent->column() + size/2,
+		 scale * m_parent->row());
+    } else {
+	p.cubicTo(scale * m_child->column() + size/2,
+		  scale * m_child->row() + size + size,
+		  scale * m_parent->column() + size/2,
+		  scale * m_child->row() + size,
+		  scale * m_parent->column() + size/2,
+		  scale * m_child->row() + scale);
+	if (abs(m_parent->row() - m_child->row()) > 1) {
+	    p.lineTo(scale * m_parent->column() + size/2,
+		     scale * m_parent->row());
+	}
+    }
+    paint->drawPath(p);
+}
+
+
diff -r 4286836bb3c9 -r bd3accba9b3f connectionitem.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/connectionitem.h	Wed Nov 10 17:11:41 2010 +0000
@@ -0,0 +1,31 @@
+#ifndef CONNECTIONITEM_H
+#define CONNECTIONITEM_H
+
+#include <QGraphicsItem>
+
+class Connection;
+
+class ChangesetItem;
+
+class ConnectionItem : public QGraphicsItem
+{
+public:
+    ConnectionItem() : m_parent(0), m_child(0) { }
+
+    virtual QRectF boundingRect() const;
+    virtual void paint(QPainter *, const QStyleOptionGraphicsItem *, QWidget *);
+
+    //!!! deletion signals from parent/child
+
+    ChangesetItem *parent() { return m_parent; }
+    ChangesetItem *child() { return m_child; }
+
+    void setParent(ChangesetItem *p) { m_parent = p; }
+    void setChild(ChangesetItem *c) { m_child = c; }
+
+private:
+    ChangesetItem *m_parent;
+    ChangesetItem *m_child;
+};
+
+#endif // CONNECTIONITEM_H
diff -r 4286836bb3c9 -r bd3accba9b3f grapher.cpp
--- a/grapher.cpp	Wed Nov 10 12:44:11 2010 +0000
+++ b/grapher.cpp	Wed Nov 10 17:11:41 2010 +0000
@@ -1,5 +1,6 @@
 
 #include "grapher.h"
+#include "connectionitem.h"
 
 #include <QGraphicsScene>
 
@@ -34,13 +35,13 @@
     if (m_handled.contains(id)) {
 	return;
     }
-    if (!m_idCsetMap.contains(id)) {
+    if (!m_changesets.contains(id)) {
 	throw LayoutException(QString("Changeset %1 not in ID map").arg(id));
     }
     if (!m_items.contains(id)) {
 	throw LayoutException(QString("Changeset %1 not in item map").arg(id));
     }
-    Changeset *cs = m_idCsetMap[id];
+    Changeset *cs = m_changesets[id];
     ChangesetItem *item = m_items[id];
     std::cerr << "Looking at " << id.toStdString() << std::endl;
 
@@ -51,7 +52,7 @@
 	bool haveRow = false;
 	foreach (QString parentId, cs->parents()) {
 
-	    if (!m_idCsetMap.contains(parentId)) continue;
+	    if (!m_changesets.contains(parentId)) continue;
 	    if (!m_items.contains(parentId)) continue;
 
 	    if (!m_handled.contains(parentId)) {
@@ -71,7 +72,6 @@
 	      << std::endl;
 
     item->setRow(row);
-    item->setY(row * 100);
     m_handled.insert(id);
 }
 
@@ -82,61 +82,149 @@
 	std::cerr << "Already looked at " << id.toStdString() << std::endl;
 	return;
     }
-    if (!m_idCsetMap.contains(id)) {
+    if (!m_changesets.contains(id)) {
 	throw LayoutException(QString("Changeset %1 not in ID map").arg(id));
     }
     if (!m_items.contains(id)) {
 	throw LayoutException(QString("Changeset %1 not in item map").arg(id));
     }
-    Changeset *cs = m_idCsetMap[id];
+    Changeset *cs = m_changesets[id];
     ChangesetItem *item = m_items[id];
     std::cerr << "Looking at " << id.toStdString() << std::endl;
 
+    foreach (QString parentId, cs->parents()) {
+	if (!m_changesets.contains(parentId)) continue;
+	if (!m_handled.contains(parentId)) {
+	    layoutCol(parentId);
+	}
+    }
+
     int col = 0;
+    int row = item->row();
+    QString branch = cs->branch();
     int nparents = cs->parents().size();
+    QString parentId;
+    int parentsOnSameBranch = 0;
 
-    if (nparents > 0) {
-	bool preferParentCol = true;
-	foreach (QString parentId, cs->parents()) {
+    switch (nparents) {
 
-	    if (!m_idCsetMap.contains(parentId)) continue;
-	    if (!m_items.contains(parentId)) continue;
+    case 0:
+	col = m_branchHomes[cs->branch()];
+	col = findAvailableColumn(row, col, true);
+	break;
 
-	    if (nparents == 1) {
-		// when introducing a new branch, aim _not_ to
-		// position child on the same column as parent
-		Changeset *parent = m_idCsetMap[parentId];
-		if (parent->branch() != cs->branch()) {
-		    preferParentCol = false;
-		}
-	    }		
+    case 1:
+	parentId = cs->parents()[0];
 
-	    if (!m_handled.contains(parentId)) {
-		layoutCol(parentId);
-	    }
-
-	    ChangesetItem *parentItem = m_items[parentId];
-	    col += parentItem->column();
+	if (!m_changesets.contains(parentId) ||
+	    m_changesets[parentId]->branch() != branch) {
+	    // new branch
+	    col = m_branchHomes[branch];
+	} else {
+	    col = m_items[parentId]->column();
 	}
 
-	col /= cs->parents().size();
-	col = findAvailableColumn(item->row(), col, preferParentCol);
-	m_alloc[item->row()].insert(col);
+	col = findAvailableColumn(row, col, true);
+	break;
+
+    case 2:
+	// a merge: behave differently if parents are both on the same
+	// branch (we also want to behave differently for nodes that
+	// have multiple children on the same branch -- spreading them
+	// out rather than having affinity to a specific branch)
+
+	foreach (QString parentId, cs->parents()) {
+	    if (!m_changesets.contains(parentId)) continue;
+	    if (m_changesets[parentId]->branch() == branch) {
+		ChangesetItem *parentItem = m_items[parentId];
+		col += parentItem->column();
+		parentsOnSameBranch++;
+	    }
+	}
+
+	if (parentsOnSameBranch > 0) {
+	    col /= parentsOnSameBranch;
+	    col = findAvailableColumn(item->row(), col, true);
+	} else {
+	    col = findAvailableColumn(item->row(), col, false);
+	}
+	break;
     }
 
     std::cerr << "putting " << cs->id().toStdString() << " at col " << col << std::endl;
 
+    m_alloc[row].insert(col);
     item->setColumn(col);
-    item->setX(col * 100);
     m_handled.insert(id);
 }
 
+bool
+Grapher::rangesConflict(const Range &r1, const Range &r2)
+{
+    // allow some additional space at edges.  we really ought also to
+    // permit space at the end of a branch up to the point where the
+    // merge happens
+    int a1 = r1.first - 2, b1 = r1.second + 2;
+    int a2 = r2.first - 2, b2 = r2.second + 2;
+    if (a1 > b2 || b1 < a2) return false;
+    if (a2 > b1 || b2 < a1) return false;
+    return true;
+}
+
+void
+Grapher::allocateBranchHomes(Changesets csets)
+{
+    foreach (Changeset *cs, csets) {
+	QString branch = cs->branch();
+	ChangesetItem *item = m_items[cs->id()];
+	if (!item) continue;
+	int row = item->row();
+	if (!m_branchRanges.contains(branch)) {
+	    m_branchRanges[branch] = Range(row, row);
+	} else {
+	    Range p = m_branchRanges[branch];
+	    if (row < p.first) p.first = row;
+	    if (row > p.second) p.second = row;
+	    m_branchRanges[branch] = p;
+	}
+    }
+
+    m_branchHomes[""] = 0;
+
+    foreach (QString branch, m_branchRanges.keys()) {
+	if (branch == "") continue;
+	QSet<int> taken;
+	taken.insert(0);
+	Range myRange = m_branchRanges[branch];
+	foreach (QString other, m_branchRanges.keys()) {
+	    if (other == branch || other == "") continue;
+	    Range otherRange = m_branchRanges[other];
+	    if (rangesConflict(myRange, otherRange)) {
+		if (m_branchHomes.contains(other)) {
+		    taken.insert(m_branchHomes[other]);
+		}
+	    }
+	}
+	int home = 2;
+	while (taken.contains(home)) {
+	    if (home > 0) home = -home;
+	    else home = -(home-2);
+	}
+	m_branchHomes[branch] = home;
+    }
+
+    foreach (QString branch, m_branchRanges.keys()) {
+	std::cerr << branch.toStdString() << ": " << m_branchRanges[branch].first << " - " << m_branchRanges[branch].second << ", home " << m_branchHomes[branch] << std::endl;
+    }
+}
+
 void
 Grapher::layout(Changesets csets)
 {
-    m_idCsetMap.clear();
+    m_changesets.clear();
     m_items.clear();
     m_alloc.clear();
+    m_branchHomes.clear();
 
     foreach (Changeset *cs, csets) {
 
@@ -146,11 +234,11 @@
 	if (id == "") {
 	    throw LayoutException("Changeset has no ID");
 	}
-	if (m_idCsetMap.contains(id)) {
+	if (m_changesets.contains(id)) {
 	    throw LayoutException(QString("Duplicate changeset ID %1").arg(id));
 	}
 
-	m_idCsetMap[id] = cs;
+	m_changesets[id] = cs;
 
         ChangesetItem *item = new ChangesetItem(cs);
         item->setX(0);
@@ -159,6 +247,18 @@
         m_scene->addItem(item);
     }
 
+    foreach (Changeset *cs, csets) {
+	QString id = cs->id();
+	ChangesetItem *item = m_items[id];
+	foreach (QString parentId, cs->parents()) {
+	    if (!m_items.contains(parentId)) continue;
+	    ConnectionItem *conn = new ConnectionItem();
+	    conn->setChild(item);
+	    conn->setParent(m_items[parentId]);
+	    m_scene->addItem(conn);
+	}
+    }
+
     // Layout in reverse order, i.e. forward chronological order.
     // This ensures that parents will normally be laid out before
     // their children -- though we can recurse from layout() if we
@@ -167,11 +267,14 @@
     for (int i = csets.size() - 1; i >= 0; --i) {
 	layoutRow(csets[i]->id());
     }
+
+    allocateBranchHomes(csets);
+
     m_handled.clear();
     for (int i = csets.size() - 1; i >= 0; --i) {
 	layoutCol(csets[i]->id());
     }
-
+/*
     foreach (Changeset *cs, csets) {
 	QString id = cs->id();
 	if (!m_items.contains(id)) continue;
@@ -185,5 +288,6 @@
 	    m_scene->addItem(line);
 	}
     }
+*/
 }
 
diff -r 4286836bb3c9 -r bd3accba9b3f grapher.h
--- a/grapher.h	Wed Nov 10 12:44:11 2010 +0000
+++ b/grapher.h	Wed Nov 10 17:11:41 2010 +0000
@@ -6,6 +6,7 @@
 
 #include <QSet>
 #include <QMap>
+#include <QPair>
 
 #include <exception>
 
@@ -28,14 +29,10 @@
     };
 
 private:
-    void layoutRow(QString id);
-    void layoutCol(QString id);
-    int findAvailableColumn(int row, int parent, bool preferParentCol);
-
     QGraphicsScene *m_scene;
 
     typedef QMap<QString, Changeset *> IdChangesetMap;
-    IdChangesetMap m_idCsetMap;
+    IdChangesetMap m_changesets;
 
     typedef QMap<QString, ChangesetItem *> IdItemMap;
     IdItemMap m_items;
@@ -44,8 +41,21 @@
     typedef QMap<int, ColumnSet> GridAlloc;
     GridAlloc m_alloc;
 
+    typedef QPair<int, int> Range;
+    typedef QMap<QString, Range> BranchRangeMap;
+    BranchRangeMap m_branchRanges;
+
+    typedef QMap<QString, int> BranchColumnMap;
+    BranchColumnMap m_branchHomes;
+
     typedef QSet<QString> IdSet;
     IdSet m_handled;
+
+    void layoutRow(QString id);
+    void layoutCol(QString id);
+    void allocateBranchHomes(Changesets csets);
+    bool rangesConflict(const Range &r1, const Range &r2);
+    int findAvailableColumn(int row, int parent, bool preferParentCol);
 };
 
 #endif 
diff -r 4286836bb3c9 -r bd3accba9b3f hgexplorer.pro
--- a/hgexplorer.pro	Wed Nov 10 12:44:11 2010 +0000
+++ b/hgexplorer.pro	Wed Nov 10 17:11:41 2010 +0000
@@ -17,7 +17,8 @@
     changesetitem.h \
     logparser.h \
     panner.h \
-    panned.h
+    panned.h \
+    connectionitem.h
 SOURCES = main.cpp \
     mainwindow.cpp \
     hgexpwidget.cpp \
@@ -29,7 +30,8 @@
     changesetitem.cpp \
     logparser.cpp \
     panner.cpp \
-    panned.cpp
+    panned.cpp \
+    connectionitem.cpp
 
 # ! [0]
 RESOURCES = hgexplorer.qrc
@@ -37,4 +39,4 @@
     RC_FILE = hgexplorer.rc
 }
 
-QT += network
+QT += network opengl
diff -r 4286836bb3c9 -r bd3accba9b3f panned.cpp
--- a/panned.cpp	Wed Nov 10 12:44:11 2010 +0000
+++ b/panned.cpp	Wed Nov 10 17:11:41 2010 +0000
@@ -18,11 +18,14 @@
 #include "panned.h"
 
 #include <QScrollBar>
+#include <QGLWidget>
 
 #include <iostream>
 
 Panned::Panned()
 {
+//    setViewport(new QGLWidget(QGLFormat(QGL::SampleBuffers)));
+    setRenderHints(QPainter::Antialiasing);
 }
 
 void
diff -r 4286836bb3c9 -r bd3accba9b3f panner.cpp
--- a/panner.cpp	Wed Nov 10 12:44:11 2010 +0000
+++ b/panner.cpp	Wed Nov 10 17:11:41 2010 +0000
@@ -21,6 +21,7 @@
 #include <QPolygon>
 #include <QMouseEvent>
 #include <QColor>
+#include <QGLWidget>
 
 #include <iostream>
 
@@ -33,6 +34,7 @@
 Panner::Panner() :
     m_clicked(false)
 {
+//    setViewport(new QGLWidget());
     setHorizontalScrollBarPolicy(Qt::ScrollBarAlwaysOff);
     setVerticalScrollBarPolicy(Qt::ScrollBarAlwaysOff);
     setOptimizationFlags(QGraphicsView::DontSavePainterState);