Geek Answers Handbook

What to use? IComparable generic or non-generic in this scenario

I have a generic BST and a dataItem class to act as a treeNode value.

public class BinarySearchTree<T> : ICollection<T> where T : IComparable { } public class EnglishDictionaryWord : IComparer<EnglishDictionaryWord>, IComparable<EnglishDictionaryWord> { public EnglishDictionaryWord(string word, WordCompareType type) { Word = word; Length = Word.Length; _compareType = type; } public int Compare(EnglishDictionaryWord x, EnglishDictionaryWord y) { if (_compareType == WordCompareType.Length) return new WordLengthComparer().Compare(x, y); else if (_compareType == WordCompareType.Lexical) return new WordLexicalComparer().Compare(x, y); else throw new InvalidOperationException("Unsupported Comparison type"); } public int CompareTo(EnglishDictionaryWord obj) { return Compare(this, obj); } } public class WordLengthComparer : IComparer<EnglishDictionaryWord> { public WordLengthComparer() { } public int Compare(EnglishDictionaryWord x, EnglishDictionaryWord y) { return x.Length - y.Length; } } and similar Lexical comparer class.

Now when I try to use:

 BinarySearchTree<EnglishDictionaryWord> _tree = new BinarySearchTree<EnglishDictionaryWord>();

I get a compilation error:

The type "DsLib.EnglishDictionaryWord" cannot be used as a parameter of type "T" in the generic type or method "DsLib.BinarySearchTree". There is no implicit conversion of links from "DsLib.EnglishDictionaryWord" to "System.IComparable".

If I try to do

 public class BinarySearchTree<T> : ICollection<T> where T : IComparable<T>

then I get this compilation error about the impossibility of converting a box.

Type 'T' cannot be used as a parameter of type 'T' in a generic type or method 'DsLib.BinaryTreeNode'. There is no conversion of box conversion or conversion of type parameters from "T" to "System.IComparable".

I have 2 questions:

(1). I am confused about the implementation of generics. Can anyone clarify how to fix it? and a general outline to avoid such errors in the future. When to use IComparable<T> and when to IComparable .

(2). Is this comparison template having a comparator inside the dataitem class correct? Because the user will provide a new EnglishWord for insertion into the tree. It can potentially use different comparisons for each word. Then he will destroy the tree.

EDIT: Added BSTNode class code

 public class BinaryTreeNode<T> where T : IComparable { public BinaryTreeNode(T value) { Value = value; } public T Value { get; protected internal set; } public BinaryTreeNode<T> Right { get; protected internal set; } public BinaryTreeNode<T> Left { get; protected internal set; } public BinaryTreeNode<T> Parent { get; protected internal set; } public int Height { get; protected internal set; } }
+4
source share
3 answers

I tried my code with the following definitions:

  public class BinarySearchTree<T> : ICollection<T> where T : IComparable<T> public class EnglishDictionaryWord : IComparer<EnglishDictionaryWord>, IComparable<EnglishDictionaryWord> public class WordLengthComparer : IComparer<EnglishDictionaryWord>

and it works just fine - it compiles, executes, etc. (.NET 4.0, C #):

  BinarySearchTree<EnglishDictionaryWord> _tree = new BinarySearchTree<EnglishDictionaryWord>();

And to answer your other questions:

  • You should always use IComparable<T> instead of IComparable . It is faster and less error prone (without casting / boxing / unpacking), etc. As for your question: why is this required? it's simple - IComparable<T> and IComparable are different types (they have similar names, but don't let this confuse you - the types are different). Thus, you just need to put the same type that is referenced.

  • Data inserted into the tree must have a comparison logic. When you define a tree, you precisely determine what types of elements it will work with - so as long as this object lives, you cannot add a completely different type to it. For example, if you define:

    BinarySearchTree<EnglishDictionaryWord> _tree;

you cannot add anything else to _tree , such as SpanglishDictionaryWord , so the tree preserves the structure correctly, because only EnglishDictionaryWord elements are added, and they determined the structure and the comparative logic that will correspond.

EDIT I just saw that you have the comparison logic "Has" and not pure "Is" comparable. This should be fixed (remove the link to the comparator from the data elements) - if not, you are right - the tree may break ...

EDIT2 If you need data elements for flexible comparison logic (i.e. change the way they are compared, which is strange, think about it), then BST should have a link to the instance of the resolver that you are going to use with it: either put elements that wrap both the comparator and the actual element either put Comparer elements as a BST property and use this for each data element when choosing which branch.

+1
source

You also need to change the BinaryTreeNode :

 public class BinaryTreeNode<T> where T : IComparable<T>
+1
source

It compiles if I change to IComparable<T> everywhere in tree related classes / methods. Why is this required?

IComparable<T> not inherited from IComparable .

and the second question?

You are right - if different elements have different types of sorting, the list will not work correctly. The best example is for each type to have a single default behavior, and then allow the collection to accept and use alternative IComparers. To see this in action, look at the Enumerable.OrderBy overloads.

+1
source

More articles:


All Articles