KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > gnu > lists > GapVector


1 // Copyright (c) 2001 Per M.A. Bothner and Brainfood Inc.
2
// This is free software; for terms and warranty disclaimer see ./COPYING.
3

4 package gnu.lists;
5
6 /**
7  * An array with a gap in the middle, allowing efficient insert and delete.
8  * The actual storage is delegated to a SimpleVector, so the element
9  * type depends on the sub-class of SimpleVector used.
10  */

11
12 public class GapVector extends AbstractSequence implements Sequence
13 {
14   public SimpleVector base;
15   public int gapStart;
16   public int gapEnd;
17
18   public GapVector(SimpleVector base)
19   {
20     this.base = base;
21     this.gapStart = 0;
22     this.gapEnd = base.size;
23   }
24
25   protected GapVector ()
26   {
27   }
28
29   public int size()
30   {
31     return base.size - (gapEnd - gapStart);
32   }
33
34   public boolean hasNext(int ipos)
35   {
36     int index = ipos >>> 1;
37     if (index >= gapStart)
38       index += gapEnd - gapStart;
39     return index < base.size;
40   }
41
42   public int getNextKind(int ipos)
43   {
44     return hasNext(ipos) ? base.getElementKind() : EOF_VALUE;
45   }
46
47   public Object JavaDoc get (int index)
48   {
49     // If index is out of bounds, the base.get will catch that.
50
if (index >= gapStart)
51       index += gapEnd - gapStart;
52     return base.get(index);
53   }
54
55   public Object JavaDoc set (int index, Object JavaDoc value)
56   {
57     // If index is out of bounds, the base.set will catch that.
58
if (index >= gapStart)
59       index += gapEnd - gapStart;
60     return base.set(index, value);
61   }
62
63   public void fill (Object JavaDoc value)
64   {
65     base.fill(gapEnd, base.size, value);
66     base.fill(0, gapStart, value);
67   }
68
69   public void fillPosRange(int fromPos, int toPos, Object JavaDoc value)
70   {
71     int from = fromPos == -1 ? base.size : fromPos >>> 1;
72     int to = toPos == -1 ? base.size : toPos >>> 1;
73     int limit = gapStart < to ? gapStart : to;
74     for (int i = from; i < limit; i++)
75       base.setBuffer(i, value);
76     for (int i = gapEnd; i < to; i++)
77       base.setBuffer(i, value);
78   }
79
80   protected void shiftGap(int newGapStart)
81   {
82     int delta = newGapStart - gapStart;
83     if (delta > 0)
84       base.shift(gapEnd, gapStart, delta);
85     else if (delta < 0)
86       base.shift(newGapStart, gapEnd + delta, - delta);
87     gapEnd += delta;
88     gapStart = newGapStart;
89   }
90
91   /** Make sure gap is at least 'size' elements long. */
92   protected void gapReserve(int size)
93   {
94     if (size > gapEnd - gapStart)
95       {
96     int oldLength = base.size;
97         int newLength = oldLength < 16 ? 16 : 2 * oldLength;
98     int minLength = oldLength - (gapEnd - gapStart) + size;
99     if (newLength < minLength)
100       newLength = minLength;
101     // FIXME this does unneeded copying.
102
// It may also leave unwanted junk in the gap (gap for gc).
103
base.setSize(newLength);
104     int newGapEnd = newLength - oldLength + gapEnd;
105     base.shift(gapEnd, newGapEnd, oldLength - gapEnd);
106     gapEnd = newGapEnd;
107       }
108   }
109
110   /** Adjust gap to 'where', and make sure it is least `size' elements long. */
111   protected void gapReserve(int where, int size)
112   {
113     gapReserve(size);
114     if (where != gapStart)
115       shiftGap(where);
116   }
117
118   /** If needed, move the gap so the given segment is contiguous.
119    * @return the offset in the base array containing the segment,
120    * or -1 if the parameters are bad.
121    */

122    
123   public int getSegment (int where, int len)
124   {
125     int length = size();
126     if (where < 0 || where > length)
127       return -1;
128     if (len < 0)
129       len = 0;
130     else if (where + len > length)
131       len = length - where;
132     // if (len < 0 || where + len > length)
133
// return -1;
134
if (where + len <= gapStart)
135       return where;
136     if (where >= gapStart)
137       return where + (gapEnd - gapStart);
138     // Shift the gap depending in which direction needs least copying.
139
if (gapStart - where > (len >> 1))
140       {
141     shiftGap(where + len);
142     return where;
143       }
144     else
145       {
146     shiftGap(where);
147     return where + (gapEnd - gapStart);
148       }
149   }
150
151   protected int addPos (int ipos, Object JavaDoc value)
152   {
153     int index = ipos >>> 1;
154     if (index >= gapStart)
155       index += gapEnd - gapStart;
156     add(index, value);
157     return ((index + 1) << 1) | 1;
158   }
159
160   public void add(int index, Object JavaDoc o)
161   {
162     gapReserve(index, 1);
163     base.set(index, o);
164     gapStart++;
165   }
166
167   protected void removePosRange(int ipos0, int ipos1)
168   {
169     ipos0 >>>= 1;
170     ipos1 >>>= 1;
171     if (ipos0 > gapEnd)
172       shiftGap(ipos0-gapEnd+gapStart);
173     else if (ipos1 < gapStart)
174       shiftGap(ipos1);
175     if (ipos0 < gapStart)
176       {
177     base.clearBuffer(ipos0, gapStart - ipos0);
178     gapStart = ipos0;
179       }
180     if (ipos1 > gapEnd)
181       {
182     base.clearBuffer(gapEnd, ipos1 - gapEnd);
183     gapEnd = ipos1;
184       }
185   }
186
187   /* FIXME - ths is quite wrong!
188   public Object remove(int index)
189   {
190     if (index >= gapStart)
191       index += gapEnd - gapStart;
192     return base.remove(index);
193   }
194   */

195
196   public int createPos(int index, boolean isAfter)
197   {
198     if (index > gapStart)
199       index += gapEnd - gapStart;
200     // if (index == gapStart && isAfter) index = gapEnd; ??
201
return (index << 1) | (isAfter ? 1 : 0);
202   }
203
204   protected boolean isAfterPos(int ipos)
205   {
206     return (ipos & 1) != 0;
207   }
208
209   protected int nextIndex(int ipos)
210   {
211     int index = ipos == -1 ? base.size : ipos >>> 1;
212     if (index > gapStart)
213       index -= gapEnd - gapStart;
214     return index;
215   }
216
217   public void consumePosRange (int iposStart, int iposEnd, Consumer out)
218   {
219     if (out.ignoring())
220       return;
221     int i = iposStart >>> 1;
222     int end = iposEnd >>> 1;
223     if (i < gapStart)
224       {
225     int lim = end > gapStart ? end : gapStart;
226     consumePosRange(iposStart, lim << 1, out);
227       }
228     if (end > gapEnd)
229       {
230     i = i < gapEnd ? gapEnd : i;
231     consumePosRange(i << 1, iposEnd, out);
232       }
233   }
234
235 }
236
Popular Tags