enforce()?

[Steven Schveighoffer]

On Mon, 19 Jul 2010 11:10:03 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> On 07/19/2010 09:27 AM, Steven Schveighoffer wrote:
>> On Mon, 19 Jul 2010 09:36:54 -0400, Andrei Alexandrescu
>> <SeeWebsiteForEmail at erdani.org> wrote:
>>
>>> On 07/19/2010 06:36 AM, Steven Schveighoffer wrote:
>>>> Just thinking out loud here, couldn't you use the predicate already in
>>>> AssumeSorted? I mean, if you're going to pass AssumeSorted into find,
>>>> you don't want to also specify the predicate as then the range just
>>>> becomes a standard range.
>>>>
>>>> There must be some kind of way to use template constraints to kill the
>>>> predicate arg to find when the range is an AssumeSorted struct. If  
>>>> not,
>>>> there should be.
>>>
>>> That's a good idea. The find predicate that could be derived from
>>> AssumeSorted's predicate pred would be !pred(a, b) && !pred(b, a).
>>>
>>> Thanks, Steve.
>>
>> You're welcome :)
>>
>> BTW, you don't need the combo predicate until the very end. Basically,
>> you do a binary search for the first element where pred(a, E) is false
>> (where E is the target), and then see if pred(E, a) is also false on
>> that element (to test for equality).
>
> You mean like this? :o)
>
> http://www.dsource.org/projects/phobos/browser/trunk/phobos/std/algorithm.d?rev=1279#L4703

Yep.  I realized after I wrote this that you probably were already doing  
it :)

Interestingly, I found that when doing the redblacktree that I tried to do  
some optimization on the lookup of an element.  Basically, while I'm going  
down the tree looking for a single element, I'm using the binary predicate  
to move left or right.  However, if I move left (i.e. it's not less), then  
that could be the element I'm looking for!  So I try the opposite of the  
predicate to see if I should return.

But when I allow multiple identical elements (i.e. multiset), I want to  
find the *first* instance of the element, the code is much simpler.  If I  
move to the left child, I store that as the "Best result so far".  Then at  
the end, I simply run the opposite predicate once on the aforementioned  
best result.

The benefit of running the opposite predicate sooner is that if the  
element is higher in the tree, I'll return quicker, but I think it ends up  
being a wash.  I'll probably change it to be the same as the multi style  
tree.

It all comes from the original code which used an int return for the  
comparison, making it just as simple to detect equality as it is to detect  
less-than.

Maybe I'm the first one to make that mistake :)

-Steve