001: /*
002: * Copyright (c) 2001, Jacob Smullyan.
003: *
004: * This is part of SkunkDAV, a WebDAV client. See http://skunkdav.sourceforge.net/
005: * for the latest version.
006: *
007: * SkunkDAV is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License as published
009: * by the Free Software Foundation; either version 2, or (at your option)
010: * any later version.
011: *
012: * SkunkDAV is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015: * General Public License for more details.
016: *
017: * You should have received a copy of the GNU General Public License
018: * along with SkunkDAV; see the file COPYING. If not, write to the Free
019: * Software Foundation, 59 Temple Place - Suite 330, Boston, MA
020: * 02111-1307, USA.
021: */
022:
023: package org.skunk.util;
024:
025: import org.skunk.trace.Debug;
026:
027: /**
028: * a container for ints that keeps a gap in the array
029: */
030: public class GappedIntArray {
031: private int[] content;
032: static int DEFAULT_GAP_SIZE = 80;
033: private int preferredGapSize;
034: private int currentGapSize;
035: private int gapOffset;
036:
037: public GappedIntArray() {
038: this (DEFAULT_GAP_SIZE, 0, null);
039: }
040:
041: public GappedIntArray(int[] initialContent) {
042: this (DEFAULT_GAP_SIZE, 0, initialContent);
043: }
044:
045: public GappedIntArray(int gapSize, int gapOffset,
046: int[] initialContent) {
047: if (gapSize < 1 || gapOffset < 0)
048: throw new IllegalArgumentException(
049: "illegal arguments in constructor");
050: this .preferredGapSize = gapSize;
051: this .currentGapSize = gapSize;
052:
053: if (initialContent == null) {
054: this .gapOffset = 0; // argument for gapOffset ignored
055: content = new int[gapSize];
056: } else {
057: this .gapOffset = gapOffset;
058: int initLen = initialContent.length;
059: content = new int[gapSize + initLen];
060: System.arraycopy(initialContent, 0, content, 0, gapOffset);
061: System.arraycopy(initialContent, gapOffset, content,
062: gapOffset + gapSize, initLen - gapOffset);
063: }
064: }
065:
066: private int translate(int coordinate) {
067: return (coordinate < gapOffset) ? coordinate : coordinate
068: + currentGapSize;
069: }
070:
071: public int length() {
072: return content.length - currentGapSize;
073: }
074:
075: public int get(int offset) throws ArrayIndexOutOfBoundsException {
076: return content[translate(offset)];
077: }
078:
079: public int[] get(int offset, int length)
080: throws ArrayIndexOutOfBoundsException {
081: int endOffset = offset + length;
082: int[] tmp = new int[length];
083: if (gapOffset > endOffset) {
084: System.arraycopy(content, offset, tmp, 0, length);
085: } else if (gapOffset <= offset) {
086: System.arraycopy(content, offset + currentGapSize, tmp, 0,
087: length);
088: } else if (gapOffset == offset) {
089: System.arraycopy(content, gapOffset + currentGapSize, tmp,
090: 0, length);
091: } else {
092: int firstChunkLength = gapOffset - offset;
093: int secondChunkLength = length - firstChunkLength;
094: System.arraycopy(content, offset, tmp, 0, firstChunkLength);
095: System.arraycopy(content, gapOffset + currentGapSize, tmp,
096: firstChunkLength, secondChunkLength);
097: }
098: return tmp;
099: }
100:
101: public synchronized void append(int[] someInts) {
102: insertAt(length(), someInts);
103: }
104:
105: public synchronized void set(int offset, int anInt) {
106: content[translate(offset)] = anInt;
107: }
108:
109: public synchronized void set(int offset, int[] someInts)
110: throws ArrayIndexOutOfBoundsException {
111: if (Debug.DEBUG)
112: Debug.trace(this , Debug.DP8,
113: "in set: offset: {0}, ints to insert: {1}",
114: new Object[] { new Integer(offset),
115: toString(someInts) });
116:
117: int endOffset = offset + someInts.length;
118: if (endOffset >= length())
119: throw new ArrayIndexOutOfBoundsException(
120: "attempt to access beyond end of array; use insertAt instead");
121: if (gapOffset < offset) {
122: System.arraycopy(someInts, 0, content, currentGapSize
123: + offset, someInts.length);
124: } else if (gapOffset >= endOffset) {
125: System.arraycopy(someInts, 0, content, offset,
126: someInts.length);
127: } else if (gapOffset == offset) {
128: System.arraycopy(someInts, 0, content, offset
129: + currentGapSize, someInts.length);
130: } else //gapOffset is > offset, or gapOffset < offset && gapOffset<endOffset
131: {
132: int firstChunkLength = Math.max(0, gapOffset - offset);
133: int secondChunkLength = someInts.length - firstChunkLength;
134: System.arraycopy(someInts, 0, content, offset,
135: firstChunkLength);
136: System.arraycopy(someInts, firstChunkLength, content,
137: offset + firstChunkLength + currentGapSize,
138: secondChunkLength);
139: }
140: }
141:
142: public synchronized void remove(int offset, int len) {
143: if (Debug.DEBUG)
144: Debug.trace(this , Debug.DP8,
145: "in remove: offset: {0} length: {1}", new Object[] {
146: new Integer(offset), new Integer(len) });
147: if (len == 0)
148: return;
149: if ((offset + len + currentGapSize) > content.length)
150: throw new ArrayIndexOutOfBoundsException(
151: "can't remove that much");
152: if (len + currentGapSize <= preferredGapSize) {
153: if (offset == gapOffset) {
154: currentGapSize += len;
155: return;
156: } else if (offset < gapOffset && offset + len >= gapOffset) // removal is contiguous with gap
157: {
158: currentGapSize += len;
159: gapOffset = offset;
160: /*
161: * N.B.: it is possible here for currentGapSize
162: * to be greater than preferredGapSize
163: */
164: return;
165: }
166: }
167: //have to copy array
168: int[] tmp = content;
169: content = new int[tmp.length + preferredGapSize - len
170: - currentGapSize];
171: if (gapOffset <= offset) {
172: //copy from start to gapOffset
173: System.arraycopy(tmp, 0, content, 0, gapOffset);
174: //skip gap, copy until offset
175: System.arraycopy(tmp, gapOffset + currentGapSize, content,
176: gapOffset, offset - gapOffset);
177: int srcInd = currentGapSize + offset;
178: //skip removed ints
179: srcInd += len;
180: //copy the rest
181: System.arraycopy(tmp, srcInd, content, offset
182: + preferredGapSize, tmp.length - srcInd);
183: } else {
184: //copy from start to offset
185: System.arraycopy(tmp, 0, content, 0, offset);
186: if (offset + len >= gapOffset) {
187: System.arraycopy(tmp, offset + len + currentGapSize,
188: content, offset + preferredGapSize, tmp.length
189: - offset - currentGapSize - len);
190: } else {
191: //skip removed items, copy from there to gapOffset
192: System.arraycopy(tmp, offset + len, content, offset
193: + preferredGapSize, gapOffset - offset - len);
194: //copy remainder
195: System.arraycopy(tmp, gapOffset + currentGapSize,
196: content, preferredGapSize + gapOffset - len,
197: tmp.length - gapOffset - currentGapSize);
198: }
199:
200: }
201: gapOffset = offset;
202: currentGapSize = preferredGapSize;
203:
204: }
205:
206: public int getGapOffset() {
207: return this .gapOffset;
208: }
209:
210: public int getCurrentGapSize() {
211: return this .currentGapSize;
212: }
213:
214: public synchronized void insertAt(int offset, int[] someInts) {
215: if (Debug.DEBUG)
216: Debug.trace(this , Debug.DP8, "inserting {0}",
217: toString(someInts));
218: int insertLen = someInts.length;
219: if (insertLen == 0)
220: return;
221: if (gapOffset == offset && insertLen <= currentGapSize) {
222: System
223: .arraycopy(someInts, 0, content, gapOffset,
224: insertLen);
225: currentGapSize -= insertLen;
226: gapOffset += insertLen;
227: } else {
228: int[] tmp = content;
229: content = new int[tmp.length + preferredGapSize + insertLen
230: - currentGapSize];
231: if (gapOffset <= offset) {
232: //copy from start to gapOffset
233: System.arraycopy(tmp, 0, content, 0, gapOffset);
234: //skip gap, copy until offset
235: System.arraycopy(tmp, gapOffset + currentGapSize,
236: content, gapOffset, offset - gapOffset);
237: //do insert
238: System.arraycopy(someInts, 0, content, offset,
239: insertLen);
240: int lastOff = offset + currentGapSize;
241: gapOffset = offset + insertLen;
242: //copy the remainder
243: System.arraycopy(tmp, lastOff, content, gapOffset
244: + preferredGapSize, tmp.length - lastOff);
245: } else {
246: System.arraycopy(tmp, 0, content, 0, offset);
247: System.arraycopy(someInts, 0, content, offset,
248: insertLen);
249: System.arraycopy(tmp, offset, content, offset
250: + insertLen + preferredGapSize, gapOffset
251: - offset);
252: int lastOff = gapOffset + currentGapSize;
253: System.arraycopy(tmp, lastOff, content, insertLen
254: + preferredGapSize + gapOffset, tmp.length
255: - lastOff);
256: gapOffset = offset + insertLen;
257: }
258:
259: currentGapSize = preferredGapSize;
260: }
261: }
262:
263: public int[] toIntArray() {
264: int[] tmp = new int[content.length - currentGapSize];
265: System.arraycopy(content, 0, tmp, 0, gapOffset);
266: System.arraycopy(content, gapOffset + currentGapSize, tmp,
267: gapOffset, tmp.length - gapOffset);
268: return tmp;
269: }
270:
271: public static String toString(int[] array) {
272: StringBuffer sb = new StringBuffer("[");
273: int len = array.length - 1;
274:
275: for (int i = 0; i <= len; i++) {
276: sb.append(array[i]);
277: if (i < len)
278: sb.append(", ");
279: }
280: return sb.append(']').toString();
281: }
282:
283: public String toString() {
284: return toString(toIntArray());
285: }
286:
287: public static void main(String[] args) {
288: GappedIntArray gapper = new GappedIntArray();
289: System.out.println(gapper);
290: int[] blah = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
291: gapper.insertAt(0, blah);
292: System.out.println("inserting 10 items at 0 :\n" + gapper);
293: System.out.println("length: " + gapper.length());
294: gapper.remove(3, 1);
295: System.out.println("removing 1 item at 3:\n" + gapper);
296: System.out.println("length: " + gapper.length());
297: gapper.remove(3, 2);
298: System.out.println("removing 2 items at 3:\n" + gapper);
299: System.out.println("length: " + gapper.length());
300: gapper.insertAt(5, blah);
301: System.out.println("inserting 10 items at 5:\n" + gapper);
302: System.out.println("length: " + gapper.length());
303: gapper.insertAt(7, blah);
304: System.out.println("inserting 10 items at 6:\n" + gapper);
305: System.out.println("length: " + gapper.length());
306: gapper.remove(10, 5);
307: System.out.println("removing 5 items at 10:\n" + gapper);
308: System.out.println("length: " + gapper.length());
309: gapper.remove(10, 0);
310: System.out.println("removing zero items :\n" + gapper);
311: System.out.println("length: " + gapper.length());
312: gapper.remove(0, gapper.length() - 1);
313: System.out.println("removing all but one item:\n" + gapper);
314: System.out.println("length: " + gapper.length());
315: gapper.insertAt(1, blah);
316: System.out.println("inserting 10 items at 1:\n" + gapper);
317: System.out.println("length: " + gapper.length());
318: gapper.remove(0, gapper.length());
319: System.out.println("removing all items:\n" + gapper);
320: System.out.println("length: " + gapper.length());
321: gapper.insertAt(0, blah);
322: System.out.println("inserting 10 items at 0 :\n" + gapper);
323: System.out.println("length: " + gapper.length());
324: gapper.insertAt(5, blah);
325: System.out.println("inserting 10 items at 5 :\n" + gapper);
326: System.out.println("length: " + gapper.length());
327: blah = new int[] { 89, 45, 20 };
328: gapper.set(4, blah);
329: System.out.println("setting three values at 4:\n" + gapper);
330: System.out.println("length: " + gapper.length());
331: System.out.println("obtaining an array of five items: "
332: + gapper.toString(gapper.get(5, 5)));
333: gapper.set(4, blah);
334: System.out.println("setting three values at 12:\n" + gapper);
335: System.out.println("length: " + gapper.length());
336: System.out.println("obtaining an array of five items: "
337: + gapper.toString(gapper.get(0, 5)));
338: System.out.println("obtaining an array of five items: "
339: + gapper.toString(gapper.get(10, 5)));
340: System.out.println("obtaining an array of five items: "
341: + gapper.toString(gapper.get(12, 5)));
342: System.out.println("obtaining an array of five items: "
343: + gapper.toString(gapper.get(15, 5)));
344: System.out.println("getting the last five items: "
345: + gapper.toString(gapper.get(gapper.length() - 5, 5)));
346: }
347: }
348:
349: /* $Log: GappedIntArray.java,v $
350: /* Revision 1.9 2001/02/13 01:37:38 smulloni
351: /* additional tweaks to html mode. Flexicizer bug (possible
352: /* ArrayIndexOutOfBoundsException on reparse) fixed.
353: /*
354: /* Revision 1.8 2001/02/09 20:00:01 smulloni
355: /* fixed particularly nasty bug in GappedIntArray.set(int, int[]), and other
356: /* bugs in the syntax highlighting system.
357: /*
358: /* Revision 1.7 2001/02/06 00:11:18 smulloni
359: /* struggle, perhaps futile, with the TextEditorCustomizer and other implicated
360: /* classes
361: /*
362: /* Revision 1.6 2001/01/30 18:01:27 smulloni
363: /* first working beta of syntax highlighting. Nasty bug in
364: /* GappedIntArray.remove() fixed.
365: /*
366: /* Revision 1.5 2001/01/29 22:28:47 smulloni
367: /* syntax highlighting package now uses a custom view for painting the
368: /* highlights. Fixed bug in get(int, int[]) in GappedIntArray.
369: /*
370: /* Revision 1.4 2001/01/25 22:52:48 smulloni
371: /* added get(int, int) method to GappedIntArray
372: /*
373: /* Revision 1.3 2001/01/18 22:29:21 smulloni
374: /* experimental work on syntax package.
375: /*
376: /* Revision 1.2 2001/01/17 23:02:29 smulloni
377: /* beginning to rework SyntaxDocument, SyntaxTokenizer, to shift the
378: /* responsibility for handling context requirements from the document
379: /* to the tokenizer.
380: /*
381: /* Revision 1.1 2001/01/17 22:05:07 smulloni
382: /* a container for ints that holds a gap at the point of insert or removal, to
383: /* make subsequent operations at that point more efficient. Is it actually more
384: /* efficient? I don't know yet.
385: /* */
|