Topics

C#•3mo 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

potzko•3mo 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•3mo 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

potzko•3mo 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•3mo 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

potzko•3mo 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•3mo 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

potzko•3mo 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•3mo ago

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

potzko•3mo 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•3mo 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

potzko•3mo ago

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

TheBoxyBear•3mo ago

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

potzko•3mo ago

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

TheBoxyBear•3mo 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

potzko•3mo 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•3mo 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>

potzko•3mo ago

😱 pain

TheBoxyBear•3mo ago

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

potzko•3mo ago

yea

TheBoxyBear•3mo ago

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

potzko•3mo ago

huh? what do you mean?

TheBoxyBear•3mo 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.

potzko•3mo ago

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

TheBoxyBear•3mo ago

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

potzko•3mo ago

hmm I don't think I can guerentee that

TheBoxyBear•3mo ago

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

potzko•3mo 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•3mo 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]

potzko•3mo 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•3mo ago

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

potzko•3mo ago

I see

TheBoxyBear•3mo ago

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

potzko•3mo ago

one last question if you don't mind

TheBoxyBear•3mo ago

sure

potzko•3mo 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•3mo 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 🙂

potzko•3mo 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•3mo 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

potzko•3mo ago

so I have to cast it first?

TheBoxyBear•3mo ago

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

potzko•3mo ago

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

TheBoxyBear•3mo ago

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

potzko•3mo 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.

52KMembers

View on Discord

Want results from more Discord servers?

Add your server

More Posts

✅ How to run code after completing all threads?I have N threads runned in same time, and i need to optimize result of all treads into one object. A Using Out parameterI might be dumb but I can't wrap my head around the Out parameter in self defined methods. Is Out ✅ System.Data.SQLite Data TypesI'm wanting to save a float value to a relative database through the package System.Data.SQLite. I'v Curious for the use case / reasoning for using C# to make a Discord bothi, i am new to development, currently getting a foundation in PowerShell and some light C# projec Generic type that extends boolHow can I make my generic type "extend" boolean? ```c# class MyClass<T> where T : bool { } ```EF Core how can I access temporal table PeriordStart value to use it for "last modified" informationFrom the docs: `var validFrom = foo.Property<DateTime>("VALID_FROM").CurrentValue;` This works and ✅ Help with sockets c#how would i go by showing a message to every client connected to a server ?ASP.NET CORE + firebase deploying to Heroku issuesI'm creating a ASP.NET core API for my multiplayer game and at the end of every game there is a pdf Tower of hanoi, problem: a disk vanished after 2 movesCode: https://gdl.space/ifajegotok.cs yes its not cleaned up or well made or whatever but i NEED to Official .NET tutorial errors without me changing anything?Hey guys, I'm following the official .NET tutorial for creating a web app with asp.net core and blaz