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"
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
*/
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];
/*
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)
{
- 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_;
}
}
-Array<Skyline_entry>
+vector<Skyline_entry>
empty_skyline (Direction d)
{
- Array<Skyline_entry> skyline;
+ vector<Skyline_entry> skyline;
Interval i;
i.set_empty ();
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),
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;
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;
}
void
-heighten_skyline (Array<Skyline_entry> *buildings, Real ground)
+heighten_skyline (vector<Skyline_entry> *buildings, Real ground)
{
- for (int i = 0; i < buildings->size (); i++)
- buildings->elem_ref (i).height_ += ground;
+ for (vsize i = 0; i < buildings->size (); i++)
+ buildings->at (i).height_ += ground;
}
Real
-skyline_height (Array<Skyline_entry> const &buildings,
+skyline_height (vector<Skyline_entry> const &buildings,
Real airplane,
Direction sky_dir)
{
/*
Ugh! linear, should be O(log n).
*/
- for (int i = 0; i < buildings.size (); i++)
+ 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_);