1/*
2 * Copyright (C) 2013 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.android.photos.views;
18
19import android.content.Context;
20import android.graphics.Bitmap;
21import android.graphics.Rect;
22import android.graphics.RectF;
23import android.support.v4.util.Pools.Pool;
24import android.support.v4.util.Pools.SynchronizedPool;
25import android.util.DisplayMetrics;
26import android.util.Log;
27import android.util.LongSparseArray;
28import android.view.View;
29import android.view.WindowManager;
30
31import com.android.gallery3d.common.Utils;
32import com.android.gallery3d.glrenderer.BasicTexture;
33import com.android.gallery3d.glrenderer.GLCanvas;
34import com.android.gallery3d.glrenderer.UploadedTexture;
35
36/**
37 * Handles laying out, decoding, and drawing of tiles in GL
38 */
39public class TiledImageRenderer {
40    public static final int SIZE_UNKNOWN = -1;
41
42    private static final String TAG = "TiledImageRenderer";
43    private static final int UPLOAD_LIMIT = 1;
44
45    /*
46     *  This is the tile state in the CPU side.
47     *  Life of a Tile:
48     *      ACTIVATED (initial state)
49     *              --> IN_QUEUE - by queueForDecode()
50     *              --> RECYCLED - by recycleTile()
51     *      IN_QUEUE --> DECODING - by decodeTile()
52     *               --> RECYCLED - by recycleTile)
53     *      DECODING --> RECYCLING - by recycleTile()
54     *               --> DECODED  - by decodeTile()
55     *               --> DECODE_FAIL - by decodeTile()
56     *      RECYCLING --> RECYCLED - by decodeTile()
57     *      DECODED --> ACTIVATED - (after the decoded bitmap is uploaded)
58     *      DECODED --> RECYCLED - by recycleTile()
59     *      DECODE_FAIL -> RECYCLED - by recycleTile()
60     *      RECYCLED --> ACTIVATED - by obtainTile()
61     */
62    private static final int STATE_ACTIVATED = 0x01;
63    private static final int STATE_IN_QUEUE = 0x02;
64    private static final int STATE_DECODING = 0x04;
65    private static final int STATE_DECODED = 0x08;
66    private static final int STATE_DECODE_FAIL = 0x10;
67    private static final int STATE_RECYCLING = 0x20;
68    private static final int STATE_RECYCLED = 0x40;
69
70    private static Pool<Bitmap> sTilePool = new SynchronizedPool<Bitmap>(64);
71
72    // TILE_SIZE must be 2^N
73    private int mTileSize;
74
75    private TileSource mModel;
76    private BasicTexture mPreview;
77    protected int mLevelCount;  // cache the value of mScaledBitmaps.length
78
79    // The mLevel variable indicates which level of bitmap we should use.
80    // Level 0 means the original full-sized bitmap, and a larger value means
81    // a smaller scaled bitmap (The width and height of each scaled bitmap is
82    // half size of the previous one). If the value is in [0, mLevelCount), we
83    // use the bitmap in mScaledBitmaps[mLevel] for display, otherwise the value
84    // is mLevelCount
85    private int mLevel = 0;
86
87    private int mOffsetX;
88    private int mOffsetY;
89
90    private int mUploadQuota;
91    private boolean mRenderComplete;
92
93    private final RectF mSourceRect = new RectF();
94    private final RectF mTargetRect = new RectF();
95
96    private final LongSparseArray<Tile> mActiveTiles = new LongSparseArray<Tile>();
97
98    // The following three queue are guarded by mQueueLock
99    private final Object mQueueLock = new Object();
100    private final TileQueue mRecycledQueue = new TileQueue();
101    private final TileQueue mUploadQueue = new TileQueue();
102    private final TileQueue mDecodeQueue = new TileQueue();
103
104    // The width and height of the full-sized bitmap
105    protected int mImageWidth = SIZE_UNKNOWN;
106    protected int mImageHeight = SIZE_UNKNOWN;
107
108    protected int mCenterX;
109    protected int mCenterY;
110    protected float mScale;
111    protected int mRotation;
112
113    private boolean mLayoutTiles;
114
115    // Temp variables to avoid memory allocation
116    private final Rect mTileRange = new Rect();
117    private final Rect mActiveRange[] = {new Rect(), new Rect()};
118
119    private TileDecoder mTileDecoder;
120    private boolean mBackgroundTileUploaded;
121
122    private int mViewWidth, mViewHeight;
123    private View mParent;
124
125    /**
126     * Interface for providing tiles to a {@link TiledImageRenderer}
127     */
128    public static interface TileSource {
129
130        /**
131         * If the source does not care about the tile size, it should use
132         * {@link TiledImageRenderer#suggestedTileSize(Context)}
133         */
134        public int getTileSize();
135        public int getImageWidth();
136        public int getImageHeight();
137        public int getRotation();
138
139        /**
140         * Return a Preview image if available. This will be used as the base layer
141         * if higher res tiles are not yet available
142         */
143        public BasicTexture getPreview();
144
145        /**
146         * The tile returned by this method can be specified this way: Assuming
147         * the image size is (width, height), first take the intersection of (0,
148         * 0) - (width, height) and (x, y) - (x + tileSize, y + tileSize). If
149         * in extending the region, we found some part of the region is outside
150         * the image, those pixels are filled with black.
151         *
152         * If level > 0, it does the same operation on a down-scaled version of
153         * the original image (down-scaled by a factor of 2^level), but (x, y)
154         * still refers to the coordinate on the original image.
155         *
156         * The method would be called by the decoder thread.
157         */
158        public Bitmap getTile(int level, int x, int y, Bitmap reuse);
159    }
160
161    public static int suggestedTileSize(Context context) {
162        return isHighResolution(context) ? 512 : 256;
163    }
164
165    private static boolean isHighResolution(Context context) {
166        DisplayMetrics metrics = new DisplayMetrics();
167        WindowManager wm = (WindowManager)
168                context.getSystemService(Context.WINDOW_SERVICE);
169        wm.getDefaultDisplay().getMetrics(metrics);
170        return metrics.heightPixels > 2048 ||  metrics.widthPixels > 2048;
171    }
172
173    public TiledImageRenderer(View parent) {
174        mParent = parent;
175        mTileDecoder = new TileDecoder();
176        mTileDecoder.start();
177    }
178
179    public int getViewWidth() {
180        return mViewWidth;
181    }
182
183    public int getViewHeight() {
184        return mViewHeight;
185    }
186
187    private void invalidate() {
188        mParent.postInvalidate();
189    }
190
191    public void setModel(TileSource model, int rotation) {
192        if (mModel != model) {
193            mModel = model;
194            notifyModelInvalidated();
195        }
196        if (mRotation != rotation) {
197            mRotation = rotation;
198            mLayoutTiles = true;
199        }
200    }
201
202    private void calculateLevelCount() {
203        if (mPreview != null) {
204            mLevelCount = Math.max(0, Utils.ceilLog2(
205                mImageWidth / (float) mPreview.getWidth()));
206        } else {
207            int levels = 1;
208            int maxDim = Math.max(mImageWidth, mImageHeight);
209            int t = mTileSize;
210            while (t < maxDim) {
211                t <<= 1;
212                levels++;
213            }
214            mLevelCount = levels;
215        }
216    }
217
218    public void notifyModelInvalidated() {
219        invalidateTiles();
220        if (mModel == null) {
221            mImageWidth = 0;
222            mImageHeight = 0;
223            mLevelCount = 0;
224            mPreview = null;
225        } else {
226            mImageWidth = mModel.getImageWidth();
227            mImageHeight = mModel.getImageHeight();
228            mPreview = mModel.getPreview();
229            mTileSize = mModel.getTileSize();
230            calculateLevelCount();
231        }
232        mLayoutTiles = true;
233    }
234
235    public void setViewSize(int width, int height) {
236        mViewWidth = width;
237        mViewHeight = height;
238    }
239
240    public void setPosition(int centerX, int centerY, float scale) {
241        if (mCenterX == centerX && mCenterY == centerY
242                && mScale == scale) {
243            return;
244        }
245        mCenterX = centerX;
246        mCenterY = centerY;
247        mScale = scale;
248        mLayoutTiles = true;
249    }
250
251    // Prepare the tiles we want to use for display.
252    //
253    // 1. Decide the tile level we want to use for display.
254    // 2. Decide the tile levels we want to keep as texture (in addition to
255    //    the one we use for display).
256    // 3. Recycle unused tiles.
257    // 4. Activate the tiles we want.
258    private void layoutTiles() {
259        if (mViewWidth == 0 || mViewHeight == 0 || !mLayoutTiles) {
260            return;
261        }
262        mLayoutTiles = false;
263
264        // The tile levels we want to keep as texture is in the range
265        // [fromLevel, endLevel).
266        int fromLevel;
267        int endLevel;
268
269        // We want to use a texture larger than or equal to the display size.
270        mLevel = Utils.clamp(Utils.floorLog2(1f / mScale), 0, mLevelCount);
271
272        // We want to keep one more tile level as texture in addition to what
273        // we use for display. So it can be faster when the scale moves to the
274        // next level. We choose the level closest to the current scale.
275        if (mLevel != mLevelCount) {
276            Rect range = mTileRange;
277            getRange(range, mCenterX, mCenterY, mLevel, mScale, mRotation);
278            mOffsetX = Math.round(mViewWidth / 2f + (range.left - mCenterX) * mScale);
279            mOffsetY = Math.round(mViewHeight / 2f + (range.top - mCenterY) * mScale);
280            fromLevel = mScale * (1 << mLevel) > 0.75f ? mLevel - 1 : mLevel;
281        } else {
282            // Activate the tiles of the smallest two levels.
283            fromLevel = mLevel - 2;
284            mOffsetX = Math.round(mViewWidth / 2f - mCenterX * mScale);
285            mOffsetY = Math.round(mViewHeight / 2f - mCenterY * mScale);
286        }
287
288        fromLevel = Math.max(0, Math.min(fromLevel, mLevelCount - 2));
289        endLevel = Math.min(fromLevel + 2, mLevelCount);
290
291        Rect range[] = mActiveRange;
292        for (int i = fromLevel; i < endLevel; ++i) {
293            getRange(range[i - fromLevel], mCenterX, mCenterY, i, mRotation);
294        }
295
296        // If rotation is transient, don't update the tile.
297        if (mRotation % 90 != 0) {
298            return;
299        }
300
301        synchronized (mQueueLock) {
302            mDecodeQueue.clean();
303            mUploadQueue.clean();
304            mBackgroundTileUploaded = false;
305
306            // Recycle unused tiles: if the level of the active tile is outside the
307            // range [fromLevel, endLevel) or not in the visible range.
308            int n = mActiveTiles.size();
309            for (int i = 0; i < n; i++) {
310                Tile tile = mActiveTiles.valueAt(i);
311                int level = tile.mTileLevel;
312                if (level < fromLevel || level >= endLevel
313                        || !range[level - fromLevel].contains(tile.mX, tile.mY)) {
314                    mActiveTiles.removeAt(i);
315                    i--;
316                    n--;
317                    recycleTile(tile);
318                }
319            }
320        }
321
322        for (int i = fromLevel; i < endLevel; ++i) {
323            int size = mTileSize << i;
324            Rect r = range[i - fromLevel];
325            for (int y = r.top, bottom = r.bottom; y < bottom; y += size) {
326                for (int x = r.left, right = r.right; x < right; x += size) {
327                    activateTile(x, y, i);
328                }
329            }
330        }
331        invalidate();
332    }
333
334    private void invalidateTiles() {
335        synchronized (mQueueLock) {
336            mDecodeQueue.clean();
337            mUploadQueue.clean();
338
339            // TODO(xx): disable decoder
340            int n = mActiveTiles.size();
341            for (int i = 0; i < n; i++) {
342                Tile tile = mActiveTiles.valueAt(i);
343                recycleTile(tile);
344            }
345            mActiveTiles.clear();
346        }
347    }
348
349    private void getRange(Rect out, int cX, int cY, int level, int rotation) {
350        getRange(out, cX, cY, level, 1f / (1 << (level + 1)), rotation);
351    }
352
353    // If the bitmap is scaled by the given factor "scale", return the
354    // rectangle containing visible range. The left-top coordinate returned is
355    // aligned to the tile boundary.
356    //
357    // (cX, cY) is the point on the original bitmap which will be put in the
358    // center of the ImageViewer.
359    private void getRange(Rect out,
360            int cX, int cY, int level, float scale, int rotation) {
361
362        double radians = Math.toRadians(-rotation);
363        double w = mViewWidth;
364        double h = mViewHeight;
365
366        double cos = Math.cos(radians);
367        double sin = Math.sin(radians);
368        int width = (int) Math.ceil(Math.max(
369                Math.abs(cos * w - sin * h), Math.abs(cos * w + sin * h)));
370        int height = (int) Math.ceil(Math.max(
371                Math.abs(sin * w + cos * h), Math.abs(sin * w - cos * h)));
372
373        int left = (int) Math.floor(cX - width / (2f * scale));
374        int top = (int) Math.floor(cY - height / (2f * scale));
375        int right = (int) Math.ceil(left + width / scale);
376        int bottom = (int) Math.ceil(top + height / scale);
377
378        // align the rectangle to tile boundary
379        int size = mTileSize << level;
380        left = Math.max(0, size * (left / size));
381        top = Math.max(0, size * (top / size));
382        right = Math.min(mImageWidth, right);
383        bottom = Math.min(mImageHeight, bottom);
384
385        out.set(left, top, right, bottom);
386    }
387
388    public void freeTextures() {
389        mLayoutTiles = true;
390
391        mTileDecoder.finishAndWait();
392        synchronized (mQueueLock) {
393            mUploadQueue.clean();
394            mDecodeQueue.clean();
395            Tile tile = mRecycledQueue.pop();
396            while (tile != null) {
397                tile.recycle();
398                tile = mRecycledQueue.pop();
399            }
400        }
401
402        int n = mActiveTiles.size();
403        for (int i = 0; i < n; i++) {
404            Tile texture = mActiveTiles.valueAt(i);
405            texture.recycle();
406        }
407        mActiveTiles.clear();
408        mTileRange.set(0, 0, 0, 0);
409
410        while (sTilePool.acquire() != null) {}
411    }
412
413    public boolean draw(GLCanvas canvas) {
414        layoutTiles();
415        uploadTiles(canvas);
416
417        mUploadQuota = UPLOAD_LIMIT;
418        mRenderComplete = true;
419
420        int level = mLevel;
421        int rotation = mRotation;
422        int flags = 0;
423        if (rotation != 0) {
424            flags |= GLCanvas.SAVE_FLAG_MATRIX;
425        }
426
427        if (flags != 0) {
428            canvas.save(flags);
429            if (rotation != 0) {
430                int centerX = mViewWidth / 2, centerY = mViewHeight / 2;
431                canvas.translate(centerX, centerY);
432                canvas.rotate(rotation, 0, 0, 1);
433                canvas.translate(-centerX, -centerY);
434            }
435        }
436        try {
437            if (level != mLevelCount) {
438                int size = (mTileSize << level);
439                float length = size * mScale;
440                Rect r = mTileRange;
441
442                for (int ty = r.top, i = 0; ty < r.bottom; ty += size, i++) {
443                    float y = mOffsetY + i * length;
444                    for (int tx = r.left, j = 0; tx < r.right; tx += size, j++) {
445                        float x = mOffsetX + j * length;
446                        drawTile(canvas, tx, ty, level, x, y, length);
447                    }
448                }
449            } else if (mPreview != null) {
450                mPreview.draw(canvas, mOffsetX, mOffsetY,
451                        Math.round(mImageWidth * mScale),
452                        Math.round(mImageHeight * mScale));
453            }
454        } finally {
455            if (flags != 0) {
456                canvas.restore();
457            }
458        }
459
460        if (mRenderComplete) {
461            if (!mBackgroundTileUploaded) {
462                uploadBackgroundTiles(canvas);
463            }
464        } else {
465            invalidate();
466        }
467        return mRenderComplete || mPreview != null;
468    }
469
470    private void uploadBackgroundTiles(GLCanvas canvas) {
471        mBackgroundTileUploaded = true;
472        int n = mActiveTiles.size();
473        for (int i = 0; i < n; i++) {
474            Tile tile = mActiveTiles.valueAt(i);
475            if (!tile.isContentValid()) {
476                queueForDecode(tile);
477            }
478        }
479    }
480
481   private void queueForDecode(Tile tile) {
482       synchronized (mQueueLock) {
483           if (tile.mTileState == STATE_ACTIVATED) {
484               tile.mTileState = STATE_IN_QUEUE;
485               if (mDecodeQueue.push(tile)) {
486                   mQueueLock.notifyAll();
487               }
488           }
489       }
490    }
491
492    private void decodeTile(Tile tile) {
493        synchronized (mQueueLock) {
494            if (tile.mTileState != STATE_IN_QUEUE) {
495                return;
496            }
497            tile.mTileState = STATE_DECODING;
498        }
499        boolean decodeComplete = tile.decode();
500        synchronized (mQueueLock) {
501            if (tile.mTileState == STATE_RECYCLING) {
502                tile.mTileState = STATE_RECYCLED;
503                if (tile.mDecodedTile != null) {
504                    sTilePool.release(tile.mDecodedTile);
505                    tile.mDecodedTile = null;
506                }
507                mRecycledQueue.push(tile);
508                return;
509            }
510            tile.mTileState = decodeComplete ? STATE_DECODED : STATE_DECODE_FAIL;
511            if (!decodeComplete) {
512                return;
513            }
514            mUploadQueue.push(tile);
515        }
516        invalidate();
517    }
518
519    private Tile obtainTile(int x, int y, int level) {
520        synchronized (mQueueLock) {
521            Tile tile = mRecycledQueue.pop();
522            if (tile != null) {
523                tile.mTileState = STATE_ACTIVATED;
524                tile.update(x, y, level);
525                return tile;
526            }
527            return new Tile(x, y, level);
528        }
529    }
530
531    private void recycleTile(Tile tile) {
532        synchronized (mQueueLock) {
533            if (tile.mTileState == STATE_DECODING) {
534                tile.mTileState = STATE_RECYCLING;
535                return;
536            }
537            tile.mTileState = STATE_RECYCLED;
538            if (tile.mDecodedTile != null) {
539                sTilePool.release(tile.mDecodedTile);
540                tile.mDecodedTile = null;
541            }
542            mRecycledQueue.push(tile);
543        }
544    }
545
546    private void activateTile(int x, int y, int level) {
547        long key = makeTileKey(x, y, level);
548        Tile tile = mActiveTiles.get(key);
549        if (tile != null) {
550            if (tile.mTileState == STATE_IN_QUEUE) {
551                tile.mTileState = STATE_ACTIVATED;
552            }
553            return;
554        }
555        tile = obtainTile(x, y, level);
556        mActiveTiles.put(key, tile);
557    }
558
559    private Tile getTile(int x, int y, int level) {
560        return mActiveTiles.get(makeTileKey(x, y, level));
561    }
562
563    private static long makeTileKey(int x, int y, int level) {
564        long result = x;
565        result = (result << 16) | y;
566        result = (result << 16) | level;
567        return result;
568    }
569
570    private void uploadTiles(GLCanvas canvas) {
571        int quota = UPLOAD_LIMIT;
572        Tile tile = null;
573        while (quota > 0) {
574            synchronized (mQueueLock) {
575                tile = mUploadQueue.pop();
576            }
577            if (tile == null) {
578                break;
579            }
580            if (!tile.isContentValid()) {
581                if (tile.mTileState == STATE_DECODED) {
582                    tile.updateContent(canvas);
583                    --quota;
584                } else {
585                    Log.w(TAG, "Tile in upload queue has invalid state: " + tile.mTileState);
586                }
587            }
588        }
589        if (tile != null) {
590            invalidate();
591        }
592    }
593
594    // Draw the tile to a square at canvas that locates at (x, y) and
595    // has a side length of length.
596    private void drawTile(GLCanvas canvas,
597            int tx, int ty, int level, float x, float y, float length) {
598        RectF source = mSourceRect;
599        RectF target = mTargetRect;
600        target.set(x, y, x + length, y + length);
601        source.set(0, 0, mTileSize, mTileSize);
602
603        Tile tile = getTile(tx, ty, level);
604        if (tile != null) {
605            if (!tile.isContentValid()) {
606                if (tile.mTileState == STATE_DECODED) {
607                    if (mUploadQuota > 0) {
608                        --mUploadQuota;
609                        tile.updateContent(canvas);
610                    } else {
611                        mRenderComplete = false;
612                    }
613                } else if (tile.mTileState != STATE_DECODE_FAIL){
614                    mRenderComplete = false;
615                    queueForDecode(tile);
616                }
617            }
618            if (drawTile(tile, canvas, source, target)) {
619                return;
620            }
621        }
622        if (mPreview != null) {
623            int size = mTileSize << level;
624            float scaleX = (float) mPreview.getWidth() / mImageWidth;
625            float scaleY = (float) mPreview.getHeight() / mImageHeight;
626            source.set(tx * scaleX, ty * scaleY, (tx + size) * scaleX,
627                    (ty + size) * scaleY);
628            canvas.drawTexture(mPreview, source, target);
629        }
630    }
631
632    private boolean drawTile(
633            Tile tile, GLCanvas canvas, RectF source, RectF target) {
634        while (true) {
635            if (tile.isContentValid()) {
636                canvas.drawTexture(tile, source, target);
637                return true;
638            }
639
640            // Parent can be divided to four quads and tile is one of the four.
641            Tile parent = tile.getParentTile();
642            if (parent == null) {
643                return false;
644            }
645            if (tile.mX == parent.mX) {
646                source.left /= 2f;
647                source.right /= 2f;
648            } else {
649                source.left = (mTileSize + source.left) / 2f;
650                source.right = (mTileSize + source.right) / 2f;
651            }
652            if (tile.mY == parent.mY) {
653                source.top /= 2f;
654                source.bottom /= 2f;
655            } else {
656                source.top = (mTileSize + source.top) / 2f;
657                source.bottom = (mTileSize + source.bottom) / 2f;
658            }
659            tile = parent;
660        }
661    }
662
663    private class Tile extends UploadedTexture {
664        public int mX;
665        public int mY;
666        public int mTileLevel;
667        public Tile mNext;
668        public Bitmap mDecodedTile;
669        public volatile int mTileState = STATE_ACTIVATED;
670
671        public Tile(int x, int y, int level) {
672            mX = x;
673            mY = y;
674            mTileLevel = level;
675        }
676
677        @Override
678        protected void onFreeBitmap(Bitmap bitmap) {
679            sTilePool.release(bitmap);
680        }
681
682        boolean decode() {
683            // Get a tile from the original image. The tile is down-scaled
684            // by (1 << mTilelevel) from a region in the original image.
685            try {
686                Bitmap reuse = sTilePool.acquire();
687                if (reuse != null && reuse.getWidth() != mTileSize) {
688                    reuse = null;
689                }
690                mDecodedTile = mModel.getTile(mTileLevel, mX, mY, reuse);
691            } catch (Throwable t) {
692                Log.w(TAG, "fail to decode tile", t);
693            }
694            return mDecodedTile != null;
695        }
696
697        @Override
698        protected Bitmap onGetBitmap() {
699            Utils.assertTrue(mTileState == STATE_DECODED);
700
701            // We need to override the width and height, so that we won't
702            // draw beyond the boundaries.
703            int rightEdge = ((mImageWidth - mX) >> mTileLevel);
704            int bottomEdge = ((mImageHeight - mY) >> mTileLevel);
705            setSize(Math.min(mTileSize, rightEdge), Math.min(mTileSize, bottomEdge));
706
707            Bitmap bitmap = mDecodedTile;
708            mDecodedTile = null;
709            mTileState = STATE_ACTIVATED;
710            return bitmap;
711        }
712
713        // We override getTextureWidth() and getTextureHeight() here, so the
714        // texture can be re-used for different tiles regardless of the actual
715        // size of the tile (which may be small because it is a tile at the
716        // boundary).
717        @Override
718        public int getTextureWidth() {
719            return mTileSize;
720        }
721
722        @Override
723        public int getTextureHeight() {
724            return mTileSize;
725        }
726
727        public void update(int x, int y, int level) {
728            mX = x;
729            mY = y;
730            mTileLevel = level;
731            invalidateContent();
732        }
733
734        public Tile getParentTile() {
735            if (mTileLevel + 1 == mLevelCount) {
736                return null;
737            }
738            int size = mTileSize << (mTileLevel + 1);
739            int x = size * (mX / size);
740            int y = size * (mY / size);
741            return getTile(x, y, mTileLevel + 1);
742        }
743
744        @Override
745        public String toString() {
746            return String.format("tile(%s, %s, %s / %s)",
747                    mX / mTileSize, mY / mTileSize, mLevel, mLevelCount);
748        }
749    }
750
751    private static class TileQueue {
752        private Tile mHead;
753
754        public Tile pop() {
755            Tile tile = mHead;
756            if (tile != null) {
757                mHead = tile.mNext;
758            }
759            return tile;
760        }
761
762        public boolean push(Tile tile) {
763            if (contains(tile)) {
764                Log.w(TAG, "Attempting to add a tile already in the queue!");
765                return false;
766            }
767            boolean wasEmpty = mHead == null;
768            tile.mNext = mHead;
769            mHead = tile;
770            return wasEmpty;
771        }
772
773        private boolean contains(Tile tile) {
774            Tile other = mHead;
775            while (other != null) {
776                if (other == tile) {
777                    return true;
778                }
779                other = other.mNext;
780            }
781            return false;
782        }
783
784        public void clean() {
785            mHead = null;
786        }
787    }
788
789    private class TileDecoder extends Thread {
790
791        public void finishAndWait() {
792            interrupt();
793            try {
794                join();
795            } catch (InterruptedException e) {
796                Log.w(TAG, "Interrupted while waiting for TileDecoder thread to finish!");
797            }
798        }
799
800        private Tile waitForTile() throws InterruptedException {
801            synchronized (mQueueLock) {
802                while (true) {
803                    Tile tile = mDecodeQueue.pop();
804                    if (tile != null) {
805                        return tile;
806                    }
807                    mQueueLock.wait();
808                }
809            }
810        }
811
812        @Override
813        public void run() {
814            try {
815                while (!isInterrupted()) {
816                    Tile tile = waitForTile();
817                    decodeTile(tile);
818                }
819            } catch (InterruptedException ex) {
820                // We were finished
821            }
822        }
823
824    }
825}
826