+
+ /* Target node is unreachable */
+ return -1;
+}
+
+void FuncNode::add_failed_predicate(Predicate * pred)
+{
+ failed_predicates.add(pred);
+}
+
+/* Implement quick sort to sort leaves before assigning base scores */
+template<typename _Tp>
+static int partition(ModelVector<_Tp *> * arr, int low, int high)
+{
+ unsigned int pivot = (*arr)[high]->get_depth();
+ int i = low - 1;
+
+ for (int j = low; j <= high - 1; j++) {
+ if ( (*arr)[j]->get_depth() < pivot ) {
+ i++;
+ _Tp * tmp = (*arr)[i];
+ (*arr)[i] = (*arr)[j];
+ (*arr)[j] = tmp;
+ }
+ }
+
+ _Tp * tmp = (*arr)[i + 1];
+ (*arr)[i + 1] = (*arr)[high];
+ (*arr)[high] = tmp;
+
+ return i + 1;
+}
+
+/* Implement quick sort to sort leaves before assigning base scores */
+template<typename _Tp>
+static void quickSort(ModelVector<_Tp *> * arr, int low, int high)
+{
+ if (low < high) {
+ int pi = partition(arr, low, high);
+
+ quickSort(arr, low, pi - 1);
+ quickSort(arr, pi + 1, high);
+ }
+}
+
+void FuncNode::assign_initial_weight()
+{
+ PredSetIter * it = predicate_leaves.iterator();
+ leaves_tmp_storage.clear();
+
+ while (it->hasNext()) {
+ Predicate * pred = it->next();
+ double weight = 100.0 / sqrt(pred->get_expl_count() + pred->get_fail_count() + 1);
+ pred->set_weight(weight);
+ leaves_tmp_storage.push_back(pred);
+ }
+ delete it;
+
+ quickSort(&leaves_tmp_storage, 0, leaves_tmp_storage.size() - 1);
+
+ // assign scores for internal nodes;
+ while ( !leaves_tmp_storage.empty() ) {
+ Predicate * leaf = leaves_tmp_storage.back();
+ leaves_tmp_storage.pop_back();
+
+ Predicate * curr = leaf->get_parent();
+ while (curr != NULL) {
+ if (curr->get_weight() != 0) {
+ // Has been exlpored
+ break;
+ }
+
+ ModelVector<Predicate *> * children = curr->get_children();
+ double weight_sum = 0;
+ bool has_unassigned_node = false;
+
+ for (uint i = 0; i < children->size(); i++) {
+ Predicate * child = (*children)[i];
+
+ // If a child has unassigned weight
+ double weight = child->get_weight();
+ if (weight == 0) {
+ has_unassigned_node = true;
+ break;
+ } else
+ weight_sum += weight;
+ }
+
+ if (!has_unassigned_node) {
+ double average_weight = (double) weight_sum / (double) children->size();
+ double weight = average_weight * pow(0.9, curr->get_depth());
+ curr->set_weight(weight);
+ } else
+ break;
+
+ curr = curr->get_parent();
+ }
+ }
+}
+
+void FuncNode::update_predicate_tree_weight()
+{
+ if (marker == 2) {
+ // Predicate tree is initially built
+ assign_initial_weight();
+ return;
+ }
+
+ weight_debug_vec.clear();
+
+ PredSetIter * it = failed_predicates.iterator();
+ while (it->hasNext()) {
+ Predicate * pred = it->next();
+ leaves_tmp_storage.push_back(pred);
+ }
+ delete it;
+ failed_predicates.reset();
+
+ quickSort(&leaves_tmp_storage, 0, leaves_tmp_storage.size() - 1);
+ for (uint i = 0; i < leaves_tmp_storage.size(); i++) {
+ Predicate * pred = leaves_tmp_storage[i];
+ double weight = 100.0 / sqrt(pred->get_expl_count() + pred->get_fail_count() + 1);
+ pred->set_weight(weight);
+ }
+
+ // Update weights in internal nodes
+ while ( !leaves_tmp_storage.empty() ) {
+ Predicate * leaf = leaves_tmp_storage.back();
+ leaves_tmp_storage.pop_back();
+
+ Predicate * curr = leaf->get_parent();
+ while (curr != NULL) {
+ ModelVector<Predicate *> * children = curr->get_children();
+ double weight_sum = 0;
+ bool has_unassigned_node = false;
+
+ for (uint i = 0; i < children->size(); i++) {
+ Predicate * child = (*children)[i];
+
+ double weight = child->get_weight();
+ if (weight != 0)
+ weight_sum += weight;
+ else if ( predicate_leaves.contains(child) ) {
+ // If this child is a leaf
+ double weight = 100.0 / sqrt(child->get_expl_count() + 1);
+ child->set_weight(weight);
+ weight_sum += weight;
+ } else {
+ has_unassigned_node = true;
+ weight_debug_vec.push_back(child); // For debugging purpose
+ break;
+ }
+ }
+
+ if (!has_unassigned_node) {
+ double average_weight = (double) weight_sum / (double) children->size();
+ double weight = average_weight * pow(0.9, curr->get_depth());
+ curr->set_weight(weight);
+ } else
+ break;
+
+ curr = curr->get_parent();
+ }
+ }
+
+ for (uint i = 0; i < weight_debug_vec.size(); i++) {
+ Predicate * tmp = weight_debug_vec[i];
+ ASSERT( tmp->get_weight() != 0 );
+ }
+}
+
+void FuncNode::print_predicate_tree()
+{
+ model_print("digraph function_%s {\n", func_name);
+ predicate_tree_entry->print_pred_subtree();
+ predicate_tree_exit->print_predicate();
+ model_print("}\n"); // end of graph