Ok.

So I have a BST template, and it passes my tests.

However, if you look at how I insert the data into the BST, you'll quickly notice the problem I have.

https://dpaste.dzfl.pl/ff58876ce213

Keep in mind I just pasted that stack in there because I use it in my last unittest at the bottom. It has its own file.

the method that I use is called insert, on line 79.


What Id like to do is this:

auto tree = new BSTbase!int;
...
tree.insert(7);

and

auto Tree2 = new BSTbase!Aclass;
...
Tree2.insert(Aclassobject);

What I have is:
Tree.insert(7, cast(real) 7);
and
Tree2.insert(Aclassobject, cast(real) (cast(void*) Aclassobject));

I tried a few things, but I can't get them to work.

Can anyone give a way for me to avoid doing it this clumsy way? The only otpion I can think of is just using inheritance, one for Complex Data types, and the other for primitives. But that defeats the purpose of having be a template (a little bit).


Thanks.

On 06/09/2017 05:32 AM, Mark wrote:
> https://dpaste.dzfl.pl/ff58876ce213
[...]
> What Id like to do is this:
> 
> auto tree = new BSTbase!int;
> ...
> tree.insert(7);
> 
> and
> 
> auto Tree2 = new BSTbase!Aclass;
> ...
> Tree2.insert(Aclassobject);
> 
> What I have is:
> Tree.insert(7, cast(real) 7);
> and
> Tree2.insert(Aclassobject, cast(real) (cast(void*) Aclassobject));
> 
> I tried a few things, but I can't get them to work.
> 
> Can anyone give a way for me to avoid doing it this clumsy way?

Get rid of `real val;` and just compare `payload`s. For classes, you can detect them with `static if (is(T == class))` or some such, and cast to void* when comparing.

But when you cast to void*, you're ignoring an opEquals or opCmp the class might have. That might be surprising. So maybe just require that classes implement opCmp. Or try to detect when a class doesn't have opCmp and only cast then.

On Friday, 9 June 2017 at 05:53:11 UTC, ag0aep6g wrote:
...
> Get rid of `real val;` and just compare `payload`s. For classes, you can detect them with `static if (is(T == class))` or some such, and cast to void* when comparing.
>
> But when you cast to void*, you're ignoring an opEquals or opCmp the class might have. That might be surprising. So maybe just require that classes implement opCmp. Or try to detect when a class doesn't have opCmp and only cast then.


Possibly. but I can't use those methods on primitive types. 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.

This is why I'm converting the addresses to real numbers. Which means that I have to do the same to the primitive types. I also tried using 2 different constructors, with the idea of doing all that casting stuff in there. But that didn't bode well with the compiler. It didn't know which one to use, as both are entering as type T.

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.


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.

Thanks though.

Maybe Ill just go with my inheritance idea, and have one for primitives, and one for classes.

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.

Ok. WOW!

I was way off. I adapted your code to my BST and it works perfectly.

Thanks!

I didn't know what static if was. I should experiment with it.

For the code that I mentioned, I'd have to retype it. I wrote, tried and deleted those pieces of code several days ago because it really didn't work.

On Friday, 9 June 2017 at 15:12:04 UTC, ag0aep6g wrote:
...
> 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.

 I'm not sure what you mean by this?

I'm fairly certain that all inserted nodes (not duplicates) are in fact in the tree. Also, Although  I deleted the method, I did check my size variable by traversing the tree and counting the actual number of nodes.
They matched exactly for each unit test.

??

On 06/10/2017 06:57 AM, Mark wrote:
> On Friday, 9 June 2017 at 15:12:04 UTC, ag0aep6g wrote:
> ...
>> 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.
> 
>   I'm not sure what you mean by this?

Just that you shouldn't take my version of addNode and rely on it without double checking that it's correct.

On Saturday, 10 June 2017 at 14:35:48 UTC, ag0aep6g wrote:
...
> Just that you shouldn't take my version of addNode and rely on it without double checking that it's correct.

Ah, Okay. I rechecked that everything is working. The size is correct, and the membership is correct for every insert/delete.

Thanks again.