Блог

У меня есть общий BST и класс DataItem, которые будут действовать как значение TreeNode.

 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.
  

Теперь, когда я пытаюсь использовать:

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

Я получаю ошибку компиляции:

Тип ‘DsLib.EnglishDictionaryWord’ не может использоваться в качестве параметра типа ‘T’ в универсальном типе или методе ‘DsLib.BinarySearchTree’. Неявное преобразование ссылки из ‘DsLib.EnglishDictionaryWord’ в ‘System’ отсутствует.IComparable’.

Если я попытаюсь сделать

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

затем я получаю эту ошибку компиляции о недоступности преобразования бокса.

Тип ‘T’ не может использоваться в качестве параметра типа ‘T’ в универсальном типе или методе ‘DsLib.BinaryTreeNode’. Нет преобразования бокса или преобразования параметра типа из ‘T’ в ‘System.IComparable’.

У меня есть 2 вопроса:

(1). Я запутался в реализации generics. Может ли кто-нибудь подробно рассказать, как это исправить? и общий шаблон, чтобы избежать подобных ошибок в будущем. Когда использовать IComparable<T> и когда IComparable .

(2). Корректен ли этот шаблон сравнения, имеющий comparer внутри класса dataitem? Потому что пользователь предоставит new EnglishWord для вставки в дерево. Потенциально он может использовать разные средства сравнения для каждого слова. Тогда это приведет к разрыву дерева.

РЕДАКТИРОВАТЬ: Добавлен код класса BSTNode

 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; }
}
  

Я попробовал ваш код со следующими определениями:

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

  public class EnglishDictionaryWord
      : IComparer<EnglishDictionaryWord>,
        IComparable<EnglishDictionaryWord>

  public class WordLengthComparer
      : IComparer<EnglishDictionaryWord>
  

и это работает просто отлично — компилируется, выполняется и т.д. … (.NET 4.0, c #):

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

И чтобы ответить на другие ваши вопросы:

1. Вы всегда должны отдавать предпочтение IComparable<T> вместо IComparable . Это быстрее и менее подвержено ошибкам (нет кастинга / упаковки / распаковки) и т.д… Что касается вашего вопроса: Зачем это требуется?все просто — IComparable<T> и IComparable — это разные типы (у них похожие названия, но пусть это вас не смущает — типы разные). Итак, вам просто нужно поместить один и тот же тип везде, где есть ссылка.

2. Данные, которые вставляются в дерево, должны иметь логику сравнения. Когда вы определяете дерево, вы точно указываете, с какими типами элементов оно будет работать, поэтому до тех пор, пока этот объект существует, вы не сможете добавить в него какой-то совершенно другой тип. Например, если вы определили:

   BinarySearchTree<EnglishDictionaryWord> _tree;