comparison grapher.cpp @ 185:ec2baee80833

* Some rather uncertain modifications to grapher logic for branch homes -- try to place branches close to their "parent branches".
Have also experimented with placing popular branches closer to the centre; neither is definitively better.  Also, make changeset placement tend towards the branch home for the changeset

 #include "debug.h"
 #include "changesetscene.h"
 
 #include <iostream>
 
-int Grapher::findAvailableColumn(int row, int parent, bool preferParentCol)
+#include <QMultiMap>
+
+int Grapher::findAvailableColumn(int row, int parent, int sign,
+                                 bool preferParentCol)
 {
     int col = parent;
     if (preferParentCol) {
         if (isAvailable(row, col)) return col;
     }

     }
     while (col < 0) {
         if (isAvailable(row, ++col)) return col;
     }
     col = parent;
-    int sign = (col < 0 ? -1 : 1);
+    if (sign == 0) {
+        sign = (col < 0 ? -1 : 1);
+    }
     while (1) {
         col += sign;
         if (isAvailable(row, col)) return col;
     }
 }

     ChangesetItem *item = m_items[id];
 
     int col = 0;
     int row = item->row();
     QString branch = cs->branch();
+    int branchHome = m_branchHomes[branch];
 
     int nparents = cs->parents().size();
     QString parentId;
     int parentsOnSameBranch = 0;
 
     switch (nparents) {
 
     case 0:
-        col = m_branchHomes[cs->branch()];
-        col = findAvailableColumn(row, col, true);
+        col = findAvailableColumn(row, branchHome, 0, true);
         break;
 
     case 1:
         parentId = cs->parents()[0];
 

             col = m_branchHomes[branch];
         } else {
             col = m_items[parentId]->column();
         }
 
-        col = findAvailableColumn(row, col, true);
+        col = findAvailableColumn(row, col, branchHome - 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

             }
         }
 
         if (parentsOnSameBranch > 0) {
             col /= parentsOnSameBranch;
-            col = findAvailableColumn(item->row(), col, true);
+            col = findAvailableColumn(item->row(), col, 0, true);
         } else {
-            col = findAvailableColumn(item->row(), col, false);
+            col = findAvailableColumn(item->row(), col, 0, false);
         }
         break;
     }
 
     DEBUG << "putting " << cs->id().toStdString() << " at col " << col << endl;

     // given the same column as us (we already noted that its
     // connecting line would end at our row)
 
     if (m_uncommittedParents.contains(id)) {
         if (m_uncommittedParents[0] == id) {
-            int ucol = findAvailableColumn(row-1, col, true);
+            int ucol = findAvailableColumn(row-1, col, branchHome - col, true);
             m_uncommitted->setColumn(ucol);
             m_haveAllocatedUncommittedColumn = true;
         }
         // also, if the uncommitted item has a different branch from
         // any of its parents, tell it to show the branch

         if (special.size() == 2) {
             DEBUG << "handling split-in-two for children " << special[0] << " and " << special[1] << endl;
             for (int i = 0; i < 2; ++i) {
                 int off = i * 2 - 1; // 0 -> -1, 1 -> 1
                 ChangesetItem *it = m_items[special[i]];
-                it->setColumn(findAvailableColumn(it->row(), col + off, true));
+                it->setColumn(findAvailableColumn(it->row(), col + off, 0, true));
                 for (int r = row-1; r >= it->row(); --r) {
                     m_alloc[r].insert(it->column());
                 }
                 m_handled.insert(special[i]);
             }

     return true;
 }
 
 void Grapher::allocateBranchHomes(Changesets csets)
 {
-    foreach (Changeset *cs, csets) {
+    QMap<QString, int> branchCounts;
+    QMap<QString, QString> branchParents;
+
+    QStringList branches;
+
+    foreach (Changeset *cs, csets) {
+
         QString branch = cs->branch();
+
+        if (!branchCounts.contains(branch)) {
+            // Guess at the parent branch for this one which we
+            // haven't seen before. This is not entirely reliable, but
+            // it doesn't need to be
+            if (!cs->parents().empty()) {
+                QString firstParentId = cs->parents()[0];
+                if (m_changesets.contains(firstParentId)) {
+                    Changeset *firstParent = m_changesets[firstParentId];
+                    branchParents[branch] = firstParent->branch();
+                }
+            }
+            branches.push_back(branch);
+        }
+
+        branchCounts[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];

         }
     }
 
     m_branchHomes[""] = 0;
     m_branchHomes["default"] = 0;
-
-    foreach (QString branch, m_branchRanges.keys()) {
+/*
+    QStringList orderedBranches; // will be ordered by "popularity"
+
+    QMultiMap<int, QString> branchesByCount;
+    foreach (QString branch, branchCounts.keys()) {
+        branchesByCount.insert(branchCounts[branch], branch);
+    }
+    foreach (QString branch, branchesByCount) {
+        orderedBranches.push_front(branch);
+    }
+*/
+    int sign = -1;
+    
+    foreach (QString branch, branches) {
         if (branch == "") continue;
         QSet<int> taken;
         taken.insert(0);
         Range myRange = m_branchRanges[branch];
         foreach (QString other, m_branchRanges.keys()) {

                     taken.insert(m_branchHomes[other]);
                 }
             }
         }
         int home = 2;
+        QString parent = branchParents[branch];
+        if (parent != "" && parent != "default" &&
+            m_branchHomes.contains(parent)) {
+            home = m_branchHomes[parent];
+            if (home > 0) sign = 1;
+            else sign = -1;
+        } else {
+            sign = -sign;
+        }
         while (taken.contains(home)) {
-            if (home > 0) {
-                if (home % 2 == 1) {
-                    home = -home;
-                } else {
-                    home = home + 1;
-                }
-            } else {
-                if ((-home) % 2 == 1) {
-                    home = home + 1;
-                } else {
-                    home = -(home-2);
-                }
-            }
+            home = home + 2 * sign;
         }
         m_branchHomes[branch] = home;
     }
 
-    foreach (QString branch, m_branchRanges.keys()) {
-        DEBUG << branch.toStdString() << ": " << m_branchRanges[branch].first << " - " << m_branchRanges[branch].second << ", home " << m_branchHomes[branch] << endl;
+    foreach (QString branch, branches) {
+        DEBUG << branch << ": pop " << branchCounts[branch] << ", parent " << branchParents[branch] << ", range " << m_branchRanges[branch].first << " - " << m_branchRanges[branch].second << ", home " << m_branchHomes[branch] << endl;
     }
 }
 
 static bool
 compareChangesetsByDate(Changeset *const &a, Changeset *const &b)