lily/rhythmic-grouping.cc

   1 /*
   2   rhythmic-grouping.cc -- implement Rhythmic_grouping
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c)  1997--1999 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8
   9 #include "debug.hh"
  10 #include "rhythmic-grouping.hh"
  11 #include "interval.hh"
  12
  13 void
  14 Rhythmic_grouping::init()
  15 {
  16   interval_ = 0;
  17   children.clear();
  18 }
  19
  20 void
  21 Rhythmic_grouping::OK() const
  22 {
  23 #ifndef NDEBUG
  24   assert (bool (children.size()) != bool (interval_));
  25
  26   for (int i= 0; i < children.size(); i++)
  27     {
  28       children[i]->OK();
  29       if (i>0)
  30         assert (children[i-1]->interval()[RIGHT] ==
  31                 children[i]->interval()[LEFT]);
  32     }
  33 #endif
  34 }
  35
  36 Moment
  37 Rhythmic_grouping::length_mom () const
  38 {
  39   return interval().length ();
  40 }
  41
  42 MInterval
  43 Rhythmic_grouping::interval() const
  44 {
  45   if (interval_)
  46     return *interval_;
  47   else
  48     return
  49       MInterval (children[0]->interval()[LEFT],
  50                  children.top()->interval ()[RIGHT]);
  51 }
  52
  53 void
  54 Rhythmic_grouping::split (Rhythmic_grouping r)
  55 {
  56   if (interval_)
  57     return ;
  58
  59   r.intersect (interval());
  60   split (r.intervals());
  61
  62   for (int i= 0; i < children.size(); i++)
  63     {
  64       if (!children[i]->interval_)
  65         {
  66           Rhythmic_grouping here (r);
  67           children[i]->split (here);
  68         }
  69     }
  70 }
  71
  72
  73 Array<MInterval>
  74 Rhythmic_grouping::intervals()
  75 {
  76   Array<MInterval> r;
  77   if (interval_ || children.size() == 1)
  78     {
  79       MInterval i (interval());
  80       MInterval r1(i), r2(i);
  81       r1[RIGHT] = r2[LEFT] = i.center();
  82       r.push (r1); r.push (r2);
  83     }
  84   else
  85     {
  86       for (int i=0; i < children.size(); i++)
  87         r.push (children[i]->interval());
  88     }
  89   return r;
  90 }
  91
  92 void
  93 Rhythmic_grouping::intersect (MInterval t)
  94 {
  95   if (interval_)
  96     {
  97       interval_->intersect (t);
  98       return;
  99     }
 100
 101   for (int i=0; i < children.size(); i++)
 102     {
 103       MInterval inter = intersection (t, children[i]->interval());
 104       if (inter.empty_b() || inter.length () <= Moment (0))
 105         {
 106           delete children[i];
 107           children[i] =0;
 108         }
 109       else
 110         {
 111           children[i]->intersect (t);
 112         }
 113     }
 114   for (int i=0; i < children.size();)
 115     {
 116       if (!children[i])
 117         children.del (i);
 118       else
 119         i++;
 120     }
 121
 122 }
 123
 124 /**
 125   Put our children in branches of #this#.
 126   The min and max time intervals coincide with elements of #splitpoints#
 127
 128   I really should be documenting what is happening here, but I find
 129   that difficult, since I don't really understand what's going on here.
 130
 131   */
 132 void
 133 Rhythmic_grouping::split (Array<MInterval> splitpoints)
 134 {
 135   //check on splitpoints..
 136   int j = 0, i = 0, starti = 0, startj = 0;
 137
 138   Link_array<Rhythmic_grouping> ch;
 139   while (1)
 140     {
 141       if  (i >= children.size() || j >= splitpoints.size ())
 142         break;
 143
 144       assert (
 145               children[starti]->interval()[LEFT]== splitpoints[startj][LEFT]);
 146       if (children[i]->interval()[RIGHT] < splitpoints[j][RIGHT])
 147         {
 148           i ++;
 149         }
 150       else if (children[i]->interval()[RIGHT] > splitpoints[j][RIGHT])
 151         {
 152           j ++;
 153         }
 154       else
 155         {
 156
 157           if (i == starti)
 158             {
 159               ch.push (children[i]);
 160             }
 161           else
 162             {
 163               Link_array<Rhythmic_grouping> slice = children.slice (starti, i+1);
 164               Rhythmic_grouping *newchild=new Rhythmic_grouping (slice);
 165
 166               ch.push (newchild);
 167             }
 168           i ++;
 169           j++;
 170           starti = i;
 171           startj = j;
 172
 173
 174         }
 175     }
 176   if (ch.size() != 1)
 177     children = ch;
 178 }
 179
 180
 181 Rhythmic_grouping::Rhythmic_grouping (MInterval t, int n)
 182 {
 183   init();
 184   if (n == 1 || !n)
 185     {
 186       interval_ = new MInterval (t);
 187       return;
 188     }
 189   Moment dt = t.length ()/Moment (n);
 190   MInterval basic = MInterval (t[LEFT], t[LEFT]+dt);
 191   for (int i= 0; i < n; i++)
 192     children.push (new Rhythmic_grouping (dt*Moment (i) + basic));
 193 }
 194
 195
 196 Rhythmic_grouping::Rhythmic_grouping (Link_array<Rhythmic_grouping> r)
 197   :children (r)
 198 {
 199   interval_ =0;
 200 }
 201
 202 Rhythmic_grouping::~Rhythmic_grouping()
 203 {
 204   junk();
 205 }
 206
 207 void
 208 Rhythmic_grouping::copy (Rhythmic_grouping const&s)
 209 {
 210   interval_ =  (s.interval_)? new MInterval (*s.interval_) : 0;
 211   for (int i=0; i < s.children.size(); i++)
 212     children.push (new Rhythmic_grouping (*s.children[i]));
 213 }
 214
 215 void
 216 Rhythmic_grouping::operator=(Rhythmic_grouping const &s)
 217 {
 218   junk();
 219   copy (s);
 220 }
 221
 222 Rhythmic_grouping::Rhythmic_grouping (Rhythmic_grouping const&s)
 223 {
 224   init();
 225   copy (s);
 226 }
 227
 228 void
 229 Rhythmic_grouping::junk()
 230 {
 231   delete interval_;
 232   junk_pointer_array (children);
 233   init();
 234 }
 235
 236 void
 237 Rhythmic_grouping::print() const
 238 {
 239 #ifndef NPRINT
 240   DOUT << "{ \n";
 241   if (interval_)
 242     DOUT <<" Interval "<< interval_->str();
 243   for (int i=0; i < children.size(); i++)
 244     {
 245       children[i]->print();
 246     }
 247   DOUT << "}\n";
 248 #endif
 249 }
 250
 251 bool
 252 Rhythmic_grouping::child_fit_b (Moment start)
 253 {
 254   if (children.size())
 255     return (children.top()->interval ()[RIGHT]== start);
 256
 257   return true;
 258 }
 259
 260 void
 261 Rhythmic_grouping::add_child (Moment start, Moment len)
 262 {
 263   Moment stop = start+len;
 264   assert (child_fit_b (start));
 265   children.push (new Rhythmic_grouping (MInterval (start, stop)));
 266 }
 267
 268 Rhythmic_grouping::Rhythmic_grouping()
 269 {
 270   interval_ =0;
 271 }
 272
 273 int
 274 min_elt (Array<int> v)
 275 {
 276   int i = 1000;         // ugh
 277   for (int j = 0 ; j <  v.size(); j++)
 278     i = i <? v[j];
 279   return i;
 280 }
 281
 282 Array<int>
 283 Rhythmic_grouping::generate_beams (Array<int> flags, int &flagidx)
 284 {
 285   assert (!interval_) ;
 286
 287   Array< Array<int> > children_beams;
 288   for (int i=0; i < children.size(); i++)
 289     {
 290       Array<int> child_beams;
 291       if (children[i]->interval_)
 292         {
 293           int f = flags[flagidx++];
 294           child_beams.push (f);
 295         }
 296       else
 297         {
 298           child_beams = children[i]->
 299             generate_beams (flags, flagidx);
 300         }
 301       children_beams.push (child_beams);
 302     }
 303   Array<int> beams;
 304   int lastm, m, nextm;
 305   for (int i=0; i  < children_beams.size(); i++)
 306     {
 307       bool add_left =  (i >0);
 308       bool add_right = (i  < children_beams.size() -1);
 309
 310       if (!i)
 311         m =  min_elt (children_beams[i]);
 312       if (add_right)
 313         nextm = min_elt (children_beams[i+1]);
 314
 315       if (children_beams[i].size() == 1)
 316         {
 317           if (add_right)
 318             beams.push (m);
 319           if (add_left)
 320             beams.push (m);
 321         }
 322       else
 323         {
 324           if (add_left)
 325             beams.push (lastm <? m);
 326           beams.concat (children_beams[i]);
 327           if (add_right)
 328             beams.push (m <? nextm);
 329         }
 330       lastm = m;
 331       m = nextm;
 332     }
 333   assert (!(beams.size()%2));
 334   return beams;
 335 }
 336
 337 void
 338 Rhythmic_grouping::translate (Moment m)
 339 {
 340   if (interval_)
 341     *interval_ += m;
 342   else
 343     for (int i=0; i < children.size(); i++)
 344       children[i]->translate (m);
 345 }
 346
 347 void
 348 Rhythmic_grouping::extend (MInterval m) const
 349 {
 350   assert (m[LEFT] >= interval()[LEFT]);
 351   while (m[RIGHT]  >interval()[RIGHT])
 352     {
 353       Link_array<Rhythmic_grouping> a (children);
 354       for (int i=0; i < a.size(); i++)
 355         {
 356           a[i] =new Rhythmic_grouping (*children[i]);
 357           a[i]->translate (children.top()->interval ()[RIGHT]);
 358         }
 359       ((Rhythmic_grouping*)this)->children.concat (a);
 360     }
 361   assert (m[RIGHT] <= interval()[RIGHT]);
 362   OK();
 363 }
 364
 365 Rhythmic_grouping
 366 parse_grouping (Array<int> beat_i_arr, Array<Moment> elt_length_arr)
 367 {
 368   Moment here =0;
 369   assert (beat_i_arr.size() == elt_length_arr.size ());
 370
 371   Link_array<Rhythmic_grouping> children;
 372   for (int i=0; i < beat_i_arr.size(); i++)
 373     {
 374       Moment last = here;
 375       here += elt_length_arr[i] * Moment (beat_i_arr[i]);
 376       children.push (
 377                      new Rhythmic_grouping (MInterval (last, here),
 378                                             beat_i_arr[i]));
 379     }
 380   return Rhythmic_grouping (children);
 381 }
 382