ConverterSet


1   /*
2    *  Copyright 2001-2005 Stephen Colebourne
3    *
4    *  Licensed under the Apache License, Version 2.0 (the "License");
5    *  you may not use this file except in compliance with the License.
6    *  You may obtain a copy of the License at
7    *
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    *
10   *  Unless required by applicable law or agreed to in writing, software
11   *  distributed under the License is distributed on an "AS IS" BASIS,
12   *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   *  See the License for the specific language governing permissions and
14   *  limitations under the License.
15   */
16  package org.joda.time.convert;
17  
18  /**
19   * A set of converters, which allows exact converters to be quickly
20   * selected. This class is threadsafe because it is (essentially) immutable.
21   *
22   * @author Brian S O'Neill
23   * @since 1.0
24   */
25  class ConverterSet {
26      private final Converter[] iConverters;
27  
28      // A simple immutable hashtable: closed hashing, linear probing, sized
29      // power of 2, at least one null slot.
30      private Entry[] iSelectEntries;
31  
32      ConverterSet(Converter[] converters) {
33          // Since this is a package private constructor, we trust ourselves not
34          // to alter the array outside this class.
35          iConverters = converters;
36          iSelectEntries = new Entry[1 << 4]; // 16
37      }
38  
39      /**
40       * Returns the closest matching converter for the given type, or null if
41       * none found.
42       *
43       * @param type type to select, which may be null
44       * @throws IllegalStateException if multiple converters match the type
45       * equally well
46       */
47      Converter select(Class   type) throws IllegalStateException   {
48          // Check the hashtable first.
49          Entry[] entries = iSelectEntries;
50          int length = entries.length;
51          int index = type == null ? 0 : type.hashCode() & (length - 1);
52  
53          Entry e;
54          // This loop depends on there being at least one null slot.
55          while ((e = entries[index]) != null) {
56              if (e.iType == type) {
57                  return e.iConverter;
58              }
59              if (++index >= length) {
60                  index = 0;
61              }
62          }
63  
64          // Not found in the hashtable, so do actual work.
65  
66          Converter converter = selectSlow(this, type);
67          e = new Entry(type, converter);
68  
69          // Save the entry for future selects. This class must be threadsafe,
70          // but there is no synchronization. Since the hashtable is being used
71          // as a cache, it is okay to destroy existing entries. This isn't
72          // likely to occur unless there is a high amount of concurrency. As
73          // time goes on, cache updates will occur less often, and the cache
74          // will fill with all the necessary entries.
75  
76          // Do all updates on a copy: slots in iSelectEntries must not be
77          // updated by multiple threads as this can allow all null slots to be
78          // consumed.
79          entries = (Entry[])entries.clone();
80  
81          // Add new entry.
82          entries[index] = e;
83  
84          // Verify that at least one null slot exists!
85          for (int i=0; i<length; i++) {
86              if (entries[i] == null) {
87                  // Found a null slot, swap in new hashtable.
88                  iSelectEntries = entries;
89                  return converter;
90              }
91          }
92  
93          // Double capacity and re-hash.
94  
95          int newLength = length << 1;
96          Entry[] newEntries = new Entry[newLength];
97          for (int i=0; i<length; i++) {
98              e = entries[i];
99              type = e.iType;
100             index = type == null ? 0 : type.hashCode() & (newLength - 1);
101             while (newEntries[index] != null) {
102                 if (++index >= newLength) {
103                     index = 0;
104                 }
105             }
106             newEntries[index] = e;
107         }
108 
109         // Swap in new hashtable.
110         iSelectEntries = newEntries;
111         return converter;
112     }
113 
114     /**
115      * Returns the amount of converters in the set.
116      */
117     int size() {
118         return iConverters.length;
119     }
120 
121     /**
122      * Copies all the converters in the set to the given array.
123      */
124     void copyInto(Converter[] converters) {
125         System.arraycopy(iConverters, 0, converters, 0, iConverters.length);
126     }
127 
128     /**
129      * Returns a copy of this set, with the given converter added. If a
130      * matching converter is already in the set, the given converter replaces
131      * it. If the converter is exactly the same as one already in the set, the
132      * original set is returned.
133      *
134      * @param converter  converter to add, must not be null
135      * @param removed  if not null, element 0 is set to the removed converter
136      * @throws NullPointerException if converter is null
137      */
138     ConverterSet add(Converter converter, Converter[] removed) {
139         Converter[] converters = iConverters;
140         int length = converters.length;
141 
142         for (int i=0; i<length; i++) {
143             Converter existing = converters[i];
144             if (converter.equals(existing)) {
145                 // Already in the set.
146                 if (removed != null) {
147                     removed[0] = null;
148                 }
149                 return this;
150             }
151             
152             if (converter.getSupportedType() == existing.getSupportedType()) {
153                 // Replace the converter.
154                 Converter[] copy = new Converter[length];
155                     
156                 for (int j=0; j<length; j++) {
157                     if (j != i) {
158                         copy[j] = converters[j];
159                     } else {
160                         copy[j] = converter;
161                     }
162                 }
163 
164                 if (removed != null) {
165                     removed[0] = existing;
166                 }
167                 return new ConverterSet(copy);
168             }
169         }
170 
171         // Not found, so add it.
172         Converter[] copy = new Converter[length + 1];
173         System.arraycopy(converters, 0, copy, 0, length);
174         copy[length] = converter;
175         
176         if (removed != null) {
177             removed[0] = null;
178         }
179         return new ConverterSet(copy);
180     }
181 
182     /**
183      * Returns a copy of this set, with the given converter removed. If the
184      * converter was not in the set, the original set is returned.
185      *
186      * @param converter  converter to remove, must not be null
187      * @param removed  if not null, element 0 is set to the removed converter
188      * @throws NullPointerException if converter is null
189      */
190     ConverterSet remove(Converter converter, Converter[] removed) {
191         Converter[] converters = iConverters;
192         int length = converters.length;
193 
194         for (int i=0; i<length; i++) {
195             if (converter.equals(converters[i])) {
196                 return remove(i, removed);
197             }
198         }
199 
200         // Not found.
201         if (removed != null) {
202             removed[0] = null;
203         }
204         return this;
205     }
206 
207     /**
208      * Returns a copy of this set, with the converter at the given index
209      * removed.
210      *
211      * @param index index of converter to remove
212      * @param removed if not null, element 0 is set to the removed converter
213      * @throws IndexOutOfBoundsException if the index is invalid
214      */
215     ConverterSet remove(final int index, Converter[] removed) {
216         Converter[] converters = iConverters;
217         int length = converters.length;
218         if (index >= length) {
219             throw new IndexOutOfBoundsException  ();
220         }
221 
222         if (removed != null) {
223             removed[0] = converters[index];
224         }
225 
226         Converter[] copy = new Converter[length - 1];
227                 
228         int j = 0;
229         for (int i=0; i<length; i++) {
230             if (i != index) {
231                 copy[j++] = converters[i];
232             }
233         }
234         
235         return new ConverterSet(copy);
236     }
237 
238     /**
239      * Returns the closest matching converter for the given type, but not very
240      * efficiently.
241      */
242     private static Converter selectSlow(ConverterSet set, Class   type) {
243         Converter[] converters = set.iConverters;
244         int length = converters.length;
245         Converter converter;
246 
247         for (int i=length; --i>=0; ) {
248             converter = converters[i];
249             Class   supportedType = converter.getSupportedType();
250 
251             if (supportedType == type) {
252                 // Exact match.
253                 return converter;
254             }
255 
256             if (supportedType == null || (type != null && !supportedType.isAssignableFrom(type))) {
257                 // Eliminate the impossible.
258                 set = set.remove(i, null);
259                 converters = set.iConverters;
260                 length = converters.length;
261             }
262         }
263 
264         // Haven't found exact match, so check what remains in the set.
265 
266         if (type == null || length == 0) {
267             return null;
268         }
269         if (length == 1) {
270             // Found the one best match.
271             return converters[0];
272         }
273 
274         // At this point, there exist multiple potential converters.
275 
276         // Eliminate supertypes.
277         for (int i=length; --i>=0; ) {
278             converter = converters[i];
279             Class   supportedType = converter.getSupportedType();
280             for (int j=length; --j>=0; ) {
281                 if (j != i && converters[j].getSupportedType().isAssignableFrom(supportedType)) {
282                     // Eliminate supertype.
283                     set = set.remove(j, null);
284                     converters = set.iConverters;
285                     length = converters.length;
286                     i = length - 1;
287                 }
288             }
289         }        
290         
291         // Check what remains in the set.
292 
293         if (length == 1) {
294             // Found the one best match.
295             return converters[0];
296         }
297 
298         // Class c implements a, b {}
299         // Converters exist only for a and b. Which is better? Neither.
300 
301         StringBuffer   msg = new StringBuffer  ();
302         msg.append("Unable to find best converter for type \"");
303         msg.append(type.getName());
304         msg.append("\" from remaining set: ");
305         for (int i=0; i<length; i++) {
306             converter = converters[i];
307             Class   supportedType = converter.getSupportedType();
308 
309             msg.append(converter.getClass().getName());
310             msg.append('[');
311             msg.append(supportedType == null ? null : supportedType.getName());
312             msg.append("], ");
313         }
314 
315         throw new IllegalStateException  (msg.toString());
316     }
317 
318     static class Entry {
319         final Class   iType;
320         final Converter iConverter;
321 
322         Entry(Class   type, Converter converter) {
323             iType = type;
324             iConverter = converter;
325         }
326     }
327 
328 }
329
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags