Enumerables { public static <TSource, TInner, TKey extends Comparable<TKey>, TResult> Enumerable<TResult> mergeJoin(final Enumerable<TSource> outer, final Enumerable<TInner> inner, final Function1<TSource, TKey> outerKeySelector, final Function1<TInner, TKey> innerKeySelector, final Function2<TSource, TInner, TResult> resultSelector, boolean generateNullsOnLeft, boolean generateNullsOnRight) { assert !generateNullsOnLeft : "not implemented"; assert !generateNullsOnRight : "not implemented"; return new AbstractEnumerable<TResult>() { public Enumerator<TResult> enumerator() { return new Enumerator<TResult>() { final Enumerator<TSource> leftEnumerator = outer.enumerator(); final Enumerator<TInner> rightEnumerator = inner.enumerator(); final List<TSource> lefts = Lists.newArrayList(); final List<TInner> rights = Lists.newArrayList(); boolean done; Enumerator<List<Object>> cartesians; { start(); } private void start() { if (!leftEnumerator.moveNext() || !rightEnumerator.moveNext() || !advance()) { done = true; cartesians = Linq4j.emptyEnumerator(); } } private boolean advance() { TSource left = leftEnumerator.current(); TKey leftKey = outerKeySelector.apply(left); TInner right = rightEnumerator.current(); TKey rightKey = innerKeySelector.apply(right); for (;;) { int c = leftKey.compareTo(rightKey); if (c == 0) { break; } if (c < 0) { if (!leftEnumerator.moveNext()) { done = true; return false; } left = leftEnumerator.current(); leftKey = outerKeySelector.apply(left); } else { if (!rightEnumerator.moveNext()) { done = true; return false; } right = rightEnumerator.current(); rightKey = innerKeySelector.apply(right); } } lefts.clear(); lefts.add(left); for (;;) { if (!leftEnumerator.moveNext()) { done = true; break; } left = leftEnumerator.current(); TKey leftKey2 = outerKeySelector.apply(left); int c = leftKey.compareTo(leftKey2); if (c != 0) { assert c < 0 : "not sorted"; break; } lefts.add(left); } rights.clear(); rights.add(right); for (;;) { if (!rightEnumerator.moveNext()) { done = true; break; } right = rightEnumerator.current(); TKey rightKey2 = innerKeySelector.apply(right); int c = rightKey.compareTo(rightKey2); if (c != 0) { assert c < 0 : "not sorted"; break; } rights.add(right); } cartesians = Linq4j.product( ImmutableList.of(Linq4j.<Object>enumerator(lefts), Linq4j.<Object>enumerator(rights))); return true; } public TResult current() { final List<Object> list = cartesians.current(); @SuppressWarnings("unchecked") final TSource left = (TSource) list.get(0); @SuppressWarnings("unchecked") final TInner right = (TInner) list.get(1); return resultSelector.apply(left, right); } public boolean moveNext() { for (;;) { if (cartesians.moveNext()) { return true; } if (done) { return false; } if (!advance()) { return false; } } } public void reset() { done = false; leftEnumerator.reset(); rightEnumerator.reset(); start(); } public void close() { } }; } }; } private  Enumerables(); static Enumerable<E> slice0(Enumerable<E[]> enumerable); static Enumerable<TSource> semiJoin(
      final Enumerable<TSource> outer, final Enumerable<TInner> inner,
      final Function1<TSource, TKey> outerKeySelector,
      final Function1<TInner, TKey> innerKeySelector); static Enumerable<TSource> semiJoin(
      final Enumerable<TSource> outer, final Enumerable<TInner> inner,
      final Function1<TSource, TKey> outerKeySelector,
      final Function1<TInner, TKey> innerKeySelector,
      final EqualityComparer<TKey> comparer); static Enumerable<TResult> thetaJoin(
      final Enumerable<TSource> outer, final Enumerable<TInner> inner,
      final Predicate2<TSource, TInner> predicate,
      Function2<TSource, TInner, TResult> resultSelector,
      final boolean generateNullsOnLeft,
      final boolean generateNullsOnRight); static Enumerable<TSource> where(
      final Enumerable<TSource> source, final Predicate1<TSource> predicate); static Enumerable<Row> toRow(final Enumerable<Object[]> enumerator); static Enumerable<TResult> mergeJoin(final Enumerable<TSource> outer,
      final Enumerable<TInner> inner,
      final Function1<TSource, TKey> outerKeySelector,
      final Function1<TInner, TKey> innerKeySelector,
      final Function2<TSource, TInner, TResult> resultSelector,
      boolean generateNullsOnLeft,
      boolean generateNullsOnRight);  }
@Test public void testMergeJoin() { assertThat( Enumerables.mergeJoin( Linq4j.asEnumerable( Arrays.asList( new Emp(10, "Fred"), new Emp(20, "Theodore"), new Emp(20, "Sebastian"), new Emp(30, "Joe"), new Emp(30, "Greg"))), Linq4j.asEnumerable( Arrays.asList( new Dept(15, "Marketing"), new Dept(20, "Sales"), new Dept(30, "Research"), new Dept(30, "Development"))), new Function1<Emp, Integer>() { public Integer apply(Emp a0) { return a0.deptno; } }, new Function1<Dept, Integer>() { public Integer apply(Dept a0) { return a0.deptno; } }, new Function2<Emp, Dept, String>() { public String apply(Emp v0, Dept v1) { return v0 + ", " + v1; } }, false, false).toList().toString(), equalTo("[Emp(20, Theodore), Dept(20, Sales)," + " Emp(20, Sebastian), Dept(20, Sales)," + " Emp(30, Joe), Dept(30, Research)," + " Emp(30, Joe), Dept(30, Development)," + " Emp(30, Greg), Dept(30, Research)," + " Emp(30, Greg), Dept(30, Development)]")); }