lily/interval-minefield.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2011 Mike Solomon <mike@apollinemike.com>
   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 #include "grob.hh"
  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           Direction d = DOWN;
  62           do
  63             {
  64               Interval feasible_widened = Interval (feasible_placements_[d], feasible_placements_[d]);
  65               feasible_widened.widen (bulk_ / 2.);
  66
  67               if (forbidden_intervals_[i][d] == d * infinity_f)
  68                 feasible_placements_[d] = d * infinity_f;
  69               else if (forbidden_intervals_[i].contains (feasible_widened[d])
  70                        || forbidden_intervals_[i].contains (feasible_widened[-d])
  71                        || feasible_widened.contains (forbidden_intervals_[i][d])
  72                        || feasible_widened.contains (forbidden_intervals_[i][-d]))
  73                 {
  74                   feasible_placements_[d] = forbidden_intervals_[i][d] + d * (epsilon +  (bulk_ / 2));
  75                   dirty = true;
  76                 }
  77             }
  78           while (flip (&d) != DOWN);
  79         }
  80     }
  81   while (dirty);
  82 }