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