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
 266   assert (child_fit_b (start));
 267   children.push (new Rhythmic_grouping (MInterval (start, stop)));
 268 }
 269
 270 Rhythmic_grouping::Rhythmic_grouping()
 271 {
 272   interval_ =0;
 273 }
 274
 275 int
 276 min_elt (Array<int> v)
 277 {
 278   int i = 1000;         // ugh
 279   for (int j = 0 ; j <  v.size(); j++)
 280     i = i <? v[j];
 281   return i;
 282 }
 283
 284 Array<int>
 285 Rhythmic_grouping::generate_beams (Array<int> flags, int &flagidx)
 286 {
 287   assert (!interval_) ;
 288
 289   Array< Array<int> > children_beams;
 290   for (int i=0; i < children.size(); i++)
 291     {
 292       Array<int> child_beams;
 293       if (children[i]->interval_)
 294         {
 295           int f = flags[flagidx++];
 296           child_beams.push (f);
 297         }
 298       else
 299         {
 300           child_beams = children[i]->
 301             generate_beams (flags, flagidx);
 302         }
 303       children_beams.push (child_beams);
 304     }
 305   Array<int> beams;
 306   int lastm, m, nextm;
 307   for (int i=0; i  < children_beams.size(); i++)
 308     {
 309       bool add_left =  (i >0);
 310       bool add_right = (i  < children_beams.size() -1);
 311
 312       if (!i)
 313         m =  min_elt (children_beams[i]);
 314       if (add_right)
 315         nextm = min_elt (children_beams[i+1]);
 316
 317       if (children_beams[i].size() == 1)
 318         {
 319           if (add_right)
 320             beams.push (m);
 321           if (add_left)
 322             beams.push (m);
 323         }
 324       else
 325         {
 326           if (add_left)
 327             beams.push (lastm <? m);
 328           beams.concat (children_beams[i]);
 329           if (add_right)
 330             beams.push (m <? nextm);
 331         }
 332       lastm = m;
 333       m = nextm;
 334     }
 335   assert (!(beams.size()%2));
 336   return beams;
 337 }
 338
 339 void
 340 Rhythmic_grouping::translate (Moment m)
 341 {
 342   if (interval_)
 343     *interval_ += m;
 344   else
 345     for (int i=0; i < children.size(); i++)
 346       children[i]->translate (m);
 347 }
 348
 349 void
 350 Rhythmic_grouping::extend (MInterval m) const
 351 {
 352   assert (m.left >= interval().left);
 353   while (m.right  >interval().right)
 354     {
 355       Array<Rhythmic_grouping*> a (children);
 356       for (int i=0; i < a.size(); i++)
 357         {
 358           a[i] =new Rhythmic_grouping (*children[i]);
 359           a[i]->translate (children.top()->interval ().right);
 360         }
 361       ((Rhythmic_grouping*)this)->children.concat (a);
 362     }
 363   assert (m.right <= interval().right);
 364   OK();
 365 }
 366
 367 Rhythmic_grouping
 368 parse_grouping (Array<int> beat_i_arr, Array<Moment> elt_length_arr)
 369 {
 370   Moment here =0;
 371   assert (beat_i_arr.size() == elt_length_arr.size ());
 372
 373   Array<Rhythmic_grouping*> children;
 374   for (int i=0; i < beat_i_arr.size(); i++)
 375     {
 376       Moment last = here;
 377       here += elt_length_arr[i] * Moment (beat_i_arr[i]);
 378       children.push (
 379                      new Rhythmic_grouping (MInterval (last, here),
 380                                             beat_i_arr[i]));
 381     }
 382   return Rhythmic_grouping (children);
 383 }
 384