1 /*
2 * Copyright (C) 2012 The Guava Authors
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
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkArgument;
20 import static com.google.common.base.Preconditions.checkNotNull;
21
22 import com.google.common.annotations.Beta;
23 import com.google.common.annotations.GwtCompatible;
24 import com.google.common.annotations.VisibleForTesting;
25 import com.google.errorprone.annotations.CanIgnoreReturnValue;
26 import java.io.Serializable;
27 import java.util.ArrayDeque;
28 import java.util.Collection;
29 import java.util.Queue;
30
31 /**
32 * A non-blocking queue which automatically evicts elements from the head of the queue when
33 * attempting to add new elements onto the queue and it is full. This queue orders elements FIFO
34 * (first-in-first-out). This data structure is logically equivalent to a circular buffer (i.e.,
35 * cyclic buffer or ring buffer).
36 *
37 * <p>An evicting queue must be configured with a maximum size. Each time an element is added to a
38 * full queue, the queue automatically removes its head element. This is different from conventional
39 * bounded queues, which either block or reject new elements when full.
40 *
41 * <p>This class is not thread-safe, and does not accept null elements.
42 *
43 * @author Kurt Alfred Kluever
44 * @since 15.0
45 */
46 @Beta
47 @GwtCompatible
48 public final class EvictingQueue<E> extends ForwardingQueue<E> implements Serializable {
49
50 private final Queue<E> delegate;
51
52 @VisibleForTesting final int maxSize;
53
54 private EvictingQueue(int maxSize) {
55 checkArgument(maxSize >= 0, "maxSize (%s) must >= 0", maxSize);
56 this.delegate = new ArrayDeque<E>(maxSize);
57 this.maxSize = maxSize;
58 }
59
60 /**
61 * Creates and returns a new evicting queue that will hold up to {@code maxSize} elements.
62 *
63 * <p>When {@code maxSize} is zero, elements will be evicted immediately after being added to the
64 * queue.
65 */
66 public static <E> EvictingQueue<E> create(int maxSize) {
67 return new EvictingQueue<E>(maxSize);
68 }
69
70 /**
71 * Returns the number of additional elements that this queue can accept without evicting; zero if
72 * the queue is currently full.
73 *
74 * @since 16.0
75 */
76 public int remainingCapacity() {
77 return maxSize - size();
78 }
79
80 @Override
81 protected Queue<E> delegate() {
82 return delegate;
83 }
84
85 /**
86 * Adds the given element to this queue. If the queue is currently full, the element at the head
87 * of the queue is evicted to make room.
88 *
89 * @return {@code true} always
90 */
91 @Override
92 @CanIgnoreReturnValue
93 public boolean offer(E e) {
94 return add(e);
95 }
96
97 /**
98 * Adds the given element to this queue. If the queue is currently full, the element at the head
99 * of the queue is evicted to make room.
100 *
101 * @return {@code true} always
102 */
103 @Override
104 @CanIgnoreReturnValue
105 public boolean add(E e) {
106 checkNotNull(e); // check before removing
107 if (maxSize == 0) {
108 return true;
109 }
110 if (size() == maxSize) {
111 delegate.remove();
112 }
113 delegate.add(e);
114 return true;
115 }
116
117 @Override
118 @CanIgnoreReturnValue
119 public boolean addAll(Collection<? extends E> collection) {
120 int size = collection.size();
121 if (size >= maxSize) {
122 clear();
123 return Iterables.addAll(this, Iterables.skip(collection, size - maxSize));
124 }
125 return standardAddAll(collection);
126 }
127
128 @Override
129 public boolean contains(Object object) {
130 return delegate().contains(checkNotNull(object));
131 }
132
133 @Override
134 @CanIgnoreReturnValue
135 public boolean remove(Object object) {
136 return delegate().remove(checkNotNull(object));
137 }
138
139 // TODO(kak): Do we want to checkNotNull each element in containsAll, removeAll, and retainAll?
140
141 private static final long serialVersionUID = 0L;
142 }