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