1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package io.wcm.caravan.hal.comparison.impl.matching;
21
22 import java.util.ArrayList;
23 import java.util.List;
24 import java.util.function.Function;
25 import java.util.stream.Collectors;
26
27 import com.google.common.collect.LinkedListMultimap;
28 import com.google.common.collect.Multimap;
29
30
31
32
33 public class SimpleIdMatchingAlgorithm<T> implements MatchingAlgorithm<T> {
34
35 private final Function<T, String> idProvider;
36
37
38
39
40 public SimpleIdMatchingAlgorithm(Function<T, String> idProvider) {
41 this.idProvider = idProvider;
42 }
43
44 @Override
45 public MatchingResult<T> findMatchingItems(List<T> expectedList, List<T> actualList) {
46
47 MatchingResultImpl<T> result = new MatchingResultImpl<T>();
48
49 IndexedItemList<T> remainingExpected = new IndexedItemList<T>(expectedList, idProvider);
50 IndexedItemList<T> remainingActual = new IndexedItemList<T>(actualList, idProvider);
51
52 while (remainingExpected.hasMoreItems()) {
53 ItemWithIdAndIndex<T> nextExpected = remainingExpected.getAndRemoveNextItem();
54 String nextId = nextExpected.getId();
55
56 if (remainingActual.hasItemWithId(nextId)) {
57 ItemWithIdAndIndex<T> matchingActual = remainingActual.getAndRemoveItemWithId(nextId);
58 result.addMatched(nextExpected, matchingActual);
59 }
60 else {
61 result.addRemoved(nextExpected);
62 }
63 }
64
65 while (remainingActual.hasMoreItems()) {
66 result.addAdded(remainingActual.getAndRemoveNextItem());
67 }
68
69 return result;
70 }
71
72 private static class MatchingResultImpl<T> implements MatchingResult<T> {
73
74 private final List<ItemWithIdAndIndex<T>> matchedExpected = new ArrayList<>();
75 private final List<ItemWithIdAndIndex<T>> matchedActual = new ArrayList<>();
76
77 private final List<ItemWithIdAndIndex<T>> removedExpected = new ArrayList<>();
78 private final List<ItemWithIdAndIndex<T>> addedActual = new ArrayList<>();
79
80 void addMatched(ItemWithIdAndIndex<T> expected, ItemWithIdAndIndex<T> actual) {
81 matchedExpected.add(expected);
82 matchedActual.add(actual);
83 }
84
85 void addRemoved(ItemWithIdAndIndex<T> removed) {
86 this.removedExpected.add(removed);
87 }
88
89 void addAdded(ItemWithIdAndIndex<T> added) {
90 this.addedActual.add(added);
91 }
92
93 @Override
94 public boolean areMatchesReordered() {
95 int lastIndex = -1;
96 for (ItemWithIdAndIndex actual : matchedActual) {
97 int nextIndex = actual.getIndex();
98 if (nextIndex < lastIndex) {
99 return true;
100 }
101 lastIndex = nextIndex;
102 }
103 return false;
104 }
105
106 private List<T> extractItems(List<ItemWithIdAndIndex<T>> list) {
107 return list.stream()
108 .map(ItemWithIdAndIndex<T>::getItem)
109 .collect(Collectors.toList());
110 }
111
112 @Override
113 public List<T> getMatchedExpected() {
114 return extractItems(matchedExpected);
115 }
116
117 @Override
118 public List<T> getMatchedActual() {
119 return extractItems(matchedActual);
120 }
121
122 @Override
123 public List<T> getRemovedExpected() {
124 return extractItems(removedExpected);
125 }
126
127 @Override
128 public List<T> getAddedActual() {
129 return extractItems(addedActual);
130 }
131 }
132
133 private static class ItemWithIdAndIndex<T> {
134
135 private final T item;
136 private final int index;
137 private final String id;
138
139 ItemWithIdAndIndex(T item, int index, String id) {
140 this.item = item;
141 this.index = index;
142 this.id = id;
143 }
144
145 public T getItem() {
146 return this.item;
147 }
148
149 public int getIndex() {
150 return this.index;
151 }
152
153 public String getId() {
154 return this.id;
155 }
156
157 static <T> List<ItemWithIdAndIndex<T>> createListFrom(Iterable<T> items, Function<T, String> idProvider) {
158 List<ItemWithIdAndIndex<T>> itemList = new ArrayList<>();
159
160 int index = 0;
161 for (T item : items) {
162 itemList.add(new ItemWithIdAndIndex<T>(item, index++, idProvider.apply(item)));
163 }
164
165 return itemList;
166 }
167
168 @Override
169 public String toString() {
170 return "{index=" + index + ", id=" + id + "}";
171 }
172 }
173
174 private static class IndexedItemList<T> {
175
176 private final List<ItemWithIdAndIndex<T>> itemList;
177 private final Multimap<String, ItemWithIdAndIndex<T>> idItemMap = LinkedListMultimap.create();
178
179 IndexedItemList(Iterable<T> resources, Function<T, String> idProvider) {
180 this.itemList = ItemWithIdAndIndex.createListFrom(resources, idProvider);
181
182 for (ItemWithIdAndIndex<T> item : itemList) {
183 idItemMap.put(item.getId(), item);
184 }
185 }
186
187 boolean hasMoreItems() {
188 return itemList.size() > 0;
189 }
190
191 ItemWithIdAndIndex<T> getAndRemoveNextItem() {
192 ItemWithIdAndIndex<T> item = itemList.remove(0);
193 idItemMap.remove(item.getId(), item);
194 return item;
195 }
196
197 boolean hasItemWithId(String id) {
198 return idItemMap.containsKey(id);
199 }
200
201 ItemWithIdAndIndex<T> getAndRemoveItemWithId(String id) {
202 ItemWithIdAndIndex<T> item = idItemMap.get(id).iterator().next();
203 itemList.remove(item);
204 idItemMap.remove(id, item);
205 return item;
206 }
207
208 @Override
209 public String toString() {
210 return itemList.toString();
211 }
212 }
213 }