// Copyright (C) 2003 Adam Megacz <adam@xwt.org> all rights reserved.
//
// You may modify, copy, and redistribute this code under the terms of
// the GNU Library Public License version 2.1, with the exception of
// the portion of clause 6a after the semicolon (aka the "obnoxious
// relink clause")

package org.xwt.util;

import java.util.*;

/** 
 *  A general-purpose data structure for holding a list of rectangular
 *  regions that need to be repainted, with intelligent coalescing.
 *
 *  DirtyList will unify two regions A and B if the smallest rectangle
 *  enclosing both A and B occupies no more than epsilon + Area_A +
 *  Area_B. Failing this, if two corners of A fall within B, A will be
 *  shrunk to exclude the union of A and B.
 */
public class DirtyList {

    public DirtyList() { }
    
    /** The dirty regions (each one is an int[4]). */
    private int[][] dirties = new int[10][];

    /** The number of dirty regions */
    private int numdirties = 0;

    /** See class comment */
    private static final int epsilon = 50 * 50;

    public int num() { return numdirties; }
    
    /** grows the array */
    private void grow() {
        int[][] newdirties = new int[dirties.length * 2][];
        System.arraycopy(dirties, 0, newdirties, 0, numdirties);
        dirties = newdirties;
    }

    /** Add a new rectangle to the dirty list; returns false if the
     *  region fell completely within an existing rectangle or set of
     *  rectangles (ie did not expand the dirty area)
     */
    public synchronized boolean dirty(int x, int y, int w, int h) {
        if (numdirties == dirties.length) grow();

        // we attempt the "lossless" combinations first
        for(int i=0; i<numdirties; i++) {
            int[] cur = dirties[i];

            // new region falls completely within existing region
            if (x >= cur[0] && y >= cur[1] && x + w <= cur[0] + cur[2] && y + h <= cur[1] + cur[3]) {
                return false;

            // existing region falls completely within new region
            } else if (x <= cur[0] && y <= cur[1] && x + w >= cur[0] + cur[2] && y + h >= cur[1] + cur[3]) {
                dirties[i][2] = 0;
                dirties[i][3] = 0;

            // left end of new region falls within existing region
            } else if (x >= cur[0] && x < cur[0] + cur[2] && y >= cur[1] && y + h <= cur[1] + cur[3]) {
                w = x + w - (cur[0] + cur[2]);
                x = cur[0] + cur[2];
                i = -1; continue;
                
            // right end of new region falls within existing region
            } else if (x + w > cur[0] && x + w <= cur[0] + cur[2] && y >= cur[1] && y + h <= cur[1] + cur[3]) {
                w = cur[0] - x;
                i = -1; continue;
                
            // top end of new region falls within existing region
            } else if (x >= cur[0] && x + w <= cur[0] + cur[2] && y >= cur[1] && y < cur[1] + cur[3]) {
                h = y + h - (cur[1] + cur[3]);
                y = cur[1] + cur[3];
                i = -1; continue;
                
            // bottom end of new region falls within existing region
            } else if (x >= cur[0] && x + w <= cur[0] + cur[2] && y + h > cur[1] && y + h <= cur[1] + cur[3]) {
                h = cur[1] - y;
                i = -1; continue;
                
            // left end of existing region falls within new region
            } else if (dirties[i][0] >= x && dirties[i][0] < x + w && dirties[i][1] >= y && dirties[i][1] + dirties[i][3] <= y + h) {
                dirties[i][2] = dirties[i][2] - (x + w - dirties[i][0]);
                dirties[i][0] = x + w;
                i = -1; continue;
                
            // right end of existing region falls within new region
            } else if (dirties[i][0] + dirties[i][2] > x && dirties[i][0] + dirties[i][2] <= x + w &&
                       dirties[i][1] >= y && dirties[i][1] + dirties[i][3] <= y + h) {
                dirties[i][2] = x - dirties[i][0];
                i = -1; continue;
                
            // top end of existing region falls within new region
            } else if (dirties[i][0] >= x && dirties[i][0] + dirties[i][2] <= x + w && dirties[i][1] >= y && dirties[i][1] < y + h) {
                dirties[i][3] = dirties[i][3] - (y + h - dirties[i][1]);
                dirties[i][1] = y + h;
                i = -1; continue;
                
            // bottom end of existing region falls within new region
            } else if (dirties[i][0] >= x && dirties[i][0] + dirties[i][2] <= x + w &&
                       dirties[i][1] + dirties[i][3] > y && dirties[i][1] + dirties[i][3] <= y + h) {
                dirties[i][3] = y - dirties[i][1];
                i = -1; continue;
            }

        }

        // then we attempt the "lossy" combinations
        for(int i=0; i<numdirties; i++) {
            int[] cur = dirties[i];
            if (w > 0 && h > 0 && cur[2] > 0 && cur[3] > 0 &&
                ((max(x + w, cur[0] + cur[2]) - min(x, cur[0])) *
                 (max(y + h, cur[1] + cur[3]) - min(y, cur[1])) <
                 w * h + cur[2] * cur[3] + epsilon)) {
                int a = min(cur[0], x);
                int b = min(cur[1], y);
                int c = max(x + w, cur[0] + cur[2]) - min(cur[0], x);
                int d = max(y + h, cur[1] + cur[3]) - min(cur[1], y);
                dirties[i][2] = 0;
                dirties[i][3] = 0;
                return dirty(a, b, c, d);
            }
        }

        dirties[numdirties++] = new int[] { x, y, w, h };
        return true;
    }

    /** Returns true if there are no regions that need repainting */
    public boolean empty() { return (numdirties == 0); }
    
    /**
     *  Atomically returns the list of dirty rectangles as an array of
     *  four-int arrays and clears the internal dirty-rectangle
     *  list. Note that some of the regions returned may be null, or
     *  may have zero height or zero width, and do not need to be
     *  repainted.
     */
    public synchronized int[][] flush() {
        if (numdirties == 0) return null;
        int[][] ret = dirties;
        for(int i=numdirties; i<ret.length; i++) ret[i] = null;
        dirties = new int[dirties.length][];
        numdirties = 0;
        return ret;
    }

    /** included here so that it can be inlined */
    private static final int min(int a, int b) {
        if (a<b) return a;
        else return b;
    }
    
    /** included here so that it can be inlined */
    private static final int max(int a, int b) {
        if (a>b) return a;
        else return b;
    }
    
    /** included here so that it can be inlined */
    private static final int min(int a, int b, int c) {
        if (a<=b && a<=c) return a;
        else if (b<=c && b<=a) return b;
        else return c;
    }
    
    /** included here so that it can be inlined */
    private static final int max(int a, int b, int c) {
        if (a>=b && a>=c) return a;
        else if (b>=c && b>=a) return b;
        else return c;
    }
    
    /** included here so that it can be inlined */
    private static final int bound(int a, int b, int c) {
        if (a > b) return a;
        if (c < b) return c;
        return b;
    }

}