Need way to compare classes, and primitive types in bst Template

ag0aep6g via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Fri Jun 9 08:12:04 PDT 2017


On 06/09/2017 04:08 PM, Mark wrote:
> Possibly. but I can't use those methods on primitive types.

Those methods implement operators. In your code you use the usual 
comparison operators: '==', '<', etc.

> Also, I 
> tried implementing a internal method to determine if it is a class, or 
> primitive, and compare based off of mem location, or actual value.
> 
> For some reason, the compiler didn't care, telling me that I can't just 
> compare two classes with < or > operators, even though I thought I 
> seperated that code out for primitives only.

Can't tell what's wrong unless you show your code.

[...]
> I then tried to implement a typeid check, I thought that would work, but 
> even though I had said if typeid.toString() was in ["int", "float", ... 
> ] call primitive func, else call class func, the compiler complained 
> that I can't throw classes into the logic of the first function. Which 
> wasn't even possible, because it wouldn't pass the type check that I made.

Sounds like that was a run-time check. It has to happen at compile time 
(e.g. using `static if`). You shouln't need typeid or strings.

> Also, I don't want to require that classes implement an opEquals. I want 
> to use this with other people's classes, as well as built-in classes. 
> That would cause problems.
> 
> And it wouldn't bypass the whole primitives/class-struct problem.

It would, because you wouldn't need any special casing. You'd just use 
the normal comparison operators with objects like you do with primitives.

--

Anyway, here's how you can detect classes and special case them when 
comparing.

----
import std.exception: enforce;

class BSTbase(T)
{
     tree_node* root = null;

     static struct tree_node
     {
         T payload;
         tree_node* left = null;
         tree_node* right = null;
     }

     static int cmp(T a, T b)
     {
         static if (is(T == class))
         {
             auto x = cast(void*) a;
             auto y = cast(void*) b;
         }
         else
         {
             alias x = a;
             alias y = b;
         }

         if (x == y) return 0;
         if (x < y) return -1;
         if (x > y) return 1;
         enforce(false);
         assert(false);
     }

     void addNode(T item)
     {
         tree_node** current = &root;

         while (*current !is null)
         {
             immutable c = cmp(item, (**current).payload);
             if (c == 0) return; /* value is already in the tree */
             else if (c > 0) current = &(*current).right;
             else if (c < 0) current = &(*current).left;
             else enforce(false);
         }

         assert(*current is null);
         *current = new tree_node(item);
     }
}

void main()
{
     auto bi = new BSTbase!int;
     bi.addNode(3);
     bi.addNode(1);
     bi.addNode(2);
     assert(bi.root.payload == 3);
     assert(bi.root.left.payload == 1);
     assert(bi.root.left.right.payload == 2);

     auto bc = new BSTbase!Object;
     auto o1 = new Object;
     auto o2 = new Object;
     bc.addNode(o1);
     bc.addNode(o2);
     assert(bc.root.payload is o1);
     if (cast(void*) o2 > cast(void*) o1)
     {
         assert(bc.root.right.payload is o2);
     }
     else  assert(bc.root.left.payload is o2);
}
----

Note that this is only supposed to show how to do the special casing for 
classes. addNode probably doesn't do exactly what it's supposed to do in 
your tree.


More information about the Digitalmars-d-learn mailing list