Skip to content

Commit e3d8fce

Browse files
mperrymperry
committed
Added priority queue and related methods javadoc
1 parent e0839e1 commit e3d8fce

5 files changed

Lines changed: 107 additions & 43 deletions

File tree

‎core/src/main/java/fj/Monoid.java‎

Lines changed: 14 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -401,8 +401,14 @@ public static <A> Monoid<IO<A>> ioMonoid(final Monoid <A> ma) {
401401
return monoid(Semigroup.ioSemigroup(ma.semigroup()), IOFunctions.unit(ma.zero()));
402402
}
403403

404+
/**
405+
* A monoid for the maximum of two integers.
406+
*/
404407
public static final Monoid<Integer> intMaxMonoid = monoid(Semigroup.intMaximumSemigroup, Integer.MIN_VALUE);
405408

409+
/**
410+
* A monoid for the minimum of two integers.
411+
*/
406412
public static final Monoid<Integer> intMinMonoid = monoid(Semigroup.intMinimumSemigroup, Integer.MAX_VALUE);
407413

408414
/**
@@ -420,7 +426,14 @@ public static <A> Monoid<Set<A>> setMonoid(final Ord<A> o) {
420426
return monoid(Semigroup.setSemigroup(), Set.empty(o));
421427
}
422428

423-
public static <A> Monoid<A> ordMonoid(Ord<A> o, A zero) {
429+
430+
/**
431+
* A monoid for the maximum of elements with ordering o.
432+
*
433+
* @param o An ordering of elements.
434+
* @param zero The minimum element.
435+
*/
436+
public static <A> Monoid<A> ordMaxMonoid(final Ord<A> o, final A zero) {
424437
return monoid(o.max, zero);
425438
}
426439

‎core/src/main/java/fj/data/PriorityQueue.java‎

Lines changed: 64 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,8 @@
1111
import fj.data.fingertrees.FingerTree;
1212

1313
/**
14+
* A priority queue implementation backed by a {@link fj.data.fingertrees.FingerTree}. The finger tree nodes are annotated with type K, are combined using a monoid of K and both the key and value are stored in the leaf. Priorities of the same value are returned FIFO (first in, first out).
15+
*
1416
* Created by MarkPerry on 31 May 16.
1517
*/
1618
public class PriorityQueue<K, A> {
@@ -23,55 +25,94 @@ private PriorityQueue(Equal<K> e, FingerTree<K, P2<K, A>> ft) {
2325
ftree = ft;
2426
}
2527

28+
/**
29+
* Creates a priority queue from a finger tree.
30+
*/
2631
public static <K, A> PriorityQueue<K, A> priorityQueue(Equal<K> e, FingerTree<K, P2<K, A>> ft) {
2732
return new PriorityQueue<K, A>(e, ft);
2833
}
2934

35+
/**
36+
* Creates an empty priority queue.
37+
*
38+
* @param m A monoid to combine node annotations.
39+
* @param e A value to compare key equality.
40+
*/
3041
public static <K, A> PriorityQueue<K, A> empty(Monoid<K> m, Equal<K> e) {
3142
return priorityQueue(e, FingerTree.empty(m, (P2<K, A> p) -> p._1()));
3243
}
3344

45+
/**
46+
* An empty priority queue with integer priorities.
47+
*/
3448
public static <A> PriorityQueue<Integer, A> emptyInt() {
3549
return priorityQueue(Equal.intEqual, FingerTree.empty(Monoid.intMaxMonoid, (P2<Integer, A> p) -> p._1()));
3650
}
3751

52+
/**
53+
* Maps the values in each node with function f.
54+
*/
3855
public <B> PriorityQueue<K, B> map(F<A, B> f) {
3956
return priorityQueue(equal,
4057
ftree.map(p2 -> p2.map2(a -> f.f(a)),
4158
FingerTree.measured(ftree.measured().monoid(), (P2<K, B> p2) -> p2._1()))
4259
);
4360
}
4461

62+
/**
63+
* Filters nodes based on the value inside each node.
64+
*/
4565
public PriorityQueue<K, A> filterValues(F<A, Boolean> f) {
4666
return priorityQueue(equal, ftree.filter(p2 -> f.f(p2._2())));
4767
}
4868

69+
/**
70+
* Filters the nodes based on the annotation of each node.
71+
*/
4972
public PriorityQueue<K, A> filterKeys(F<K, Boolean> f) {
5073
return priorityQueue(equal, ftree.filter(p2 -> f.f(p2._1())));
5174
}
5275

76+
/**
77+
* Is the tree empty?
78+
*/
5379
public boolean isEmpty() {
5480
return ftree.isEmpty();
5581
}
5682

83+
/**
84+
* If the tree is not empty, returns the node with highest priority otherwise returns nothing.
85+
*/
5786
public Option<P2<K, A>> top() {
5887
K top = ftree.measure();
5988
P2<FingerTree<K, P2<K, A>>, FingerTree<K, P2<K, A>>> p = ftree.split(k -> equal.eq(top, k));
6089
return p._2().headOption();
6190
}
6291

92+
/**
93+
* Adds a node with priority k and value a. This operation take O(1).
94+
*/
6395
public PriorityQueue<K, A> enqueue(K k, A a) {
6496
return priorityQueue(equal, ftree.snoc(P.p(k, a)));
6597
}
6698

99+
/**
100+
* Adds nodes using the list of products with priority k and value a. This operation takes O(list.length()).
101+
*/
67102
public PriorityQueue<K, A> enqueue(List<P2<K, A>> list) {
68103
return list.foldLeft(pq -> p -> pq.enqueue(p._1(), p._2()), this);
69104
}
70105

71-
public boolean contains(final K k1) {
72-
return !ftree.split(k2 -> equal.eq(k1, k2))._2().isEmpty();
106+
/**
107+
* Does the priority k exist already?
108+
*/
109+
public boolean contains(final K k) {
110+
return !ftree.split(k2 -> equal.eq(k, k2))._2().isEmpty();
73111
}
74112

113+
/**
114+
* Adds nodes using the iterable of products with priority k and value a.
115+
*/
75116
public PriorityQueue<K, A> enqueue(Iterable<P2<K, A>> it) {
76117
PriorityQueue<K, A> result = this;
77118
for (P2<K, A> p: it) {
@@ -80,21 +121,33 @@ public PriorityQueue<K, A> enqueue(Iterable<P2<K, A>> it) {
80121
return result;
81122
}
82123

124+
/**
125+
* Adds a node with priority k and value a. This operation take O(1).
126+
*/
83127
public PriorityQueue<K, A> enqueue(P2<K, A> p) {
84128
return enqueue(p._1(), p._2());
85129
}
86130

131+
/**
132+
* Removes the node with the highest priority.
133+
*/
87134
public PriorityQueue<K, A> dequeue() {
88135
K top = ftree.measure();
89136
P2<FingerTree<K, P2<K, A>>, FingerTree<K, P2<K, A>>> p = ftree.split(k -> equal.eq(k, top));
90137
FingerTree<K, P2<K, A>> right = p._2();
91138
return right.isEmpty() ? this : priorityQueue(equal, p._1().append(right.tail()));
92139
}
93140

141+
/**
142+
* Returns a tuple of the node with the highest priority and the rest of the priority queue.
143+
*/
94144
public P2<Option<P2<K, A>>, PriorityQueue<K, A>> dequeueTop() {
95145
return P.p(top(), dequeue());
96146
}
97147

148+
/**
149+
* Removes the top n elements with the highest priority.
150+
*/
98151
public PriorityQueue<K, A> dequeue(int n) {
99152
int i = n;
100153
PriorityQueue<K, A> result = this;
@@ -105,14 +158,23 @@ public PriorityQueue<K, A> dequeue(int n) {
105158
return result;
106159
}
107160

161+
/**
162+
* Does the priority k have greater priority than the top of the queue?
163+
*/
108164
public boolean isGreaterThan(Ord<K> ok, K k) {
109165
return top().map(p -> ok.isGreaterThan(k, p._1())).orSome(true);
110166
}
111167

168+
/**
169+
* Returns a stream of products with priority k and value a.
170+
*/
112171
public Stream<P2<K, A>> toStream() {
113172
return top().map(p -> Stream.cons(p, () -> dequeue().toStream())).orSome(() -> Stream.nil());
114173
}
115174

175+
/**
176+
* Returns a list of products with priority k and value a.
177+
*/
116178
public List<P2<K, A>> toList() {
117179
return toStream().toList();
118180
}

‎core/src/main/java/fj/data/fingertrees/FingerTree.java‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -231,10 +231,22 @@ public static <A> FingerTree<Integer, A> emptyIntAddition() {
231231
return empty(intAdditionMonoid, Function.constant(1));
232232
}
233233

234+
/**
235+
* Creates an empty finger tree with elements of type A and node annotations
236+
* of type V.
237+
*
238+
* @param m A monoid to combine node annotations
239+
* @param f Function to convert node element to annotation.
240+
* @return An empty finger tree.
241+
*/
234242
public static <V, A> FingerTree<V, A> empty(Monoid<V> m, F<A, V> f) {
235243
return FingerTree.mkTree(measured(m, f)).empty();
236244
}
237245

246+
/**
247+
* Returns a finger tree which combines the integer node annotations with the
248+
* maximum function. A priority queue with integer priorities.
249+
*/
238250
public static <A> FingerTree<Integer, P2<Integer, A>> emptyIntMax() {
239251
return empty(intMaxMonoid, (P2<Integer, A> p) -> p._1());
240252
}

‎core/src/test/java/fj/data/PriorityQueueTest.java‎

Lines changed: 0 additions & 18 deletions
This file was deleted.

‎props-core/src/test/java/fj/data/properties/PriorityQueueProperties.java‎

Lines changed: 17 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,6 @@
77
import fj.data.Option;
88
import fj.data.PriorityQueue;
99
import fj.data.Set;
10-
import fj.test.Arbitrary;
1110
import fj.test.Gen;
1211
import fj.test.Property;
1312
import fj.test.reflect.CheckParams;
@@ -22,8 +21,6 @@
2221
import static fj.test.Property.impliesBoolean;
2322
import static fj.test.Property.prop;
2423
import static fj.test.Property.property;
25-
import static org.hamcrest.CoreMatchers.equalTo;
26-
import static org.junit.Assert.assertThat;
2724

2825
/**
2926
* Created by MarkPerry on 18 Jun 16.
@@ -34,6 +31,9 @@ public class PriorityQueueProperties {
3431

3532
public static Gen<PriorityQueue<Integer, String>> arbPriorityQueueIntegerString = arbUniqueQueue(arbAlphaNumString);
3633

34+
/**
35+
* Returns a queue with unique integer priorities.
36+
*/
3737
public static <A> Gen<PriorityQueue<Integer, A>> arbUniqueQueue(Gen<A> aa) {
3838
Gen<Set<Integer>> as = arbSet(Ord.intOrd, arbInteger);
3939
Gen<List<Integer>> ints = (as.map(si -> si.toList()));
@@ -48,49 +48,44 @@ Property empty() {
4848
return prop(pq.isEmpty());
4949
}
5050

51+
/**
52+
* Adding a priority that is at the top and then removing it returns the original top.
53+
*/
5154
Property addRemove() {
5255
return property(arbPriorityQueueIntegerString, arbInteger, arbAlphaNumString, (q, i, s) -> {
5356
Option<P2<Integer, String>> o = q.top();
5457
Option<P2<Integer, String>> o2 = q.enqueue(i, s).dequeue().top();
5558
return Property.impliesBoolean(
5659
q.isGreaterThan(Ord.intOrd, i),
57-
// o.map(p -> i > p._1()).orSome(true),
5860
() -> o.equals(o2)
5961
);
6062
});
6163
}
6264

65+
/**
66+
* An empty queue has no top.
67+
*/
6368
Property emptyTop() {
6469
return prop(emptyInt().top().isNone());
6570
}
6671

72+
/**
73+
* Adding a value with the highest priority makes it the top item.
74+
*/
6775
Property addTop() {
6876
return property(arbPriorityQueueIntegerString, arbInteger, arbAlphaNumString, (q, i, s) -> {
6977
Option<P2<Integer, String>> actual = q.enqueue(i, s).top();
7078
return impliesBoolean(
7179
q.isGreaterThan(Ord.intOrd, i),
72-
// q.top().map(p -> p._1() < i).orSome(true),
7380
actual.equals(some(P.p(i, s))));
7481
});
7582
}
7683

77-
Property sorted() {
78-
Gen<Set<Integer>> as = arbSet(Ord.intOrd, arbInteger);
79-
Gen<List<Integer>> ints = (as.map(si -> si.toList()));
80-
Gen<List<P2<Integer, String>>> alp = (
81-
ints.bind(li -> arbAlphaNumString.map(s -> li.map(i -> P.p(i, s))))
82-
);
83-
return property(alp, list -> {
84-
PriorityQueue<Integer, String> q = PriorityQueue.<String>emptyInt().enqueue(list);
85-
List<P2<Integer, String>> expected = list.sort(Ord.p2Ord1(Ord.intOrd.reverse()));
86-
List<P2<Integer, String>> actual = q.toStream().toList();
87-
assertThat(actual, equalTo(expected));
88-
System.out.println(actual);
89-
return prop(actual.equals(expected));
90-
});
91-
}
92-
93-
public Property sorted2() {
84+
/**
85+
* Sorting a list returns the same as putting the list into a priority queue and getting
86+
* the queue as a list.
87+
*/
88+
public Property sorted() {
9489
return property(arbPriorityQueueIntegerString, pq -> {
9590
List<P2<Integer, String>> expected = pq.toList().sort(Ord.p2Ord1(Ord.intOrd.reverse()));
9691
return prop(expected.equals(pq.toList()));

0 commit comments

Comments
 (0)