# Re: problem with constraints algorithm

From: Harald Alvestrand <harald@alvestrand.no>
Date: Thu, 19 Jul 2012 22:25:28 +0200
Message-ID: <50086D38.7060607@alvestrand.no>

```On 07/19/2012 06:32 PM, Li Li wrote:
> I hope I can understand the problem with the following example, where track T1 fails the optional constraint O1 and T2 passes O1 but fails O2:
>
> 	O1	O2
> T1	0	1
> T2	1	0
>
> In this case, the algorithm rolls back O2 and returns {T2}.
>
> However, the selected track may skip high priority constraint. For example, the algorithm returns {T1} even though T1 does not satisfy O2:
>
> 	O2	O1
> T1	0	1
> T2	0	0
Can you please show the constraint description you are imagining here in
the proposed syntax?

I *think* you intend

optional [
{O2: true}
{O1: true}
]

In that case, the algorithm will try to apply O2, get the empty set
back, and therefore disregard that constraint, which should satisfy the
requester. If the requester had really meant to require O2, he would
have listed it as a mandatory constraint.

>If this is the algorithm we want, it can be described in an abstract way that's independent of implementations:
>
>Given a set of candidate tracks Ti, and an ordered list of optional constraints Oj, let m(Ti,Oj)=1 if Ti matches Oj >and 0 otherwise.
>Let m(Ti)=the binary number formed by m(Ti,Oj) for all Oj.
>Select all Ti whose m(Ti) are the greatest (ties permitted).

At first glance, I think that's equivalent. So that's one valid implementation of the algorithm.

>
> Thanks.
> Li
>
> -----Original Message-----
> From: Harald Alvestrand [mailto:harald@alvestrand.no]
> Sent: Wednesday, July 18, 2012 11:22 AM
> To: public-webrtc@w3.org
> Subject: Re: problem with constraints algorithm
>
> My problem with Cullen's note is that I've read it a couple of times
> now, and can't figure out what the change is - he describes the desired
> algorithm exactly the way I parsed the text that he says is wrong.
>
> In particular, this paragraph:
>
> 	3  If the secondPassSet is now empty, let the secondPassSet be
> the current contents of the candidateSet. Otherwise, let the
> candidateSet be the current contents of the secondPassSet.
>
>
> which I parse as
>
>      if (secondPassSet.empty()) {
>         secondPassSet = candidateSet; // Restore secondPassSet to what it was before 5.2
>      } else {
>         candidateSet = secondPassSet; // Remember what we successfully reduced to
>      }
>
> matches my parse of Cullen's language exactly.
>
> Somewhere I must be parsing it wrong.
>
>           Harald
>
>
>
>
> On 07/13/2012 08:34 PM, Cullen Jennings wrote:
>> makes sense ... I don't see any reason not to apply all the constraints that can be satisfied even after a higher priority constraint fails.
>>
>> On Jul 10, 2012, at 13:47 , Jim Barnett wrote:
>>
>>> That seems right.  One question:  in that case (where an optional
>>> constraint has removed all the tracks), should  we proceed to subsequent
>>> constraints?  They are all lower priority than the one that just
>>> resulted in an empty track list.  I don't know how intuitive it is to
>>> skip a constraint and then apply a bunch of lower-priority ones.  It
>>> might be clearest to say that we go as far down the list of optional
>>> constraints as we can go (and still keep a non-null track list), and
>>> then stop.
>>>
>>> In either case, the algorithm will need to keep track of the last
>>> non-null value of the secondPassSet.
>>>
>>> - Jim
>>>
>>> -----Original Message-----
>>> From: Cullen Jennings (fluffy) [mailto:fluffy@cisco.com]
>>> Sent: Tuesday, July 10, 2012 4:16 PM
>>> To: public-webrtc@w3.org
>>> Subject: problem with constraints algorithm
>>>
>>>
>>> It currently says
>>>
>>> 4 Let the secondPassSet be the current contents of the candidateSet.
>>>
>>> 5  For each constraint key-value pair in the "optional" sequence of the
>>> constraints that are for the current media type, in order,
>>>
>>> 	1  If the constraint is not supported by the browser, skip it
>>> and continue with the next constraint.
>>>
>>> 	2  Remove from the secondPassSet any tracks that cannot satisfy
>>> the value given for the constraint.
>>>
>>> 	3  If the secondPassSet is now empty, let the secondPassSet be
>>> the current contents of the candidateSet. Otherwise, let the
>>> candidateSet be the current contents of the secondPassSet.
>>>
>>>
>>>
>>>
>>> But in 5.3, I think it should go back to what it was before 5.2 not what
>>> it was in step 5. Think of the case where an earlier constraint removed
>>> some but not all of the tracks. Then a later constraint removed all the
>>> tracks - it's the effect of the last constrains that we want to roll
>>> back.
>>>
>>> If this does not make sense, I provide a more detailed example.
>>>
>>>
>>>
>>>
>
>
>
```
Received on Thursday, 19 July 2012 20:27:11 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 19:17:30 UTC