ArrayStorage


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  package org.openide.util.lookup;
20  
21  import org.openide.util.Lookup;
22  
23  import java.io.*;
24  
25  import java.lang.ref.WeakReference  ;
26  
27  import java.util.*;
28  import org.openide.util.lookup.AbstractLookup.Pair;
29  
30  
31  /** ArrayStorage of Pairs from AbstractLookup.
32   * @author  Jaroslav Tulach
33   */
34  final class ArrayStorage extends Object  
35  implements AbstractLookup.Storage<ArrayStorage.Transaction> {
36      /** default trashold */
37      static final Integer   DEFAULT_TRASH = new Integer  (11);
38  
39      /** list of items */
40      private Object   content;
41  
42      /** linked list of refernces to results */
43      private transient AbstractLookup.ReferenceToResult<?> results;
44  
45      /** Constructor
46       */
47      public ArrayStorage() {
48          this(DEFAULT_TRASH);
49      }
50  
51      /** Constructs new ArrayStorage */
52      public ArrayStorage(Integer   treshhold) {
53          this.content = treshhold;
54      }
55  
56      /** Adds an item into the tree.
57      * @param item to add
58      * @return true if the Item has been added for the first time or false if some other
59      *    item equal to this one already existed in the lookup
60      */
61      public boolean add(AbstractLookup.Pair<?> item, Transaction changed) {
62          Object  [] arr = changed.current;
63  
64          if (changed.arr == null) {
65              // just simple add of one item
66              for (int i = 0; i < arr.length; i++) {
67                  if (arr[i] == null) {
68                      arr[i] = item;
69                      changed.add(item);
70  
71                      return true;
72                  }
73  
74                  if (arr[i].equals(item)) {
75                      // reassign the item number
76                      item.setIndex(null, ((AbstractLookup.Pair) arr[i]).getIndex());
77  
78                      // already there, but update it
79                      arr[i] = item;
80  
81                      return false;
82                  }
83              }
84  
85              // cannot happen as the beginTransaction ensured we can finish 
86              // correctly
87              throw new IllegalStateException  ();
88          } else {
89              // doing remainAll after that, let Transaction hold the new array
90              int newIndex = changed.addPair(item);
91  
92              for (int i = 0; i < arr.length; i++) {
93                  if (arr[i] == null) {
94                      changed.add(item);
95  
96                      return true;
97                  }
98  
99                  if (arr[i].equals(item)) {
100                     // already there
101                     if (i != newIndex) {
102                         // change in index
103                         changed.add(item);
104 
105                         return false;
106                     } else {
107                         // no change
108                         return false;
109                     }
110                 }
111             }
112 
113             // if not found in the original array
114             changed.add(item);
115 
116             return true;
117         }
118     }
119 
120     /** Removes an item.
121     */
122     public void remove(AbstractLookup.Pair item, Transaction changed) {
123         Object  [] arr = changed.current;
124 
125         int found = -1;
126 
127         for (int i = 0; i < arr.length;) {
128             if (arr[i] == null) {
129                 // end of task
130                 return;
131             }
132 
133             if ((found == -1) && arr[i].equals(item)) {
134                 // already there
135                 Pair<?> p = (Pair<?>)arr[i];
136                 p.setIndex(null, -1);
137                 changed.add(p);
138                 found = i;
139             }
140 
141             i++;
142 
143             if (found != -1) {
144                 if (i < arr.length) {
145                     // moving the array
146                     arr[i - 1] = arr[i];
147                 } else {
148                     arr[i - 1] = null;
149                 }
150             }
151         }
152     }
153 
154     /** Removes all items that are not present in the provided collection.
155     * @param retain Pair -> AbstractLookup.Info map
156     * @param notify set of Classes that has possibly changed
157     */
158     public void retainAll(Map retain, Transaction changed) {
159         Object  [] arr = changed.current;
160 
161         for (int from = 0; from < arr.length; from++) {
162             if (!(arr[from] instanceof AbstractLookup.Pair)) {
163                 // end of content
164                 break;
165             }
166 
167             AbstractLookup.Pair p = (AbstractLookup.Pair) arr[from];
168 
169             AbstractLookup.Info info = (AbstractLookup.Info) retain.get(p);
170 
171             if (info == null) {
172                 // was removed
173 
174                 /*
175                 if (info != null) {
176                 if (info.index < arr.length) {
177                     newArr[info.index] = p;
178                 }
179 
180                 if (p.getIndex() != info.index) {
181                     p.setIndex (null, info.index);
182                     changed.add (p);
183                 }
184                 } else {
185                 // removed
186                  */
187                 changed.add(p);
188             }
189         }
190     }
191 
192     /** Queries for instances of given class.
193     * @param clazz the class to check
194     * @return enumeration of Item
195     * @see #unsorted
196     */
197     public <T> Enumeration<Pair<T>> lookup(final Class  <T> clazz) {
198         class CheckEn implements org.openide.util.Enumerations.Processor<Object  ,Pair<T>> {
199             @SuppressWarnings  ("unchecked")
200             public Pair<T> process(Object   o, Collection ignore) {
201                 boolean ok;
202 
203                 if (o instanceof AbstractLookup.Pair) {
204                     ok = (clazz == null) || ((AbstractLookup.Pair) o).instanceOf(clazz);
205                 } else {
206                     ok = false;
207                 }
208 
209                 return ok ? (Pair<T>)o : null;
210             }
211         }
212 
213         if (content instanceof Object  []) {
214             Enumeration<Object  > all = org.openide.util.Enumerations.array((Object  []) content);
215             return org.openide.util.Enumerations.filter(all, new CheckEn());
216         } else {
217             return org.openide.util.Enumerations.empty();
218         }
219     }
220 
221     /** Associates another result with this storage.
222      */
223     public AbstractLookup.ReferenceToResult registerReferenceToResult(AbstractLookup.ReferenceToResult<?> newRef) {
224         AbstractLookup.ReferenceToResult prev = this.results;
225         this.results = newRef;
226 
227         return prev;
228     }
229 
230     /** Cleanup the references
231      */
232     public AbstractLookup.ReferenceToResult cleanUpResult(Lookup.Template<?> templ) {
233         AbstractLookup.ReferenceIterator it = new AbstractLookup.ReferenceIterator(this.results);
234 
235         while (it.next())
236             ;
237 
238         return this.results = it.first();
239     }
240 
241     /** We use a hash set of all modified Pair to handle the transaction */
242     public Transaction beginTransaction(int ensure) {
243         return new Transaction(ensure, content);
244     }
245 
246     /** Extract all results.
247      */
248     public void endTransaction(Transaction changed, Set<AbstractLookup.R> modified) {
249         AbstractLookup.ReferenceIterator it = new AbstractLookup.ReferenceIterator(this.results);
250 
251         if (changed.arr == null) {
252             // either add or remove, only check the content of check HashSet
253             while (it.next()) {
254                 AbstractLookup.ReferenceToResult ref = it.current();
255                 Iterator<Pair<?>> pairs = changed.iterator();
256 
257                 while (pairs.hasNext()) {
258                     AbstractLookup.Pair p = (AbstractLookup.Pair) pairs.next();
259 
260                     if (AbstractLookup.matches(ref.template, p, true)) {
261                         modified.add(ref.getResult());
262                     }
263                 }
264             }
265         } else {
266             // do full check of changes
267             while (it.next()) {
268                 AbstractLookup.ReferenceToResult ref = it.current();
269 
270                 int oldIndex = -1;
271                 int newIndex = -1;
272 
273                 for (;;) {
274                     oldIndex = findMatching(ref.template, changed.current, oldIndex);
275                     newIndex = findMatching(ref.template, changed.arr, newIndex);
276 
277                     if ((oldIndex == -1) && (newIndex == -1)) {
278                         break;
279                     }
280 
281                     if (
282                         (oldIndex == -1) || (newIndex == -1) ||
283                             !changed.current[oldIndex].equals(changed.arr[newIndex])
284                     ) {
285                         modified.add(ref.getResult());
286 
287                         break;
288                     }
289                 }
290             }
291         }
292 
293         this.results = it.first();
294         this.content = changed.newContent();
295     }
296 
297     private static int findMatching(Lookup.Template t, Object  [] arr, int from) {
298         while (++from < arr.length) {
299             if (arr[from] instanceof AbstractLookup.Pair) {
300                 if (AbstractLookup.matches(t, (AbstractLookup.Pair) arr[from], true)) {
301                     return from;
302                 }
303             }
304         }
305 
306         return -1;
307     }
308 
309     /** HashSet with additional field for new array which is callocated
310      * in case we are doing replace to hold all new items.
311      */
312     static final class Transaction extends HashSet<Pair<?>> {
313         /** array with current objects */
314         public final Object  [] current;
315 
316         /** array with new objects */
317         public final Object  [] arr;
318 
319         /** number of objects in the array */
320         private int cnt;
321 
322         public Transaction(int ensure, Object   currentContent) {
323             Integer   trashold;
324             Object  [] arr;
325 
326             if (currentContent instanceof Integer  ) {
327                 trashold = (Integer  ) currentContent;
328                 arr = null;
329             } else {
330                 arr = (Object  []) currentContent;
331 
332                 if (arr[arr.length - 1] instanceof Integer  ) {
333                     trashold = (Integer  ) arr[arr.length - 1];
334                 } else {
335                     // nowhere to grow we have reached the limit
336                     trashold = null;
337                 }
338             }
339 
340             int maxSize = (trashold == null) ? arr.length : trashold.intValue();
341 
342             if (ensure > maxSize) {
343                 throw new UnsupportedOperationException  ();
344             }
345 
346             if (ensure == -1) {
347                 // remove => it is ok
348                 this.current = (Object  []) currentContent;
349                 this.arr = null;
350 
351                 return;
352             }
353 
354             if (ensure == -2) {
355                 // adding one
356                 if (arr == null) {
357                     // first time add, let's allocate the array
358                     arr = new Object  [2];
359                     arr[1] = trashold;
360                 } else {
361                     if (arr[arr.length - 1] instanceof AbstractLookup.Pair) {
362                         // we are full
363                         throw new UnsupportedOperationException  ();
364                     } else {
365                         // ensure we have allocated enough space
366                         if (arr.length < 2 || arr[arr.length - 2] != null) {
367                             // double the array
368                             int newSize = (arr.length - 1) * 2;
369                             
370                             if (newSize <= 1) {
371                                 newSize = 2;
372                             }
373 
374                             if (newSize > maxSize) {
375                                 newSize = maxSize;
376 
377                                 if (newSize <= arr.length) {
378                                     // no space to get in
379                                     throw new UnsupportedOperationException  ();
380                                 }
381 
382                                 arr = new Object  [newSize];
383                             } else {
384                                 // still a lot of space
385                                 arr = new Object  [newSize + 1];
386                                 arr[newSize] = trashold;
387                             }
388 
389                             // copy content of original array without the last Integer into 
390                             // the new one
391                             System.arraycopy(currentContent, 0, arr, 0, ((Object  []) currentContent).length - 1);
392                         }
393                     }
394                 }
395 
396                 this.current = arr;
397                 this.arr = null;
398             } else {
399                 // allocate array for complete replacement
400                 if (ensure == maxSize) {
401                     this.arr = new Object  [ensure];
402                 } else {
403                     this.arr = new Object  [ensure + 1];
404                     this.arr[ensure] = trashold;
405                 }
406 
407                 this.current = (currentContent instanceof Object  []) ? (Object  []) currentContent : new Object  [0];
408             }
409         }
410 
411         public int addPair(AbstractLookup.Pair<?> p) {
412             p.setIndex(null, cnt);
413             arr[cnt++] = p;
414 
415             return p.getIndex();
416         }
417 
418         public Object   newContent() {
419             return (arr == null) ? current : arr;
420         }
421     }
422      // end of Transaction
423 }
424
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags