remove $(release-dir)/ ; must contain actions within build or srcdir

[lilypond.git] / lily / skyline.cc

diff --git a/lily/skyline.cc b/lily/skyline.cc
index bbbf7f55808b15939c796546ee6d341a166cbbd2..f72ea5b2f6d5fcbf8c6cdf229d62077373b90c39 100644 (file)
--- a/lily/skyline.cc
+++ b/lily/skyline.cc
@@ -3,7 +3,7 @@
 
   source file of the GNU LilyPond music typesetter
 
-  (c) 2002--2005 Han-Wen Nienhuys <hanwen@cs.uu.nl>
+  (c) 2002--2006 Han-Wen Nienhuys <hanwen@xs4all.nl>
 */
 
 #include "skyline.hh"
@@ -12,26 +12,24 @@
   A skyline is a shape of the form:
 
 
-  ----
-  |  |
-  ---------|  |
-  |          |
-  |          |
-  |          |______
-  --------|                 |___
-
-
+  *                  ----
+  *                  |  |
+  *         ---------|  |
+  *         |           |
+  *         |           |
+  *         |          |______
+  * --------|                |___
+  *
 
   This file deals with building such skyline structure, and computing
   the minimum distance between two opposing skylines.
 
-
   Invariants for a skyline:
 
   skyline[...].width_ forms a partition of the real interval, where
   the segments are adjacent, and ascending. Hence we have
 
-  skyline.top ().width_[RIGHT] = inf
+  skyline.back ().width_[RIGHT] = inf
   skyline[0].width_[LEFT] = -inf
 */
 
@@ -44,7 +42,7 @@ const Real EPS = 1e-12;
   binsearch.
 */
 void
-insert_extent_into_skyline (Array<Skyline_entry> *line, Box b, Axis line_axis,
+insert_extent_into_skyline (vector<Skyline_entry> *line, Box b, Axis line_axis,
                            Direction d)
 {
   Interval extent = b[line_axis];
@@ -56,41 +54,40 @@ insert_extent_into_skyline (Array<Skyline_entry> *line, Box b, Axis line_axis,
   /*
     Intersect each segment of LINE with EXTENT, and if non-empty, insert relevant segments.
   */
-  for (int i = line->size (); i--;)
+  for (vsize i = line->size (); i--;)
     {
-      Interval w = line->elem (i).width_;
+      Interval w = line->at (i).width_;
       w.intersect (extent);
 
       if (extent[LEFT] >= w[RIGHT])
        break;
 
-      Real my_height = line->elem (i).height_;
+      Real my_height = line->at (i).height_;
 
       if (!w.is_empty ()
          && w.length () > EPS
-         && d* (my_height - stick_out) < 0)
+         && d * (my_height - stick_out) < 0)
        {
-         Interval e1 (line->elem (i).width_[LEFT], extent[LEFT]);
-         Interval e3 (extent[RIGHT], line->elem (i).width_[RIGHT]);
+         Interval e1 (line->at (i).width_[LEFT], extent[LEFT]);
+         Interval e3 (extent[RIGHT], line->at (i).width_[RIGHT]);
 
          if (!e3.is_empty () && e3.length () > EPS)
-           line->insert (Skyline_entry (e3, my_height), i + 1);
+           line->insert (line->begin () + i + 1, Skyline_entry (e3, my_height));
 
-         line->elem_ref (i).height_ = stick_out;
-         line->elem_ref (i).width_ = w;
+         line->at (i).height_ = stick_out;
+         line->at (i).width_ = w;
          if (!e1.is_empty () && e1.length () > EPS)
-           line->insert (Skyline_entry (e1, my_height), i);
+           line->insert (line->begin () + i, Skyline_entry (e1, my_height));
        }
-
     }
 }
 
 void
-merge_skyline (Array<Skyline_entry> * a1,
-              Array<Skyline_entry> const &a2,
+merge_skyline (vector<Skyline_entry> *a1,
+              vector<Skyline_entry> const &a2,
               Direction dir)
 {
-  for (int i = 0; i < a2.size (); i++)
+  for (vsize i = 0; i < a2.size (); i++)
     {
       Box b;
       b[X_AXIS] = a2[i].width_;
@@ -101,10 +98,10 @@ merge_skyline (Array<Skyline_entry> * a1,
     }
 }
 
-Array<Skyline_entry>
+vector<Skyline_entry>
 empty_skyline (Direction d)
 {
-  Array<Skyline_entry> skyline;
+  vector<Skyline_entry> skyline;
 
   Interval i;
   i.set_empty ();
@@ -112,15 +109,15 @@ empty_skyline (Direction d)
   Skyline_entry e;
   e.width_ = i;
   e.height_ = -d * infinity_f;
-  skyline.push (e);
+  skyline.push_back (e);
   return skyline;
 }
 
-Array<Skyline_entry>
-extents_to_skyline (Array<Box> const &extents, Axis a, Direction d)
+vector<Skyline_entry>
+extents_to_skyline (vector<Box> const &extents, Axis a, Direction d)
 {
 
-  Array<Skyline_entry> skyline = empty_skyline (d);
+  vector<Skyline_entry> skyline = empty_skyline (d);
 
   /*
     This makes a cubic algorithm (array  insertion is O (n),
@@ -129,7 +126,7 @@ extents_to_skyline (Array<Box> const &extents, Axis a, Direction d)
     We could do a lot better (n log (n), using a balanced tree) but
     that seems overkill for now.
   */
-  for (int j = extents.size (); j--;)
+  for (vsize j = extents.size (); j--;)
     insert_extent_into_skyline (&skyline, extents[j], a, d);
 
   return skyline;
@@ -142,8 +139,8 @@ extents_to_skyline (Array<Box> const &extents, Axis a, Direction d)
   This is an O (n) algorithm.
 */
 Real
-skyline_meshing_distance (Array<Skyline_entry> const &buildings,
-                         Array<Skyline_entry> const &clouds)
+skyline_meshing_distance (vector<Skyline_entry> const &buildings,
+                         vector<Skyline_entry> const &clouds)
 {
   int i = buildings.size () -1;
   int j = clouds.size () -1;
@@ -156,16 +153,12 @@ skyline_meshing_distance (Array<Skyline_entry> const &buildings,
       w.intersect (clouds[j].width_);
 
       if (!w.is_empty ())
-       distance = distance >? (buildings[i].height_ - clouds[j].height_);
+       distance = max (distance, (buildings[i].height_ - clouds[j].height_));
 
       if (i > 0 && buildings[i].width_[LEFT] >= clouds[j].width_[LEFT])
-       {
-         i--;
-       }
+       i--;
       else if (j > 0 && buildings[i].width_[LEFT] <= clouds[j].width_[LEFT])
-       {
-         j--;
-       }
+       j--;
     }
 
   return distance;
@@ -180,12 +173,30 @@ Skyline_entry::Skyline_entry (Interval i, Real r)
 {
   width_ = i;
   height_ = r;
-
 }
 
 void
-heighten_skyline (Array<Skyline_entry> *buildings, Real ground)
+heighten_skyline (vector<Skyline_entry> *buildings, Real ground)
+{
+  for (vsize i = 0; i < buildings->size (); i++)
+    buildings->at (i).height_ += ground;
+}
+
+Real
+skyline_height (vector<Skyline_entry> const &buildings,
+               Real airplane,
+               Direction sky_dir)
 {
-  for (int i = 0; i < buildings->size (); i++)
-    buildings->elem_ref (i).height_ += ground;
+  Real h = - sky_dir * infinity_f;
+
+  /*
+    Ugh! linear, should be O(log n).
+   */
+  for (vsize i = 0; i < buildings.size (); i++)
+    if (buildings[i].width_.contains (airplane))
+      h = sky_dir * max (sky_dir * h,
+                        sky_dir * buildings[i].height_);
+  
+  return h;
 }
+