diff options
Diffstat (limited to 'gcc-4.4.3/libjava/classpath/gnu/java/awt/java2d/ScanlineCoverage.java')
| -rw-r--r-- | gcc-4.4.3/libjava/classpath/gnu/java/awt/java2d/ScanlineCoverage.java | 630 |
1 files changed, 630 insertions, 0 deletions
diff --git a/gcc-4.4.3/libjava/classpath/gnu/java/awt/java2d/ScanlineCoverage.java b/gcc-4.4.3/libjava/classpath/gnu/java/awt/java2d/ScanlineCoverage.java new file mode 100644 index 000000000..deb603bcb --- /dev/null +++ b/gcc-4.4.3/libjava/classpath/gnu/java/awt/java2d/ScanlineCoverage.java @@ -0,0 +1,630 @@ +/* ScanlineCoverage.java -- Manages coverage information for a scanline + Copyright (C) 2007 Free Software Foundation, Inc. + +This file is part of GNU Classpath. + +GNU Classpath is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU Classpath is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Classpath; see the file COPYING. If not, write to the +Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301 USA. + +Linking this library statically or dynamically with other modules is +making a combined work based on this library. Thus, the terms and +conditions of the GNU General Public License cover the whole +combination. + +As a special exception, the copyright holders of this library give you +permission to link this library with independent modules to produce an +executable, regardless of the license terms of these independent +modules, and to copy and distribute the resulting executable under +terms of your choice, provided that you also meet, for each linked +independent module, the terms and conditions of the license of that +module. An independent module is a module which is not derived from +or based on this library. If you modify this library, you may extend +this exception to your version of the library, but you are not +obligated to do so. If you do not wish to do so, delete this +exception statement from your version. */ + +package gnu.java.awt.java2d; + +/** + * Stores and handles the pixel converage for a scanline. The pixel coverage + * is stored as sorted list of {@linke Covergage} entries, each of which holds + * information about the coverage for the X and Y axis. This is utilized to + * compute the actual coverage for each pixel on the scanline and finding + * chunks of pixels with equal coverage quickly. + */ +public final class ScanlineCoverage +{ + + /** + * Iterates over the coverage list and calculates the actual coverage + * ranges on a scanline. + */ + public final class Iterator + { + /** + * This instance is reused in the iteration. + */ + private Range range; + + /** + * The pointer to the current item in the iteration. + */ + private Coverage currentItem; + + /** + * The current coverage value. + */ + private int currentCoverage; + + /** + * True when the current pixel coverage has already been handled, false + * otherwise. + */ + private boolean handledPixelCoverage; + + /** + * Creates a new CoverageIterator. + */ + Iterator() + { + range = new Range(); + } + + /** + * Returns the next coverage range on the scanline. The returned object + * will always be the same object, but with different values. Keep that + * in mind when dealing with this object. + * + * @return the next coverage range on the scanline + */ + public Range next() + { + // TODO: Lump together the single-pixel coverage and the + // between-pixel coverage when the pixel coverage delta is 0. + if (handledPixelCoverage == false) + { + // Handle single pixel coverage. + range.setXPos(currentItem.xPos); + range.setLength(1); + range.setCoverage(currentCoverage + currentItem.pixelCoverage); + handledPixelCoverage = true; + } + else + { + // Handle pixel span coverage. + currentCoverage += currentItem.covDelta; + range.setCoverage(currentCoverage); + range.setXPos(currentItem.xPos + 1); + currentItem = currentItem.next; + range.setLength(currentItem.xPos - range.xPos); + handledPixelCoverage = false; + } + return range; + } + + /** + * Returns {@ true} when there are more coverage ranges to iterate, + * {@ false} otherwise. + * + * @return {@ true} when there are more coverage ranges to iterate, + * {@ false} otherwise + */ + public boolean hasNext() + { + boolean hasNext; + if (currentItem != null && handledPixelCoverage == false) + { + // We have at least one more coverage item when there's a pixel + // coverage piece left. + hasNext = true; + } + else if (currentItem == null || currentItem.next == null + || currentItem.next == last) + { + hasNext = false; + } + else + { + hasNext = true; + } + return hasNext; + } + + /** + * Resets this iterator to the start of the list. + */ + void reset() + { + currentItem = head; + currentCoverage = 0; + handledPixelCoverage = false; + } + } + + /** + * A data object that carries information about pixel coverage on a scanline. + * The data consists of a starting X position on the scanline, the + * length of the range in pixels and the actual coverage value. + **/ + public static final class Range + { + /** + * The X position on the scanline, in pixels. + */ + private int xPos; + + /** + * The length of the range, in pixels. + */ + private int length; + + /** + * The actual coverage. The relation depends on + * {@link ScanlineCoverage#maxCoverage}. + */ + private int coverage; + + /** + * Creates a new CoverageRange object. + */ + Range() + { + // Nothing to do. The values get initialized in the corresponding + // setters. + } + + /** + * Sets the X start position (left) on the scanline. This value is + * considered to be in pixels and device space. + * + * @param x the x position + */ + void setXPos(int x) + { + xPos = x; + } + + /** + * Returns the X start position (left) on the scanline. This value + * is considered to be in pixels and device space. + * + * @return the X position on the scanline + */ + public int getXPos() + { + return xPos; + } + + /** + * Sets the length of the pixel range. This is in pixel units. + * + * @param l the length of the range + */ + void setLength(int l) + { + length = l; + } + + /** + * Returns the length of the range in pixel units. + * + * @return the length of the range in pixel units + */ + public int getLength() + { + return length; + } + + /** + * Returns the first X position after the range. + * + * @return the first X position after the range + */ + public int getXPosEnd() + { + return xPos + length; + } + + /** + * Sets the coverage of the pixel range. The relation of that value + * depends on {@link ScanlineCoverage#maxCoverage}. + * + * @param cov the coverage value for the pixel range + */ + void setCoverage(int cov) + { + coverage = cov; + } + + /** + * Returns the coverage of the pixel range. The relation of this value + * depends on {@link ScanlineCoverage#getMaxCoverage()}. + * + * @return the coverage of the pixel range + */ + public int getCoverage() + { + return coverage; + } + + /** + * Returns a string representation. + */ + public String toString() + { + return "Coverage range: xPos=" + xPos + ", length=" + length + + ", coverage: " + coverage; + } + } + + /** + * One bucket in the list. + */ + private static final class Coverage + { + /** + * The X coordinate on the scanline to which this bucket belongs. + */ + int xPos; + + /** + * The coverage delta from the pixel at xPos to xPos + 1. + */ + int covDelta; + + /** + * The delta for the pixel at xPos. This is added to the pixel at xPos, + * but not to the following pixel. + */ + int pixelCoverage; + + /** + * Implements a linked list. This points to the next element of the list. + */ + Coverage next; + + /** + * Returns the X coordinate for this entry. + * + * @return the X coordinate for this entry + */ + public int getXPos() + { + return xPos; + } + + /** + * Returns the coverage delta for this entry. + * + * @return the coverage delta for this entry + */ + public int getCoverageDelta() + { + return covDelta; + } + + /** + * Returns a string representation. + * + * @return a string representation + */ + public String toString() + { + return "Coverage: xPos: " + xPos + ", covDelta: " + covDelta; + } + + /** + * Returns a string representation of this entry and all the following + * in the linked list. + * + * @return a string representation of this entry and all the following + * in the linked list + */ + public String list() + { + String str = toString(); + if (next != null) + str = str + " --> " + next.list(); + return str; + } + } + + /** + * The head of the sorted list of buckets. + */ + private Coverage head; + + /** + * The current bucket. We make use of the fact that the scanline converter + * always scans the scanline (and thus this list) from left to right to + * quickly find buckets or insertion points. + */ + private Coverage current; + + /** + * The item that is before current in the list. + */ + private Coverage currentPrev; + + /** + * The bucket after the last valid bucket. Unused buckets are not thrown + * away and garbage collected. Instead, we keep them at the tail of the list + * and reuse them when necessary. + */ + private Coverage last; + + /** + * The last valid entry. + */ + private Coverage lastPrev; + + /** + * The minimum X coordinate of this scanline. + */ + private int minX; + + /** + * The maximum X coordinate of this scanline. + */ + private int maxX; + + /** + * The maximum coverage value. + */ + private int maxCoverage; + + /** + * The iterator over the ranges of this scanline. + */ + private Iterator iterator; + + /** + * Creates a new ScanlineCoverage instance. + */ + public ScanlineCoverage() + { + iterator = new Iterator(); + } + + /** + * Indicates the the next scan of the scanline begins and that the next + * request will be at the beginning of this list. This makes searching and + * sorting of this list very quick. + */ + public void rewind() + { + current = head; + currentPrev = null; + } + + /** + * Clears the list. This does not throw away the old buckets but only + * resets the end-pointer of the list to the first element. All buckets are + * then unused and are reused when the list is filled again. + */ + public void clear() + { + last = head; + lastPrev = null; + current = head; + currentPrev = null; + minX = Integer.MAX_VALUE; + maxX = Integer.MIN_VALUE; + } + + /** + * This adds the specified coverage to the pixel at the specified + * X position. + * + * @param x the X position + * @param xc the x coverage + * @param yc the y coverage + */ + public void add(int x, int xc, int yc) + { + Coverage bucket = findOrInsert(x); + bucket.covDelta += xc; + bucket.pixelCoverage += yc; + minX = Math.min(minX, x); + maxX = Math.max(maxX, x); + } + + /** + * Returns the maximum coverage value for the scanline. + * + * @return the maximum coverage value for the scanline + */ + public int getMaxCoverage() + { + return maxCoverage; + } + + /** + * Sets the maximum coverage value for the scanline. + * + * @param maxCov the maximum coverage value for the scanline + */ + void setMaxCoverage(int maxCov) + { + maxCoverage = maxCov; + } + + /** + * Returns the maximum X coordinate of the current scanline. + * + * @return the maximum X coordinate of the current scanline + */ + public int getMaxX() + { + return maxX; + } + + /** + * Returns the minimum X coordinate of the current scanline. + * + * @return the minimum X coordinate of the current scanline + */ + public int getMinX() + { + return minX; + } + + /** + * Finds the bucket in the list with the specified X coordinate. + * If no such bucket is found, then a new one is fetched (either a cached + * bucket from the end of the list or a newly allocated one) inserted at the + * correct position and returned. + * + * @param x the X coordinate + * + * @return a bucket to hold the coverage data + */ + private Coverage findOrInsert(int x) + { + // First search for a matching bucket. + if (head == null) + { + // Special case: the list is still empty. + // Testpoint 1. + head = new Coverage(); + head.xPos = x; + current = head; + currentPrev = null; + return head; + } + + // This performs a linear search, starting from the current bucket. + // This is reasonably efficient because access to this list is always done + // in a linear fashion and we are usually not more then 1 or 2 buckets away + // from the one we're looking for. + Coverage match = current; + Coverage prev = currentPrev; + while (match != last && match.xPos < x) + { + prev = match; + match = match.next; + } + + // At this point we have either found an entry with xPos >= x, or reached + // the end of the list (match == last || match == null). + if (match == null) + { + // End of the list. No cached items to reuse. + // Testpoint 2. + match = new Coverage(); + match.xPos = x; + if (prev != null) + prev.next = match; + current = match; + currentPrev = prev; + return match; + } + else if (match == last) + { + // End of the list. Reuse this item. Expand list. + // Testpoint 3. + last = match.next; + lastPrev = match; + match.xPos = x; + match.covDelta = 0; + match.pixelCoverage = 0; + // Keep link to last element or null, indicating the end of the list. + current = match; + currentPrev = prev; + return match; + } + + if (x == match.xPos) + { + // Special case: We have another coverage entry at the same location + // as an already existing entry. Return this. + // Testpoint 4. + current = match; + currentPrev = prev; + return match; + } + else // x <= match.xPos + { + assert (x <= match.xPos); + assert (prev == null ||x > prev.xPos); + + // Create new entry, or reuse existing one. + Coverage cov; + if (last != null) + { + // Testpoint 5. + cov = last; + last = cov.next; + lastPrev.next = last; + } + else + { + // Testpoint 6. + cov = new Coverage(); + } + + cov.xPos = x; + cov.covDelta = 0; + cov.pixelCoverage = 0; + + // Insert this item in the list. + if (prev != null) + { + // Testpoint 5 & 6. + prev.next = cov; + cov.next = match; + current = cov; + currentPrev = prev; + } + else + { + // Testpoint 7. + assert (match == head); + // Insert at head. + head = cov; + head.next = match; + current = head; + currentPrev = null; + } + return cov; + } + } + + /** + * (Re-)Starts iterating the coverage values for the scanline. + * Use the returned iterator to get the consecutive coverage ranges. + * + * @return the iterator + */ + public Iterator iterate() + { + iterator.reset(); + return iterator; + } + + /** + * Returns {@ true} if this object has no entries for the current scanline, + * {@ false} otherwise. + * + * @return {@ true} if this object has no entries for the current scanline, + * {@ false} otherwise + */ + public boolean isEmpty() + { + return head == null || head == last + || head.next == null || head.next == last; + } + +} |