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 using std::vector;
  23
  24 /*
  25   A union of intervals in the real line.
  26
  27   This class gives good performance for finding the union of
  28   a collection of intervals (n log n) and for testing if a point
  29   belongs to the union (log n).  It does not give an efficient way to
  30   update the set (ie. by adding more intervals); to do this
  31   efficiently would require a self-balancing tree, and it would not
  32   be currently useful in lilypond anyway.
  33 */
  34
  35 Interval_set::Interval_set ()
  36 {
  37 }
  38
  39 Interval_set
  40 Interval_set::interval_union (vector<Interval> ivs)
  41 {
  42   vector_sort (ivs, Interval::left_less);
  43
  44   Interval_set ret;
  45
  46   if (ivs.empty ())
  47     return ret;
  48
  49   ret.intervals_.push_back (ivs.front ());
  50
  51   // Go over the intervals from left to right.  If the current interval
  52   // overlaps with the last one, merge them.  Otherwise, append the
  53   // current interval to the list.
  54   for (vsize i = 1; i < ivs.size (); ++i)
  55     {
  56       Interval iv = ivs[i];
  57       Interval &last = ret.intervals_.back ();
  58
  59       if (last[RIGHT] >= iv[LEFT])
  60         // overlapping intervals: merge them
  61         last[RIGHT] = max (last[RIGHT], iv[RIGHT]);
  62       else if (!iv.is_empty ())
  63         ret.intervals_.push_back (iv);
  64     }
  65
  66   return ret;
  67 }
  68
  69 // Returns an iterator pointing to the first interval whose left
  70 // endpoint is at least x.  That interval may or may not contain x.
  71 vector<Interval>::const_iterator
  72 Interval_set::upper_bound (Real x) const
  73 {
  74   Interval xx (x, x);
  75   return std::upper_bound (intervals_.begin (), intervals_.end (), xx, Interval::left_less);
  76 }
  77
  78 Real
  79 Interval_set::nearest_point (Real x, Direction d) const
  80 {
  81   Real left = -infinity_f; // The closest point to the left of x.
  82   Real right = infinity_f; // The closest point to the right of x.
  83
  84   vector<Interval>::const_iterator i = upper_bound (x);
  85   if (i != intervals_.end ())
  86     right = (*i)[LEFT];
  87
  88   if (i != intervals_.begin ())
  89     {
  90       Interval left_iv = *(i - 1);
  91       // left_iv[LEFT] is guaranteed to be less than x. So if
  92       // left_iv[RIGHT] >= x then left_iv contains x, which must then
  93       // be the nearest point to x.
  94       if (left_iv[RIGHT] >= x)
  95         return x;
  96
  97       left = left_iv[RIGHT];
  98     }
  99
 100   if (d == RIGHT)
 101     return right;
 102   if (d == LEFT)
 103     return left;
 104   else
 105     return (right - x) < (x - left) ? right : left;
 106 }
 107
 108 Interval_set
 109 Interval_set::complement () const
 110 {
 111   Interval_set ret;
 112
 113   if (intervals_.empty ())
 114     {
 115       ret.intervals_.push_back (Interval (-infinity_f, infinity_f));
 116       return ret;
 117     }
 118
 119   if (intervals_[0][LEFT] > -infinity_f)
 120     ret.intervals_.push_back (Interval (-infinity_f, intervals_[0][LEFT]));
 121
 122   for (vsize i = 1; i < intervals_.size (); ++i)
 123     ret.intervals_.push_back (Interval (intervals_[i - 1][RIGHT], intervals_[i][LEFT]));
 124
 125   if (intervals_.back ()[RIGHT] < infinity_f)
 126     ret.intervals_.push_back (Interval (intervals_.back ()[RIGHT], infinity_f));
 127
 128   return ret;
 129 }