lily/grouping.cc

   1 /*
   2   grouping.cc -- implement Rhythmic_grouping
   3
   4   source file of the GNU LilyPond music typesetter
   5
   6   (c) 1997 Han-Wen Nienhuys <hanwen@stack.nl>
   7 */
   8
   9 #include "debug.hh"
  10 #include "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() 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 () <= Rational (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   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               Rhythmic_grouping *newchild=new Rhythmic_grouping (
 164                                                                  children.slice (starti, i+1));
 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()/Rational (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*Rational (i) + basic));
 193 }
 194
 195
 196 Rhythmic_grouping::Rhythmic_grouping (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   for (int i=0; i < children.size(); i++)
 233     delete children[i];
 234   init();
 235 }
 236
 237 void
 238 Rhythmic_grouping::print() const
 239 {
 240 #ifndef NPRINT
 241   DOUT << "{ \n";
 242   if (interval_)
 243     DOUT <<" Interval "<< interval_->str();
 244   for (int i=0; i < children.size(); i++)
 245     {
 246       children[i]->print();
 247     }
 248   DOUT << "}\n";
 249 #endif
 250 }
 251
 252 bool
 253 Rhythmic_grouping::child_fit_b (Moment start)
 254 {
 255   if (children.size())
 256     return (children.top()->interval ().right== start);
 257
 258   return true;
 259 }
 260
 261 void
 262 Rhythmic_grouping::add_child (Moment start, Moment len)
 263 {
 264   Moment stop = start+len;
 265   assert (child_fit_b (start));
 266   children.push (new Rhythmic_grouping (MInterval (start, stop)));
 267 }
 268
 269 Rhythmic_grouping::Rhythmic_grouping()
 270 {
 271   interval_ =0;
 272 }
 273
 274 int
 275 min_elt (Array<int> v)
 276 {
 277   int i = 1000;         // ugh
 278   for (int j = 0 ; j <  v.size(); j++)
 279     i = i <? v[j];
 280   return i;
 281 }
 282
 283 Array<int>
 284 Rhythmic_grouping::generate_beams (Array<int> flags, int &flagidx)
 285 {
 286   assert (!interval_) ;
 287
 288   Array< Array<int> > children_beams;
 289   for (int i=0; i < children.size(); i++)
 290     {
 291       Array<int> child_beams;
 292       if (children[i]->interval_)
 293         {
 294           int f = flags[flagidx++];
 295           child_beams.push (f);
 296         }
 297       else
 298         {
 299           child_beams = children[i]->
 300             generate_beams (flags, flagidx);
 301         }
 302       children_beams.push (child_beams);
 303     }
 304   Array<int> beams;
 305   int lastm, m, nextm;
 306   for (int i=0; i  < children_beams.size(); i++)
 307     {
 308       bool add_left =  (i >0);
 309       bool add_right = (i  < children_beams.size() -1);
 310
 311       if (!i)
 312         m =  min_elt (children_beams[i]);
 313       if (add_right)
 314         nextm = min_elt (children_beams[i+1]);
 315
 316       if (children_beams[i].size() == 1)
 317         {
 318           if (add_right)
 319             beams.push (m);
 320           if (add_left)
 321             beams.push (m);
 322         }
 323       else
 324         {
 325           if (add_left)
 326             beams.push (lastm <? m);
 327           beams.concat (children_beams[i]);
 328           if (add_right)
 329             beams.push (m <? nextm);
 330         }
 331       lastm = m;
 332       m = nextm;
 333     }
 334   assert (!(beams.size()%2));
 335   return beams;
 336 }
 337
 338 void
 339 Rhythmic_grouping::translate (Moment m)
 340 {
 341   if (interval_)
 342     *interval_ += m;
 343   else
 344     for (int i=0; i < children.size(); i++)
 345       children[i]->translate (m);
 346 }
 347
 348 void
 349 Rhythmic_grouping::extend (MInterval m) const
 350 {
 351   assert (m.left >= interval().left);
 352   while (m.right  >interval().right)
 353     {
 354       Array<Rhythmic_grouping*> a (children);
 355       for (int i=0; i < a.size(); i++)
 356         {
 357           a[i] =new Rhythmic_grouping (*children[i]);
 358           a[i]->translate (children.top()->interval ().right);
 359         }
 360       ((Rhythmic_grouping*)this)->children.concat (a);
 361     }
 362   assert (m.right <= interval().right);
 363   OK();
 364 }
 365
 366 Rhythmic_grouping
 367 parse_grouping (Array<int> beat_i_arr, Array<Moment> elt_length_arr)
 368 {
 369   Moment here =0;
 370   assert (beat_i_arr.size() == elt_length_arr.size ());
 371
 372   Array<Rhythmic_grouping*> children;
 373   for (int i=0; i < beat_i_arr.size(); i++)
 374     {
 375       Moment last = here;
 376       here += elt_length_arr[i] * Moment (beat_i_arr[i]);
 377       children.push (
 378                      new Rhythmic_grouping (MInterval (last, here),
 379                                             beat_i_arr[i]));
 380     }
 381   return Rhythmic_grouping (children);
 382 }
 383