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.java.ui;
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     /** This method is currently called from org.openide.nodes.EntrySupport to create lazy filtering list
231      * for nodes, excludes everything that is not node, as default value it return null
232      * @param model model to filter
233      */
234     public static LazyListModel create (final org.openide.nodes.Children.Keys ch, ListModel model) {
235         class NodeF implements Filter {
236             private java.lang.reflect.Method   m;
237             
238             public boolean accept (Object   obj) {
239                 return obj instanceof org.openide.nodes.Node;
240             }
241             public void scheduleUpdate (Runnable   run) {
242                 try {
243                     if (m == null) {
244                         m = org.openide.nodes.Children.Keys.class.getDeclaredMethod (
245                             "updateMyAssumptions", // NOI18N
246                             new Class  [] { Runnable  .class }
247                         ); 
248                         m.setAccessible (true);
249                     }
250                     m.invoke (ch, new Object  [] { run });
251                 } catch (Exception   ex) {
252                     IllegalStateException   i = new IllegalStateException   (ex.getMessage ());
253                     i.initCause (ex);
254                     throw i;
255                 }
256             }
257         }
258         
259         return create (model, new NodeF (), 1.0, null);
260     }
261     
262     //
263     // Model methods.
264     //
265 
266     public void addListDataListener(ListDataListener l) {
267         list.add (ListDataListener.class, l);
268     }
269     
270     public void removeListDataListener(ListDataListener l) {
271         list.remove (ListDataListener.class, l);
272     }
273     
274     private void fireChange (ListDataEvent ev) {
275         if (list.getListenerCount () == 0) return ;
276         
277         Object  [] arr = list.getListenerList ();
278         for (int i = arr.length - 1; i >= 0; i -= 2) {
279             ListDataListener l = (ListDataListener)arr[i];
280             switch (ev.getType ()) {
281                 case ListDataEvent.CONTENTS_CHANGED: l.contentsChanged (ev); break;
282                 case ListDataEvent.INTERVAL_ADDED: l.intervalAdded (ev); break;
283                 case ListDataEvent.INTERVAL_REMOVED: l.intervalRemoved (ev); break;
284                 default:
285                     throw new IllegalArgumentException    ("Unknown type: " + ev.getType ());
286             }
287         }
288     }
289     
290     /** Is this index accepted.
291      */
292     private boolean accepted (int indx, Object  [] result) {
293         Object   v = listModel.getElementAt (indx);
294         tested.set (indx);
295         if (filter.accept (v)) {
296             result[0] = v;
297             return true;
298         }
299         
300         markDirty ();
301         return false;
302     }
303     
304     /** Initialize the bitsets to sizes of the listModel.
305      */
306     private void initialize () {
307         if (tested == null) {
308             originalSize = listModel.getSize ();
309             size = listModel.getSize ();
310             tested = new BitSet   (size);
311             external = new int[size];
312             for (int i = 0; i < size; i++) {
313                 external[i] = NOT_TESTED;
314             }
315             checked = new BitSet   (size);
316         }
317         assert externalContraints () : "Constraints failed"; // NOI18N
318     }
319     
320     /** this variable is used from tests to prevent creation of elements in
321      * certain cases.
322      */
323     static Boolean   CREATE;
324     /** If value is not know for given index and CREATE.get() is Boolean.FALSE it returns defaultValue.
325      */
326     public Object   getElementAt(int index) {
327         initialize ();
328         
329         if (log) {
330             System.err.println("model.getElementAt (" + index + ");"); // NOI18N
331         }
332         
333         if (external[index] >= 0) {
334             // we have computed the index, so return it
335             return listModel.getElementAt (external[index]);
336         }
337         
338         if (external[index] == EMPTY_VALUE) {
339             // default value needs to be used
340             return defaultValue;
341         }
342         
343         if (CREATE != null && !CREATE.booleanValue()) {
344             assert Thread.holdsLock(CREATE) : "Only one thread (from tests) can access this"; // NOI18N
345             return defaultValue;
346         }
347         
348         
349         // JST: Why there is no BitSet.previousSetBit!!!???
350         int minIndex = index;
351         while (minIndex >= 0 && getExternal (minIndex) < 0) {
352             minIndex--;
353         }
354         int maxIndex;
355         if (checked.get (index)) {
356             maxIndex = index; 
357         } else {
358             maxIndex = checked.nextSetBit (index);
359             if (maxIndex == -1 || maxIndex > size) {
360                 maxIndex = size;
361             }
362         }
363 
364         int myMinIndex = getExternal (minIndex) + 1; // one after the index of the first non-1 index
365         int myMaxIndex = getExternal (maxIndex);
366         
367         assert myMaxIndex >= myMaxIndex : "Must be greater"; // NOI18N        
368         if (myMaxIndex != myMinIndex) {
369             int myIndex = myMinIndex + (index - minIndex) - 1;
370             if (myIndex >= myMaxIndex) {
371                 myIndex = myMaxIndex - 1;
372             }
373 
374             Object  [] result = new Object  [1];
375             if (accepted (myIndex, result)) {
376                 assert external[index] == NOT_TESTED : "External index " + index + " still needs to be unset: " + external[index];
377                 external[index] = myIndex;
378                 checked.set (index);
379                 return result[0];
380             }
381 
382             boolean checkBefore = true;
383             boolean checkAfter = true;
384             for (int i = 1; checkAfter || checkBefore; i++) {
385                 if (checkBefore) {
386                     checkBefore = index - i >= minIndex && myIndex - i >= myMinIndex && getExternal (index - i) == NOT_TESTED;
387                     if (checkBefore && accepted (myIndex - i, result)) {
388                         external[index] = myIndex - i;
389                         checked.set (index);
390                         return result[0];
391                     }
392                 }
393                 if (checkAfter) {
394                     checkAfter = index + i < maxIndex && myIndex + i < myMaxIndex && getExternal (index + i) == NOT_TESTED;
395                     if (checkAfter && accepted (myIndex + i, result)) {
396                         external[index] = myIndex + i;
397                         checked.set (index);
398                         return result[0];
399                     }
400                 }
401             }
402         }
403         
404         markDirty ();
405 
406         // set default value for all objects in the interval
407         for (int i = minIndex + 1; i < maxIndex; i++) {
408             assert external[i] == NOT_TESTED : i + " should not be set: " + external[i]; // NOI18N
409             external[i] = EMPTY_VALUE;
410         }
411         checked.clear (minIndex + 1, maxIndex);
412         
413         assert external[index] == EMPTY_VALUE : "Should be asigned in the cycle above"; // NOI18N
414         return defaultValue;
415     }
416 
417     public int getSize() {
418         initialize ();
419         return size;
420     }
421     
422     //
423     // Notifications from the underlaying model
424     //
425     
426     /** Inserts specified amount of bits into the set.
427      */
428     private static BitSet   insertAt (BitSet   b, int at, int len, int size) {
429         BitSet   before = b.get (0, at);
430         
431         BitSet   res = new BitSet   (size);
432         res.or (before);
433         
434         int max = b.length ();
435         while (at < max) {
436             res.set (at + len, b.get (at));
437             at++;
438         }
439         return res;
440     }
441     /** Removes specified amount of bits from the set.
442      */
443     private static BitSet   removeAt (BitSet   b, int at, int len, int newSize) {
444         BitSet   clone = (BitSet  )b.clone ();
445         
446         int max = b.length ();
447         while (at < max) {
448             clone.set (at, b.get (at + len));
449             at++;
450         }
451         clone.set (newSize, b.size (), false);
452         return clone;
453     }
454 
455     public void contentsChanged (ListDataEvent listDataEvent) {
456         throw new java.lang.UnsupportedOperationException   ("Not yet implemented");
457     }
458 
459     public void intervalAdded (ListDataEvent listDataEvent) {
460         if (external == null) {
461             return;
462         }
463         
464         updateYourAssumeptions ();
465         
466         int first = listDataEvent.getIndex0 ();
467         int end = listDataEvent.getIndex1 () + 1; 
468         int len = end - first;
469         
470         int newOriginalSize = originalSize + len;
471         int newSize = size + len;
472         
473         tested = insertAt (tested, first, len, newOriginalSize);
474         
475         int insert = findExternalIndex (first);
476         int[] newExternal = new int[newSize];
477         System.arraycopy (external, 0, newExternal, 0, insert);
478         for (int i = 0; i < len; i++) {
479             newExternal[insert + i] = NOT_TESTED;
480         }
481         for (int i = insert + len; i < newExternal.length; i++) {
482             int v = external[i - len];
483             newExternal[i] = v < 0 ? v : v + len;
484         }
485         external = newExternal;
486         size = newSize;
487         originalSize = newOriginalSize;
488 
489         regenerateCheckedBitSet ();
490 
491         fireChange (new ListDataEvent (this, ListDataEvent.INTERVAL_ADDED, insert, insert + len - 1));
492         assert externalContraints () : "Constraints failed"; // NOI18N
493     }
494     
495     /** Finds the appropriate index of given internal index. The state is 
496      * supposed to be after updateYourAssumeptions => no EMPTY_VALUE
497      */
498     private int findExternalIndex (int myIndex) {
499         int outIndex = 0;
500         for (int i = -1; i < size; i++) {
501             if (getExternal (i) == NOT_TESTED) {
502                 outIndex++;
503             } else {
504                 outIndex = getExternal (i);
505             }
506             
507             if (outIndex >= myIndex) {
508                 return i;
509             }
510         }
511         return size;
512     }
513 
514     public void intervalRemoved (ListDataEvent listDataEvent) {
515         if (external == null) {
516             return;
517         }
518         
519         updateYourAssumeptions ();
520         
521         int first = listDataEvent.getIndex0 ();
522         int end = listDataEvent.getIndex1 () + 1; 
523         int len = end - first;
524 
525         int newOriginalSize = originalSize - len;
526         
527         int f = findExternalIndex (first);
528         int e = findExternalIndex (end);
529         
530         assert f >= 0 : "First index must be above zero: " + f; // NOI18N
531         assert e >= f : "End index must be above first: " + f + " <= " + e; // NOI18N
532         
533         int outLen = e - f;
534         
535         int[] newExternal = (int[])external.clone ();
536         for (int i = e; i < size; i++) {
537             int v = external[i];
538             newExternal[i - outLen] = v < 0 ? v : v - len;
539             checked.set (i - outLen, v >= 0);
540         }
541         external = newExternal;
542         size -= outLen;
543         originalSize = newOriginalSize;
544         
545         if (outLen != 0) {
546             fireChange (new ListDataEvent (this, ListDataEvent.INTERVAL_REMOVED, f, e - 1));
547         }
548         assert externalContraints () : "Constraints failed"; // NOI18N
549    }
550 
551     
552     /** Interface for those that wish to filter content of the list.
553      * This filter is expected to always return the same result for
554      * the same object - e.g. either always exclude or include it.
555      */
556     public interface Filter {
557         public boolean accept (Object   obj);
558         /** This method is called when the list needs update. It's goal is
559          * usually to do SwingUtilities.invokeLater, even more rafined 
560          * methods are allowed.
561          */
562         public void scheduleUpdate (Runnable   run);
563     }
564 }
565
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags