LineOffsets


1   package gnu.jemacs.swt;
2   
3   import java.util.regex.Matcher  ;
4   import java.util.regex.Pattern  ;
5   
6   import gnu.lists.GapVector;
7   import gnu.lists.U32Vector;
8   
9   /**
10   * The purpose of this class is to maintain an ordered set of line offsets for an
11   * SwtCharBuffer. 
12   * <p>
13   * With a LineOffsets instance it's possible to map from the number of a line to the text
14   * position where it begins, and back, reasonably fast. 
15   * (O(1) for line number to line offset, O(log(#lines)) for line offset to line number)
16   * <p>
17   * LineOffsets extends GapVector with an U32Vector as base, allowing new line offsets to be inserted
18   * quickly during normal text typing.
19   * <p>
20   * <p>
21   * Instances of SwtCharBuffer should hold an instance LineOffsets class and notify it whenever the it's text changes.
22   * The notification happens through the methods: 
23   * <p>
24   * <ul>  
25   *   <li>
26   *     textRegionMoved, which should be called when the gap (of SwtCharBuffer) changes 
27   *     (position or size). 
28   *   </li>
29   *   <li>
30   *     textInserted.
31   *   </li>
32   *   <li>
33   *     textDeleted. 
34   *   </li>
35   * </ul> 
36   * <p>
37   * <p>
38   * 
39   * TODO: decouple this, using a more general event model..
40   * 
41   * Assume that lineOffset is an instance of LineOffsets, held by swtCharBuffer an instance of 
42   * SwtCharBuffer. 
43   * <p>
44   * Then a value of <code>o</code> at index <code>i</code> in lineOffsets.base
45   * means that the line with line number
46   * <code>n = (i < lOff.gapStart ? i : i + lOff.gapEnd - lOff.gapStart)</code>  
47   * <p>
48   * starts at text position 
49   * <code>p = (o < swtCB.gapStart ? o : o + swtCB.gapEnd - swtCB.gapStart)</code>
50   * <p>
51   * @author Christian Surlykke
52   *         12-07-2004
53   */
54  public class LineOffsets extends GapVector
55  {
56    
57    public final static int minGapSize = 100;
58    private static Pattern   newLinePattern = Pattern.compile("\n|\r\n|\r"); // We recognize all the usual forms of 
59                                                                           // linedelimiters
60  
61    
62    private U32Vector offsets;
63    
64    public LineOffsets(int initialSize)
65    {
66      super(new U32Vector(Math.max(101, initialSize)));
67      offsets = (U32Vector) base;
68      insertLine(0, 0); // Line 0 allways starts at position 0 -
69                        // even if the text is just the empty string
70    }
71    
72    private void setOffset(int index, int Offset)
73    {
74      offsets.setIntAt(index < gapStart ? index : index + gapEnd - gapStart, Offset);
75    }
76  
77    private int getOffset(int index)
78    {
79      return offsets.intAt(index < gapStart ? index : index + gapEnd - gapStart);
80    }
81  
82    public void insertLine(int index, int offSet)
83    {
84      gapReserve(index, 1);
85      offsets.setIntAt(gapStart++, offSet);
86    }
87  
88    public int index2offset(int index) 
89    {
90      return offsets.intAt(index < gapStart ? index : index + gapEnd - gapStart); 
91    }
92    
93    /**
94     * We seek the line containing a given text offset using a halfing of intervals algorithm. Therefore
95     * the method will use O(log(n)) time, n being the number of lines. 
96     * 
97     * @see org.eclipse.swt.custom.StyledTextContent#getLineAtOffset(int)
98     */
99    public int offset2index(int offset)
100   {
101     // Adhoc optimization: Very often this class will be asked for the line index belonging to the point
102     // where insertion happens, i.e. at the start of the gap. 
103     // We try this before the full search so that we may return in O(1) time in this case.
104     try 
105     {
106       if (index2offset(gapStart - 1) <= offset && index2offset(gapStart) > offset)
107       {
108         return gapStart - 1;
109       }
110     }
111     catch (IndexOutOfBoundsException   e)
112     { 
113     }
114     
115     // The normal search
116     int intervalStart = 0;
117     int intervalEnd = size();
118   
119     // Invariant: offset(intervalStart) <= offset AND offset(intervalEnd) > offset
120     while (intervalEnd > intervalStart + 1) 
121     {
122       int middle = (intervalStart + intervalEnd) / 2;
123       if (index2offset(middle) <= offset) 
124       {
125         intervalStart = middle;
126       }
127       else 
128       {
129         intervalEnd = middle;
130       }
131     }
132     
133     return intervalStart;
134   }
135 
136   public void deleteLines(int firstLine, int numberOfLines)
137   {
138     if (numberOfLines > 0)
139     {
140       int pos = createPos(firstLine, false);
141       removePos(pos, numberOfLines);
142       releasePos(pos);
143     }
144   }
145 
146   public void insertLines(int index, int[] offsets)
147   {
148     if (offsets != null && offsets.length > 0)
149     {
150       // The offsets should comply with:
151       // 0 <= offset[i] < offset[j] for 0 <= i < j
152       // 
153       
154       // TOCONSIDER: 
155       // Maybe we should define an exception of our own here?
156       
157       if (index2offset(index) > offsets[0])
158       {
159         throw new IllegalArgumentException  ();
160       }
161       
162       if (index < size() && offsets[offsets.length - 1] > index2offset(index + 1))
163       {
164         throw new IllegalArgumentException  ();
165       }
166       
167       for(int i = 0; i < offsets.length -1; i++)
168       {
169         if (offsets[i] > offsets[i + 1])
170         {
171           throw new IllegalArgumentException  ();
172         }
173       }
174       
175       gapReserve(index + 1, offsets.length);
176       System.arraycopy(offsets, 0, offsets, index + 1, offsets.length);
177     }
178   }
179   
180   public String   toString()
181   {
182     StringBuffer   sbuf = new StringBuffer  ();
183     sbuf.append("Lines: {" + size() + ", " + gapStart + ", " + gapEnd);
184     sbuf.append(" [");
185     for (int i = 0; i < size(); i++) 
186     { 
187       if (i == gapStart)
188       {
189         sbuf.append("|");
190       }
191       sbuf.append(offsets.intAt(i < gapStart ? i : i + gapEnd - gapStart));
192       
193       if (i < size() - 1) 
194       {
195         sbuf.append(" ");
196       }
197     }
198     sbuf.append("]}");
199     return sbuf.toString();
200     
201   }
202 
203   public int countLines(String   newText)
204   {
205     Matcher   m = newLinePattern.matcher(newText);
206     int i = 0;
207     while (m.find())
208     {
209       i++;
210     }
211     return i;
212   }
213 
214   public int linesInRange(int startOffset, int endOffset)
215   {
216     int indexOfStart = offset2index(startOffset);
217     int indexOfEnd = offset2index(endOffset);
218     return indexOfEnd - indexOfStart;
219   }
220 
221   public void textRegionMoved(int regionStart, int regionEnd, int displacement)
222   {
223     int firstIndexToUpdate = offset2index(regionStart) + 1;
224     int lastIndexToUpdate = offset2index(regionEnd);
225     for (int index = firstIndexToUpdate; index <= lastIndexToUpdate; index++)
226     {
227       setOffset(index, getOffset(index) + displacement);
228     }
229   }
230 
231   public void textInserted(int startOffset, CharSequence   seq)
232   {
233     int index = offset2index(startOffset);
234     for (Matcher   m = newLinePattern.matcher(seq); m.find(); )
235     {
236       insertLine(++index, startOffset + m.end());
237     }
238   }
239 
240   public void textDeleted(int startOffset, int endOffset)
241   {
242     int index = offset2index(startOffset);
243     shiftGap(index + 1);
244     while (gapEnd < offsets.getBufferLength() && offsets.intAt(gapEnd) <= endOffset)
245     {
246       gapEnd++;
247     }
248   }
249 
250   public boolean isLineDelimiter(char c)
251   {
252     // TODO Auto-generated method stub
253     return c == '\n' || c == '\r';
254   }
255 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags