RangeMap


1   /*
2    * RangeMap.java
3    * :tabSize=8:indentSize=8:noTabs=false:
4    * :folding=explicit:collapseFolds=1:
5    *
6    * Copyright (C) 2001, 2005 Slava Pestov
7    *
8    * This program is free software; you can redistribute it and/or
9    * modify it under the terms of the GNU General Public License
10   * as published by the Free Software Foundation; either version 2
11   * of the License, or any later version.
12   *
13   * This program is distributed in the hope that it will be useful,
14   * but WITHOUT ANY WARRANTY; without even the implied warranty of
15   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16   * GNU General Public License for more details.
17   *
18   * You should have received a copy of the GNU General Public License
19   * along with this program; if not, write to the Free Software
20   * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
21   */
22  
23  package org.gjt.sp.jedit.textarea;
24  
25  import org.gjt.sp.jedit.Debug;
26  import org.gjt.sp.util.Log;
27  
28  /**
29   * The fold visibility map.
30   *
31   * All lines from fvm[2*n] to fvm[2*n+1]-1 inclusive are visible.
32   * All lines from position fvm[2*n+1] to fvm[2*n+2]-1 inclusive are
33   * invisible.
34   *
35   * Examples:
36   * ---------
37   * All lines visible: { 0, buffer.getLineCount() }
38   * Narrow from a to b: { a, b + 1 }
39   * Collapsed fold from a to b: { 0, a + 1, b, buffer.getLineCount() }
40   *
41   * Note: length is always even.
42   */
43  class RangeMap
44  {
45      //{{{ RangeMap constructor
46      RangeMap()
47      {
48          fvm = new int[2];
49          lastfvmget = -1;
50      } //}}}
51  
52      //{{{ RangeMap constructor
53      RangeMap(RangeMap copy)
54      {
55          this.fvm = (int[])copy.fvm.clone();
56          this.fvmcount = copy.fvmcount;
57      } //}}}
58  
59      //{{{ reset() method
60      void reset(int lines)
61      {
62          lastfvmget = -1;
63          fvmcount = 2;
64          fvm[0] = 0;
65          fvm[1] = lines;
66      } //}}}
67  
68      //{{{ first() method
69      int first()
70      {
71          return fvm[0];
72      } //}}}
73  
74      //{{{ last() method
75      int last()
76      {
77          return fvm[fvmcount - 1] - 1;
78      } //}}}
79  
80      //{{{ lookup() method
81      int lookup(int index)
82      {
83          return fvm[index];
84      } //}}}
85  
86      //{{{ search() method
87      /**
88       * Returns the fold visibility map index for the given line.
89       */
90      int search(int line)
91      {
92          if(line < fvm[0])
93              return -1;
94          if(line >= fvm[fvmcount - 1])
95              return fvmcount - 1;
96  
97          if(lastfvmget != -1)
98          {
99              if(line >= fvm[lastfvmget])
100             {
101                 if(lastfvmget == fvmcount - 1
102                     || line < fvm[lastfvmget + 1])
103                 {
104                     return lastfvmget;
105                 }
106             }
107         }
108 
109         int start = 0;
110         int end = fvmcount - 1;
111 
112 loop:       for(;;)
113         {
114             switch(end - start)
115             {
116             case 0:
117                 lastfvmget = start;
118                 break loop;
119             case 1:
120                 int value = fvm[end];
121                 if(value <= line)
122                     lastfvmget = end;
123                 else
124                     lastfvmget = start;
125                 break loop;
126             default:
127                 int pivot = (end + start) / 2;
128                 value = fvm[pivot];
129                 if(value == line)
130                 {
131                     lastfvmget = pivot;
132                     break loop;
133                 }
134                 else if(value < line)
135                     start = pivot;
136                 else
137                     end = pivot - 1;
138                 break;
139             }
140         }
141 
142         return lastfvmget;
143     } //}}}
144 
145     //{{{ put() method
146     /**
147      * Replaces from <code>start</code> to <code>end-1</code> inclusive with
148      * <code>put</code>. Update <code>fvmcount</code>.
149      */
150     void put(int start, int end, int[] put)
151     {
152         if(Debug.FOLD_VIS_DEBUG)
153         {
154             StringBuffer   buf = new StringBuffer  ("{");
155             if(put != null)
156             {
157                 for(int i = 0; i < put.length; i++)
158                 {
159                     if(i != 0)
160                         buf.append(',');
161                     buf.append(put[i]);
162                 }
163             }
164             buf.append("}");
165             Log.log(Log.DEBUG,this,"fvmput(" + start + ","
166                 + end + "," + buf + ")");
167         }
168         int putl = (put == null ? 0 : put.length);
169 
170         int delta = putl - (end - start);
171         if(fvmcount + delta > fvm.length)
172         {
173             int[] newfvm = new int[fvm.length * 2 + 1];
174             System.arraycopy(fvm,0,newfvm,0,fvmcount);
175             fvm = newfvm;
176         }
177 
178         if(delta != 0)
179         {
180             System.arraycopy(fvm,end,fvm,start + putl,
181                 fvmcount - end);
182         }
183 
184         if(putl != 0)
185         {
186             System.arraycopy(put,0,fvm,start,put.length);
187         }
188 
189         fvmcount += delta;
190 
191         dump();
192 
193         if(fvmcount == 0)
194             throw new InternalError  ();
195     } //}}}
196 
197     //{{{ put2() method
198     /**
199      * Merge previous and next entry if necessary.
200      */
201     void put2(int starti, int endi, int start, int end)
202     {
203         if(Debug.FOLD_VIS_DEBUG)
204         {
205             Log.log(Log.DEBUG,this,"*fvmput2(" + starti + ","
206                 + endi + "," + start + "," + end + ")");
207         }
208         if(starti != -1 && fvm[starti] == start)
209         {
210             if(endi <= fvmcount - 2 && fvm[endi + 1]
211                 == end + 1)
212             {
213                 put(starti,endi + 2,null);
214             }
215             else
216             {
217                 put(starti,endi + 1,
218                     new int[] { end + 1 });
219             }
220         }
221         else
222         {
223             if(endi != fvmcount - 1 && fvm[endi + 1]
224                 == end + 1)
225             {
226                 put(starti + 1,endi + 2,
227                     new int[] { start });
228             }
229             else
230             {
231                 put(starti + 1,endi + 1,
232                     new int[] { start,
233                     end + 1 });
234             }
235         }
236     } //}}}
237 
238     //{{{ next() method
239     int next(int line)
240     {
241         int index = search(line);
242         /* in collapsed range */
243         if(index % 2 != 0)
244         {
245             /* beyond last visible line */
246             if(fvmcount == index + 1)
247                 return - 1;
248             /* start of next expanded range */
249             else
250                 return fvm[index + 1];
251         }
252         /* last in expanded range */
253         else if(line == fvm[index + 1] - 1)
254         {
255             /* equal to last visible line */
256             if(fvmcount == index + 2)
257                 return -1;
258             /* start of next expanded range */
259             else
260                 return fvm[index + 2];
261         }
262         /* next in expanded range */
263         else
264             return line + 1;
265     } //}}}
266 
267     //{{{ prev() method
268     int prev(int line)
269     {
270         int index = search(line);
271         /* before first visible line */
272         if(index == -1)
273             return -1;
274         /* in collapsed range */
275         else if(index % 2 == 1)
276         {
277             /* end of prev expanded range */
278             return fvm[index] - 1;
279         }
280         /* first in expanded range */
281         else if(line == fvm[index])
282         {
283             /* equal to first visible line */
284             if(index == 0)
285                 return -1;
286             /* end of prev expanded range */
287             else
288                 return fvm[index - 1] - 1;
289         }
290         /* prev in expanded range */
291         else
292             return line - 1;
293     } //}}}
294 
295     //{{{ show() method
296     void show(int start, int end)
297     {
298         int starti = search(start);
299         int endi = search(end);
300 
301         if(starti % 2 == 0)
302         {
303             if(endi % 2 == 0)
304                 put(starti + 1,endi + 1,null);
305             else
306             {
307                 if(endi != fvmcount - 1
308                     && fvm[endi + 1] == end + 1)
309                     put(starti + 1,endi + 2,null);
310                 else
311                 {
312                     put(starti + 1,endi,null);
313                     fvm[starti + 1] = end + 1;
314                 }
315             }
316         }
317         else
318         {
319             if(endi % 2 == 0)
320             {
321                 if(starti != -1 && fvm[starti] == start)
322                     put(starti,endi + 1,null);
323                 else
324                 {
325                     put(starti + 1,endi,null);
326                     fvm[starti + 1] = start;
327                 }
328             }
329             else
330                 put2(starti,endi,start,end);
331         }
332 
333         lastfvmget = -1;
334     } //}}}
335     
336     //{{{ hide() method
337     void hide(int start, int end)
338     {
339         int starti = search(start);
340         int endi = search(end);
341 
342         if(starti % 2 == 0)
343         {
344             if(endi % 2 == 0)
345                 put2(starti,endi,start,end);
346             else
347             {
348                 if(start == fvm[0])
349                     put(starti,endi + 1,null);
350                 else
351                 {
352                     put(starti + 1,endi,null);
353                     fvm[starti + 1] = start;
354                 }
355             }
356         }
357         else
358         {
359             if(endi % 2 == 0)
360             {
361                 if(end + 1 == fvm[fvmcount - 1])
362                     put(starti + 1,endi + 2,null);
363                 else
364                 {
365                     put(starti + 1,endi,null);
366                     fvm[starti + 1] = end + 1;
367                 }
368             }
369             else
370                 put(starti + 1,endi + 1,null);
371         }
372 
373         lastfvmget = -1;
374     } //}}}
375 
376     //{{{ count() method
377     int count()
378     {
379         return fvmcount;
380     } //}}}
381 
382     //{{{ dump() method
383     void dump()
384     {
385         if(Debug.FOLD_VIS_DEBUG)
386         {
387             StringBuffer   buf = new StringBuffer  ("{");
388             for(int i = 0; i < fvmcount; i++)
389             {
390                 if(i != 0)
391                     buf.append(',');
392                 buf.append(fvm[i]);
393             }
394             buf.append("}");
395             Log.log(Log.DEBUG,this,"fvm = " + buf);
396         }
397     } //}}}
398 
399     //{{{ contentInserted() method
400     void contentInserted(int startLine, int numLines)
401     {
402         if(numLines != 0)
403         {
404             int index = search(startLine);
405             int start = index + 1;
406 
407             for(int i = start; i < fvmcount; i++)
408                 fvm[i] += numLines;
409 
410             lastfvmget = -1;
411             dump();
412         }
413     } //}}}
414 
415     //{{{ preContentRemoved() method
416     /**
417      * @return If the anchors should be reset.
418      */
419     boolean preContentRemoved(int startLine, int numLines)
420     {
421         boolean returnValue = false;
422 
423         int endLine = startLine + numLines;
424 
425         /* update fold visibility map. */
426         int starti = search(startLine);
427         int endi = search(endLine);
428 
429         /* both have same visibility; just remove
430          * anything in between. */
431         if(Math.abs(starti % 2) == Math.abs(endi % 2))
432         {
433             if(endi - starti == fvmcount)
434             {
435                 // we're removing from before
436                 // the first visible to after
437                 // the last visible
438                 returnValue = true;
439                 starti = 1;
440             }
441             else
442             {
443                 put(starti + 1,endi + 1,null);
444                 starti++;
445             }
446         }
447         /* collapse 2 */
448         else if(starti != -1 && fvm[starti] == startLine)
449         {
450             if(endi - starti == fvmcount - 1)
451             {
452                 // we're removing from
453                 // the first visible to after
454                 // the last visible
455                 returnValue = true;
456                 starti = 1;
457             }
458             else
459                 put(starti,endi + 1,null);
460         }
461         /* shift */
462         else
463         {
464             put(starti + 1,endi,null);
465             fvm[starti + 1] = startLine;
466             starti += 2;
467         }
468 
469         /* update */
470         for(int i = starti; i < fvmcount; i++)
471             fvm[i] -= numLines;
472 
473         lastfvmget = -1;
474         dump();
475 
476         return returnValue;
477     } //}}}
478 
479     //{{{ Private members
480     private int[] fvm;
481     private int fvmcount;
482     private int lastfvmget;
483     //}}}
484 }
485
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags