10888a09821a98ac0680fad765217302858e70fa4Paul Duffin/* 20888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Copyright (C) 2012 The Guava Authors 30888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 40888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Licensed under the Apache License, Version 2.0 (the "License"); 50888a09821a98ac0680fad765217302858e70fa4Paul Duffin * you may not use this file except in compliance with the License. 60888a09821a98ac0680fad765217302858e70fa4Paul Duffin * You may obtain a copy of the License at 70888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 80888a09821a98ac0680fad765217302858e70fa4Paul Duffin * http://www.apache.org/licenses/LICENSE-2.0 90888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 100888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Unless required by applicable law or agreed to in writing, software 110888a09821a98ac0680fad765217302858e70fa4Paul Duffin * distributed under the License is distributed on an "AS IS" BASIS, 120888a09821a98ac0680fad765217302858e70fa4Paul Duffin * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 130888a09821a98ac0680fad765217302858e70fa4Paul Duffin * See the License for the specific language governing permissions and 140888a09821a98ac0680fad765217302858e70fa4Paul Duffin * limitations under the License. 150888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 160888a09821a98ac0680fad765217302858e70fa4Paul Duffin 170888a09821a98ac0680fad765217302858e70fa4Paul Duffinpackage com.google.common.collect; 180888a09821a98ac0680fad765217302858e70fa4Paul Duffin 190888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.base.Preconditions.checkArgument; 200888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.base.Preconditions.checkNotNull; 210888a09821a98ac0680fad765217302858e70fa4Paul Duffin 220888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.annotations.Beta; 230888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.annotations.GwtIncompatible; 240888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.annotations.VisibleForTesting; 250888a09821a98ac0680fad765217302858e70fa4Paul Duffin 260888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.io.Serializable; 273ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport java.util.ArrayDeque; 280888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.Collection; 290888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.Queue; 300888a09821a98ac0680fad765217302858e70fa4Paul Duffin 310888a09821a98ac0680fad765217302858e70fa4Paul Duffin/** 320888a09821a98ac0680fad765217302858e70fa4Paul Duffin * A non-blocking queue which automatically evicts elements from the head of the queue when 330888a09821a98ac0680fad765217302858e70fa4Paul Duffin * attempting to add new elements onto the queue and it is full. 340888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 350888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>An evicting queue must be configured with a maximum size. Each time an element is added 360888a09821a98ac0680fad765217302858e70fa4Paul Duffin * to a full queue, the queue automatically removes its head element. This is different from 370888a09821a98ac0680fad765217302858e70fa4Paul Duffin * conventional bounded queues, which either block or reject new elements when full. 380888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 390888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>This class is not thread-safe, and does not accept null elements. 400888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 410888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @author Kurt Alfred Kluever 420888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 15.0 430888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 440888a09821a98ac0680fad765217302858e70fa4Paul Duffin@Beta 450888a09821a98ac0680fad765217302858e70fa4Paul Duffin@GwtIncompatible("java.util.ArrayDeque") 460888a09821a98ac0680fad765217302858e70fa4Paul Duffinpublic final class EvictingQueue<E> extends ForwardingQueue<E> implements Serializable { 470888a09821a98ac0680fad765217302858e70fa4Paul Duffin 480888a09821a98ac0680fad765217302858e70fa4Paul Duffin private final Queue<E> delegate; 490888a09821a98ac0680fad765217302858e70fa4Paul Duffin 500888a09821a98ac0680fad765217302858e70fa4Paul Duffin @VisibleForTesting 510888a09821a98ac0680fad765217302858e70fa4Paul Duffin final int maxSize; 520888a09821a98ac0680fad765217302858e70fa4Paul Duffin 530888a09821a98ac0680fad765217302858e70fa4Paul Duffin private EvictingQueue(int maxSize) { 540888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkArgument(maxSize >= 0, "maxSize (%s) must >= 0", maxSize); 553ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin this.delegate = new ArrayDeque<E>(maxSize); 560888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.maxSize = maxSize; 570888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 580888a09821a98ac0680fad765217302858e70fa4Paul Duffin 590888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 600888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates and returns a new evicting queue that will hold up to {@code maxSize} elements. 610888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 620888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>When {@code maxSize} is zero, elements will be evicted immediately after being added to the 630888a09821a98ac0680fad765217302858e70fa4Paul Duffin * queue. 640888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 650888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> EvictingQueue<E> create(int maxSize) { 660888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new EvictingQueue<E>(maxSize); 670888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 680888a09821a98ac0680fad765217302858e70fa4Paul Duffin 690888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 700888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns the number of additional elements that this queue can accept without evicting; 710888a09821a98ac0680fad765217302858e70fa4Paul Duffin * zero if the queue is currently full. 720888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 730888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 16.0 740888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 750888a09821a98ac0680fad765217302858e70fa4Paul Duffin public int remainingCapacity() { 760888a09821a98ac0680fad765217302858e70fa4Paul Duffin return maxSize - size(); 770888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 780888a09821a98ac0680fad765217302858e70fa4Paul Duffin 790888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override protected Queue<E> delegate() { 800888a09821a98ac0680fad765217302858e70fa4Paul Duffin return delegate; 810888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 820888a09821a98ac0680fad765217302858e70fa4Paul Duffin 830888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 840888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Adds the given element to this queue. If the queue is currently full, the element at the head 850888a09821a98ac0680fad765217302858e70fa4Paul Duffin * of the queue is evicted to make room. 860888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 870888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return {@code true} always 880888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 890888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean offer(E e) { 900888a09821a98ac0680fad765217302858e70fa4Paul Duffin return add(e); 910888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 920888a09821a98ac0680fad765217302858e70fa4Paul Duffin 930888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 940888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Adds the given element to this queue. If the queue is currently full, the element at the head 950888a09821a98ac0680fad765217302858e70fa4Paul Duffin * of the queue is evicted to make room. 960888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 970888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return {@code true} always 980888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 990888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean add(E e) { 1000888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNotNull(e); // check before removing 1010888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (maxSize == 0) { 1020888a09821a98ac0680fad765217302858e70fa4Paul Duffin return true; 1030888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1040888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (size() == maxSize) { 1050888a09821a98ac0680fad765217302858e70fa4Paul Duffin delegate.remove(); 1060888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1070888a09821a98ac0680fad765217302858e70fa4Paul Duffin delegate.add(e); 1080888a09821a98ac0680fad765217302858e70fa4Paul Duffin return true; 1090888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1100888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1110888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean addAll(Collection<? extends E> collection) { 1120888a09821a98ac0680fad765217302858e70fa4Paul Duffin return standardAddAll(collection); 1130888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1140888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1150888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 1160888a09821a98ac0680fad765217302858e70fa4Paul Duffin public boolean contains(Object object) { 1170888a09821a98ac0680fad765217302858e70fa4Paul Duffin return delegate().contains(checkNotNull(object)); 1180888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1190888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1200888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 1210888a09821a98ac0680fad765217302858e70fa4Paul Duffin public boolean remove(Object object) { 1220888a09821a98ac0680fad765217302858e70fa4Paul Duffin return delegate().remove(checkNotNull(object)); 1230888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1240888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1250888a09821a98ac0680fad765217302858e70fa4Paul Duffin // TODO(user): Do we want to checkNotNull each element in containsAll, removeAll, and retainAll? 1260888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1270888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final long serialVersionUID = 0L; 1280888a09821a98ac0680fad765217302858e70fa4Paul Duffin} 129