On 07/19/2010 10:24 AM, Steven Schveighoffer wrote:
On Mon, 19 Jul 2010 11:10:03 -0400, Andrei Alexandrescu
<[email protected]> wrote:
On 07/19/2010 09:27 AM, Steven Schveighoffer wrote:
On Mon, 19 Jul 2010 09:36:54 -0400, Andrei Alexandrescu
<[email protected]> 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
