]> git.donarmstrong.com Git - lilypond.git/blob - lily/interval-minefield.cc
Merge remote branch 'origin/master' into release/unstable
[lilypond.git] / lily / interval-minefield.cc
1 /*
2   This file is part of LilyPond, the GNU music typesetter.
3
4   Copyright (C) 2011--2015 Mike Solomon <mike@mikesolomon.org>
5   Jan Nieuwenhuizen <janneke@gnu.org>
6
7   LilyPond is free software: you can redistribute it and/or modify
8   it under the terms of the GNU General Public License as published by
9   the Free Software Foundation, either version 3 of the License, or
10   (at your option) any later version.
11
12   LilyPond is distributed in the hope that it will be useful,
13   but WITHOUT ANY WARRANTY; without even the implied warranty of
14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15   GNU General Public License for more details.
16
17   You should have received a copy of the GNU General Public License
18   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
19 */
20
21 #include "interval-minefield.hh"
22
23 Interval_minefield::Interval_minefield (Interval feasible_placements, Real bulk)
24 {
25   feasible_placements_ = feasible_placements;
26   bulk_ = bulk;
27 }
28
29 void
30 Interval_minefield::add_forbidden_interval (Interval forbidden)
31 {
32   forbidden_intervals_.push_back (forbidden);
33 }
34
35 Interval
36 Interval_minefield::feasible_placements ()
37 {
38   return feasible_placements_;
39 }
40
41 /*
42   forbidden_intervals_ contains a vector of intervals in which
43   the beam cannot start.  it iterates through these intervals,
44   pushing feasible_placements_ epsilon over or epsilon under a
45   collision.  when this type of change happens, the loop is marked
46   as "dirty" and re-iterated.
47
48   TODO: figure out a faster ways that this loop can happen via
49   a better search algorithm.
50 */
51 void
52 Interval_minefield::solve ()
53 {
54   Real epsilon = 1.0e-10;
55   bool dirty = false;
56   do
57     {
58       dirty = false;
59       for (vsize i = 0; i < forbidden_intervals_.size (); i++)
60         {
61           for (DOWN_and_UP (d))
62             {
63               Interval feasible_widened = Interval (feasible_placements_[d], feasible_placements_[d]);
64               feasible_widened.widen (bulk_ / 2.);
65
66               if (forbidden_intervals_[i][d] == d * infinity_f)
67                 feasible_placements_[d] = d * infinity_f;
68               else if (forbidden_intervals_[i].contains (feasible_widened[d])
69                        || forbidden_intervals_[i].contains (feasible_widened[-d])
70                        || feasible_widened.contains (forbidden_intervals_[i][d])
71                        || feasible_widened.contains (forbidden_intervals_[i][-d]))
72                 {
73                   feasible_placements_[d] = forbidden_intervals_[i][d] + d * (epsilon + (bulk_ / 2));
74                   dirty = true;
75                 }
76             }
77         }
78     }
79   while (dirty);
80 }