Сравнение элементов в общем списке

Question

Ранее в этом году я написал реализацию связанного списка для своего Java-класса. Это универсальный класс, называемый LList. Теперь нам нужно выписать алгоритм сортировки слиянием для лаборатории. Вместо того чтобы создавать новую реализацию List, которая использует Ints, я решил просто повторно использовать общий список, который я создал ранее.

Проблема в том, как сравнить два общих объекта? Ява не позволит мне сделать что-то вроде

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

ПРИМЕЧАНИЕ: весь класс LList можно найти [здесь] (http://rapidshare.com/files/219112739/LList.java.html MD5: BDA8217D0756CC171032FDBDE1539478)

Answer 1

Обратите внимание, что Comparable также является универсальным типом, параметризованным тем, с каким типом он сопоставим. Наиболее общий типобезопасный способ объявления вашей функции mergeSort выше:

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

Это обеспечивает, что метод compareTo типа T может принимать аргумент типа T. (Теоретически, тип может реализовывать Comparable, но не быть сопоставимым с самим собой, как SomeClass implements Comparable<CompletelyDifferentClass>, поэтому важно иметь требование параметр типа Comparable. Однако на практике любой хорошо спроектированный класс Comparable должен быть сравним по крайней мере с самим собой.)

Мы требуем, чтобы <T extends Comparable<? super T>> вместо <T extends Comparable<T>>, потому что все в порядке, если метод compareTo типа T принимает более общий тип, чем T, потому что он все еще мог бы принимать аргумент типа T. Это важно, потому что, если у вас есть класс A, который реализует Comparable<A>; и затем у вас есть подкласс B, который расширяет A, B не может реализовать Comparable<B>, потому что B уже реализует Comparable<A>, унаследованный от A, и класс не может реализовать интерфейс дважды. Поэтому, если бы нам потребовалось <T extends Comparable<T>> выше, B не удовлетворил бы его, и мы не смогли бы отсортировать LList<B> объектов.

Answer 2

Посмотрите на Comparator и Comparable интерфейсы.

Ваш метод сортировки должен принимать Comparator или вы должны указать , чтобы можно было использовать интерфейс 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 3

Ну, как вы обнаружили, у вас есть проблема. Все, что вы знаете об объектах в вашем списке, это то, что они являются экземплярами Object или одного из его подклассов. Вы не можете на самом деле сортировать объекты. Теперь у вас есть несколько вариантов:

Один из вариантов, который у вас есть, - сортировать что-то совершенно бессмысленное, например, хэш-код для объекта. Фактически вы можете реализовать совершенно корректную сортировку с использованием hashCode, но это было бы в значительной степени бессмысленно, поскольку хеш-код фактически ничего не значит, и нет особой причины сортировать его, кроме как узнать о сортировке.

Вот гораздо лучший способ: изменить правила вашего общего списка. Прямо сейчас все в вашем списке должно быть чем-то вроде этого. Почему бы не изменить это так, чтобы оно могло быть чем-то, что реализует интерфейс Comparable? Таким образом, вам не нужно ничего знать об объектах, кроме как сравнивать их. Это во многом то, как сама Java решает эту проблему. (Я рекомендую почитать о его коллекциях).

Просто измените свой объект с LList<T> на LList<T extends Comparable<T>> и все готово!

Answer 4

Что-то, что работало для меня в C # framework, которое я сделал. Создает объект сравнения для типизированного объекта и использует отражение, чтобы определить значение свойства, по которому сортируется список. Твик по мере необходимости:

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

Answer 5

Вы должны использовать интерфейс Comparable .

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

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

Обратите внимание: это довольно небрежно. Я нигде не проверяю, что headNode.data на самом деле является сопоставимым объектом. Мы действительно должны выбросить исключение, если это так.