Skip to content

Commit 7417c43

Browse files
siro-mateosjbgi
siro-mateos
authored and
jbgi
committed
+ Added 'Set.lookup', and 'Set.lookupLT', 'Set.lookupGT','Set.lookupLE' and 'Set.lookupGE' from Haskell.
 + Added some test cases for new Set.lookup* functionality. * Changed 'get(K)' to use 'Set.lookup' instead of 'Set.split', so it can run much faster.
1 parent 6ac5f95 commit 7417c43

3 files changed

Lines changed: 140 additions & 2 deletions

File tree

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

Lines changed: 123 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -515,6 +515,129 @@ public final P3<Set<A>, Option<A>, Set<A>> split(final A a) {
515515
}
516516
}
517517

518+
/**
519+
* Find element equal to the given one.
520+
*
521+
* @param a An element to compare with.
522+
* @return Some element in this set equal to the given one, or None.
523+
*/
524+
public final Option<A> lookup(final A a) {
525+
Set<A> s = this;
526+
while (true)
527+
if (s.isEmpty())
528+
return none();
529+
else {
530+
final A h = s.head();
531+
final Ordering i = ord.compare(a, h);
532+
if (i == LT)
533+
s = s.l();
534+
else if (i == GT)
535+
s = s.r();
536+
else
537+
return some(h);
538+
}
539+
}
540+
541+
/**
542+
* Find largest element smaller than the given one.
543+
*
544+
* @param a An element to compare with.
545+
* @return Some largest element in this set smaller than the given one, or None.
546+
*/
547+
public final Option<A> lookupLT(final A a) {
548+
Set<A> s = this;
549+
Option<A> r = none();
550+
while (true)
551+
if (s.isEmpty())
552+
return r;
553+
else {
554+
final A h = s.head();
555+
final Ordering i = ord.compare(a, h);
556+
if (i == GT) {
557+
r = some(h);
558+
s = s.r();
559+
}
560+
else
561+
s = s.l();
562+
}
563+
}
564+
565+
/**
566+
* Find smallest element greater than the given one.
567+
*
568+
* @param a An element to compare with.
569+
* @return Some smallest element in this set greater than the given one, or None.
570+
*/
571+
public final Option<A> lookupGT(final A a) {
572+
Set<A> s = this;
573+
Option<A> r = none();
574+
while (true)
575+
if (s.isEmpty())
576+
return r;
577+
else {
578+
final A h = s.head();
579+
final Ordering i = ord.compare(a, h);
580+
if (i == LT) {
581+
r = some(h);
582+
s = s.l();
583+
}
584+
else
585+
s = s.r();
586+
}
587+
}
588+
589+
/**
590+
* Find largest element smaller or equal to the given one.
591+
*
592+
* @param a An element to compare with.
593+
* @return Some largest element in this set smaller or equal to the given one, or None.
594+
*/
595+
public final Option<A> lookupLE(final A a) {
596+
Set<A> s = this;
597+
Option<A> r = none();
598+
while (true)
599+
if (s.isEmpty())
600+
return r;
601+
else {
602+
final A h = s.head();
603+
final Ordering i = ord.compare(a, h);
604+
if (i == LT)
605+
s = s.l();
606+
else if (i == GT) {
607+
r = some(h);
608+
s = s.r();
609+
}
610+
else
611+
return some(h);
612+
}
613+
}
614+
615+
/**
616+
* Find smallest element greater or equal to the given one.
617+
*
618+
* @param a An element to compare with.
619+
* @return Some smallest element in this set greater or equal to the given one, or None.
620+
*/
621+
public final Option<A> lookupGE(final A a) {
622+
Set<A> s = this;
623+
Option<A> r = none();
624+
while (true)
625+
if (s.isEmpty())
626+
return r;
627+
else {
628+
final A h = s.head();
629+
final Ordering i = ord.compare(a, h);
630+
if (i == LT) {
631+
r = some(h);
632+
s = s.l();
633+
}
634+
else if (i == GT)
635+
s = s.r();
636+
else
637+
return some(h);
638+
}
639+
}
640+
518641
/**
519642
* Returns true if this set is a subset of the given set.
520643
*

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

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -129,8 +129,7 @@ public static <K, V> TreeMap<K, V> arrayTreeMap(final Ord<K> keyOrd, final P2<K,
129129
* @return A potential value for the given key.
130130
*/
131131
public Option<V> get(final K k) {
132-
final Option<P2<K, Option<V>>> x = tree.split(p(k, Option.none()))._2();
133-
return x.bind(P2.__2());
132+
return tree.lookup(p(k, Option.none())).bind(P2::_2);
134133
}
135134

136135
/**

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

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,8 @@
22

33
import org.junit.Test;
44

5+
import static fj.data.Option.none;
6+
import static fj.data.Option.some;
57
import static fj.Ord.intOrd;
68
import static org.hamcrest.CoreMatchers.equalTo;
79
import static org.junit.Assert.assertThat;
@@ -23,4 +25,18 @@ public void testString() {
2325
assertThat(s.toString(), equalTo("Set(1,2,3)"));
2426
}
2527

28+
@Test
29+
public void testLookups() {
30+
Set<Integer> s = Set.set(intOrd, 5, 1, 7, 8);
31+
assertThat(s.lookup(7), equalTo(some(7)));
32+
assertThat(s.lookup(4), equalTo(none()));
33+
assertThat(s.lookupLT(6), equalTo(some(5)));
34+
assertThat(s.lookupLT(1), equalTo(none()));
35+
assertThat(s.lookupGT(5), equalTo(some(7)));
36+
assertThat(s.lookupGT(9), equalTo(none()));
37+
assertThat(s.lookupLE(8), equalTo(some(8)));
38+
assertThat(s.lookupLE(0), equalTo(none()));
39+
assertThat(s.lookupGE(8), equalTo(some(8)));
40+
assertThat(s.lookupGE(9), equalTo(none()));
41+
}
2642
}

0 commit comments

Comments
 (0)