Question

今年早些时候，我为我的java类编写了一个链表实现。这是一个名为LList的泛型类。我们现在必须为实验室编写合并排序算法。我决定重新使用之前创建的通用列表，而不是创建一个使用Ints的新列表实现。

The problem is how do I compare two generic objects? java wont let me do something like

if(first.headNode.data > second.headNode.data)

所以，我的问题是，它们是否是实现某种对任何类型的数据都有效的比较函数的一种方法？我尝试了以下操作：

        String one, two;
        one = first.headNode.data.toString();
        two = second.headNode.data.toString();
        if(first.headNode.data.compareTo(second.headNode.data) < 0) {
            result.add(first.headNode.data);
            // remove head node. remove() takes care of list size.
            first.remove(1);
        } else {
            // If compareTo returns 0 or higher, second.headNode is lower or
            // equal to first.headNode. So it s safe to update the result
            // list
            result.add(second.headNode.data);
            second.remove(1);
        }

这甚至不能正常工作。我用数字6和12进行了测试，上面的数字在结果列表中增加了12。

相关资料：

 private LList<T> mergeSort(LList<T> list) {
    LList<T> first = new LList();
    LList<T> second = new LList();
    if (list.length() == 1) {
        return list;
    }

    int middle = list.length() / 2;
    second.headNode = list.getNodeAt(middle + 1);
    second.length = list.length() - (middle);
    // Set first half to full list, then remove the "second" half.
    first.headNode = list.headNode;
    first.length = middle;
    first.getNodeAt(middle).next = null;

    // Get the splitted halves.
    first = mergeSort(first);
    second = mergeSort(second);
    return merge(first, second);
}

private LList<T> merge(LList<T> first, LList<T> second) {
    LList<T> result = new LList();

    while((first.length > 0) && (second.length > 0)) {
        // Ok, lets force toString to compare stuff since generics are a pain.
        String one, two;
        one = first.headNode.data.toString();
        two = second.headNode.data.toString();
        if(one.compareTo(two)) < 0) {
            result.add(first.headNode.data);
            // remove head node. remove() takes care of list size.
            first.remove(1);
        } else {
            // If compareTo returns 0 or higher, second.headNode is lower or
            // equal to first.headNode. So it s safe to update the result
            // list
            result.add(second.headNode.data);
            second.remove(1);
        }
    }
    return result;
}

NOTE: entire LList class can be found [here](http://rapidshare.com/files/219112739/LList.java.html MD5: BDA8217D0756CC171032FDBDE1539478)

Answer 1

查看比较器和可比较的接口。

您的排序方法应该采用比较器或者您应该指定<；T extends Comparable>；，以便可以使用Comparable接口。

public void sort(Comparable<T> comparator) {
    sort(SortType.MERGE, comparator);
}
....
private LList<T> merge(LList<T> first, LList<T> second) {
    ...
        if(comparator.compare(first.headNode.data, second.headNode.data) < 0) {
    ...
}

Answer 2

请注意，Comparable也是一个泛型类型，通过可比较的类型进行参数化。声明上面的mergeSort函数的最通用、类型安全的方法是：

private <T extends Comparable<? super T>> LList<T> mergeSort(LList<T> list) { }

这强制类型T的compareTo方法可以接受类型T的参数。（理论上，一个类型可以实现Comparable，但不能与其本身相比较，就像SomeClass实现Comparable<；CompletelyDifferentClass>；一样，因此对Comparable的类型参数有要求是很重要的。然而，在实践中，任何精心设计的Comparable类都应该至少与自身相比较。）

我们要求<；T扩展可比较<；？超级T>>而不仅仅是<；T扩展了Comparable<；T>>，因为如果类型T的compareTo方法接受比T更通用的类型是可以的，因为它仍然能够接受类型T的参数。这很重要，因为如果你有一个类a，它实现了Comparable<；答：；然后你有一个扩展a的子类B，B不能实现＜code＞Comparable＜；B>，因为B已经实现了Comparable<；答：，并且一个类不能实现两次接口。因此，如果我们需要＜code＞<；T扩展了Comparable<；T>>，B将不满足它，并且我们将无法对LList<；B>对象。

Answer 3


好吧，正如你所发现的，你遇到了一个问题。关于列表中的对象，您所知道的只是它们是Object的实例或其子类之一。您无法真正对对象进行排序。您现在有几个选项：

一种选择是对一些完全没有意义的东西进行排序，比如对象的hashCode。事实上，您可以使用hashCode实现一个完全有效的合并排序，但这在很大程度上是毫无意义的，因为hash代码实际上没有任何意义，除了学习排序之外，没有什么特别的理由根据它进行排序。

这里有一个更好的方法：更改通用列表的规则。现在，你列表中的所有东西都必须是某种东西。为什么不改变它，使其成为某种实现Comparable接口的东西呢？这样，除了如何比较对象之外，您不需要了解任何关于对象的信息。Java本身在很大程度上就是这样解决这个问题的。（我建议大家多读一下《收藏》的内容）。

只需将您的对象从＜code＞LList<；T>到LList<；T扩展了Comparable<；T>>，你就可以出发了！

Answer 4

您应该使用可比较接口。

Comparable one = (Comparable)first.headNode.data;
Comparable two = (Comparable)second.headNode.data;

if(one.compareTo(two) < 0)
{
  ...
}
else
{
  ...
}

请注意：这太草率了。我没有在任何地方检查headNode.data实际上是一个Comparable对象。如果是这样的话，我们真的应该抛出一个例外。

Answer 5

在我制作的C#框架中对我有用的东西。为类型化对象生成比较器对象，并使用反射来确定列表排序所依据的属性的值。根据需要进行调整：

using System;
using System.Collections.Generic;
using System.ComponentModel;

namespace BOCL
{
  /// <summary>
  /// Provides a comparer for collections of BOCL objects so they can be compared on any property
  /// </summary>
  /// <typeparam name="T">The type of BOCL object to compare</typeparam>
  public class BusinessBaseComparer<T> : IComparer<T> where T : BusinessBase<T>, new()
  {
    #region Constructors

    /// <summary>
    /// Provides a default constructor for the comparer
    /// </summary>
    protected BusinessBaseComparer()
    {
      //An instance of the business base comparer must be declared with at least one argument to be of any use
    }

    /// <summary>
    /// Build this comparer sorting on a particular property ascending
    /// </summary>
    /// <param name="property">The property on which the sort should be applied</param>
    public BusinessBaseComparer(PropertyDescriptor property)
    {
      m_SortProperty = property;
    }

    /// <summary>
    /// Build this comparer sorting on a particular property
    /// </summary>
    /// <param name="property">The property on which the sort should be applied</param>
    /// <param name="direction">The direction to which the sort should be applied</param>
    public BusinessBaseComparer(PropertyDescriptor property, ListSortDirection direction)
    {
      m_SortProperty = property;
      m_SortDirection = direction;
    }

    #endregion

    #region SortProperty

    private PropertyDescriptor m_SortProperty = null;

    /// <summary>
    /// The property on which the type is to be sorted. If the property is not found, the objects are deemed equal
    /// </summary>
    protected PropertyDescriptor SortProperty
    {
      get { return m_SortProperty; }
    }

    #endregion

    #region SortDirection

    private ListSortDirection m_SortDirection = ListSortDirection.Ascending;

    /// <summary>
    /// The direction in which the type is to be sorted
    /// </summary>
    protected ListSortDirection SortDirection
    {
      get { return m_SortDirection; }
    }

    #endregion

    #region IComparer<T> Members

    /// <summary>
    /// Performs comparison between to BOCL objects
    /// </summary>
    /// <param name="x">The first object to compare</param>
    /// <param name="y">The second object to compare</param>
    /// <returns>The result of the comparison</returns>
    public int Compare(T x, T y)
    {
      if (SortProperty == null)
        return 0; //we didn t find the property we were supposed to sort on

      //set up to get the value of the objects we are comparing against
      IComparable xValue = null;
      IComparable yValue = null;

      try
      {
        //now get the value for the x object and value for the y object
        //as something we can compare against
        xValue = (IComparable)SortProperty.GetValue(x);
        yValue = (IComparable)SortProperty.GetValue(y);

        //if either property came back null
        if (xValue == null || yValue == null)
          return 0; //treat them as the same
      }
      catch (InvalidCastException)
      {
        return 0; //ran into a proplem trying to convert the object into something we could compare against
      }


      if (SortDirection == ListSortDirection.Ascending)
        return xValue.CompareTo(yValue);
      else
        return yValue.CompareTo(xValue);
    }

    #endregion
  }
}

友情链接