ObjectArrayUtilities


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.editor;
21  
22  import java.util.Comparator  ;
23  
24  /**
25   * Utilities over object array.
26   *
27   * @author Miloslav Metelka
28   * @version 1.00
29   */
30  
31  public class ObjectArrayUtilities {
32  
33      private ObjectArrayUtilities() {
34          // no instances
35      }
36  
37      /**
38       * Searches the specified object array for the specified object using the binary
39       * search algorithm.  The object array must be sorted into ascending order
40       * according to the <i>natural ordering</i> of its items. If it is
41       * not sorted, the results are undefined.  If the object array contains multiple
42       * elements equal to the specified object, there is no guarantee which one
43       * will be found.
44       * <BR>This method runs in log(n) time.
45       * @param  objectArray object array to be searched.
46       * @param  key the key to be searched for.
47       * @return index of the search key, if it is contained in the object array;
48       *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
49       *         <i>insertion point</i> is defined as the point at which the
50       *         key would be inserted into the object array: the index of the first
51       *         element greater than the key, or <tt>objectArray.getItemCount()</tt>, if all
52       *         elements in the object array are less than the specified key.  Note
53       *         that this guarantees that the return value will be &gt;= 0 if
54       *         and only if the key is found.
55       * @throws ClassCastException if the object array contains elements that are not
56       *         <i>mutually comparable</i> (for example, strings and
57       *         integers), or the search key in not mutually comparable
58       *         with the elements of the object array.
59       * @see    Comparable
60       */
61      public static int binarySearch(ObjectArray objectArray, Object   key) {
62          int low = 0;
63          int high = objectArray.getItemCount() - 1;
64          
65          while (low <= high) {
66              int mid = (low + high) >> 1;
67              Object   midVal = objectArray.getItem(mid);
68              int cmp = ((Comparable  )midVal).compareTo(key);
69              
70              if (cmp < 0)
71                  low = mid + 1;
72              else if (cmp > 0)
73                  high = mid - 1;
74              else
75                  return mid; // key found
76          }
77  
78          return -(low + 1);  // key not found
79      }
80  
81      /**
82       * Perform binary search with the specified comparator. The more detailed
83       * description is given in the doc for {@link #binarySearch(ObjectArray, Object)}.
84       * @param objectArray object array to be searched.
85       * @param key key to search for.
86       * @param c comparator to be used to compare the items.
87       * @return index of the search key, if it is contained in the object array;
88       *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.
89       * @see binarySearch(ObjectArray, Object)
90       */
91      public static int binarySearch(ObjectArray objectArray, Object   key, Comparator   c) {
92          int low = 0;
93          int high = objectArray.getItemCount() - 1;
94          
95          while (low <= high) {
96              int mid = (low + high) >> 1;
97              Object   midVal = objectArray.getItem(mid);
98              int cmp = c.compare(midVal, key);
99              
100             if (cmp < 0)
101                 low = mid + 1;
102             else if (cmp > 0)
103                 high = mid - 1;
104             else
105                 return mid; // key found
106         }
107 
108         return -(low + 1);  // key not found
109     }
110     
111     /**
112      * Get index of the occurrence of the given item in the object array
113      * by using binary search and scanning the adjacent items
114      * that are equal copmared to the searched item.
115      * @param objectArray object array containing the item.
116      * @param item object to be found.
117      * @return index of the found object. The object must be the same physical
118      *  instance as the search item.
119      *  <BR>For multiple occurrences of the item in the object array
120      *  a random occurrence is returned.
121      *  <BR>If the object is not found in the objectArray then
122      *  this method returns -1.
123      */
124     public static int findIndex(ObjectArray objectArray, Object   item) {
125         int index = binarySearch(objectArray, item);
126 
127         if (index < 0) { // nothing equal to item found
128             return -1;
129         }
130         if (objectArray.getItem(index) == item) {
131             return index;
132         }
133 
134         int cnt = objectArray.getItemCount();
135         for (int upIndex = index + 1; upIndex < cnt; upIndex++) {
136             Object   indexItem = objectArray.getItem(upIndex);
137             if (indexItem == item) {
138                 return upIndex;
139             }
140             if (((Comparable  )item).compareTo(indexItem) != 0) {
141                 break;
142             }
143         }
144 
145         while (--index >= 0) {
146             Object   indexItem = objectArray.getItem(index);
147             if (indexItem == item) {
148                 return index;
149             }
150             if (((Comparable  )item).compareTo(indexItem) != 0) {
151                 break;
152             }
153         }
154 
155         return -1;
156     }
157 
158     /**
159      * Get index of the occurrence of the given item in the object array
160      * by using binary search and scanning the adjacent items
161      * that are equal copmared to the searched item.
162      * @param objectArray object array containing the item.
163      * @param item object to be found.
164      * @param c comparator to use to compare the items.
165      * @return index of the found object. The object must be the same physical
166      *  instance as the search item.
167      *  <BR>For multiple occurrences of the item in the object array
168      *  a random occurrence is returned.
169      *  <BR>If the object is not found in the objectArray then
170      *  this method returns -1.
171      */
172     public static int findIndex(ObjectArray objectArray, Object   item, Comparator   c) {
173         int index = binarySearch(objectArray, item, c);
174 
175         if (index < 0) { // nothing equal to item found
176             return -1;
177         }
178         if (objectArray.getItem(index) == item) {
179             return index;
180         }
181 
182         int cnt = objectArray.getItemCount();
183         for (int upIndex = index + 1; upIndex < cnt; upIndex++) {
184             Object   indexItem = objectArray.getItem(upIndex);
185             if (indexItem == item) {
186                 return upIndex;
187             }
188             if (c.compare(item, indexItem) != 0) {
189                 break;
190             }
191         }
192 
193         while (--index >= 0) {
194             Object   indexItem = objectArray.getItem(index);
195             if (indexItem == item) {
196                 return index;
197             }
198             if (c.compare(item, indexItem) != 0) {
199                 break;
200             }
201         }
202 
203         return -1;
204     }
205 
206     /**
207      * Create array and fill it with all the items from the given objectArray.
208      * @param objectArray objectArray containing items to copy.
209      * @return array containing all the items from the given objectArray.
210      */
211     public static Object  [] toArray(ObjectArray objectArray) {
212         return toArray(objectArray, 0, objectArray.getItemCount());
213     }
214     
215     /**
216      * Create array and fill it with the items from the given objectArray.
217      * @param objectArray objectArray containing items to copy.
218      * @param startIndex index of the first item to copy.
219      * @param endIndex index that follows the last item to copy.
220      * @return array containing the requested items from the given objectArray.
221      */
222     public static Object  [] toArray(ObjectArray objectArray, int startIndex, int endIndex) {
223         Object  [] dest = new Object  [endIndex - startIndex];
224         copyItems(objectArray, startIndex, endIndex, dest, 0);
225         return dest;
226     }
227 
228     /**
229      * Copy all items from the given object array into destination array.
230      * @param srcObjectArray objectArray containing items to copy.
231      * @param dest array into which the items will be copied (at index zero).
232      */
233     public static void copyItems(ObjectArray srcObjectArray, Object  [] dest) {
234         copyItems(srcObjectArray, 0, srcObjectArray.getItemCount(), dest, 0);
235     }
236 
237     /**
238      * Copy items from the given object array into destination array.
239      * @param srcObjectArray objectArray containing items to copy.
240      * @param srcStartIndex index of the first item in the objectArray to copy.
241      * @param srcEndIndex index that follows the last item in the objectArray to copy.
242      * @param dest array into which the items will be copied.
243      * @param destIndex index in the destination array at which the placing
244      *  of the copied items will be started.
245      */
246     public static void copyItems(ObjectArray srcObjectArray,
247     int srcStartIndex, int srcEndIndex, Object  [] dest, int destIndex) {
248      
249         if (srcObjectArray instanceof ObjectArray.CopyItems) {
250             ((ObjectArray.CopyItems)srcObjectArray).copyItems(
251                 srcStartIndex, srcEndIndex, dest, destIndex);
252 
253         } else {
254             while (srcStartIndex < srcEndIndex) {
255                 dest[destIndex++] = srcObjectArray.getItem(srcStartIndex++);
256             }
257         }
258     }
259 
260     /**
261      * Utility method to reverse order of the elements in the given array.
262      * @param array array to be reversed.
263      */
264     public static void reverse(Object  [] array) {
265         for (int i = 0, j = array.length - 1; i < j; i++, j--) {
266             Object   o = array[i];
267             array[i] = array[j];
268             array[j] = o;
269         }
270     }
271 
272 
273     public static ObjectArray.Modification mergeModifications(final ObjectArray.Modification mod1, final ObjectArray.Modification mod2) {
274         if (mod1.getArray() != mod2.getArray()) {
275             throw new IllegalArgumentException  ("Cannot merge modifications to different object arrays."); // NOI18N
276         }
277         final int index;
278         final Object  [] addedItems;
279         final int removedItemsCount;
280         if (mod1.getIndex() <= mod2.getIndex()) {
281             index = mod1.getIndex();
282             int overlap = Math.min(mod1.getIndex() + mod1.getAddedItems().length - mod2.getIndex(), mod2.getRemovedItemsCount());
283             addedItems = new Object  [mod1.getAddedItems().length + mod2.getAddedItems().length - overlap];
284             if (overlap < 0) { // disjunkt modifications
285                 System.arraycopy(mod1.getAddedItems(), 0, addedItems, 0, mod1.getAddedItems().length);
286                 copyItems(mod1.getArray(), mod1.getIndex() + mod1.getRemovedItemsCount(), mod1.getIndex() + mod1.getRemovedItemsCount() - overlap, addedItems, mod1.getAddedItems().length);
287                 System.arraycopy(mod2.getAddedItems(), 0, addedItems, mod2.getIndex() - mod1.getIndex(), mod2.getAddedItems().length);
288             } else { // mod2 overlaps mod1
289                 System.arraycopy(mod1.getAddedItems(), 0, addedItems, 0, mod2.getIndex() - mod1.getIndex());
290                 System.arraycopy(mod2.getAddedItems(), 0, addedItems, mod2.getIndex() - mod1.getIndex(), mod2.getAddedItems().length);
291                 System.arraycopy(mod1.getAddedItems(), mod2.getIndex() - mod1.getIndex() + overlap, addedItems, mod2.getIndex() - mod1.getIndex() + mod2.getAddedItems().length, mod1.getAddedItems().length - mod2.getIndex() + mod1.getIndex() - overlap);
292             }
293             removedItemsCount = mod1.getRemovedItemsCount() + mod2.getRemovedItemsCount() - overlap;
294         } else {
295             index = mod2.getIndex();
296             int overlap = Math.min(mod2.getIndex() + mod2.getRemovedItemsCount() - mod1.getIndex(), mod1.getAddedItems().length);
297             addedItems = new Object  [mod1.getAddedItems().length + mod2.getAddedItems().length - overlap];
298             System.arraycopy(mod2.getAddedItems(), 0, addedItems, 0, mod2.getAddedItems().length);
299             if (overlap < 0) { // disjunkt modifiations
300                 copyItems(mod1.getArray(), mod2.getIndex() + mod2.getRemovedItemsCount(), mod1.getIndex(), addedItems, mod2.getAddedItems().length);
301                 System.arraycopy(mod1.getAddedItems(), 0, addedItems, mod2.getAddedItems().length - overlap, mod1.getAddedItems().length);
302             } else { // mod2 overlaps mod1
303                 System.arraycopy(mod1.getAddedItems(), overlap, addedItems, mod2.getAddedItems().length, mod1.getAddedItems().length - overlap);
304             }
305             removedItemsCount = mod1.getRemovedItemsCount() + mod2.getRemovedItemsCount() - overlap;
306         }
307         return new ObjectArray.Modification () {
308             public ObjectArray getArray() {
309                 return mod1.getArray();
310             }
311             public int getIndex() {
312                 return index;
313             }
314             public Object  [] getAddedItems() {
315                 return addedItems;
316             }
317             public int getRemovedItemsCount() {
318                 return removedItemsCount;
319             }
320         };
321     }
322 
323     public static ObjectArray.Modification mergeModifications(ObjectArray.Modification[] mods) {
324         ObjectArray.Modification ret = mods.length > 0 ? mods[0] : null;
325         for (int i = 1; i < mods.length; i++) {
326             ret = mergeModifications(ret, mods[i]);
327         }
328         return ret;
329     }
330 }
331
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags