1 // ========================================================================
2 // Copyright (c) 2004-2009 Mort Bay Consulting Pty. Ltd.
3 // ------------------------------------------------------------------------
4 // All rights reserved. This program and the accompanying materials
5 // are made available under the terms of the Eclipse Public License v1.0
6 // and Apache License v2.0 which accompanies this distribution.
7 // The Eclipse Public License is available at
8 // http://www.eclipse.org/legal/epl-v10.html
9 // The Apache License v2.0 is available at
10 // http://www.opensource.org/licenses/apache2.0.php
11 // You may elect to redistribute this code under either of these licenses.
12 // ========================================================================
13
14 package org.eclipse.jetty.util;
15 import java.io.Serializable;
16 import java.lang.reflect.Array;
17 import java.util.ArrayList;
18 import java.util.Arrays;
19 import java.util.Collection;
20 import java.util.Collections;
21 import java.util.Iterator;
22 import java.util.List;
23 import java.util.ListIterator;
24
25 /* ------------------------------------------------------------ */
26 /** Lazy List creation.
27 * A List helper class that attempts to avoid unnecessary List
28 * creation. If a method needs to create a List to return, but it is
29 * expected that this will either be empty or frequently contain a
30 * single item, then using LazyList will avoid additional object
31 * creations by using {@link Collections#EMPTY_LIST} or
32 * {@link Collections#singletonList(Object)} where possible.
33 * <p>
34 * LazyList works by passing an opaque representation of the list in
35 * and out of all the LazyList methods. This opaque object is either
36 * null for an empty list, an Object for a list with a single entry
37 * or an {@link ArrayList} for a list of items.
38 *
39 * <p><h4>Usage</h4>
40 * <pre>
41 * Object lazylist =null;
42 * while(loopCondition)
43 * {
44 * Object item = getItem();
45 * if (item.isToBeAdded())
46 * lazylist = LazyList.add(lazylist,item);
47 * }
48 * return LazyList.getList(lazylist);
49 * </pre>
50 *
51 * An ArrayList of default size is used as the initial LazyList.
52 *
53 * @see java.util.List
54 */
55 public class LazyList
56 implements Cloneable, Serializable
57 {
58 private static final String[] __EMTPY_STRING_ARRAY = new String[0];
59
60 /* ------------------------------------------------------------ */
61 private LazyList()
62 {}
63
64 /* ------------------------------------------------------------ */
65 /** Add an item to a LazyList
66 * @param list The list to add to or null if none yet created.
67 * @param item The item to add.
68 * @return The lazylist created or added to.
69 */
70 @SuppressWarnings("unchecked")
71 public static Object add(Object list, Object item)
72 {
73 if (list==null)
74 {
75 if (item instanceof List || item==null)
76 {
77 List<Object> l = new ArrayList<Object>();
78 l.add(item);
79 return l;
80 }
81
82 return item;
83 }
84
85 if (list instanceof List)
86 {
87 ((List<Object>)list).add(item);
88 return list;
89 }
90
91 List<Object> l=new ArrayList<Object>();
92 l.add(list);
93 l.add(item);
94 return l;
95 }
96
97 /* ------------------------------------------------------------ */
98 /** Add an item to a LazyList
99 * @param list The list to add to or null if none yet created.
100 * @param index The index to add the item at.
101 * @param item The item to add.
102 * @return The lazylist created or added to.
103 */
104 @SuppressWarnings("unchecked")
105 public static Object add(Object list, int index, Object item)
106 {
107 if (list==null)
108 {
109 if (index>0 || item instanceof List || item==null)
110 {
111 List<Object> l = new ArrayList<Object>();
112 l.add(index,item);
113 return l;
114 }
115 return item;
116 }
117
118 if (list instanceof List)
119 {
120 ((List<Object>)list).add(index,item);
121 return list;
122 }
123
124 List<Object> l=new ArrayList<Object>();
125 l.add(list);
126 l.add(index,item);
127 return l;
128 }
129
130 /* ------------------------------------------------------------ */
131 /** Add the contents of a Collection to a LazyList
132 * @param list The list to add to or null if none yet created.
133 * @param collection The Collection whose contents should be added.
134 * @return The lazylist created or added to.
135 */
136 public static Object addCollection(Object list, Collection<?> collection)
137 {
138 Iterator<?> i=collection.iterator();
139 while(i.hasNext())
140 list=LazyList.add(list,i.next());
141 return list;
142 }
143
144 /* ------------------------------------------------------------ */
145 /** Add the contents of an array to a LazyList
146 * @param list The list to add to or null if none yet created.
147 * @param array The array whose contents should be added.
148 * @return The lazylist created or added to.
149 */
150 public static Object addArray(Object list, Object[] array)
151 {
152 for(int i=0;array!=null && i<array.length;i++)
153 list=LazyList.add(list,array[i]);
154 return list;
155 }
156
157 /* ------------------------------------------------------------ */
158 /** Ensure the capacity of the underlying list.
159 *
160 */
161 public static Object ensureSize(Object list, int initialSize)
162 {
163 if (list==null)
164 return new ArrayList<Object>(initialSize);
165 if (list instanceof ArrayList)
166 {
167 ArrayList<?> ol=(ArrayList<?>)list;
168 if (ol.size()>initialSize)
169 return ol;
170 ArrayList<Object> nl = new ArrayList<Object>(initialSize);
171 nl.addAll(ol);
172 return nl;
173 }
174 List<Object> l= new ArrayList<Object>(initialSize);
175 l.add(list);
176 return l;
177 }
178
179 /* ------------------------------------------------------------ */
180 public static Object remove(Object list, Object o)
181 {
182 if (list==null)
183 return null;
184
185 if (list instanceof List)
186 {
187 List<?> l = (List<?>)list;
188 l.remove(o);
189 if (l.size()==0)
190 return null;
191 return list;
192 }
193
194 if (list.equals(o))
195 return null;
196 return list;
197 }
198
199 /* ------------------------------------------------------------ */
200 public static Object remove(Object list, int i)
201 {
202 if (list==null)
203 return null;
204
205 if (list instanceof List)
206 {
207 List<?> l = (List<?>)list;
208 l.remove(i);
209 if (l.size()==0)
210 return null;
211 return list;
212 }
213
214 if (i==0)
215 return null;
216 return list;
217 }
218
219
220
221 /* ------------------------------------------------------------ */
222 /** Get the real List from a LazyList.
223 *
224 * @param list A LazyList returned from LazyList.add(Object)
225 * @return The List of added items, which may be an EMPTY_LIST
226 * or a SingletonList.
227 */
228 public static<E> List<E> getList(Object list)
229 {
230 return getList(list,false);
231 }
232
233
234 /* ------------------------------------------------------------ */
235 /** Get the real List from a LazyList.
236 *
237 * @param list A LazyList returned from LazyList.add(Object) or null
238 * @param nullForEmpty If true, null is returned instead of an
239 * empty list.
240 * @return The List of added items, which may be null, an EMPTY_LIST
241 * or a SingletonList.
242 */
243 @SuppressWarnings("unchecked")
244 public static<E> List<E> getList(Object list, boolean nullForEmpty)
245 {
246 if (list==null)
247 {
248 if (nullForEmpty)
249 return null;
250 return Collections.emptyList();
251 }
252 if (list instanceof List)
253 return (List<E>)list;
254
255 return (List<E>)Collections.singletonList(list);
256 }
257
258
259 /* ------------------------------------------------------------ */
260 public static String[] toStringArray(Object list)
261 {
262 if (list==null)
263 return __EMTPY_STRING_ARRAY;
264
265 if (list instanceof List)
266 {
267 List<?> l = (List<?>)list;
268 String[] a = new String[l.size()];
269 for (int i=l.size();i-->0;)
270 {
271 Object o=l.get(i);
272 if (o!=null)
273 a[i]=o.toString();
274 }
275 return a;
276 }
277
278 return new String[] {list.toString()};
279 }
280
281 /* ------------------------------------------------------------ */
282 /** Convert a lazylist to an array
283 * @param list The list to convert
284 * @param clazz The class of the array, which may be a primitive type
285 * @return array of the lazylist entries passed in
286 */
287 public static Object toArray(Object list,Class<?> clazz)
288 {
289 if (list==null)
290 return Array.newInstance(clazz,0);
291
292 if (list instanceof List)
293 {
294 List<?> l = (List<?>)list;
295 if (clazz.isPrimitive())
296 {
297 Object a = Array.newInstance(clazz,l.size());
298 for (int i=0;i<l.size();i++)
299 Array.set(a,i,l.get(i));
300 return a;
301 }
302 return l.toArray((Object[])Array.newInstance(clazz,l.size()));
303
304 }
305
306 Object a = Array.newInstance(clazz,1);
307 Array.set(a,0,list);
308 return a;
309 }
310
311 /* ------------------------------------------------------------ */
312 /** The size of a lazy List
313 * @param list A LazyList returned from LazyList.add(Object) or null
314 * @return the size of the list.
315 */
316 public static int size(Object list)
317 {
318 if (list==null)
319 return 0;
320 if (list instanceof List)
321 return ((List<?>)list).size();
322 return 1;
323 }
324
325 /* ------------------------------------------------------------ */
326 /** Get item from the list
327 * @param list A LazyList returned from LazyList.add(Object) or null
328 * @param i int index
329 * @return the item from the list.
330 */
331 @SuppressWarnings("unchecked")
332 public static <E> E get(Object list, int i)
333 {
334 if (list==null)
335 throw new IndexOutOfBoundsException();
336
337 if (list instanceof List)
338 return (E)((List<?>)list).get(i);
339
340 if (i==0)
341 return (E)list;
342
343 throw new IndexOutOfBoundsException();
344 }
345
346 /* ------------------------------------------------------------ */
347 public static boolean contains(Object list,Object item)
348 {
349 if (list==null)
350 return false;
351
352 if (list instanceof List)
353 return ((List<?>)list).contains(item);
354
355 return list.equals(item);
356 }
357
358
359 /* ------------------------------------------------------------ */
360 public static Object clone(Object list)
361 {
362 if (list==null)
363 return null;
364 if (list instanceof List)
365 return new ArrayList<Object>((List<?>)list);
366 return list;
367 }
368
369 /* ------------------------------------------------------------ */
370 public static String toString(Object list)
371 {
372 if (list==null)
373 return "[]";
374 if (list instanceof List)
375 return list.toString();
376 return "["+list+"]";
377 }
378
379 /* ------------------------------------------------------------ */
380 @SuppressWarnings("unchecked")
381 public static<E> Iterator<E> iterator(Object list)
382 {
383 if (list==null)
384 {
385 List<E> empty=Collections.emptyList();
386 return empty.iterator();
387 }
388 if (list instanceof List)
389 {
390 return ((List<E>)list).iterator();
391 }
392 List<E> l=getList(list);
393 return l.iterator();
394 }
395
396 /* ------------------------------------------------------------ */
397 @SuppressWarnings("unchecked")
398 public static<E> ListIterator<E> listIterator(Object list)
399 {
400 if (list==null)
401 {
402 List<E> empty=Collections.emptyList();
403 return empty.listIterator();
404 }
405 if (list instanceof List)
406 return ((List<E>)list).listIterator();
407
408 List<E> l=getList(list);
409 return l.listIterator();
410 }
411
412 /* ------------------------------------------------------------ */
413 /**
414 * @param array Any array of object
415 * @return A new <i>modifiable</i> list initialised with the elements from <code>array</code>.
416 */
417 public static<E> List<E> array2List(E[] array)
418 {
419 if (array==null || array.length==0)
420 return new ArrayList<E>();
421 return new ArrayList<E>(Arrays.asList(array));
422 }
423
424 /* ------------------------------------------------------------ */
425 /** Add element to an array
426 * @param array The array to add to (or null)
427 * @param item The item to add
428 * @param type The type of the array (in case of null array)
429 * @return new array with contents of array plus item
430 */
431 public static<T> T[] addToArray(T[] array, T item, Class<?> type)
432 {
433 if (array==null)
434 {
435 if (type==null && item!=null)
436 type= item.getClass();
437 @SuppressWarnings("unchecked")
438 T[] na = (T[])Array.newInstance(type, 1);
439 na[0]=item;
440 return na;
441 }
442 else
443 {
444 // TODO: Replace with Arrays.copyOf(T[] original, int newLength) from Java 1.6+
445 Class<?> c = array.getClass().getComponentType();
446 @SuppressWarnings("unchecked")
447 T[] na = (T[])Array.newInstance(c, Array.getLength(array)+1);
448 System.arraycopy(array, 0, na, 0, array.length);
449 na[array.length]=item;
450 return na;
451 }
452 }
453
454 /* ------------------------------------------------------------ */
455 public static<T> T[] removeFromArray(T[] array, Object item)
456 {
457 if (item==null || array==null)
458 return array;
459 for (int i=array.length;i-->0;)
460 {
461 if (item.equals(array[i]))
462 {
463 Class<?> c = array==null?item.getClass():array.getClass().getComponentType();
464 @SuppressWarnings("unchecked")
465 T[] na = (T[])Array.newInstance(c, Array.getLength(array)-1);
466 if (i>0)
467 System.arraycopy(array, 0, na, 0, i);
468 if (i+1<array.length)
469 System.arraycopy(array, i+1, na, i, array.length-(i+1));
470 return na;
471 }
472 }
473 return array;
474 }
475
476 }
477