1 /****************************************************************************************
2 * Copyright (c) 2011 Ralf Engels <ralf-engels@gmx.de> *
3 * *
4 * This program is free software; you can redistribute it and/or modify it under *
5 * the terms of the GNU General Public License as published by the Free Software *
6 * Foundation; either version 2 of the License, or (at your option) version 3 or *
7 * any later version accepted by the membership of KDE e.V. (or its successor approved *
8 * by the membership of KDE e.V.), which shall act as a proxy defined in Section 14 of *
9 * version 3 of the license. *
10 * *
11 * This program is distributed in the hope that it will be useful, but WITHOUT ANY *
12 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A *
13 * PARTICULAR PURPOSE. See the GNU General Public License for more details. *
14 * *
15 * You should have received a copy of the GNU General Public License along with *
16 * this program. If not, see <http://www.gnu.org/licenses/>. *
17 ****************************************************************************************/
18
19 #define DEBUG_PREFIX "PartBias"
20
21 #include "PartBias.h"
22
23 #include "core/meta/Meta.h"
24 #include "core/support/Debug.h"
25 #include "widgets/SliderWidget.h"
26
27 #include <KLocalizedString>
28 #include <KRandom>
29
30 #include <QtGlobal> // for qRound
31 #include <QApplication>
32 #include <QGridLayout>
33 #include <QLabel>
34 #include <QSlider>
35 #include <QStyle>
36 #include <QStyleOption>
37 #include <QWidget>
38 #include <QXmlStreamReader>
39 #include <QXmlStreamWriter>
40
41 QString
i18nName() const42 Dynamic::PartBiasFactory::i18nName() const
43 { return i18nc("Name of the \"Part\" bias", "Partition"); }
44
45 QString
name() const46 Dynamic::PartBiasFactory::name() const
47 { return Dynamic::PartBias::sName(); }
48
49 QString
i18nDescription() const50 Dynamic::PartBiasFactory::i18nDescription() const
51 { return i18nc("Description of the \"Part\" bias",
52 "The \"Part\" bias fills parts of the playlist from different sub-biases."); }
53
54 Dynamic::BiasPtr
createBias()55 Dynamic::PartBiasFactory::createBias()
56 { return Dynamic::BiasPtr( new Dynamic::PartBias() ); }
57
58
59
60 /* Note:
61 We use the Ford-Fulkerson method to compute the maximum match between the bias
62 and the tracks.
63 The MatchState class will do this matching and keep track of all the needed
64 data.
65 We are not building up the full graph and we don't even compute in advance
66 all the edges.
67 */
68
69 /** This is the helper object to calculate the maximum match.
70 For the sake of the algorithm we are using every sub-bias as a source with
71 a capacity depending on it's weight.
72 Every track in the playlist is a drain with capacity 1.
73 */
74 class MatchState
75 {
76 public:
77 /** Creates the matching
78 */
MatchState(const Dynamic::PartBias * bias,const Meta::TrackList & playlist,int contextCount,int finalCount)79 MatchState( const Dynamic::PartBias *bias,
80 const Meta::TrackList& playlist,
81 int contextCount, int finalCount )
82 : m_bias( bias )
83 , m_playlist( playlist )
84 , m_contextCount( contextCount )
85 , m_sourceCount( bias->weights().count() )
86 , m_drainCount( finalCount - contextCount )
87 , m_edges( m_sourceCount * m_drainCount, false )
88 , m_edgesUsed( m_sourceCount * m_drainCount, false )
89 , m_sourceCapacity( m_sourceCount )
90 , m_sourceFlow( m_sourceCount )
91 , m_drainFlow( m_drainCount )
92 , m_drainSource( m_drainCount )
93 {
94 QList<qreal> weights = m_bias->weights();
95
96 int assignedDrainCount = 0;
97 for( int source = 0; source < m_sourceCount-1; source++ )
98 {
99 m_sourceCapacity[source] = qRound( weights[source] * m_drainCount );
100 assignedDrainCount += m_sourceCapacity[source];
101 // debug() << "MatchState: bias"<<m_bias->biases()[source]->name()<<"should match"<<m_sourceCapacity[source]<<"of"<< m_drainCount << "tracks.";
102 }
103
104 // the last bias get's all the rest
105 if( m_sourceCount > 0 )
106 m_sourceCapacity[m_sourceCount - 1] = m_drainCount - assignedDrainCount;
107
108 compute();
109 }
110
compute()111 void compute()
112 {
113 // -- initialize the values
114 for( int source = m_sourceCount-1; source >= 0; --source )
115 m_sourceFlow[source] = 0;
116
117 for( int drain = m_drainCount-1; drain >= 0; --drain )
118 {
119 m_drainFlow[drain] = 0;
120 m_drainSource[drain] = -1;
121 }
122
123 // -- get all the edges
124 Dynamic::BiasList biases = m_bias->biases();
125 for( int source = m_sourceCount-1; source >= 0; --source )
126 for( int drain = m_drainCount-1; drain >= 0; --drain )
127 {
128 m_edgesUsed[ source * m_drainCount + drain ] = false;
129
130 if( drain + m_contextCount >= m_playlist.count() )
131 continue;
132
133 m_edges[ source * m_drainCount + drain ] =
134 biases[source]->trackMatches( drain + m_contextCount,
135 m_playlist,
136 m_contextCount );
137 // debug() << "edge:" << source << "x" << drain << ":" << m_edges[ source * m_drainCount + drain ];
138 }
139
140 // find a source whose capacity is not full
141 for( int source = m_sourceCount-1; source >= 0; --source )
142 {
143 if( m_sourceFlow[source] >= m_sourceCapacity[source] )
144 continue;
145
146 for( int drain = 0; drain < m_drainCount; drain++ )
147 {
148 if( !m_edges[ source * m_drainCount + drain ] )
149 continue;
150
151 if( m_drainFlow[drain] < 1 )
152 {
153 // direct connections source to drain
154 // make a new connection
155 m_sourceFlow[source]++;
156 m_drainFlow[drain]++;
157 m_drainSource[drain] = source;
158 m_edgesUsed[ source * m_drainCount + drain ] = true;
159 }
160 else
161 {
162 // indirect connections source to drain to source to drain
163 // or in other words: Check if we can re-order another source
164 // to get a connection for this source
165 int source2 = m_drainSource[drain];
166
167 for( int drain2 = m_drainCount-1; drain2 >= 0; --drain2 )
168 {
169 if( m_drainFlow[drain2] > 0 )
170 continue;
171 if( !m_edgesUsed[ source2 * m_drainCount + drain ] )
172 continue;
173 if( !m_edges[ source2 * m_drainCount + drain2 ] )
174 continue;
175
176 // revert the old connection
177 m_sourceFlow[source2]--;
178 m_drainFlow[drain]--;
179 m_edgesUsed[ source2 * m_drainCount + drain ] = false;
180
181 // make two new connections
182 m_sourceFlow[source]++;
183 m_drainFlow[drain]++;
184 m_drainSource[drain] = source;
185 m_edgesUsed[ source * m_drainCount + drain ] = true;
186
187 m_sourceFlow[source2]++;
188 m_drainFlow[drain2]++;
189 m_drainSource[drain2] = source2;
190 m_edgesUsed[ source2 * m_drainCount + drain2 ] = true;
191 break;
192 }
193
194 }
195
196 // finished with this source?
197 if( m_sourceFlow[source] >= m_sourceCapacity[source] )
198 break;
199 }
200 }
201 }
202
203
204 const Dynamic::PartBias* const m_bias;
205 const Meta::TrackList& m_playlist;
206 int m_contextCount;
207
208 int m_sourceCount;
209 int m_drainCount;
210 QBitArray m_edges;
211 QBitArray m_edgesUsed;
212
213 QVector<int> m_sourceCapacity;
214 QVector<int> m_sourceFlow;
215 QVector<int> m_drainFlow;
216 QVector<int> m_drainSource; // the source currently used by the drain
217 };
218
219 // -------- PartBiasWidget -----------
220
PartBiasWidget(Dynamic::PartBias * bias,QWidget * parent)221 Dynamic::PartBiasWidget::PartBiasWidget( Dynamic::PartBias* bias, QWidget* parent )
222 : QWidget( parent )
223 , m_inSignal( false )
224 , m_bias( bias )
225 {
226 connect( bias, &PartBias::biasAppended,
227 this, &PartBiasWidget::biasAppended );
228
229 connect( bias, &PartBias::biasRemoved,
230 this, &PartBiasWidget::biasRemoved );
231
232 connect( bias, &PartBias::biasMoved,
233 this, &PartBiasWidget::biasMoved );
234
235 connect( bias, &PartBias::weightsChanged,
236 this, &PartBiasWidget::biasWeightsChanged );
237
238 m_layout = new QGridLayout( this );
239
240 // -- add all sub-bias widgets
241 foreach( Dynamic::BiasPtr bias, m_bias->biases() )
242 {
243 biasAppended( bias );
244 }
245 }
246
247 void
biasAppended(Dynamic::BiasPtr bias)248 Dynamic::PartBiasWidget::biasAppended( Dynamic::BiasPtr bias )
249 {
250 int index = m_bias->biases().indexOf( bias );
251
252 Amarok::Slider* slider = 0;
253 slider = new Amarok::Slider( Qt::Horizontal, 100 );
254 slider->setValue( m_bias->weights()[ m_bias->biases().indexOf( bias ) ] * 100.0 );
255 slider->setToolTip( i18n( "This controls what portion of the playlist should match the criteria" ) );
256 connect( slider, &Amarok::Slider::valueChanged, this, &PartBiasWidget::sliderValueChanged );
257
258 QLabel* label = new QLabel( bias->toString() );
259
260 m_sliders.append( slider );
261 m_widgets.append( label );
262 // -- add the widget (with slider)
263 m_layout->addWidget( slider, index, 0 );
264 m_layout->addWidget( label, index, 1 );
265 }
266
267 void
biasRemoved(int pos)268 Dynamic::PartBiasWidget::biasRemoved( int pos )
269 {
270 m_layout->takeAt( pos * 2 );
271 m_layout->takeAt( pos * 2 );
272 m_sliders.takeAt( pos )->deleteLater();
273 m_widgets.takeAt( pos )->deleteLater();
274 }
275
276 void
biasMoved(int from,int to)277 Dynamic::PartBiasWidget::biasMoved( int from, int to )
278 {
279 QSlider* slider = m_sliders.takeAt( from );
280 m_sliders.insert( to, slider );
281
282 QWidget* widget = m_widgets.takeAt( from );
283 m_widgets.insert( to, widget );
284
285 // -- move the item in the layout
286 // TODO
287 /*
288 m_layout->insertWidget( to * 2, slider );
289 m_layout->insertWidget( to * 2 + 1, widget );
290 */
291 }
292
293 void
sliderValueChanged(int val)294 Dynamic::PartBiasWidget::sliderValueChanged( int val )
295 {
296 DEBUG_BLOCK;
297 // protect against recursion
298 if( m_inSignal )
299 return;
300
301 for( int i = 0; i < m_sliders.count(); i++ )
302 {
303 if( m_sliders.at(i) == sender() )
304 m_bias->changeBiasWeight( i, qreal(val) / 100.0 );
305 }
306 }
307
308 void
biasWeightsChanged()309 Dynamic::PartBiasWidget::biasWeightsChanged()
310 {
311 DEBUG_BLOCK;
312 // protect against recursion
313 if( m_inSignal )
314 return;
315
316 m_inSignal = true;
317
318 QList<qreal> weights = m_bias->weights();
319 for( int i = 0; i < weights.count() && i < m_sliders.count(); i++ )
320 m_sliders.at(i)->setValue( weights.at(i) * 100.0 );
321
322 m_inSignal = false;
323 }
324
325
326
327 // ----------- PartBias ----------------
328
PartBias()329 Dynamic::PartBias::PartBias()
330 : AndBias()
331 {
332 // add weights for already existing biases
333 for( int i = 0; i < biases().count(); i++ )
334 m_weights.append( 1.0 / biases().count() );
335 }
336
337 void
fromXml(QXmlStreamReader * reader)338 Dynamic::PartBias::fromXml( QXmlStreamReader *reader )
339 {
340 QList<qreal> weights; // we have to add all biases before we can set their weights
341
342 while (!reader->atEnd()) {
343 reader->readNext();
344
345 if( reader->isStartElement() )
346 {
347 float weight = reader->attributes().value( QStringLiteral("weight") ).toString().toFloat();
348 Dynamic::BiasPtr bias( Dynamic::BiasFactory::fromXml( reader ) );
349 if( bias )
350 {
351 appendBias( bias );
352 weights.append( weight );
353 }
354 else
355 {
356 warning()<<"Unexpected xml start element"<<reader->name()<<"in input";
357 reader->skipCurrentElement();
358 }
359 }
360 else if( reader->isEndElement() )
361 {
362 break;
363 }
364 }
365
366 m_weights = weights;
367 }
368
369 void
toXml(QXmlStreamWriter * writer) const370 Dynamic::PartBias::toXml( QXmlStreamWriter *writer ) const
371 {
372 for( int i = 0; i < m_biases.count(); i++ )
373 {
374 writer->writeStartElement( m_biases[i]->name() );
375 writer->writeAttribute( QStringLiteral("weight"), QString::number(m_weights[i]) );
376 m_biases[i]->toXml( writer );
377 writer->writeEndElement();
378 }
379 }
380
381 QString
sName()382 Dynamic::PartBias::sName()
383 {
384 return QStringLiteral( "partBias" );
385 }
386
387 QString
name() const388 Dynamic::PartBias::name() const
389 {
390 return Dynamic::PartBias::sName();
391 }
392
393 QString
toString() const394 Dynamic::PartBias::toString() const
395 {
396 return i18nc("Part bias representation", "Partition");
397 }
398
399
400 QWidget*
widget(QWidget * parent)401 Dynamic::PartBias::widget( QWidget* parent )
402 {
403 return new Dynamic::PartBiasWidget( this, parent );
404 }
405
406 void
paintOperator(QPainter * painter,const QRect & rect,Dynamic::AbstractBias * bias)407 Dynamic::PartBias::paintOperator( QPainter* painter, const QRect& rect, Dynamic::AbstractBias* bias )
408 {
409 int index = m_biases.indexOf( Dynamic::BiasPtr(bias) );
410 if( index < 0 )
411 return;
412
413 QStyleOptionProgressBar progressBarOption;
414 progressBarOption.rect = rect.adjusted( 2, 2, -2, -2 );
415 progressBarOption.minimum = 0;
416 progressBarOption.maximum = 100;
417 progressBarOption.progress = m_weights[index] * 100.0;
418
419 QApplication::style()->drawControl(QStyle::CE_ProgressBar, &progressBarOption, painter);
420 }
421
422 QList<qreal>
weights() const423 Dynamic::PartBias::weights() const
424 {
425 return m_weights;
426 }
427
428 Dynamic::TrackSet
matchingTracks(const Meta::TrackList & playlist,int contextCount,int finalCount,const Dynamic::TrackCollectionPtr & universe) const429 Dynamic::PartBias::matchingTracks( const Meta::TrackList& playlist,
430 int contextCount, int finalCount,
431 const Dynamic::TrackCollectionPtr &universe ) const
432 {
433 DEBUG_BLOCK;
434
435 // store the parameters in case we need to request additional matching tracks later
436 m_playlist = playlist;
437 m_contextCount = contextCount;
438 m_finalCount = finalCount;
439 m_universe = universe;
440
441 m_tracks = Dynamic::TrackSet();
442 m_matchingTracks.resize( m_biases.length() );
443
444 // get the matching tracks from all sub-biases
445 for( int i = 0; i < m_biases.length(); ++i )
446 m_matchingTracks[i] = m_biases[i]->matchingTracks( playlist, contextCount, finalCount, universe );
447 updateResults();
448
449 return m_tracks;
450 }
451
452 void
updateResults() const453 Dynamic::PartBias::updateResults() const
454 {
455 DEBUG_BLOCK;
456
457 // -- first check if we have valid tracks from all sub-biases
458 foreach( const Dynamic::TrackSet &tracks, m_matchingTracks )
459 if( tracks.isOutstanding() )
460 return;
461
462 // -- determine the current matching
463 MatchState state( this, m_playlist, m_contextCount, m_finalCount );
464
465 debug()<<"compute matching tracks for"<<m_finalCount<<"pc"<<m_playlist.count()<<"context:"<<m_contextCount;
466
467 // -- add all the tracks from one bias that has not fulfilled their capacity
468 // biases still missing more tracks are picked more often
469 // this prevents the problem that biases with only a few tracks always add their tracks
470 // last
471 int missingCapacity = 0;
472 for( int source = 0; source < state.m_sourceCount; source++ )
473 {
474 if( state.m_sourceFlow[source] < state.m_sourceCapacity[source] &&
475 m_matchingTracks[source].trackCount() > 0 )
476 missingCapacity += state.m_sourceCapacity[source] - state.m_sourceFlow[source];
477 }
478
479 m_tracks = Dynamic::TrackSet( m_universe, false );
480
481 // if we have some biases under-represented
482 if( missingCapacity > 0 )
483 {
484 int random = KRandom::random() % missingCapacity;
485 for( int source = 0; source < state.m_sourceCount; source++ )
486 {
487 // debug() << "PartBias::matchingTracks: biase"<<m_biases[source]->toString()<<"matches"<<state.m_sourceFlow[source]<<"out of"<<state.m_sourceCapacity[source]<<"tracks.";
488 if( state.m_sourceFlow[source] < state.m_sourceCapacity[source] &&
489 m_matchingTracks[source].trackCount() > 0 )
490 random -= state.m_sourceCapacity[source] - state.m_sourceFlow[source];
491 if( random < 0 )
492 {
493 m_tracks.unite( m_matchingTracks[source] );
494 break;
495 }
496 }
497 }
498
499 // else pick a random one.
500 }
501
502 void
resultReceived(const Dynamic::TrackSet & tracks)503 Dynamic::PartBias::resultReceived( const Dynamic::TrackSet &tracks )
504 {
505 int index = m_biases.indexOf(Dynamic::BiasPtr(qobject_cast<Dynamic::AbstractBias*>(sender())));
506 if( index < 0 ) {
507 warning() << "Got results from a bias that I don't have.";
508 return;
509 }
510 if( !m_tracks.isOutstanding() ) {
511 warning() << "currently in resultReceived but we already have a solution";
512 return;
513 }
514
515 m_matchingTracks[index] = tracks;
516 updateResults();
517
518 if( !m_tracks.isOutstanding() )
519 Q_EMIT resultReady( m_tracks );
520 }
521
522 bool
trackMatches(int position,const Meta::TrackList & playlist,int contextCount) const523 Dynamic::PartBias::trackMatches( int position,
524 const Meta::TrackList& playlist,
525 int contextCount ) const
526 {
527 MatchState state( this, playlist, contextCount, playlist.count() );
528
529 return ( state.m_drainFlow[position - contextCount] >= 0 );
530 }
531
532 void
appendBias(const Dynamic::BiasPtr & bias)533 Dynamic::PartBias::appendBias( const Dynamic::BiasPtr &bias )
534 {
535 DEBUG_BLOCK;
536 m_weights.append( qreal(0.0) );
537 changeBiasWeight( 0, m_weights.at(0) ); // fix the weights to 1.0 again.
538 AndBias::appendBias( bias );
539 }
540
541 void
moveBias(int from,int to)542 Dynamic::PartBias::moveBias( int from, int to )
543 {
544 DEBUG_BLOCK;
545 m_weights.insert( to, m_weights.takeAt( from ) );
546 AndBias::moveBias( from, to );
547 }
548
549 void
changeBiasWeight(int biasNum,qreal value)550 Dynamic::PartBias::changeBiasWeight( int biasNum, qreal value )
551 {
552 DEBUG_BLOCK;
553 Q_ASSERT( biasNum >= 0 && biasNum < m_weights.count() );
554
555 // the weights should sum up to 1.0
556
557 // -- only one weight. that is easy
558 if( m_weights.count() == 1 )
559 {
560 if( m_weights.at(0) != 1.0 )
561 {
562 m_weights[0] = 1.0;
563 Q_EMIT weightsChanged();
564 }
565 return;
566 }
567
568 // -- more than one. we have to modify the remaining.
569 m_weights[biasNum] = qBound( qreal( 0.0 ), value, qreal( 1.0 ) );
570
571 // - sum up all the weights
572 qreal sum = 0.0;
573 foreach( qreal v, m_weights )
574 sum += v;
575
576 // -- we are always using the first value to balance it out if possible
577 if( biasNum != 0 )
578 {
579 qreal oldV = m_weights.at(0);
580 qreal newV = qBound<qreal>( qreal( 0.0 ), 1.0 - (sum - oldV), qreal( 1.0 ) );
581 m_weights[0] = newV;
582
583 sum = sum - oldV + newV;
584 }
585
586 // modify all the remaining value
587
588 if( sum != 1.0 )
589 {
590 if( sum - m_weights.at(biasNum) == 0.0 )
591 {
592 // in this case the entry has all the weight.
593 // distribute the remainder to the other weights
594 for( int i = 0; i < m_weights.count(); i++ )
595 if( i != biasNum )
596 m_weights[i] = sum / (m_weights.count() - 1);
597
598 }
599 else
600 {
601 // in this case we have some remaining weights. use a factor
602 qreal factor = (1.0 - m_weights.at(biasNum)) / (sum - m_weights.at(biasNum));
603 for( int i = 0; i < m_weights.count(); i++ )
604 if( i != biasNum )
605 m_weights[i] *= factor;
606 }
607 }
608
609 for( int i = 0; i < m_weights.count(); i++ )
610 debug() << "Weight"<<i<<":"<<m_weights[i];
611
612 Q_EMIT weightsChanged();
613 Q_EMIT changed( BiasPtr( this ) );
614 }
615
616 void
biasReplaced(const Dynamic::BiasPtr & oldBias,const Dynamic::BiasPtr & newBias)617 Dynamic::PartBias::biasReplaced( const Dynamic::BiasPtr &oldBias, const Dynamic::BiasPtr &newBias )
618 {
619 DEBUG_BLOCK;
620 int index = m_biases.indexOf( oldBias );
621 if( !newBias )
622 {
623 m_weights.takeAt( index );
624 if( !m_weights.isEmpty() )
625 changeBiasWeight( 0, m_weights.at(0) ); // fix the weights to 1.0 again.
626 }
627
628 AndBias::biasReplaced( oldBias, newBias );
629 }
630
631
632