src/grouping.cc

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