001    package org.openstreetmap.gui.jmapviewer;
002    
003    //License: GPL. Copyright 2008 by Jan Peter Stotz
004    
005    import java.util.Hashtable;
006    import java.util.logging.Logger;
007    
008    import org.openstreetmap.gui.jmapviewer.interfaces.TileCache;
009    import 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     */
018    public 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 Hashtable<String, CacheEntry> hashtable;
028    
029        /**
030         * List of all tiles in their last recently used order
031         */
032        protected CacheLinkedListElement lruTiles;
033    
034        public MemoryTileCache() {
035            hashtable = new Hashtable<String, CacheEntry>(cacheSize);
036            lruTiles = new CacheLinkedListElement();
037        }
038    
039        public void addTile(Tile tile) {
040            CacheEntry entry = createCacheEntry(tile);
041            hashtable.put(tile.getKey(), entry);
042            lruTiles.addFirst(entry);
043            if (hashtable.size() > cacheSize)
044                removeOldEntries();
045        }
046    
047        public Tile getTile(TileSource source, int x, int y, int z) {
048            CacheEntry entry = hashtable.get(Tile.getTileKey(source, x, y, z));
049            if (entry == null)
050                return null;
051            // We don't care about placeholder tiles and hourglass image tiles, the
052            // important tiles are the loaded ones
053            if (entry.tile.isLoaded())
054                lruTiles.moveElementToFirstPos(entry);
055            return entry.tile;
056        }
057    
058        /**
059         * Removes the least recently used tiles
060         */
061        protected void removeOldEntries() {
062            synchronized (lruTiles) {
063                try {
064                    while (lruTiles.getElementCount() > cacheSize) {
065                        removeEntry(lruTiles.getLastElement());
066                    }
067                } catch (Exception e) {
068                    log.warning(e.getMessage());
069                }
070            }
071        }
072    
073        protected void removeEntry(CacheEntry entry) {
074            hashtable.remove(entry.tile.getKey());
075            lruTiles.removeEntry(entry);
076        }
077    
078        protected CacheEntry createCacheEntry(Tile tile) {
079            return new CacheEntry(tile);
080        }
081    
082        /**
083         * Clears the cache deleting all tiles from memory
084         */
085        public void clear() {
086            synchronized (lruTiles) {
087                hashtable.clear();
088                lruTiles.clear();
089            }
090        }
091    
092        public int getTileCount() {
093            return hashtable.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 void setCacheSize(int cacheSize) {
107            this.cacheSize = cacheSize;
108            if (hashtable.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 synchronized 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 synchronized void addFirst(CacheEntry element) {
168                if (elementCount == 0) {
169                    firstElement = element;
170                    lastElement = element;
171                    element.prev = null;
172                    element.next = null;
173                } else {
174                    element.next = firstElement;
175                    firstElement.prev = element;
176                    element.prev = null;
177                    firstElement = element;
178                }
179                elementCount++;
180            }
181    
182            /**
183             * Removes the specified element from the list.
184             *
185             * @param element element to be removed
186             */
187            public synchronized void removeEntry(CacheEntry element) {
188                if (element.next != null) {
189                    element.next.prev = element.prev;
190                }
191                if (element.prev != null) {
192                    element.prev.next = element.next;
193                }
194                if (element == firstElement)
195                    firstElement = element.next;
196                if (element == lastElement)
197                    lastElement = element.prev;
198                element.next = null;
199                element.prev = null;
200                elementCount--;
201            }
202    
203            public synchronized void moveElementToFirstPos(CacheEntry entry) {
204                if (firstElement == entry)
205                    return;
206                removeEntry(entry);
207                addFirst(entry);
208            }
209    
210            public int getElementCount() {
211                return elementCount;
212            }
213    
214            public CacheEntry getLastElement() {
215                return lastElement;
216            }
217    
218            public CacheEntry getFirstElement() {
219                return firstElement;
220            }
221    
222        }
223    }