001: package javolution.util;
002:
003: import javolution.lang.Configurable;
004: import javolution.text.Text;
005: import javolution.xml.XMLSerializable;
006: import j2me.lang.CharSequence;
007: import j2me.lang.Comparable;
008: import j2me.util.Comparator;
009:
010: /**
011: * <p> This class represents a comparator to be used for equality as well as
012: * for ordering; instances of this class provide a hashcode function
013: * consistent with equal (if two objects {@link #areEqual
014: * are equal}, they have the same {@link #hashCodeOf hashcode}),
015: * equality with <code>null</code> values is supported.</p>
016: *
017: * <p> {@link FastComparator} can be employed with {@link FastMap} (e.g. custom
018: * key comparators for identity maps, value retrieval using keys of a
019: * different class that the map keys) or with {@link FastCollection}
020: * classes.</p>
021: *
022: * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
023: * @version 4.2, December 18, 2006
024: */
025: public abstract class FastComparator/*<T>*/implements
026: Comparator/*<T>*/, XMLSerializable {
027:
028: /**
029: * Indicates if the system hash code should be rehashed
030: * (see <a href="{@docRoot}/overview-summary.html#configuration">
031: * Javolution Configuration</a> for details).
032: */
033: public static final Configurable/*<Boolean>*/REHASH_SYSTEM_HASHCODE = new Configurable(
034: new Boolean(isPoorSystemHash())) {
035: protected void notifyChange() {
036: _Rehash = ((Boolean) get()).booleanValue();
037: }
038: };
039: static boolean _Rehash = ((Boolean) REHASH_SYSTEM_HASHCODE.get())
040: .booleanValue();
041:
042: private static boolean isPoorSystemHash() {
043: boolean[] dist = new boolean[64]; // Length power of 2.
044: for (int i = 0; i < dist.length; i++) {
045: dist[new Object().hashCode() & (dist.length - 1)] = true;
046: }
047: int occupied = 0;
048: for (int i = 0; i < dist.length;) {
049: occupied += dist[i++] ? 1 : 0; // Count occupied slots.
050: }
051: return occupied < (dist.length >> 2); // Less than 16 slots on 64.
052: }
053:
054: /**
055: * Holds the default object comparator; rehash is performed if the
056: * system hash code (platform dependent) is not evenly distributed.
057: * @see <a href="{@docRoot}/overview-summary.html#configuration">
058: * Javolution Configuration</a>
059: */
060: public static final FastComparator/*<Object>*/DEFAULT = new Default/*<Object>*/();
061:
062: static final class Default/*<T>*/extends FastComparator/*<T>*/{
063:
064: public int hashCodeOf(Object/*{T}*/obj) {
065: return (_Rehash ? REHASH.hashCodeOf(obj) : obj.hashCode());
066: }
067:
068: public boolean areEqual(Object/*{T}*/o1, Object/*{T}*/o2) {
069: return (o1 == null) ? (o2 == null) : (o1 == o2)
070: || o1.equals(o2);
071: }
072:
073: public int compare(Object/*{T}*/o1, Object/*{T}*/o2) {
074: return ((Comparable) o1).compareTo(o2);
075: }
076:
077: public String toString() {
078: return "Default";
079: }
080:
081: };
082:
083: /**
084: * Holds the direct object comparator; no rehash is performed.
085: * Two objects o1 and o2 are considered {@link #areEqual equal} if and
086: * only if <code>o1.equals(o2)</code>. The {@link #compare} method
087: * throws {@link ClassCastException} if the specified objects are not
088: * {@link Comparable}.
089: */
090: public static final FastComparator/*<Object>*/DIRECT = new Direct/*<Object>*/();
091:
092: static final class Direct/*<T>*/extends FastComparator/*<T>*/{
093: public int hashCodeOf(Object/*{T}*/obj) {
094: return obj.hashCode();
095: }
096:
097: public boolean areEqual(Object/*{T}*/o1, Object/*{T}*/o2) {
098: return (o1 == null) ? (o2 == null) : (o1 == o2)
099: || o1.equals(o2);
100: }
101:
102: public int compare(Object/*{T}*/o1, Object/*{T}*/o2) {
103: return ((Comparable) o1).compareTo(o2);
104: }
105:
106: public String toString() {
107: return "Direct";
108: }
109:
110: };
111:
112: /**
113: * Holds the comparator for objects with uneven hash distribution; objects
114: * hashcodes are rehashed. Two objects o1 and o2 are considered
115: * {@link #areEqual equal} if and only if <code>o1.equals(o2)</code>.
116: * The {@link #compare} method throws {@link ClassCastException} if the
117: * specified objects are not {@link Comparable}.
118: */
119: public static final FastComparator/*<Object>*/REHASH = new Rehash/*<Object>*/();
120:
121: static final class Rehash/*<T>*/extends FastComparator/*<T>*/{
122: public int hashCodeOf(Object/*{T}*/obj) {
123: // Formula identical <code>java.util.HashMap</code> to ensures
124: // similar behavior for ill-conditioned hashcode keys.
125: int h = obj.hashCode();
126: h += ~(h << 9);
127: h ^= (h >>> 14);
128: h += (h << 4);
129: return h ^ (h >>> 10);
130: }
131:
132: public boolean areEqual(Object/*{T}*/o1, Object/*{T}*/o2) {
133: return (o1 == null) ? (o2 == null) : (o1 == o2)
134: || o1.equals(o2);
135: }
136:
137: public int compare(Object/*{T}*/o1, Object/*{T}*/o2) {
138: return ((Comparable) o1).compareTo(o2);
139: }
140:
141: public String toString() {
142: return "Rehash";
143: }
144:
145: };
146:
147: /**
148: * Holds a fast comparator for <code>java.lang.String</code>. Hashcodes
149: * are calculated by taking a sample of few characters instead of
150: * the whole string.
151: */
152: public static final FastComparator/*<String>*/STRING = new StringComparator();
153:
154: static final class StringComparator extends FastComparator {
155: public int hashCodeOf(Object obj) {
156: final String str = (String) obj;
157: final int length = str.length();
158: if (length == 0)
159: return 0;
160: return str.charAt(0) + str.charAt(length - 1) * 31
161: + str.charAt(length >> 1) * 1009
162: + str.charAt(length >> 2) * 27583
163: + str.charAt(length - 1 - (length >> 2)) * 73408859;
164: }
165:
166: public boolean areEqual(Object o1, Object o2) {
167: return (o1 == null) ? (o2 == null) : (o1 == o2)
168: || o1.equals(o2);
169: }
170:
171: public int compare(Object o1, Object o2) {
172: return ((String) o1).compareTo((String) o2);
173: }
174:
175: public String toString() {
176: return "String";
177: }
178: };
179:
180: /**
181: * Holds the identity comparator; poorly distributed system hashcodes are
182: * rehashed. Two objects o1 and o2 are considered {@link #areEqual equal}
183: * if and only if <code>(o1 == o2)</code>. The {@link #compare} method
184: * throws {@link ClassCastException} if the specified objects are not
185: * {@link Comparable}.
186: */
187: public static final FastComparator/*<Object>*/IDENTITY = new Identity();
188:
189: static final class Identity extends FastComparator {
190: public int hashCodeOf(Object obj) {
191: int h = System.identityHashCode(obj);
192: if (!_Rehash)
193: return h;
194: h += ~(h << 9);
195: h ^= (h >>> 14);
196: h += (h << 4);
197: return h ^ (h >>> 10);
198:
199: }
200:
201: public boolean areEqual(Object o1, Object o2) {
202: return o1 == o2;
203: }
204:
205: public int compare(Object o1, Object o2) {
206: return ((Comparable) o1).compareTo(o2);
207: }
208:
209: public String toString() {
210: return "identity";
211: }
212: };
213:
214: /**
215: * Holds a lexicographic comparator for any {@link CharSequence} or
216: * {@link String} instances.
217: * Two objects are considered {@link #areEqual equal} if and only if they
218: * represents the same character sequence). The hashcode is calculated
219: * using the following formula (same as for <code>java.lang.String</code>):
220: * <code>s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]</code>
221: */
222: public static final FastComparator/*<CharSequence>*/LEXICAL = new Lexical();
223:
224: static final class Lexical extends FastComparator {
225:
226: public int hashCodeOf(Object obj) {
227: if ((obj instanceof String) || (obj instanceof Text))
228: return obj.hashCode();
229: CharSequence chars = (CharSequence) obj;
230: int h = 0;
231: final int length = chars.length();
232: for (int i = 0; i < length;) {
233: h = 31 * h + chars.charAt(i++);
234: }
235: return h;
236: }
237:
238: public boolean areEqual(Object o1, Object o2) {
239: if ((o1 instanceof String) && (o2 instanceof String))
240: return o1.equals(o2);
241: if ((o1 instanceof CharSequence) && (o2 instanceof String)) {
242: final CharSequence csq = (CharSequence) o1;
243: final String str = (String) o2;
244: final int length = str.length();
245: if (csq.length() != length)
246: return false;
247: for (int i = 0; i < length;) {
248: if (str.charAt(i) != csq.charAt(i++))
249: return false;
250: }
251: return true;
252: }
253: if ((o1 instanceof String) && (o2 instanceof CharSequence)) {
254: final CharSequence csq = (CharSequence) o2;
255: final String str = (String) o1;
256: final int length = str.length();
257: if (csq.length() != length)
258: return false;
259: for (int i = 0; i < length;) {
260: if (str.charAt(i) != csq.charAt(i++))
261: return false;
262: }
263: return true;
264: }
265: if ((o1 == null) || (o2 == null))
266: return o1 == o2;
267: final CharSequence csq1 = (CharSequence) o1;
268: final CharSequence csq2 = (CharSequence) o2;
269: final int length = csq1.length();
270: if (csq2.length() != length)
271: return false;
272: for (int i = 0; i < length;) {
273: if (csq1.charAt(i) != csq2.charAt(i++))
274: return false;
275: }
276: return true;
277: }
278:
279: public int compare(Object left, Object right) {
280: if (left instanceof String) {
281: if (right instanceof String)
282: return ((String) left).compareTo((String) right);
283: // Right must be a CharSequence.
284: String seq1 = (String) left;
285: CharSequence seq2 = (CharSequence) right;
286: int i = 0;
287: int n = Math.min(seq1.length(), seq2.length());
288: while (n-- != 0) {
289: char c1 = seq1.charAt(i);
290: char c2 = seq2.charAt(i++);
291: if (c1 != c2) {
292: return c1 - c2;
293: }
294: }
295: return seq1.length() - seq2.length();
296: }
297: if (right instanceof String)
298: return -compare(right, left);
299:
300: // Both are CharSequence.
301: CharSequence seq1 = (CharSequence) left;
302: CharSequence seq2 = (CharSequence) right;
303: int i = 0;
304: int n = Math.min(seq1.length(), seq2.length());
305: while (n-- != 0) {
306: char c1 = seq1.charAt(i);
307: char c2 = seq2.charAt(i++);
308: if (c1 != c2) {
309: return c1 - c2;
310: }
311: }
312: return seq1.length() - seq2.length();
313: }
314:
315: public String toString() {
316: return "lexical";
317: }
318:
319: };
320:
321: /**
322: * Returns the hash code for the specified object (consistent with
323: * {@link #areEqual}). Two objects considered {@link #areEqual equal} have
324: * the same hash code.
325: *
326: * @param obj the object to return the hashcode for.
327: * @return the hashcode for the specified object.
328: * @throws NullPointerException if the specified object is
329: * <code>null</code>.
330: */
331: public abstract int hashCodeOf(Object/*{T}*/obj);
332:
333: /**
334: * Indicates if the specified objects can be considered equal.
335: *
336: * @param o1 the first object (or <code>null</code>).
337: * @param o2 the second object (or <code>null</code>).
338: * @return <code>true</code> if both objects are considered equal;
339: * <code>false</code> otherwise.
340: */
341: public abstract boolean areEqual(Object/*{T}*/o1, Object/*{T}*/o2);
342:
343: /**
344: * Compares the specified objects for order. Returns a negative integer,
345: * zero, or a positive integer as the first argument is less than, equal to,
346: * or greater than the second.
347: *
348: * @param o1 the first object.
349: * @param o2 the second object.
350: * @return a negative integer, zero, or a positive integer as the first
351: * argument is less than, equal to, or greater than the second.
352: * @throws NullPointerException if any of the specified object is
353: * <code>null</code>.
354: */
355: public abstract int compare(Object/*{T}*/o1, Object/*{T}*/o2);
356:
357: }
|