Skip to content

Commit e65b0bc

Browse files
jnapejnape
committed
Intersection (lazy iterable intersection), and tightening up javadocs
1 parent 9e16ed9 commit e65b0bc

6 files changed

Lines changed: 113 additions & 21 deletions

File tree

‎CHANGELOG.md‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -10,10 +10,11 @@ The format is based on [Keep a Changelog](http://keepachangelog.com/).
1010
- `CmpEqBy`, `CmpEq`, `GTBy`, `GT`, `LTBy`, `LT`, `GTEBy`, `GTE`, `LTEBy`, and `LTE` inequality checks
1111
- `MinBy`, `MaxBy`, `Min`, and `Max` semigroups
1212
- `Product2-8` interfaces, representing general product types
13-
- `Union`, a semigroup that behaves like a lazy set union on `Iterable`s
13+
- `Union`, a monoid that behaves like a lazy set union on `Iterable`s
1414
- `Difference`, a semigroup that behaves like a partially lazy set difference on `Iterable`s
1515
- `LambdaMap`, extension point for `j.u.Map`, similar to `LambdaIterable`
1616
- `Sequence#sequence` overloads for `j.u.Map` that traverse via intermediate `LambdaMap` instances
17+
- `Intersection`, a semigroup that behaves like a lazy set intersection on `Iterable`s
1718

1819
### Changed
1920
- `Tuple2-8` now implement `Product2-8`

‎src/main/java/com/jnape/palatable/lambda/monoid/builtin/Union.java‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,17 +1,17 @@
11
package com.jnape.palatable.lambda.monoid.builtin;
22

33
import com.jnape.palatable.lambda.functions.Fn1;
4+
import com.jnape.palatable.lambda.functions.builtin.fn1.Distinct;
45
import com.jnape.palatable.lambda.iteration.UnioningIterable;
56
import com.jnape.palatable.lambda.monoid.Monoid;
67

78
import java.util.Collections;
89

910
/**
10-
* Given two {@link Iterable}s, return the union of all unique occurrences of elements between them. Note that this
11-
* operation preserves order, so the unique elements of the first {@link Iterable} are iterated before the unique
12-
* elements of the second {@link Iterable}.
11+
* Given two {@link Iterable Iterables} <code>xs</code> and <code>ys</code>, return the {@link Concat concatenation} of
12+
* the {@link Distinct distinct} elements of both <code>xs</code> and <code>ys</code>.
1313
*
14-
* @param <A> the {@link Iterable} element type)
14+
* @param <A> the {@link Iterable} element type
1515
*/
1616
public final class Union<A> implements Monoid<Iterable<A>> {
1717

src/main/java/com/jnape/palatable/lambda/monoid/Difference.java renamed to src/main/java/com/jnape/palatable/lambda/semigroup/builtin/Difference.java

Lines changed: 15 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,27 +1,33 @@
1-
package com.jnape.palatable.lambda.monoid;
1+
package com.jnape.palatable.lambda.semigroup.builtin;
22

33
import com.jnape.palatable.lambda.functions.Fn1;
4+
import com.jnape.palatable.lambda.functions.builtin.fn1.Distinct;
5+
import com.jnape.palatable.lambda.semigroup.Semigroup;
46

5-
import java.util.Collections;
67
import java.util.HashSet;
78

89
import static com.jnape.palatable.lambda.functions.builtin.fn1.Distinct.distinct;
910
import static com.jnape.palatable.lambda.functions.builtin.fn1.Empty.empty;
1011
import static com.jnape.palatable.lambda.functions.builtin.fn2.Filter.filter;
1112
import static com.jnape.palatable.lambda.functions.builtin.fn2.ToCollection.toCollection;
1213

13-
public final class Difference<A> implements Monoid<Iterable<A>> {
14+
/**
15+
* Given two {@link Iterable Iterables} <code>xs</code> and <code>ys</code>, return the {@link Distinct distinct}
16+
* elements of <code>xs</code> that are not in <code>ys</code>. Note that this is <strong>not</strong> symmetric
17+
* difference.
18+
* <p>
19+
* This operation preserves order, so the resulting elements from <code>xs</code> are iterated in the order that
20+
* they uniquely occur in.
21+
*
22+
* @param <A> the {@link Iterable} element type
23+
*/
24+
public final class Difference<A> implements Semigroup<Iterable<A>> {
1425

1526
private static final Difference INSTANCE = new Difference();
1627

1728
private Difference() {
1829
}
1930

20-
@Override
21-
public Iterable<A> identity() {
22-
return Collections::emptyIterator;
23-
}
24-
2531
@Override
2632
public Iterable<A> apply(Iterable<A> xs, Iterable<A> ys) {
2733
return () -> {
@@ -31,7 +37,7 @@ public Iterable<A> apply(Iterable<A> xs, Iterable<A> ys) {
3137
if (empty(ys))
3238
return distinct(xs).iterator();
3339

34-
//todo: pre-order dfs fold the expression tree to make stack-safe
40+
//todo: a pre-order depth-first fold of the expression tree would make this stack-safe
3541
HashSet<A> uniqueYs = toCollection(HashSet::new, ys);
3642
return distinct(filter(a -> !uniqueYs.contains(a), xs)).iterator();
3743
};

‎src/main/java/com/jnape/palatable/lambda/semigroup/builtin/Intersection.java‎

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package com.jnape.palatable.lambda.semigroup.builtin;
2+
3+
import com.jnape.palatable.lambda.functions.Fn1;
4+
import com.jnape.palatable.lambda.functions.builtin.fn1.Distinct;
5+
import com.jnape.palatable.lambda.semigroup.Semigroup;
6+
7+
import java.util.HashSet;
8+
import java.util.Set;
9+
10+
import static com.jnape.palatable.lambda.functions.builtin.fn1.Constantly.constantly;
11+
import static com.jnape.palatable.lambda.functions.builtin.fn1.Distinct.distinct;
12+
import static com.jnape.palatable.lambda.functions.builtin.fn2.Eq.eq;
13+
import static com.jnape.palatable.lambda.functions.builtin.fn2.Filter.filter;
14+
import static com.jnape.palatable.lambda.functions.builtin.fn2.Find.find;
15+
16+
/**
17+
* Given two {@link Iterable Iterables} <code>xs</code> and <code>ys</code>, return the {@link Distinct distinct}
18+
* elements of <code>xs</code> that are also in <code>ys</code> in order of their unique occurrence in <code>xs</code>.
19+
*
20+
* @param <A> the {@link Iterable} element type
21+
*/
22+
public final class Intersection<A> implements Semigroup<Iterable<A>> {
23+
24+
private static final Intersection INSTANCE = new Intersection();
25+
26+
private Intersection() {
27+
}
28+
29+
@Override
30+
public Iterable<A> apply(Iterable<A> xs, Iterable<A> ys) {
31+
Set<A> seen = new HashSet<>();
32+
return distinct(filter(a -> seen.contains(a) || find(eq(a), ys).peek(seen::add).fmap(constantly(true)).orElse(false), xs));
33+
}
34+
35+
@SuppressWarnings("unchecked")
36+
public static <A> Intersection<A> intersection() {
37+
return INSTANCE;
38+
}
39+
40+
public static <A> Fn1<Iterable<A>, Iterable<A>> intersection(Iterable<A> xs) {
41+
return Intersection.<A>intersection().apply(xs);
42+
}
43+
44+
public static <A> Iterable<A> intersection(Iterable<A> xs, Iterable<A> ys) {
45+
return intersection(xs).apply(ys);
46+
}
47+
}

src/test/java/com/jnape/palatable/lambda/monoid/DifferenceTest.java renamed to src/test/java/com/jnape/palatable/lambda/semigroup/builtin/DifferenceTest.java

Lines changed: 2 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.jnape.palatable.lambda.monoid;
1+
package com.jnape.palatable.lambda.semigroup.builtin;
22

33
import com.jnape.palatable.lambda.functions.Fn1;
44
import com.jnape.palatable.traitor.annotations.TestTraits;
@@ -11,7 +11,7 @@
1111
import testsupport.traits.InfiniteIterableSupport;
1212
import testsupport.traits.Laziness;
1313

14-
import static com.jnape.palatable.lambda.monoid.Difference.difference;
14+
import static com.jnape.palatable.lambda.semigroup.builtin.Difference.difference;
1515
import static java.util.Arrays.asList;
1616
import static java.util.Collections.emptyList;
1717
import static java.util.Collections.singletonList;
@@ -27,11 +27,6 @@ public Fn1<Iterable<Integer>, Iterable<Integer>> testSubject() {
2727
return Difference.<Integer>difference().flip().apply(asList(1, 2, 3));
2828
}
2929

30-
@Test
31-
public void identity() {
32-
assertThat(difference().identity(), isEmpty());
33-
}
34-
3530
@Test
3631
public void semigroup() {
3732
assertThat(difference(emptyList(), emptyList()), isEmpty());

‎src/test/java/com/jnape/palatable/lambda/semigroup/builtin/IntersectionTest.java‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package com.jnape.palatable.lambda.semigroup.builtin;
2+
3+
import com.jnape.palatable.lambda.functions.Fn1;
4+
import com.jnape.palatable.traitor.annotations.TestTraits;
5+
import com.jnape.palatable.traitor.runners.Traits;
6+
import org.junit.Test;
7+
import org.junit.runner.RunWith;
8+
import testsupport.traits.EmptyIterableSupport;
9+
import testsupport.traits.FiniteIteration;
10+
import testsupport.traits.InfiniteIterableSupport;
11+
import testsupport.traits.Laziness;
12+
13+
import static com.jnape.palatable.lambda.semigroup.builtin.Intersection.intersection;
14+
import static java.util.Arrays.asList;
15+
import static java.util.Collections.emptyList;
16+
import static java.util.Collections.singletonList;
17+
import static org.junit.Assert.assertThat;
18+
import static testsupport.matchers.IterableMatcher.isEmpty;
19+
import static testsupport.matchers.IterableMatcher.iterates;
20+
21+
@RunWith(Traits.class)
22+
public class IntersectionTest {
23+
24+
@TestTraits({Laziness.class, InfiniteIterableSupport.class, EmptyIterableSupport.class, FiniteIteration.class})
25+
public Fn1<Iterable<Integer>, Iterable<Integer>> testSubject() {
26+
return intersection(asList(0, 1, 2, 3));
27+
}
28+
29+
@Test
30+
public void intersectionOfEmptyOnEitherSideIsEmpty() {
31+
assertThat(intersection(emptyList(), singletonList(1)), isEmpty());
32+
assertThat(intersection(singletonList(1), emptyList()), isEmpty());
33+
assertThat(intersection(emptyList(), emptyList()), isEmpty());
34+
}
35+
36+
@Test
37+
public void intersectionIsCommonElementsAcrossIterables() {
38+
assertThat(intersection(asList(1, 2, 3), asList(1, 2, 3)), iterates(1, 2, 3));
39+
assertThat(intersection(asList(1, 2, 3), asList(2, 3, 4)), iterates(2, 3));
40+
assertThat(intersection(singletonList(1), singletonList(2)), isEmpty());
41+
assertThat(intersection(asList(1, 2, 3, 3), singletonList(3)), iterates(3));
42+
}
43+
}

0 commit comments

Comments
 (0)