001: /*
002: * (C) Copyright IBM Corp. 1998-2004. All Rights Reserved.
003: *
004: * The program is provided "as is" without any warranty express or
005: * implied, including the warranty of non-infringement and the implied
006: * warranties of merchantibility and fitness for a particular purpose.
007: * IBM will not be liable for any damages suffered by you as a result
008: * of using the Program. In no event will IBM be liable for any
009: * special, indirect or consequential damages or lost profits even if
010: * IBM has been advised of the possibility of their occurrence. IBM
011: * will not be liable for any third party claims against you.
012: */
013: /**
014: * This class maintains intervals within a piece of text. Interval boundaries
015: * are stored in the fRunStart array. Interval boundaries may have a
016: * positive or negative representation. A positive boundary is given as an offset
017: * from 0. A negative boundary is given as a negative offset from the ned of the text.
018: * The RunArray stores positive boundaries in the entries [0, fPosEnd], and negative
019: * boundaries in the entries [fNegStart, fLength). New boundaries may be inserted into
020: * the undefined middle of the RunArray. If fPosEnd < 0, there are no positive entries.
021: * If fNegStart >= fRunArray.length, there are no negative netries. It's possible to have
022: * a runarray with neither positive or negative entries.
023: *
024: * As an example of how the RunArray works, consider a piece of text with 5 intervals,
025: * where each interval is 3 characters in length. The RunArray for this text could
026: * look like:
027: * fCurTextLength = 15, fPosEnd = 5, fNegStart = 10,
028: * fRunStart = { 0, 3, 6, 9, 12, U, U, U, U, U };
029: * where U is an undefined array element.
030:
031: * An equivalent representation would be:
032: * fCurTextLength = 15, fPosEnd = 3, fNegStart = 8,
033: * fRunStart = { 0, 3, 6, U, U, U, U, U, -6, -3 };
034: *
035: * The RunArray class is used in the StyleBuffer and the ParagraphBuffer. In the StyleBuffer,
036: * the entries in fRunStart give the offsets where style runs begin. In the
037: * ParagraphBuffer, the fRunStart entries store offsets of paragraph breaks.
038: *
039: * This class provides methods for shifting the run table to a particular position, expanding the
040: * run table, and returning the index of the run containing a particular offset in the text. All
041: * other functionality is implemented in the RunArray clients.
042: *
043: * RunArray uses FastIntBinarySearch for searches. The searches are constructed on demand in
044: * the findRunContaining method. The searches are invalidated when the run array is shifted;
045: * however, the RunArray can be modified by other classes. Thus, if another class modifies
046: * the entries in fRunArray, or modifies fPosEnd or fNegStart, it is responsible for
047: * calling runStartsChanged.
048: */package com.ibm.richtext.styledtext;
049:
050: import java.io.Externalizable;
051: import java.io.ObjectInput;
052: import java.io.ObjectOutput;
053: import java.io.IOException;
054:
055: final class RunArray implements Externalizable {
056:
057: static final String COPYRIGHT = "(C) Copyright IBM Corp. 1998-1999 - All Rights Reserved";
058: private static final long serialVersionUID = 22356934;
059:
060: int[] fRunStart;
061: private int fCurTextLength;
062: int fPosEnd, fNegStart;
063:
064: transient private FastIntBinarySearch fPosSearch;
065: transient private boolean fPosSearchValid;
066: transient private FastIntBinarySearch fNegSearch;
067: transient private boolean fNegSearchValid;
068:
069: private static final int CURRENT_VERSION = 1;
070:
071: RunArray(int initialSize, int curTextLength) {
072:
073: fRunStart = new int[initialSize];
074: fCurTextLength = curTextLength;
075: fPosEnd = -1;
076: fNegStart = initialSize;
077:
078: fPosSearch = new FastIntBinarySearch(fRunStart, 0, 1);
079: fNegSearch = new FastIntBinarySearch(fRunStart, 0, 1);
080: fPosSearchValid = fNegSearchValid = false;
081: }
082:
083: /**
084: * Note: this constructor is ONLY for use by the Serialization
085: * mechanism. It does not leave this object in a valid state!
086: */
087: public RunArray() {
088: }
089:
090: public void writeExternal(ObjectOutput out) throws IOException {
091:
092: out.writeInt(CURRENT_VERSION);
093: out.writeObject(fRunStart);
094: out.writeInt(fCurTextLength);
095: out.writeInt(fPosEnd);
096: out.writeInt(fNegStart);
097: }
098:
099: public void readExternal(ObjectInput in) throws IOException,
100: ClassNotFoundException {
101:
102: if (in.readInt() != CURRENT_VERSION) {
103: throw new IOException("Invalid version of RunArray");
104: }
105: fRunStart = (int[]) in.readObject();
106: fCurTextLength = in.readInt();
107: fPosEnd = in.readInt();
108: fNegStart = in.readInt();
109:
110: fPosSearch = new FastIntBinarySearch(fRunStart, 0, 1);
111: fNegSearch = new FastIntBinarySearch(fRunStart, 0, 1);
112: fPosSearchValid = fNegSearchValid = false;
113: }
114:
115: public int getCurTextLength() {
116:
117: return fCurTextLength;
118: }
119:
120: public void setCurTextLength(int curTextLength) {
121:
122: fCurTextLength = curTextLength;
123: }
124:
125: public void addToCurTextLength(int delta) {
126:
127: fCurTextLength += delta;
128: }
129:
130: public void runStartsChanged() {
131:
132: fPosSearchValid = fNegSearchValid = false;
133: }
134:
135: /**
136: * Returns the index of the last valid run.
137: */
138: int lastRun() {
139:
140: return (fNegStart == fRunStart.length) ? fPosEnd
141: : fRunStart.length - 1;
142: }
143:
144: /**
145: * Returns the length of the run array. Replaces old fLength member.
146: */
147: int getArrayLength() {
148:
149: return fRunStart.length;
150: }
151:
152: /**
153: * Shifts style table such that the last positive run
154: * starts before pos.
155: */
156: void shiftTableTo(int pos) {
157:
158: int oldPosEnd = fPosEnd;
159:
160: while (fPosEnd >= 0 && fRunStart[fPosEnd] >= pos) {
161:
162: fNegStart--;
163: fRunStart[fNegStart] = fRunStart[fPosEnd] - fCurTextLength;
164: fPosEnd--;
165:
166: }
167:
168: pos -= fCurTextLength;
169:
170: while (fNegStart < fRunStart.length
171: && fRunStart[fNegStart] < pos) {
172:
173: fPosEnd++;
174: fRunStart[fPosEnd] = fRunStart[fNegStart] + fCurTextLength;
175: fNegStart++;
176: }
177:
178: if (oldPosEnd != fPosEnd) {
179: fPosSearchValid = fNegSearchValid = false;
180: }
181: }
182:
183: /**
184: * Returns index of style run containing pos. If first style run starts before
185: * pos, -1 is returned. If pos is greater than text length, lastrun is returned.
186: */
187: int findRunContaining(int pos) {
188:
189: FastIntBinarySearch search;
190: final int length = fRunStart.length;
191:
192: if (fNegStart < length
193: && (pos - fCurTextLength >= fRunStart[fNegStart])) {
194:
195: pos -= fCurTextLength;
196:
197: if (!fNegSearchValid) {
198: fNegSearch.setData(fRunStart, fNegStart, length
199: - fNegStart);
200: }
201: search = fNegSearch;
202: } else if (fPosEnd >= 0) {
203:
204: if (!fPosSearchValid) {
205: fPosSearch.setData(fRunStart, 0, fPosEnd + 1);
206: }
207: search = fPosSearch;
208: } else
209: return -1;
210:
211: int run = search.findIndex(pos);
212:
213: return run;
214: }
215:
216: int getLogicalRunStart(int run) {
217:
218: if (run == -1) {
219: return 0;
220: } else if (run == fRunStart.length) {
221: return fCurTextLength;
222: } else {
223: if (run <= fPosEnd) {
224: return fRunStart[run];
225: } else if (run >= fNegStart) {
226: return fRunStart[run] + fCurTextLength;
227: } else {
228: throw new IllegalArgumentException("Illegal run");
229: }
230: }
231: }
232:
233: /**
234: * Increases size of run table. Current implementation doubles the run table's size.
235: */
236: void expandRunTable() {
237:
238: resizeRunTable(fRunStart.length * 2);
239: }
240:
241: /**
242: * Return the minimum number of elements possible in fRunStart.
243: */
244: private int getMinSize() {
245:
246: return Math
247: .max(fPosEnd + (fRunStart.length - fNegStart) + 1, 1);
248: }
249:
250: void compress() {
251:
252: int minSize = getMinSize();
253: if (fRunStart.length > minSize) {
254: resizeRunTable(minSize);
255: }
256: }
257:
258: private void resizeRunTable(int newSize) {
259:
260: if (newSize < getMinSize()) {
261: throw new IllegalArgumentException(
262: "Attempt to make RunArray too small.");
263: }
264:
265: final int oldLength = fRunStart.length;
266:
267: int newRunStart[] = new int[newSize];
268: System.arraycopy(fRunStart, 0, newRunStart, 0, fPosEnd + 1);
269: int newNegStart = newRunStart.length - (oldLength - fNegStart);
270: System.arraycopy(fRunStart, fNegStart, newRunStart,
271: newNegStart, (oldLength - fNegStart));
272:
273: fNegStart = newNegStart;
274: fRunStart = newRunStart;
275:
276: fPosSearchValid = fNegSearchValid = false;
277: }
278: }
|