Topics

C#•9mo ago

help with generic interface

im writing a small binary tree library for fun and ran into a small problem I made a small interface for Node and Tree: however the Node interface can only reference itself if that makes sense? public interface Node<T> where T : IComparable<T>

public interface Node<T> where T : IComparable<T>
{
    T GetValue();
    Node<T>? Getleft();
    Node<T>? GetRight();
}

public class SplayTreeNode<T> : Node<T> where T : IComparable<T>
{
    private T data;
    private SplayTreeNode<T>? left;
    private SplayTreeNode<T>? right;
    private SplayTreeNode<T>? parent;

    public SplayTreeNode(T value)
    {
        data = value;
    }

    public T GetValue()
    {
        return data;
    }

    public SplayTreeNode<T>? Getleft()
    {
        return left;
    }

    public SplayTreeNode<T>? GetRight()
    {
        return right;
    }
}

public interface Node<T> where T : IComparable<T>
{
    T GetValue();
    Node<T>? Getleft();
    Node<T>? GetRight();
}

public class SplayTreeNode<T> : Node<T> where T : IComparable<T>
{
    private T data;
    private SplayTreeNode<T>? left;
    private SplayTreeNode<T>? right;
    private SplayTreeNode<T>? parent;

    public SplayTreeNode(T value)
    {
        data = value;
    }

    public T GetValue()
    {
        return data;
    }

    public SplayTreeNode<T>? Getleft()
    {
        return left;
    }

    public SplayTreeNode<T>? GetRight()
    {
        return right;
    }
}

43 Replies

potzkoOP•9mo ago

the issue here is that I want SplayTreeNode.Getleft to return a SplayTreeNode but if I make another Node like an AVLTreeNode ill want it to return an AVLTreeNode ill then maybe use the fact that they are both of type Node and put them in a Node<T> but I want my function signature to be stricter how can I do that?

TheBoxyBear•9mo ago

So you would want say a AVLTreeNode<T> : SplayTreeNode<T> to override the return type with itself? Or if all the nodes are to implement INode without inheriting between themselves, you can easily do that by exposing custom implementations using the respective return types while explicitely implementing INode to return INode

potzkoOP•9mo ago

they can't override eachother I think so AVLTreeNode can't also be a SplayTreeNode but both of them are ITreeNodes I ended up writing some abomination that works I just think its deep in an antipattern

public interface ITreeNode<T, NodeType> 
    where T : IComparable<T> 
    where NodeType : ITreeNode<T, NodeType>
{
    T GetValue();
    NodeType? GetLeft();
    NodeType? GetRight();
}

public class SplayTreeNode<T> : ITreeNode<T, SplayTreeNode<T>> 
where T : IComparable<T>
{
    private T value;
    private SplayTreeNode<T>? left;
    private SplayTreeNode<T>? right;
    private SplayTreeNode<T>? perent;


    public SplayTreeNode(T value)
    {
        this.value = value;
    }

    public T GetValue()
    {
        return value;
    }

    public SplayTreeNode<T>? GetLeft()
    {
        return left;
    }

    public SplayTreeNode<T>? GetRight()
    {
        return right;
    }
}

public interface ITreeNode<T, NodeType> 
    where T : IComparable<T> 
    where NodeType : ITreeNode<T, NodeType>
{
    T GetValue();
    NodeType? GetLeft();
    NodeType? GetRight();
}

public class SplayTreeNode<T> : ITreeNode<T, SplayTreeNode<T>> 
where T : IComparable<T>
{
    private T value;
    private SplayTreeNode<T>? left;
    private SplayTreeNode<T>? right;
    private SplayTreeNode<T>? perent;


    public SplayTreeNode(T value)
    {
        this.value = value;
    }

    public T GetValue()
    {
        return value;
    }

    public SplayTreeNode<T>? GetLeft()
    {
        return left;
    }

    public SplayTreeNode<T>? GetRight()
    {
        return right;
    }
}

the problem is that im also doing another layer over this

TheBoxyBear•9mo ago

Having the node type as a genric has advantages like writing utility methods that work with any node and and being able to return the right type

potzkoOP•9mo ago

and I end up with these types:

public interface ITree<T, NodeType, Self> where T : IComparable<T>
where NodeType: ITreeNode<T, NodeType>
where Self : ITree<T, NodeType, Self>
{...}

public class SplayTreeNode<T> : ITreeNode<T, SplayTreeNode<T>> 
where T : IComparable<T>
{...}

public interface ITree<T, NodeType, Self> where T : IComparable<T>
where NodeType: ITreeNode<T, NodeType>
where Self : ITree<T, NodeType, Self>
{...}

public class SplayTreeNode<T> : ITreeNode<T, SplayTreeNode<T>> 
where T : IComparable<T>
{...}

TheBoxyBear•9mo ago

I would however add a less specific base interface where left and right are INode By having the node type as a generic, you are forced to know it which may not always be possible. Having the second layer allows for more type safety when the node type is known while keeping the broader abstraction for when it's not

potzkoOP•9mo ago

wouldn't it still work? if I have like

ITreeNode a = SplayTreeNode
a.GetLeft.type() // ITreeNode ?

ITreeNode a = SplayTreeNode
a.GetLeft.type() // ITreeNode ?

TheBoxyBear•9mo ago

Being a base interface, the declaring type would be ITreeNode but the runtime type would be the specific class

potzkoOP•9mo ago

ah so I can still have the behavior when I do it, but not a guerentee that all the values of ITreeNode are the same class?

TheBoxyBear•9mo ago

You can reference it through the base interface and get ITreeNodes from it yes. GetLeft and GetRight would just be implemented by calling the respective implementations returning the Self type

potzkoOP•9mo ago

ah I see ty I think it should work its just super ugly...

TheBoxyBear•9mo ago

You can do that by providing default implementations for the base interface in the Self interface

potzkoOP•9mo ago

yea, the reason I want the interface is for some shared behavior

TheBoxyBear•9mo ago

Generics can get ugly :dviperShrug: just depends on your purposes. You can overengineer it for max functionality or just don't if it's not needed

potzkoOP•9mo ago

I just didn't send it here because I didn't want to write huge blobs of text 🙂 im going to write a few trees so im better off with the big type signtures I think thanks a lot 🙂

TheBoxyBear•9mo ago

(look at the declarations of numeric types for ugly but max functionality :NotLikeThis: )

public readonly struct Int32 : IComparable<int>, IConvertible, IEquatable<int>, IParsable<int>, ISpanParsable<int>, IUtf8SpanParsable<int>, System.Numerics.IAdditionOperators<int,int,int>, System.Numerics.IAdditiveIdentity<int,int>, System.Numerics.IBinaryInteger<int>, System.Numerics.IBinaryNumber<int>, System.Numerics.IBitwiseOperators<int,int,int>, System.Numerics.IComparisonOperators<int,int,bool>, System.Numerics.IDecrementOperators<int>, System.Numerics.IDivisionOperators<int,int,int>, System.Numerics.IEqualityOperators<int,int,bool>, System.Numerics.IIncrementOperators<int>, System.Numerics.IMinMaxValue<int>, System.Numerics.IModulusOperators<int,int,int>, System.Numerics.IMultiplicativeIdentity<int,int>, System.Numerics.IMultiplyOperators<int,int,int>, System.Numerics.INumber<int>, System.Numerics.INumberBase<int>, System.Numerics.IShiftOperators<int,int,int>, System.Numerics.ISignedNumber<int>, System.Numerics.ISubtractionOperators<int,int,int>, System.Numerics.IUnaryNegationOperators<int,int>, System.Numerics.IUnaryPlusOperators<int,int>

public readonly struct Int32 : IComparable<int>, IConvertible, IEquatable<int>, IParsable<int>, ISpanParsable<int>, IUtf8SpanParsable<int>, System.Numerics.IAdditionOperators<int,int,int>, System.Numerics.IAdditiveIdentity<int,int>, System.Numerics.IBinaryInteger<int>, System.Numerics.IBinaryNumber<int>, System.Numerics.IBitwiseOperators<int,int,int>, System.Numerics.IComparisonOperators<int,int,bool>, System.Numerics.IDecrementOperators<int>, System.Numerics.IDivisionOperators<int,int,int>, System.Numerics.IEqualityOperators<int,int,bool>, System.Numerics.IIncrementOperators<int>, System.Numerics.IMinMaxValue<int>, System.Numerics.IModulusOperators<int,int,int>, System.Numerics.IMultiplicativeIdentity<int,int>, System.Numerics.IMultiplyOperators<int,int,int>, System.Numerics.INumber<int>, System.Numerics.INumberBase<int>, System.Numerics.IShiftOperators<int,int,int>, System.Numerics.ISignedNumber<int>, System.Numerics.ISubtractionOperators<int,int,int>, System.Numerics.IUnaryNegationOperators<int,int>, System.Numerics.IUnaryPlusOperators<int,int>

potzkoOP•9mo ago

😱 pain

TheBoxyBear•9mo ago

It just makes sense to maximize functionality if it's to be used by millions of devs

potzkoOP•9mo ago

yea

TheBoxyBear•9mo ago

One last thing if your nodes are to be immutable at certain levels, you should consider making these layers covariant.

potzkoOP•9mo ago

huh? what do you mean?

TheBoxyBear•9mo ago

https://learn.microsoft.com/en-us/dotnet/csharp/programming-guide/concepts/covariance-contravariance/

Covariance and Contravariance (C#) - C#

Learn about covariance and contravariance and how they affect assignment compatibility. See a code example that demonstrates the differences between them.

potzkoOP•9mo ago

oh, so if I can't change a leaf for example

TheBoxyBear•9mo ago

ITreeNode<object> = new AVLNode<Foo>() would be supported As long as ITreeNode is immutable

potzkoOP•9mo ago

hmm I don't think I can guerentee that

TheBoxyBear•9mo ago

Then covariance doesn't make sense in this scenario and shouldn't be forced

potzkoOP•9mo ago

as all trees have pointers to their children and an insert will change them yea, in rust I think I had the same idea, just didn't do it because of that ownership of data is hard in these structures

TheBoxyBear•9mo ago

But an example is IEnumerable<T>. Since those are immutable, T is marked as covariant and you can do IEnumerable<object> = new Foo[10]

potzkoOP•9mo ago

ah yea so you can quicly cast from one to another maybe I can do some covariants but I don't think I will do em only me writing the code lol

TheBoxyBear•9mo ago

Not quite cast as Foo to object is implicit. Just smarter type-safety

potzkoOP•9mo ago

I see

TheBoxyBear•9mo ago

The same way you can do object = Foo but wrapped in the context of a read-only generic

potzkoOP•9mo ago

one last question if you don't mind

TheBoxyBear•9mo ago

sure

potzkoOP•9mo ago

in my Itreenode I implemented a generic search min/max functions:

public interface ITreeNode<T, NodeType> 
    where T : IComparable<T> 
    where NodeType : ITreeNode<T, NodeType>
{
    T GetValue();
    NodeType? GetLeft();
    NodeType? GetRight();
    T GetMax() {
        ITreeNode<T, NodeType>  tmp = this;
        while (tmp.GetRight != null) {
            tmp = tmp.GetRight()!;
        }
        return tmp.GetValue();
    }
    T GetMin() {
        ITreeNode<T, NodeType>  tmp = this;
        while (tmp.GetLeft != null) {
            tmp = tmp.GetLeft()!;
        }
        return tmp.GetValue();
    }
}

public interface ITreeNode<T, NodeType> 
    where T : IComparable<T> 
    where NodeType : ITreeNode<T, NodeType>
{
    T GetValue();
    NodeType? GetLeft();
    NodeType? GetRight();
    T GetMax() {
        ITreeNode<T, NodeType>  tmp = this;
        while (tmp.GetRight != null) {
            tmp = tmp.GetRight()!;
        }
        return tmp.GetValue();
    }
    T GetMin() {
        ITreeNode<T, NodeType>  tmp = this;
        while (tmp.GetLeft != null) {
            tmp = tmp.GetLeft()!;
        }
        return tmp.GetValue();
    }
}

when I write my tree it still asks me to implement them why is that? can it not just use the ones I wrote for the interface?

TheBoxyBear•9mo ago

In what context are you calling them? Default implementations are only visible when accessed through the interface and aren't implemented to be visible in the type Also may not be related but in the while loops you're accessing GetLeft/Right without calling 🙂

potzkoOP•9mo ago

I have the Node implementing the TreeNode as normal without the GetMin/GetMax:

public class SimpleTreeNode<T> : ITreeNode<T, SimpleTreeNode<T>> where T : IComparable<T>
...

public class SimpleTreeNode<T> : ITreeNode<T, SimpleTreeNode<T>> where T : IComparable<T>
...

and then when I try to use it

class SimpleTree<T> : ITree<T, SimpleTreeNode<T>, SimpleTree<T>>
where T : IComparable<T>
{
    SimpleTreeNode<T>? root;

    public T? GetMax()
    {
        if (this.root == null) {return default(T);}
        return this.GetRoot()!.GetMax();
    }
}

class SimpleTree<T> : ITree<T, SimpleTreeNode<T>, SimpleTree<T>>
where T : IComparable<T>
{
    SimpleTreeNode<T>? root;

    public T? GetMax()
    {
        if (this.root == null) {return default(T);}
        return this.GetRoot()!.GetMax();
    }
}

I get

'SimpleTreeNode<T>' does not contain a definition for 'GetMax' and no accessible extension method 'GetMax' accepting a first argument of type 'SimpleTreeNode<T>' could be found (are you missing a using directive or an assembly reference?)

'SimpleTreeNode<T>' does not contain a definition for 'GetMax' and no accessible extension method 'GetMax' accepting a first argument of type 'SimpleTreeNode<T>' could be found (are you missing a using directive or an assembly reference?)

oh oops ty 🙂

TheBoxyBear•9mo ago

As mentionned, you won't be able to call the default implemented methods from the class. They are only visible when accessing through the interface

potzkoOP•9mo ago

so I have to cast it first?

TheBoxyBear•9mo ago

That's one approach but the class should also implement it directly so it's exposed without having to cast everywhere

potzkoOP•9mo ago

ah I should cast once, inside my SimpleTreeNode class and have then there is no need to cast outside it

TheBoxyBear•9mo ago

Just keep in mind boxing if implementing the interface in a struct

potzkoOP•9mo ago

I see, thenks a lot, ill get to implementing some trees then 🙂 oh I can just add the accessibility thing to my interface and then I can acceess it is internal for optimization or visibility? ah now I think I get it actually no its not working how I think it works lol it looks neat, but I think ill stick to the explicit definitions everywhere as im only going to implement like 5-6 trees I think

We are a programming server aimed at coders discussing everything related to C# (CSharp) and .NET.

54KMembers

View on Discord

Want results from more Discord servers?

Add your server