enforce()?

[Andrei Alexandrescu]

On 07/19/2010 10:24 AM, Steven Schveighoffer wrote:
> 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 :)

Yah, it's quite the STL classic. STL commonly defines implicitly 
equivalence in terms of !less(a, b) && !less(b, a) but uses only one of 
the two comparisons until the last leg, when it's testing the opposite way.

> 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.

Indeed that's 100% what STL's lower_bound and rb_tree.find do.

By the way, I'm still eagerly waiting for your red-black tree 
implementation. I think it would be pure awesomeness if you massaged the 
red/black bit inside one of the pointers. I figured out a way of doing 
that without throwing off the garbage collector:

union
{
     unsigned byte * _gcHelper;
     size_t _bits;
}
bool setRed() { _bits |= 1; }
bool setBlack() { _bits &= ~(cast(size_t) 1); }
bool isRed() { return _bits & 1; }
RBTreeNode * left()
{
     return cast(RBTreeNode *) cast(size_t) (_bits & ~(cast(size_t) 1));
}

The idea is to leave _gcHelper in there as a valid pointer to either a 
RBTreeNode or a pointer to one byte inside the RBTreeNode. That way the 
GC is never confused - it will keep the node.

I think putting that one bit inside the pointer has important consequences.

I also suggest you read up on "left-leaning red-black trees" for a 
recent alternative approach that simplifies the code a fair amount.


Andrei