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;
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        this(200);
039    }
040
041    /**
042     * Constructs a new {@code MemoryTileCache}.
043     * @param cacheSize size of the cache
044     */
045    public MemoryTileCache(int cacheSize) {
046        this.cacheSize = cacheSize;
047        hash = new HashMap<>(cacheSize);
048        lruTiles = new CacheLinkedListElement();
049    }
050
051    @Override
052    public synchronized void addTile(Tile tile) {
053        CacheEntry entry = createCacheEntry(tile);
054        if (hash.put(tile.getKey(), entry) == null) {
055            // only if hash hadn't had the element, add it to LRU
056            lruTiles.addFirst(entry);
057            if (hash.size() > cacheSize || lruTiles.getElementCount() > cacheSize) {
058                removeOldEntries();
059            }
060        }
061    }
062
063    @Override
064    public synchronized Tile getTile(TileSource source, int x, int y, int z) {
065        CacheEntry entry = hash.get(Tile.getTileKey(source, x, y, z));
066        if (entry == null)
067            return null;
068        lruTiles.moveElementToFirstPos(entry);
069        return entry.tile;
070    }
071
072    /**
073     * Removes the least recently used tiles
074     */
075    protected synchronized void removeOldEntries() {
076        try {
077            while (lruTiles.getElementCount() > cacheSize) {
078                removeEntry(lruTiles.getLastElement());
079            }
080        } catch (NullPointerException e) {
081            log.warning(e.getMessage());
082        }
083    }
084
085    protected synchronized void removeEntry(CacheEntry entry) {
086        hash.remove(entry.tile.getKey());
087        lruTiles.removeEntry(entry);
088    }
089
090    protected CacheEntry createCacheEntry(Tile tile) {
091        return new CacheEntry(tile);
092    }
093
094    @Override
095    public synchronized void clear() {
096        hash.clear();
097        lruTiles.clear();
098    }
099
100    @Override
101    public synchronized int getTileCount() {
102        return hash.size();
103    }
104
105    @Override
106    public synchronized int getCacheSize() {
107        return cacheSize;
108    }
109
110    /**
111     * Changes the maximum number of {@link Tile} objects that this cache holds.
112     *
113     * @param cacheSize
114     *            new maximum number of tiles
115     */
116    public synchronized void setCacheSize(int cacheSize) {
117        this.cacheSize = cacheSize;
118        if (hash.size() > cacheSize)
119            removeOldEntries();
120    }
121
122    /**
123     * Linked list element holding the {@link Tile} and links to the
124     * {@link #next} and {@link #prev} item in the list.
125     */
126    protected static class CacheEntry {
127        private Tile tile;
128        private CacheEntry next;
129        private CacheEntry prev;
130
131        protected CacheEntry(Tile tile) {
132            this.tile = tile;
133        }
134
135        @Override
136        public String toString() {
137            return tile.toString();
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;
150        protected CacheEntry lastElement;
151        protected int elementCount;
152
153        /**
154         * Constructs a new {@code CacheLinkedListElement}.
155         */
156        public CacheLinkedListElement() {
157            clear();
158        }
159
160        public void clear() {
161            elementCount = 0;
162            firstElement = null;
163            lastElement = null;
164        }
165
166        /**
167         * Add the element to the head of the list.
168         *
169         * @param element new element to be added
170         */
171        public void addFirst(CacheEntry element) {
172            if (element == null) return;
173            if (elementCount == 0) {
174                firstElement = element;
175                lastElement = element;
176                element.prev = null;
177                element.next = null;
178            } else {
179                element.next = firstElement;
180                firstElement.prev = element;
181                element.prev = null;
182                firstElement = element;
183            }
184            elementCount++;
185        }
186
187        /**
188         * Removes the specified element from the list.
189         *
190         * @param element element to be removed
191         */
192        public void removeEntry(CacheEntry element) {
193            if (element == null) return;
194            if (element.next != null) {
195                element.next.prev = element.prev;
196            }
197            if (element.prev != null) {
198                element.prev.next = element.next;
199            }
200            if (element == firstElement)
201                firstElement = element.next;
202            if (element == lastElement)
203                lastElement = element.prev;
204            element.next = null;
205            element.prev = null;
206            elementCount--;
207        }
208
209        public void moveElementToFirstPos(CacheEntry entry) {
210            if (firstElement == entry)
211                return;
212            removeEntry(entry);
213            addFirst(entry);
214        }
215
216        public int getElementCount() {
217            return elementCount;
218        }
219
220        public CacheEntry getLastElement() {
221            return lastElement;
222        }
223
224        public CacheEntry getFirstElement() {
225            return firstElement;
226        }
227    }
228}