X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;ds=sidebyside;f=lily%2Ftie-formatting-problem.cc;h=8d40e75f71784c9f4aad5ed497fd7abbd824c656;hb=8054dbca2f440e4cdbf98af57a9d548df64f9f8f;hp=03293c564b221cba7d79bab2e920ff18be951b66;hpb=7e33691750a97e1b66192cb484f479a173390132;p=lilypond.git diff --git a/lily/tie-formatting-problem.cc b/lily/tie-formatting-problem.cc index 03293c564b..8d40e75f71 100644 --- a/lily/tie-formatting-problem.cc +++ b/lily/tie-formatting-problem.cc @@ -22,6 +22,16 @@ #include "tie.hh" #include "warn.hh" +/* + 0 at threshold, 1 at 0, with 1/x falloff. + */ +Real peak_around (Real epsilon, Real threshold, Real x) +{ + if (x < 0) + return 1.0; + return max (- epsilon * (x - threshold) / ((x + epsilon) * threshold), 0.0); +} + Interval Tie_formatting_problem::get_attachment (Real y) const { @@ -49,15 +59,16 @@ Tie_formatting_problem::~Tie_formatting_problem () } void -Tie_formatting_problem::set_chord_outline (Link_array bounds, +Tie_formatting_problem::set_chord_outline (vector bounds, Direction d) { Real staff_space = Staff_symbol_referencer::staff_space (bounds[0]); - Array boxes; + vector boxes; + vector head_boxes; Grob *stem = 0; - for (int i = 0; i < bounds.size (); i++) + for (vsize i = 0; i < bounds.size (); i++) { Grob *head = bounds[i]; if (!Note_head::has_interface (head)) @@ -71,33 +82,33 @@ Tie_formatting_problem::set_chord_outline (Link_array bounds, (p+1) * 0.5 * staff_space); Interval x = head->extent (x_refpoint_, X_AXIS); - boxes.push (Box (x, y)); + head_boxes.push_back (Box (x, y)); + boxes.push_back (Box (x, y)); Grob *dots = Rhythmic_head::get_dots (head); if (d == LEFT && dots) { Interval x = dots->extent (x_refpoint_, X_AXIS); - Interval y (-0.5, 0.5); int p = int (Staff_symbol_referencer::get_position (dots)); - y.translate (p); dot_positions_.insert (p); dot_x_.unite (x); + + Interval y (dots->extent (dots, Y_AXIS)); + y.translate (p * staff_space * 0.5); - y *= staff_space * 0.5; - // boxes.push (Box (x, y)); + boxes.push_back (Box (x, y)); } } chord_outlines_[d] = empty_skyline (-d); - if (bounds[0]->break_status_dir ()) { Real x = robust_relative_extent (bounds[0], x_refpoint_, X_AXIS)[-d]; - chord_outlines_[d].elem_ref (0).height_ = x; + chord_outlines_[d].at (0).height_ = x; } - for (int i = 0; i < boxes.size (); i++) + for (vsize i = 0; i < boxes.size (); i++) insert_extent_into_skyline (&chord_outlines_[d] , boxes[i], Y_AXIS, -d); @@ -116,7 +127,7 @@ Tie_formatting_problem::set_chord_outline (Link_array bounds, insert_extent_into_skyline (&chord_outlines_[d], Box (x,y), Y_AXIS, -d); - + stem_extents_[d].unite (Box (x,y)); if (d == LEFT) { @@ -132,9 +143,9 @@ Tie_formatting_problem::set_chord_outline (Link_array bounds, { Interval x; Interval y; - if (boxes.size()) + if (head_boxes.size()) { - Box b = boxes.boundary (updowndir, 0); + Box b = boundary (head_boxes, updowndir, 0); x = b[X_AXIS]; x[-d] = b[X_AXIS].linear_combination (-d / 2); y[-updowndir] = b[Y_AXIS][updowndir]; @@ -153,9 +164,8 @@ Tie_formatting_problem::set_chord_outline (Link_array bounds, void Tie_formatting_problem::from_tie (Grob *tie) { - Link_array ties; - ties.push (tie); - + vector ties; + ties.push_back (tie); from_ties (ties); details_.from_grob (tie); @@ -168,13 +178,13 @@ Tie_formatting_problem::common_x_refpoint () const } void -Tie_formatting_problem::from_ties (Link_array const &ties) +Tie_formatting_problem::from_ties (vector const &ties) { - if (ties.is_empty ()) + if (ties.empty ()) return; x_refpoint_ = ties[0]; - for (int i = 0; i < ties.size (); i++) + for (vsize i = 0; i < ties.size (); i++) { x_refpoint_ = dynamic_cast (ties[i])->get_bound (LEFT)->common_refpoint (x_refpoint_, X_AXIS); x_refpoint_ = dynamic_cast (ties[i])->get_bound (RIGHT)->common_refpoint (x_refpoint_, X_AXIS); @@ -185,13 +195,13 @@ Tie_formatting_problem::from_ties (Link_array const &ties) Direction d = LEFT; do { - Link_array bounds; + vector bounds; - for (int i = 0; i < ties.size (); i++) + for (vsize i = 0; i < ties.size (); i++) { Item *it = dynamic_cast (ties[i])->get_bound (d); - bounds.push (it); + bounds.push_back (it); } set_chord_outline (bounds, d); @@ -199,7 +209,7 @@ Tie_formatting_problem::from_ties (Link_array const &ties) while (flip (&d) != LEFT); - for (int i = 0; i < ties.size (); i++) + for (vsize i = 0; i < ties.size (); i++) { Tie_specification spec; @@ -217,20 +227,20 @@ Tie_formatting_problem::from_ties (Link_array const &ties) } while (flip (&d) != LEFT); - specifications_.push (spec); + specifications_.push_back (spec); } } void -Tie_formatting_problem::from_lv_ties (Link_array const &lv_ties) +Tie_formatting_problem::from_lv_ties (vector const &lv_ties) { - if (lv_ties.is_empty ()) - return ; + if (lv_ties.empty ()) + return; details_.from_grob (lv_ties[0]); - Link_array heads; + vector heads; - for (int i = 0; i < lv_ties.size (); i++) + for (vsize i = 0; i < lv_ties.size (); i++) { Tie_specification spec; Item *head = unsmob_item (lv_ties[i]->get_object ("note-head")); @@ -244,21 +254,21 @@ Tie_formatting_problem::from_lv_ties (Link_array const &lv_ties) } spec.note_head_drul_[LEFT] = head; - heads.push (head); - specifications_.push (spec); + heads.push_back (head); + specifications_.push_back (spec); } x_refpoint_ = lv_ties [0]; - for (int i = 0; i < lv_ties.size (); i++) - { - x_refpoint_ = lv_ties[i]->common_refpoint (x_refpoint_, X_AXIS); - } + for (vsize i = 0; i < lv_ties.size (); i++) + x_refpoint_ = lv_ties[i]->common_refpoint (x_refpoint_, X_AXIS); + for (vsize i = 0; i < heads.size (); i++) + x_refpoint_ = heads[i]->common_refpoint (x_refpoint_, X_AXIS); set_chord_outline (heads, LEFT); Real right_most = - infinity_f; - for (int i = 0; i < chord_outlines_[LEFT].size (); i++) + for (vsize i = 0; i < chord_outlines_[LEFT].size (); i++) { right_most = max (right_most, chord_outlines_[LEFT][i].height_); } @@ -267,7 +277,7 @@ Tie_formatting_problem::from_lv_ties (Link_array const &lv_ties) right_entry.width_.set_full (); right_entry.height_ = right_most + 1.5; - chord_outlines_[RIGHT].push (right_entry); + chord_outlines_[RIGHT].push_back (right_entry); } @@ -290,7 +300,7 @@ Tie_formatting_problem::get_configuration (int pos, Direction dir) } - Tie_configuration *conf = generate_configuration (pos,dir); + Tie_configuration *conf = generate_configuration (pos, dir); possibilities_[key] = conf; return conf; } @@ -311,17 +321,43 @@ Tie_formatting_problem::generate_configuration (int pos, Direction dir) const conf->attachment_x_ = get_attachment (y + conf->delta_y_); Real h = conf->height (details_); + + if (h < details_.intra_space_threshold_ * 0.5 * details_.staff_space_) + { + /* + This is less sensible for long ties, since those are more + horizontal. + */ + Interval close_by = get_attachment (y + + conf->delta_y_ + + (dir * details_.intra_space_threshold_ * 0.25 + * details_.staff_space_)); + + conf->attachment_x_.intersect (close_by); + } + if (!conf->delta_y_) { - if (h < 0.5 * details_.staff_space_) + /* + TODO: + + - should make sliding criterion, should flatten ties if + + - they're just the wrong (ie. touching line at top & bottom) + size. + + */ + if (h < details_.intra_space_threshold_ * 0.5 * details_.staff_space_) { - if (!Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, pos)) + if (!Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, pos) + && abs (pos) < 2 * Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_)) { conf->center_tie_vertically (details_); } else if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, pos)) { - conf->delta_y_ += dir * 0.2 * details_.staff_space_; + conf->delta_y_ += dir * + details_.tip_staff_line_clearance_ * 0.5 * details_.staff_space_; } } else @@ -331,7 +367,7 @@ Tie_formatting_problem::generate_configuration (int pos, Direction dir) const int round_pos = int (my_round (top_pos)); /* TODO: should use other variable? */ - Real clearance = details_.staff_line_clearance_; + Real clearance = details_.center_staff_line_clearance_; if (fabs (top_pos - round_pos) < clearance && Staff_symbol_referencer::on_staff_line (details_.staff_symbol_referencer_, round_pos)) @@ -342,7 +378,26 @@ Tie_formatting_problem::generate_configuration (int pos, Direction dir) const } } + /* + we don't recompute attachment_x_ to take changed Y (through + delta_Y) into account. Doing would make ties go into small holes between heads, which + means we get collisions with neighboring heads. + */ conf->attachment_x_.widen ( - details_.x_gap_); + + Direction d = LEFT; + do + { + Real y = conf->position_ * details_.staff_space_ * 0.5 + conf->delta_y_; + if (stem_extents_[d][X_AXIS].is_empty () + || !stem_extents_[d][Y_AXIS].contains (y)) + continue; + + conf->attachment_x_[d] = + d* min (d * conf->attachment_x_[d], + d * (stem_extents_[d][X_AXIS][-d] - d * details_.stem_gap_)); + } + while (flip (&d) != LEFT); return conf; } @@ -356,7 +411,21 @@ Tie_formatting_problem::score_aptitude (Tie_configuration const &conf, if (sign (curve_y - tie_y) != conf.dir_) penalty += details_.wrong_direction_offset_penalty_; - penalty += details_.distance_penalty_factor_ * fabs (curve_y - tie_y); + penalty += details_.vertical_distance_penalty_factor_ * fabs (curve_y - tie_y); + + + Direction d = LEFT; + do + { + if (!spec.note_head_drul_[d]) + continue; + + Interval head_x = spec.note_head_drul_[d]->extent (x_refpoint_, X_AXIS); + Real dist = head_x.distance (conf.attachment_x_[d]); + penalty += details_.horizontal_distance_penalty_factor_ * dist; + } + while (flip (&d) != LEFT); + return penalty; } @@ -365,8 +434,8 @@ Tie_formatting_problem::score_configuration (Tie_configuration const &conf) cons { Real penalty = 0.0; Real length = conf.attachment_x_.length (); - if (length < details_.min_length_) - penalty += details_.length_penalty_factor_ / max (0.01, length); + + penalty += peak_around (0.5 * details_.min_length_, details_.min_length_, length); Real tip_pos = conf.position_ + conf.delta_y_ / 0.5 * details_.staff_space_; Real tip_y = tip_pos * details_.staff_space_ * 0.5; @@ -375,19 +444,24 @@ Tie_formatting_problem::score_configuration (Tie_configuration const &conf) cons Real top_y = tip_y + conf.dir_ * height; Real top_pos = 2 * top_y / details_.staff_space_; Real round_top_pos = rint (top_pos); - if (fabs (top_pos - round_top_pos) < details_.staff_line_clearance_ - && Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, + if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, int (round_top_pos)) && Staff_symbol_referencer::staff_radius (details_.staff_symbol_referencer_) > top_y) { - penalty += details_.staff_line_collision_penalty_; + penalty += + details_.staff_line_collision_penalty_ + * peak_around (0.1 * details_.center_staff_line_clearance_, + details_.center_staff_line_clearance_, + fabs (top_pos - round_top_pos)); } - if (fabs (tip_pos - rint (tip_pos)) < details_.staff_line_clearance_ - && Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, - int (rint (tip_pos)))) + if (Staff_symbol_referencer::on_line (details_.staff_symbol_referencer_, + int (rint (tip_pos)))) { - penalty += details_.staff_line_collision_penalty_; + penalty += details_.staff_line_collision_penalty_ + * peak_around (0.1 * details_.tip_staff_line_clearance_, + details_.tip_staff_line_clearance_, + fabs (tip_pos - rint (tip_pos))); } if (!dot_x_.is_empty ()) @@ -404,10 +478,11 @@ Tie_formatting_problem::score_configuration (Tie_configuration const &conf) cons i != dot_positions_.end (); i ++) { int dot_pos = (*i); - if (fabs (dot_pos * details_.staff_space_ * 0.5 - y) < details_.dot_collision_clearance_) - { - penalty += details_.dot_collision_penalty_; - } + penalty += + details_.dot_collision_penalty_ + * peak_around (.1 * details_.dot_collision_clearance_, + details_.dot_collision_clearance_, + fabs (dot_pos * details_.staff_space_ * 0.5 - y)); } } } @@ -418,7 +493,7 @@ Tie_formatting_problem::score_configuration (Tie_configuration const &conf) cons Tie_configuration Tie_formatting_problem::find_optimal_tie_configuration (Tie_specification const &spec) const { - Link_array confs; + vector confs; int pos = spec.position_; Direction dir = spec.manual_dir_; @@ -426,14 +501,14 @@ Tie_formatting_problem::find_optimal_tie_configuration (Tie_specification const int region_size = 3; for (int i = 0; i < region_size; i ++) { - confs.push (generate_configuration (pos + i * dir, dir)); + confs.push_back (generate_configuration (pos + i * dir, dir)); } - Array scores; + vector scores; int best_idx = -1; Real best_score = 1e6; - for (int i = 0; i < confs.size (); i ++) + for (vsize i = 0; i < confs.size (); i ++) { Real score = 0.0; score += score_configuration (*confs[i]); @@ -447,7 +522,7 @@ Tie_formatting_problem::find_optimal_tie_configuration (Tie_specification const } Tie_configuration best = *confs[best_idx]; - for (int i = 0; i < confs.size (); i++) + for (vsize i = 0; i < confs.size (); i++) delete confs[i]; return best; @@ -475,7 +550,7 @@ Tie_formatting_problem::score_ties_aptitude (Ties_configuration const &ties) con return infinity_f; } - for (int i = 0; i < ties.size (); i++) + for (vsize i = 0; i < ties.size (); i++) score += score_aptitude (ties[i], specifications_[i]); return score; @@ -492,15 +567,14 @@ Real Tie_formatting_problem::score_ties_configuration (Ties_configuration const &ties) const { Real score = 0.0; - for (int i = 0; i < ties.size (); i++) + for (vsize i = 0; i < ties.size (); i++) { score += score_configuration (ties[i]); } - Real last_edge = 0.0; Real last_center = 0.0; - for (int i = 0; i < ties.size (); i++) + for (vsize i = 0; i < ties.size (); i++) { Bezier b (ties[i].get_transformed_bezier (details_)); @@ -512,22 +586,37 @@ Tie_formatting_problem::score_ties_configuration (Ties_configuration const &ties if (edge <= last_edge) score += details_.tie_column_monotonicity_penalty_; if (center <= last_center) - score +=details_. tie_column_monotonicity_penalty_; + score += details_.tie_column_monotonicity_penalty_; score += - details_.tie_tie_collision_penalty_ - * max (details_.tie_tie_collision_distance_ - fabs (center - last_center), 0.0) - / details_.tie_tie_collision_distance_; + details_.tie_tie_collision_penalty_ * + peak_around (0.1 * details_.tie_tie_collision_distance_, + details_.tie_tie_collision_distance_, + fabs (center - last_center)); score += - details_.tie_tie_collision_penalty_ - * max (details_.tie_tie_collision_distance_ - fabs (edge - last_edge), 0.0) - / details_.tie_tie_collision_distance_; + details_.tie_tie_collision_penalty_ * + peak_around (0.1 * details_.tie_tie_collision_distance_, + details_.tie_tie_collision_distance_, + fabs (edge - last_edge)); } last_edge = edge; last_center = center; } + + score += + details_.outer_tie_length_symmetry_penalty_factor_ + * fabs (ties[0].attachment_x_.length () - ties.back ().attachment_x_.length ()); + + score += + details_.outer_tie_vertical_distance_symmetry_penalty_factor_ + * (fabs (specifications_[0].position_ + - (ties[0].position_ * 0.5 * details_.staff_space_ + ties[0].delta_y_)) + - + fabs (specifications_.back ().position_ + - (ties.back ().position_ * 0.5 * details_.staff_space_ + ties.back ().delta_y_))); + return score; } @@ -539,7 +628,7 @@ Ties_configuration Tie_formatting_problem::generate_ties_configuration (Ties_configuration const &ties_config) { Ties_configuration copy; - for (int i = 0; i < ties_config.size (); i++) + for (vsize i = 0; i < ties_config.size (); i++) { Tie_configuration * ptr = get_configuration (ties_config[i].position_, ties_config[i].dir_); if (specifications_[i].has_manual_position_) @@ -548,7 +637,7 @@ Tie_formatting_problem::generate_ties_configuration (Ties_configuration const &t = (specifications_[i].manual_position_ - ties_config[i].position_) * 0.5 * details_.staff_space_; } - copy.push (*ptr); + copy.push_back (*ptr); } return copy; @@ -558,7 +647,7 @@ Ties_configuration Tie_formatting_problem::generate_base_chord_configuration () { Ties_configuration ties_config; - for (int i = 0; i < specifications_.size (); i ++) + for (vsize i = 0; i < specifications_.size (); i ++) { Tie_configuration conf; if (specifications_[i].has_manual_dir_) @@ -570,12 +659,16 @@ Tie_formatting_problem::generate_base_chord_configuration () * 0.5 * details_.staff_space_; } else - conf.position_ = specifications_[i].position_; - - ties_config.push (conf); + { + conf.position_ = specifications_[i].position_; + } + ties_config.push_back (conf); } set_ties_config_standard_directions (&ties_config); + for (vsize i = 0; i < ties_config.size (); i++) + if (!specifications_[i].manual_position_) + ties_config[i].position_ += ties_config[i].dir_; ties_config = generate_ties_configuration (ties_config); @@ -586,22 +679,21 @@ Ties_configuration Tie_formatting_problem::generate_optimal_chord_configuration () { Ties_configuration base = generate_base_chord_configuration (); - Array vars = get_variations (base); + vector vars = get_variations (base); Ties_configuration best = base; - Real best_score = score_ties_configuration (best); + Real best_score = score_ties (best); /* This simply is 1-opt: we have K substitions, and we try applying exactly every one for each. */ - for (int i = 0; i < vars.size (); i++) + for (vsize i = 0; i < vars.size (); i++) { Ties_configuration variant = base; variant[vars[i].index_] = *vars[i].suggestion_; - Real score = (score_ties_configuration (variant) - + score_ties_aptitude (variant)); + Real score = score_ties (variant); if (score < best_score) { best = variant; @@ -615,34 +707,34 @@ Tie_formatting_problem::generate_optimal_chord_configuration () void Tie_formatting_problem::set_ties_config_standard_directions (Ties_configuration *tie_configs) { - if (tie_configs->is_empty ()) + if (tie_configs->empty ()) return ; - if (!tie_configs->elem (0).dir_) - tie_configs->elem_ref (0).dir_ = DOWN; - if (!tie_configs->top().dir_) - tie_configs->top().dir_ = UP; + if (!tie_configs->at (0).dir_) + tie_configs->at (0).dir_ = DOWN; + if (!tie_configs->back ().dir_) + tie_configs->back ().dir_ = UP; /* Seconds */ - for (int i = 1; i < tie_configs->size (); i++) + for (vsize i = 1; i < tie_configs->size (); i++) { - Real diff = (tie_configs->elem (i-1).position_ - - tie_configs->elem (i).position_); + Real diff = (tie_configs->at (i-1).position_ + - tie_configs->at (i).position_); if (fabs (diff) <= 1) { - if (!tie_configs->elem (i-1).dir_) - tie_configs->elem_ref (i-1).dir_ = DOWN; - if (!tie_configs->elem (i).dir_) - tie_configs->elem_ref (i).dir_ = UP; + if (!tie_configs->at (i-1).dir_) + tie_configs->at (i-1).dir_ = DOWN; + if (!tie_configs->at (i).dir_) + tie_configs->at (i).dir_ = UP; } } - for (int i = 1; i < tie_configs->size() - 1; i++) + for (vsize i = 1; i < tie_configs->size() - 1; i++) { - Tie_configuration &conf = tie_configs->elem_ref (i); + Tie_configuration &conf = tie_configs->at (i); if (conf.dir_) continue; @@ -661,14 +753,14 @@ Tie_configuration_variation::Tie_configuration_variation () suggestion_ = 0; } -Array +vector Tie_formatting_problem::get_variations (Ties_configuration const &ties) { Real center_distance_tolerance = 0.25; - Array vars; + vector vars; Real last_center = 0.0; - for (int i = 0; i < ties.size (); i++) + for (vsize i = 0; i < ties.size (); i++) { Bezier b (ties[i].get_transformed_bezier (details_)); @@ -682,55 +774,80 @@ Tie_formatting_problem::get_variations (Ties_configuration const &ties) { Tie_configuration_variation var; var.index_ = i; - var.suggestion_ = get_configuration (ties[i].position_, + var.suggestion_ = get_configuration (specifications_[i].position_ + - ties[i].dir_, -ties[i].dir_); - vars.push (var); + vars.push_back (var); } if (!specifications_[i-1].has_manual_dir_) { Tie_configuration_variation var; var.index_ = i-1; - var.suggestion_ = get_configuration (ties[i-1].position_, - -ties[i-1].dir_); + var.suggestion_ = get_configuration (specifications_[i-1].position_ + - ties[i-1].dir_, + - ties[i-1].dir_); - vars.push (var); + vars.push_back (var); } } + else if (dot_positions_.find (ties[i].position_) != dot_positions_.end () + && !specifications_[i].has_manual_position_) + { + Tie_configuration_variation var; + var.index_ = i; + var.suggestion_ = get_configuration (ties[i].position_ + ties[i].dir_, + ties[i].dir_); + vars.push_back (var); + } + } last_center = center; } + /* TODO: switch off? */ + Direction d = DOWN; + do + { + if (boundary (ties, d, 0).dir_ == d) + { + Tie_configuration_variation var; + var.index_ = (d == DOWN) ? 0 : ties.size () - 1; + var.suggestion_ = get_configuration (boundary (ties, d, 0).position_ + + d, d); + vars.push_back (var); + } + } + while (flip (&d) != DOWN); + return vars; - } void Tie_formatting_problem::set_manual_tie_configuration (SCM manual_configs) { - int k = 0; + vsize k = 0; for (SCM s = manual_configs; - scm_is_pair (s) && k < specifications_.size(); s = scm_cdr (s)) + scm_is_pair (s) && k < specifications_.size (); s = scm_cdr (s)) { SCM entry = scm_car (s); - if (!scm_is_pair (entry)) - continue; - - Tie_specification &spec = specifications_[k]; - - if (scm_is_number (scm_cdr (entry))) - { - spec.has_manual_dir_ = true; - spec.manual_dir_ = Direction (scm_to_int (scm_cdr (entry))); - } - if (scm_is_number (scm_car (entry))) + if (scm_is_pair (entry)) { - spec.has_manual_position_ = true; - spec.manual_position_ = scm_to_double (scm_car (entry)); - } - + Tie_specification &spec = specifications_[k]; + + if (scm_is_number (scm_car (entry))) + { + spec.has_manual_position_ = true; + spec.manual_position_ = scm_to_double (scm_car (entry)); + } + if (scm_is_number (scm_cdr (entry))) + { + spec.has_manual_dir_ = true; + spec.manual_dir_ = Direction (scm_to_int (scm_cdr (entry))); + } + } k ++; } }