FastComparator


1   package javolution.util;
2   
3   import javolution.Javolution;
4   import javolution.lang.Configurable;
5   import javolution.text.Text;
6   import javolution.xml.XMLFormat;
7   import javolution.xml.stream.XMLStreamException;
8   import j2me.io.Serializable;
9   import j2me.lang.CharSequence;
10  import j2me.lang.Comparable;
11  import j2me.util.Comparator;
12  
13  /**
14   * <p> This class represents a comparator to be used for equality as well as 
15   *     for ordering; instances of this class provide a hashcode function 
16   *     consistent with equal (if two objects {@link #areEqual
17   *     are equal}, they have the same {@link #hashCodeOf hashcode}),
18   *     equality with <code>null</code> values is supported.</p>
19   *     
20   * <p> {@link FastComparator} can be employed with {@link FastMap} (e.g. custom 
21   *     key comparators for identity maps, value retrieval using keys of a 
22   *     different class that the map keys) or with {@link FastCollection}
23   *     classes.</p>
24   *     
25   * @author <a HREF="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
26   * @version 4.2, December 18, 2006
27   */
28  public abstract class FastComparator/*<T>*/implements Comparator/*<T>*/,
29          Serializable {
30  
31      /**
32       * Holds the default XML representation for FastComparator instances
33       * (format ensures unicity of predefined comparator).
34       */
35      protected static final XMLFormat/*<FastComparator>*/ XML = new XMLFormat(
36              Javolution.j2meGetClass("javolution.util.FastComparator")) {
37  
38          public Object   newInstance(Class   cls, javolution.xml.XMLFormat.InputElement xml) throws XMLStreamException {
39              if (cls == FastComparator.DEFAULT.getClass())
40                  return FastComparator.DEFAULT;
41              if (cls == FastComparator.DIRECT.getClass())
42                  return FastComparator.DIRECT;
43              if (cls == FastComparator.IDENTITY.getClass())
44                  return FastComparator.IDENTITY;
45              if (cls == FastComparator.LEXICAL.getClass())
46                  return FastComparator.LEXICAL;
47              if (cls == FastComparator.REHASH.getClass())
48                  return FastComparator.REHASH;
49              return super.newInstance(cls, xml);
50          }
51  
52          public void read(InputElement xml, Object   obj) throws XMLStreamException {
53              // Do nothing.
54          }
55  
56          public void write(Object   obj, OutputElement xml) throws XMLStreamException {
57              // Do nothing.
58          }
59      };
60  
61      /**
62       * Indicates if the system hash code should be rehashed 
63       * (see <a HREF="{@docRoot}/overview-summary.html#configuration">
64       * Javolution Configuration</a> for details).
65       */
66      public static final Configurable/*<Boolean>*/ REHASH_SYSTEM_HASHCODE 
67           = new Configurable(isPoorSystemHash()) {
68          protected void notifyChange() {
69              _Rehash = ((Boolean  )get()).booleanValue();
70          }
71      };
72      static boolean _Rehash 
73           = ((Boolean  )REHASH_SYSTEM_HASHCODE.get()).booleanValue();
74  
75      /**
76       * Holds the default object comparator; rehash is performed if the 
77       * system hash code (platform dependent) is not evenly distributed.
78       * @see <a HREF="{@docRoot}/overview-summary.html#configuration">
79       *      Javolution Configuration</a> 
80       */
81      public static final FastComparator/*<Object>*/ DEFAULT = new Default();
82  
83      static final class Default extends FastComparator {
84  
85          public int hashCodeOf(Object   obj) {
86              return (_Rehash ? REHASH.hashCodeOf(obj) : obj.hashCode());
87          }
88  
89          public boolean areEqual(Object   o1, Object   o2) {
90              return (o1 == null) ? (o2 == null) : (o1 == o2) || o1.equals(o2);
91          }
92  
93          public int compare(Object   o1, Object   o2) {
94              return ((Comparable  ) o1).compareTo(o2);
95          }
96  
97          public String   toString() {
98              return "default";
99          }
100 
101     };
102 
103     /**
104      * Holds the direct object comparator; no rehash is performed.
105      * Two objects o1 and o2 are considered {@link #areEqual equal} if and
106      * only if <code>o1.equals(o2)</code>. The {@link #compare} method 
107      * throws {@link ClassCastException} if the specified objects are not
108      * {@link Comparable}. 
109      */
110     public static final FastComparator/*<Object>*/ DIRECT = new Direct();
111 
112     static final class Direct extends FastComparator {
113         public int hashCodeOf(Object   obj) {
114             return obj.hashCode();
115         }
116 
117         public boolean areEqual(Object   o1, Object   o2) {
118             return (o1 == null) ? (o2 == null) : (o1 == o2) || o1.equals(o2);
119         }
120 
121         public int compare(Object   o1, Object   o2) {
122             return ((Comparable  ) o1).compareTo(o2);
123         }
124 
125         public String   toString() {
126             return "direct";
127         }
128 
129     };
130 
131     /**
132      * Holds the comparator for objects with uneven hash distribution; objects
133      * hashcodes are rehashed. Two objects o1 and o2 are considered 
134      * {@link #areEqual equal} if and only if <code>o1.equals(o2)</code>.
135      * The {@link #compare} method throws {@link ClassCastException} if the
136      * specified objects are not {@link Comparable}.
137      */
138     public static final FastComparator/*<Object>*/ REHASH = new Rehash();
139 
140     static final class Rehash extends FastComparator {
141         public int hashCodeOf(Object   obj) {
142             // Formula identical <code>java.util.HashMap</code> to ensures
143             // similar behavior for ill-conditioned hashcode keys. 
144             int h = obj.hashCode();
145             h += ~(h << 9);
146             h ^= (h >>> 14);
147             h += (h << 4);
148             return h ^ (h >>> 10);
149         }
150 
151         public boolean areEqual(Object   o1, Object   o2) {
152             return (o1 == null) ? (o2 == null) : (o1 == o2) || o1.equals(o2);
153         }
154 
155         public int compare(Object   o1, Object   o2) {
156             return ((Comparable  ) o1).compareTo(o2);
157         }
158 
159         public String   toString() {
160             return "rehash";
161         }
162 
163     };
164 
165     /**
166      * Holds the identity comparator; poorly distributed system hashcodes are
167      * rehashed. Two objects o1 and o2 are considered {@link #areEqual equal} 
168      * if and only if <code>(o1 == o2)</code>. The {@link #compare} method 
169      * throws {@link ClassCastException} if the specified objects are not
170      * {@link Comparable}.
171      */
172     public static final FastComparator/*<Object>*/ IDENTITY = new Identity();
173 
174     static final class Identity extends FastComparator {
175         public int hashCodeOf(Object   obj) {
176             int h = System.identityHashCode(obj);
177             if (!_Rehash)
178                 return h;
179             h += ~(h << 9);
180             h ^= (h >>> 14);
181             h += (h << 4);
182             return h ^ (h >>> 10);
183 
184         }
185 
186         public boolean areEqual(Object   o1, Object   o2) {
187             return o1 == o2;
188         }
189 
190         public int compare(Object   o1, Object   o2) {
191             return ((Comparable  ) o1).compareTo(o2);
192         }
193 
194         public String   toString() {
195             return "identity";
196         }
197     };
198 
199     /**
200      * Holds a lexicographic comparator for any {@link CharSequence} or 
201      * {@link String} instances. 
202      * Two objects are considered {@link #areEqual equal} if and only if they 
203      * represents the same character sequence). The hashcode is calculated
204      * using the following formula (same as for <code>java.lang.String</code>):
205      * <code>s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]</code>
206      */
207     public static final FastComparator/*<CharSequence>*/ LEXICAL = new Lexical();
208 
209     static final class Lexical extends FastComparator {
210 
211         public int hashCodeOf(Object   obj) {
212             if ((obj instanceof String  ) || (obj instanceof Text))
213                 return obj.hashCode();
214             CharSequence   chars = (CharSequence  ) obj;
215             int h = 0;
216             final int length = chars.length();
217             for (int i = 0; i < length;) {
218                 h = 31 * h + chars.charAt(i++);
219             }
220             return h;
221         }
222 
223         public boolean areEqual(Object   o1, Object   o2) {
224             if ((o1 instanceof String  ) && (o2 instanceof String  ))
225                 return o1.equals(o2);
226             if ((o1 instanceof CharSequence  ) && (o2 instanceof String  )) {
227                 final CharSequence   csq = (CharSequence  ) o1;
228                 final String   str = (String  ) o2;
229                 final int length = str.length();
230                 if (csq.length() != length)
231                     return false;
232                 for (int i = 0; i < length;) {
233                     if (str.charAt(i) != csq.charAt(i++))
234                         return false;
235                 }
236                 return true;
237             }
238             if ((o1 instanceof String  ) && (o2 instanceof CharSequence  )) {
239                 final CharSequence   csq = (CharSequence  ) o2;
240                 final String   str = (String  ) o1;
241                 final int length = str.length();
242                 if (csq.length() != length)
243                     return false;
244                 for (int i = 0; i < length;) {
245                     if (str.charAt(i) != csq.charAt(i++))
246                         return false;
247                 }
248                 return true;
249             }
250             if ((o1 == null) || (o2 == null)) 
251                 return o1 == o2;
252             final CharSequence   csq1 = (CharSequence  ) o1;
253             final CharSequence   csq2 = (CharSequence  ) o2;
254             final int length = csq1.length();
255             if (csq2.length() != length)
256                 return false;
257             for (int i = 0; i < length;) {
258                 if (csq1.charAt(i) != csq2.charAt(i++))
259                     return false;
260             }
261             return true;
262         }
263 
264         public int compare(Object   left, Object   right) {
265             if (left instanceof String  ) {
266                 if (right instanceof String  )
267                     return ((String  ) left).compareTo((String  ) right);
268                 // Right must be a CharSequence.
269                 String   seq1 = (String  ) left;
270                 CharSequence   seq2 = (CharSequence  ) right;
271                 int i = 0;
272                 int n = Math.min(seq1.length(), seq2.length());
273                 while (n-- != 0) {
274                     char c1 = seq1.charAt(i);
275                     char c2 = seq2.charAt(i++);
276                     if (c1 != c2) {
277                         return c1 - c2;
278                     }
279                 }
280                 return seq1.length() - seq2.length();
281             }
282             if (right instanceof String  )
283                 return -compare(right, left);
284 
285             // Both are CharSequence.
286             CharSequence   seq1 = (CharSequence  ) left;
287             CharSequence   seq2 = (CharSequence  ) right;
288             int i = 0;
289             int n = Math.min(seq1.length(), seq2.length());
290             while (n-- != 0) {
291                 char c1 = seq1.charAt(i);
292                 char c2 = seq2.charAt(i++);
293                 if (c1 != c2) {
294                     return c1 - c2;
295                 }
296             }
297             return seq1.length() - seq2.length();
298         }
299 
300         public String   toString() {
301             return "lexical";
302         }
303 
304     };
305 
306     /**
307      * Returns the hash code for the specified object (consistent with 
308      * {@link #areEqual}). Two objects considered {@link #areEqual equal} have 
309      * the same hash code. 
310      * 
311      * @param  obj the object to return the hashcode for.
312      * @return the hashcode for the specified object.
313      * @throws NullPointerException if the specified object is 
314      *         <code>null</code>.
315      */
316     public abstract int hashCodeOf(Object  /*{T}*/obj);
317 
318     /**
319      * Indicates if the specified objects can be considered equal.
320      * 
321      * @param o1 the first object (or <code>null</code>).
322      * @param o2 the second object (or <code>null</code>).
323      * @return <code>true</code> if both objects are considered equal;
324      *         <code>false</code> otherwise. 
325      */
326     public abstract boolean areEqual(Object  /*{T}*/o1, Object  /*{T}*/o2);
327 
328     /**
329      * Compares the specified objects for order. Returns a negative integer, 
330      * zero, or a positive integer as the first argument is less than, equal to,
331      * or greater than the second.
332      * 
333      * @param o1 the first object.
334      * @param o2 the second object.
335      * @return a negative integer, zero, or a positive integer as the first
336      *         argument is less than, equal to, or greater than the second.
337      * @throws NullPointerException if any of the specified object is 
338      *         <code>null</code>.
339      */
340     public abstract int compare(Object  /*{T}*/o1, Object  /*{T}*/o2);
341 
342     /**
343      * Test the system hash code.
344      * 
345      * @return <code>true</code> if the system hash code is not evenly 
346      *         distributed; <code>false<code> otherwise.
347      */
348     private static Boolean   isPoorSystemHash() {
349         boolean[] dist = new boolean[32]; // Length power of 2.
350         for (int i = 0; i < dist.length; i++) {
351             dist[new Object  ().hashCode() & (dist.length - 1)] = true;
352         }
353         int holes = 0;
354         for (int i = 0; i < dist.length; i++) {
355             if (!dist[i])
356                 holes++; // Count holes.
357         }
358         return new Boolean  (holes > (dist.length >> 1));
359     }
360 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags