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