/*
 * Copyright (c) 2006, 2013, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

package com.sun.prism.impl.packrect;

import com.sun.javafx.geom.Rectangle;
import com.sun.prism.Texture;
import java.util.ArrayList;
import java.util.List;

/**
 * Packs rectangles supplied by the user (typically representing image regions)
 * into a larger backing store rectangle (typically representing a large
 * texture). Supports automatic compaction of the space on the backing store,
 * and automatic expansion of the backing store, when necessary.
 */
public class TexturesPacker {
    /**
     * A reference to the backing store that was created (lazily)
     * by the backing store manager.
     */
    private Texture backingStore;

    /** Manages a list of Levels; this is the core data structure
     contained within the RectanglePacker and encompasses the storage
     algorithm for the contained Rects. */
    // Maintained in sorted order by increasing Y coordinate
    private List<Level> levels = new ArrayList<Level>(150);
    private static final int MIN_HEIGHT = 8; // The minimum height of level
    private static final int ROUND_UP = 4; // Round up to multiple of 4
    private int recentUsedLevelIndex = 0;
    private int nextAddY;
    private int w;
    private int h;

    /**
     * Creates a new RectanglePacker. You must specify the texture used as the
     * backing store, and the width and height of the space within which rectangles
     * are to be packed.
     *
     * @param backingStore The backing store texture, must not be null
     * @param width The width of the backing store, must be > 0 (typically > 512)
     * @param height The height of the backing store, must be > 0 (typically > 512)
     */
    public TexturesPacker(Texture backingStore, int width, int height) {
        this.backingStore = backingStore;
        this.w = width;
        this.h = height;
    }

    /**
     * Gets a reference to the backing store, creating it lazily if necessary.
     * @return A reference to the backing store.
     */
    public final Texture getBackingStore() {
        return backingStore;
    }

    /**
     * Decides upon an (x, y) position for the given rectangle (leaving
     * its width and height unchanged) and places it on the backing
     * store.
     */
    public final boolean add(Rectangle rect) {
        // N need to continue if the rectangle simply won't fit.
        if (rect.width > w) return false;

        int newHeight = MIN_HEIGHT > rect.height ? MIN_HEIGHT : rect.height;

        // Round up
        int roundUp = newHeight < 32 ? ROUND_UP : newHeight < 64 ? ROUND_UP * 4 : ROUND_UP * 8;
        newHeight = (newHeight + roundUp - 1) - (newHeight - 1) % roundUp;

        int newIndex;
        // If it does not match recent used level, using binary search to find
        // the best fit level's index
        if (recentUsedLevelIndex < levels.size()
                && levels.get(recentUsedLevelIndex).height != newHeight) {
            newIndex = binarySearch(levels, newHeight);
        } else {
            newIndex = recentUsedLevelIndex;
        }

        // Can create a new level with newHeight
        boolean newLevelFlag = nextAddY + newHeight <= h;

        // Go through the levels check whether we can satisfy the allocation
        // request
        for (int i = newIndex, max = levels.size(); i < max; i++) {
            Level level = levels.get(i);
            // If level's height is more than (newHeight + ROUND_UP * 2) and
            // the cache still has some space left, go create a new level
            if (level.height > (newHeight + roundUp * 2) && newLevelFlag) {
                break;
            } else if (level.add(rect)) {
                recentUsedLevelIndex = i;
                return true;
            }
        }

        // Try to add a new Level.
        if (!newLevelFlag) {
            return false;
        }

        Level newLevel = new Level(w, newHeight, nextAddY);
        nextAddY += newHeight;

        // For a rect that cannot fit into the existing level, create a new
        // level and add at the end of levels that have the same height
        if (newIndex < levels.size() && levels.get(newIndex).height <= newHeight) {
            levels.add(newIndex + 1, newLevel);
            recentUsedLevelIndex = newIndex + 1;
        } else {
            levels.add(newIndex, newLevel);
            recentUsedLevelIndex = newIndex;
        }
        return newLevel.add(rect);
    }

    /**
     * Clears all Rectangles contained in this RectanglePacker.
     */
    public void clear() {
        levels.clear();
        nextAddY = 0;
        recentUsedLevelIndex = 0;
    }

    /**
     * Disposes the backing store allocated by the
     * BackingStoreManager. This RectanglePacker may no longer be used
     * after calling this method.
     */
    public void dispose() {
        if (backingStore != null) {
            backingStore.dispose();
        }

        backingStore = null;
        levels = null;
    }

    /** Using binary search to find the last index of best fit level for k,
     where k is a rounded-up value. */
    private static int binarySearch(List<Level> levels, int k) {

        // k+1 is used to find the last index of the level with height of k. Because of rounding up, more
        // likely, there are a bunch of levels have the same height. But, we always keep adding levels and
        // rects at the end. k+1 is a trick to find the last index by finding the next greater value's index
        // and go back one.
        int key = k + 1;
        int from = 0, to = levels.size() - 1;
        int mid = 0;
        int height = 0;

        if (to < 0) {
            return 0;
        }

        while (from <= to) {
            mid = (from + to) / 2;
            height = levels.get(mid).height;
            if (key < height) {
                to = mid - 1;
            } else {
                from = mid + 1;
            }
        }

        if (height < k) {
            return mid + 1;
        } else if (height > k) {
            return mid > 0 ? mid - 1 : 0;
        } else {
            return mid;
        }
    }
}