flower/interval-set.cc

   1 /*
   2   interval-set.hh -- implement Interval_set
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 2004 Han-Wen Nienhuys <hanwen@xs4all.nl>
   7 */
   8
   9 #include "interval-set.hh"
  10
  11 /*
  12   A union of intervals in the real line.
  13
  14   Abysmal performance (quadratic) for large N, hopefully we don't have
  15   that large N. In any case, this should probably be rewritten to use
  16   a balanced tree.
  17 */
  18
  19 Interval_set::Interval_set ()
  20 {
  21   set_full ();
  22 }
  23
  24 void
  25 Interval_set::set_full ()
  26 {
  27   allowed_regions_.clear ();
  28   Interval s;
  29   s.set_full ();
  30   allowed_regions_.push_back (s);
  31 }
  32
  33 void
  34 Interval_set::remove_interval (Interval rm)
  35 {
  36   for (vsize i = 0; i < allowed_regions_.size ();)
  37     {
  38       Interval s = rm;
  39
  40       s.intersect (allowed_regions_[i]);
  41
  42       if (!s.is_empty ())
  43         {
  44           Interval before = allowed_regions_[i];
  45           Interval after = allowed_regions_[i];
  46
  47           before[RIGHT] = s[LEFT];
  48           after[LEFT] = s[RIGHT];
  49
  50           if (!before.is_empty () && before.length () > 0.0)
  51             {
  52               allowed_regions_.insert (allowed_regions_.begin () + i, before);
  53               i++;
  54             }
  55           allowed_regions_.erase (allowed_regions_.begin () + i);
  56           if (!after.is_empty () && after.length () > 0.0)
  57             {
  58               allowed_regions_.insert (allowed_regions_.begin () + i, after);
  59               i++;
  60             }
  61         }
  62       else
  63         i++;
  64     }
  65 }