diff options
Diffstat (limited to 'subprojects/viatra-runtime-matchers/src/main/java/tools/refinery/viatra/runtime/matchers/algorithms/OrderedIterableMerge.java')
-rw-r--r-- | subprojects/viatra-runtime-matchers/src/main/java/tools/refinery/viatra/runtime/matchers/algorithms/OrderedIterableMerge.java | 83 |
1 files changed, 83 insertions, 0 deletions
diff --git a/subprojects/viatra-runtime-matchers/src/main/java/tools/refinery/viatra/runtime/matchers/algorithms/OrderedIterableMerge.java b/subprojects/viatra-runtime-matchers/src/main/java/tools/refinery/viatra/runtime/matchers/algorithms/OrderedIterableMerge.java new file mode 100644 index 00000000..1917e909 --- /dev/null +++ b/subprojects/viatra-runtime-matchers/src/main/java/tools/refinery/viatra/runtime/matchers/algorithms/OrderedIterableMerge.java | |||
@@ -0,0 +1,83 @@ | |||
1 | /******************************************************************************* | ||
2 | * Copyright (c) 2010-2018, Gabor Bergmann, IncQuery Labs Ltd. | ||
3 | * This program and the accompanying materials are made available under the | ||
4 | * terms of the Eclipse Public License v. 2.0 which is available at | ||
5 | * http://www.eclipse.org/legal/epl-v20.html. | ||
6 | * | ||
7 | * SPDX-License-Identifier: EPL-2.0 | ||
8 | *******************************************************************************/ | ||
9 | package tools.refinery.viatra.runtime.matchers.algorithms; | ||
10 | |||
11 | import java.util.Comparator; | ||
12 | import java.util.Iterator; | ||
13 | import java.util.NoSuchElementException; | ||
14 | |||
15 | /** | ||
16 | * @author Gabor Bergmann | ||
17 | * @since 2.1 | ||
18 | * | ||
19 | */ | ||
20 | public class OrderedIterableMerge { | ||
21 | |||
22 | private OrderedIterableMerge() { | ||
23 | // Hidden utility class constructor | ||
24 | } | ||
25 | |||
26 | /** | ||
27 | * Lazily merges two iterables, each ordered according to a given comparator. | ||
28 | * Retains order in the result, and also eliminates any duplicates that appear in both arguments. | ||
29 | */ | ||
30 | public static <T> Iterable<T> mergeUniques(Iterable<T> first, Iterable<T> second, Comparator<T> comparator) { | ||
31 | return () -> new Iterator<T>() { | ||
32 | Iterator<T> firstIterator = first.iterator(); | ||
33 | Iterator<T> secondIterator = second.iterator(); | ||
34 | T firstItem; | ||
35 | T secondItem; | ||
36 | |||
37 | { | ||
38 | fetchFirst(); | ||
39 | fetchSecond(); | ||
40 | } | ||
41 | |||
42 | private T fetchFirst() { | ||
43 | T previous = firstItem; | ||
44 | if (firstIterator.hasNext()) | ||
45 | firstItem = firstIterator.next(); | ||
46 | else | ||
47 | firstItem = null; | ||
48 | return previous; | ||
49 | } | ||
50 | private T fetchSecond() { | ||
51 | T previous = secondItem; | ||
52 | if (secondIterator.hasNext()) | ||
53 | secondItem = secondIterator.next(); | ||
54 | else | ||
55 | secondItem = null; | ||
56 | return previous; | ||
57 | } | ||
58 | |||
59 | @Override | ||
60 | public boolean hasNext() { | ||
61 | return firstItem != null || secondItem != null; | ||
62 | } | ||
63 | @Override | ||
64 | public T next() { | ||
65 | if (!hasNext()) throw new NoSuchElementException(); | ||
66 | if (firstItem != null && secondItem != null) { | ||
67 | if (secondItem == firstItem) { // duplicates | ||
68 | fetchFirst(); | ||
69 | return fetchSecond(); | ||
70 | } else if (comparator.compare(firstItem, secondItem) < 0) { | ||
71 | return fetchFirst(); | ||
72 | } else { | ||
73 | return fetchSecond(); | ||
74 | } | ||
75 | } else if (firstItem != null) { | ||
76 | return fetchFirst(); | ||
77 | } else { // secondItem must be non-null | ||
78 | return fetchSecond(); | ||
79 | } | ||
80 | } | ||
81 | }; | ||
82 | } | ||
83 | } | ||