View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *   http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing,
13   * software distributed under the License is distributed on an
14   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   * KIND, either express or implied.  See the License for the
16   * specific language governing permissions and limitations
17   * under the License.
18   */
19  package org.apache.myfaces.trinidad.util;
20  
21  import java.io.ByteArrayOutputStream;
22  import java.io.IOException;
23  import java.io.ObjectOutputStream;
24  import java.io.ObjectStreamException;
25  import java.io.Serializable;
26  import java.lang.reflect.Array;
27  import java.util.AbstractQueue;
28  import java.util.ArrayList;
29  import java.util.Collection;
30  import java.util.Collections;
31  import java.util.ConcurrentModificationException;
32  import java.util.EnumSet;
33  import java.util.HashSet;
34  import java.util.Iterator;
35  import java.util.LinkedList;
36  import java.util.List;
37  import java.util.ListIterator;
38  import java.util.Map;
39  import java.util.NoSuchElementException;
40  import java.util.Queue;
41  import java.util.RandomAccess;
42  import java.util.Set;
43  import java.util.concurrent.atomic.AtomicReference;
44  
45  import org.apache.myfaces.trinidad.component.CompositeIterator;
46  import org.apache.myfaces.trinidad.logging.TrinidadLogger;
47  
48  /**
49   * This class contains Collection utilities.
50   */
51  public final class CollectionUtils
52  {
53    private CollectionUtils()
54    {
55      // no-op
56    }
57    
58    /**
59     * Returns an ArrayList containing all of the elements of the
60     * Iterator
61     * @param iterator Iterator to copy the contexts of
62     * @return an ArrayList containing a copy of the iterator contents
63     */
64    public static <T> ArrayList<T> arrayList(Iterator<T> iterator)
65    {
66      ArrayList<T> arrayList = new ArrayList<T>();
67      
68      while (iterator.hasNext())
69        arrayList.add(iterator.next());
70      
71      return arrayList;
72    }
73  
74    /**
75     * Returns an array containing all of the elements of the
76     * Iterator
77     * @param iterator Iterator to copy the contexts of
78     * @return an array containing a copy of the iterator contents
79     */
80    public static <T> T[] toArray(Iterator<? extends T> iterator, Class<T> type)
81    {
82      if (iterator.hasNext())
83      {
84        Collection arrayList = arrayList(iterator);
85        T[] outArray = (T[])Array.newInstance(type, arrayList.size());
86      
87        return (T[])arrayList.toArray(outArray);
88      }
89      else
90      {
91        // optimize empty iterator case
92        return (T[])Array.newInstance(type, 0);
93      }
94    }
95  
96    /**
97     * Returns an empty, unmodifiable, Serializable Queue.
98     * @return an empty, unmodifiable, Serializable Queue.
99     */
100   public static <T> Queue<T> emptyQueue()
101   {
102     return (Queue<T>)_EMPTY_QUEUE;
103   }
104 
105   /**
106    * Returns an empty, unmodifiable, Iterator.
107    * @return an empty, unmodifiable, Iterator.
108    */
109   public static <T> Iterator<T> emptyIterator()
110   {
111     return (Iterator<T>)_EMPTY_ITERATOR;
112   }
113 
114   /**
115    * Returns an empty, unmodifiable, ListIterator.
116    * @return an empty, unmodifiable, ListIterator.
117    */
118   public static <T> ListIterator<T> emptyListIterator()
119   {
120     return (ListIterator<T>)_EMPTY_LIST_ITERATOR;
121   }
122   
123   /**
124    * Returns a minimal Set containing the elements passed in.  There is no guarantee that the
125    * returned set is mutable or immutable.
126    * @param <T>
127    * @param a The elements to add to the Set
128    * @return A set containing the elements passed in.
129    * @see #asUnmodifiableSet
130    */
131   public static <T> Set<T> asSet(T... a)
132   {
133     return _asSet(a, false);
134   }
135 
136   /**
137    * Returns an unmodifiable Set containing the elements passed in.
138    * @param <T>
139    * @param a The elements to add to the Set
140    * @return A set containing the elements passed in.
141    * @see #asSet
142    */
143   public static <T> Set<T> asUnmodifiableSet(T... a)
144   {
145     return _asSet(a, true);
146   }
147 
148   /**
149    * Returns an unmodifiable versions of the Set of Enums.  If the contents of the set are known
150    * to be unmodifiable by the caller in any way, the set itself will be retured, otherwise an
151    * unmodifiable copy of the Set will be returned.
152    * @param s Set to get the tamper-proof version of
153    * @return An unmodifiable tamper-proof version of the set
154    */
155   public static <E extends Enum<E>> Set<E> unmodifiableCopyOfEnumSet(Set<E> s)
156   {
157     Class<? extends Set> copyClass = s.getClass();
158 
159     if ((_EMPTY_SET == copyClass) || (_SINGLETON_SET == copyClass))
160     {
161       // these classes are already unmodifiable, so just return
162       return s;
163     }
164     else
165     {
166       return Collections.unmodifiableSet(EnumSet.copyOf(s));
167     }
168   }
169 
170   private static <T> Set<T> _asSet(T[] a, boolean makeImmutable)
171   {
172     int count = (a != null) ? a.length : 0;
173 
174     Set<T> outSet;
175     
176     if (count == 0)
177     {
178       outSet = Collections.emptySet();
179     }
180     else
181     {
182       if (count == 1)
183       {
184         outSet = Collections.singleton(a[0]);
185       }
186       else
187       {
188         // make the initial size big enough that we don't have to rehash to fit the array, for
189         // the .75 load factor we pass in
190         int initialSize = (int)Math.ceil(count / .75d);
191         
192         outSet = new HashSet<T>(initialSize, .75f);
193         
194         for (int i = 0; i < count ; i++)
195         {
196           outSet.add(a[i]);
197         } 
198         
199         if (makeImmutable)
200         {
201           outSet = Collections.unmodifiableSet(outSet);
202         }
203       }
204     }
205     
206     return outSet;
207   }
208 
209   /**
210    * Given two disjoint sets, returns a live composition of the two Sets that maintains
211    * the disjoint invariant.  If both Sets are Serializable, the returned
212    * implementation will be Serializable as well.  The returned Set implementation is
213    * not thread safe.
214    * @param primarySet The Set that modifications will be applied to
215    * @param secondarySet The other Set.  Modifications will be applied in response to changes
216    * to the primary set to ensure that the disjoint invariant is maintained
217    * @return The composition of the two disjoint Sets
218    * @throws NullPointerException of primarySet or secondarySet are <code>null</code>
219    * @see #overlappingCompositeSet
220    */
221   public static <T> Set<T> compositeSet(Set<T> primarySet, Set<T> secondarySet)
222   {
223     if ((primarySet instanceof Serializable) && (secondarySet instanceof Serializable))
224       return new SerializableFixedCompositeSet<T>(primarySet, secondarySet);
225     else
226       return new FixedCompositeSet<T>(primarySet, secondarySet);
227   }
228 
229   /**
230    * Given two possibly overlapping sets, returns a live composition of the two Sets.
231    * If both Sets are Serializable, the returned
232    * implementation will be Serializable as well.  The lack of the disjoint invariant makes
233    * operations such as calculating the size of the Set expensive.  If the disjoint invariant
234    * can be guaranteed, <code>compositeSet</code> should be used instead.
235    * The returned Set implementation is
236    * not thread safe.
237    * @param primarySet The Set that modifications will be applied to
238    * @param secondarySet The other Set.  If a removal is performed on the primarySet, it will
239    * also be applied to the secondarySet to ensure that the element is logically removed from the
240    * Set.
241    * @return The composition of the two possibly overallping Sets
242    * @throws NullPointerException of primarySet or secondarySet are <code>null</code>
243    * @see #compositeSet
244    */
245   public static <T> Set<T> overlappingCompositeSet(Set<T> primarySet, Set<T> secondarySet)
246   {
247     if ((primarySet instanceof Serializable) && (secondarySet instanceof Serializable))
248       return new SerializableLenientFixedCompositeSet<T>(primarySet, secondarySet);
249     else
250       return new LenientFixedCompositeSet<T>(primarySet, secondarySet);
251   }
252 
253   /**
254    * Returns a Collection based on the passed in Collection <code>c</code>,
255    * guaranteed to be Serializable. If <code>c</code> is Serializable,
256    * <code>c</code> will be returned, otherwise, <code>c</code> will be
257    * wrapped in a Collection that implements Serializable and upon
258    * Serialization the contents of <code>c</code> will be copied into
259    * the result.
260    * <p>
261    * The results is very similar to creating a new ArrayList with the
262    * contents of <code>c</code>, but no wrapper is created unless necessary
263    * and the actual creation of the Serializable copy is deferred until
264    * Serialization occurs.
265    * @param c The Collection to get a Serializable version of
266    * @return A Serializable version of Collection <code>c</code>
267    * @see #getSerializableList
268    */
269   public static <T> Collection<T> getSerializableCollection(Collection<T> c)
270   {
271     if (c instanceof Serializable)
272       return c;
273     else
274       return new SerializableCollection<T>(c);
275   }
276 
277   /**
278    * Returns a List based on the passed in List <code>l</code>,
279    * guaranteed to be Serializable. List <code>l</code> will be
280    * wrapped in a List that implements Serializable and upon
281    * Serialization the contents of <code>l</code> will be copied into
282    * the result.
283    * <p>
284    * If <code>l</code> implements RandomAccess, any returned List will also
285    * implement RandomAccess.
286    * <p>
287    * The results is very similar to creating a new ArrayList with the
288    * contents of <code>l</code>, but no wrapper is created unless necessary
289    * and the actual creation of the Serializable copy is deferred until
290    * Serialization occurs.
291    * <p>
292    * Code that calls List.subList() and needs the result to be Serializable should always
293    * use <code>newSerializableList</code> rather than <code>getSerializableList</code> because
294    * the <code>java.util.Collections</code> implementations of <code>checkedList</code>,
295    * <code>unmodifiableList</code>, and <code>synchronizedList</code> all lie and always implement
296    * Serializable, regardless of the serializability of their backing List.
297    * @param l The List to get a Serializable version of
298    * @return A Serializable version of List <code>l</code>
299    * @see #getSerializableList
300    * @see #getSerializableCollection
301    */
302   public static <T> List<T> newSerializableList(List<T> l)
303   {
304     if (l instanceof RandomAccess)
305     {
306       return new SerializableRandomAccessList<T>(l);
307     }
308     else
309     {
310       return new SerializableList<T>(l);
311     }
312   }
313 
314   /**
315    * Returns a List based on the passed in List <code>l</code>,
316    * guaranteed to be Serializable. If <code>l</code> is Serializable,
317    * <code>l</code> will be returned, otherwise, <code>l</code> will be
318    * wrapped in a List that implements Serializable and upon
319    * Serialization the contents of <code>l</code> will be copied into
320    * the result.
321    * <p>
322    * If <code>l</code> implements RandomAccess, any returned List will also
323    * implement RandomAccess.
324    * <p>
325    * The results is very similar to creating a new ArrayList with the
326    * contents of <code>l</code>, but no wrapper is created unless necessary
327    * and the actual creation of the Serializable copy is deferred until
328    * Serialization occurs.
329    * <p>
330    * Code that calls List.subList() and needs the result to be Serializable should always
331    * use <code>newSerializableList</code> rather than <code>getSerializableList</code> because
332    * the <code>java.util.Collections</code> implementations of <code>checkedList</code>,
333    * <code>unmodifiableList</code>, and <code>synchronizedList</code> all lie and always implement
334    * Serializable, regardless of the serializability of their backing List.
335    * @param l The List to get a Serializable version of
336    * @return A Serializable version of List <code>l</code>
337    * @see #newSerializableList
338    * @see #getSerializableCollection
339    */
340   public static <T> List<T> getSerializableList(List<T> l)
341   {
342     // because we can't trust the implementations of the checked, unmodifiable, and synchronized
343     // versions, always create a Serializable wrapper if we see one of these classes
344     if ((l instanceof Serializable) &&
345          !_CHECKED_LIST.isInstance(l) &&
346          !_UNMODIFIABLE_LIST.isInstance(l) &&
347          !_SYNCHRONIZED_LIST.isInstance(l))
348       return l;
349     else
350     {
351       return newSerializableList(l);
352     }
353   }
354 
355   /**
356    * Interface for trapping mutations to a Map.
357    * @param <K> the type of the keys of the Map that MapMutationHooks are associated with
358    * @param <V> the type of the values of the Map that MapMutationHooks are associated with
359    * @see #newMutationHookedMap
360    */
361   public interface MapMutationHooks<K, V>
362   {
363     /**
364      * Called when the associated Map of the MapMutationHooks is written to
365      * @param map   Map the write occurred on
366      * @param key   key of entry that has changed
367      * @param value value of entry that has changed
368      */
369     public void writeNotify(Map<K,V> map, K key, V value);
370 
371     /**
372      * Called when an entry is removed from the associated Map of the MapMutationHooks
373      * @param map   Map the removal occurred on
374      * @param key   key of entry that has been removed
375      */
376     public void removeNotify(Map<K,V> map, Object key);
377     
378     /**
379      * Called when all entries are removed from the Map associated with the MapMutationHooks
380      * @param map   Map the clear occurred on
381      */
382     public void clearNotify(Map<K,V> map);
383   }
384 
385   /**
386    * Creates a new Map that informs the MapMutationHooks of any direct mutations.  Mutations to
387    * the underlying Map will not be caught.
388    * If the base map is Serializable, the returned Map will be Serializable
389    * @param <K> type of the keys of the Map
390    * @param <V> type of the values of the Map
391    * @param map Underlying map to trap mutations of
392    * @param hooks MapMutationHooks to inform of mutations to the returned Map
393    * @return a new Map that traps the mutations to the underlying Map
394    * @throws NullPointerException if map or hooks are null
395    */
396   public static <K,V> Map<K, V> newMutationHookedMap(Map<K, V> map, MapMutationHooks<K, V> hooks)
397   {
398     if (map == null)
399       throw new NullPointerException();
400     
401     if (hooks == null)
402       throw new NullPointerException();
403     
404     if (map instanceof Serializable)
405       return new SerializableExternalAccessHookMap<K, V>(map, hooks);
406     else
407       return new ExternalAccessHookMap<K, V>(map, hooks);
408   }
409 
410   /**
411    * Creates a Map that dynamically verifies that all keys and values added to it will
412    * succeed Serialization.  The validations checks not only that the keys and values added
413    * to the Map implement Serializable, but that these instances will actually succeed
414    * Serialization.
415    * <p>
416    * This checking can be defeated by either modifying the backing map directly or by modifying
417    * an object added to the checked Map after adding it.
418    * </p>
419    * @param map Map to wrap for Serialization validation
420    * @return Map where all modifications are checked to ensure that they will succeeed if
421    * serialized
422    */
423   public static <K,V> Map<K, V> getCheckedSerializationMap(Map<K, V> map)
424   {
425     return getCheckedSerializationMap(map, true);
426   }
427 
428   /**
429    * Creates a Map that dynamically verifies that all keys and values added to it will
430    * succeed Serialization.  The validations checks not only that the keys and values added
431    * to the Map implement Serializable, but that these instances will actually succeed
432    * Serialization.
433    * <p>
434    * This checking can be defeated by either modifying the backing map directly or by modifying
435    * an object added to the checked Map after adding it.
436    * </p>
437    * @param map Map to wrap for Serialization validation
438    * @param requireSerializable if <code>true</code>, require that all values in the map implement
439    *                            Serializable.
440    * @return Map where  modifications are checked to ensure that they will succeeed if
441    * serialized
442    */
443   public static <K,V> Map<K, V> getCheckedSerializationMap(
444     Map<K, V> map,
445     boolean   requireSerializable)
446   {
447     if (map instanceof CheckedSerializationMap)
448       return map;
449     else
450       return new CheckedSerializationMap<K,V>(map, requireSerializable);
451   }
452 
453   /**
454    * Given two Collections, return the size of their union
455    * @param firstCollection The first collection.  <code>null</code> is allowed.
456    * @param secondCollection The second collection.  <code>null</code> is allowed.
457    * @return
458    */
459   public static <E> int getUnionSize(
460     Collection<? extends E> firstCollection,
461     Collection<? extends E> secondCollection)
462   {    
463     int firstSize = (firstCollection != null)
464                         ? firstCollection.size()
465                         : 0;
466     
467     int secondSize = (secondCollection != null)
468                         ? secondCollection.size()
469                         : 0;
470     
471     if (firstSize == 0)
472       return secondSize;
473     
474     if (secondSize == 0)
475       return firstSize;
476     
477     // determine the size of the union by iterating over the smaller collection
478     int size;
479     Collection<? extends E> iteratingCollection;
480     Collection<? extends E> baseCollection;
481     
482     if (firstSize >= secondSize)
483     {
484       baseCollection      = firstCollection;
485       iteratingCollection = secondCollection;
486       size                = firstSize;
487     }
488     else
489     {
490       baseCollection      = secondCollection;
491       iteratingCollection = firstCollection;
492       size                = secondSize;
493     }
494     
495     for (E currValue : iteratingCollection)
496     {
497       if (!baseCollection.contains(currValue))
498       {
499         size++;
500       }
501     }
502     
503     return size; 
504   }
505   
506   
507   protected static <T> T[] copyOf(T[] original, int newLength)
508   {
509     return (T[]) copyOf(original, newLength, original.getClass());
510   }
511 
512   protected static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType)
513   {
514     T[] copy = ((Object)newType == (Object)Object[].class)
515         ? (T[]) new Object[newLength]
516         : (T[]) Array.newInstance(newType.getComponentType(), newLength);
517     System.arraycopy(original, 0, copy, 0,
518                      Math.min(original.length, newLength));
519     return copy;
520   }
521 
522   protected abstract static class DelegatingCollection<E> implements Collection<E>
523   {
524     protected abstract Collection<E> getDelegate();
525 
526     public int size()
527     {
528       return getDelegate().size();
529     }
530 
531     public boolean isEmpty()
532     {
533       return getDelegate().isEmpty();
534     }
535 
536     public boolean contains(Object o)
537     {
538       return getDelegate().contains(o);
539     }
540 
541     public Iterator<E> iterator()
542     {
543       return getDelegate().iterator();
544     }
545 
546     public Object[] toArray()
547     {
548       return getDelegate().toArray();
549     }
550 
551     public <T> T[] toArray(T[] a)
552     {
553       return getDelegate().toArray(a);
554     }
555 
556     public boolean add(E e)
557     {
558       return getDelegate().add(e);
559     }
560 
561     public boolean remove(Object o)
562     {
563       return getDelegate().remove(0);
564     }
565 
566     public boolean containsAll(Collection<?> c)
567     {
568       return getDelegate().containsAll(c);
569     }
570 
571     public boolean addAll(Collection<? extends E> c)
572     {
573       return getDelegate().addAll(c);
574     }
575 
576     public boolean removeAll(Collection<?> c)
577     {
578       return getDelegate().removeAll(c);
579     }
580 
581     public boolean retainAll(Collection<?> c)
582     {
583       return getDelegate().retainAll(c);
584     }
585 
586     public void clear()
587     {
588       getDelegate().clear();
589     }
590     
591     /**
592      * All Collections
593      * @param o
594      * @return
595      */
596     public boolean equals(Object o)
597     {
598       return (o == this) || getDelegate().equals(o);
599     }
600 
601     public int hashCode()
602     {
603       return getDelegate().hashCode();
604     }
605 
606     public String toString()
607     {
608       return getDelegate().toString();
609     }
610   }
611 
612   /**
613    * Note: Requires contents to be disjoint!
614    * @param <E>
615    */
616   protected abstract static class CompositeCollection<E> implements Collection<E>
617   {
618     protected abstract Collection<E> getPrimaryDelegate();
619     protected abstract Collection<E> getSecondaryDelegate();
620 
621     public int size()
622     {
623       return getPrimaryDelegate().size() + getSecondaryDelegate().size();
624     }
625 
626     public boolean isEmpty()
627     {
628       return getPrimaryDelegate().isEmpty() && getSecondaryDelegate().isEmpty();
629     }
630 
631     public boolean contains(Object o)
632     {
633       return getPrimaryDelegate().contains(o) || getSecondaryDelegate().contains(o);
634     }
635 
636     public Iterator<E> iterator()
637     {
638       return new CompositeIterator<E>(getPrimaryDelegate().iterator(),
639                                       getSecondaryDelegate().iterator());
640     }
641 
642     public Object[] toArray()
643     {
644       int size = size();
645       
646       Object[] out = new Object[size];
647       
648       int i = 0;
649       for (Object currObject : this)
650       {
651         out[i] = currObject;
652         
653         i++;
654         
655         if (i == size)
656           break;
657       }
658       
659       return out;
660     }
661 
662     public <T> T[] toArray(T[] outArray)
663     {
664       int collectionSize = size();
665       int arraySize = outArray.length;
666       
667       // size isn't big enough, so need a new array
668       if (collectionSize > arraySize)
669       {
670         outArray = (T[])Array.newInstance(outArray.getClass().getComponentType(),
671                                           collectionSize);
672       }
673 
674       Iterator<E> iterator = this.iterator();
675       
676       for (int i = 0; i < collectionSize; i++)
677       {
678         if (!iterator.hasNext())
679           break;
680         
681         outArray[i] = (T)iterator.next();
682       }
683       
684       return outArray;
685     }
686 
687     public boolean add(E e)
688     {
689       boolean modified = getPrimaryDelegate().add(e);
690       
691       if (modified)
692       {
693         // maintain disjointness.  If the secondary delegate already contained this element
694         // then we didn't really change
695         modified = !getSecondaryDelegate().remove(e);
696       }
697       
698       return modified;
699     }
700 
701     public boolean remove(Object o)
702     {
703       boolean removed = getPrimaryDelegate().remove(0);
704       
705       if (!removed)
706         removed = getSecondaryDelegate().remove(0);
707       
708       return removed;
709     }
710 
711     public boolean containsAll(Collection<?> c)
712     {
713       // find all of the items in both the collection and the primary delegate
714       
715       Set<Object> intersection = new HashSet<Object>(getPrimaryDelegate());
716       intersection.retainAll(c);
717             
718       if (intersection.size() == c.size())
719       {
720         // the primary delegate contained all of the items, so we're done
721         return true;
722       }
723       else
724       {
725         // compute the set of items we still haven't match in order to check against the
726         // secondary delegate
727         Set<Object> remainder = new HashSet<Object>(c);
728         remainder.removeAll(intersection);
729         
730         return getSecondaryDelegate().containsAll(remainder);
731       }
732     }
733 
734     public boolean addAll(Collection<? extends E> c)
735     {
736       // determine the result ahead of time
737       boolean changed = !containsAll(c);
738       
739       // make sure that the collections maintain disjointness
740       getSecondaryDelegate().removeAll(c);
741       getPrimaryDelegate().addAll(c);
742       
743       return changed;
744     }
745 
746     public boolean removeAll(Collection<?> c)
747     {
748       return getPrimaryDelegate().removeAll(c) || getSecondaryDelegate().removeAll(c);
749     }
750 
751     public boolean retainAll(Collection<?> c)
752     {
753       return getPrimaryDelegate().retainAll(c) || getSecondaryDelegate().retainAll(c);
754     }
755 
756     public void clear()
757     {
758       getPrimaryDelegate().clear();
759       getSecondaryDelegate().clear();
760     }
761     
762     @Override
763     public String toString()
764     {
765       return super.toString() + 
766              "[primary:" + 
767              getPrimaryDelegate() +
768              ", secondary:" +
769              getSecondaryDelegate() +
770              "]";
771     }
772   }
773   
774   /**
775    * Iterator that guarantees that removals are also performed on the non-disjoint Collection
776    * @param <E>
777    */
778   private static class RemovingIterator<E> implements Iterator<E>
779   {    
780     public RemovingIterator(Iterator<E> baseIterator, Collection<E> disjointCollection)
781     {
782       _baseIterator = baseIterator;
783       _disjointCollection = disjointCollection;
784     }
785 
786     public boolean hasNext()
787     {
788       return _baseIterator.hasNext();
789     }
790     
791     public E next()
792     {
793       _last = _baseIterator.next();
794       
795       return _last;
796     }
797  
798     public void remove()
799     {
800       _baseIterator.remove();
801       
802       // ensure that the removed element is also removed from the disjoint collection
803       // so that removing the element from the primary collection doesn't accidentally
804       // expose it in the secondary collection
805       _disjointCollection.remove(_last);
806       _last = null;
807     }
808     
809     private final Iterator<E> _baseIterator;
810     private final Collection<E> _disjointCollection;
811     private E _last;
812   }
813   
814   
815   /**
816    * Iterator returning only the elements in the disjoint Collection that aren't in the
817    * checked Collection
818    */
819   private static class DisjointIterator<E> implements Iterator<E>
820   {    
821     public DisjointIterator(Collection<E> checkedCollection, Collection<E> disjointCollection)
822     {
823       _checkedCollection = checkedCollection;
824       _disjointIterator = disjointCollection.iterator();
825     }
826 
827     public boolean hasNext()
828     {
829       if (_nextHolder == null)
830       {
831         do
832         {
833           if (_disjointIterator.hasNext())
834           {
835             E next = _disjointIterator.next();
836             
837             if (!_checkedCollection.contains(next))
838             {
839               // found it
840               _nextHolder = new AtomicReference<E>(next);
841               break;
842             }
843           }
844           else
845           {
846             return false;
847           }
848         }
849         while (true);
850       }
851       
852       return true;
853     }
854 
855     public E next()
856     {
857       // check if we have another value and if we do, populate _nextHolder
858       if (hasNext())
859       {
860         E value = _nextHolder.get();
861         
862         // clear so we know that we need to recalculate next time
863         _nextHolder = null;
864         return value;
865       }
866       else
867       {
868         throw new NoSuchElementException();
869       }
870     }
871 
872     public void remove()
873     {
874       // make sure that have have called next() before removing.  In the case where
875       // next() has never been called, the _disjointIterator should blow up on its own.
876       // one problem we have is that this code won't work correctly if the call order
877       // is next(), hasNext(), remove(), since hasNext() calls next() as a side-effect.
878       // In this case we will throw an IllegalStateException(), which is probably
879       // preferable to removing the wrong element, which is what would happen if we
880       // didn't have the (_nextHolder == null) check.
881       if (_nextHolder == null)
882         _disjointIterator.remove();
883       else
884         throw new IllegalStateException();
885     }
886 
887     private final Collection<E> _checkedCollection;
888     private final Iterator<E> _disjointIterator;
889     private AtomicReference<E> _nextHolder;
890   }
891   
892   /**
893    * Note: Requires contents to be disjoint!
894    * @param <E>
895    */
896   protected abstract static class CompositeSet<E> extends CompositeCollection<E> implements Set<E>
897   {
898     @Override
899     protected abstract Set<E> getPrimaryDelegate();
900     
901     @Override
902     protected abstract Set<E> getSecondaryDelegate();
903 
904     /**
905      * Implement Set-defined equals behavior 
906      */
907     @Override
908     public boolean equals(Object o)
909     {
910       if (o == this)
911         return true;
912       else if (!(o instanceof Set))
913         return false;
914       else
915       {
916         Collection other = (Collection) o;
917 
918         if (other.size() != size())
919         {
920           return false;
921         }
922         else
923         {
924           // since the sizes are the same, if we contain all of the other collection's
925           // elements, we are identical
926           try
927           {
928             return containsAll(other);
929           }
930           catch(NullPointerException npe)
931           {
932             // optional NullPointerException that containsAll is allowed to throw
933             return false;
934           }
935           catch(ClassCastException npe)
936           {
937             // optional ClassCastException that containsAll is allowed to throw
938             return false;
939           }
940         }
941       }
942     }
943 
944     /**
945      * Implement Set-defined equals behavior 
946      */
947     @Override
948     public int hashCode()
949     {
950       // Set defines hashCode() as additive based on the contents
951       return getPrimaryDelegate().hashCode() + getSecondaryDelegate().hashCode();
952     }
953   }
954   
955   /**
956    * Concrete Composite Set that takes the two sets to compose
957    */
958   private static class FixedCompositeSet<E> extends CompositeSet<E>
959   {
960     FixedCompositeSet(Set<E> primarySet, Set<E> secondarySet)
961     {
962       if (primarySet == null)
963         throw new NullPointerException();
964 
965       if (secondarySet == null)
966         throw new NullPointerException();
967       
968       assert Collections.disjoint(primarySet, secondarySet) : "Composed Sets not disjoint";
969       
970       _primarySet   = primarySet;
971       _secondarySet = secondarySet;
972     }
973 
974     @Override
975     protected Set<E> getPrimaryDelegate()
976     {
977       return _primarySet;
978     }
979     
980     @Override
981     protected Set<E> getSecondaryDelegate()
982     {
983       return _secondarySet;
984     }
985     
986     private final Set<E> _primarySet;
987     private final Set<E> _secondarySet;
988   }
989 
990   /**
991    * Serializable version of FixedCompositeSet
992    * @param <E>
993    */
994   private static final class SerializableFixedCompositeSet<E> extends FixedCompositeSet<E>
995                                                               implements Serializable
996   {
997     SerializableFixedCompositeSet(Set<E> primarySet, Set<E> secondarySet)
998     {
999       super(primarySet, secondarySet);
1000     }
1001 
1002     private static final long serialVersionUID = 0L;
1003   }
1004 
1005   /**
1006    * Live composite set where both sets are allowed to be disjoint.
1007    * @param <E>
1008    */
1009   protected abstract static class LenientCompositeSet<E> extends CompositeSet<E>
1010   {
1011     @Override
1012     public int size()
1013     {
1014       return CollectionUtils.getUnionSize(getPrimaryDelegate(), getSecondaryDelegate());
1015     }
1016 
1017     @Override
1018     public Iterator<E> iterator()
1019     {
1020       // create a CompositeIterator of the primary and secondary Sets such that all of the
1021       // elements of the bigger Set are returned directly and the smaller Collection returns
1022       // only the elements not present in the larger Collection
1023       Set<E> primaryDelegate = getPrimaryDelegate();
1024       Set<E> secondaryDelegate = getSecondaryDelegate();
1025       
1026       if (primaryDelegate.size() >= secondaryDelegate.size())
1027       {
1028         return new CompositeIterator<E>(
1029                         new RemovingIterator<E>(primaryDelegate.iterator(), secondaryDelegate),
1030                         new DisjointIterator<E>(primaryDelegate, secondaryDelegate));
1031       }
1032       else
1033       {
1034         return new CompositeIterator<E>(
1035                         new RemovingIterator<E>(secondaryDelegate.iterator(), primaryDelegate),
1036                         new DisjointIterator<E>(secondaryDelegate, primaryDelegate));
1037       }
1038     }
1039 
1040     @Override
1041     public boolean add(E e)
1042     {
1043       boolean modified = getPrimaryDelegate().add(e);
1044       
1045       if (modified)
1046       {
1047         // If the secondary delegate already contained this element
1048         // then we didn't really change.  Since we don't need to maintain the disjoint
1049         // property, we don't have to remove the item from the secondaryDelegate.
1050         modified = !getSecondaryDelegate().contains(e);
1051       }
1052       
1053       return modified;
1054     }
1055 
1056     @Override
1057     public boolean remove(Object o)
1058     {
1059       // override to remove from both Sets to ensure that removing from the first
1060       // doesn't cause the same value to no longer be eclipsed in the second
1061       boolean removed = getPrimaryDelegate().remove(0);
1062       removed |= getSecondaryDelegate().remove(0);
1063       
1064       return removed;
1065     }
1066 
1067     @Override
1068     public boolean addAll(Collection<? extends E> c)
1069     {
1070       // determine the result ahead of time
1071       boolean changed = !containsAll(c);
1072       
1073       // We don't need to remove the items from the secondaryDelegate because we don't
1074       // need to maintain disjointness
1075       getPrimaryDelegate().addAll(c);
1076       
1077       return changed;
1078     }
1079 
1080     /**
1081      * Implement Set-defined equals behavior 
1082      */
1083     @Override
1084     public int hashCode()
1085     {
1086       // Set defines hashCode() as additive based on the contents
1087       
1088       // create a CompositeIterator of the primary and secondary Sets such that all of the
1089       // elements of the bigger Set are returned directly and the smaller Collection returns
1090       // only the elements not present in the larger Collection
1091       Set<E> primaryDelegate = getPrimaryDelegate();
1092       Set<E> secondaryDelegate = getSecondaryDelegate();
1093       
1094       int hashCode;
1095       Iterator<E> disjointElements;
1096       
1097       if (primaryDelegate.size() >= secondaryDelegate.size())
1098       {
1099         hashCode = primaryDelegate.hashCode();
1100         disjointElements = new DisjointIterator<E>(primaryDelegate, secondaryDelegate);
1101       }
1102       else
1103       {
1104         hashCode = secondaryDelegate.hashCode();
1105         disjointElements = new DisjointIterator<E>(secondaryDelegate, primaryDelegate);
1106       }
1107       
1108       while (disjointElements.hasNext())
1109       {
1110         E currElement = disjointElements.next();
1111         
1112         if (currElement != null)
1113           hashCode += currElement.hashCode();
1114       }
1115       
1116       return hashCode;
1117     }
1118   }
1119   
1120   /**
1121    * Concrete Composite Set that takes the two sets to compose
1122    */
1123   private static class LenientFixedCompositeSet<E> extends LenientCompositeSet<E>
1124   {
1125     LenientFixedCompositeSet(Set<E> primarySet, Set<E> secondarySet)
1126     {
1127       if (primarySet == null)
1128         throw new NullPointerException();
1129 
1130       if (secondarySet == null)
1131         throw new NullPointerException();
1132             
1133       _primarySet   = primarySet;
1134       _secondarySet = secondarySet;
1135     }
1136 
1137     @Override
1138     protected Set<E> getPrimaryDelegate()
1139     {
1140       return _primarySet;
1141     }
1142     
1143     @Override
1144     protected Set<E> getSecondaryDelegate()
1145     {
1146       return _secondarySet;
1147     }
1148     
1149     private final Set<E> _primarySet;
1150     private final Set<E> _secondarySet;
1151   }
1152 
1153   /**
1154    * Serializable version of LenientFixedCompositeSet
1155    * @param <E>
1156    */
1157   private static final class SerializableLenientFixedCompositeSet<E> extends
1158      LenientFixedCompositeSet<E> implements Serializable
1159   {
1160     SerializableLenientFixedCompositeSet(Set<E> primarySet, Set<E> secondarySet)
1161     {
1162       super(primarySet, secondarySet);
1163     }
1164 
1165     private static final long serialVersionUID = 0L;
1166   }
1167 
1168 
1169   private static class SerializableCollection<E> extends DelegatingCollection<E>
1170                                                  implements Serializable
1171   {
1172     SerializableCollection(Collection<E> delegate)
1173     {
1174       // we don't check that the delegate is Serializable because of the Collections
1175       // classes that lie about Serializability
1176       if (delegate == null)
1177         throw new NullPointerException();
1178            
1179       _delegate = delegate;
1180     }
1181 
1182     protected Collection<E> getDelegate()
1183     {
1184       return _delegate;
1185     }
1186     
1187     protected Object writeReplace() throws ObjectStreamException
1188     {
1189       // copy delegate into a Serializable ArrayList on Serialization
1190       return new ArrayList(_delegate);
1191     }
1192 
1193     private static final long serialVersionUID = 0L;
1194 
1195     private final transient Collection<E> _delegate;
1196   }
1197 
1198 
1199   private static class SerializableList<E> extends SerializableCollection<E> implements List<E>
1200   {
1201     SerializableList(List<E> delegate)
1202     {
1203       super(delegate);
1204       _delegate = delegate;
1205     }
1206     
1207     public void add(int index, E element)
1208     {
1209       _delegate.add(index, element);
1210     }
1211 
1212     public E remove(int index)
1213     {
1214       return _delegate.remove(index);
1215     }
1216 
1217     public boolean addAll(int index, Collection<? extends E> c)
1218     {
1219       return _delegate.addAll(index, c);
1220     }
1221 
1222     public E get(int index)
1223     {
1224       return _delegate.get(index);
1225     }
1226 
1227     public E set(int index, E element)
1228     {
1229       return _delegate.set(index, element);
1230     }
1231 
1232     public int indexOf(Object o)
1233     {
1234       return _delegate.indexOf(o);
1235     }
1236 
1237     public int lastIndexOf(Object o)
1238     {
1239       return _delegate.lastIndexOf(o);
1240     }
1241 
1242     public ListIterator<E> listIterator()
1243     {
1244       return _delegate.listIterator();
1245     }
1246 
1247     public ListIterator<E> listIterator(int index)
1248     {
1249       return _delegate.listIterator(index);
1250     }
1251 
1252     public List<E> subList(int fromIndex, int toIndex)
1253     {
1254       return CollectionUtils.getSerializableList(_delegate.subList(fromIndex, toIndex));
1255     }
1256  
1257     private static final long serialVersionUID = 0L;
1258     
1259     private final transient List<E> _delegate;
1260   }
1261 
1262   private static class SerializableRandomAccessList<E> extends SerializableList<E> implements RandomAccess
1263   {
1264     SerializableRandomAccessList(List<E> delegate)
1265     {
1266       super(delegate);
1267     }
1268 
1269     private static final long serialVersionUID = 0L;
1270   }
1271 
1272   protected static abstract class DelegatingMap<K,V> implements Map<K,V>
1273   {
1274     protected abstract Map<K,V> getDelegate();
1275 
1276     public int size()
1277     {
1278       return getDelegate().size();
1279     }
1280 
1281     public boolean isEmpty()
1282     {
1283       return getDelegate().isEmpty();
1284     }
1285 
1286     public boolean containsKey(Object key)
1287     {
1288       return getDelegate().containsKey(key);
1289     }
1290 
1291     public boolean containsValue(Object value)
1292     {
1293       return getDelegate().containsValue(value);
1294     }
1295 
1296     public V get(Object key)
1297     {
1298       return getDelegate().get(key);
1299     }
1300 
1301     // Modification Operations
1302 
1303     public V put(K key, V value)
1304     {
1305       return getDelegate().put(key, value);
1306     }
1307 
1308     public V remove(Object key)
1309     {
1310       return getDelegate().remove(key);
1311     }
1312 
1313     // Bulk Operations
1314 
1315     public void putAll(Map<? extends K, ? extends V> m)
1316     {
1317       getDelegate().putAll(m);
1318     }
1319 
1320     public void clear()
1321     {
1322       getDelegate().clear();
1323     }
1324 
1325     // Views
1326     
1327     public Set<K> keySet()
1328     {
1329       return getDelegate().keySet();
1330     }
1331 
1332     public Collection<V> values()
1333     {
1334       return getDelegate().values();
1335     }
1336 
1337     public Set<Map.Entry<K, V>> entrySet()
1338     {
1339       return getDelegate().entrySet();      
1340     }
1341 
1342     // Comparison and hashing
1343 
1344     public boolean equals(Object o)
1345     {
1346       return getDelegate().equals(o);
1347     }
1348 
1349     public int hashCode()
1350     {
1351       return getDelegate().hashCode();
1352     }
1353   }
1354   
1355   protected static abstract class DelegatingEntry<K,V> implements Map.Entry<K,V>
1356   {
1357     protected abstract Map.Entry<K,V> getDelegate();
1358                                 
1359     public K getKey()
1360     {
1361       return getDelegate().getKey();
1362     }
1363 
1364     public V getValue()
1365     {
1366       return getDelegate().getValue();
1367     }
1368 
1369     public V setValue(V value)
1370     {
1371       return getDelegate().setValue(value);
1372     }
1373 
1374     public boolean equals(Object o)
1375     {
1376       return getDelegate().equals(o);
1377     }
1378 
1379     public int hashCode()
1380     {
1381       return getDelegate().hashCode();
1382     }
1383   }
1384   
1385   protected static abstract class AccessHookMap<K,V> extends DelegatingMap<K, V>
1386   {     
1387     protected abstract void writeNotify(K key, V value);
1388 
1389     protected abstract void removeNotify(Object key);
1390 
1391     protected abstract void clearNotify();
1392 
1393     @Override
1394     public V put(K key, V value)
1395     {
1396       writeNotify(key, value);
1397       
1398       return super.put(key, value);
1399     }
1400 
1401     @Override
1402     public V remove(Object key)
1403     {
1404       removeNotify(key);
1405       
1406       return super.remove(key);
1407     }
1408 
1409     @Override
1410     public void putAll(Map<? extends K, ? extends V> m)
1411     {      
1412       for (Map.Entry<? extends K, ? extends V> entry : m.entrySet())
1413       {        
1414         K key   = entry.getKey();
1415         V value = entry.getValue();
1416         
1417         writeNotify(key, value);
1418         super.put(key, value);
1419       }
1420     }
1421     
1422     @Override
1423     public void clear()
1424     {
1425       clearNotify();
1426       super.clear();
1427     }
1428  
1429     public Set<Map.Entry<K, V>> entrySet()
1430     {
1431       return new MutationHookedEntrySet<K, V>(this);      
1432     }
1433 
1434 
1435     // Entry Set returns CheckedSerializationEntry Objects
1436     private static class MutationHookedEntrySet<K, V> extends DelegatingCollection<Entry<K,V>>
1437                                          implements Set<Entry<K, V>>
1438     {
1439       private MutationHookedEntrySet(AccessHookMap<K, V> accessHookMap)
1440       {
1441         if (accessHookMap == null)
1442           throw new NullPointerException();
1443         
1444         _accessHookMap = accessHookMap;
1445         _delegate = accessHookMap.getDelegate().entrySet();
1446       }
1447 
1448       protected Set<Entry<K, V>> getDelegate()
1449       {
1450         return _delegate;
1451       }
1452 
1453       public Iterator<Entry<K,V>> iterator()
1454       {
1455         return new MutationHookedEntrySetIterator<K, V>(super.iterator(), _accessHookMap);
1456       }
1457       
1458       public Object[] toArray()
1459       {
1460         Object[] delegateEntries = super.toArray();
1461 
1462         int entryCount = delegateEntries.length;
1463         
1464         // make sure that the array allows generic Entry objects.  If so, use the source array
1465         // as the destination array, otherwise create a new destination array for our entries
1466         Object[] entries = 
1467                        (delegateEntries.getClass().getComponentType().isAssignableFrom(Entry.class))
1468                          ? delegateEntries
1469                          : new Entry[entryCount];
1470                         
1471         for (int i = 0; i < entryCount; i++)
1472           entries[i] = new MutationHookedEntry((Entry<K,V>)delegateEntries[i], _accessHookMap);
1473         
1474         return entries;
1475       }
1476 
1477       public <T> T[] toArray(T[] a)
1478       {
1479         int inputSize = a.length;
1480         
1481         // compute the output type array so that the delegate creates an array of the correct
1482         // type.  We always truncate the input array's size to 0 so that the delegate doesn't
1483         // attempt to copy any of its contents into the output array
1484         T[] outTypeArray = (inputSize == 0)
1485                              ? a
1486                              : CollectionUtils.copyOf(a, 0);
1487         
1488         Object[] delegateEntries = super.toArray(outTypeArray);
1489         
1490         // now proxy the contents
1491         int entryCount = delegateEntries.length;
1492         
1493         for (int i = 0; i < entryCount; i++)
1494           delegateEntries[i] = new MutationHookedEntry<K, V>((Entry<K,V>)delegateEntries[i],
1495                                                              _accessHookMap);
1496         
1497         // now figure out whether we have to copy the entries into the passed in array or not
1498         if (entryCount > inputSize)
1499           return (T[])delegateEntries;
1500         
1501         // they fit so we need to copy the values into the input array
1502         System.arraycopy(delegateEntries, 0, a, 0, entryCount);
1503        
1504         // see if we have room for the wacky null terminator
1505         if (inputSize > entryCount)
1506           a[entryCount] = null;
1507         
1508         return a;
1509       }
1510 
1511       // Iterator for MutationHookedEntrySet that returns MutationHookedEntry
1512       private static final class MutationHookedEntrySetIterator<K, V> implements Iterator<Entry<K,V>>
1513       {
1514         private MutationHookedEntrySetIterator(Iterator<Entry<K, V>> delegate,
1515                                                AccessHookMap<K, V>   accessHookMap)
1516         {
1517           _delegate      = delegate;
1518           _accessHookMap = accessHookMap;
1519         }
1520 
1521         public boolean hasNext()
1522         {
1523           return _delegate.hasNext();
1524         }
1525 
1526         public Map.Entry<K,V> next()
1527         {
1528           Map.Entry<K,V> nextEntry = _delegate.next();
1529           
1530           // update the current key
1531           _currKey = nextEntry.getKey();
1532           
1533           // return wrapped entry
1534           return new MutationHookedEntry<K,V>(nextEntry, _accessHookMap);
1535         }
1536 
1537         public void remove()
1538         {
1539           if (_currKey == _NO_KEY)
1540             throw new IllegalStateException();
1541           
1542           // notify listener of removal
1543           _accessHookMap.removeNotify(_currKey);
1544           
1545           // let the delegate remove the entry
1546           _delegate.remove();
1547           
1548           // no more entry to remove until next call to next()
1549           _currKey = _NO_KEY;
1550         }
1551  
1552         private static final Object _NO_KEY = new Object();
1553        
1554         // either _NO_KEY or the current key.  We use volatile to ensure safe publication for
1555         // thread use
1556         private volatile Object _currKey = _NO_KEY;
1557         
1558         private final Iterator<Entry<K, V>> _delegate;
1559         private final AccessHookMap<K, V> _accessHookMap;
1560       }
1561 
1562       // Entry implementation that hooks calls to setValue
1563       private static class MutationHookedEntry<K, V> extends DelegatingEntry<K, V>
1564       {
1565         private MutationHookedEntry(Entry<K, V> delegate, AccessHookMap<K, V> accessHookMap)
1566         {
1567           if (delegate == null)
1568             throw new NullPointerException();
1569           
1570           _delegate = delegate;
1571           _accessHookMap = accessHookMap;
1572         }
1573         
1574         protected Entry<K, V> getDelegate()
1575         {
1576           return _delegate;
1577         }
1578         
1579         public V setValue(V value)
1580         {
1581           _accessHookMap.writeNotify(getKey(), value);
1582           return super.setValue(value);
1583         }
1584       
1585         private final Entry<K, V> _delegate;
1586         private final AccessHookMap<K, V> _accessHookMap;
1587      }
1588 
1589       private final AccessHookMap<K, V> _accessHookMap;
1590       private final Set<Entry<K, V>> _delegate;
1591     }
1592   }
1593 
1594   protected static class ExternalAccessHookMap<K,V> extends AccessHookMap<K, V>
1595   {
1596     protected ExternalAccessHookMap(Map<K, V> delegate, MapMutationHooks<K, V> mutationHooks)
1597     {
1598       if (delegate == null)
1599         throw new NullPointerException("delegate is null");
1600       
1601       if (mutationHooks == null)
1602         throw new NullPointerException("accessHooks is null");
1603       
1604       _delegate = delegate;
1605       _mutationHooks = mutationHooks;
1606     }
1607     
1608     protected final Map<K, V> getDelegate()
1609     {
1610       return _delegate;
1611     }
1612     
1613     protected final void writeNotify(K key, V value)
1614     {
1615       _mutationHooks.writeNotify(this, key, value);      
1616     }
1617   
1618     protected final void removeNotify(Object key)
1619     {
1620       _mutationHooks.removeNotify(this, key);      
1621     }
1622 
1623     protected final void clearNotify()
1624     {
1625       _mutationHooks.clearNotify(this);      
1626     }
1627 
1628     private static final long serialVersionUID = 1L;
1629 
1630     private final Map<K, V> _delegate;
1631     private final MapMutationHooks<K, V> _mutationHooks;
1632   }
1633 
1634   private static final class SerializableExternalAccessHookMap<K, V> 
1635                                                      extends ExternalAccessHookMap<K, V>
1636                                                      implements Serializable
1637   {
1638     private SerializableExternalAccessHookMap(
1639       Map<K, V> delegate,
1640       MapMutationHooks<K, V> mutationHooks)
1641     {
1642       super(delegate, mutationHooks); 
1643 
1644       if (!(delegate instanceof Serializable))
1645         throw new IllegalArgumentException("Delegate must be Serializable");
1646   
1647       if (!(mutationHooks instanceof Serializable))
1648         throw new IllegalArgumentException("mutation hooka must be Serializable");
1649     }
1650     
1651     private static final long serialVersionUID = 1L;
1652   }
1653 
1654 
1655   // Map that validates that the keys and values added to the map are Serializable
1656   private final static class CheckedSerializationMap<K, V> extends AccessHookMap<K,V>
1657                                                            implements Serializable
1658   {
1659     /**
1660      * @param requireSerializable if <code>true</code>, require that all values in the map implement
1661      *                            Serializable.
1662      * @param delegate we do not check whether the delegate itself is Serializable. We just check its contents.
1663      */
1664     public CheckedSerializationMap(
1665       Map<K, V> delegate,
1666       boolean   requireSerializable)
1667     {
1668       if (delegate == null)
1669         throw new NullPointerException();
1670 
1671       _delegate = delegate;
1672       _requireSerializable = requireSerializable;
1673     }
1674 
1675     protected Map<K, V> getDelegate()
1676     {
1677       return _delegate;
1678     }
1679 
1680     protected void writeNotify(K key, V value)
1681     {
1682       // don't bother checking common case of String
1683       if (!(key instanceof String))
1684       {
1685         if (key instanceof Serializable)
1686         {
1687           // verify that the contents of the key are in fact Serializable
1688           try
1689           {
1690             new ObjectOutputStream(new ByteArrayOutputStream()).writeObject(key);
1691           }
1692           catch (IOException e)
1693           {          
1694             throw new IllegalArgumentException(_LOG.getMessage("FAILED_SERIALIZATION_PROPERTY_KEY",
1695                                                        new Object[]{key, this}),
1696                                                        e);
1697           }
1698         }
1699         else
1700         {
1701           if (_requireSerializable)
1702           {
1703             throw new ClassCastException(_LOG.getMessage("UNSERIALIZABLE_PROPERTY_KEY",
1704                                                          new Object[]{key, this}));
1705           }
1706         }
1707       }
1708       
1709       if (value instanceof Serializable)
1710       {
1711         // verify that the contents of the value are in fact Serializable
1712         try
1713         {
1714           new ObjectOutputStream(new ByteArrayOutputStream()).writeObject(value);
1715         }
1716         catch (IOException e)
1717         {          
1718           throw new IllegalArgumentException(_LOG.getMessage("FAILED_SERIALIZATION_PROPERTY_VALUE",
1719                                                      new Object[]{value, key, this}),
1720                                                      e);
1721         }
1722       }
1723       else if (value != null)
1724       {
1725         if (_requireSerializable)
1726         {
1727           throw new ClassCastException(_LOG.getMessage("UNSERIALIZABLE_PROPERTY_VALUE",
1728                                                        new Object[]{value, key, this}));
1729         }
1730       }
1731     }
1732 
1733     protected void removeNotify(Object key)
1734     {
1735       // do nothing
1736     }
1737     
1738     protected void clearNotify()
1739     {
1740       // do nothing
1741     }
1742 
1743     @Override
1744     public void putAll(Map<? extends K, ? extends V> m)
1745     {
1746       
1747       Object[] keys = m.keySet().toArray();
1748       Object[] values = m.values().toArray();
1749       
1750       int keyCount = keys.length;
1751       
1752       // in case an entry was added or removed between to tow toArray calls above
1753       if (keyCount != values.length)
1754         throw new ConcurrentModificationException();
1755       
1756       // atomically check for serializability before adding
1757       for (int k = 0; k < keyCount; k++)
1758       {
1759         writeNotify((K)keys[k], (V)values[k]);        
1760       }
1761 
1762       // add the contents we checked rather that calling super.putAll(m), in case
1763       // the map changed after we checked its contents above
1764       Map<K, V> delegate = getDelegate();
1765       
1766       for (int k = 0; k < keyCount; k++)
1767       {
1768         delegate.put((K)keys[k], (V)values[k]);
1769       }
1770     }
1771 
1772     private static final long serialVersionUID = 1L;
1773 
1774     private final Map<K, V> _delegate;
1775     private final boolean   _requireSerializable;
1776   }
1777 
1778   private static class EmptyIterator implements Iterator
1779   {
1780     public boolean hasNext()
1781     {
1782       return false;
1783     }
1784 
1785     public Object next()
1786     {
1787       throw new NoSuchElementException();
1788     }
1789 
1790     public void remove()
1791     {
1792       throw new UnsupportedOperationException();
1793     }
1794   }
1795   
1796   private static final class EmptyListIterator extends EmptyIterator implements ListIterator
1797   {
1798     public boolean hasPrevious()
1799     {
1800       return false;
1801     }
1802 
1803     public Object previous()
1804     {
1805       throw new NoSuchElementException();
1806     }
1807 
1808     public int nextIndex()
1809     {
1810       return 0;
1811     }
1812 
1813     public int previousIndex()
1814     {
1815       return -1;
1816     }
1817 
1818     public void set(Object e)
1819     {
1820       throw new UnsupportedOperationException();
1821     }
1822 
1823     public void add(Object e)
1824     {
1825       throw new UnsupportedOperationException();
1826     }
1827   }
1828 
1829   private static final class EmptyQueue extends AbstractQueue implements Serializable
1830   {
1831     public Iterator iterator()
1832     {
1833       return _EMPTY_ITERATOR;
1834     }
1835 
1836     public int size()
1837     {
1838       return 0;
1839     }
1840 
1841     @Override
1842     public boolean isEmpty()
1843     {
1844       return true;
1845     }
1846     
1847     @Override
1848     public boolean contains(Object o)
1849     {
1850       return false;
1851     }
1852 
1853     public boolean offer(Object e)
1854     {
1855       throw new UnsupportedOperationException();
1856     }
1857 
1858     public Object poll()
1859     {
1860       return null;
1861     }
1862 
1863     public Object peek()
1864     {
1865       return null;
1866     }
1867     
1868     private Object readResolve()
1869     {
1870       return _EMPTY_QUEUE;
1871     }
1872 
1873     private static final long serialVersionUID = 0L;
1874   }
1875 
1876   //
1877   // Build up references to implementation classes used by Collections to implement the following
1878   // features.  This way we can detect when these classes are used and work around problems.
1879   //
1880   private static final Class<? extends List> _CHECKED_LIST;
1881   private static final Class<? extends List> _UNMODIFIABLE_LIST;
1882   private static final Class<? extends List> _SYNCHRONIZED_LIST;
1883   private static final Class<? extends Set> _EMPTY_SET = Collections.emptySet().getClass();
1884   private static final Class<? extends Set> _SINGLETON_SET = Collections.singleton(null).getClass();
1885   private static final Queue _EMPTY_QUEUE = new EmptyQueue();
1886   private static final Iterator _EMPTY_ITERATOR = new EmptyIterator();
1887   private static final Iterator _EMPTY_LIST_ITERATOR = new EmptyListIterator();
1888    
1889   
1890   static
1891   {
1892     // use a LinkedList as it doesn't implement RandomAccess, so that we don't accidentally get
1893     // the RandomAccess subclasses
1894     LinkedList<Object> dummyList = new LinkedList<Object>();
1895     
1896     _CHECKED_LIST      = Collections.checkedList(dummyList, Object.class).getClass();
1897     _UNMODIFIABLE_LIST = Collections.unmodifiableList(dummyList).getClass();
1898     _SYNCHRONIZED_LIST = Collections.synchronizedList(dummyList).getClass();
1899   }
1900 
1901   private static final TrinidadLogger _LOG = 
1902                                         TrinidadLogger.createTrinidadLogger(CollectionUtils.class);
1903 
1904 }