diff options
author | 2023-06-29 02:30:40 +0200 | |
---|---|---|
committer | 2023-06-29 02:30:40 +0200 | |
commit | 7413a73f35e6c5e4cb3dc0570ec0be3819b87bd5 (patch) | |
tree | 9cc6850dba18ed526eb27a911bc3f73b28752a14 /subprojects/store-query | |
parent | fix: FilteredView default value (diff) | |
parent | feat: ordered query ResultSet (diff) | |
download | refinery-7413a73f35e6c5e4cb3dc0570ec0be3819b87bd5.tar.gz refinery-7413a73f35e6c5e4cb3dc0570ec0be3819b87bd5.tar.zst refinery-7413a73f35e6c5e4cb3dc0570ec0be3819b87bd5.zip |
Merge pull request #27 from kris7t/ordered-result-set
feat: ordered query ResultSet
Diffstat (limited to 'subprojects/store-query')
11 files changed, 1567 insertions, 5 deletions
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryAdapter.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryAdapter.java index ae3bbcbb..1fa96a07 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryAdapter.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/ModelQueryAdapter.java | |||
@@ -8,6 +8,8 @@ package tools.refinery.store.query; | |||
8 | import tools.refinery.store.adapter.ModelAdapter; | 8 | import tools.refinery.store.adapter.ModelAdapter; |
9 | import tools.refinery.store.query.dnf.AnyQuery; | 9 | import tools.refinery.store.query.dnf.AnyQuery; |
10 | import tools.refinery.store.query.dnf.Query; | 10 | import tools.refinery.store.query.dnf.Query; |
11 | import tools.refinery.store.query.resultset.AnyResultSet; | ||
12 | import tools.refinery.store.query.resultset.ResultSet; | ||
11 | 13 | ||
12 | public interface ModelQueryAdapter extends ModelAdapter { | 14 | public interface ModelQueryAdapter extends ModelAdapter { |
13 | ModelQueryStoreAdapter getStoreAdapter(); | 15 | ModelQueryStoreAdapter getStoreAdapter(); |
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Dnf.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Dnf.java index c5b51b81..50b245f7 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Dnf.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/Dnf.java | |||
@@ -6,7 +6,7 @@ | |||
6 | package tools.refinery.store.query.dnf; | 6 | package tools.refinery.store.query.dnf; |
7 | 7 | ||
8 | import tools.refinery.store.query.Constraint; | 8 | import tools.refinery.store.query.Constraint; |
9 | import tools.refinery.store.query.Reduction; | 9 | import tools.refinery.store.query.literal.Reduction; |
10 | import tools.refinery.store.query.equality.DnfEqualityChecker; | 10 | import tools.refinery.store.query.equality.DnfEqualityChecker; |
11 | import tools.refinery.store.query.equality.LiteralEqualityHelper; | 11 | import tools.refinery.store.query.equality.LiteralEqualityHelper; |
12 | import tools.refinery.store.query.term.Parameter; | 12 | import tools.refinery.store.query.term.Parameter; |
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/Reduction.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Reduction.java index 82c52b04..ee155a9a 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/Reduction.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Reduction.java | |||
@@ -3,7 +3,7 @@ | |||
3 | * | 3 | * |
4 | * SPDX-License-Identifier: EPL-2.0 | 4 | * SPDX-License-Identifier: EPL-2.0 |
5 | */ | 5 | */ |
6 | package tools.refinery.store.query; | 6 | package tools.refinery.store.query.literal; |
7 | 7 | ||
8 | public enum Reduction { | 8 | public enum Reduction { |
9 | /** | 9 | /** |
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AbstractResultSet.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AbstractResultSet.java new file mode 100644 index 00000000..a710c64d --- /dev/null +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AbstractResultSet.java | |||
@@ -0,0 +1,63 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.query.resultset; | ||
7 | |||
8 | import tools.refinery.store.query.ModelQueryAdapter; | ||
9 | import tools.refinery.store.query.dnf.Query; | ||
10 | import tools.refinery.store.tuple.Tuple; | ||
11 | |||
12 | import java.util.ArrayList; | ||
13 | import java.util.List; | ||
14 | |||
15 | public abstract class AbstractResultSet<T> implements ResultSet<T> { | ||
16 | private final ModelQueryAdapter adapter; | ||
17 | private final Query<T> query; | ||
18 | private final List<ResultSetListener<T>> listeners = new ArrayList<>(); | ||
19 | |||
20 | protected AbstractResultSet(ModelQueryAdapter adapter, Query<T> query) { | ||
21 | this.adapter = adapter; | ||
22 | this.query = query; | ||
23 | } | ||
24 | |||
25 | @Override | ||
26 | public ModelQueryAdapter getAdapter() { | ||
27 | return adapter; | ||
28 | } | ||
29 | |||
30 | @Override | ||
31 | public Query<T> getQuery() { | ||
32 | return query; | ||
33 | } | ||
34 | |||
35 | @Override | ||
36 | public void addListener(ResultSetListener<T> listener) { | ||
37 | if (listeners.isEmpty()) { | ||
38 | startListeningForChanges(); | ||
39 | } | ||
40 | listeners.add(listener); | ||
41 | } | ||
42 | |||
43 | @Override | ||
44 | public void removeListener(ResultSetListener<T> listener) { | ||
45 | listeners.remove(listener); | ||
46 | if (listeners.isEmpty()) { | ||
47 | stopListeningForChanges(); | ||
48 | } | ||
49 | } | ||
50 | |||
51 | protected abstract void startListeningForChanges(); | ||
52 | |||
53 | protected abstract void stopListeningForChanges(); | ||
54 | |||
55 | protected void notifyChange(Tuple key, T oldValue, T newValue) { | ||
56 | int listenerCount = listeners.size(); | ||
57 | // Use a for loop instead of a for-each loop to avoid {@code Iterator} allocation overhead. | ||
58 | //noinspection ForLoopReplaceableByForEach | ||
59 | for (int i = 0; i < listenerCount; i++) { | ||
60 | listeners.get(i).put(key, oldValue, newValue); | ||
61 | } | ||
62 | } | ||
63 | } | ||
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/AnyResultSet.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AnyResultSet.java index f29bb278..02809477 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/AnyResultSet.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/AnyResultSet.java | |||
@@ -3,8 +3,9 @@ | |||
3 | * | 3 | * |
4 | * SPDX-License-Identifier: EPL-2.0 | 4 | * SPDX-License-Identifier: EPL-2.0 |
5 | */ | 5 | */ |
6 | package tools.refinery.store.query; | 6 | package tools.refinery.store.query.resultset; |
7 | 7 | ||
8 | import tools.refinery.store.query.ModelQueryAdapter; | ||
8 | import tools.refinery.store.query.dnf.AnyQuery; | 9 | import tools.refinery.store.query.dnf.AnyQuery; |
9 | 10 | ||
10 | public sealed interface AnyResultSet permits ResultSet { | 11 | public sealed interface AnyResultSet permits ResultSet { |
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/EmptyResultSet.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/EmptyResultSet.java index 5361f645..2795a44b 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/EmptyResultSet.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/EmptyResultSet.java | |||
@@ -3,10 +3,11 @@ | |||
3 | * | 3 | * |
4 | * SPDX-License-Identifier: EPL-2.0 | 4 | * SPDX-License-Identifier: EPL-2.0 |
5 | */ | 5 | */ |
6 | package tools.refinery.store.query; | 6 | package tools.refinery.store.query.resultset; |
7 | 7 | ||
8 | import tools.refinery.store.map.Cursor; | 8 | import tools.refinery.store.map.Cursor; |
9 | import tools.refinery.store.map.Cursors; | 9 | import tools.refinery.store.map.Cursors; |
10 | import tools.refinery.store.query.ModelQueryAdapter; | ||
10 | import tools.refinery.store.query.dnf.Query; | 11 | import tools.refinery.store.query.dnf.Query; |
11 | import tools.refinery.store.tuple.Tuple; | 12 | import tools.refinery.store.tuple.Tuple; |
12 | 13 | ||
@@ -35,4 +36,14 @@ public record EmptyResultSet<T>(ModelQueryAdapter adapter, Query<T> query) imple | |||
35 | public int size() { | 36 | public int size() { |
36 | return 0; | 37 | return 0; |
37 | } | 38 | } |
39 | |||
40 | @Override | ||
41 | public void addListener(ResultSetListener<T> listener) { | ||
42 | // No need to store the listener, because the empty result set will never change. | ||
43 | } | ||
44 | |||
45 | @Override | ||
46 | public void removeListener(ResultSetListener<T> listener) { | ||
47 | // No need to remove the listener, because we never stored it. | ||
48 | } | ||
38 | } | 49 | } |
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/OrderedResultSet.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/OrderedResultSet.java new file mode 100644 index 00000000..39006d65 --- /dev/null +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/OrderedResultSet.java | |||
@@ -0,0 +1,80 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.query.resultset; | ||
7 | |||
8 | import tools.refinery.store.map.Cursor; | ||
9 | import tools.refinery.store.query.ModelQueryAdapter; | ||
10 | import tools.refinery.store.query.dnf.Query; | ||
11 | import tools.refinery.store.query.utils.OrderStatisticTree; | ||
12 | import tools.refinery.store.tuple.Tuple; | ||
13 | |||
14 | import java.util.Objects; | ||
15 | |||
16 | public class OrderedResultSet<T> implements AutoCloseable, ResultSet<T> { | ||
17 | private final ResultSet<T> resultSet; | ||
18 | private final OrderStatisticTree<Tuple> tree = new OrderStatisticTree<>(); | ||
19 | private final ResultSetListener<T> listener = (key, fromValue, toValue) -> { | ||
20 | var defaultValue = getQuery().defaultValue(); | ||
21 | if (Objects.equals(defaultValue, toValue)) { | ||
22 | tree.remove(key); | ||
23 | } else { | ||
24 | tree.add(key); | ||
25 | } | ||
26 | }; | ||
27 | |||
28 | public OrderedResultSet(ResultSet<T> resultSet) { | ||
29 | this.resultSet = resultSet; | ||
30 | resultSet.addListener(listener); | ||
31 | var cursor = resultSet.getAll(); | ||
32 | while (cursor.move()) { | ||
33 | tree.add(cursor.getKey()); | ||
34 | } | ||
35 | } | ||
36 | |||
37 | @Override | ||
38 | public ModelQueryAdapter getAdapter() { | ||
39 | return resultSet.getAdapter(); | ||
40 | } | ||
41 | |||
42 | @Override | ||
43 | public int size() { | ||
44 | return resultSet.size(); | ||
45 | } | ||
46 | |||
47 | @Override | ||
48 | public Query<T> getQuery() { | ||
49 | return resultSet.getQuery(); | ||
50 | } | ||
51 | |||
52 | @Override | ||
53 | public T get(Tuple parameters) { | ||
54 | return resultSet.get(parameters); | ||
55 | } | ||
56 | |||
57 | public Tuple getKey(int index) { | ||
58 | return tree.get(index); | ||
59 | } | ||
60 | |||
61 | @Override | ||
62 | public Cursor<Tuple, T> getAll() { | ||
63 | return resultSet.getAll(); | ||
64 | } | ||
65 | |||
66 | @Override | ||
67 | public void addListener(ResultSetListener<T> listener) { | ||
68 | resultSet.addListener(listener); | ||
69 | } | ||
70 | |||
71 | @Override | ||
72 | public void removeListener(ResultSetListener<T> listener) { | ||
73 | resultSet.removeListener(listener); | ||
74 | } | ||
75 | |||
76 | @Override | ||
77 | public void close() { | ||
78 | resultSet.removeListener(listener); | ||
79 | } | ||
80 | } | ||
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/ResultSet.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/ResultSet.java index 9ab83172..33d1ea95 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/ResultSet.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/ResultSet.java | |||
@@ -3,7 +3,7 @@ | |||
3 | * | 3 | * |
4 | * SPDX-License-Identifier: EPL-2.0 | 4 | * SPDX-License-Identifier: EPL-2.0 |
5 | */ | 5 | */ |
6 | package tools.refinery.store.query; | 6 | package tools.refinery.store.query.resultset; |
7 | 7 | ||
8 | import tools.refinery.store.map.Cursor; | 8 | import tools.refinery.store.map.Cursor; |
9 | import tools.refinery.store.query.dnf.Query; | 9 | import tools.refinery.store.query.dnf.Query; |
@@ -15,4 +15,8 @@ public non-sealed interface ResultSet<T> extends AnyResultSet { | |||
15 | T get(Tuple parameters); | 15 | T get(Tuple parameters); |
16 | 16 | ||
17 | Cursor<Tuple, T> getAll(); | 17 | Cursor<Tuple, T> getAll(); |
18 | |||
19 | void addListener(ResultSetListener<T> listener); | ||
20 | |||
21 | void removeListener(ResultSetListener<T> listener); | ||
18 | } | 22 | } |
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/ResultSetListener.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/ResultSetListener.java new file mode 100644 index 00000000..fd8a503e --- /dev/null +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/resultset/ResultSetListener.java | |||
@@ -0,0 +1,13 @@ | |||
1 | /* | ||
2 | * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * | ||
4 | * SPDX-License-Identifier: EPL-2.0 | ||
5 | */ | ||
6 | package tools.refinery.store.query.resultset; | ||
7 | |||
8 | import tools.refinery.store.tuple.Tuple; | ||
9 | |||
10 | @FunctionalInterface | ||
11 | public interface ResultSetListener<T> { | ||
12 | void put(Tuple key, T fromValue, T toValue); | ||
13 | } | ||
diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/utils/OrderStatisticTree.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/utils/OrderStatisticTree.java new file mode 100644 index 00000000..b568b99d --- /dev/null +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/utils/OrderStatisticTree.java | |||
@@ -0,0 +1,754 @@ | |||
1 | /* | ||
2 | * Copyright (c) 2021 Rodion Efremov | ||
3 | * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/> | ||
4 | * | ||
5 | * SPDX-License-Identifier: MIT OR EPL-2.0 | ||
6 | */ | ||
7 | package tools.refinery.store.query.utils; | ||
8 | |||
9 | import java.util.*; | ||
10 | |||
11 | /** | ||
12 | * This class implements an order statistic tree which is based on AVL-trees. | ||
13 | * <p> | ||
14 | * This class was copied into <i>Refinery</i> from | ||
15 | * <a href="https://github.com/coderodde/OrderStatisticTree/tree/546c343b9f5d868e394a079ff32691c9dbfd83e3">https://github.com/coderodde/OrderStatisticTree</a> | ||
16 | * and is available under the | ||
17 | * <a href="https://github.com/coderodde/OrderStatisticTree/blob/master/LICENSE">MIT License</a>. | ||
18 | * We also incorporated changes by <a href="https://github.com/coderodde/OrderStatisticTree/issues/3">Eugene Schava</a> | ||
19 | * and cleaned up some linter warnings. | ||
20 | * | ||
21 | * @param <T> the actual element type. | ||
22 | * @author Rodion "rodde" Efremov | ||
23 | * @version based on 1.6 (Feb 11, 2016) | ||
24 | */ | ||
25 | public class OrderStatisticTree<T extends Comparable<? super T>> implements Set<T> { | ||
26 | |||
27 | @Override | ||
28 | public Iterator<T> iterator() { | ||
29 | return new TreeIterator(); | ||
30 | } | ||
31 | |||
32 | private final class TreeIterator implements Iterator<T> { | ||
33 | |||
34 | private Node<T> previousNode; | ||
35 | private Node<T> nextNode; | ||
36 | private int expectedModCount = modCount; | ||
37 | |||
38 | TreeIterator() { | ||
39 | if (root == null) { | ||
40 | nextNode = null; | ||
41 | } else { | ||
42 | nextNode = minimumNode(root); | ||
43 | } | ||
44 | } | ||
45 | |||
46 | @Override | ||
47 | public boolean hasNext() { | ||
48 | return nextNode != null; | ||
49 | } | ||
50 | |||
51 | @Override | ||
52 | public T next() { | ||
53 | if (nextNode == null) { | ||
54 | throw new NoSuchElementException("Iteration exceeded."); | ||
55 | } | ||
56 | |||
57 | checkConcurrentModification(); | ||
58 | T datum = nextNode.key; | ||
59 | previousNode = nextNode; | ||
60 | nextNode = successorOf(nextNode); | ||
61 | return datum; | ||
62 | } | ||
63 | |||
64 | @Override | ||
65 | public void remove() { | ||
66 | if (previousNode == null) { | ||
67 | throw new IllegalStateException( | ||
68 | nextNode == null ? | ||
69 | "Not a single call to next(); nothing to remove." : | ||
70 | "Removing the same element twice." | ||
71 | ); | ||
72 | } | ||
73 | |||
74 | checkConcurrentModification(); | ||
75 | |||
76 | Node<T> x = deleteNode(previousNode); | ||
77 | fixAfterModification(x, false); | ||
78 | |||
79 | if (x == nextNode) { | ||
80 | nextNode = previousNode; | ||
81 | } | ||
82 | |||
83 | expectedModCount = ++modCount; | ||
84 | size--; | ||
85 | previousNode = null; | ||
86 | } | ||
87 | |||
88 | private void checkConcurrentModification() { | ||
89 | if (expectedModCount != modCount) { | ||
90 | throw new ConcurrentModificationException( | ||
91 | "The set was modified while iterating."); | ||
92 | } | ||
93 | } | ||
94 | |||
95 | private Node<T> successorOf(Node<T> node) { | ||
96 | if (node.right != null) { | ||
97 | node = node.right; | ||
98 | |||
99 | while (node.left != null) { | ||
100 | node = node.left; | ||
101 | } | ||
102 | |||
103 | return node; | ||
104 | } | ||
105 | |||
106 | Node<T> parent = node.parent; | ||
107 | |||
108 | while (parent != null && parent.right == node) { | ||
109 | node = parent; | ||
110 | parent = parent.parent; | ||
111 | } | ||
112 | |||
113 | return parent; | ||
114 | } | ||
115 | } | ||
116 | |||
117 | @Override | ||
118 | public Object[] toArray() { | ||
119 | Object[] array = new Object[size]; | ||
120 | Iterator<T> iterator = iterator(); | ||
121 | int index = 0; | ||
122 | |||
123 | while (iterator.hasNext()) { | ||
124 | array[index++] = iterator.next(); | ||
125 | } | ||
126 | |||
127 | return array; | ||
128 | } | ||
129 | |||
130 | @Override | ||
131 | public <U> U[] toArray(U[] a) { | ||
132 | Iterator<T> iterator = iterator(); | ||
133 | |||
134 | if (size > a.length) { | ||
135 | a = Arrays.copyOf(a, size); | ||
136 | } | ||
137 | |||
138 | int index = 0; | ||
139 | |||
140 | for (; index < size; ++index) { | ||
141 | @SuppressWarnings("unchecked") | ||
142 | var convertedValue = (U) iterator.next(); | ||
143 | a[index] = convertedValue; | ||
144 | } | ||
145 | |||
146 | if (index < a.length) { | ||
147 | a[index] = null; | ||
148 | } | ||
149 | |||
150 | return a; | ||
151 | } | ||
152 | |||
153 | @Override | ||
154 | public boolean containsAll(Collection<?> c) { | ||
155 | for (Object element : c) { | ||
156 | if (!contains(element)) { | ||
157 | return false; | ||
158 | } | ||
159 | } | ||
160 | |||
161 | return true; | ||
162 | } | ||
163 | |||
164 | @Override | ||
165 | public boolean addAll(Collection<? extends T> c) { | ||
166 | boolean modified = false; | ||
167 | |||
168 | for (T element : c) { | ||
169 | if (add(element)) { | ||
170 | modified = true; | ||
171 | } | ||
172 | } | ||
173 | |||
174 | return modified; | ||
175 | } | ||
176 | |||
177 | @Override | ||
178 | public boolean retainAll(Collection<?> c) { | ||
179 | if (!c.getClass().equals(HashSet.class)) { | ||
180 | c = new HashSet<>(c); | ||
181 | } | ||
182 | |||
183 | Iterator<T> iterator = iterator(); | ||
184 | boolean modified = false; | ||
185 | |||
186 | while (iterator.hasNext()) { | ||
187 | T element = iterator.next(); | ||
188 | |||
189 | if (!c.contains(element)) { | ||
190 | iterator.remove(); | ||
191 | modified = true; | ||
192 | } | ||
193 | } | ||
194 | |||
195 | return modified; | ||
196 | } | ||
197 | |||
198 | @Override | ||
199 | public boolean removeAll(Collection<?> c) { | ||
200 | boolean modified = false; | ||
201 | |||
202 | for (Object element : c) { | ||
203 | if (remove(element)) { | ||
204 | modified = true; | ||
205 | } | ||
206 | } | ||
207 | |||
208 | return modified; | ||
209 | } | ||
210 | |||
211 | private static final class Node<T> { | ||
212 | T key; | ||
213 | |||
214 | Node<T> parent; | ||
215 | Node<T> left; | ||
216 | Node<T> right; | ||
217 | |||
218 | int height; | ||
219 | int count; | ||
220 | |||
221 | Node(T key) { | ||
222 | this.key = key; | ||
223 | } | ||
224 | } | ||
225 | |||
226 | private Node<T> root; | ||
227 | private int size; | ||
228 | private int modCount; | ||
229 | |||
230 | @Override | ||
231 | public boolean add(T element) { | ||
232 | Objects.requireNonNull(element, "The input element is null."); | ||
233 | |||
234 | if (root == null) { | ||
235 | root = new Node<>(element); | ||
236 | size = 1; | ||
237 | modCount++; | ||
238 | return true; | ||
239 | } | ||
240 | |||
241 | Node<T> parent = null; | ||
242 | Node<T> node = root; | ||
243 | int cmp; | ||
244 | |||
245 | while (node != null) { | ||
246 | cmp = element.compareTo(node.key); | ||
247 | |||
248 | if (cmp == 0) { | ||
249 | // The element is already in this tree. | ||
250 | return false; | ||
251 | } | ||
252 | |||
253 | parent = node; | ||
254 | |||
255 | if (cmp < 0) { | ||
256 | node = node.left; | ||
257 | } else { | ||
258 | node = node.right; | ||
259 | } | ||
260 | } | ||
261 | |||
262 | Node<T> newnode = new Node<>(element); | ||
263 | |||
264 | if (element.compareTo(parent.key) < 0) { | ||
265 | parent.left = newnode; | ||
266 | } else { | ||
267 | parent.right = newnode; | ||
268 | } | ||
269 | |||
270 | newnode.parent = parent; | ||
271 | size++; | ||
272 | modCount++; | ||
273 | Node<T> hi = parent; | ||
274 | Node<T> lo = newnode; | ||
275 | |||
276 | while (hi != null) { | ||
277 | if (hi.left == lo) { | ||
278 | hi.count++; | ||
279 | } | ||
280 | |||
281 | lo = hi; | ||
282 | hi = hi.parent; | ||
283 | } | ||
284 | |||
285 | fixAfterModification(newnode, true); | ||
286 | return true; | ||
287 | } | ||
288 | |||
289 | @Override | ||
290 | public boolean contains(Object o) { | ||
291 | @SuppressWarnings("unchecked") | ||
292 | T element = (T) o; | ||
293 | Node<T> x = root; | ||
294 | int cmp; | ||
295 | |||
296 | while (x != null && (cmp = element.compareTo(x.key)) != 0) { | ||
297 | if (cmp < 0) { | ||
298 | x = x.left; | ||
299 | } else { | ||
300 | x = x.right; | ||
301 | } | ||
302 | } | ||
303 | |||
304 | return x != null; | ||
305 | } | ||
306 | |||
307 | @Override | ||
308 | public boolean remove(Object o) { | ||
309 | @SuppressWarnings("unchecked") | ||
310 | T element = (T) o; | ||
311 | Node<T> x = root; | ||
312 | int cmp; | ||
313 | |||
314 | while (x != null && (cmp = element.compareTo(x.key)) != 0) { | ||
315 | if (cmp < 0) { | ||
316 | x = x.left; | ||
317 | } else { | ||
318 | x = x.right; | ||
319 | } | ||
320 | } | ||
321 | |||
322 | if (x == null) { | ||
323 | return false; | ||
324 | } | ||
325 | |||
326 | x = deleteNode(x); | ||
327 | fixAfterModification(x, false); | ||
328 | size--; | ||
329 | modCount++; | ||
330 | return true; | ||
331 | } | ||
332 | |||
333 | public T get(int index) { | ||
334 | checkIndex(index); | ||
335 | Node<T> node = root; | ||
336 | |||
337 | while (true) { | ||
338 | if (index > node.count) { | ||
339 | index -= node.count + 1; | ||
340 | node = node.right; | ||
341 | } else if (index < node.count) { | ||
342 | node = node.left; | ||
343 | } else { | ||
344 | return node.key; | ||
345 | } | ||
346 | } | ||
347 | } | ||
348 | |||
349 | public int indexOf(T element) { | ||
350 | Node<T> node = root; | ||
351 | |||
352 | if (root == null) { | ||
353 | return -1; | ||
354 | } | ||
355 | |||
356 | int rank = root.count; | ||
357 | int cmp; | ||
358 | |||
359 | while (true) { | ||
360 | if ((cmp = element.compareTo(node.key)) < 0) { | ||
361 | if (node.left == null) { | ||
362 | return -1; | ||
363 | } | ||
364 | |||
365 | rank -= (node.count - node.left.count); | ||
366 | node = node.left; | ||
367 | } else if (cmp > 0) { | ||
368 | if (node.right == null) { | ||
369 | return -1; | ||
370 | } | ||
371 | |||
372 | rank += 1 + node.right.count; | ||
373 | node = node.right; | ||
374 | } else { | ||
375 | return rank; | ||
376 | } | ||
377 | } | ||
378 | } | ||
379 | |||
380 | @Override | ||
381 | public int size() { | ||
382 | return size; | ||
383 | } | ||
384 | |||
385 | @Override | ||
386 | public boolean isEmpty() { | ||
387 | return size == 0; | ||
388 | } | ||
389 | |||
390 | @Override | ||
391 | public void clear() { | ||
392 | modCount += size; | ||
393 | root = null; | ||
394 | size = 0; | ||
395 | } | ||
396 | |||
397 | |||
398 | private void checkIndex(int index) { | ||
399 | if (index < 0) { | ||
400 | throw new IndexOutOfBoundsException( | ||
401 | "The input index is negative: " + index); | ||
402 | } | ||
403 | |||
404 | if (index >= size) { | ||
405 | throw new IndexOutOfBoundsException( | ||
406 | "The input index is too large: " + index + | ||
407 | ", the size of this tree is " + size); | ||
408 | } | ||
409 | } | ||
410 | |||
411 | @SuppressWarnings("squid:S3776") | ||
412 | private Node<T> deleteNode(Node<T> node) { | ||
413 | if (node.left == null && node.right == null) { | ||
414 | // 'node' has no children. | ||
415 | Node<T> parent = node.parent; | ||
416 | |||
417 | if (parent == null) { | ||
418 | // 'node' is the root node of this tree. | ||
419 | root = null; | ||
420 | ++modCount; | ||
421 | return node; | ||
422 | } | ||
423 | |||
424 | Node<T> lo = node; | ||
425 | Node<T> hi = parent; | ||
426 | |||
427 | while (hi != null) { | ||
428 | if (hi.left == lo) { | ||
429 | hi.count--; | ||
430 | } | ||
431 | |||
432 | lo = hi; | ||
433 | hi = hi.parent; | ||
434 | } | ||
435 | |||
436 | if (node == parent.left) { | ||
437 | parent.left = null; | ||
438 | } else { | ||
439 | parent.right = null; | ||
440 | } | ||
441 | |||
442 | return node; | ||
443 | } | ||
444 | |||
445 | if (node.left != null && node.right != null) { | ||
446 | // 'node' has both children. | ||
447 | Node<T> successor = minimumNode(node.right); | ||
448 | node.key = successor.key; | ||
449 | Node<T> child = successor.right; | ||
450 | Node<T> parent = successor.parent; | ||
451 | |||
452 | if (parent.left == successor) { | ||
453 | parent.left = child; | ||
454 | } else { | ||
455 | parent.right = child; | ||
456 | } | ||
457 | |||
458 | if (child != null) { | ||
459 | child.parent = parent; | ||
460 | } | ||
461 | |||
462 | Node<T> lo = child; | ||
463 | Node<T> hi = parent; | ||
464 | |||
465 | while (hi != null) { | ||
466 | if (hi.left == lo) { | ||
467 | hi.count--; | ||
468 | } | ||
469 | |||
470 | lo = hi; | ||
471 | hi = hi.parent; | ||
472 | } | ||
473 | |||
474 | return successor; | ||
475 | } | ||
476 | |||
477 | Node<T> child; | ||
478 | |||
479 | // 'node' has only one child. | ||
480 | if (node.left != null) { | ||
481 | child = node.left; | ||
482 | } else { | ||
483 | child = node.right; | ||
484 | } | ||
485 | |||
486 | Node<T> parent = node.parent; | ||
487 | child.parent = parent; | ||
488 | |||
489 | if (parent == null) { | ||
490 | root = child; | ||
491 | return node; | ||
492 | } | ||
493 | |||
494 | if (node == parent.left) { | ||
495 | parent.left = child; | ||
496 | } else { | ||
497 | parent.right = child; | ||
498 | } | ||
499 | |||
500 | Node<T> hi = parent; | ||
501 | Node<T> lo = child; | ||
502 | |||
503 | while (hi != null) { | ||
504 | if (hi.left == lo) { | ||
505 | hi.count--; | ||
506 | } | ||
507 | |||
508 | lo = hi; | ||
509 | hi = hi.parent; | ||
510 | } | ||
511 | |||
512 | return node; | ||
513 | |||
514 | } | ||
515 | |||
516 | private Node<T> minimumNode(Node<T> node) { | ||
517 | while (node.left != null) { | ||
518 | node = node.left; | ||
519 | } | ||
520 | |||
521 | return node; | ||
522 | } | ||
523 | |||
524 | private int height(Node<T> node) { | ||
525 | return node == null ? -1 : node.height; | ||
526 | } | ||
527 | |||
528 | private Node<T> leftRotate(Node<T> node1) { | ||
529 | Node<T> node2 = node1.right; | ||
530 | node2.parent = node1.parent; | ||
531 | node1.parent = node2; | ||
532 | node1.right = node2.left; | ||
533 | node2.left = node1; | ||
534 | |||
535 | if (node1.right != null) { | ||
536 | node1.right.parent = node1; | ||
537 | } | ||
538 | |||
539 | node1.height = Math.max(height(node1.left), height(node1.right)) + 1; | ||
540 | node2.height = Math.max(height(node2.left), height(node2.right)) + 1; | ||
541 | node2.count += node1.count + 1; | ||
542 | return node2; | ||
543 | } | ||
544 | |||
545 | private Node<T> rightRotate(Node<T> node1) { | ||
546 | Node<T> node2 = node1.left; | ||
547 | node2.parent = node1.parent; | ||
548 | node1.parent = node2; | ||
549 | node1.left = node2.right; | ||
550 | node2.right = node1; | ||
551 | |||
552 | if (node1.left != null) { | ||
553 | node1.left.parent = node1; | ||
554 | } | ||
555 | |||
556 | node1.height = Math.max(height(node1.left), height(node1.right)) + 1; | ||
557 | node2.height = Math.max(height(node2.left), height(node2.right)) + 1; | ||
558 | node1.count -= node2.count + 1; | ||
559 | return node2; | ||
560 | } | ||
561 | |||
562 | private Node<T> rightLeftRotate(Node<T> node1) { | ||
563 | Node<T> node2 = node1.right; | ||
564 | node1.right = rightRotate(node2); | ||
565 | return leftRotate(node1); | ||
566 | } | ||
567 | |||
568 | private Node<T> leftRightRotate(Node<T> node1) { | ||
569 | Node<T> node2 = node1.left; | ||
570 | node1.left = leftRotate(node2); | ||
571 | return rightRotate(node1); | ||
572 | } | ||
573 | |||
574 | // Fixing an insertion: use insertionMode = true. | ||
575 | // Fixing a deletion: use insertionMode = false. | ||
576 | @SuppressWarnings("squid:S3776") | ||
577 | private void fixAfterModification(Node<T> node, boolean insertionMode) { | ||
578 | Node<T> parent = node.parent; | ||
579 | Node<T> grandParent; | ||
580 | Node<T> subTree; | ||
581 | |||
582 | while (parent != null) { | ||
583 | if (height(parent.left) == height(parent.right) + 2) { | ||
584 | grandParent = parent.parent; | ||
585 | |||
586 | if (height(parent.left.left) >= height(parent.left.right)) { | ||
587 | subTree = rightRotate(parent); | ||
588 | } else { | ||
589 | subTree = leftRightRotate(parent); | ||
590 | } | ||
591 | |||
592 | if (grandParent == null) { | ||
593 | root = subTree; | ||
594 | } else if (grandParent.left == parent) { | ||
595 | grandParent.left = subTree; | ||
596 | } else { | ||
597 | grandParent.right = subTree; | ||
598 | } | ||
599 | |||
600 | if (grandParent != null) { | ||
601 | grandParent.height = Math.max( | ||
602 | height(grandParent.left), | ||
603 | height(grandParent.right)) + 1; | ||
604 | } | ||
605 | |||
606 | if (insertionMode) { | ||
607 | // Whenever fixing after insertion, at most one rotation is | ||
608 | // required in order to maintain the balance. | ||
609 | return; | ||
610 | } | ||
611 | } else if (height(parent.right) == height(parent.left) + 2) { | ||
612 | grandParent = parent.parent; | ||
613 | |||
614 | if (height(parent.right.right) >= height(parent.right.left)) { | ||
615 | subTree = leftRotate(parent); | ||
616 | } else { | ||
617 | subTree = rightLeftRotate(parent); | ||
618 | } | ||
619 | |||
620 | if (grandParent == null) { | ||
621 | root = subTree; | ||
622 | } else if (grandParent.left == parent) { | ||
623 | grandParent.left = subTree; | ||
624 | } else { | ||
625 | grandParent.right = subTree; | ||
626 | } | ||
627 | |||
628 | if (grandParent != null) { | ||
629 | grandParent.height = | ||
630 | Math.max(height(grandParent.left), | ||
631 | height(grandParent.right)) + 1; | ||
632 | } | ||
633 | |||
634 | if (insertionMode) { | ||
635 | return; | ||
636 | } | ||
637 | } | ||
638 | |||
639 | parent.height = Math.max(height(parent.left), | ||
640 | height(parent.right)) + 1; | ||
641 | parent = parent.parent; | ||
642 | } | ||
643 | } | ||
644 | |||
645 | boolean isHealthy() { | ||
646 | if (root == null) { | ||
647 | return true; | ||
648 | } | ||
649 | |||
650 | return !containsCycles() | ||
651 | && heightsAreCorrect() | ||
652 | && isBalanced() | ||
653 | && isWellIndexed(); | ||
654 | } | ||
655 | |||
656 | private boolean containsCycles() { | ||
657 | Set<Node<T>> visitedNodes = new HashSet<>(); | ||
658 | return containsCycles(root, visitedNodes); | ||
659 | } | ||
660 | |||
661 | private boolean containsCycles(Node<T> current, Set<Node<T>> visitedNodes) { | ||
662 | if (current == null) { | ||
663 | return false; | ||
664 | } | ||
665 | |||
666 | if (visitedNodes.contains(current)) { | ||
667 | return true; | ||
668 | } | ||
669 | |||
670 | visitedNodes.add(current); | ||
671 | |||
672 | return containsCycles(current.left, visitedNodes) | ||
673 | || containsCycles(current.right, visitedNodes); | ||
674 | } | ||
675 | |||
676 | private boolean heightsAreCorrect() { | ||
677 | return getHeight(root) == root.height; | ||
678 | } | ||
679 | |||
680 | private int getHeight(Node<T> node) { | ||
681 | if (node == null) { | ||
682 | return -1; | ||
683 | } | ||
684 | |||
685 | int leftTreeHeight = getHeight(node.left); | ||
686 | |||
687 | if (leftTreeHeight == Integer.MIN_VALUE) { | ||
688 | return Integer.MIN_VALUE; | ||
689 | } | ||
690 | |||
691 | int rightTreeHeight = getHeight(node.right); | ||
692 | |||
693 | if (rightTreeHeight == Integer.MIN_VALUE) { | ||
694 | return Integer.MIN_VALUE; | ||
695 | } | ||
696 | |||
697 | if (node.height == Math.max(leftTreeHeight, rightTreeHeight) + 1) { | ||
698 | return node.height; | ||
699 | } | ||
700 | |||
701 | return Integer.MIN_VALUE; | ||
702 | } | ||
703 | |||
704 | private boolean isBalanced() { | ||
705 | return isBalanced(root); | ||
706 | } | ||
707 | |||
708 | private boolean isBalanced(Node<T> node) { | ||
709 | if (node == null) { | ||
710 | return true; | ||
711 | } | ||
712 | |||
713 | if (!isBalanced(node.left)) { | ||
714 | return false; | ||
715 | } | ||
716 | |||
717 | if (!isBalanced(node.right)) { | ||
718 | return false; | ||
719 | } | ||
720 | |||
721 | int leftHeight = height(node.left); | ||
722 | int rightHeight = height(node.right); | ||
723 | |||
724 | return Math.abs(leftHeight - rightHeight) < 2; | ||
725 | } | ||
726 | |||
727 | private boolean isWellIndexed() { | ||
728 | return size == count(root); | ||
729 | } | ||
730 | |||
731 | private int count(Node<T> node) { | ||
732 | if (node == null) { | ||
733 | return 0; | ||
734 | } | ||
735 | |||
736 | int leftTreeSize = count(node.left); | ||
737 | |||
738 | if (leftTreeSize == Integer.MIN_VALUE) { | ||
739 | return Integer.MIN_VALUE; | ||
740 | } | ||
741 | |||
742 | if (node.count != leftTreeSize) { | ||
743 | return Integer.MIN_VALUE; | ||
744 | } | ||
745 | |||
746 | int rightTreeSize = count(node.right); | ||
747 | |||
748 | if (rightTreeSize == Integer.MIN_VALUE) { | ||
749 | return Integer.MIN_VALUE; | ||
750 | } | ||
751 | |||
752 | return leftTreeSize + 1 + rightTreeSize; | ||
753 | } | ||
754 | } | ||
diff --git a/subprojects/store-query/src/test/java/tools/refinery/store/query/utils/OrderStatisticTreeTest.java b/subprojects/store-query/src/test/java/tools/refinery/store/query/utils/OrderStatisticTreeTest.java new file mode 100644 index 00000000..cbb48603 --- /dev/null +++ b/subprojects/store-query/src/test/java/tools/refinery/store/query/utils/OrderStatisticTreeTest.java | |||
@@ -0,0 +1,634 @@ | |||
1 | /* | ||
2 | * Copyright (c) 2021 Rodion Efremov | ||
3 | * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/> | ||
4 | * | ||
5 | * SPDX-License-Identifier: MIT OR EPL-2.0 | ||
6 | */ | ||
7 | package tools.refinery.store.query.utils; | ||
8 | |||
9 | import org.junit.jupiter.api.BeforeEach; | ||
10 | import org.junit.jupiter.api.Test; | ||
11 | import org.junit.jupiter.params.ParameterizedTest; | ||
12 | import org.junit.jupiter.params.provider.Arguments; | ||
13 | import org.junit.jupiter.params.provider.MethodSource; | ||
14 | |||
15 | import java.util.*; | ||
16 | import java.util.stream.Stream; | ||
17 | |||
18 | import static org.junit.jupiter.api.Assertions.*; | ||
19 | |||
20 | /** | ||
21 | * Tests for an order statistic tree which is based on AVL-trees. | ||
22 | * <p> | ||
23 | * This class was copied into <i>Refinery</i> from | ||
24 | * <a href="https://github.com/coderodde/OrderStatisticTree/tree/546c343b9f5d868e394a079ff32691c9dbfd83e3">https://github.com/coderodde/OrderStatisticTree</a> | ||
25 | * and is available under the | ||
26 | * <a href="https://github.com/coderodde/OrderStatisticTree/blob/master/LICENSE">MIT License</a>. | ||
27 | * We also migrated the code to Junit 5, cleaned up some linter warnings, and made the tests deterministic by fixing | ||
28 | * the random seeds. | ||
29 | * | ||
30 | * @author Rodion "rodde" Efremov | ||
31 | * @version based on 1.6 (Feb 11, 2016) | ||
32 | */ | ||
33 | class OrderStatisticTreeTest { | ||
34 | private final OrderStatisticTree<Integer> tree = new OrderStatisticTree<>(); | ||
35 | |||
36 | private final TreeSet<Integer> set = new TreeSet<>(); | ||
37 | |||
38 | @BeforeEach | ||
39 | void before() { | ||
40 | tree.clear(); | ||
41 | set.clear(); | ||
42 | } | ||
43 | |||
44 | @Test | ||
45 | void testAdd() { | ||
46 | assertEquals(set.isEmpty(), tree.isEmpty()); | ||
47 | |||
48 | for (int i = 10; i < 30; i += 2) { | ||
49 | assertTrue(tree.isHealthy()); | ||
50 | assertEquals(set.contains(i), tree.contains(i)); | ||
51 | assertEquals(set.add(i), tree.add(i)); | ||
52 | assertEquals(set.add(i), tree.add(i)); | ||
53 | assertEquals(set.contains(i), tree.contains(i)); | ||
54 | assertTrue(tree.isHealthy()); | ||
55 | } | ||
56 | |||
57 | assertEquals(set.isEmpty(), tree.isEmpty()); | ||
58 | } | ||
59 | |||
60 | @Test | ||
61 | void testAddAll() { | ||
62 | for (int i = 0; i < 10; ++i) { | ||
63 | assertEquals(set.add(i), tree.add(i)); | ||
64 | } | ||
65 | |||
66 | Collection<Integer> coll = Arrays.asList(10, 9, 7, 11, 12); | ||
67 | |||
68 | assertEquals(set.addAll(coll), tree.addAll(coll)); | ||
69 | assertEquals(set.size(), tree.size()); | ||
70 | |||
71 | for (int i = -10; i < 20; ++i) { | ||
72 | assertEquals(set.contains(i), tree.contains(i)); | ||
73 | } | ||
74 | } | ||
75 | |||
76 | @Test | ||
77 | void testClear() { | ||
78 | for (int i = 0; i < 2000; ++i) { | ||
79 | set.add(i); | ||
80 | tree.add(i); | ||
81 | } | ||
82 | |||
83 | assertEquals(set.size(), tree.size()); | ||
84 | set.clear(); | ||
85 | tree.clear(); | ||
86 | // We expect {@code tree.size()} to always be 0, but we also test for it. | ||
87 | //noinspection ConstantValue | ||
88 | assertEquals(0, tree.size()); | ||
89 | } | ||
90 | |||
91 | @Test | ||
92 | void testContains() { | ||
93 | for (int i = 100; i < 200; i += 3) { | ||
94 | assertTrue(tree.isHealthy()); | ||
95 | assertEquals(set.add(i), tree.add(i)); | ||
96 | assertTrue(tree.isHealthy()); | ||
97 | } | ||
98 | |||
99 | assertEquals(set.size(), tree.size()); | ||
100 | |||
101 | for (int i = 0; i < 300; ++i) { | ||
102 | assertEquals(set.contains(i), tree.contains(i)); | ||
103 | } | ||
104 | } | ||
105 | |||
106 | @Test | ||
107 | void testContainsAll() { | ||
108 | for (int i = 0; i < 50; ++i) { | ||
109 | set.add(i); | ||
110 | tree.add(i); | ||
111 | } | ||
112 | |||
113 | Collection<Integer> coll = new HashSet<>(); | ||
114 | |||
115 | for (int i = 10; i < 20; ++i) { | ||
116 | coll.add(i); | ||
117 | } | ||
118 | |||
119 | assertEquals(set.containsAll(coll), tree.containsAll(coll)); | ||
120 | coll.add(100); | ||
121 | assertEquals(set.containsAll(coll), tree.containsAll(coll)); | ||
122 | } | ||
123 | |||
124 | @Test | ||
125 | void testRemove() { | ||
126 | for (int i = 0; i < 200; ++i) { | ||
127 | assertEquals(set.add(i), tree.add(i)); | ||
128 | } | ||
129 | |||
130 | for (int i = 50; i < 150; i += 2) { | ||
131 | assertEquals(set.remove(i), tree.remove(i)); | ||
132 | assertTrue(tree.isHealthy()); | ||
133 | } | ||
134 | |||
135 | for (int i = -100; i < 300; ++i) { | ||
136 | assertEquals(set.contains(i), tree.contains(i)); | ||
137 | } | ||
138 | } | ||
139 | |||
140 | @Test | ||
141 | void testRemoveLast() { | ||
142 | tree.add(1); | ||
143 | tree.remove(1); | ||
144 | assertEquals(0, tree.size()); | ||
145 | } | ||
146 | |||
147 | @Test | ||
148 | void testRemoveAll() { | ||
149 | for (int i = 0; i < 40; ++i) { | ||
150 | set.add(i); | ||
151 | tree.add(i); | ||
152 | } | ||
153 | |||
154 | Collection<Integer> coll = new HashSet<>(); | ||
155 | |||
156 | for (int i = 10; i < 20; ++i) { | ||
157 | coll.add(i); | ||
158 | } | ||
159 | |||
160 | assertEquals(set.removeAll(coll), tree.removeAll(coll)); | ||
161 | |||
162 | for (int i = -10; i < 50; ++i) { | ||
163 | assertEquals(set.contains(i), tree.contains(i)); | ||
164 | } | ||
165 | |||
166 | assertEquals(set.removeAll(coll), tree.removeAll(coll)); | ||
167 | |||
168 | for (int i = -10; i < 50; ++i) { | ||
169 | assertEquals(set.contains(i), tree.contains(i)); | ||
170 | } | ||
171 | } | ||
172 | |||
173 | @Test | ||
174 | void testSize() { | ||
175 | for (int i = 0; i < 200; ++i) { | ||
176 | assertEquals(set.size(), tree.size()); | ||
177 | assertEquals(set.add(i), tree.add(i)); | ||
178 | assertEquals(set.size(), tree.size()); | ||
179 | } | ||
180 | } | ||
181 | |||
182 | @Test | ||
183 | void testIndexOf() { | ||
184 | for (int i = 0; i < 100; ++i) { | ||
185 | assertTrue(tree.add(i * 2)); | ||
186 | } | ||
187 | |||
188 | for (int i = 0; i < 100; ++i) { | ||
189 | assertEquals(i, tree.indexOf(2 * i)); | ||
190 | } | ||
191 | |||
192 | for (int i = 100; i < 150; ++i) { | ||
193 | assertEquals(-1, tree.indexOf(2 * i)); | ||
194 | } | ||
195 | } | ||
196 | |||
197 | @Test | ||
198 | void testEmpty() { | ||
199 | assertEquals(set.isEmpty(), tree.isEmpty()); | ||
200 | set.add(0); | ||
201 | tree.add(0); | ||
202 | assertEquals(set.isEmpty(), tree.isEmpty()); | ||
203 | } | ||
204 | |||
205 | @Test | ||
206 | void testEmptyTreeGetThrowsOnNegativeIndex() { | ||
207 | assertThrows(IndexOutOfBoundsException.class, () -> tree.get(-1)); | ||
208 | } | ||
209 | |||
210 | @Test | ||
211 | void testEmptyTreeSelectThrowsOnTooLargeIndex() { | ||
212 | assertThrows(IndexOutOfBoundsException.class, () -> tree.get(0)); | ||
213 | } | ||
214 | |||
215 | @Test | ||
216 | void testSelectThrowsOnNegativeIndex() { | ||
217 | for (int i = 0; i < 5; ++i) { | ||
218 | tree.add(i); | ||
219 | } | ||
220 | |||
221 | assertThrows(IndexOutOfBoundsException.class, () -> tree.get(-1)); | ||
222 | } | ||
223 | |||
224 | @Test | ||
225 | void testSelectThrowsOnTooLargeIndex() { | ||
226 | for (int i = 0; i < 5; ++i) { | ||
227 | tree.add(i); | ||
228 | } | ||
229 | |||
230 | assertThrows(IndexOutOfBoundsException.class, () -> tree.get(5)); | ||
231 | } | ||
232 | |||
233 | @Test | ||
234 | void testGet() { | ||
235 | for (int i = 0; i < 100; i += 3) { | ||
236 | tree.add(i); | ||
237 | } | ||
238 | |||
239 | for (int i = 0; i < tree.size(); ++i) { | ||
240 | assertEquals(Integer.valueOf(3 * i), tree.get(i)); | ||
241 | } | ||
242 | } | ||
243 | |||
244 | @Test | ||
245 | void findBug() { | ||
246 | tree.add(0); | ||
247 | assertTrue(tree.isHealthy()); | ||
248 | |||
249 | tree.add(-1); | ||
250 | tree.remove(-1); | ||
251 | assertTrue(tree.isHealthy()); | ||
252 | |||
253 | tree.add(1); | ||
254 | tree.remove(1); | ||
255 | assertTrue(tree.isHealthy()); | ||
256 | |||
257 | tree.add(-1); | ||
258 | tree.add(1); | ||
259 | tree.remove(0); | ||
260 | assertTrue(tree.isHealthy()); | ||
261 | |||
262 | tree.clear(); | ||
263 | tree.add(0); | ||
264 | tree.add(-1); | ||
265 | tree.add(10); | ||
266 | tree.add(5); | ||
267 | tree.add(15); | ||
268 | tree.add(11); | ||
269 | tree.add(30); | ||
270 | tree.add(7); | ||
271 | |||
272 | tree.remove(-1); | ||
273 | |||
274 | assertTrue(tree.isHealthy()); | ||
275 | } | ||
276 | |||
277 | @ParameterizedTest(name = "seed = {0}") | ||
278 | @MethodSource("seedSource") | ||
279 | void tryReproduceTheCounterBug(long seed) { | ||
280 | Random random = new Random(seed); | ||
281 | List<Integer> list = new ArrayList<>(); | ||
282 | |||
283 | for (int i = 0; i < 10; ++i) { | ||
284 | int number = random.nextInt(1000); | ||
285 | list.add(number); | ||
286 | tree.add(number); | ||
287 | assertTrue(tree.isHealthy()); | ||
288 | } | ||
289 | |||
290 | for (Integer i : list) { | ||
291 | tree.remove(i); | ||
292 | boolean healthy = tree.isHealthy(); | ||
293 | assertTrue(healthy); | ||
294 | } | ||
295 | } | ||
296 | |||
297 | @Test | ||
298 | void testEmptyIterator() { | ||
299 | var iterator = tree.iterator(); | ||
300 | assertThrows(NoSuchElementException.class, iterator::next); | ||
301 | } | ||
302 | |||
303 | @Test | ||
304 | void testIteratorThrowsOnDoubleRemove() { | ||
305 | for (int i = 10; i < 20; ++i) { | ||
306 | set.add(i); | ||
307 | tree.add(i); | ||
308 | } | ||
309 | |||
310 | Iterator<Integer> iterator1 = set.iterator(); | ||
311 | Iterator<Integer> iterator2 = tree.iterator(); | ||
312 | |||
313 | for (int i = 0; i < 3; ++i) { | ||
314 | assertEquals(iterator1.next(), iterator2.next()); | ||
315 | } | ||
316 | |||
317 | iterator1.remove(); | ||
318 | iterator2.remove(); | ||
319 | |||
320 | assertThrows(IllegalStateException.class, iterator1::remove); | ||
321 | assertThrows(IllegalStateException.class, iterator2::remove); | ||
322 | } | ||
323 | |||
324 | @Test | ||
325 | void testIterator() { | ||
326 | for (int i = 0; i < 5; ++i) { | ||
327 | tree.add(i); | ||
328 | set.add(i); | ||
329 | } | ||
330 | |||
331 | Iterator<Integer> iterator1 = set.iterator(); | ||
332 | Iterator<Integer> iterator2 = tree.iterator(); | ||
333 | |||
334 | for (int i = 0; i < 5; ++i) { | ||
335 | assertEquals(iterator1.hasNext(), iterator2.hasNext()); | ||
336 | assertEquals(iterator1.next(), iterator2.next()); | ||
337 | } | ||
338 | |||
339 | assertEquals(iterator1.hasNext(), iterator2.hasNext()); | ||
340 | |||
341 | assertThrows(NoSuchElementException.class, iterator1::next); | ||
342 | assertThrows(NoSuchElementException.class, iterator2::next); | ||
343 | } | ||
344 | |||
345 | @Test | ||
346 | void testRemoveBeforeNextThrowsEmpty() { | ||
347 | var setIterator = set.iterator(); | ||
348 | assertThrows(IllegalStateException.class, setIterator::remove); | ||
349 | |||
350 | var treeIterator = tree.iterator(); | ||
351 | assertThrows(IllegalStateException.class, treeIterator::remove); | ||
352 | } | ||
353 | |||
354 | @Test | ||
355 | void testRemoveThrowsWithoutNext() { | ||
356 | for (int i = 0; i < 10; ++i) { | ||
357 | tree.add(i); | ||
358 | set.add(i); | ||
359 | } | ||
360 | |||
361 | Iterator<Integer> iterator1 = set.iterator(); | ||
362 | Iterator<Integer> iterator2 = tree.iterator(); | ||
363 | |||
364 | for (int i = 0; i < 4; ++i) { | ||
365 | assertEquals(iterator1.hasNext(), iterator2.hasNext()); | ||
366 | assertEquals(iterator1.next(), iterator2.next()); | ||
367 | } | ||
368 | |||
369 | iterator1.remove(); | ||
370 | iterator2.remove(); | ||
371 | |||
372 | assertThrows(IllegalStateException.class, iterator1::remove); | ||
373 | assertThrows(IllegalStateException.class, iterator2::remove); | ||
374 | } | ||
375 | |||
376 | @Test | ||
377 | void testRetainAll() { | ||
378 | for (int i = 0; i < 100; ++i) { | ||
379 | set.add(i); | ||
380 | tree.add(i); | ||
381 | } | ||
382 | |||
383 | Collection<Integer> coll = Arrays.asList(26, 29, 25); | ||
384 | |||
385 | assertEquals(set.retainAll(coll), tree.retainAll(coll)); | ||
386 | assertEquals(set.size(), tree.size()); | ||
387 | |||
388 | assertTrue(set.containsAll(tree)); | ||
389 | assertTrue(tree.containsAll(set)); | ||
390 | } | ||
391 | |||
392 | @Test | ||
393 | void testIteratorRemove() { | ||
394 | for (int i = 10; i < 16; ++i) { | ||
395 | assertEquals(set.add(i), tree.add(i)); | ||
396 | } | ||
397 | |||
398 | Iterator<Integer> iterator1 = set.iterator(); | ||
399 | Iterator<Integer> iterator2 = tree.iterator(); | ||
400 | |||
401 | assertEquals(iterator1.hasNext(), iterator2.hasNext()); | ||
402 | assertEquals(iterator1.next(), iterator2.next()); | ||
403 | |||
404 | assertEquals(iterator1.hasNext(), iterator2.hasNext()); | ||
405 | assertEquals(iterator1.next(), iterator2.next()); | ||
406 | |||
407 | iterator1.remove(); // remove 11 | ||
408 | iterator2.remove(); | ||
409 | |||
410 | assertEquals(iterator1.hasNext(), iterator2.hasNext()); | ||
411 | assertEquals(iterator1.next(), iterator2.next()); | ||
412 | |||
413 | assertEquals(iterator1.hasNext(), iterator2.hasNext()); | ||
414 | assertEquals(iterator1.next(), iterator2.next()); | ||
415 | |||
416 | iterator1.remove(); // remove 13 | ||
417 | iterator2.remove(); | ||
418 | |||
419 | assertEquals(set.size(), tree.size()); | ||
420 | |||
421 | for (int i = 10; i < 16; ++i) { | ||
422 | assertEquals(set.contains(i), tree.contains(i)); | ||
423 | } | ||
424 | } | ||
425 | |||
426 | @ParameterizedTest(name = "seed = {0}") | ||
427 | @MethodSource("seedSource") | ||
428 | void testIteratorBruteForce(long seed) { | ||
429 | for (int i = 0; i < 1000; ++i) { | ||
430 | assertEquals(set.add(i), tree.add(i)); | ||
431 | } | ||
432 | |||
433 | Iterator<Integer> iterator1 = set.iterator(); | ||
434 | Iterator<Integer> iterator2 = tree.iterator(); | ||
435 | |||
436 | Random random = new Random(seed); | ||
437 | |||
438 | while (true) { | ||
439 | if (!iterator1.hasNext()) { | ||
440 | assertFalse(iterator2.hasNext()); | ||
441 | break; | ||
442 | } | ||
443 | |||
444 | boolean toRemove = random.nextBoolean(); | ||
445 | |||
446 | if (toRemove) { | ||
447 | boolean thrown = false; | ||
448 | |||
449 | try { | ||
450 | iterator1.remove(); | ||
451 | } catch (IllegalStateException ex) { | ||
452 | thrown = true; | ||
453 | } | ||
454 | |||
455 | if (thrown) { | ||
456 | assertThrows(IllegalStateException.class, iterator2::remove); | ||
457 | } else { | ||
458 | iterator2.remove(); | ||
459 | } | ||
460 | } else { | ||
461 | assertEquals(iterator1.hasNext(), iterator2.hasNext()); | ||
462 | |||
463 | if (iterator1.hasNext()) { | ||
464 | assertEquals(iterator1.next(), iterator2.next()); | ||
465 | } else { | ||
466 | break; | ||
467 | } | ||
468 | } | ||
469 | } | ||
470 | |||
471 | assertEquals(set.size(), tree.size()); | ||
472 | assertTrue(tree.isHealthy()); | ||
473 | assertTrue(set.containsAll(tree)); | ||
474 | assertTrue(tree.containsAll(set)); | ||
475 | } | ||
476 | |||
477 | @Test | ||
478 | void testIteratorConcurrentModification() { | ||
479 | for (int i = 0; i < 100; ++i) { | ||
480 | set.add(i); | ||
481 | tree.add(i); | ||
482 | } | ||
483 | |||
484 | Iterator<Integer> iterator1 = set.iterator(); | ||
485 | Iterator<Integer> iterator2 = tree.iterator(); | ||
486 | |||
487 | set.remove(10); | ||
488 | tree.remove(10); | ||
489 | |||
490 | assertEquals(iterator1.hasNext(), iterator2.hasNext()); | ||
491 | |||
492 | boolean thrown = false; | ||
493 | |||
494 | try { | ||
495 | iterator1.next(); | ||
496 | } catch (ConcurrentModificationException ex) { | ||
497 | thrown = true; | ||
498 | } | ||
499 | |||
500 | if (thrown) { | ||
501 | assertThrows(ConcurrentModificationException.class, iterator2::next); | ||
502 | } else { | ||
503 | iterator2.next(); | ||
504 | } | ||
505 | } | ||
506 | |||
507 | @Test | ||
508 | void testIteratorConcurrentRemove() { | ||
509 | for (int i = 10; i < 20; ++i) { | ||
510 | set.add(i); | ||
511 | tree.add(i); | ||
512 | } | ||
513 | |||
514 | Iterator<Integer> iterator1 = set.iterator(); | ||
515 | Iterator<Integer> iterator2 = tree.iterator(); | ||
516 | |||
517 | for (int i = 0; i < 4; ++i) { | ||
518 | iterator1.next(); | ||
519 | iterator2.next(); | ||
520 | } | ||
521 | |||
522 | // None of them contains 2, should not change the modification count. | ||
523 | set.remove(2); | ||
524 | tree.remove(2); | ||
525 | |||
526 | iterator1.remove(); | ||
527 | iterator2.remove(); | ||
528 | |||
529 | iterator1.next(); | ||
530 | iterator2.next(); | ||
531 | |||
532 | set.remove(12); | ||
533 | tree.remove(12); | ||
534 | |||
535 | // Both of them should throw. | ||
536 | assertThrows(ConcurrentModificationException.class, iterator1::remove); | ||
537 | assertThrows(ConcurrentModificationException.class, iterator2::remove); | ||
538 | } | ||
539 | |||
540 | @Test | ||
541 | void testConcurrentOrIllegalStateOnRemove() { | ||
542 | for (int i = 0; i < 10; ++i) { | ||
543 | set.add(i); | ||
544 | tree.add(i); | ||
545 | } | ||
546 | |||
547 | Iterator<Integer> iterator1 = set.iterator(); | ||
548 | Iterator<Integer> iterator2 = tree.iterator(); | ||
549 | |||
550 | set.add(100); | ||
551 | tree.add(100); | ||
552 | |||
553 | assertThrows(IllegalStateException.class, iterator1::remove); | ||
554 | assertThrows(IllegalStateException.class, iterator2::remove); | ||
555 | } | ||
556 | |||
557 | @Test | ||
558 | void testConcurrentIterators() { | ||
559 | for (int i = 0; i < 10; ++i) { | ||
560 | set.add(i); | ||
561 | tree.add(i); | ||
562 | } | ||
563 | |||
564 | Iterator<Integer> iterator1a = set.iterator(); | ||
565 | Iterator<Integer> iterator1b = set.iterator(); | ||
566 | Iterator<Integer> iterator2a = tree.iterator(); | ||
567 | Iterator<Integer> iterator2b = tree.iterator(); | ||
568 | |||
569 | for (int i = 0; i < 3; ++i) { | ||
570 | iterator1a.next(); | ||
571 | iterator2a.next(); | ||
572 | } | ||
573 | |||
574 | iterator1a.remove(); | ||
575 | iterator2a.remove(); | ||
576 | |||
577 | assertEquals(iterator1b.hasNext(), iterator2b.hasNext()); | ||
578 | |||
579 | assertThrows(ConcurrentModificationException.class, iterator1b::next); | ||
580 | assertThrows(ConcurrentModificationException.class, iterator2b::next); | ||
581 | } | ||
582 | |||
583 | @ParameterizedTest(name = "seed = {0}") | ||
584 | @MethodSource("seedSource") | ||
585 | void testToArray(long seed) { | ||
586 | Random r = new Random(seed); | ||
587 | |||
588 | for (int i = 0; i < 50; ++i) { | ||
589 | int num = r.nextInt(); | ||
590 | set.add(num); | ||
591 | tree.add(num); | ||
592 | } | ||
593 | |||
594 | assertArrayEquals(set.toArray(), tree.toArray()); | ||
595 | } | ||
596 | |||
597 | @Test | ||
598 | void testToArrayGeneric() { | ||
599 | for (int i = 0; i < 100; ++i) { | ||
600 | set.add(i); | ||
601 | tree.add(i); | ||
602 | } | ||
603 | |||
604 | Integer[] array1before = new Integer[99]; | ||
605 | Integer[] array2before = new Integer[99]; | ||
606 | |||
607 | Integer[] array1after = set.toArray(array1before); | ||
608 | Integer[] array2after = tree.toArray(array2before); | ||
609 | |||
610 | assertNotSame(array1before, array1after); | ||
611 | assertNotSame(array2before, array2after); | ||
612 | assertArrayEquals(array1after, array2after); | ||
613 | |||
614 | set.remove(1); | ||
615 | tree.remove(1); | ||
616 | |||
617 | array1after = set.toArray(array1before); | ||
618 | array2after = tree.toArray(array2before); | ||
619 | |||
620 | assertSame(array1before, array1after); | ||
621 | assertSame(array2before, array2after); | ||
622 | assertArrayEquals(array1after, array2after); | ||
623 | } | ||
624 | |||
625 | static Stream<Arguments> seedSource() { | ||
626 | return Stream.of( | ||
627 | Arguments.of(0L), | ||
628 | Arguments.of(1L), | ||
629 | Arguments.of(2L), | ||
630 | Arguments.of(3L), | ||
631 | Arguments.of(4L) | ||
632 | ); | ||
633 | } | ||
634 | } | ||