LazyListModel


1   /*
2    * The contents of this file are subject to the terms of the Common Development
3    * and Distribution License (the License). You may not use this file except in
4    * compliance with the License.
5    *
6    * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
7    * or http://www.netbeans.org/cddl.txt.
8    *
9    * When distributing Covered Code, include this CDDL Header Notice in each file
10   * and include the License file at http://www.netbeans.org/cddl.txt.
11   * If applicable, add the following below the CDDL Header, with the fields
12   * enclosed by brackets [] replaced by your own identifying information:
13   * "Portions Copyrighted [year] [name of copyright owner]"
14   *
15   * The Original Software is NetBeans. The Initial Developer of the Original
16   * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
17   * Microsystems, Inc. All Rights Reserved.
18   */
19  
20  package org.netbeans.modules.editor.completion;
21  
22  import java.util.BitSet  ;
23  import javax.swing.*;
24  import javax.swing.event.*;
25  
26  /** Model that can compute its values lazily and moreover handle some
27   * kind of filtering.
28   *
29   * Made public just to test an impl of Children.EntrySource based on this
30   * filtering list.
31  */
32  public final class LazyListModel extends Object   
33  implements ListModel, Runnable  , javax.swing.event.ListDataListener   {
34      /** means that the value has not yet been assigned */
35      private static int NOT_TESTED = Short.MIN_VALUE - 1;
36      private static int EMPTY_VALUE = Short.MIN_VALUE - 2;
37      /** skips extensive asserts - needed for performance tests */
38      private static final boolean skipExpensiveAsserts = Boolean.getBoolean ("org.openide.explorer.view.LazyListModel.skipExpensiveAsserts"); // NOI18N
39      
40      
41      private boolean log;
42      private ListModel listModel;
43      private Filter filter;
44      /** the value to return when nothing else can be returned */
45      private Object   defaultValue;
46      /** simple event listener list */
47      private javax.swing.event.EventListenerList   list = new javax.swing.event.EventListenerList   ();
48  
49      /** the size of the original list we now know it has */
50      private int originalSize;
51      /** the size we currently pretend to have */
52      private int size;
53      /** maps an external index to our internal one 
54       * (NOT_TESTED, means it has not been tested yet, EMPTY_VALUE means for this external index
55       * we have returned default value)
56       */
57      private int[] external;
58      /** set with marked values where external is different than EMPTY_VALUE or NOT_TESTED */
59      private BitSet   checked;
60      /** counts number of refused elements */
61      private int refused;
62      /** contains 1 if the bit mask if the index in listModel has already been tested */
63      private BitSet   tested;
64      /** dirty means that we should really update assumptions */
65      private boolean markDirty;
66      
67      private LazyListModel (ListModel m, Filter f, double expectedRadio, Object   defaultValue) {
68          this.listModel = m;
69          this.filter = f;
70          this.defaultValue = defaultValue;
71          
72          // JST-PENDING: Weak or not?
73          m.addListDataListener (this);
74      }
75      
76      final Filter getFilter () {
77          return filter;
78      }
79      
80      final boolean isComputed (int index) {
81          return tested != null && tested.get (index);
82      }
83      
84      /** Makes itself dirty and schedules an update.
85       */
86      private void markDirty () {
87          this.markDirty = true;
88          getFilter ().scheduleUpdate (this);
89      }
90      
91      /** When executed, updateYourAssumeptions.
92       */
93      public void run () {
94          if (!markDirty) {
95              return;
96          }
97  
98          markDirty = false;
99          if (log) {
100             System.err.println("updateYourAssumeptions ();"); // NOI18N
101         }
102         updateYourAssumeptions ();
103     }
104     
105     /** Notifies removal of inteval from (inclusive) to (exclusive) and
106      * updates its structures.
107      * 
108      * !!! as a side effect updates size !!!
109      *
110      * @return s - number of removals
111      */
112     private void notifyRemoval (int from, int to) {
113         ListDataEvent ev = new ListDataEvent (
114             this, ListDataEvent.INTERVAL_REMOVED, from, to - 1
115         );
116         removeInterval (external, from, to);
117         int cnt = to - from;
118         size -= cnt;
119         
120         regenerateCheckedBitSet ();
121         fireChange (ev);
122     }
123     
124     private void regenerateCheckedBitSet () {
125         checked = new BitSet   (size);
126         for (int i = 0; i < size; i++) {
127             if (external[i] >= 0) {
128                 checked.set (i);
129             }
130         }
131     }
132     
133     private int getExternal (int index) {
134         if (index == size) {
135             return originalSize;
136         }
137         if (index < 0) {
138             return -1;
139         }
140         return external[index];
141     }
142     
143     /** Can be called to ask the LazyListModel to update its assumptions, 
144      * especially assumptions about the size to match its current knowledge.
145      */
146     final void updateYourAssumeptions () {
147         if (external == null) {
148             return;
149         }
150         
151         int sizeBefore = size;
152         int notifiedRemovals = 0;
153         
154         int i = 0;
155         LOOP: while (i < size) {
156             while (getExternal (i) >= 0 && i < size) {
157                 i++;
158             }
159             if (i == size) {
160                 break;
161             }
162             
163             if (getExternal (i) == NOT_TESTED) {
164                 int minusOneIndex = i - 1;
165                 while (i < size && getExternal (i) == NOT_TESTED) { 
166                     i++;
167                 }
168                 
169                 int count = i - minusOneIndex - 1;
170                 int from = getExternal (minusOneIndex) + 1;
171                 int to = getExternal (i);
172                 
173                 assert from >= 0 : "Value at " + minusOneIndex + "(" + from + ") must be greater than minus one"; // NOI18N
174                 assert to >= 0 : "Value at " + i + "must be greater than minus one but was: " + to; // NOI18N
175                 assert to >= from : "Must be true: " + to + " >= " + from; // NOI18N
176 
177                 int howMuch = count - (to - from);
178                 if (howMuch > 0) {
179                     // we need to notify some kind of removal
180                     notifyRemoval (i - howMuch, i);
181                     i -= howMuch;
182                 }
183             } else {
184                 int minusTwoIndex = i;
185                 while (i < size && getExternal (i) == EMPTY_VALUE) {
186                     i++;
187                 }
188                 notifyRemoval (minusTwoIndex, i);
189                 i = minusTwoIndex;
190             }
191         }
192         
193         assert externalContraints () : "Constraints failed"; // NOI18N
194     }
195     
196     private boolean externalContraints () {
197         assert external != null : "Not null"; // NOI18N
198         assert external.length >= size : "Length " + external.length + " >= " + size; // NOI18N
199         if (!skipExpensiveAsserts) {
200             for (int i = 1; i < size; i++) {
201                 assert external[i - 1] != NOT_TESTED || external[i] != EMPTY_VALUE : "There cannot be empty value after not tested value"; // NOI18N
202                 assert external[i - 1] != EMPTY_VALUE || external[i] != NOT_TESTED : "Not tested cannot immediatelly follow empty value"; // NOI18N
203                 assert external[i] < 0 || external[i] > external[i - 1] : "If valid index it has to be greater: " + i; // NOI18N
204                 assert external[i] < 0 == !checked.get (i) : "external and checked must be consistent: " + i; // NOI18N
205             }
206         }
207         return true;
208     }
209     
210     /** Removes an interval from array */
211     private static void removeInterval (int[] array, int index0, int index1) {
212         assert index0 < index1 : "Index1 must be bigger than index0: " + index1 + " > " + index0; // NOI18N
213         System.arraycopy (array, index1, array, index0, array.length - index1);
214     }
215     
216     /** Factory method to create new filtering lazy model.
217      */
218     public static LazyListModel create (ListModel listModel, Filter f, double expectedRadio, Object   defValue) {
219         return create (listModel, f, expectedRadio, defValue, false);
220     }
221     
222     /** Model with enabled logging.
223      */
224     static LazyListModel create (ListModel listModel, Filter f, double expectedRadio, Object   defValue, boolean log) {
225         LazyListModel lazy = new LazyListModel (listModel, f, expectedRadio, defValue);
226         lazy.log = log;
227         return lazy;
228     }
229     
230     //
231     // Model methods.
232     //
233 
234     public void addListDataListener(ListDataListener l) {
235         list.add (ListDataListener.class, l);
236     }
237     
238     public void removeListDataListener(ListDataListener l) {
239         list.remove (ListDataListener.class, l);
240     }
241     
242     private void fireChange (ListDataEvent ev) {
243         if (list.getListenerCount () == 0) return ;
244         
245         Object  [] arr = list.getListenerList ();
246         for (int i = arr.length - 1; i >= 0; i -= 2) {
247             ListDataListener l = (ListDataListener)arr[i];
248             switch (ev.getType ()) {
249                 case ListDataEvent.CONTENTS_CHANGED: l.contentsChanged (ev); break;
250                 case ListDataEvent.INTERVAL_ADDED: l.intervalAdded (ev); break;
251                 case ListDataEvent.INTERVAL_REMOVED: l.intervalRemoved (ev); break;
252                 default:
253                     throw new IllegalArgumentException    ("Unknown type: " + ev.getType ());
254             }
255         }
256     }
257     
258     /** Is this index accepted.
259      */
260     private boolean accepted (int indx, Object  [] result) {
261         Object   v = listModel.getElementAt (indx);
262         tested.set (indx);
263         if (filter.accept (v)) {
264             result[0] = v;
265             return true;
266         }
267         
268         markDirty ();
269         return false;
270     }
271     
272     /** Initialize the bitsets to sizes of the listModel.
273      */
274     private void initialize () {
275         if (tested == null) {
276             originalSize = listModel.getSize ();
277             size = listModel.getSize ();
278             tested = new BitSet   (size);
279             external = new int[size];
280             for (int i = 0; i < size; i++) {
281                 external[i] = NOT_TESTED;
282             }
283             checked = new BitSet   (size);
284         }
285         assert externalContraints () : "Constraints failed"; // NOI18N
286     }
287     
288     /** this variable is used from tests to prevent creation of elements in
289      * certain cases.
290      */
291     static Boolean   CREATE;
292     /** If value is not know for given index and CREATE.get() is Boolean.FALSE it returns defaultValue.
293      */
294     public Object   getElementAt(int index) {
295         initialize ();
296         
297         if (log) {
298             System.err.println("model.getElementAt (" + index + ");"); // NOI18N
299         }
300         
301         if (external[index] >= 0) {
302             // we have computed the index, so return it
303             return listModel.getElementAt (external[index]);
304         }
305         
306         if (external[index] == EMPTY_VALUE) {
307             // default value needs to be used
308             return defaultValue;
309         }
310         
311         if (CREATE != null && !CREATE.booleanValue()) {
312             assert Thread.holdsLock(CREATE) : "Only one thread (from tests) can access this"; // NOI18N
313             return defaultValue;
314         }
315         
316         
317         // JST: Why there is no BitSet.previousSetBit!!!???
318         int minIndex = index;
319         while (minIndex >= 0 && getExternal (minIndex) < 0) {
320             minIndex--;
321         }
322         int maxIndex;
323         if (checked.get (index)) {
324             maxIndex = index; 
325         } else {
326             maxIndex = checked.nextSetBit (index);
327             if (maxIndex == -1 || maxIndex > size) {
328                 maxIndex = size;
329             }
330         }
331 
332         int myMinIndex = getExternal (minIndex) + 1; // one after the index of the first non-1 index
333         int myMaxIndex = getExternal (maxIndex);
334         
335         assert myMaxIndex >= myMaxIndex : "Must be greater"; // NOI18N        
336         if (myMaxIndex != myMinIndex) {
337             int myIndex = myMinIndex + (index - minIndex) - 1;
338             if (myIndex >= myMaxIndex) {
339                 myIndex = myMaxIndex - 1;
340             }
341 
342             Object  [] result = new Object  [1];
343             if (accepted (myIndex, result)) {
344                 assert external[index] == NOT_TESTED : "External index " + index + " still needs to be unset: " + external[index];
345                 external[index] = myIndex;
346                 checked.set (index);
347                 return result[0];
348             }
349 
350             boolean checkBefore = true;
351             boolean checkAfter = true;
352             for (int i = 1; checkAfter || checkBefore; i++) {
353                 if (checkBefore) {
354                     checkBefore = index - i >= minIndex && myIndex - i >= myMinIndex && getExternal (index - i) == NOT_TESTED;
355                     if (checkBefore && accepted (myIndex - i, result)) {
356                         external[index] = myIndex - i;
357                         checked.set (index);
358                         return result[0];
359                     }
360                 }
361                 if (checkAfter) {
362                     checkAfter = index + i < maxIndex && myIndex + i < myMaxIndex && getExternal (index + i) == NOT_TESTED;
363                     if (checkAfter && accepted (myIndex + i, result)) {
364                         external[index] = myIndex + i;
365                         checked.set (index);
366                         return result[0];
367                     }
368                 }
369             }
370         }
371         
372         markDirty ();
373 
374         // set default value for all objects in the interval
375         for (int i = minIndex + 1; i < maxIndex; i++) {
376             assert external[i] == NOT_TESTED : i + " should not be set: " + external[i]; // NOI18N
377             external[i] = EMPTY_VALUE;
378         }
379         checked.clear (minIndex + 1, maxIndex);
380         
381         assert external[index] == EMPTY_VALUE : "Should be asigned in the cycle above"; // NOI18N
382         return defaultValue;
383     }
384 
385     public int getSize() {
386         initialize ();
387         return size;
388     }
389     
390     //
391     // Notifications from the underlaying model
392     //
393     
394     /** Inserts specified amount of bits into the set.
395      */
396     private static BitSet   insertAt (BitSet   b, int at, int len, int size) {
397         BitSet   before = b.get (0, at);
398         
399         BitSet   res = new BitSet   (size);
400         res.or (before);
401         
402         int max = b.length ();
403         while (at < max) {
404             res.set (at + len, b.get (at));
405             at++;
406         }
407         return res;
408     }
409     /** Removes specified amount of bits from the set.
410      */
411     private static BitSet   removeAt (BitSet   b, int at, int len, int newSize) {
412         BitSet   clone = (BitSet  )b.clone ();
413         
414         int max = b.length ();
415         while (at < max) {
416             clone.set (at, b.get (at + len));
417             at++;
418         }
419         clone.set (newSize, b.size (), false);
420         return clone;
421     }
422 
423     public void contentsChanged (ListDataEvent listDataEvent) {
424         throw new java.lang.UnsupportedOperationException   ("Not yet implemented");
425     }
426 
427     public void intervalAdded (ListDataEvent listDataEvent) {
428         if (external == null) {
429             return;
430         }
431         
432         updateYourAssumeptions ();
433         
434         int first = listDataEvent.getIndex0 ();
435         int end = listDataEvent.getIndex1 () + 1; 
436         int len = end - first;
437         
438         int newOriginalSize = originalSize + len;
439         int newSize = size + len;
440         
441         tested = insertAt (tested, first, len, newOriginalSize);
442         
443         int insert = findExternalIndex (first);
444         int[] newExternal = new int[newSize];
445         System.arraycopy (external, 0, newExternal, 0, insert);
446         for (int i = 0; i < len; i++) {
447             newExternal[insert + i] = NOT_TESTED;
448         }
449         for (int i = insert + len; i < newExternal.length; i++) {
450             int v = external[i - len];
451             newExternal[i] = v < 0 ? v : v + len;
452         }
453         external = newExternal;
454         size = newSize;
455         originalSize = newOriginalSize;
456 
457         regenerateCheckedBitSet ();
458 
459         fireChange (new ListDataEvent (this, ListDataEvent.INTERVAL_ADDED, insert, insert + len - 1));
460         assert externalContraints () : "Constraints failed"; // NOI18N
461     }
462     
463     /** Finds the appropriate index of given internal index. The state is 
464      * supposed to be after updateYourAssumeptions => no EMPTY_VALUE
465      */
466     private int findExternalIndex (int myIndex) {
467         int outIndex = 0;
468         for (int i = -1; i < size; i++) {
469             if (getExternal (i) == NOT_TESTED) {
470                 outIndex++;
471             } else {
472                 outIndex = getExternal (i);
473             }
474             
475             if (outIndex >= myIndex) {
476                 return i;
477             }
478         }
479         return size;
480     }
481 
482     public void intervalRemoved (ListDataEvent listDataEvent) {
483         if (external == null) {
484             return;
485         }
486         
487         updateYourAssumeptions ();
488         
489         int first = listDataEvent.getIndex0 ();
490         int end = listDataEvent.getIndex1 () + 1; 
491         int len = end - first;
492 
493         int newOriginalSize = originalSize - len;
494         
495         int f = findExternalIndex (first);
496         int e = findExternalIndex (end);
497         
498         assert f >= 0 : "First index must be above zero: " + f; // NOI18N
499         assert e >= f : "End index must be above first: " + f + " <= " + e; // NOI18N
500         
501         int outLen = e - f;
502         
503         int[] newExternal = (int[])external.clone ();
504         for (int i = e; i < size; i++) {
505             int v = external[i];
506             newExternal[i - outLen] = v < 0 ? v : v - len;
507             checked.set (i - outLen, v >= 0);
508         }
509         external = newExternal;
510         size -= outLen;
511         originalSize = newOriginalSize;
512         
513         if (outLen != 0) {
514             fireChange (new ListDataEvent (this, ListDataEvent.INTERVAL_REMOVED, f, e - 1));
515         }
516         assert externalContraints () : "Constraints failed"; // NOI18N
517    }
518 
519     
520     /** Interface for those that wish to filter content of the list.
521      * This filter is expected to always return the same result for
522      * the same object - e.g. either always exclude or include it.
523      */
524     public interface Filter {
525         public boolean accept (Object   obj);
526         /** This method is called when the list needs update. It's goal is
527          * usually to do SwingUtilities.invokeLater, even more rafined 
528          * methods are allowed.
529          */
530         public void scheduleUpdate (Runnable   run);
531     }
532 }
533
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags