19556545386

Committed 21 Nov 2025 01:10AM UTC coverage: 94.471%. First build

Build # 19556545386

Build Type

Pull #155

github

Committed by

web-flow

Commit Message

Merge d1e6e0721 into 7c236fec9

Pull Request Pull Request #155: Bump Java Version to 17/25

Run Details

59 of 83 new or added lines in 25 files covered. (71.08%)

12611 of 13349 relevant lines covered (94.47%)

1.73 hits per line

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

72.5

/filters/reuse/src/main/java/de/learnlib/filter/reuse/tree/BoundedDeque.java

/* Copyright (C) 2013-2025 TU Dortmund University
 * This file is part of LearnLib <https://learnlib.de>.
 *
 * 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 de.learnlib.filter.reuse.tree;

import java.util.AbstractCollection;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;

import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * A generic deque-derived container which transparently acts <i>either</i> as a stack <i>or</i> a queue, and optionally
 * a capacity restriction with a configurable policy which element is evicted (or reject) if the maximum capacity is
 * reached.
 * <p>
 * <b>Note:</b> Like {@link ArrayDeque}, this deque implementation is not thread-safe. Concurrent access by multiple
 * threads requires explicit synchronization.
 *
 * @param <E>
 *         element type
 */
public class BoundedDeque<E> extends AbstractCollection<E> {

    private final EvictPolicy evictPolicy;
    private final AccessPolicy accessPolicy;
    private final int capacity;
    private final Deque<E> deque;

    /**
     * Constructor. Creates an unbounded deque with the given access policy.
     *
     * @param accessPolicy
     *         whether this deque acts as a stack or a queue
     */
    public BoundedDeque(AccessPolicy accessPolicy) {
        this(-1, accessPolicy, EvictPolicy.EVICT_OLDEST); // policy does not matter
    }

    /**
     * Constructor. Creates a possibly capacity-restricted deque with the given access policy.
     *
     * @param capacity
     *         the maximum capacity of this deque. A value less than or equal to 0 means unbounded
     * @param accessPolicy
     *         whether this deque acts as a stack or a queue
     * @param evictPolicy
     *         which elements to remove if the maximum capacity is reached. If the capacity is unbounded, this parameter
     *         has no effect
     */
    public BoundedDeque(int capacity, AccessPolicy accessPolicy, EvictPolicy evictPolicy) {
        if (capacity <= 0) {
            this.deque = new ArrayDeque<>(); // unbounded, default capacity
        } else {
            this.deque = new ArrayDeque<>(capacity);
        }
        this.capacity = capacity;
        this.accessPolicy = accessPolicy;
        this.evictPolicy = evictPolicy;
    }

    /**
     * Inserts an element into the deque, and returns the one that had to be evicted in case of a capacity violation.
     *
     * @param element
     *         the element to insert
     *
     * @return the evicted element, {@code null} if the maximum capacity has not been reached
     */
    public @Nullable E insert(E element) {
        E evicted = null;
        if (size() >= capacity) {
            if (evictPolicy == EvictPolicy.REJECT_NEW) {
                // reject the new element
                return element;
            }
            // Evict first, so we do not need to resize
            evicted = evict();
        }
        deque.offerLast(element);
        return evicted;
    }

    /**
     * Evicts an element, depending on the configured {@link EvictPolicy}.
     *
     * @return the evicted element, may be {@code null} if the queue was empty
     */
    private @Nullable E evict() {
        return switch (evictPolicy) {
            case EVICT_OLDEST -> deque.pollFirst();
            case EVICT_NEWEST -> deque.pollLast();
            default -> throw new IllegalStateException("Illegal evict policy: " + evictPolicy);
        };
    }

    /**
     * Retrieves and remove the top-most element, i.e., the element that is either the top of the stack or the head of
     * the queue, depending on the configured {@link AccessPolicy}.
     *
     * @return the evicted element, may be {@code null} if the queue was empty
     */
    public @Nullable E retrieve() {
        return switch (accessPolicy) {
            case LIFO -> deque.pollLast();
            case FIFO -> deque.pollFirst();
        };
    }

    /**
     * Retrieves, but does not remove the top-most element, i.e., the element that is either the top of the stack or the
     * head of the queue, depending on the configured {@link AccessPolicy}. May be {@code null} if the stack is empty.
     *
     * @return the top-most element of the container
     */
    public @Nullable E peek() {
        return switch (accessPolicy) {
            case LIFO -> deque.peekLast();
            case FIFO -> deque.peekFirst();
        };
    }

    /**
     * Retrieves whether capacity restriction is in effect.
     *
     * @return {@code true} if the capacity is restricted, {@code false} otherwise
     */
    public boolean isBounded() {
        return capacity > 0;
    }

    @Override
    public Iterator<E> iterator() {
        return deque.iterator();
    }

    @Override
    public int size() {
        return deque.size();
    }

    @Override
    public boolean isEmpty() {
        return deque.isEmpty();
    }

    @Override
    public void clear() {
        deque.clear();
    }

    /**
     * The policy which determines in which order elements are accessed.
     */
    public enum AccessPolicy {
        /**
         * Last-in first-out. This deque will then act as a <i>stack</i>.
         */
        LIFO,
        /**
         * First-in first-out. This deque will then act as a <i>queue</i>.
         */
        FIFO
    }

    /**
     * The policy which determines in which order elements are removed if the maximum capacity is reached.
     */
    public enum EvictPolicy {
        /**
         * Evict the oldest element, i.e., the one at the head of the queue/bottom of the stack.
         */
        EVICT_OLDEST,
        /**
         * Reject the element that is about to be inserted.
         */
        REJECT_NEW,
        /**
         * Evict the newest element, that is already *in* the queue (i.e., in any case inserts the new element).
         */
        EVICT_NEWEST
    }

}

1	/* Copyright (C) 2013-2025 TU Dortmund University
2	* This file is part of LearnLib <https://learnlib.de>.
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 de.learnlib.filter.reuse.tree;
17
18	import java.util.AbstractCollection;
19	import java.util.ArrayDeque;
20	import java.util.Deque;
21	import java.util.Iterator;
22
23	import org.checkerframework.checker.nullness.qual.Nullable;
24
25	/**
26	* A generic deque-derived container which transparently acts <i>either</i> as a stack <i>or</i> a queue, and optionally
27	* a capacity restriction with a configurable policy which element is evicted (or reject) if the maximum capacity is
28	* reached.
29	* <p>
30	* <b>Note:</b> Like {@link ArrayDeque}, this deque implementation is not thread-safe. Concurrent access by multiple
31	* threads requires explicit synchronization.
32	*
33	* @param <E>
34	* element type
35	*/
36	public class BoundedDeque<E> extends AbstractCollection<E> {
37
38	private final EvictPolicy evictPolicy;
39	private final AccessPolicy accessPolicy;
40	private final int capacity;
41	private final Deque<E> deque;
42
43	/**
44	* Constructor. Creates an unbounded deque with the given access policy.
45	*
46	* @param accessPolicy
47	* whether this deque acts as a stack or a queue
48	*/
49	public BoundedDeque(AccessPolicy accessPolicy) {
50	this(-1, accessPolicy, EvictPolicy.EVICT_OLDEST); // policy does not matter	×
51	}	×
52
53	/**
54	* Constructor. Creates a possibly capacity-restricted deque with the given access policy.
55	*
56	* @param capacity
57	* the maximum capacity of this deque. A value less than or equal to 0 means unbounded
58	* @param accessPolicy
59	* whether this deque acts as a stack or a queue
60	* @param evictPolicy
61	* which elements to remove if the maximum capacity is reached. If the capacity is unbounded, this parameter
62	* has no effect
63	*/
64	public BoundedDeque(int capacity, AccessPolicy accessPolicy, EvictPolicy evictPolicy) {	2✔
65	if (capacity <= 0) {	2✔
66	this.deque = new ArrayDeque<>(); // unbounded, default capacity	2✔
67	} else {
68	this.deque = new ArrayDeque<>(capacity);	×
69	}
70	this.capacity = capacity;	2✔
71	this.accessPolicy = accessPolicy;	2✔
72	this.evictPolicy = evictPolicy;	2✔
73	}	2✔
74
75	/**
76	* Inserts an element into the deque, and returns the one that had to be evicted in case of a capacity violation.
77	*
78	* @param element
79	* the element to insert
80	*
81	* @return the evicted element, {@code null} if the maximum capacity has not been reached
82	*/
83	public @Nullable E insert(E element) {
84	E evicted = null;	2✔
85	if (size() >= capacity) {	2✔
86	if (evictPolicy == EvictPolicy.REJECT_NEW) {	2✔
87	// reject the new element
88	return element;	×
89	}
90	// Evict first, so we do not need to resize
91	evicted = evict();	2✔
92	}
93	deque.offerLast(element);	2✔
94	return evicted;	2✔
95	}
96
97	/**
98	* Evicts an element, depending on the configured {@link EvictPolicy}.
99	*
100	* @return the evicted element, may be {@code null} if the queue was empty
101	*/
102	private @Nullable E evict() {
103	return switch (evictPolicy) {	2✔
104	case EVICT_OLDEST -> deque.pollFirst();	2✔
NEW 105	case EVICT_NEWEST -> deque.pollLast();	×
NEW 106	default -> throw new IllegalStateException("Illegal evict policy: " + evictPolicy);	×
107	};
108	}
109
110	/**
111	* Retrieves and remove the top-most element, i.e., the element that is either the top of the stack or the head of
112	* the queue, depending on the configured {@link AccessPolicy}.
113	*
114	* @return the evicted element, may be {@code null} if the queue was empty
115	*/
116	public @Nullable E retrieve() {
117	return switch (accessPolicy) {	2✔
118	case LIFO -> deque.pollLast();	2✔
NEW 119	case FIFO -> deque.pollFirst();	×
120	};
121	}
122
123	/**
124	* Retrieves, but does not remove the top-most element, i.e., the element that is either the top of the stack or the
125	* head of the queue, depending on the configured {@link AccessPolicy}. May be {@code null} if the stack is empty.
126	*
127	* @return the top-most element of the container
128	*/
129	public @Nullable E peek() {
NEW 130	return switch (accessPolicy) {	×
NEW 131	case LIFO -> deque.peekLast();	×
NEW 132	case FIFO -> deque.peekFirst();	×
133	};
134	}
135
136	/**
137	* Retrieves whether capacity restriction is in effect.
138	*
139	* @return {@code true} if the capacity is restricted, {@code false} otherwise
140	*/
141	public boolean isBounded() {
142	return capacity > 0;	×
143	}
144
145	@Override
146	public Iterator<E> iterator() {
147	return deque.iterator();	1✔
148	}
149
150	@Override
151	public int size() {
152	return deque.size();	2✔
153	}
154
155	@Override
156	public boolean isEmpty() {
157	return deque.isEmpty();	2✔
158	}
159
160	@Override
161	public void clear() {
162	deque.clear();	1✔
163	}	1✔
164
165	/**
166	* The policy which determines in which order elements are accessed.
167	*/
168	public enum AccessPolicy {	2✔
169	/**
170	* Last-in first-out. This deque will then act as a <i>stack</i>.
171	*/
172	LIFO,	2✔
173	/**
174	* First-in first-out. This deque will then act as a <i>queue</i>.
175	*/
176	FIFO	2✔
177	}
178
179	/**
180	* The policy which determines in which order elements are removed if the maximum capacity is reached.
181	*/
182	public enum EvictPolicy {	2✔
183	/**
184	* Evict the oldest element, i.e., the one at the head of the queue/bottom of the stack.
185	*/
186	EVICT_OLDEST,	2✔
187	/**
188	* Reject the element that is about to be inserted.
189	*/
190	REJECT_NEW,	2✔
191	/**
192	* Evict the newest element, that is already in the queue (i.e., in any case inserts the new element).
193	*/
194	EVICT_NEWEST	2✔
195	}
196
197	}

LearnLib / learnlib / 19556545386

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