2
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
4
* Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
6
* The contents of this file are subject to the terms of either the GNU
7
* General Public License Version 2 only ("GPL") or the Common
8
* Development and Distribution License("CDDL") (collectively, the
9
* "License"). You may not use this file except in compliance with the
10
* License. You can obtain a copy of the License at
11
* http://www.netbeans.org/cddl-gplv2.html
12
* or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
13
* specific language governing permissions and limitations under the
14
* License. When distributing the software, include this License Header
15
* Notice in each file and include the License file at
16
* nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
17
* particular file as subject to the "Classpath" exception as provided
18
* by Sun in the GPL Version 2 section of the License file that
19
* accompanied this code. If applicable, add the following below the
20
* License Header, with the fields enclosed by brackets [] replaced by
21
* your own identifying information:
22
* "Portions Copyrighted [year] [name of copyright owner]"
26
* The Original Software is NetBeans. The Initial Developer of the Original
27
* Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
28
* Microsystems, Inc. All Rights Reserved.
30
* If you wish your version of this file to be governed by only the CDDL
31
* or only the GPL Version 2, indicate your decision by adding
32
* "[Contributor] elects to include this software in this distribution
33
* under the [CDDL or GPL Version 2] license." If you do not indicate a
34
* single choice of license, a recipient has the option to distribute
35
* your version of this file under either the CDDL, the GPL Version 2 or
36
* to extend the choice of license to its licensees as provided above.
37
* However, if you add GPL Version 2 code and therefore, elected the GPL
38
* Version 2 license, then the option applies only if the new code is
39
* made subject to such option by the copyright holder.
42
package org.netbeans.modules.editor.completion;
44
import java.util.BitSet;
46
import javax.swing.event.*;
48
/** Model that can compute its values lazily and moreover handle some
51
* Made public just to test an impl of Children.EntrySource based on this
54
public final class LazyListModel extends Object
55
implements ListModel, Runnable, javax.swing.event.ListDataListener {
56
/** means that the value has not yet been assigned */
57
private static int NOT_TESTED = Short.MIN_VALUE - 1;
58
private static int EMPTY_VALUE = Short.MIN_VALUE - 2;
59
/** skips extensive asserts - needed for performance tests */
60
private static final boolean skipExpensiveAsserts = Boolean.getBoolean ("org.openide.explorer.view.LazyListModel.skipExpensiveAsserts"); // NOI18N
64
private ListModel listModel;
65
private Filter filter;
66
/** the value to return when nothing else can be returned */
67
private Object defaultValue;
68
/** simple event listener list */
69
private javax.swing.event.EventListenerList list = new javax.swing.event.EventListenerList ();
71
/** the size of the original list we now know it has */
72
private int originalSize;
73
/** the size we currently pretend to have */
75
/** maps an external index to our internal one
76
* (NOT_TESTED, means it has not been tested yet, EMPTY_VALUE means for this external index
77
* we have returned default value)
79
private int[] external;
80
/** set with marked values where external is different than EMPTY_VALUE or NOT_TESTED */
81
private BitSet checked;
82
/** counts number of refused elements */
84
/** contains 1 if the bit mask if the index in listModel has already been tested */
85
private BitSet tested;
86
/** dirty means that we should really update assumptions */
87
private boolean markDirty;
89
private LazyListModel (ListModel m, Filter f, double expectedRadio, Object defaultValue) {
92
this.defaultValue = defaultValue;
94
// JST-PENDING: Weak or not?
95
m.addListDataListener (this);
98
final Filter getFilter () {
102
final boolean isComputed (int index) {
103
return tested != null && tested.get (index);
106
/** Makes itself dirty and schedules an update.
108
private void markDirty () {
109
this.markDirty = true;
110
getFilter ().scheduleUpdate (this);
113
/** When executed, updateYourAssumeptions.
122
System.err.println("updateYourAssumeptions ();"); // NOI18N
124
updateYourAssumeptions ();
127
/** Notifies removal of inteval from (inclusive) to (exclusive) and
128
* updates its structures.
130
* !!! as a side effect updates size !!!
132
* @return s - number of removals
134
private void notifyRemoval (int from, int to) {
135
ListDataEvent ev = new ListDataEvent (
136
this, ListDataEvent.INTERVAL_REMOVED, from, to - 1
138
removeInterval (external, from, to);
142
regenerateCheckedBitSet ();
146
private void regenerateCheckedBitSet () {
147
checked = new BitSet (size);
148
for (int i = 0; i < size; i++) {
149
if (external[i] >= 0) {
155
private int getExternal (int index) {
162
return external[index];
165
/** Can be called to ask the LazyListModel to update its assumptions,
166
* especially assumptions about the size to match its current knowledge.
168
final void updateYourAssumeptions () {
169
if (external == null) {
173
int sizeBefore = size;
174
int notifiedRemovals = 0;
177
LOOP: while (i < size) {
178
while (getExternal (i) >= 0 && i < size) {
185
if (getExternal (i) == NOT_TESTED) {
186
int minusOneIndex = i - 1;
187
while (i < size && getExternal (i) == NOT_TESTED) {
191
int count = i - minusOneIndex - 1;
192
int from = getExternal (minusOneIndex) + 1;
193
int to = getExternal (i);
195
assert from >= 0 : "Value at " + minusOneIndex + "(" + from + ") must be greater than minus one"; // NOI18N
196
assert to >= 0 : "Value at " + i + "must be greater than minus one but was: " + to; // NOI18N
197
assert to >= from : "Must be true: " + to + " >= " + from; // NOI18N
199
int howMuch = count - (to - from);
201
// we need to notify some kind of removal
202
notifyRemoval (i - howMuch, i);
206
int minusTwoIndex = i;
207
while (i < size && getExternal (i) == EMPTY_VALUE) {
210
notifyRemoval (minusTwoIndex, i);
215
assert externalContraints () : "Constraints failed"; // NOI18N
218
private boolean externalContraints () {
219
assert external != null : "Not null"; // NOI18N
220
assert external.length >= size : "Length " + external.length + " >= " + size; // NOI18N
221
if (!skipExpensiveAsserts) {
222
for (int i = 1; i < size; i++) {
223
assert external[i - 1] != NOT_TESTED || external[i] != EMPTY_VALUE : "There cannot be empty value after not tested value"; // NOI18N
224
assert external[i - 1] != EMPTY_VALUE || external[i] != NOT_TESTED : "Not tested cannot immediatelly follow empty value"; // NOI18N
225
assert external[i] < 0 || external[i] > external[i - 1] : "If valid index it has to be greater: " + i; // NOI18N
226
assert external[i] < 0 == !checked.get (i) : "external and checked must be consistent: " + i; // NOI18N
232
/** Removes an interval from array */
233
private static void removeInterval (int[] array, int index0, int index1) {
234
assert index0 < index1 : "Index1 must be bigger than index0: " + index1 + " > " + index0; // NOI18N
235
System.arraycopy (array, index1, array, index0, array.length - index1);
238
/** Factory method to create new filtering lazy model.
240
public static LazyListModel create (ListModel listModel, Filter f, double expectedRadio, Object defValue) {
241
return create (listModel, f, expectedRadio, defValue, false);
244
/** Model with enabled logging.
246
static LazyListModel create (ListModel listModel, Filter f, double expectedRadio, Object defValue, boolean log) {
247
LazyListModel lazy = new LazyListModel (listModel, f, expectedRadio, defValue);
256
public void addListDataListener(ListDataListener l) {
257
list.add (ListDataListener.class, l);
260
public void removeListDataListener(ListDataListener l) {
261
list.remove (ListDataListener.class, l);
264
private void fireChange (ListDataEvent ev) {
265
if (list.getListenerCount () == 0) return ;
267
Object[] arr = list.getListenerList ();
268
for (int i = arr.length - 1; i >= 0; i -= 2) {
269
ListDataListener l = (ListDataListener)arr[i];
270
switch (ev.getType ()) {
271
case ListDataEvent.CONTENTS_CHANGED: l.contentsChanged (ev); break;
272
case ListDataEvent.INTERVAL_ADDED: l.intervalAdded (ev); break;
273
case ListDataEvent.INTERVAL_REMOVED: l.intervalRemoved (ev); break;
275
throw new IllegalArgumentException ("Unknown type: " + ev.getType ());
280
/** Is this index accepted.
282
private boolean accepted (int indx, Object[] result) {
283
Object v = listModel.getElementAt (indx);
285
if (filter.accept (v)) {
294
/** Initialize the bitsets to sizes of the listModel.
296
private void initialize () {
297
if (tested == null) {
298
originalSize = listModel.getSize ();
299
size = listModel.getSize ();
300
tested = new BitSet (size);
301
external = new int[size];
302
for (int i = 0; i < size; i++) {
303
external[i] = NOT_TESTED;
305
checked = new BitSet (size);
307
assert externalContraints () : "Constraints failed"; // NOI18N
310
/** this variable is used from tests to prevent creation of elements in
313
static Boolean CREATE;
314
/** If value is not know for given index and CREATE.get() is Boolean.FALSE it returns defaultValue.
316
public Object getElementAt(int index) {
320
System.err.println("model.getElementAt (" + index + ");"); // NOI18N
323
if (external[index] >= 0) {
324
// we have computed the index, so return it
325
return listModel.getElementAt (external[index]);
328
if (external[index] == EMPTY_VALUE) {
329
// default value needs to be used
333
if (CREATE != null && !CREATE.booleanValue()) {
334
assert Thread.holdsLock(CREATE) : "Only one thread (from tests) can access this"; // NOI18N
339
// JST: Why there is no BitSet.previousSetBit!!!???
340
int minIndex = index;
341
while (minIndex >= 0 && getExternal (minIndex) < 0) {
345
if (checked.get (index)) {
348
maxIndex = checked.nextSetBit (index);
349
if (maxIndex == -1 || maxIndex > size) {
354
int myMinIndex = getExternal (minIndex) + 1; // one after the index of the first non-1 index
355
int myMaxIndex = getExternal (maxIndex);
357
assert myMaxIndex >= myMaxIndex : "Must be greater"; // NOI18N
358
if (myMaxIndex != myMinIndex) {
359
int myIndex = myMinIndex + (index - minIndex) - 1;
360
if (myIndex >= myMaxIndex) {
361
myIndex = myMaxIndex - 1;
364
Object[] result = new Object[1];
365
if (accepted (myIndex, result)) {
366
assert external[index] == NOT_TESTED : "External index " + index + " still needs to be unset: " + external[index];
367
external[index] = myIndex;
372
boolean checkBefore = true;
373
boolean checkAfter = true;
374
for (int i = 1; checkAfter || checkBefore; i++) {
376
checkBefore = index - i >= minIndex && myIndex - i >= myMinIndex && getExternal (index - i) == NOT_TESTED;
377
if (checkBefore && accepted (myIndex - i, result)) {
378
external[index] = myIndex - i;
384
checkAfter = index + i < maxIndex && myIndex + i < myMaxIndex && getExternal (index + i) == NOT_TESTED;
385
if (checkAfter && accepted (myIndex + i, result)) {
386
external[index] = myIndex + i;
396
// set default value for all objects in the interval
397
for (int i = minIndex + 1; i < maxIndex; i++) {
398
assert external[i] == NOT_TESTED : i + " should not be set: " + external[i]; // NOI18N
399
external[i] = EMPTY_VALUE;
401
checked.clear (minIndex + 1, maxIndex);
403
assert external[index] == EMPTY_VALUE : "Should be asigned in the cycle above"; // NOI18N
407
public int getSize() {
413
// Notifications from the underlaying model
416
/** Inserts specified amount of bits into the set.
418
private static BitSet insertAt (BitSet b, int at, int len, int size) {
419
BitSet before = b.get (0, at);
421
BitSet res = new BitSet (size);
424
int max = b.length ();
426
res.set (at + len, b.get (at));
431
/** Removes specified amount of bits from the set.
433
private static BitSet removeAt (BitSet b, int at, int len, int newSize) {
434
BitSet clone = (BitSet)b.clone ();
436
int max = b.length ();
438
clone.set (at, b.get (at + len));
441
clone.set (newSize, b.size (), false);
445
public void contentsChanged (ListDataEvent listDataEvent) {
446
throw new java.lang.UnsupportedOperationException ("Not yet implemented");
449
public void intervalAdded (ListDataEvent listDataEvent) {
450
if (external == null) {
454
updateYourAssumeptions ();
456
int first = listDataEvent.getIndex0 ();
457
int end = listDataEvent.getIndex1 () + 1;
458
int len = end - first;
460
int newOriginalSize = originalSize + len;
461
int newSize = size + len;
463
tested = insertAt (tested, first, len, newOriginalSize);
465
int insert = findExternalIndex (first);
466
int[] newExternal = new int[newSize];
467
System.arraycopy (external, 0, newExternal, 0, insert);
468
for (int i = 0; i < len; i++) {
469
newExternal[insert + i] = NOT_TESTED;
471
for (int i = insert + len; i < newExternal.length; i++) {
472
int v = external[i - len];
473
newExternal[i] = v < 0 ? v : v + len;
475
external = newExternal;
477
originalSize = newOriginalSize;
479
regenerateCheckedBitSet ();
481
fireChange (new ListDataEvent (this, ListDataEvent.INTERVAL_ADDED, insert, insert + len - 1));
482
assert externalContraints () : "Constraints failed"; // NOI18N
485
/** Finds the appropriate index of given internal index. The state is
486
* supposed to be after updateYourAssumeptions => no EMPTY_VALUE
488
private int findExternalIndex (int myIndex) {
490
for (int i = -1; i < size; i++) {
491
if (getExternal (i) == NOT_TESTED) {
494
outIndex = getExternal (i);
497
if (outIndex >= myIndex) {
504
public void intervalRemoved (ListDataEvent listDataEvent) {
505
if (external == null) {
509
updateYourAssumeptions ();
511
int first = listDataEvent.getIndex0 ();
512
int end = listDataEvent.getIndex1 () + 1;
513
int len = end - first;
515
int newOriginalSize = originalSize - len;
517
int f = findExternalIndex (first);
518
int e = findExternalIndex (end);
520
assert f >= 0 : "First index must be above zero: " + f; // NOI18N
521
assert e >= f : "End index must be above first: " + f + " <= " + e; // NOI18N
525
int[] newExternal = (int[])external.clone ();
526
for (int i = e; i < size; i++) {
528
newExternal[i - outLen] = v < 0 ? v : v - len;
529
checked.set (i - outLen, v >= 0);
531
external = newExternal;
533
originalSize = newOriginalSize;
536
fireChange (new ListDataEvent (this, ListDataEvent.INTERVAL_REMOVED, f, e - 1));
538
assert externalContraints () : "Constraints failed"; // NOI18N
542
/** Interface for those that wish to filter content of the list.
543
* This filter is expected to always return the same result for
544
* the same object - e.g. either always exclude or include it.
546
public interface Filter {
547
public boolean accept (Object obj);
548
/** This method is called when the list needs update. It's goal is
549
* usually to do SwingUtilities.invokeLater, even more rafined
550
* methods are allowed.
552
public void scheduleUpdate (Runnable run);