search

abdonkov / DSA

Data structures and algorithms in C#
MIT License
682 stars 115 forks source link

Over constraining TVertex #1

Open mattwar opened 7 years ago

mattwar commented 7 years ago

You seem to constrain a lot of your TVertex declarations to ICompareable<TVertext> when most of the algorithms and data structures only ever need/use equality. You should use IEquatable<TVertex> in many places instead.

abdonkov commented 7 years ago

I use vertex comparison in my shortest paths, mst and topological sorting algorithms. Also the main reason for it to be of IComparable is that I have methods for the graph data srtuctures that return sorted incoming/outgoing edges. Also the BFS and DFS methods in the graph structure perform sorting on the vertices too.

m-carrasco commented 2 years ago

@abdonkov What about allowing the constructors to receive a IComparer rather than constraining the generic parameter? I mean this similarly to how SortedSet)) works.

abdonkov commented 2 years ago

That will mean runtime error when used incorrectly and I'm not completely sure I want that. However, something that can be done while maintaining backwards compatibility is moving the IComparable<> constraint to the BFS and DFS methods that use it and introducing a new set of BFS and DFS that do not perform any type of comparison.

m-carrasco commented 2 years ago

That will mean runtime error when used incorrectly and I'm not completely sure I want that.

Yes, you're right - you can have runtime errors.

However, something that can be done while maintaining backwards compatibility is moving the IComparable<> constraint to the BFS and DFS methods that use it and introducing a new set of BFS and DFS that do not perform any type of comparison.

Yes, this sounds like a possible solution. However, it may introduce more code and more effort to maintain it. Regardless of any particular solution, I think it would be great if IComparable is not always required. Sometimes, certain classes, have no "one size fits all" possible IComparable implementation.

abdonkov commented 2 years ago

However, it may introduce more code and more effort to maintain it.

I think it could be done by moving the BFS and DFS to a private method that uses IComparer as a parameter and when a null value is provided the sorting step will be skipped... So the same method can be used for all public methods with or without the generic constraint. This way could also allow introduction of a overload that accepts IComparer for custom sorting...