1 // Copyright 2000-2005 the Contributors, as shown in the revision logs.
2 // Licensed under the Apache Public Source License 2.0 ("the License").
3 // You may not use this file except in compliance with the License.
8 * A general-purpose data structure for holding a list of rectangular
9 * regions that need to be repainted, with intelligent coalescing.
11 * DirtyList will unify two regions A and B if the smallest rectangle
12 * enclosing both A and B occupies no more than epsilon + Area_A +
13 * Area_B. Failing this, if two corners of A fall within B, A will be
14 * shrunk to exclude the union of A and B.
16 public class DirtyList {
18 /** The dirty regions (each one is an int[4]). */
19 private int[][] dirties = new int[10][];
21 /** The number of dirty regions */
22 private int numdirties = 0;
24 /** See class comment */
25 private static final int epsilon = 50 * 50;
27 public int num() { return numdirties; }
29 /** grows the array */
31 int[][] newdirties = new int[dirties.length * 2][];
32 System.arraycopy(dirties, 0, newdirties, 0, numdirties);
36 /** Add a new rectangle to the dirty list; returns false if the
37 * region fell completely within an existing rectangle or set of
38 * rectangles (ie did not expand the dirty area)
40 public synchronized boolean dirty(int x, int y, int w, int h) {
41 if (numdirties == dirties.length) grow();
43 // we attempt the "lossless" combinations first
44 for(int i=0; i<numdirties; i++) {
45 int[] cur = dirties[i];
47 // new region falls completely within existing region
48 if (x >= cur[0] && y >= cur[1] && x + w <= cur[0] + cur[2] && y + h <= cur[1] + cur[3]) {
51 // existing region falls completely within new region
52 } else if (x <= cur[0] && y <= cur[1] && x + w >= cur[0] + cur[2] && y + h >= cur[1] + cur[3]) {
56 // left end of new region falls within existing region
57 } else if (x >= cur[0] && x < cur[0] + cur[2] && y >= cur[1] && y + h <= cur[1] + cur[3]) {
58 w = x + w - (cur[0] + cur[2]);
62 // right end of new region falls within existing region
63 } else if (x + w > cur[0] && x + w <= cur[0] + cur[2] && y >= cur[1] && y + h <= cur[1] + cur[3]) {
67 // top end of new region falls within existing region
68 } else if (x >= cur[0] && x + w <= cur[0] + cur[2] && y >= cur[1] && y < cur[1] + cur[3]) {
69 h = y + h - (cur[1] + cur[3]);
73 // bottom end of new region falls within existing region
74 } else if (x >= cur[0] && x + w <= cur[0] + cur[2] && y + h > cur[1] && y + h <= cur[1] + cur[3]) {
78 // left end of existing region falls within new region
79 } else if (dirties[i][0] >= x && dirties[i][0] < x + w && dirties[i][1] >= y && dirties[i][1] + dirties[i][3] <= y + h) {
80 dirties[i][2] = dirties[i][2] - (x + w - dirties[i][0]);
81 dirties[i][0] = x + w;
84 // right end of existing region falls within new region
85 } else if (dirties[i][0] + dirties[i][2] > x && dirties[i][0] + dirties[i][2] <= x + w &&
86 dirties[i][1] >= y && dirties[i][1] + dirties[i][3] <= y + h) {
87 dirties[i][2] = x - dirties[i][0];
90 // top end of existing region falls within new region
91 } else if (dirties[i][0] >= x && dirties[i][0] + dirties[i][2] <= x + w && dirties[i][1] >= y && dirties[i][1] < y + h) {
92 dirties[i][3] = dirties[i][3] - (y + h - dirties[i][1]);
93 dirties[i][1] = y + h;
96 // bottom end of existing region falls within new region
97 } else if (dirties[i][0] >= x && dirties[i][0] + dirties[i][2] <= x + w &&
98 dirties[i][1] + dirties[i][3] > y && dirties[i][1] + dirties[i][3] <= y + h) {
99 dirties[i][3] = y - dirties[i][1];
105 // then we attempt the "lossy" combinations
106 for(int i=0; i<numdirties; i++) {
107 int[] cur = dirties[i];
108 if (w > 0 && h > 0 && cur[2] > 0 && cur[3] > 0 &&
109 ((max(x + w, cur[0] + cur[2]) - min(x, cur[0])) *
110 (max(y + h, cur[1] + cur[3]) - min(y, cur[1])) <
111 w * h + cur[2] * cur[3] + epsilon)) {
112 int a = min(cur[0], x);
113 int b = min(cur[1], y);
114 int c = max(x + w, cur[0] + cur[2]) - min(cur[0], x);
115 int d = max(y + h, cur[1] + cur[3]) - min(cur[1], y);
118 return dirty(a, b, c, d);
122 dirties[numdirties++] = new int[] { x, y, w, h };
126 /** Returns true if there are no regions that need repainting */
127 public boolean empty() { return (numdirties == 0); }
130 * Atomically returns the list of dirty rectangles as an array of
131 * four-int arrays and clears the internal dirty-rectangle
132 * list. Note that some of the regions returned may be null, or
133 * may have zero height or zero width, and do not need to be
136 public synchronized int[][] flush() {
137 if (numdirties == 0) return null;
138 int[][] ret = dirties;
139 for(int i=numdirties; i<ret.length; i++) ret[i] = null;
140 dirties = new int[dirties.length][];
145 /** included here so that it can be inlined */
146 private static final int min(int a, int b) {
151 /** included here so that it can be inlined */
152 private static final int max(int a, int b) {
157 /** included here so that it can be inlined */
158 private static final int min(int a, int b, int c) {
159 if (a<=b && a<=c) return a;
160 else if (b<=c && b<=a) return b;
164 /** included here so that it can be inlined */
165 private static final int max(int a, int b, int c) {
166 if (a>=b && a>=c) return a;
167 else if (b>=c && b>=a) return b;
171 /** included here so that it can be inlined */
172 private static final int bound(int a, int b, int c) {