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 :)
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
