StableVector


1   // Copyright (c) 2001, 2002, 2003  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   /** Implements a stable sequence with sticky positions.
7    * I.e if you have a position, it gets automatically updated after
8    * insertions and deletions. */
9   
10  public class StableVector extends GapVector
11  {
12    /** This array maps from the exported ipos values (indexes in the positions
13     * array) to the ipos of the underlying SimpleVector base.
14     * The first two elements are reserved for START_POSITION and END_POSITION.
15     * Unused elements in positions are chained together in a free list
16     * headed by the 'free' variable.  */
17    protected int[] positions;
18  
19    /** The head of the free elements in position, if they are chained.
20     * We need track of available elements in the positions array in two ways:
21     * In unchained mode, there is no free list per se.  Instead an index i
22     * is available if positions[i]==FREE_POSITION.  This modemakes it
23     * easy to loop over all positions, ignores the unused ones.
24     * In chained mode, there is a free list and if index i is available,
25     * then positions[i] is the next available index, with -1 if there is none.
26     * Unchained mode is indicated by free==-2.
27     * In chained mode, free is the first element in the free list,
28     * or -1 if the free list is empty.
29     * The main virtue of this convention is that we don't need a separate
30     * list or array for the free list.  But we should get rid of the
31     * unchained mode, at least.  FIXME.
32     */
33    protected int free;
34  
35    /** An invalid value for an in-use element of positions. */
36    protected static final int FREE_POSITION = -1 << 1;
37  
38    /** Put all free elements in positions in a chain starting with free. */
39    protected void chainFreelist()
40    {
41      free = -1;
42      for (int i = positions.length;  --i > END_POSITION; )
43        {
44      int pos = positions[i];
45      if (pos == FREE_POSITION)
46        {
47          positions[i] = free;
48          free = i;
49        }
50        }
51    }
52  
53    /** Set all free elements in positions to FREE_POSITION. */
54    protected void unchainFreelist()
55    {
56      for (int i = free;  i >= 0; )
57        {
58      int next = positions[i];
59      positions[i] = FREE_POSITION;
60      i = next;
61        }
62      free = -2;
63    }
64  
65    /** Index in positions for the start position.
66     * positions[START_POSITION] is always 0. */
67    static final int START_POSITION = 0;
68  
69    /** Index in positions for the end position.
70     * positions[END] is always (size()<<1)+1. */
71    static final int END_POSITION = 1;
72  
73    public int startPos () { return START_POSITION; }
74    public int endPos () { return END_POSITION; }
75  
76    public StableVector(SimpleVector base)
77    {
78      super(base);
79      positions = new int[16];
80      positions[START_POSITION] = 0;
81      positions[END_POSITION] = (base.getBufferLength() << 1) | 1;
82      free = -1;
83      for (int i = positions.length;  --i >= 2; )
84        {
85      positions[i] = free;
86      free = i;
87        }
88    }
89  
90    protected StableVector ()
91    {
92    }
93  
94    protected int allocPositionIndex()
95    {
96      if (free == -2)
97        chainFreelist();
98      if (free < 0)
99        {
100     int oldLength = positions.length;
101     int[] tmp = new int[2 * oldLength];
102     System.arraycopy(positions, 0, tmp, 0, oldLength);
103     for (int i = 2 * oldLength;  --i >= oldLength; )
104       {
105         tmp[i] = free;
106         free = i;
107       }
108     positions = tmp;
109       }
110     int pos = free;
111     free = positions[free];
112     return pos;
113   }
114 
115   public int createPos (int index, boolean isAfter)
116   {
117     if (index == 0 && ! isAfter)
118       return START_POSITION;
119     else if (isAfter && index == size())
120       return END_POSITION;
121     if (index > gapStart || (index == gapStart && isAfter))
122       index += gapEnd - gapStart;
123     int ipos = allocPositionIndex();
124     positions[ipos] = (index << 1) | (isAfter ? 1 : 0);
125     return ipos;
126   }
127 
128   protected boolean isAfterPos (int ipos)
129   {
130     return (positions[ipos] & 1) != 0;
131   }
132 
133   public boolean hasNext(int ipos)
134   {
135     int ppos = positions[ipos];
136     int index = ppos >>> 1;
137     if (index >= gapStart)
138       index += gapEnd - gapStart;
139     return index < base.getBufferLength();
140   }
141 
142   public int nextPos (int ipos)
143   {
144     int ppos = positions[ipos];
145     int index = ppos >>> 1;
146     if (index >= gapStart)
147       index += gapEnd - gapStart;
148     if (index >= base.getBufferLength())
149       {
150     releasePos(ipos);
151     return 0;
152       }
153     if (ipos == 0)
154       ipos = createPos(0, true);
155     positions[ipos] = ppos | 1;
156     return ipos;
157   }
158 
159   public int nextIndex (int ipos)
160   {
161     int index = positions[ipos] >>> 1;
162     if (index > gapStart)
163       index -= gapEnd - gapStart;
164     return index;
165   }
166 
167   public void releasePos(int ipos)
168   {
169     if (ipos >= 2)
170       {
171     if (free == -2)
172       chainFreelist();
173     positions[ipos] = free;
174     free = ipos;
175       }
176   }
177 
178   public int copyPos (int ipos)
179   {
180     if (ipos > END_POSITION)
181       {
182     int i = allocPositionIndex();
183     positions[i] = positions[ipos];
184     ipos = i;
185       }
186     return ipos;
187   }
188 
189   public void fillPosRange(int fromPos, int toPos, Object   value)
190   {
191     fillPosRange(positions[fromPos], positions[toPos], value);
192   }
193 
194   protected void shiftGap(int newGapStart)
195   {
196     int oldGapStart = gapStart;
197     int delta = newGapStart - oldGapStart;
198     int low, high, adjust;
199     if (delta > 0)
200       {
201     low = gapEnd;
202     high = low + delta;
203     adjust = (oldGapStart - low) << 1;
204     // The position corresponding to the new endGap should be adjusted
205     // only if it has the isAfter (low-order) bit is clear.  Hence the -1.
206     low = low << 1;
207     high = (high << 1) - 1;
208       }
209     else if (newGapStart == oldGapStart)
210       return;
211     else // newGapStart < gapStart:
212       {
213     // Positions at the newgapStart should be adjust only if isAfter.
214     low = (newGapStart << 1) + 1;
215     high = oldGapStart << 1;
216     adjust = (gapEnd - oldGapStart) << 1;
217       }
218     super.shiftGap(newGapStart);
219 
220     adjustPositions(low, high, adjust);
221   }
222 
223   /** Add a delta to all positions elements that point into a given range.
224    * Assume x==positions[i], then if (unsigned)x>=(unsigned)low
225    * && (unsigned)x <= (unsigned)high, then add delta to positions[i].
226    * Using unsigned comparisons allows us to compare ipos values,
227    * which include both the index and the isAfter low-order bit.   */
228   protected void adjustPositions(int low, int high, int delta)
229   {
230     if (free >= 0)
231       unchainFreelist();
232 
233     // Invert the high-order bit, because:
234     // (unsigned) X > (unsigned) Y
235     // iff (int) (X^0x80000000) > (int) (Y^0x80000000)
236     low = low ^ 0x80000000;
237     high = high ^ 0x80000000;
238 
239     for (int i = positions.length;  --i > START_POSITION; )
240       {
241     int pos = positions[i];
242     if (pos != FREE_POSITION)
243       {
244         int index = pos ^ 0x80000000;
245         if (index >= low && index <= high)
246           positions[i] = pos + delta;
247       }
248       }
249   }
250 
251   protected void gapReserve(int size)
252   {
253     int oldGapEnd = gapEnd;
254     int oldLength = base.getBufferLength();
255     super.gapReserve(size);
256     int newLength = base.getBufferLength();
257     adjustPositions(oldGapEnd << 1, (newLength << 1) | 1,
258             (newLength - oldLength) << 1);
259   }
260 
261   protected int addPos(int ipos, Object   value)
262   {
263     int ppos = positions[ipos];
264     int index = ppos >>> 1;
265     if (index >= gapStart)
266       index += gapEnd - gapStart;
267     // Force positions[ipos] to have the isAfter property.
268     if ((ppos & 1) == 0)
269       {
270     if (ipos == 0)
271       ipos = createPos(0, true);
272     else
273       positions[ipos] = ppos | 1;
274       }
275     add(index, value);
276     return ipos;
277   }
278 
279   protected void removePosRange(int ipos0, int ipos1)
280   {
281     super.removePosRange(positions[ipos0], positions[ipos1]);
282 
283     // adjust positions in gap
284     int low = gapStart;
285     int high = gapEnd;
286     if (free >= 0)
287       unchainFreelist();
288     for (int i = positions.length;  --i > START_POSITION; )
289       {
290     int pos = positions[i];
291     if (pos != FREE_POSITION)
292       {
293         int index = pos >> 1;
294             boolean isAfter = (pos & 1) != 0;
295             if (isAfter)
296               {
297                 if (index >= low && index < high)
298                   positions[i] = (gapEnd << 1) | 1;
299               }
300             else
301               {
302                 if (index > low && index <= high)
303                   positions[i] = (gapStart << 1);
304               }
305       }
306       }
307   }
308 
309   /*
310   public Object remove(int index)
311   {
312     // FIXME
313   }
314   */
315 
316   public void consumePosRange (int iposStart, int iposEnd, Consumer out)
317   {
318     super.consumePosRange(positions[iposStart], positions[iposEnd], out);
319   }
320 }
321
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags