Chris@44: 
Chris@44: #include "grapher.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:     }
cannam@45:     if (!m_idCsetMap.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:     }
cannam@45:     Changeset *cs = m_idCsetMap[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: 
cannam@45: 	    if (!m_idCsetMap.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);
Chris@44:     item->setY(row * 100);
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:     }
cannam@45:     if (!m_idCsetMap.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:     }
cannam@45:     Changeset *cs = m_idCsetMap[id];
cannam@45:     ChangesetItem *item = m_items[id];
cannam@45:     std::cerr << "Looking at " << id.toStdString() << std::endl;
cannam@45: 
cannam@45:     int col = 0;
cannam@45:     int nparents = cs->parents().size();
cannam@45: 
cannam@45:     if (nparents > 0) {
cannam@45: 	bool preferParentCol = true;
cannam@45: 	foreach (QString parentId, cs->parents()) {
cannam@45: 
cannam@45: 	    if (!m_idCsetMap.contains(parentId)) continue;
cannam@45: 	    if (!m_items.contains(parentId)) continue;
cannam@45: 
cannam@45: 	    if (nparents == 1) {
cannam@45: 		// when introducing a new branch, aim _not_ to
cannam@45: 		// position child on the same column as parent
cannam@45: 		Changeset *parent = m_idCsetMap[parentId];
cannam@45: 		if (parent->branch() != cs->branch()) {
cannam@45: 		    preferParentCol = false;
cannam@45: 		}
cannam@45: 	    }		
cannam@45: 
cannam@45: 	    if (!m_handled.contains(parentId)) {
cannam@45: 		layoutCol(parentId);
cannam@45: 	    }
cannam@45: 
cannam@45: 	    ChangesetItem *parentItem = m_items[parentId];
cannam@45: 	    col += parentItem->column();
Chris@44: 	}
cannam@45: 
cannam@45: 	col /= cs->parents().size();
cannam@45: 	col = findAvailableColumn(item->row(), col, preferParentCol);
cannam@45: 	m_alloc[item->row()].insert(col);
Chris@44:     }
Chris@44: 
cannam@45:     std::cerr << "putting " << cs->id().toStdString() << " at col " << col << std::endl;
cannam@45: 
cannam@45:     item->setColumn(col);
cannam@45:     item->setX(col * 100);
cannam@45:     m_handled.insert(id);
cannam@45: }
cannam@45: 
cannam@45: void
cannam@45: Grapher::layout(Changesets csets)
cannam@45: {
cannam@45:     m_idCsetMap.clear();
cannam@45:     m_items.clear();
cannam@45:     m_alloc.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: 	}
cannam@45: 	if (m_idCsetMap.contains(id)) {
cannam@45: 	    throw LayoutException(QString("Duplicate changeset ID %1").arg(id));
cannam@45: 	}
cannam@45: 
cannam@45: 	m_idCsetMap[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: 
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:     }
cannam@45:     m_handled.clear();
cannam@45:     for (int i = csets.size() - 1; i >= 0; --i) {
cannam@45: 	layoutCol(csets[i]->id());
cannam@45:     }
cannam@45: 
cannam@45:     foreach (Changeset *cs, csets) {
cannam@45: 	QString id = cs->id();
cannam@45: 	if (!m_items.contains(id)) continue;
cannam@45: 	ChangesetItem *me = m_items[id];
cannam@45: 	foreach (QString parentId, cs->parents()) {
cannam@45: 	    if (!m_items.contains(parentId)) continue;
cannam@45: 	    ChangesetItem *parent = m_items[parentId];
cannam@45: 	    QGraphicsLineItem *line = new QGraphicsLineItem;
cannam@45: 	    line->setLine(me->x() + 25, me->y() + 50,
cannam@45: 			  parent->x() + 25, parent->y());
cannam@45: 	    m_scene->addItem(line);
cannam@45: 	}
Chris@44:     }
Chris@44: }
Chris@44: