#Comparator lambda function usage with priority queue

100 messages · Page 1 of 1 (latest)

runic harbor
#

Can someone explain me this snippet of code?

    {

        // Comparator lambda function that enables the priority queue to store the nodes
        // based on the cost in the ascending order.
        Comparator<NodeCost> NodeCostComparator = (obj1, obj2) -> Integer.compare(obj1.cost, obj2.cost);

        // Priority queue stores the object node-cost into the queue with 
        // the smallest cost node at the top.
        PriorityQueue<NodeCost> pq = new PriorityQueue<>(NodeCostComparator);

        // The cost of the source node to itself is 0
        pq.add(new NodeCost(source_node, 0));
shadow nebulaBOT
#

⌛ This post has been reserved for your question.

Hey @runic harbor! Please use /close or the Close Post button above when you're finished. Please remember to follow the help guidelines. This post will be automatically closed after 300 minutes of inactivity.

TIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here.

runic harbor
#

I understand that a integer and a list of lists is passed to the method. Then a variable of NodeCost type is declared, what does the Comparator mean at the front, i know its used in .sort

main basin
#

Comparator<NodeCost> NodeCostComparator - this means, that you declare a variable NodeCostComparator of type Comparator<NodeCost>

#

and you itinitialize that variable with lambda (obj1, obj2) -> Integer.compare(obj1.cost, obj2.cost)

#

that will be executed as method compare(NodeCost obj1, NodeCost obj2) will be is called

#

then you create priority queue with that comparator and add and object of NodeCost

runic harbor
#

what kind of variable is Comparator<>

#

i thought its an interface

main basin
#

you can have variables of interfaces

runic harbor
#

what i mean is, for example List is a list of elements, what does Comparator represent

main basin
#

it represents an object, that implements Comparator interface

runic harbor
#

list is also an object that implements List

main basin
#

yes

runic harbor
#

in terms of creating a variable

main basin
# runic harbor if a list is a list of elements, or an ArrayList is a list of Arrays, in similar...

ArrayList is a list of Arrays
Its not a lit of arrays. It's also list, that stores their values in array, so it gives some advantages in instant access to i-th element if the list.
in similar vein what is Comparator
it's object that is used to compare elements of a data structure (in your case - PriorityQueue), so have elements sorted in a way, that data structure has to implement. So comparator is used to compare elements.

main basin
runic harbor
#

its not my code, i am having trouble understanding it

#

i would have sent the whole code but its too long for discord

main basin
#

look, imagine you need to sort elements, and you sort integers. That's easy, right. But what if you need to sort objects of Employee class? Who should go first? Sort them by name? or age? or salary?
Usually, develovers implement Comparable interface in their class, where they implement the only method, that will be used to compare with another objects. But what if you need to sort objects using another field? or by few fields? or developers didn't implement Comparable interface in their classes? that's why Comparator was created - to provide an object that will be comparing elements. You implement the only method int compare(T ob1, T ob2);. And during sorting, fo figure out, which element should go first in queue, that method of Comparator will be called

#

to create Comparator object, you could do this:java Comparator<Node> comparator = new Comparator<>(){ public int compare(Node obj1, Node obj2) { return Integer.compare(obj1.cost, obj2.cost); }; }But in your snippet of code was used lambda expression (obj1, obj2) -> Integer.compare(obj1.cost, obj2.cost); that is the same

#

if you don't understand why they are the same - read about lambda expressions

runic harbor
#

lambda expressions are just syntactic sugar afaik

main basin
#

iirc, they have a little different implementation comparing to anonymous classes, so not really syntax sugar. But in this case it doesn't matter

runic harbor
#

also when the variable is initialized, obj1 and obj2 are empty right?

main basin
#

they are nothing. They are like parameters of method public int compare(Node obj1, Node obj2)

runic harbor
#

so the first time NodeCostComparator gets any value is when pq.add is done?

main basin
#

it will be called as sorting algorithm will need to compare elements

#

like, comparator.compare(element[i], element[i-1])

#

so element[i] will be passed as obj1, and element[i-1] will be passed as obj2 arguments

runic harbor
#

so the whole NodeCostComparator acts as a parameter that will eventually hold some value when it is passed, rather than a typical variable that holds some value?

#

its like a method but in a variable?

main basin
#

Comparator doesn't hold any values. It provides logic of comparing 2 objects. It provides a method that implementations it

# 
Comparator<Node> comparator = new Comparator<>(){
  public int compare(Node obj1, Node obj2) { 
    return Integer.compare(obj1.cost, obj2.cost);
  };
}```
is same as 
```java
Comparator<Node> comparator = (obj1, obj2) -> Integer.compare(obj1.cost, obj2.cost);
runic harbor
#

yes

#

comparator was clearer to understand when used in the objectname.sort(()) manner

#

well now that you have explained it, i understand it a bit more

#

also, what does it mean when there are different datatypes in the lhs and rhs of the assignment operator

#

List<List<NodeCost>> graph_1 = new ArrayList<>(num_nodes);

main basin
#

what are lhs and rhs of the assignment operator?

runic harbor
#

left hand side right hs, = being the assignment operator

main basin
#

List is interface. And you declare that it is list of lists, that hold NodeCost

#

and implementation of that interface is ArraysList

#

and pass num_nodes as argument into constructor of ArrayList

#

diamond operator <> means that compiler will manage on it's own the type of ArrayList

#

it's short form of the same as in List

#

so it's same as List<List<NodeCost>> graph_1 = new ArrayList<List<NodeCost>>(num_nodes);

runic harbor
main basin
#

polymorphism allows to assign objects of classes to variables of same class or parents

runic harbor
#

because both are part of Collections?

main basin
#

since ArrayList implements List interface, it works

#

All Implemented Interfaces:
Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, RandomAccess

#

that's why you can assign object of ArrayList to a variable of List type

runic harbor
main basin
#

it depends on the rest of code. if you use some specific for ArrayList methods, and someday you will decide to change ArrayList to something else, (LinkedList for example), you will have to edit the code where specific methods are used. That's why it's recommended to use interfaces, because it allows to change the implmentation objects without any problems

#

but for your case it seems to be no difference

#

example

runic harbor
#

so i understand that its for flexibility right?

#

ArrayList<List<NodeCost>> graph_1 = new List<List<nodeCost>>(num_nodes); this wouldn't be allowed right?

main basin
#

imagine you use a lib to do sql request to database and receive list of objects (that is work for ORM , like Hibernate). Suppose, it has a method
ArrayList<Object> getAll() { ... }
So everywhere in your code you could use ArrayList as return type of that method. But next update they change ArrayList ot LinkedList, and whole client code stops to work, and you have to change tons of your code.
But when you use interfaces, that doesn't matter anymore. The lib can return the implementation of List as they want. We don't care, our code will be working

main basin
main basin
#

basically, it will be anonymous class that implements the interface

runic harbor
runic harbor
main basin
#

yeah

runic harbor
#

i thought ArrayList was part of list, which is not the case

main basin
#

ArrayList is a class that implements List interface

runic harbor
#

so if List<List<NodeCost>> graph_1 = new ArrayList<List<NodeCost>>(num_nodes); this is ok then will this also work? ArrayList<List<NodeCost>> graph_1 = new List<List<NodeCost>>(num_nodes);

main basin
#

It doesn't work like that.

#

you can't create object of interface without providing an implementation of abstract methods. But even if you provide that implementations, that won't be the ArrayList class. Because ArrayList has it's own fields and methods, that anonymous implementation of List doesn't

#

tesla is a car, but car isn't tesla (it can be ford etc)

runic harbor
#

List<List<NodeCost>> graph_1 = new ArrayList<List<NodeCost>>(num_nodes); this worked because ArrayList already implements List?

main basin
#

yes

#

imagine you have interface Car java interface car { void beep(); }

#

and have implementation (actual car) Ford:```java
class Ford implements Car {
@Override
public void beep() {
sout("BEEEEEEEE!");
}

void playMusic() {
...
}
}

#

so you can do now :```java
Car car = new Ford();

#

because Ford implements car

#

that guarantees that it has beep method

#

but you can't do this:```java
Ford ford = new Car();

#

because Ford may have another methods, fields, and Car interface have no idea about them

runic harbor
#

yes that makes sense

main basin
#

I've just added playMusic() method into Ford class

#

Car interface has no idea about that

main basin
#

I recommend you to read a book about java. it gives you information in structured form, it explains all of this. Because right now you take pieces of information and can't understand a lot of things, and then spending much more time to figure out it.

#

usually people want to learn something fast, so don't read books, but then have to spend more time to understand.

runic harbor
#

can you recommend a good book that explains all of this?

main basin
runic harbor
#

do you know if this book explains comparator and similar interfaces in util package?

main basin
#

yes

runic harbor
#

because i did try to read a book before and learn about classes, interfaces, etc but I was only supposed to do very basic stuff like Fibonacci, etc so never used a lot of package interfaces and never really learned about it

runic harbor
#

Thanks a lot for giving me so much time, really appreciate it. very helpful.

shadow nebulaBOT
main basin