SimpleIdMatchingAlgorithm.java

/*
 * #%L
 * wcm.io
 * %%
 * Copyright (C) 2018 wcm.io
 * %%
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 * #L%
 */
package io.wcm.caravan.hal.comparison.impl.matching;

import java.util.ArrayList;
import java.util.List;
import java.util.function.Function;
import java.util.stream.Collectors;

import com.google.common.collect.LinkedListMultimap;
import com.google.common.collect.Multimap;

/**
 * An algorithm that finds matching items by comparing an id.
 */
public class SimpleIdMatchingAlgorithm<T> implements MatchingAlgorithm<T> {

  private final Function<T, String> idProvider;

  /**
   * @param idProvider the function to generate/extract an id for a given item
   */
  public SimpleIdMatchingAlgorithm(Function<T, String> idProvider) {
    this.idProvider = idProvider;
  }

  @Override
  public MatchingResult<T> findMatchingItems(List<T> expectedList, List<T> actualList) {

    MatchingResultImpl<T> result = new MatchingResultImpl<T>();

    IndexedItemList<T> remainingExpected = new IndexedItemList<T>(expectedList, idProvider);
    IndexedItemList<T> remainingActual = new IndexedItemList<T>(actualList, idProvider);

    while (remainingExpected.hasMoreItems()) {
      ItemWithIdAndIndex<T> nextExpected = remainingExpected.getAndRemoveNextItem();
      String nextId = nextExpected.getId();

      if (remainingActual.hasItemWithId(nextId)) {
        ItemWithIdAndIndex<T> matchingActual = remainingActual.getAndRemoveItemWithId(nextId);
        result.addMatched(nextExpected, matchingActual);
      }
      else {
        result.addRemoved(nextExpected);
      }
    }

    while (remainingActual.hasMoreItems()) {
      result.addAdded(remainingActual.getAndRemoveNextItem());
    }

    return result;
  }

  private static class MatchingResultImpl<T> implements MatchingResult<T> {

    private final List<ItemWithIdAndIndex<T>> matchedExpected = new ArrayList<>();
    private final List<ItemWithIdAndIndex<T>> matchedActual = new ArrayList<>();

    private final List<ItemWithIdAndIndex<T>> removedExpected = new ArrayList<>();
    private final List<ItemWithIdAndIndex<T>> addedActual = new ArrayList<>();

    void addMatched(ItemWithIdAndIndex<T> expected, ItemWithIdAndIndex<T> actual) {
      matchedExpected.add(expected);
      matchedActual.add(actual);
    }

    void addRemoved(ItemWithIdAndIndex<T> removed) {
      this.removedExpected.add(removed);
    }

    void addAdded(ItemWithIdAndIndex<T> added) {
      this.addedActual.add(added);
    }

    @Override
    public boolean areMatchesReordered() {
      int lastIndex = -1;
      for (ItemWithIdAndIndex actual : matchedActual) {
        int nextIndex = actual.getIndex();
        if (nextIndex < lastIndex) {
          return true;
        }
        lastIndex = nextIndex;
      }
      return false;
    }

    private List<T> extractItems(List<ItemWithIdAndIndex<T>> list) {
      return list.stream()
          .map(ItemWithIdAndIndex<T>::getItem)
          .collect(Collectors.toList());
    }

    @Override
    public List<T> getMatchedExpected() {
      return extractItems(matchedExpected);
    }

    @Override
    public List<T> getMatchedActual() {
      return extractItems(matchedActual);
    }

    @Override
    public List<T> getRemovedExpected() {
      return extractItems(removedExpected);
    }

    @Override
    public List<T> getAddedActual() {
      return extractItems(addedActual);
    }
  }

  private static class ItemWithIdAndIndex<T> {

    private final T item;
    private final int index;
    private final String id;

    ItemWithIdAndIndex(T item, int index, String id) {
      this.item = item;
      this.index = index;
      this.id = id;
    }

    public T getItem() {
      return this.item;
    }

    public int getIndex() {
      return this.index;
    }

    public String getId() {
      return this.id;
    }

    static <T> List<ItemWithIdAndIndex<T>> createListFrom(Iterable<T> items, Function<T, String> idProvider) {
      List<ItemWithIdAndIndex<T>> itemList = new ArrayList<>();

      int index = 0;
      for (T item : items) {
        itemList.add(new ItemWithIdAndIndex<T>(item, index++, idProvider.apply(item)));
      }

      return itemList;
    }

    @Override
    public String toString() {
      return "{index=" + index + ", id=" + id + "}";
    }
  }

  private static class IndexedItemList<T> {

    private final List<ItemWithIdAndIndex<T>> itemList;
    private final Multimap<String, ItemWithIdAndIndex<T>> idItemMap = LinkedListMultimap.create();

    IndexedItemList(Iterable<T> resources, Function<T, String> idProvider) {
      this.itemList = ItemWithIdAndIndex.createListFrom(resources, idProvider);

      for (ItemWithIdAndIndex<T> item : itemList) {
        idItemMap.put(item.getId(), item);
      }
    }

    boolean hasMoreItems() {
      return itemList.size() > 0;
    }

    ItemWithIdAndIndex<T> getAndRemoveNextItem() {
      ItemWithIdAndIndex<T> item = itemList.remove(0);
      idItemMap.remove(item.getId(), item);
      return item;
    }

    boolean hasItemWithId(String id) {
      return idItemMap.containsKey(id);
    }

    ItemWithIdAndIndex<T> getAndRemoveItemWithId(String id) {
      ItemWithIdAndIndex<T> item = idItemMap.get(id).iterator().next();
      itemList.remove(item);
      idItemMap.remove(id, item);
      return item;
    }

    @Override
    public String toString() {
      return itemList.toString();
    }
  }
}