c4def6d886a612e0a7022beec49638cafce3af59
ceisenhart
  Mon Mar 7 12:32:20 2016 -0800
Adding in a sibling comparison function to the multi threaded function, refs #16216

diff --git src/lib/hacTree.c src/lib/hacTree.c
index c303cca..1abe93c 100644
--- src/lib/hacTree.c
+++ src/lib/hacTree.c
@@ -427,42 +427,45 @@
 *retNodeA = closestA;
 *retNodeB = closestB;
 return closestDistance;
 }
 
 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;
 dlAddTail(list, node);
 }
 
 struct hacTree *hacTreeMultiThread(int threadCount, struct slList *itemList, 
-		    struct lm *localMem, hacDistanceFunction *distF, hacMergeFunction *mergeF,
+		    struct lm *localMem, hacDistanceFunction *distF, 
+		    hacMergeFunction *mergeF, hacSibCmpFunction *cmpF,
 		    void *extraData, struct hash *precalcDistanceHash)
 /* Construct hacTree minimizing number of merges called, and doing distance calls
  * in parallel when possible.   Do a lmCleanup(localMem) to free returned tree. 
  * The inputs are
  *	threadCount - number of threads - at least one, recommended no more than 15
  *	itemList - list of items to tree up.  Format can vary, but must start with a
  *	           pointer to next item in list.
  *	localMem - memory pool where hacTree and a few other things are allocated from
  *	distF - function that calculates distance between two items, passed items and extraData
  *	mergeF - function that creates a new item in same format as itemList from two passed
  *	         in items and the extraData.  Typically does average of two input items
+ *	cmpF - function that compares two items being merged to decide who becomes left child
+ *		and who is the right child. 
  *	extraData - parameter passed through to distF and mergeF, otherwise unused, may be NULL
  *	precalcDistanceHash - a hash containing at least some of the pairwise distances
  *	            between items on itemList, set with hacTreeDistanceHashAdd. 
  *	            As a side effect this hash will be expanded to include all distances 
  *	            including those between intermediate nodes. */
 {
 /* 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;
@@ -470,34 +473,51 @@
     ht->itemOrCluster = item;
     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 */
     struct dlNode *aNode, *bNode;
     double distance = pairParallel(&remaining, distanceHash, distF, extraData, threadCount,
 	&aNode, &bNode);
 
     /* Allocated new hacTree item for them and fill it in with a merged value. */
-    struct hacTree *ht;
+    struct hacTree *ht, *left, *right;
     lmAllocVar(localMem, ht);
-    struct hacTree *left = ht->left = aNode->val;
-    struct hacTree *right = ht->right = bNode->val;
+    
+    /* Check if the user provided a function to determine sibling perference */ 
+    
+    if (cmpF != NULL)
+	{
+	if (cmpF(((struct hacTree *)aNode->val)->itemOrCluster, ((struct hacTree *)bNode->val)->itemOrCluster, extraData))
+	    {
+	    left = ht->left = aNode->val;
+	    right = ht->right = bNode->val;
+	    }
+	else{
+	    left = ht->left = bNode->val;
+	    right = ht->right = aNode->val;
+	    }
+	}
+    else{
+	left = ht->left = aNode->val;
+	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 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);
     }