src/org/xwt/util/DirtyList.java

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