001 /*
002 * (c) 2007 Tasecurity Group S.L, Spain
003 * This library is free software; you can redistribute it and/or
004 * modify it under the terms of the GNU Lesser General Public
005 * License as published by the Free Software Foundation; either
006 * version 2.1 of the License, or (at your option) any later version.
007 *
008 * This library is distributed in the hope that it will be useful,
009 * but WITHOUT ANY WARRANTY; without even the implied warranty of
010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
011 * Lesser General Public License for more details.
012 *
013 * You should have received a copy of the GNU Lesser General Public
014 * License along with this library; if not, write to the Free Software
015 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
016 */
017 package mondrian.util;
018
019 import java.lang.ref.WeakReference;
020 import java.util.ArrayList;
021 import java.util.Collection;
022 import java.util.HashMap;
023 import java.util.HashSet;
024 import java.util.List;
025 import java.util.Map;
026 import java.util.Set;
027 import java.util.WeakHashMap;
028
029 /**
030 * Map with limited size to be used as cache.
031 *
032 * @author lcanals, www.tasecurity.net
033 */
034 public class CacheMap<S, T> implements Map<S, T> {
035 private LinkedNode head;
036 private LinkedNode tail;
037 private final Map<S, Pair<S,T>> map;
038 private final int maxSize;
039
040 /**
041 * Creates an empty map with limited size.
042 *
043 * @param size Maximum number of mapped elements.
044 */
045 public CacheMap(final int size) {
046 this.head = new LinkedNode(null, null);
047 this.tail = new LinkedNode(head, null);
048 this.map = new WeakHashMap<S,Pair<S,T>>(size);
049 this.maxSize = size;
050 }
051
052 public void clear() {
053 this.head = new LinkedNode(null, null);
054 this.tail = new LinkedNode(head, null);
055 map.clear();
056 }
057
058 public boolean containsKey(final Object key) {
059 return map.containsKey(key);
060 }
061
062 public boolean containsValue(final Object value) {
063 return this.values().contains(value);
064 }
065
066 public Set entrySet() {
067 final Set<Map.Entry<S,T>> set = new HashSet<Map.Entry<S,T>>();
068 for (final Map.Entry<S, Pair<S,T>> entry : this.map.entrySet()) {
069 set.add(new Map.Entry<S,T>() {
070 public boolean equals(Object s) {
071 if (s instanceof Map.Entry) {
072 return ((Map.Entry) s).getKey().equals(
073 entry.getKey())
074 && ((Map.Entry) s).getValue().equals(
075 entry.getValue().value);
076 } else {
077 return false;
078 }
079 }
080 public S getKey() {
081 return entry.getKey();
082 }
083 public T getValue() {
084 return entry.getValue().value;
085 }
086 public int hashCode() {
087 return entry.hashCode();
088 }
089 public T setValue(final T x) {
090 return entry.setValue(new Pair<S,T>(
091 x, new LinkedNode(head, entry.getKey())))
092 .value;
093 }
094 });
095 }
096 return set;
097 }
098
099 public T get(final Object key) {
100 final Pair<S,T> pair = map.get(key);
101 if (pair != null) {
102 final LinkedNode<S> node = pair.getNode();
103 if (node == null) {
104 map.remove(key);
105 return null;
106 }
107 node.moveTo(head);
108 return pair.value;
109 } else {
110 return null;
111 }
112 }
113
114 public boolean isEmpty() {
115 return map.isEmpty();
116 }
117
118 public Set<S> keySet() {
119 return map.keySet();
120 }
121
122 public T put(final S key, final T value) {
123 final Pair<S, T> pair = new Pair<S,T>(value, new LinkedNode(head, key));
124 final Pair<S, T> obj = map.put(key, pair);
125 if (map.size() > maxSize) {
126 tail.getPrevious().remove();
127 map.remove(key);
128 }
129 if (obj != null) {
130 return obj.value;
131 } else {
132 return null;
133 }
134 }
135
136 public void putAll(final Map t) {
137 throw new UnsupportedOperationException();
138 }
139
140 public T remove(final Object key) {
141 final Pair<S,T> pair = map.get(key);
142 if (pair == null) {
143 return null;
144 }
145 pair.getNode().remove();
146 return map.remove(key).value;
147 }
148
149 public int size() {
150 return map.size();
151 }
152
153 public Collection<T> values() {
154 final List<T> vals = new ArrayList<T>();
155 for (final Pair<S,T> pair : map.values()) {
156 vals.add(pair.value);
157 }
158 return vals;
159 }
160
161 public int hashCode() {
162 return map.hashCode();
163 }
164
165 public String toString() {
166 return "Ordered keys: " + head.toString() + "\n"
167 + "Map:" + map.toString();
168 }
169
170 public boolean equals(Object o) {
171 CacheMap c = (CacheMap) o;
172 return map.equals(c.map);
173 }
174
175 //
176 // PRIVATE STUFF ------------------
177 //
178
179 /**
180 * Pair of linked key - value
181 */
182 private final class Pair<S, T> implements java.io.Serializable {
183 private final T value;
184 private final WeakReference<LinkedNode<S>> node;
185 private Pair(final T value, final LinkedNode<S> node) {
186 this.node = new WeakReference<LinkedNode<S>>(node);
187 this.value = value;
188 }
189
190 private LinkedNode<S> getNode() {
191 return node.get();
192 }
193
194 public boolean equals(final Object o) {
195 return o != null && o.equals(this.value);
196 }
197 }
198
199
200 /**
201 * Represents a node in a linked list.
202 */
203 private class LinkedNode<S> implements java.io.Serializable {
204 private LinkedNode<S> next, prev;
205 private S key;
206
207 public LinkedNode(final LinkedNode<S> prev, final S key) {
208 this.key = key;
209 insertAfter(prev);
210 }
211
212 public void remove() {
213 if (this.prev != null) {
214 this.prev.next = this.next;
215 }
216 if (this.next != null) {
217 this.next.prev = this.prev;
218 }
219 }
220
221 public void moveTo(final LinkedNode<S> prev) {
222 remove();
223 insertAfter(prev);
224 }
225
226 public LinkedNode<S> getPrevious() {
227 return this.prev;
228 }
229
230 public String toString() {
231 if (this.next != null) {
232 if (key != null) {
233 return key.toString() + ", " + this.next.toString();
234 } else {
235 return "<null>, " + this.next.toString();
236 }
237 } else {
238 if (key != null) {
239 return key.toString();
240 } else {
241 return "<null>";
242 }
243 }
244 }
245
246 private void insertAfter(final LinkedNode<S> prev) {
247 if (prev != null) {
248 this.next = prev.next;
249 } else {
250 this.prev = null;
251 }
252 this.prev = prev;
253
254 if (prev != null) {
255 if (prev.next != null) {
256 prev.next.prev = this;
257 }
258 prev.next = this;
259 }
260 }
261 }
262 }
263
264 // End CacheMap.java
265