X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=lily%2Fskyline.cc;h=0e2f2fa12b97862dd1956d9a10d8d731d53a3dfe;hb=00e3e15364b9d3c94cda1bcab9f889bb95f6832d;hp=e61abbaea6bed28b05f7b3a3f69aa532d8952be5;hpb=727a25b151d4cb1342b66b8d1c80522d5bbcc0dd;p=lilypond.git

diff --git a/lily/skyline.cc b/lily/skyline.cc
index e61abbaea6..0e2f2fa12b 100644
--- a/lily/skyline.cc
+++ b/lily/skyline.cc
@@ -2,10 +2,11 @@
 
    source file of the GNU LilyPond music typesetter
  
-   (c) 2006 Joe Neeman <joeneeman@gmail.com>
+   (c) 2006--2007 Joe Neeman <joeneeman@gmail.com>
 */
 
 #include "skyline.hh"
+#include <deque>
 
 #include "ly-smobs.icc"
 
@@ -109,11 +110,11 @@ Skyline::print () const
 }
 
 bool
-Skyline::is_legal_skyline () const
+is_legal_skyline (list<Building> const &buildings)
 {
   list<Building>::const_iterator i;
   Real last_x = -infinity_f;
-  for (i = buildings_.begin (); i != buildings_.end (); i++)
+  for (i = buildings.begin (); i != buildings.end (); i++)
     {
       if (i->iv_[LEFT] != last_x)
 	return false;
@@ -152,7 +153,7 @@ Building::Building (Box const &b, Real horizon_padding, Axis horizon_axis, Direc
 void
 Building::precompute ()
 {
-  slope_ = (height_[RIGHT] - height_[LEFT]) / (iv_.length());
+  slope_ = (height_[RIGHT] - height_[LEFT]) / (iv_.length ());
   if (height_[LEFT] == height_[RIGHT]) /* in case they're both infinity */
     slope_ = 0;
 
@@ -325,34 +326,78 @@ single_skyline (Building b, Real horizon_padding, list<Building> *const ret)
 			       -infinity_f, b.iv_[LEFT]));
 }
 
-void
-Skyline::internal_build_skyline (list<Building> *buildings, list<Building> *const result)
+/* remove a non-overlapping set of buildings from BUILDINGS and build a skyline
+   out of them */
+static list<Building>
+non_overlapping_skyline (list<Building> *const buildings)
+{
+  list<Building> result;
+  Real last_end = -infinity_f;
+  list<Building>::iterator i = buildings->begin ();
+  while (i != buildings->end ())
+    {
+      if (approx_less_than (i->iv_[LEFT], last_end))
+	{
+	  i++;
+	  continue;
+	}
+
+      if (approx_greater_than (i->iv_[LEFT], last_end))
+	result.push_back (Building (last_end, -infinity_f, -infinity_f, i->iv_[LEFT]));
+      else
+	i->iv_[LEFT] = last_end;
+
+      last_end = i->iv_[RIGHT];
+      list<Building>::iterator j = i;
+      i++;
+      result.splice (result.end (), *buildings, j);
+    }
+  if (last_end < infinity_f)
+    result.push_back (Building (last_end, -infinity_f, -infinity_f, infinity_f));
+  assert (is_legal_skyline (result));
+  return result;
+}
+
+list<Building>
+Skyline::internal_build_skyline (list<Building> *buildings)
 {
   vsize size = buildings->size ();
 
   if (size == 0)
     {
-      empty_skyline (result);
-      return;
+      list<Building> result;
+      empty_skyline (&result);
+      return result;
     }
   else if (size == 1)
     {
-      single_skyline (buildings->front (), 0, result);
-      return;
+      list<Building> result;
+      single_skyline (buildings->front (), 0, &result);
+      return result;
     }
 
-  list<Building> right_half;
-  list<Building>::iterator i = buildings->begin ();
+  deque<list<Building> > partials;
+  buildings->sort ();
+  while (!buildings->empty ())
+    partials.push_back (non_overlapping_skyline (buildings));
 
-  for (vsize s = 0; s < size/2; s++)
-    i++;
-  right_half.splice (right_half.end (), *buildings, i, buildings->end ());
-
-  list<Building> right;
-  list<Building> left;
-  internal_build_skyline (&right_half, &right);
-  internal_build_skyline (buildings, &left);
-  internal_merge_skyline (&right, &left, result);
+  /* we'd like to say while (partials->size () > 1) but that's O (n).
+     Instead, we exit in the middle of the loop */
+  while (!partials.empty ())
+    {
+      list<Building> merged;
+      list<Building> one = partials.front ();
+      partials.pop_front ();
+      if (partials.empty ())
+	return one;
+
+      list<Building> two = partials.front ();
+      partials.pop_front ();
+      internal_merge_skyline (&one, &two, &merged);
+      partials.push_back (merged);
+    }
+  assert (0);
+  return list<Building> ();
 }
 
 Skyline::Skyline ()
@@ -406,8 +451,8 @@ Skyline::Skyline (vector<Box> const &boxes, Real horizon_padding, Axis horizon_a
 	}
     }
   
-  internal_build_skyline (&bldgs, &buildings_);
-  assert (is_legal_skyline ());
+  buildings_ = internal_build_skyline (&bldgs);
+  assert (is_legal_skyline (buildings_));
 }
 
 Skyline::Skyline (Box const &b, Real horizon_padding, Axis horizon_axis, Direction sky)
@@ -426,7 +471,7 @@ Skyline::merge (Skyline const &other)
   list<Building> my_bld;
   my_bld.splice (my_bld.begin (), buildings_);
   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
-  assert (is_legal_skyline ());
+  assert (is_legal_skyline (buildings_));
 }
 
 void
@@ -438,7 +483,7 @@ Skyline::insert (Box const &b, Real horizon_padding, Axis a)
   my_bld.splice (my_bld.begin (), buildings_);
   single_skyline (Building (b, 0, a, sky_), horizon_padding, &other_bld);
   internal_merge_skyline (&other_bld, &my_bld, &buildings_);
-  assert (is_legal_skyline ());
+  assert (is_legal_skyline (buildings_));
 }
 
 void
@@ -451,7 +496,7 @@ Skyline::raise (Real r)
       i->height_[RIGHT] += sky_ * r;
       i->y_intercept_ += sky_ * r;
     }
-  assert (is_legal_skyline ());
+  assert (is_legal_skyline (buildings_));
 }
 
 void
@@ -606,6 +651,7 @@ IMPLEMENT_DEFAULT_EQUAL_P (Skyline_pair);
 SCM
 Skyline::mark_smob (SCM)
 {
+  ASSERT_LIVE_IS_ALLOWED ();
   return SCM_EOL;
 }