#677

Committed 02 Nov 2024 08:50AM UTC coverage: 99.673%. Remained the same

Build # #677

Build Type

push

Committed by

Commit Message

Optimize imports

Run Details

5786 of 5805 relevant lines covered (99.67%)

1.0 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.6

/src/main/java/one/util/streamex/CollapseSpliterator.java

/*
 * Copyright 2015, 2024 StreamEx contributors
 *
 * 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.
 */
package one.util.streamex;

import java.util.Spliterator;
import java.util.function.*;

import static one.util.streamex.Internals.*;

/* package */final class CollapseSpliterator<T, R> extends Box<T> implements Spliterator<R> {
    private final Spliterator<T> source;
    private final CollapseSpliterator<T, R> root; // used as lock
    private R acc;
    volatile Connector<T, R> left;
    volatile Connector<T, R> right;
    private final Function<T, R> mapper;
    private final BiFunction<R, T, R> accumulator;
    private final BinaryOperator<R> combiner;
    private final BiPredicate<? super T, ? super T> mergeable;

    private static final class Connector<T, R> {
        CollapseSpliterator<T, R> lhs, rhs;
        T left = none(), right = none();
        R acc;

        Connector(CollapseSpliterator<T, R> lhs, R acc, CollapseSpliterator<T, R> rhs) {
            this.lhs = lhs;
            this.rhs = rhs;
            this.acc = acc;
        }

        R drain() {
            if (lhs != null)
                lhs.right = null;
            if (rhs != null)
                rhs.left = null;
            return acc;
        }

        R drainLeft() {
            return left == NONE ? drain() : none();
        }

        R drainRight() {
            return right == NONE ? drain() : none();
        }
    }

    CollapseSpliterator(BiPredicate<? super T, ? super T> mergeable, Function<T, R> mapper,
            BiFunction<R, T, R> accumulator, BinaryOperator<R> combiner, Spliterator<T> source) {
        super(none());
        this.source = source;
        this.mergeable = mergeable;
        this.mapper = mapper;
        this.accumulator = accumulator;
        this.combiner = combiner;
        this.root = this;
    }

    private CollapseSpliterator(CollapseSpliterator<T, R> root, Spliterator<T> source, Connector<T, R> left,
            Connector<T, R> right) {
        super(none());
        this.source = source;
        this.root = root;
        this.mergeable = root.mergeable;
        this.mapper = root.mapper;
        this.accumulator = root.accumulator;
        this.combiner = root.combiner;
        this.left = left;
        this.right = right;
        if (left != null)
            left.rhs = this;
        right.lhs = this;
    }

    @Override
    public boolean tryAdvance(Consumer<? super R> action) {
        if (left != null) {
            if (accept(handleLeft(), action)) {
                return true;
            }
        }
        if (a == NONE) { // start
            if (!source.tryAdvance(this)) {
                return accept(pushRight(none(), none()), action);
            }
        }
        T first = a;
        R acc = mapper.apply(a);
        T last = first;
        while (source.tryAdvance(this)) {
            if (!this.mergeable.test(last, a)) {
                action.accept(acc);
                return true;
            }
            last = a;
            acc = this.accumulator.apply(acc, last);
        }
        return accept(pushRight(acc, last), action);
    }

    @Override
    public void forEachRemaining(Consumer<? super R> action) {
        while (left != null) {
            accept(handleLeft(), action);
        }
        if (a != NONE) {
            acc = mapper.apply(a);
        }
        source.forEachRemaining(next -> {
            if (a == NONE) {
                acc = mapper.apply(next);
            } else if (!this.mergeable.test(a, next)) {
                action.accept(acc);
                acc = mapper.apply(next);
            } else {
                acc = accumulator.apply(acc, next);
            }
            a = next;
        });
        if (a == NONE) {
            accept(pushRight(none(), none()), action);
        } else if (accept(pushRight(acc, a), action)) {
            if (right != null) {
                action.accept(right.acc);
                right = null;
            }
        }
    }

    private boolean accept(R acc, Consumer<? super R> action) {
        if (acc != NONE) {
            action.accept(acc);
            return true;
        }
        return false;
    }

    private R handleLeft() {
        synchronized (root) {
            Connector<T, R> l = left;
            if (l == null) {
                return none();
            }
            if (l.left == NONE && l.right == NONE && l.acc != NONE) {
                return l.drain();
            }
        }
        if (source.tryAdvance(this)) {
            T first = this.a;
            T last = first;
            R acc = this.mapper.apply(first);
            while (source.tryAdvance(this)) {
                if (!this.mergeable.test(last, a))
                    return pushLeft(first, acc);
                last = a;
                acc = this.accumulator.apply(acc, last);
            }
            a = none();
            return connectOne(first, acc, last);
        }
        return connectEmpty();
    }

    // l + <first|acc|?>
    private R pushLeft(T first, R acc) {
        synchronized (root) {
            Connector<T, R> l = left;
            if (l == null)
                return acc;
            left = null;
            l.rhs = null;
            T laright = l.right;
            l.right = none();
            if (l.acc == NONE) {
                l.acc = acc;
                l.left = first;
                return none();
            }
            if (this.mergeable.test(laright, first)) {
                l.acc = this.combiner.apply(l.acc, acc);
                return l.drainLeft();
            }
            if (l.left == NONE) {
                left = new Connector<>(null, acc, this);
                return l.drain();
            }
        }
        return acc;
    }

    // <?|acc|last> + r
    private R pushRight(R acc, T last) {
        a = none();
        if (right == null)
            return acc;
        synchronized (root) {
            Connector<T, R> r = right;
            if (r == null)
                return acc;
            right = null;
            r.lhs = null;
            T raleft = r.left;
            r.left = none();
            if (r.acc == NONE) {
                if (acc == NONE) {
                    r.drain();
                } else {
                    r.acc = acc;
                    r.right = last;
                }
                return none();
            }
            if (acc == NONE) {
                return r.drainRight();
            }
            if (mergeable.test(last, raleft)) {
                r.acc = combiner.apply(acc, r.acc);
                return r.drainRight();
            }
            if (r.right == NONE)
                right = new Connector<>(this, r.drain(), null);
            return acc;
        }
    }

    // l + <first|acc|last> + r
    private R connectOne(T first, R acc, T last) {
        synchronized (root) {
            Connector<T, R> l = left;
            if (l == null) {
                return pushRight(acc, last);
            }
            if (l.acc == NONE) {
                l.acc = acc;
                l.left = first;
                l.right = last;
                return connectEmpty();
            }
            T laright = l.right;
            if (mergeable.test(laright, first)) {
                l.acc = combiner.apply(l.acc, acc);
                l.right = last;
                return connectEmpty();
            }
            left = null;
            l.rhs = null;
            l.right = none();
            if (l.left != NONE) {
                return pushRight(acc, last);
            }
            acc = pushRight(acc, last);
            if (acc != NONE)
                left = new Connector<>(null, acc, this);
            return l.drain();
        }
    }

    // l + r
    private R connectEmpty() {
        synchronized (root) {
            Connector<T, R> l = left, r = right;
            if (l == null) {
                return pushRight(none(), none());
            }
            left = right = null;
            l.rhs = null;
            T laright = l.right;
            l.right = none();
            if (l.acc == NONE) {
                if (r == null)
                    l.drain();
                else {
                    if (l.lhs != null) {
                        l.lhs.right = r;
                        r.lhs = l.lhs;
                    }
                }
                return none();
            }
            if (r == null) {
                return l.drainLeft();
            }
            r.lhs = null;
            if (r.acc == NONE) {
                if (r.rhs != null) {
                    r.rhs.left = l;
                    l.rhs = r.rhs;
                    l.right = laright;
                }
                return none();
            }
            T raleft = r.left;
            r.left = none();
            if (mergeable.test(laright, raleft)) {
                R acc = combiner.apply(l.acc, r.acc);
                if (l.left == NONE && r.right == NONE) {
                    l.drain();
                    r.drain();
                    return acc;
                }
                l.acc = acc;
                l.right = r.right;
                if (r.rhs != null) {
                    r.rhs.left = l;
                    l.rhs = r.rhs;
                }
                return none();
            }
            if (l.left == NONE) {
                if (r.right == NONE)
                    right = new Connector<>(this, r.drain(), null);
                return l.drain();
            }
            return r.drainRight();
        }
    }

    @Override
    public Spliterator<R> trySplit() {
        Spliterator<T> prefix = source.trySplit();
        if (prefix == null)
            return null;
        Connector<T, R> newBox = new Connector<>(null, none(), this);
        synchronized (root) {
            CollapseSpliterator<T, R> result = new CollapseSpliterator<>(root, prefix, left, newBox);
            this.left = newBox;
            return result;
        }
    }

    @Override
    public long estimateSize() {
        return source.estimateSize();
    }

    @Override
    public int characteristics() {
        return source.characteristics() & (CONCURRENT | IMMUTABLE | ORDERED);
    }
}

1	/*
2	* Copyright 2015, 2024 StreamEx contributors
3	*
4	* Licensed under the Apache License, Version 2.0 (the "License");
5	* you may not use this file except in compliance with the License.
6	* You may obtain a copy of the License at
7	*
8	* http://www.apache.org/licenses/LICENSE-2.0
9	*
10	* Unless required by applicable law or agreed to in writing, software
11	* distributed under the License is distributed on an "AS IS" BASIS,
12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	* See the License for the specific language governing permissions and
14	* limitations under the License.
15	*/
16	package one.util.streamex;
17
18	import java.util.Spliterator;
19	import java.util.function.*;
20
21	import static one.util.streamex.Internals.*;
22
23	/* package */final class CollapseSpliterator<T, R> extends Box<T> implements Spliterator<R> {
24	private final Spliterator<T> source;
25	private final CollapseSpliterator<T, R> root; // used as lock
26	private R acc;
27	volatile Connector<T, R> left;
28	volatile Connector<T, R> right;
29	private final Function<T, R> mapper;
30	private final BiFunction<R, T, R> accumulator;
31	private final BinaryOperator<R> combiner;
32	private final BiPredicate<? super T, ? super T> mergeable;
33
34	private static final class Connector<T, R> {
35	CollapseSpliterator<T, R> lhs, rhs;
36	T left = none(), right = none();	1✔
37	R acc;
38
39	Connector(CollapseSpliterator<T, R> lhs, R acc, CollapseSpliterator<T, R> rhs) {	1✔
40	this.lhs = lhs;	1✔
41	this.rhs = rhs;	1✔
42	this.acc = acc;	1✔
43	}	1✔
44
45	R drain() {
46	if (lhs != null)	1✔
47	lhs.right = null;	1✔
48	if (rhs != null)	1✔
49	rhs.left = null;	1✔
50	return acc;	1✔
51	}
52
53	R drainLeft() {
54	return left == NONE ? drain() : none();	1✔
55	}
56
57	R drainRight() {
58	return right == NONE ? drain() : none();	1✔
59	}
60	}
61
62	CollapseSpliterator(BiPredicate<? super T, ? super T> mergeable, Function<T, R> mapper,
63	BiFunction<R, T, R> accumulator, BinaryOperator<R> combiner, Spliterator<T> source) {
64	super(none());	1✔
65	this.source = source;	1✔
66	this.mergeable = mergeable;	1✔
67	this.mapper = mapper;	1✔
68	this.accumulator = accumulator;	1✔
69	this.combiner = combiner;	1✔
70	this.root = this;	1✔
71	}	1✔
72
73	private CollapseSpliterator(CollapseSpliterator<T, R> root, Spliterator<T> source, Connector<T, R> left,
74	Connector<T, R> right) {
75	super(none());	1✔
76	this.source = source;	1✔
77	this.root = root;	1✔
78	this.mergeable = root.mergeable;	1✔
79	this.mapper = root.mapper;	1✔
80	this.accumulator = root.accumulator;	1✔
81	this.combiner = root.combiner;	1✔
82	this.left = left;	1✔
83	this.right = right;	1✔
84	if (left != null)	1✔
85	left.rhs = this;	1✔
86	right.lhs = this;	1✔
87	}	1✔
88
89	@Override
90	public boolean tryAdvance(Consumer<? super R> action) {
91	if (left != null) {	1✔
92	if (accept(handleLeft(), action)) {	1✔
93	return true;	1✔
94	}
95	}
96	if (a == NONE) { // start	1✔
97	if (!source.tryAdvance(this)) {	1✔
98	return accept(pushRight(none(), none()), action);	1✔
99	}
100	}
101	T first = a;	1✔
102	R acc = mapper.apply(a);	1✔
103	T last = first;	1✔
104	while (source.tryAdvance(this)) {	1✔
105	if (!this.mergeable.test(last, a)) {	1✔
106	action.accept(acc);	1✔
107	return true;	1✔
108	}
109	last = a;	1✔
110	acc = this.accumulator.apply(acc, last);	1✔
111	}
112	return accept(pushRight(acc, last), action);	1✔
113	}
114
115	@Override
116	public void forEachRemaining(Consumer<? super R> action) {
117	while (left != null) {	1✔
118	accept(handleLeft(), action);	1✔
119	}
120	if (a != NONE) {	1✔
121	acc = mapper.apply(a);	1✔
122	}
123	source.forEachRemaining(next -> {	1✔
124	if (a == NONE) {	1✔
125	acc = mapper.apply(next);	1✔
126	} else if (!this.mergeable.test(a, next)) {	1✔
127	action.accept(acc);	1✔
128	acc = mapper.apply(next);	1✔
129	} else {
130	acc = accumulator.apply(acc, next);	1✔
131	}
132	a = next;	1✔
133	});	1✔
134	if (a == NONE) {	1✔
135	accept(pushRight(none(), none()), action);	1✔
136	} else if (accept(pushRight(acc, a), action)) {	1✔
137	if (right != null) {	1✔
138	action.accept(right.acc);	1✔
139	right = null;	1✔
140	}
141	}
142	}	1✔
143
144	private boolean accept(R acc, Consumer<? super R> action) {
145	if (acc != NONE) {	1✔
146	action.accept(acc);	1✔
147	return true;	1✔
148	}
149	return false;	1✔
150	}
151
152	private R handleLeft() {
153	synchronized (root) {	1✔
154	Connector<T, R> l = left;	1✔
155	if (l == null) {	1✔
156	return none();	×
157	}
158	if (l.left == NONE && l.right == NONE && l.acc != NONE) {	1✔
159	return l.drain();	1✔
160	}
161	}	1✔
162	if (source.tryAdvance(this)) {	1✔
163	T first = this.a;	1✔
164	T last = first;	1✔
165	R acc = this.mapper.apply(first);	1✔
166	while (source.tryAdvance(this)) {	1✔
167	if (!this.mergeable.test(last, a))	1✔
168	return pushLeft(first, acc);	1✔
169	last = a;	1✔
170	acc = this.accumulator.apply(acc, last);	1✔
171	}
172	a = none();	1✔
173	return connectOne(first, acc, last);	1✔
174	}
175	return connectEmpty();	1✔
176	}
177
178	// l + <first\|acc\|?>
179	private R pushLeft(T first, R acc) {
180	synchronized (root) {	1✔
181	Connector<T, R> l = left;	1✔
182	if (l == null)	1✔
183	return acc;	1✔
184	left = null;	1✔
185	l.rhs = null;	1✔
186	T laright = l.right;	1✔
187	l.right = none();	1✔
188	if (l.acc == NONE) {	1✔
189	l.acc = acc;	1✔
190	l.left = first;	1✔
191	return none();	1✔
192	}
193	if (this.mergeable.test(laright, first)) {	1✔
194	l.acc = this.combiner.apply(l.acc, acc);	1✔
195	return l.drainLeft();	1✔
196	}
197	if (l.left == NONE) {	1✔
198	left = new Connector<>(null, acc, this);	1✔
199	return l.drain();	1✔
200	}
201	}	1✔
202	return acc;	1✔
203	}
204
205	// <?\|acc\|last> + r
206	private R pushRight(R acc, T last) {
207	a = none();	1✔
208	if (right == null)	1✔
209	return acc;	1✔
210	synchronized (root) {	1✔
211	Connector<T, R> r = right;	1✔
212	if (r == null)	1✔
213	return acc;	×
214	right = null;	1✔
215	r.lhs = null;	1✔
216	T raleft = r.left;	1✔
217	r.left = none();	1✔
218	if (r.acc == NONE) {	1✔
219	if (acc == NONE) {	1✔
220	r.drain();	1✔
221	} else {
222	r.acc = acc;	1✔
223	r.right = last;	1✔
224	}
225	return none();	1✔
226	}
227	if (acc == NONE) {	1✔
228	return r.drainRight();	1✔
229	}
230	if (mergeable.test(last, raleft)) {	1✔
231	r.acc = combiner.apply(acc, r.acc);	1✔
232	return r.drainRight();	1✔
233	}
234	if (r.right == NONE)	1✔
235	right = new Connector<>(this, r.drain(), null);	1✔
236	return acc;	1✔
237	}
238	}
239
240	// l + <first\|acc\|last> + r
241	private R connectOne(T first, R acc, T last) {
242	synchronized (root) {	1✔
243	Connector<T, R> l = left;	1✔
244	if (l == null) {	1✔
245	return pushRight(acc, last);	1✔
246	}
247	if (l.acc == NONE) {	1✔
248	l.acc = acc;	1✔
249	l.left = first;	1✔
250	l.right = last;	1✔
251	return connectEmpty();	1✔
252	}
253	T laright = l.right;	1✔
254	if (mergeable.test(laright, first)) {	1✔
255	l.acc = combiner.apply(l.acc, acc);	1✔
256	l.right = last;	1✔
257	return connectEmpty();	1✔
258	}
259	left = null;	1✔
260	l.rhs = null;	1✔
261	l.right = none();	1✔
262	if (l.left != NONE) {	1✔
263	return pushRight(acc, last);	1✔
264	}
265	acc = pushRight(acc, last);	1✔
266	if (acc != NONE)	1✔
267	left = new Connector<>(null, acc, this);	1✔
268	return l.drain();	1✔
269	}
270	}
271
272	// l + r
273	private R connectEmpty() {
274	synchronized (root) {	1✔
275	Connector<T, R> l = left, r = right;	1✔
276	if (l == null) {	1✔
277	return pushRight(none(), none());	×
278	}
279	left = right = null;	1✔
280	l.rhs = null;	1✔
281	T laright = l.right;	1✔
282	l.right = none();	1✔
283	if (l.acc == NONE) {	1✔
284	if (r == null)	1✔
285	l.drain();	1✔
286	else {
287	if (l.lhs != null) {	1✔
288	l.lhs.right = r;	1✔
289	r.lhs = l.lhs;	1✔
290	}
291	}
292	return none();	1✔
293	}
294	if (r == null) {	1✔
295	return l.drainLeft();	1✔
296	}
297	r.lhs = null;	1✔
298	if (r.acc == NONE) {	1✔
299	if (r.rhs != null) {	1✔
300	r.rhs.left = l;	1✔
301	l.rhs = r.rhs;	1✔
302	l.right = laright;	1✔
303	}
304	return none();	1✔
305	}
306	T raleft = r.left;	1✔
307	r.left = none();	1✔
308	if (mergeable.test(laright, raleft)) {	1✔
309	R acc = combiner.apply(l.acc, r.acc);	1✔
310	if (l.left == NONE && r.right == NONE) {	1✔
311	l.drain();	1✔
312	r.drain();	1✔
313	return acc;	1✔
314	}
315	l.acc = acc;	1✔
316	l.right = r.right;	1✔
317	if (r.rhs != null) {	1✔
318	r.rhs.left = l;	1✔
319	l.rhs = r.rhs;	1✔
320	}
321	return none();	1✔
322	}
323	if (l.left == NONE) {	1✔
324	if (r.right == NONE)	1✔
325	right = new Connector<>(this, r.drain(), null);	1✔
326	return l.drain();	1✔
327	}
328	return r.drainRight();	1✔
329	}
330	}
331
332	@Override
333	public Spliterator<R> trySplit() {
334	Spliterator<T> prefix = source.trySplit();	1✔
335	if (prefix == null)	1✔
336	return null;	1✔
337	Connector<T, R> newBox = new Connector<>(null, none(), this);	1✔
338	synchronized (root) {	1✔
339	CollapseSpliterator<T, R> result = new CollapseSpliterator<>(root, prefix, left, newBox);	1✔
340	this.left = newBox;	1✔
341	return result;	1✔
342	}
343	}
344
345	@Override
346	public long estimateSize() {
347	return source.estimateSize();	1✔
348	}
349
350	@Override
351	public int characteristics() {
352	return source.characteristics() & (CONCURRENT \| IMMUTABLE \| ORDERED);	1✔
353	}
354	}

amaembo / streamex / #677

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous