Vavr: Add a Priority Queue implementation to Javaslang

[paplorinc]

Given some basic guidelines I would gladly add a PriorityQueue implementation to Javaslang.
I could base my implementation on http://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdf.

[danieldietrich]

Hi Pap, this is a great idea. I'm returning home from vacation and have currently only my mobile phone at hand. My thoughts:

• we need to decide how the PriorityQueue fits into the type hierarchy of the Javaslang collections. Maybe we need to change the existing types (interfaces vs classes). Currently we have a class Queue which is a LinearSeq -> Seq -> Traversable. It would be nice to have a Queue interface but I think the PriorityQueue interface differs regarding the enqueue operation regarding the rank. I think that a PriorityQueue is no Seq. It is also not a Map. Is it a Set? What if we insert the same element with different priorities? (see this discussion: http://www.scala-lang.org/old/node/10374.html). Maybe it needs to be a new collection type that extends Traversable, like Tree and Iterator. I have to read more about it tomorrow...
• the Okasaki paper you referred to is of 1996. More recent sources refer to FingerTree impls (https://hackage.haskell.org/package/fingertree-0.1.1.0/docs/Data-PriorityQueue-FingerTree.html, http://stackoverflow.com/questions/18127422/is-there-a-maintained-immutable-priority-queue-in-scala). We need to check the pros/cons compared to binary tree/heap impls

Tomorrow I'm able to provide you with some more detailed information.

This will be fun :)

[danieldietrich]

@paplorinc We add the PriorityQueue as interface to the existing type hierarchy:

A (FIFO) _Queue_ is a special _Priority Queue_ ("... the priority of each inserted element is monotonically decreasing", see wikipedia). Please note that a _Stack_ is also a special _Priority Queue_ but in Javaslang the _Stack_ is not a collection but a marker interface with a bunch of Stack operations, so Stack will not implement Priority Queue.

Before talking about implementation details there is still a question (and I already have a suggested answer):

Which API do we choose to assign an element a priority?

1. Provide an explicit priority as argument when pushing an element to the Priority Queue
2. Define an underlying ordering (= Comparator) when constructing a Priority Queue (much like in TreeSet)

The first approach (using an explicit priority) is not intuitive because we may easily add one element with different priorities. The priority on the one hand is bound to an element but on the other hand it is not derived from that element. If the priority is independent of the element attributes, it can be seen as arbitrary/random from our viewpoint.

The second approach (using an ordering) goes well along with Java's standard collection. It implemented a mutable Priority Queue using an underlying Comparator. A Comparator provides us with more options, we are able to create a Priority Queue using a rank/priority function priority: T -> int that induces a Comparator compare: T x T -> int:

compare(elem1, elem2) := priority(elem2) - priority(elem1)

Choosing the right implementation

Using Heaps is just one variant to implement Priority Queues. Let's take the approach you suggested. I think it is nice because it is relatively easy. The performance characteristics are ok and we are able to exchange the implementation later because Priority Queue will be an interface and we do not expose the implementation details to the outside.

First implementation steps

The interface looks like this:

public interface PriorityQueue<T> extends LinearSeq<T> {

    Tuple2<T, ? extends PriorityQueue<T>> dequeue();
    Option<Tuple2<T, ? extends PriorityQueue<T>>> dequeueOption();
    PriorityQueue<T> enqueue(T element);
    PriorityQueue<T> enqueue(T... elements);
    PriorityQueue<T> enqueueAll(Iterable<? extends T> elements);
    T peek();
    Option<T> peekOption();

    // -- Adjusted return types of LinearSeq methods

    ...

}

Note: The _adjusted return types_ mentioned above mean that methods inherited from LinearSeq that return LinearSeq need (in 99,99% of all cases) to be overridden with PriorityQueue as return type.

Accordingly we need to change class Queue:

// before
public class Queue<T> implements Kind1<Queue<?>, T>, LinearSeq<T>, Serializable {
    ...
}

// after
public class Queue<T> implements Kind1<Queue<?>, T>, PriorityQueue<T>, Serializable {
    ...
}

Still unsatisfied undecided with the type hierarchy...

Above we see two disadvantages of letting Queue inherit PriorityQueue:

1. Some of the method return types of PriorityQueue contain ? extends PriorityQueue<T> because of Java's lack of (declaration site) variance. This is somewhat distracting API.
2. PriorityQueue<T> cannot extend Kind1<PriorityQueue<?>, T> because it would be a conflict to Queue<T> implements Kind1<Queue<?>, T>. This is a minor issue because Kind* is only relevant for the javaslang-pure module.

The second point can be ignored for now. The first point might be fixed by leaving PriorityQueue as standalone type that is not implemented by Queue.

@all Any opinions on that? I've experimented with Set and Map return types and think that it is ok to work with ? extends ... return types (no casts were needed).

[danieldietrich]

I slept one night over the type-hierarchy topic. In the comment above I suggested the following:

Queue -> PriorityQueue -> LinearSeq -> Seq -> ...

where Queue is a class and PriorityQueue is an interface.

But Java has

PriorityQueue -> Queue -> ...

where Queue is an interface and PriorityQueue is a class.

---

At a first sight we might think that PriorityQueue -> Queue goes adhere with SortedSet -> Set. But that is not true because Set has no ordering opposed to SortedSet, so SortedSet is special in this manner.

Queue has a special ordering, so Queue -> PriorityQueue is the right way to do it. This goes well along with the fact that we do not have to change the current collection hierarchy existing collections.

Just wanted to clarify it a bit.

[paplorinc]

Awesome, will start working on it shortly :)

[danieldietrich]

Great! I'm really looking forward to it :-) You can add your PR at an early stage and push your commits from time-to-time. I will guide you if there are any questions.

I've thought a little bit harder about the type hierarchy. The idea I sketched above is not the best solution. E.g. when having a method comparator() (similar to SortedSet.comparator()) our current Queue cannot implement it in a way that makes sense. There are also other examples where it makes no sense that Queue implements specific methods of PriorityQueue (like special map and flatMap methods that take a Comparator for the result type). So Queue cannot inherit PriorityQueue.

Just don't think too much about it, we start implementing the PriorityQueue as you suggested. It will directly inherit from LinearSeq for now.

---

Maybe we introduce later a common interface for Queue and PriorityQueue. The best name for that interface would be Queue. Our current class Queue needs then a different name but that is not possible because of backward compatibility. So we will introduce a 'hidden' (read: package private) interface (e.g. QueueLike) that may be renamed when releasing the next major Javaslang version (3.0). But that is not important for now. We concentrate on implementing the PriorityQueue.

[paplorinc]

@danieldietrich, could you please assign this to me?

I have translated most of the basic structure from the paper and the similarly cryptic Scalaz source -- I feel like a hacker who reverse engineered something that was not meant to be understood :p.

I will need to make it more Java-like, add some basic tests and will push a draft this week.

Once that's working, I will add the rest of the inherited methods. :)

[danieldietrich]

@paplorinc That sounds great - looking forward to the review. I will assign you...

Update: Before I can assign you, you need to follow the invitation to the Javaslang team :)