Thread overview | ||||||
---|---|---|---|---|---|---|
|
May 12, 2013 Red-Black tree with customized sorting | ||||
---|---|---|---|---|
| ||||
I need to user Red-Black trees with non-default sorting. Here is a minimal example ---- >8 import std.container; struct CC { int a; int b; } bool less(const ref CC lhs, const ref CC rhs) { if (lhs.a != rhs.a) return lhs.a < rhs.a; else return lhs.b < rhs.b; } void main() { auto t = new RedBlackTree!(CC, "a.a != b.a ? a.a < b.a : a.b < b.b"); } 8< ---- It works, but I would like to pass the function "less" as comparison operator since in my real problem the comparison is a more complex. I tried this ways: auto t = new RedBlackTree!(CC, less); auto t = new RedBlackTree!(CC, CC); auto t = new RedBlackTree!(CC, &less); auto t = new RedBlackTree!(CC, "less(a,b)"); auto t = new RedBlackTree!(CC, "what the hell!? just call less! Is it too much to ask?"); None of them works, I am stuck. The documentation states: (quote from: http://dlang.org/phobos/std_container.html#.RedBlackTree ) """ To use a different comparison than "a < b", pass a different operator string that can be used by std.functional.binaryFun, or pass in a function, delegate, functor, or any type where less(a, b) results in a bool value. """ What is wrong? How I am supposed to pass less address to do the comparison? Thanks |
May 12, 2013 Re: Red-Black tree with customized sorting | ||||
---|---|---|---|---|
| ||||
Posted in reply to Paolo Bolzoni | On 05/12/2013 02:09 PM, Paolo Bolzoni wrote: > I need to user Red-Black trees with non-default sorting. > Here is a minimal example > ---- >8 > import std.container; > struct CC { > int a; > int b; } > > bool less(const ref CC lhs, const ref CC rhs) { > if (lhs.a != rhs.a) > return lhs.a < rhs.a; > else > return lhs.b < rhs.b; } > > void main() { > auto t = new RedBlackTree!(CC, "a.a != b.a ? a.a < b.a : a.b < > b.b"); } > 8< ---- > > It works, but I would like to pass the function "less" as comparison > operator since in my real problem the comparison is a more complex. I think this is an issue with the template constraint of RedBlackTree. It passes the alias template parameter through binaryFun and I think that fails the check: final class RedBlackTree(T, alias less = "a < b", bool allowDuplicates = false) if(is(typeof(binaryFun!less(T.init, T.init)))) A workaround: auto t = new RedBlackTree!(CC, (a, b) => less(a, b)); Ali |
May 13, 2013 Re: Red-Black tree with customized sorting | ||||
---|---|---|---|---|
| ||||
Posted in reply to Paolo Bolzoni | On Sun, 12 May 2013 17:09:56 -0400, Paolo Bolzoni <paolo.bolzoni@g.invalid> wrote: > What is wrong? How I am supposed to pass less address to do the comparison? I think it is this issue: http://d.puremagic.com/issues/show_bug.cgi?id=9513 I am going to fix this, soon. -Steve |
May 13, 2013 Re: Red-Black tree with customized sorting | ||||
---|---|---|---|---|
| ||||
Posted in reply to Steven Schveighoffer | On Monday, 13 May 2013 at 15:26:12 UTC, Steven Schveighoffer wrote:
> On Sun, 12 May 2013 17:09:56 -0400, Paolo Bolzoni <paolo.bolzoni@g.invalid> wrote:
>
>> What is wrong? How I am supposed to pass less address to do the comparison?
>
> I think it is this issue:
>
> http://d.puremagic.com/issues/show_bug.cgi?id=9513
>
> I am going to fix this, soon.
Seems so. For now, you can cheat the too strict "binaryFun" condition in this way:
bool less (T) (auto ref T lhs, auto ref T rhs)
As I understand it, this creates one instance (without refs) for the "binaryFun" condition, while another (with refs) is actually used.
|
Copyright © 1999-2021 by the D Language Foundation