d4a596545a31f52e588e84a6645ba19f54d1b99d
kent
  Wed Aug 27 14:22:01 2014 -0700
Changing the new hacTree code so that it creates trees in same order (I hope) as old code.  Previously it was inverting some branches.
diff --git src/lib/hacTree.c src/lib/hacTree.c
index 9e197b8..013a621 100644
--- src/lib/hacTree.c
+++ src/lib/hacTree.c
@@ -315,83 +315,88 @@
 	     }
 	double d = *pd;
 	if (d < closestDistance)
 	    {
 	    closestDistance = d;
 	    closestA = aNode;
 	    closestB = bNode;
 	    }
 	}
     }
 *retNodeA = closestA;
 *retNodeB = closestB;
 return closestDistance;
 }
 
-static void lmDlAddValHead(struct lm *lm, struct dlList *list, void *val)
+static void lmDlAddValTail(struct lm *lm, struct dlList *list, void *val)
 /* Allocate new dlNode out of lm, initialize it with val, and add it to end of list */
 {
 struct dlNode *node;
 lmAllocVar(lm, node);
 node->val = val;
-dlAddHead(list, node);
+dlAddTail(list, node);
 }
 
 struct hacTree *hacTreeVirtualPairing(struct slList *itemList, struct lm *localMem,
 				 hacDistanceFunction *distF, hacMergeFunction *mergeF,
 				 void *extraData, hacPairingFunction *pairingF,
 				 struct hash *precalcDistanceHash)
 /* Construct hacTree using a method that will minimize the number of calls to
  * the distance and merge functions, assuming they are expensive.  Do a lmCleanup(localMem)
  * to free the returned tree. */
 {
 /* Make up a doubly-linked list in 'remaining' with all items in it */
 struct dlList remaining;
 dlListInit(&remaining);
 struct slList *item;
 int count = 0;
 struct hash *distanceHash = (precalcDistanceHash ? precalcDistanceHash : hashNew(0));
 for (item = itemList; item != NULL; item = item->next)
     {
     struct hacTree *ht;
     lmAllocVar(localMem, ht);
     ht->itemOrCluster = item;
-    lmDlAddValHead(localMem, &remaining, ht);
+    lmDlAddValTail(localMem, &remaining, ht);
     count += 1;
     }
 
 /* Loop through finding closest and merging until only one node left on remaining. */
 int i;
 for (i=1; i<count; ++i)
     {
-    /* Find closest pair and take them off of remaining list */
+    /* Find closest pair */
     struct dlNode *aNode, *bNode;
     double distance = pairingF(&remaining, distanceHash, distF, extraData, &aNode, &bNode);
-    dlRemove(aNode);
-    dlRemove(bNode);
 
     /* Allocated new hacTree item for them and fill it in with a merged value. */
     struct hacTree *ht;
     lmAllocVar(localMem, ht);
     struct hacTree *left = ht->left = aNode->val;
     struct hacTree *right = ht->right = bNode->val;
     left->parent = right->parent = ht;
     ht->itemOrCluster = mergeF(left->itemOrCluster, right->itemOrCluster, extraData);
     ht->childDistance = distance;
 
-    /* Put merged item onto remaining list. */
-    lmDlAddValHead(localMem, &remaining, ht);
+    /* Put merged item onto remaining list before first matching node in pair. */
+    struct dlNode *mergedNode;
+    lmAllocVar(localMem, mergedNode);
+    mergedNode->val = ht;
+    dlAddBefore(aNode, mergedNode);
+
+    /* Remove nodes we merged out */
+    dlRemove(aNode);
+    dlRemove(bNode);
     }
 
 /* Clean up and go home. */
 if (distanceHash != precalcDistanceHash)
     hashFree(&distanceHash);
 struct dlNode *lastNode = dlPopHead(&remaining);
 return lastNode->val;
 }
 
 struct hacTree *hacTreeForCostlyMerges(struct slList *itemList, struct lm *localMem,
 				 hacDistanceFunction *distF, hacMergeFunction *mergeF,
 				 void *extraData)
 /* Construct hacTree using a method that will minimize the number of calls to
  * the distance and merge functions, assuming they are expensive.  Do a lmCleanup(localMem)
  * to free the returned tree. */