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

   1 /* ActiveEdges.java -- A collection of active edges for scanline conversion
   2    Copyright (C) 2006 Free Software Foundation, Inc.
   3
   4 This file is part of GNU Classpath.
   5
   6 GNU Classpath is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU Classpath is distributed in the hope that it will be useful, but
  12 WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU Classpath; see the file COPYING.  If not, write to the
  18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301 USA.
  20
  21 Linking this library statically or dynamically with other modules is
  22 making a combined work based on this library.  Thus, the terms and
  23 conditions of the GNU General Public License cover the whole
  24 combination.
  25
  26 As a special exception, the copyright holders of this library give you
  27 permission to link this library with independent modules to produce an
  28 executable, regardless of the license terms of these independent
  29 modules, and to copy and distribute the resulting executable under
  30 terms of your choice, provided that you also meet, for each linked
  31 independent module, the terms and conditions of the license of that
  32 module.  An independent module is a module which is not derived from
  33 or based on this library.  If you modify this library, you may extend
  34 this exception to your version of the library, but you are not
  35 obligated to do so.  If you do not wish to do so, delete this
  36 exception statement from your version. */
  37
  38
  39 package gnu.java.awt.java2d;
  40
  41 /**
  42  * A collection of active edges for scanline conversion.
  43  */
  44 final class ActiveEdges
  45 {
  46
  47   /**
  48    * The active edges. This can contain null values at arbirary locations.
  49    * The method #sort() packs this together.
  50    */
  51   private PolyEdge[] activeEdges;
  52
  53   /**
  54    * The actual number of active edges. The array can be bigger than this
  55    * number.
  56    */
  57   private int numActiveEdges;
  58
  59   /**
  60    * Creates a new ActiveEdges object.
  61    */
  62   ActiveEdges()
  63   {
  64     activeEdges = new PolyEdge[8];
  65     numActiveEdges = 0;
  66   }
  67
  68   /**
  69    * Clears out all active edges. This is cheap as it simply resets the
  70    * counter to 0. It does not release all references to PolyEdge instances.
  71    */
  72   void clear()
  73   {
  74     numActiveEdges = 0;
  75   }
  76
  77   /**
  78    * Adds the specified edge to the list of active edges. This does not yet
  79    * sort the edges and therefore does destroy any order of the list.
  80    *
  81    * @param edge the edge to add
  82    */
  83   void add(PolyEdge edge)
  84   {
  85     // Grow array when necessary.
  86     int oldSize = activeEdges.length;
  87     if (numActiveEdges >= oldSize)
  88       {
  89         int newSize = oldSize + oldSize / 4 + 1;
  90         PolyEdge[] newEdges = new PolyEdge[newSize];
  91         System.arraycopy(activeEdges, 0, newEdges, 0, oldSize);
  92         activeEdges = newEdges;
  93       }
  94     activeEdges[numActiveEdges] = edge;
  95     numActiveEdges++;
  96   }
  97
  98   /**
  99    * Intersects all active edges, sorts them according to their intersection
 100    * points and packs the array to remove unneeded edges. This does also
 101    * remove any edges that do not intersect the scanline (i.e. they end above
 102    * of the scanline).
 103    *
 104    * @param y the scanline height
 105    */
 106   void intersectSortAndPack(int n, int y)
 107   {
 108     // Intersect and pack in one go.
 109     int last = 0;
 110     PolyEdge tmp;
 111     for (int i = 0; i < numActiveEdges; i++)
 112       {
 113         PolyEdge edge = activeEdges[i];
 114         // Clear out edge that ends above the scanline.
 115         if (edge != null && edge.y1 >= y)
 116           {
 117             assert edge.y1 >= y && edge.y0 <= y : "edge must cross scanline";
 118             edge.intersect(n, y);
 119             activeEdges[last] = edge;
 120             last++;
 121
 122             // Bubble up the added edge.
 123             for (int j = last - 1; j > 0; j--)
 124               {
 125                 if (activeEdges[j].xIntersection
 126                     < activeEdges[j - 1].xIntersection)
 127                   {
 128                     tmp = activeEdges[j];
 129                     activeEdges[j] = activeEdges[j - 1];
 130                     activeEdges[j - 1] = tmp;
 131                   }
 132                 else
 133                   {
 134                     // The beginning of the list is already sorted.
 135                     break;
 136                   }
 137               }
 138           }
 139       }
 140     numActiveEdges = last;
 141
 142   }
 143
 144   /**
 145    * Returns the number of active edges. This is only reliable after a
 146    * call to {@link #intersectSortAndPack(int, int)}.
 147    *
 148    * @return the number of active edges
 149    */
 150   int getNumActiveEdges()
 151   {
 152     return numActiveEdges;
 153   }
 154
 155   /**
 156    * Returns the active edge at the position <code>i</code>.
 157    *
 158    * @param i the index
 159    *
 160    * @return the active edge at the specified index
 161    */
 162   PolyEdge getActiveEdge(int i)
 163   {
 164     return activeEdges[i];
 165   }
 166
 167   /**
 168    * Removes all edges that end above the specified height.
 169    *
 170    * @param y the cut-off height
 171    */
 172   void remove(int y)
 173   {
 174     for (int i = 0; i < numActiveEdges; i++)
 175       {
 176         PolyEdge edge = activeEdges[i];
 177         if (edge != null && edge.y1 < y)
 178           {
 179             activeEdges[i] = null;
 180           }
 181       }
 182   }
 183
 184   public String toString()
 185   {
 186     StringBuilder s = new StringBuilder();
 187     s.append("[ActiveEdges] ");
 188     for (int i = 0; i < numActiveEdges; i++)
 189       {
 190         s.append(activeEdges[i]);
 191         s.append(',');
 192       }
 193     return s.toString();
 194   }
 195 }