java - 编程 - Java - 取消合并算法与操作的关联

Question

目前我正在开发 T 类型元素的两个排序集合之间的合并(类型并不重要，只要您提供一种比较类型的方法，例如，在 Java 中，A Comparator<T> 将完成工作).

我不想要的是必须合并合并过程中涉及的两个数据结构(我不想获得一个包含两个合并元素的全新结构)。我想要的是拥有某种合并过程的观察者，以便定义如何处理另一个类中的每个合并元素。例如，A 想要这样的东西:

merger.merge(leftCollection,rightCollection,theComparator,theObserver).

如果观察者是一个观察合并算法并收到操作通知的对象，我的意思是:

interface MergeObserver<T> {

            /**
             * Triggered when the merge algorithm decides to merge only the left entry.
             * This case correspond to the case when there is no equivalent entry on the right collection.
             */
            public void mergeLeft(T entry);

            /**
             * Triggered when the merge algorithm decides to merge both entries.
             * This case correspond to the case when there exists the same entry on both collections.
             */
            public void mergeBoth(T left, T right);

            /**
             * Triggered when the merge algorithm decides to merge only the right entry.
             * This case correspond to the case when there is no equivalent entry on the left collection.
             */
            public void mergeRight(T entry);
        }

我已经实现了排序集合，但是......我想分享这种感觉，问题来了，关于是否有人以前想过这个，特别是在 Guava 库中，什么是正确的使用的术语。

Answer 1

用于分离数据结构的遍历和数据处理的两种最常用的模式是访问者模式和迭代器模式。这两种模式不仅可以应用于内存中存在的真实数据结构，还可以应用于“虚拟”数据结构(这可能不是正确的术语)。例如Java API 中的方法 List.subList 创建列表的一部分的 View 。所以它返回的列表对象只是对另一个列表数据的一部分的引用。当然你也可以组合数据结构。例如，您可以有一个方法将两个迭代器作为参数并返回一个新的迭代器，该迭代器将两个迭代器合并而不使用任何额外的内存，因为该合并列表实际上并不存在于 RAM 中。如果您使用 Scala 而不是 Java，您将有许多可用的方法可以以许多不同的方式转换迭代器来实现这样的效果。

import java.util.function.Predicate;
import java.util.function.BiPredicate;
import java.util.function.Supplier;
import java.util.function.Consumer;
import java.util.stream.IntStream;
import java.util.NoSuchElementException;

interface MyIterator<T> extends Iterator<T> {
  class Peekable<T> {
    private final MyIterator<T> iter;
    private T next = null;
    private boolean isNextBuffered = false;
    private boolean atEnd = false;

    private Peekable(MyIterator<T> iter) {
      this.iter = iter;
    }

    private void advance() {
      if(atEnd) throw new NoSuchElementException();
      if(iter.hasNext()) {
        next = iter.next();
        isNextBuffered = true;
      } else {
        atEnd = true;
      }
    }
    private boolean hasNext() {
      if(atEnd) return false;
      if(!isNextBuffered) advance();
      return !atEnd;
    }
    private T next() {
      T next = peek();
      advance();
      return next;
    }
    private T peek() {
      if(hasNext()) return next;
      throw new NoSuchElementException();
    }
  }

  static <T> MyIterator<T> of(BooleanSupplier hasNext, Supplier<T> next) {
    return new MyIterator<T>() {
      public boolean hasNext() {
        return hasNext.getAsBoolean();
      }
      public T next() {
        return next.get();
      }
    };
  }

  static <T> MyIterator<T> of(Iterator<T> iter) {
    return of(iter::hasNext, iter::next);
  }

  static MyIterator<Integer> range(int start, int end) {
    int[] value = {start};
    return of(() -> value[0] < end, () -> value[0]++);
  }

  default <R> MyIterator<R> map(Function<? super T,? extends R> mapper) {
    return of(this::hasNext, () -> mapper.apply(this.next()));
  }

  default MyIterator<T> filter(Predicate<? super T> predicate) {
    Peekable<T> iter = new Peekable<T>(this);

    return new MyIterator<T>() {
      public boolean hasNext() {
        while(iter.hasNext() && !predicate.test(iter.peek())) iter.advance();
        return iter.hasNext();
      }
      public T next() {
        hasNext();
        return iter.next();
      }
    };
  }

  default MyIterator<T> merge(MyIterator<T> other, BiPredicate<? super T,? super T> smallerEqual) {
    Peekable<T> iter1 = new Peekable<T>(this);
    Peekable<T> iter2 = new Peekable<T>(other);

    return of(() -> iter1.hasNext() || iter2.hasNext(),
              () -> {
                if(!iter1.hasNext()) return iter2.next();
                else if(!iter2.hasNext()) return iter1.next();
                else {
                  T elem1 = iter1.peek();
                  T elem2 = iter2.peek();
                  return smallerEqual.test(elem1, elem2) ? iter1.next() : iter2.next();
                }
              });
  }
}

interface MyIterable<T> extends Iterable<T> {
  default Iterator<T> iterator() {
    return myIterator();
  }

  MyIterator<T> myIterator();

  static <T> MyIterable<T> of(Supplier<MyIterator<T>> myIterator) {
    return new MyIterable<T>() {
      public MyIterator<T> myIterator() {
        return myIterator.get();
      }
    };
  }

  static <T> MyIterable<T> of(Iterable<T> iterable) {
    return of(() -> MyIterator.of(iterable.iterator()));
  }

  static MyIterable<Integer> range(int start, int end) {
    return of(() -> MyIterator.range(start, end));
  }

  default <R> MyIterable<R> map(Function<? super T,? extends R> mapper) {
    return of(() -> this.myIterator().map(mapper));
  }

  default MyIterable<T> filter(Predicate<? super T> predicate) {
    return of(() -> this.myIterator().filter(predicate));
  }

  default MyIterable<T> merge(MyIterable<T> other, BiPredicate<? super T,? super T> smallerEqual) {
    return of(() -> this.myIterator().merge(other.myIterator(), smallerEqual));
  }
}


public class Test {
  public static void main(String[] args) {
    MyIterable<Integer> iterable = MyIterable.range(0, 10);

    MyIterable<Integer> iter1 = iterable.map(x -> 2 * x).filter(x -> x < 10);
    MyIterable<Integer> iter2 = iterable.map(x -> 2 * x + 1).filter(x -> x < 10);
    MyIterable<Integer> iterMerged = iter1.merge(iter2, (x, y) -> x <= y);

    iter1.forEach(System.out::println);
    System.out.println();
    iter2.forEach(System.out::println);
    System.out.println();
    iterMerged.forEach(System.out::println);
  }
}