libjava/classpath/gnu/java/awt/java2d/PixelCoverage.java

   1 package gnu.java.awt.java2d;
   2
   3 /**
   4  * Stores and handles the pixel converage for a scanline. The pixel coverage
   5  * is stored as sorted list of buckets, each of which holds information about
   6  * the coverage for the X and Y axis. This is utilized to compute the actual
   7  * coverage for each pixel on the scanline and finding chunks of pixels with
   8  * equal coverage.
   9  */
  10 final class PixelCoverage
  11 {
  12
  13   /**
  14    * One bucket in the list.
  15    */
  16   private static final class Bucket
  17   {
  18     /**
  19      * The X coordinate on the scanline to which this bucket belongs.
  20      */
  21     int xPos;
  22
  23     /**
  24      * The X coverage.
  25      */
  26     int xCov;
  27
  28     /**
  29      * The Y coverage.
  30      */
  31     int yCov;
  32
  33     /**
  34      * Implements a linked list. This points to the next element of the list.
  35      */
  36     Bucket next;
  37
  38     /**
  39      * Implements a linked list. This points to the previous element of the
  40      * list.
  41      */
  42     Bucket prev;
  43   }
  44
  45   /**
  46    * The head of the sorted list of buckets.
  47    */
  48   private Bucket head;
  49
  50   /**
  51    * The current bucket. We make use of the fact that the scanline converter
  52    * always scans the scanline (and thus this list) from left to right to
  53    * quickly find buckets or insertion points.
  54    */
  55   private Bucket current;
  56
  57   /**
  58    * The bucket after the last valid bucket. Unused buckets are not thrown
  59    * away and garbage collected. Instead, we keep them at the tail of the list
  60    * and reuse them when necessary.
  61    */
  62   private Bucket last;
  63
  64   /**
  65    * Indicates the the next scan of the scanline begins and that the next
  66    * request will be at the beginning of this list. This makes searching and
  67    * sorting of this list very quick.
  68    */
  69   void rewind()
  70   {
  71     current = head;
  72   }
  73
  74   /**
  75    * Clears the list. This does not throw away the old buckets but only
  76    * resets the end-pointer of the list to the first element. All buckets are
  77    * then unused and are reused when the list is filled again.
  78    */
  79   void clear()
  80   {
  81     last = head;
  82   }
  83
  84   /**
  85    * This adds the specified x and y coverage to the pixel at the specified
  86    * X position.
  87    *
  88    * @param x the X position
  89    * @param xc the x coverage
  90    * @param yc the y coverage
  91    */
  92   void add(int x, int xc, int yc)
  93   {
  94     Bucket bucket = findOrInsert(x);
  95     bucket.xCov += xc;
  96     bucket.yCov += yc;
  97   }
  98
  99   /**
 100    * Finds the bucket in the list with the specified X coordinate.
 101    * If no such bucket is found, then a new one is fetched (either a cached
 102    * bucket from the end of the list or a newly allocated one) inserted at the
 103    * correct position and returned.
 104    *
 105    * @param x the X coordinate
 106    *
 107    * @return a bucket to hold the coverage data
 108    */
 109   private Bucket findOrInsert(int x)
 110   {
 111     // First search for a matching bucket.
 112     if (head == null)
 113       {
 114         // Special case: the list is still empty.
 115         head = new Bucket();
 116         current = head;
 117         return head;
 118       }
 119
 120     // This performs a linear search, starting from the current bucket.
 121     // This is reasonably efficient because access to this list is always done
 122     // in a linear fashion and we are not more then 1 or 2 buckets away from
 123     // the one we're looking for.
 124     Bucket match = current;
 125     while (match != null && match.xPos != x)
 126       {
 127
 128       }
 129
 130     return match;
 131   }
 132 }