src/org/xwt/util/DirtyList.java

   1 // Copyright (C) 2003 Adam Megacz <adam@xwt.org> all rights reserved.
   2 //
   3 // You may modify, copy, and redistribute this code under the terms of
   4 // the GNU Library Public License version 2.1, with the exception of
   5 // the portion of clause 6a after the semicolon (aka the "obnoxious
   6 // relink clause")
   7
   8 package org.xwt.util;
   9
  10 import java.util.*;
  11
  12 /**
  13  *  A general-purpose data structure for holding a list of rectangular
  14  *  regions that need to be repainted, with intelligent coalescing.
  15  *
  16  *  DirtyList will unify two regions A and B if the smallest rectangle
  17  *  enclosing both A and B occupies no more than epsilon + Area_A +
  18  *  Area_B. Failing this, if two corners of A fall within B, A will be
  19  *  shrunk to exclude the union of A and B.
  20  */
  21 public class DirtyList {
  22
  23     public DirtyList() { }
  24
  25     /** The dirty regions (each one is an int[4]). */
  26     private int[][] dirties = new int[10][];
  27
  28     /** The number of dirty regions */
  29     private int numdirties = 0;
  30
  31     /** See class comment */
  32     private static final int epsilon = 50 * 50;
  33
  34     public int num() { return numdirties; }
  35
  36     /** grows the array */
  37     private void grow() {
  38         int[][] newdirties = new int[dirties.length * 2][];
  39         System.arraycopy(dirties, 0, newdirties, 0, numdirties);
  40         dirties = newdirties;
  41     }
  42
  43     /** Add a new rectangle to the dirty list; returns false if the
  44      *  region fell completely within an existing rectangle or set of
  45      *  rectangles (ie did not expand the dirty area)
  46      */
  47     public synchronized boolean dirty(int x, int y, int w, int h) {
  48         if (numdirties == dirties.length) grow();
  49
  50         // we attempt the "lossless" combinations first
  51         for(int i=0; i<numdirties; i++) {
  52             int[] cur = dirties[i];
  53
  54             // new region falls completely within existing region
  55             if (x >= cur[0] && y >= cur[1] && x + w <= cur[0] + cur[2] && y + h <= cur[1] + cur[3]) {
  56                 return false;
  57
  58             // existing region falls completely within new region
  59             } else if (x <= cur[0] && y <= cur[1] && x + w >= cur[0] + cur[2] && y + h >= cur[1] + cur[3]) {
  60                 dirties[i][2] = 0;
  61                 dirties[i][3] = 0;
  62
  63             // left end of new region falls within existing region
  64             } else if (x >= cur[0] && x < cur[0] + cur[2] && y >= cur[1] && y + h <= cur[1] + cur[3]) {
  65                 w = x + w - (cur[0] + cur[2]);
  66                 x = cur[0] + cur[2];
  67                 i = -1; continue;
  68
  69             // right end of new region falls within existing region
  70             } else if (x + w > cur[0] && x + w <= cur[0] + cur[2] && y >= cur[1] && y + h <= cur[1] + cur[3]) {
  71                 w = cur[0] - x;
  72                 i = -1; continue;
  73
  74             // top end of new region falls within existing region
  75             } else if (x >= cur[0] && x + w <= cur[0] + cur[2] && y >= cur[1] && y < cur[1] + cur[3]) {
  76                 h = y + h - (cur[1] + cur[3]);
  77                 y = cur[1] + cur[3];
  78                 i = -1; continue;
  79
  80             // bottom end of new region falls within existing region
  81             } else if (x >= cur[0] && x + w <= cur[0] + cur[2] && y + h > cur[1] && y + h <= cur[1] + cur[3]) {
  82                 h = cur[1] - y;
  83                 i = -1; continue;
  84
  85             // left end of existing region falls within new region
  86             } else if (dirties[i][0] >= x && dirties[i][0] < x + w && dirties[i][1] >= y && dirties[i][1] + dirties[i][3] <= y + h) {
  87                 dirties[i][2] = dirties[i][2] - (x + w - dirties[i][0]);
  88                 dirties[i][0] = x + w;
  89                 i = -1; continue;
  90
  91             // right end of existing region falls within new region
  92             } else if (dirties[i][0] + dirties[i][2] > x && dirties[i][0] + dirties[i][2] <= x + w &&
  93                        dirties[i][1] >= y && dirties[i][1] + dirties[i][3] <= y + h) {
  94                 dirties[i][2] = x - dirties[i][0];
  95                 i = -1; continue;
  96
  97             // top end of existing region falls within new region
  98             } else if (dirties[i][0] >= x && dirties[i][0] + dirties[i][2] <= x + w && dirties[i][1] >= y && dirties[i][1] < y + h) {
  99                 dirties[i][3] = dirties[i][3] - (y + h - dirties[i][1]);
 100                 dirties[i][1] = y + h;
 101                 i = -1; continue;
 102
 103             // bottom end of existing region falls within new region
 104             } else if (dirties[i][0] >= x && dirties[i][0] + dirties[i][2] <= x + w &&
 105                        dirties[i][1] + dirties[i][3] > y && dirties[i][1] + dirties[i][3] <= y + h) {
 106                 dirties[i][3] = y - dirties[i][1];
 107                 i = -1; continue;
 108             }
 109
 110         }
 111
 112         // then we attempt the "lossy" combinations
 113         for(int i=0; i<numdirties; i++) {
 114             int[] cur = dirties[i];
 115             if (w > 0 && h > 0 && cur[2] > 0 && cur[3] > 0 &&
 116                 ((max(x + w, cur[0] + cur[2]) - min(x, cur[0])) *
 117                  (max(y + h, cur[1] + cur[3]) - min(y, cur[1])) <
 118                  w * h + cur[2] * cur[3] + epsilon)) {
 119                 int a = min(cur[0], x);
 120                 int b = min(cur[1], y);
 121                 int c = max(x + w, cur[0] + cur[2]) - min(cur[0], x);
 122                 int d = max(y + h, cur[1] + cur[3]) - min(cur[1], y);
 123                 dirties[i][2] = 0;
 124                 dirties[i][3] = 0;
 125                 return dirty(a, b, c, d);
 126             }
 127         }
 128
 129         dirties[numdirties++] = new int[] { x, y, w, h };
 130         return true;
 131     }
 132
 133     /** Returns true if there are no regions that need repainting */
 134     public boolean empty() { return (numdirties == 0); }
 135
 136     /**
 137      *  Atomically returns the list of dirty rectangles as an array of
 138      *  four-int arrays and clears the internal dirty-rectangle
 139      *  list. Note that some of the regions returned may be null, or
 140      *  may have zero height or zero width, and do not need to be
 141      *  repainted.
 142      */
 143     public synchronized int[][] flush() {
 144         if (numdirties == 0) return null;
 145         int[][] ret = dirties;
 146         for(int i=numdirties; i<ret.length; i++) ret[i] = null;
 147         dirties = new int[dirties.length][];
 148         numdirties = 0;
 149         return ret;
 150     }
 151
 152     /** included here so that it can be inlined */
 153     private static final int min(int a, int b) {
 154         if (a<b) return a;
 155         else return b;
 156     }
 157
 158     /** included here so that it can be inlined */
 159     private static final int max(int a, int b) {
 160         if (a>b) return a;
 161         else return b;
 162     }
 163
 164     /** included here so that it can be inlined */
 165     private static final int min(int a, int b, int c) {
 166         if (a<=b && a<=c) return a;
 167         else if (b<=c && b<=a) return b;
 168         else return c;
 169     }
 170
 171     /** included here so that it can be inlined */
 172     private static final int max(int a, int b, int c) {
 173         if (a>=b && a>=c) return a;
 174         else if (b>=c && b>=a) return b;
 175         else return c;
 176     }
 177
 178     /** included here so that it can be inlined */
 179     private static final int bound(int a, int b, int c) {
 180         if (a > b) return a;
 181         if (c < b) return c;
 182         return b;
 183     }
 184
 185 }