www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Red-Black tree with customized sorting

reply "Paolo Bolzoni" <paolo.bolzoni g.invalid> writes:
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
next sibling parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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 12 2013
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
parent "Ivan Kazmenko" <gassa mail.ru> writes:
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.
May 13 2013