001: /*
002: * $RCSfile: IntegerSequence.java,v $
003: *
004: * Copyright (c) 2005 Sun Microsystems, Inc. All rights reserved.
005: *
006: * Use is subject to license terms.
007: *
008: * $Revision: 1.1 $
009: * $Date: 2005/02/11 04:57:10 $
010: * $State: Exp $
011: */
012: package javax.media.jai;
013:
014: import java.util.NoSuchElementException;
015:
016: /**
017: * A growable sorted integer set. Adding an integer to the sequence
018: * results in it being placed into the sequence in sorted order. Adding
019: * an integer that is already part of the sequence has no effect.
020: *
021: * <p> This structure is used by various subclasses of
022: * <code>OpImage</code> to keep track of horizontal and vertical
023: * source splits. Each instance of IntegerSequence provides an
024: * internal enumeration by means of which the elements of the sequence
025: * may be accessed in order. The enumerator is initialized by the
026: * <code>startEnumeration</code> method, and the
027: * <code>hasMoreElements</code> and <code>nextElement</code> methods
028: * allow looping through the elements. Only one enumeration at a time
029: * is supported. Calling <code>insert()</code> from multiple threads
030: * is not supported.
031: *
032: */
033: public class IntegerSequence extends Object {
034:
035: /** Lower bound of the valid integer range. */
036: private int min;
037:
038: /** Upper bound of the valid integer range. */
039: private int max;
040:
041: /** The default initial capacity of iArray. */
042: private static final int DEFAULT_CAPACITY = 16;
043:
044: /** The array storing the unsorted integer values. */
045: private int[] iArray = null;
046:
047: /** The capacity of iArray. */
048: private int capacity = 0;
049:
050: /** The number of (non-unique) elements actually stored in iArray. */
051: private int numElts = 0;
052:
053: /** True if iArray has been sorted and purged of duplicates. */
054: private boolean isSorted = false;
055:
056: /** The current element of the iteration. */
057: private int currentIndex = -1;
058:
059: /** Constructs a sequence bounded by an inclusive range of values.
060: * @param min Lower bound of the valid integer range.
061: * @param max Upper bound of the valid integer range.
062: * @throws IllegalArgumentException if min > max.
063: */
064: public IntegerSequence(int min, int max) {
065: if (min > max)
066: throw new IllegalArgumentException(JaiI18N
067: .getString("IntegerSequence1"));
068: this .min = min;
069: this .max = max;
070:
071: this .capacity = DEFAULT_CAPACITY;
072: this .iArray = new int[capacity];
073: this .numElts = 0;
074: this .isSorted = true;
075: }
076:
077: /** Constructs a sequence that may contain any integer value. */
078: public IntegerSequence() {
079: this (java.lang.Integer.MIN_VALUE, java.lang.Integer.MAX_VALUE);
080: }
081:
082: /**
083: * Inserts an integer into the sequence. If the value falls out
084: * of the desired range, it will be silently rejected. Inserting
085: * an element that is already a member of the sequence has no
086: * effect.
087: *
088: * @param element The <code>int</code> to be inserted.
089: */
090: public void insert(int element) {
091: // Ignore elements that fall outside the desired range.
092: if (element < min || element > max) {
093: return;
094: }
095:
096: if (numElts >= capacity) {
097: int newCapacity = 2 * capacity;
098: int[] newArray = new int[newCapacity];
099: System.arraycopy(iArray, 0, newArray, 0, capacity);
100:
101: this .capacity = newCapacity;
102: this .iArray = newArray;
103: }
104: isSorted = false;
105: iArray[numElts++] = element;
106: }
107:
108: /** Resets the iterator to the beginning of the sequence. */
109: public void startEnumeration() {
110: if (!isSorted) {
111: // Sort the contents of iArray
112: java.util.Arrays.sort(iArray, 0, numElts);
113:
114: // Compact the array, removing duplicate entries.
115: int readPos = 1;
116: int writePos = 1;
117: int prevElt = iArray[0];
118:
119: //
120: // Loop invariants: writePos <= readPos
121: // iArray[0..readPos - 1] contains no duplicates
122: //
123: for (readPos = 1; readPos < numElts; ++readPos) {
124: int currElt = iArray[readPos];
125: if (currElt != prevElt) {
126: iArray[writePos++] = currElt;
127: prevElt = currElt;
128: }
129: }
130:
131: numElts = writePos;
132: isSorted = true;
133: }
134:
135: currentIndex = 0;
136: }
137:
138: /** Returns true if more elements are available to be iterated over. */
139: public boolean hasMoreElements() {
140: return currentIndex < numElts;
141: }
142:
143: /**
144: * Returns the next element of the iteration in ascending order.
145: * If the end of the array has been reached, a
146: * <code>java.util.NoSuchElementException will be thrown.
147: *
148: * @throws NoSuchElementException if the end of the array has
149: * been reached.
150: */
151: public int nextElement() {
152: if (currentIndex < numElts) {
153: return iArray[currentIndex++];
154: } else {
155: throw new NoSuchElementException(JaiI18N
156: .getString("IntegerSequence0"));
157: }
158: }
159:
160: /**
161: * Returns the number of elements contained within this <code>IntegerSequence</code>.
162: */
163: public int getNumElements() {
164: return numElts;
165: }
166:
167: /** Returns a <code>String</code> representation of the sequence. */
168: public String toString() {
169: String s;
170: int i;
171:
172: if (numElts == 0) {
173: s = "[<empty>]";
174: } else {
175: s = "[";
176:
177: startEnumeration();
178: for (i = 0; i < numElts - 1; i++) {
179: s += iArray[i];
180: s += ", ";
181: }
182:
183: s += iArray[numElts - 1];
184: s += "]";
185: }
186:
187: return s;
188: }
189: }
|