001package org.openstreetmap.gui.jmapviewer;
002
003//License: GPL. Copyright 2008 by Jan Peter Stotz
004
005import java.util.HashMap;
006import java.util.Map;
007import java.util.logging.Logger;
008
009import org.openstreetmap.gui.jmapviewer.interfaces.TileCache;
010import org.openstreetmap.gui.jmapviewer.interfaces.TileSource;
011
012/**
013 * {@link TileCache} implementation that stores all {@link Tile} objects in
014 * memory up to a certain limit ({@link #getCacheSize()}). If the limit is
015 * exceeded the least recently used {@link Tile} objects will be deleted.
016 *
017 * @author Jan Peter Stotz
018 */
019public class MemoryTileCache implements TileCache {
020
021    protected static final Logger log = Logger.getLogger(MemoryTileCache.class.getName());
022
023    /**
024     * Default cache size
025     */
026    protected int cacheSize = 200;
027
028    protected final Map<String, CacheEntry> hash;
029
030    /**
031     * List of all tiles in their last recently used order
032     */
033    protected final CacheLinkedListElement lruTiles;
034
035    public MemoryTileCache() {
036        hash = new HashMap<String, CacheEntry>(cacheSize);
037        lruTiles = new CacheLinkedListElement();
038    }
039
040    @Override
041    public synchronized void addTile(Tile tile) {
042        CacheEntry entry = createCacheEntry(tile);
043            hash.put(tile.getKey(), entry);
044            lruTiles.addFirst(entry);
045            if (hash.size() > cacheSize) {
046                removeOldEntries();
047            }
048    }
049
050    @Override
051    public synchronized Tile getTile(TileSource source, int x, int y, int z) {
052        CacheEntry entry = hash.get(Tile.getTileKey(source, x, y, z));
053        if (entry == null)
054            return null;
055        // We don't care about placeholder tiles and hourglass image tiles, the
056        // important tiles are the loaded ones
057        if (entry.tile.isLoaded())
058            lruTiles.moveElementToFirstPos(entry);
059        return entry.tile;
060    }
061
062    /**
063     * Removes the least recently used tiles
064     */
065    protected synchronized void removeOldEntries() {
066        try {
067            while (lruTiles.getElementCount() > cacheSize) {
068                removeEntry(lruTiles.getLastElement());
069            }
070        } catch (Exception e) {
071            log.warning(e.getMessage());
072        }
073    }
074
075    protected synchronized void removeEntry(CacheEntry entry) {
076        hash.remove(entry.tile.getKey());
077        lruTiles.removeEntry(entry);
078    }
079
080    protected CacheEntry createCacheEntry(Tile tile) {
081        return new CacheEntry(tile);
082    }
083
084    /**
085     * Clears the cache deleting all tiles from memory
086     */
087    public synchronized void clear() {
088        hash.clear();
089        lruTiles.clear();
090    }
091
092    @Override
093    public int getTileCount() {
094        return hash.size();
095    }
096
097    public int getCacheSize() {
098        return cacheSize;
099    }
100
101    /**
102     * Changes the maximum number of {@link Tile} objects that this cache holds.
103     *
104     * @param cacheSize
105     *            new maximum number of tiles
106     */
107    public synchronized void setCacheSize(int cacheSize) {
108        this.cacheSize = cacheSize;
109        if (hash.size() > cacheSize)
110            removeOldEntries();
111    }
112
113    /**
114     * Linked list element holding the {@link Tile} and links to the
115     * {@link #next} and {@link #prev} item in the list.
116     */
117    protected static class CacheEntry {
118        Tile tile;
119
120        CacheEntry next;
121        CacheEntry prev;
122
123        protected CacheEntry(Tile tile) {
124            this.tile = tile;
125        }
126
127        public Tile getTile() {
128            return tile;
129        }
130
131        public CacheEntry getNext() {
132            return next;
133        }
134
135        public CacheEntry getPrev() {
136            return prev;
137        }
138
139    }
140
141    /**
142     * Special implementation of a double linked list for {@link CacheEntry}
143     * elements. It supports element removal in constant time - in difference to
144     * the Java implementation which needs O(n).
145     *
146     * @author Jan Peter Stotz
147     */
148    protected static class CacheLinkedListElement {
149        protected CacheEntry firstElement = null;
150        protected CacheEntry lastElement;
151        protected int elementCount;
152
153        public CacheLinkedListElement() {
154            clear();
155        }
156
157        public void clear() {
158            elementCount = 0;
159            firstElement = null;
160            lastElement = null;
161        }
162
163        /**
164         * Add the element to the head of the list.
165         *
166         * @param element new element to be added
167         */
168        public void addFirst(CacheEntry element) {
169            if (element == null) return;
170            if (elementCount == 0) {
171                firstElement = element;
172                lastElement = element;
173                element.prev = null;
174                element.next = null;
175            } else {
176                element.next = firstElement;
177                firstElement.prev = element;
178                element.prev = null;
179                firstElement = element;
180            }
181            elementCount++;
182        }
183
184        /**
185         * Removes the specified element from the list.
186         *
187         * @param element element to be removed
188         */
189        public void removeEntry(CacheEntry element) {
190            if (element == null) return;
191            if (element.next != null) {
192                element.next.prev = element.prev;
193            }
194            if (element.prev != null) {
195                element.prev.next = element.next;
196            }
197            if (element == firstElement)
198                firstElement = element.next;
199            if (element == lastElement)
200                lastElement = element.prev;
201            element.next = null;
202            element.prev = null;
203            elementCount--;
204        }
205
206        public void moveElementToFirstPos(CacheEntry entry) {
207            if (firstElement == entry)
208                return;
209            removeEntry(entry);
210            addFirst(entry);
211        }
212
213        public int getElementCount() {
214            return elementCount;
215        }
216
217        public CacheEntry getLastElement() {
218            return lastElement;
219        }
220
221        public CacheEntry getFirstElement() {
222            return firstElement;
223        }
224
225    }
226}