Chris@44: 
Chris@44: #include "grapher.h"
Chris@46: #include "connectionitem.h"
Chris@44: 
cannam@45: #include <QGraphicsScene>
Chris@44: 
Chris@44: #include <iostream>
Chris@44: 
cannam@45: int
cannam@45: Grapher::findAvailableColumn(int row, int parent, bool preferParentCol)
cannam@45: {
cannam@45:     int col = parent;
cannam@45:     if (preferParentCol) {
cannam@45: 	if (!m_alloc[row].contains(col)) {
cannam@45: 	    return col;
cannam@45: 	}
cannam@45:     }
cannam@45:     while (col > 0) {
cannam@45: 	if (!m_alloc[row].contains(--col)) return col;
cannam@45:     }
cannam@45:     while (col < 0) {
cannam@45: 	if (!m_alloc[row].contains(++col)) return col;
cannam@45:     }
cannam@45:     col = parent;
cannam@45:     int sign = (col < 0 ? -1 : 1);
cannam@45:     while (1) {
cannam@45: 	col += sign;
cannam@45: 	if (!m_alloc[row].contains(col)) return col;
cannam@45:     }
cannam@45: }
Chris@44: 
cannam@45: void
cannam@45: Grapher::layoutRow(QString id)
Chris@44: {
cannam@45:     if (m_handled.contains(id)) {
cannam@45: 	return;
Chris@44:     }
Chris@46:     if (!m_changesets.contains(id)) {
cannam@45: 	throw LayoutException(QString("Changeset %1 not in ID map").arg(id));
Chris@44:     }
cannam@45:     if (!m_items.contains(id)) {
cannam@45: 	throw LayoutException(QString("Changeset %1 not in item map").arg(id));
Chris@44:     }
Chris@46:     Changeset *cs = m_changesets[id];
cannam@45:     ChangesetItem *item = m_items[id];
cannam@45:     std::cerr << "Looking at " << id.toStdString() << std::endl;
cannam@45: 
Chris@44:     int row = 0;
cannam@45:     int nparents = cs->parents().size();
cannam@45: 
cannam@45:     if (nparents > 0) {
Chris@44: 	bool haveRow = false;
Chris@44: 	foreach (QString parentId, cs->parents()) {
cannam@45: 
Chris@46: 	    if (!m_changesets.contains(parentId)) continue;
cannam@45: 	    if (!m_items.contains(parentId)) continue;
cannam@45: 
cannam@45: 	    if (!m_handled.contains(parentId)) {
cannam@45: 		layoutRow(parentId);
cannam@45: 	    }
cannam@45: 
cannam@45: 	    ChangesetItem *parentItem = m_items[parentId];
Chris@44: 	    if (!haveRow || parentItem->row() < row) {
Chris@44: 		row = parentItem->row();
Chris@44: 		haveRow = true;
Chris@44: 	    }
Chris@44: 	}
Chris@44: 	row = row - 1;
cannam@45:     }
cannam@45: 
cannam@45:     std::cerr << "putting " << cs->id().toStdString() << " at row " << row 
cannam@45: 	      << std::endl;
cannam@45: 
Chris@44:     item->setRow(row);
cannam@45:     m_handled.insert(id);
Chris@44: }
Chris@44: 
Chris@44: void
cannam@45: Grapher::layoutCol(QString id)
Chris@44: {
cannam@45:     if (m_handled.contains(id)) {
cannam@45: 	std::cerr << "Already looked at " << id.toStdString() << std::endl;
cannam@45: 	return;
cannam@45:     }
Chris@46:     if (!m_changesets.contains(id)) {
cannam@45: 	throw LayoutException(QString("Changeset %1 not in ID map").arg(id));
cannam@45:     }
cannam@45:     if (!m_items.contains(id)) {
cannam@45: 	throw LayoutException(QString("Changeset %1 not in item map").arg(id));
cannam@45:     }
Chris@46:     Changeset *cs = m_changesets[id];
cannam@45:     ChangesetItem *item = m_items[id];
cannam@45:     std::cerr << "Looking at " << id.toStdString() << std::endl;
cannam@45: 
Chris@46:     foreach (QString parentId, cs->parents()) {
Chris@46: 	if (!m_changesets.contains(parentId)) continue;
Chris@46: 	if (!m_handled.contains(parentId)) {
Chris@46: 	    layoutCol(parentId);
Chris@46: 	}
Chris@46:     }
Chris@46: 
Chris@47:     // Parent may have layed out child in the recursive call
Chris@47:     if (m_handled.contains(id)) {
Chris@47: 	std::cerr << "Looks like we've dealt with " << id.toStdString() << std::endl;
Chris@47: 	return;
Chris@47:     }
Chris@47: 
cannam@45:     int col = 0;
Chris@46:     int row = item->row();
Chris@46:     QString branch = cs->branch();
Chris@47: 
cannam@45:     int nparents = cs->parents().size();
Chris@46:     QString parentId;
Chris@46:     int parentsOnSameBranch = 0;
cannam@45: 
Chris@46:     switch (nparents) {
cannam@45: 
Chris@46:     case 0:
Chris@46: 	col = m_branchHomes[cs->branch()];
Chris@46: 	col = findAvailableColumn(row, col, true);
Chris@46: 	break;
cannam@45: 
Chris@46:     case 1:
Chris@46: 	parentId = cs->parents()[0];
cannam@45: 
Chris@46: 	if (!m_changesets.contains(parentId) ||
Chris@46: 	    m_changesets[parentId]->branch() != branch) {
Chris@46: 	    // new branch
Chris@46: 	    col = m_branchHomes[branch];
Chris@46: 	} else {
Chris@46: 	    col = m_items[parentId]->column();
Chris@44: 	}
cannam@45: 
Chris@46: 	col = findAvailableColumn(row, col, true);
Chris@46: 	break;
Chris@46: 
Chris@46:     case 2:
Chris@46: 	// a merge: behave differently if parents are both on the same
Chris@46: 	// branch (we also want to behave differently for nodes that
Chris@46: 	// have multiple children on the same branch -- spreading them
Chris@46: 	// out rather than having affinity to a specific branch)
Chris@46: 
Chris@46: 	foreach (QString parentId, cs->parents()) {
Chris@46: 	    if (!m_changesets.contains(parentId)) continue;
Chris@46: 	    if (m_changesets[parentId]->branch() == branch) {
Chris@46: 		ChangesetItem *parentItem = m_items[parentId];
Chris@46: 		col += parentItem->column();
Chris@46: 		parentsOnSameBranch++;
Chris@46: 	    }
Chris@46: 	}
Chris@46: 
Chris@46: 	if (parentsOnSameBranch > 0) {
Chris@46: 	    col /= parentsOnSameBranch;
Chris@46: 	    col = findAvailableColumn(item->row(), col, true);
Chris@46: 	} else {
Chris@46: 	    col = findAvailableColumn(item->row(), col, false);
Chris@46: 	}
Chris@46: 	break;
Chris@44:     }
Chris@44: 
cannam@45:     std::cerr << "putting " << cs->id().toStdString() << " at col " << col << std::endl;
cannam@45: 
Chris@46:     m_alloc[row].insert(col);
cannam@45:     item->setColumn(col);
cannam@45:     m_handled.insert(id);
Chris@47: 
Chris@47:     int nchildren = cs->children().size();
Chris@47:     if (nchildren > 1) {
Chris@47: 	// Normally the children will lay out themselves.  We just
Chris@47: 	// want to handle the case where exactly two children have the
Chris@47: 	// same branch as us, because we can handle that neatly
Chris@47: 	QList<QString> special;
Chris@47: 	foreach (QString childId, cs->children()) {
Chris@47: 	    if (!m_changesets.contains(childId)) continue;
Chris@47: 	    Changeset *child = m_changesets[childId];
Chris@47: 	    if (child->branch() == branch &&
Chris@47: 		child->parents().size() == 1) {
Chris@47: 		special.push_back(childId);
Chris@47: 	    }
Chris@47: 	}
Chris@47: 	if (special.size() == 2) {
Chris@47: 	    m_items[special[0]]->setColumn
Chris@47: 		(findAvailableColumn(item->row() - 1, col - 1, true));
Chris@47: 	    m_items[special[1]]->setColumn
Chris@47: 		(findAvailableColumn(item->row() - 1, col + 1, true));
Chris@47: 	    m_handled.insert(special[0]);
Chris@47: 	    m_handled.insert(special[1]);
Chris@47: 	}
Chris@47:     }
cannam@45: }
cannam@45: 
Chris@46: bool
Chris@46: Grapher::rangesConflict(const Range &r1, const Range &r2)
Chris@46: {
Chris@46:     // allow some additional space at edges.  we really ought also to
Chris@46:     // permit space at the end of a branch up to the point where the
Chris@46:     // merge happens
Chris@46:     int a1 = r1.first - 2, b1 = r1.second + 2;
Chris@46:     int a2 = r2.first - 2, b2 = r2.second + 2;
Chris@46:     if (a1 > b2 || b1 < a2) return false;
Chris@46:     if (a2 > b1 || b2 < a1) return false;
Chris@46:     return true;
Chris@46: }
Chris@46: 
Chris@46: void
Chris@46: Grapher::allocateBranchHomes(Changesets csets)
Chris@46: {
Chris@46:     foreach (Changeset *cs, csets) {
Chris@46: 	QString branch = cs->branch();
Chris@46: 	ChangesetItem *item = m_items[cs->id()];
Chris@46: 	if (!item) continue;
Chris@46: 	int row = item->row();
Chris@46: 	if (!m_branchRanges.contains(branch)) {
Chris@46: 	    m_branchRanges[branch] = Range(row, row);
Chris@46: 	} else {
Chris@46: 	    Range p = m_branchRanges[branch];
Chris@46: 	    if (row < p.first) p.first = row;
Chris@46: 	    if (row > p.second) p.second = row;
Chris@46: 	    m_branchRanges[branch] = p;
Chris@46: 	}
Chris@46:     }
Chris@46: 
Chris@46:     m_branchHomes[""] = 0;
Chris@46: 
Chris@46:     foreach (QString branch, m_branchRanges.keys()) {
Chris@46: 	if (branch == "") continue;
Chris@46: 	QSet<int> taken;
Chris@46: 	taken.insert(0);
Chris@46: 	Range myRange = m_branchRanges[branch];
Chris@46: 	foreach (QString other, m_branchRanges.keys()) {
Chris@46: 	    if (other == branch || other == "") continue;
Chris@46: 	    Range otherRange = m_branchRanges[other];
Chris@46: 	    if (rangesConflict(myRange, otherRange)) {
Chris@46: 		if (m_branchHomes.contains(other)) {
Chris@46: 		    taken.insert(m_branchHomes[other]);
Chris@46: 		}
Chris@46: 	    }
Chris@46: 	}
Chris@47: 	int home = 3;
Chris@46: 	while (taken.contains(home)) {
Chris@46: 	    if (home > 0) home = -home;
Chris@47: 	    else home = -(home-3);
Chris@46: 	}
Chris@46: 	m_branchHomes[branch] = home;
Chris@46:     }
Chris@46: 
Chris@46:     foreach (QString branch, m_branchRanges.keys()) {
Chris@46: 	std::cerr << branch.toStdString() << ": " << m_branchRanges[branch].first << " - " << m_branchRanges[branch].second << ", home " << m_branchHomes[branch] << std::endl;
Chris@46:     }
Chris@46: }
Chris@46: 
cannam@45: void
cannam@45: Grapher::layout(Changesets csets)
cannam@45: {
Chris@46:     m_changesets.clear();
cannam@45:     m_items.clear();
cannam@45:     m_alloc.clear();
Chris@46:     m_branchHomes.clear();
cannam@45: 
Chris@44:     foreach (Changeset *cs, csets) {
cannam@45: 
cannam@45: 	QString id = cs->id();
cannam@45: 	std::cerr << id.toStdString() << std::endl;
cannam@45: 
cannam@45: 	if (id == "") {
cannam@45: 	    throw LayoutException("Changeset has no ID");
cannam@45: 	}
Chris@46: 	if (m_changesets.contains(id)) {
cannam@45: 	    throw LayoutException(QString("Duplicate changeset ID %1").arg(id));
cannam@45: 	}
cannam@45: 
Chris@46: 	m_changesets[id] = cs;
cannam@45: 
cannam@45:         ChangesetItem *item = new ChangesetItem(cs);
cannam@45:         item->setX(0);
cannam@45:         item->setY(0);
cannam@45: 	m_items[id] = item;
cannam@45:         m_scene->addItem(item);
cannam@45:     }
cannam@45: 
Chris@46:     foreach (Changeset *cs, csets) {
Chris@46: 	QString id = cs->id();
Chris@46: 	ChangesetItem *item = m_items[id];
Chris@46: 	foreach (QString parentId, cs->parents()) {
Chris@47: 	    if (!m_changesets.contains(parentId)) continue;
Chris@47: 	    Changeset *parent = m_changesets[parentId];
Chris@47: 	    parent->addChild(id);
Chris@46: 	    ConnectionItem *conn = new ConnectionItem();
Chris@46: 	    conn->setChild(item);
Chris@46: 	    conn->setParent(m_items[parentId]);
Chris@46: 	    m_scene->addItem(conn);
Chris@46: 	}
Chris@46:     }
Chris@46: 
cannam@45:     // Layout in reverse order, i.e. forward chronological order.
cannam@45:     // This ensures that parents will normally be laid out before
cannam@45:     // their children -- though we can recurse from layout() if we
cannam@45:     // find any weird exceptions
cannam@45:     m_handled.clear();
cannam@45:     for (int i = csets.size() - 1; i >= 0; --i) {
cannam@45: 	layoutRow(csets[i]->id());
cannam@45:     }
Chris@46: 
Chris@46:     allocateBranchHomes(csets);
Chris@46: 
cannam@45:     m_handled.clear();
cannam@45:     for (int i = csets.size() - 1; i >= 0; --i) {
cannam@45: 	layoutCol(csets[i]->id());
cannam@45:     }
Chris@44: }
Chris@44: