1 /*
2 Copyright 2008 Ramon Servadei
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 fulmine.util.collection;
17
18 import java.util.Collection;
19 import java.util.Iterator;
20 import java.util.Map;
21 import java.util.Set;
22
23 import fulmine.util.reference.IReferenceCounter;
24 import fulmine.util.reference.ReferenceCounter;
25
26 /**
27 * A {@link Set} implementation backed by an internal set. It tracks the
28 * 'time-to-live' of entries in the internal set. When entries are added, they
29 * are given a TTL (time-to-live) and on each successive call to
30 * {@link Set#clear()}, {@link Set#remove(Object)},
31 * {@link Set#removeAll(Collection)} or any other 'reducing' method, the TTL is
32 * decreased. When the TTL reaches 0, the entry is removed.
33 * <p>
34 * This is not thread safe.
35 *
36 * @param <COMPONENT>
37 * the element type contained by the list
38 * @author Ramon Servadei
39 */
40 public final class TtlSet<COMPONENT> implements Set<COMPONENT>
41 {
42
43 /**
44 * Delegate iterator that is used to track the next element in the
45 * iteration. On a call to {@link #remove()}, the
46 * {@link TtlSet#decrementTtl(Object)} is called to decrement the TTL before
47 * removing the object.
48 *
49 * @author Ramon Servadei
50 */
51 private final class DelegateIterator implements Iterator<COMPONENT>
52 {
53
54 private final Iterator<COMPONENT> delegate;
55
56 private COMPONENT next;
57
58 private DelegateIterator(Iterator<COMPONENT> delegate)
59 {
60 super();
61 this.delegate = delegate;
62 }
63
64 public boolean hasNext()
65 {
66 return this.delegate.hasNext();
67 }
68
69 public COMPONENT next()
70 {
71 this.next = this.delegate.next();
72 return this.next;
73 }
74
75 public void remove()
76 {
77 if (this.next != null)
78 {
79 if (TtlSet.this.decrementTtl(this.next))
80 {
81 this.delegate.remove();
82 }
83 }
84 }
85 }
86
87 /** The default TTL */
88 public static final int DEFAULT_TTL = 3;
89
90 /** Tracks the time-to-live per object */
91 private final IReferenceCounter<COMPONENT> ttl;
92
93 /** Holds the entries for the set */
94 private final Set<COMPONENT> inner;
95
96 /** The starting TTL for new entries */
97 private final int startingTtl;
98
99 /**
100 * Standard constructor for the {@link TtlSet}. Sets the
101 * {@link #startingTtl} to {@link TtlSet#DEFAULT_TTL}.
102 */
103 public TtlSet()
104 {
105 this(TtlSet.DEFAULT_TTL);
106 }
107
108 /**
109 * Construct the {@link TtlSet} with the specified TTL for any new entry
110 * added.
111 *
112 * @param ttl
113 * the TTL for new entries
114 */
115 public TtlSet(int ttl)
116 {
117 super();
118 this.inner = CollectionFactory.newSet();
119 this.ttl = new ReferenceCounter<COMPONENT>();
120 this.startingTtl = ttl;
121 }
122
123 public boolean add(COMPONENT o)
124 {
125 final boolean added = this.inner.add(o);
126 if (added)
127 {
128 ttl.adjustCount(o, startingTtl);
129 }
130 return added;
131 }
132
133 public boolean addAll(Collection<? extends COMPONENT> c)
134 {
135 boolean added = false;
136 for (COMPONENT component : c)
137 {
138 added |= add(component);
139 }
140 return added;
141 }
142
143 /**
144 * Decreases the TTL of all entries by 1. Any entries with a TTL of 0 after
145 * this operation will be removed.
146 */
147 public void clear()
148 {
149 final Iterator<COMPONENT> iterator = this.iterator();
150 while (iterator.hasNext())
151 {
152 iterator.next();
153 iterator.remove();
154 }
155 }
156
157 public boolean contains(Object o)
158 {
159 return this.inner.contains(o);
160 }
161
162 public boolean containsAll(Collection<?> c)
163 {
164 return this.inner.containsAll(c);
165 }
166
167 public boolean isEmpty()
168 {
169 return this.inner.isEmpty();
170 }
171
172 public Iterator<COMPONENT> iterator()
173 {
174 return this.new DelegateIterator(this.inner.iterator());
175 }
176
177 /**
178 * Decreases the TTL of the element by 1. If the TTL is 0, the element is
179 * removed.
180 *
181 * @return <code>true</code> if the element was removed, <code>false</code>
182 * otherwise
183 * @see Set#remove(Object)
184 */
185 public boolean remove(Object o)
186 {
187 if (decrementTtl(o))
188 {
189 return this.inner.remove(o);
190 }
191 return false;
192 }
193
194 /**
195 * Helper method to decrement the TTL of the object and return if the object
196 * can be removed
197 *
198 * @param o
199 * the object whose TTL is to be decremented
200 * @return <code>true</code> if the TTL is 0 and the object can be removed,
201 * <code>false</code> otherwise
202 */
203 @SuppressWarnings("unchecked")
204 private boolean decrementTtl(Object o)
205 {
206 this.ttl.adjustCount((COMPONENT) o, -1);
207 return (this.ttl.getCount((COMPONENT) o) == 0);
208 }
209
210 /**
211 * For each element in the passed in collection, calls
212 * {@link #remove(Object)}.
213 *
214 * @return <code>true</code> if any element in this {@link TtlSet} was
215 * removed as a result of this call, <code>false</code> otherwise
216 * @see Set#removeAll(Collection)
217 */
218 public boolean removeAll(Collection<?> c)
219 {
220 boolean changed = false;
221 if (c != null)
222 {
223 // create a set encapsulating the input collection
224 Set<?> other = CollectionFactory.newSet(c);
225 for (Object object : other)
226 {
227 changed |= remove(object);
228 }
229 }
230 return changed;
231 }
232
233 /**
234 * Unsupported.
235 *
236 * @throws UnsupportedOperationException
237 */
238 public boolean retainAll(Collection<?> c)
239 {
240 throw new UnsupportedOperationException();
241 }
242
243 public int size()
244 {
245 return this.inner.size();
246 }
247
248 public Object[] toArray()
249 {
250 return this.inner.toArray();
251 }
252
253 public <T> T[] toArray(T[] a)
254 {
255 return this.inner.toArray(a);
256 }
257
258 @SuppressWarnings("boxing")
259 @Override
260 public String toString()
261 {
262 Map<COMPONENT, Integer> stringValue =
263 CollectionFactory.newMap(this.inner.size());
264 for (COMPONENT element : this.inner)
265 {
266 stringValue.put(element, this.ttl.getCount(element));
267 }
268 return this.getClass().getSimpleName()
269 + CollectionUtils.toFormattedString(stringValue);
270 }
271
272 @Override
273 public boolean equals(Object o)
274 {
275 return this.inner.equals(o);
276 }
277
278 @Override
279 public int hashCode()
280 {
281 return this.inner.hashCode();
282 }
283 }