{
if (node_cnt_ <= max_node_cnt_) {
return;
}
memset(score_bins_, 0, sizeof(score_bins_));
int cost_range = max_cost_ - min_cost_ + 1;
for (int node_idx = 0; node_idx < node_cnt_; node_idx++) {
int cost_bin = static_cast<int>(
((node_array_[node_idx]->
BestCost() - min_cost_) *
kScoreBins) / static_cast<double>(cost_range));
if (cost_bin >= kScoreBins) {
cost_bin = kScoreBins - 1;
}
score_bins_[cost_bin]++;
}
int pruning_cost = 0;
int new_node_cnt = 0;
for (int cost_bin = 0; cost_bin < kScoreBins; cost_bin++) {
if (new_node_cnt > 0 &&
(new_node_cnt + score_bins_[cost_bin]) > max_node_cnt_) {
pruning_cost = min_cost_ + ((cost_bin * cost_range) / kScoreBins);
break;
}
new_node_cnt += score_bins_[cost_bin];
}
for (int node_idx = new_node_cnt = 0; node_idx < node_cnt_; node_idx++) {
if (node_array_[node_idx]->BestCost() > pruning_cost ||
new_node_cnt > max_node_cnt_) {
delete node_array_[node_idx];
} else {
node_array_[new_node_cnt++] = node_array_[node_idx];
}
}
node_cnt_ = new_node_cnt;
}