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 }