src/org/ibex/util/DirtyList.java

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