src/org/ibex/util/DirtyList.java

   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.
   4
   5 package org.ibex.util;
   6
   7 /**
   8  *  A general-purpose data structure for holding a list of rectangular
   9  *  regions that need to be repainted, with intelligent coalescing.
  10  *
  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.
  15  */
  16 public class DirtyList {
  17
  18     /** The dirty regions (each one is an int[4]). */
  19     private int[][] dirties = new int[10][];
  20
  21     /** The number of dirty regions */
  22     private int numdirties = 0;
  23
  24     /** See class comment */
  25     private static final int epsilon = 50 * 50;
  26
  27     public int num() { return numdirties; }
  28
  29     /** grows the array */
  30     private void grow() {
  31         int[][] newdirties = new int[dirties.length * 2][];
  32         System.arraycopy(dirties, 0, newdirties, 0, numdirties);
  33         dirties = newdirties;
  34     }
  35
  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)
  39      */
  40     public synchronized boolean dirty(int x, int y, int w, int h) {
  41         if (numdirties == dirties.length) grow();
  42
  43         // we attempt the "lossless" combinations first
  44         for(int i=0; i<numdirties; i++) {
  45             int[] cur = dirties[i];
  46
  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]) {
  49                 return false;
  50
  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]) {
  53                 dirties[i][2] = 0;
  54                 dirties[i][3] = 0;
  55
  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]);
  59                 x = cur[0] + cur[2];
  60                 i = -1; continue;
  61
  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]) {
  64                 w = cur[0] - x;
  65                 i = -1; continue;
  66
  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]);
  70                 y = cur[1] + cur[3];
  71                 i = -1; continue;
  72
  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]) {
  75                 h = cur[1] - y;
  76                 i = -1; continue;
  77
  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;
  82                 i = -1; continue;
  83
  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];
  88                 i = -1; continue;
  89
  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;
  94                 i = -1; continue;
  95
  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];
 100                 i = -1; continue;
 101             }
 102
 103         }
 104
 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);
 116                 dirties[i][2] = 0;
 117                 dirties[i][3] = 0;
 118                 return dirty(a, b, c, d);
 119             }
 120         }
 121
 122         dirties[numdirties++] = new int[] { x, y, w, h };
 123         return true;
 124     }
 125
 126     /** Returns true if there are no regions that need repainting */
 127     public boolean empty() { return (numdirties == 0); }
 128
 129     /**
 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
 134      *  repainted.
 135      */
 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][];
 141         numdirties = 0;
 142         return ret;
 143     }
 144
 145     /** included here so that it can be inlined */
 146     private static final int min(int a, int b) {
 147         if (a<b) return a;
 148         else return b;
 149     }
 150
 151     /** included here so that it can be inlined */
 152     private static final int max(int a, int b) {
 153         if (a>b) return a;
 154         else return b;
 155     }
 156
 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;
 161         else return c;
 162     }
 163
 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;
 168         else return c;
 169     }
 170
 171     /** included here so that it can be inlined */
 172     private static final int bound(int a, int b, int c) {
 173         if (a > b) return a;
 174         if (c < b) return c;
 175         return b;
 176     }
 177
 178 }