[Avida-SVN] r2363 - development/source/tools

[brysonda at myxo.css.msu.edu]

Author: brysonda
Date: 2008-02-22 19:33:31 -0500 (Fri, 22 Feb 2008)
New Revision: 2363

Modified:
   development/source/tools/cWeightedIndex.cc
   development/source/tools/cWeightedIndex.h
Log:
Change the behavior of cWeightedIndex to avoid subtree/parent node weight mismatches that can occur due to floating point rounding error.  Extreme differences in merit magnitude can cause cascade differences in subtree weighting, leading to gaps within the tree.

Addresses [ticket:9 trac://9].

Modified: development/source/tools/cWeightedIndex.cc
===================================================================
--- development/source/tools/cWeightedIndex.cc	2008-02-22 20:02:31 UTC (rev 2362)
+++ development/source/tools/cWeightedIndex.cc	2008-02-23 00:33:31 UTC (rev 2363)
@@ -43,21 +43,40 @@
 {
 }
 
-void cWeightedIndex::AdjustSubtree(int id, double weight_change)
-{
-  subtree_weight[id] += weight_change;
-  if(subtree_weight[id] < 0.0001)  //bb: added to catch round off error
-    subtree_weight[id] = 0.0;
-  if (id != 0) {
-    AdjustSubtree(GetParent(id), weight_change);
-  }
-}
 
+// The following method is subject to floating point rounding errors that can lead to weight mismatches
+// Instead, as implemented below, directly add the subtree weights to ensure that this doesn't happen. @DMB
+
+//void cWeightedIndex::AdjustSubtree(int id, double weight_change)
+//{
+//  subtree_weight[id] += weight_change;
+//  if(subtree_weight[id] < 0.0001)  //bb: added to catch round off error
+//    subtree_weight[id] = 0.0;
+//  if (id != 0) {
+//    AdjustSubtree(GetParent(id), weight_change);
+//  }
+//}
+//
+//void cWeightedIndex::SetWeight(int id, double in_weight)
+//{
+//  const double weight_change = in_weight - item_weight[id];
+//  item_weight[id] = in_weight;
+//  AdjustSubtree(id, weight_change);
+//}
+  
 void cWeightedIndex::SetWeight(int id, double in_weight)
 {
-  const double weight_change = in_weight - item_weight[id];
   item_weight[id] = in_weight;
-  AdjustSubtree(id, weight_change);
+  
+  while (true) {
+    const int left_id = GetLeftChild(id);
+    const int right_id = GetRightChild(id);
+    const double left_subtree = (left_id >= size) ? 0.0 : subtree_weight[left_id];
+    const double right_subtree = (right_id >= size) ? 0.0 : subtree_weight[right_id];
+    subtree_weight[id] = item_weight[id] + left_subtree + right_subtree;
+    if (id == 0) break;
+    id = GetParent(id);
+  }
 }
 
 // This order of testing is about 10% faster than the one used below.

Modified: development/source/tools/cWeightedIndex.h
===================================================================
--- development/source/tools/cWeightedIndex.h	2008-02-22 20:02:31 UTC (rev 2362)
+++ development/source/tools/cWeightedIndex.h	2008-02-23 00:33:31 UTC (rev 2363)
@@ -47,8 +47,6 @@
   tArray<double> subtree_weight;
 
   
-  void AdjustSubtree(int id, double weight_change);
-  
   cWeightedIndex(); // @not_implemented
   
 public: