flower/interval-set.cc

   1 /*
   2   This file is part of LilyPond, the GNU music typesetter.
   3
   4   Copyright (C) 2004--2015 Han-Wen Nienhuys <hanwen@xs4all.nl>
   5
   6   LilyPond is free software: you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation, either version 3 of the License, or
   9   (at your option) any later version.
  10
  11   LilyPond is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with LilyPond.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19
  20 #include "interval-set.hh"
  21
  22 /*
  23   A union of intervals in the real line.
  24
  25   This class gives good performance for finding the union of
  26   a collection of intervals (n log n) and for testing if a point
  27   belongs to the union (log n).  It does not give an efficient way to
  28   update the set (ie. by adding more intervals); to do this
  29   efficiently would require a self-balancing tree, and it would not
  30   be currently useful in lilypond anyway.
  31 */
  32
  33 Interval_set::Interval_set ()
  34 {
  35 }
  36
  37 Interval_set
  38 Interval_set::interval_union (vector<Interval> ivs)
  39 {
  40   vector_sort (ivs, Interval::left_less);
  41
  42   Interval_set ret;
  43
  44   if (ivs.empty ())
  45     return ret;
  46
  47   ret.intervals_.push_back (ivs.front ());
  48
  49   // Go over the intervals from left to right.  If the current interval
  50   // overlaps with the last one, merge them.  Otherwise, append the
  51   // current interval to the list.
  52   for (vsize i = 1; i < ivs.size (); ++i)
  53     {
  54       Interval iv = ivs[i];
  55       Interval &last = ret.intervals_.back ();
  56
  57       if (last[RIGHT] >= iv[LEFT])
  58         // overlapping intervals: merge them
  59         last[RIGHT] = max (last[RIGHT], iv[RIGHT]);
  60       else if (!iv.is_empty ())
  61         ret.intervals_.push_back (iv);
  62     }
  63
  64   return ret;
  65 }
  66
  67 // Returns an iterator pointing to the first interval whose left
  68 // endpoint is at least x.  That interval may or may not contain x.
  69 vector<Interval>::const_iterator
  70 Interval_set::upper_bound (Real x) const
  71 {
  72   Interval xx (x, x);
  73   return std::upper_bound (intervals_.begin (), intervals_.end (), xx, Interval::left_less);
  74 }
  75
  76 Real
  77 Interval_set::nearest_point (Real x, Direction d) const
  78 {
  79   Real left = -infinity_f; // The closest point to the left of x.
  80   Real right = infinity_f; // The closest point to the right of x.
  81
  82   vector<Interval>::const_iterator i = upper_bound (x);
  83   if (i != intervals_.end ())
  84     right = (*i)[LEFT];
  85
  86   if (i != intervals_.begin ())
  87     {
  88       Interval left_iv = *(i - 1);
  89       // left_iv[LEFT] is guaranteed to be less than x. So if
  90       // left_iv[RIGHT] >= x then left_iv contains x, which must then
  91       // be the nearest point to x.
  92       if (left_iv[RIGHT] >= x)
  93         return x;
  94
  95       left = left_iv[RIGHT];
  96     }
  97
  98   if (d == RIGHT)
  99     return right;
 100   if (d == LEFT)
 101     return left;
 102   else
 103     return (right - x) < (x - left) ? right : left;
 104 }
 105
 106 Interval_set
 107 Interval_set::complement () const
 108 {
 109   Interval_set ret;
 110
 111   if (intervals_.empty ())
 112     {
 113       ret.intervals_.push_back (Interval (-infinity_f, infinity_f));
 114       return ret;
 115     }
 116
 117   if (intervals_[0][LEFT] > -infinity_f)
 118     ret.intervals_.push_back (Interval (-infinity_f, intervals_[0][LEFT]));
 119
 120   for (vsize i = 1; i < intervals_.size (); ++i)
 121     ret.intervals_.push_back (Interval (intervals_[i - 1][RIGHT], intervals_[i][LEFT]));
 122
 123   if (intervals_.back ()[RIGHT] < infinity_f)
 124     ret.intervals_.push_back (Interval (intervals_.back ()[RIGHT], infinity_f));
 125
 126   return ret;
 127 }