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    /**
035     * Constructs a new {@code MemoryTileCache}.
036     */
037    public MemoryTileCache() {
038        hash = new HashMap<>(cacheSize);
039        lruTiles = new CacheLinkedListElement();
040    }
041
042    @Override
043    public synchronized void addTile(Tile tile) {
044        CacheEntry entry = createCacheEntry(tile);
045            hash.put(tile.getKey(), entry);
046            lruTiles.addFirst(entry);
047            if (hash.size() > cacheSize) {
048                removeOldEntries();
049            }
050    }
051
052    @Override
053    public synchronized Tile getTile(TileSource source, int x, int y, int z) {
054        CacheEntry entry = hash.get(Tile.getTileKey(source, x, y, z));
055        if (entry == null)
056            return null;
057        // We don't care about placeholder tiles and hourglass image tiles, the
058        // important tiles are the loaded ones
059        if (entry.tile.isLoaded())
060            lruTiles.moveElementToFirstPos(entry);
061        return entry.tile;
062    }
063
064    /**
065     * Removes the least recently used tiles
066     */
067    protected synchronized void removeOldEntries() {
068        try {
069            while (lruTiles.getElementCount() > cacheSize) {
070                removeEntry(lruTiles.getLastElement());
071            }
072        } catch (Exception e) {
073            log.warning(e.getMessage());
074        }
075    }
076
077    protected synchronized void removeEntry(CacheEntry entry) {
078        hash.remove(entry.tile.getKey());
079        lruTiles.removeEntry(entry);
080    }
081
082    protected CacheEntry createCacheEntry(Tile tile) {
083        return new CacheEntry(tile);
084    }
085
086    @Override
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}