Sort a array list of generic objects Java

Question

I have a class Vertex which has a field element of generic type T.

I have an ArrayList of Vertex objects which I would like to sort but I am not sure how.

I tried using a Comparator which can be seen below:

listOfNeighbours.sort(new Comparator<Vertex<T>>() {
        @Override
        public int compare(Vertex<T> v1, Vertex<T> v2) {
            if(v1.getElement() == v2.getElement()){
                return 0;
            }else if(v1.getElement() < v2.getElement()) {
                return -1;
            }else {
                return 1;
            }

         }
    });

Obviously, the solution above is wrong as we are not able to compare generics but I would like something similar to this that will sort my list of Vertex objects.

In my application T can either be an Integer, Double or String.

Any help is appreciated!

Thank you.

EDIT: My Vertex class is below:

public class Vertex<T>{

private ObjectProperty<T> element;
private BooleanProperty visited;

public Vertex() {
    element = null;
    visited = new SimpleBooleanProperty(false);
}

public Vertex(T element) {
    this.element = new SimpleObjectProperty<T>(element);
    this.visited = new SimpleBooleanProperty(false);
}

public Vertex(T element, boolean visited) {
    this.element = new SimpleObjectProperty<T>(element);
    this.visited = new SimpleBooleanProperty(visited);
}

public void setElement(T elem) {
    this.element.set(elem);
}

public T getElement() {
    return this.element.get();
}

public ObjectProperty<T> elementProperty(){
    return this.element;
}

public void setVisited(boolean b) {
    this.visited.set(b);
}

public boolean isVisited() {
    return this.visited.get();
}

public BooleanProperty visitedProperty(){
    return this.visited;
}

@Override
public boolean equals(Object o) {
    if(o == this) {
        return true;
    }

    if(!(o instanceof Vertex<?>)) {
        return false;
    }

    Vertex<?> v=  (Vertex<?>) o;

    if(v.getElement() instanceof String) {
        return v.getElement().equals(this.element.get());
    }else {
        return v.getElement() == this.element.get();
    }


}

@Override
public String toString() {
    return element.get().toString();
}

}

v1.getElement() == v2.getElement() is not a comparison, it just checks memory addresses. Your code should just be return v1.getElement().compareTo(v2.getElement()). Vertex Element must implement Comparable. — K.Nicholas
– K.Nicholas, Commented Jan 15, 2019 at 17:50

glglgl · Accepted Answer · 2019-01-16 14:17:12Z

4

A Comparator is a fine thing. It has a static <T,U extends Comparable<? super U>> Comparator<T> comparing(Function<? super T,? extends U> keyExtractor) for this specific problem. In your case, that would be

listOfNeighbours.sort(Comparator.comparing(Vertex::getElement))

If your Vertex component is not Comparable, I'd suggest static <T,U> Comparator<T> comparing(Function<? super T,? extends U> keyExtractor, Comparator<? super U> keyComparator) instead which can be fed with a custom comparator.

For example,

import java.util.*;
import javafx.beans.property.*;

public class Vertex<T>{

  private ObjectProperty<T> element;
  private BooleanProperty visited;

  public Vertex() {
      element = null;
      visited = new SimpleBooleanProperty(false);
  }

  public Vertex(T element) {
      this.element = new SimpleObjectProperty<T>(element);
      this.visited = new SimpleBooleanProperty(false);
  }

  public Vertex(T element, boolean visited) {
      this.element = new SimpleObjectProperty<T>(element);
      this.visited = new SimpleBooleanProperty(visited);
  }

  public void setElement(T elem) {
      this.element.set(elem);
  }

  public T getElement() {
      return this.element.get();
  }

  public ObjectProperty<T> elementProperty(){
      return this.element;
  }

  public void setVisited(boolean b) {
      this.visited.set(b);
  }

  public boolean isVisited() {
      return this.visited.get();
  }

  public BooleanProperty visitedProperty(){
      return this.visited;
  }

  @Override
  public boolean equals(Object o) {
      if(o == this) {
          return true;
      }

      if(!(o instanceof Vertex<?>)) {
          return false;
      }

      Vertex<?> v=  (Vertex<?>) o;

      if(v.getElement() instanceof String) {
          return v.getElement().equals(this.element.get());
      }else {
          return v.getElement() == this.element.get();
      }


  }

  @Override
  public String toString() {
      return element.get().toString();
  }

  public static void main(String[] args) {
    ArrayList<Vertex<String>> listOfNeighbours = new ArrayList<>();
    listOfNeighbours.add(new Vertex<>("foo"));
    listOfNeighbours.add(new Vertex<>("bar"));
    System.out.println(listOfNeighbours);
    listOfNeighbours.sort(Comparator.comparing(Vertex::getElement));
    System.out.println(listOfNeighbours);

    ArrayList<Vertex<Integer>> list2 = new ArrayList<>();
    list2.add(new Vertex<>(1));
    list2.add(new Vertex<>(123));
    list2.add(new Vertex<>(15));
    list2.add(new Vertex<>(2));
    System.out.println(list2);
    list2.sort(Comparator.comparing(Vertex::getElement));
    System.out.println(list2);
    list2.sort(Comparator.comparing(Vertex::getElement, Comparator.comparing(i -> i.toString())));
    System.out.println(list2);
  }
}

would be how it coud be done (tested with https://www.compilejava.net/).

The results are

[foo, bar]

(original input)

[bar, foo]

(sorted by String)

[1, 123, 15, 2]

(original input)

[1, 2, 15, 123]

(sorted by Integer natural order)

[1, 123, 15, 2]

(sorted by order given for String, i. e. lexigraphically).

The latter is done with a Comparator<Vertex<Integer>> which does its work by extracting the value fron the given Vertex<Integer> and then converting it to a String, which is then used as sort key.

edited Jan 16, 2019 at 14:17

answered Jan 15, 2019 at 17:56

glglgl

91.5k13 gold badges157 silver badges230 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Valentin Ruano Over a year ago

This solution assumes that T is a Comparable<? super T> but this is not necessarily the case in general.

Valentin Ruano Over a year ago

That said I just noticed that in the question T is alaways one of Integer, Double, String all of which are Comparables so I guess this is enough as long as he indeed impose the restriction on T, as far as I can see he may have not or might not have the ability to do so if he is not on control of his Graph/Vertex class source-code, So I would still suggest to add a solution that does not make such an assumption.

glglgl Over a year ago

@ValentinRuano You are right. In this case (they can be compared, but are not Comparable), I'd suggest static <T,U> Comparator<T> comparing(Function<? super T,? extends U> keyExtractor, Comparator<? super U> keyComparator) instead.

Jaman Over a year ago

Hi guys I am still a bit confused @glglgl I tried your solution above but I get an error. It says 'The type Vertex does not define getElement(Object) that is applicable here'.

Jaman Over a year ago

Not sure if this is relevant but in my Vertex<T> class the element field is of type ObjectProperty, but my getElement() method returns of type T.

|

Valentin Ruano · Accepted Answer · 2019-01-16 16:55:25Z

1

If T is restricted to Comparable<? super T> @glglgl solution above is good enough since it seems that any of the types that T may take on based on the question are compliant.

However if T is not bounded that way and you can't or don't want to change that, the solution would be slightly more general and would required the calling code to provide explicitly a comparator for T elements as a second argument to Comparator.comparing

static <T> void sortNeightbours(Collection<Vertex<? extends T>> neighbours, Comparator<? super T> elementComparator) {
    neighbours.sort(Comparator.comparing(Vertex::getElement, elementComparator);
}

You don't need to define a separate (static) method for this it could be inlined if you like.

For vertex whose element type is a comparable like Integer, Double or String the invoking code would be the same:

   List<Vertex<Integer>> ints = ...;
   List<Vertex<Double>> dbls = ...;
   List<Vertex<String>> strs = ...;

   sortNeighbours(ints, Comparator.naturalOrder());
   sortNeighbours(dbls, Comparator.naturalOrder());
   sortNeighbours(strs, Comparator.naturalOrder());

You could define an additional method to handle Comparables so that you don't have to add naturalOrder() call everytime in your code.

edited Jan 16, 2019 at 16:55

answered Jan 15, 2019 at 19:17

Valentin Ruano

2,83920 silver badges31 bronze badges

2 Comments

Jaman Over a year ago

Hi @Valentin Ruano I get an error saying 'The method naturalOrder() is undefined for type Collections.'

Valentin Ruano Over a year ago

Ah sorry it is defined in Comparator not Collections, my bad. I updated the answer accordingly, thanks.

h.alex · Accepted Answer · 2019-01-15 23:10:22Z

0

The question is do you know the type of elements in your Vertex at the time you want to do the comparison.

I.e. this code is valid, due to type erasure:

Vertex<String> strVtx = ...
Vertex<Integer> intVtx = ...
List<Vertex> list = Arrays.asList(strVtx, intVtx);
list.sort(aComparer);

So the comparer implementation here would need to be iffy.

However, if you do know the type you can simply do:

List<Vertex<Integer>> list = ...
list.sort(Comparator.comparing(Vertex::getElement);

edited Jan 15, 2019 at 23:10

answered Jan 15, 2019 at 17:55

h.alex

9021 gold badge8 silver badges32 bronze badges

1 Comment

Valentin Ruano Over a year ago

Vertex<int> is not valid Java. Also, given than the question indicates the existence of Vertex.getElement to get the value to compare you could improve you answer by using that method appropriately.

Collectives™ on Stack Overflow

Sort a array list of generic objects Java

3 Answers 3

8 Comments

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

8 Comments

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related