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

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

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

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

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

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

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

Answer 3

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

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

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

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

Answer 4

То, что работает для меня в рамках 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 
    } 
} 

Answer 5

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

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

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

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