001 /*
002 * Copyright 2009-2015 UnboundID Corp.
003 * All Rights Reserved.
004 */
005 /*
006 * Copyright (C) 2015 UnboundID Corp.
007 *
008 * This program is free software; you can redistribute it and/or modify
009 * it under the terms of the GNU General Public License (GPLv2 only)
010 * or the terms of the GNU Lesser General Public License (LGPLv2.1 only)
011 * as published by the Free Software Foundation.
012 *
013 * This program is distributed in the hope that it will be useful,
014 * but WITHOUT ANY WARRANTY; without even the implied warranty of
015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
016 * GNU General Public License for more details.
017 *
018 * You should have received a copy of the GNU General Public License
019 * along with this program; if not, see <http://www.gnu.org/licenses>.
020 */
021 package com.unboundid.ldap.sdk.unboundidds.examples;
022
023
024
025 import java.io.Serializable;
026 import java.util.Arrays;
027 import java.util.Comparator;
028 import java.util.Iterator;
029 import java.util.TreeSet;
030
031 import com.unboundid.ldap.sdk.Filter;
032 import com.unboundid.util.NotMutable;
033 import com.unboundid.util.ThreadSafety;
034 import com.unboundid.util.ThreadSafetyLevel;
035
036 import static com.unboundid.util.StaticUtils.*;
037
038
039
040 /**
041 * <BLOCKQUOTE>
042 * <B>NOTE:</B> This class is part of the Commercial Edition of the UnboundID
043 * LDAP SDK for Java. It is not available for use in applications that
044 * include only the Standard Edition of the LDAP SDK, and is not supported for
045 * use in conjunction with non-UnboundID products.
046 * </BLOCKQUOTE>
047 * This class provides a comparator that may be used to define a relative order
048 * for search filters. The filter order will be based first on the filter type
049 * (in the following order: AND, OR, NOT, equality, substring,
050 * greater-or-equal, less-or-equal, presence, approximate match, extensible
051 * match), then based on the attribute name, and then by the assertion value.
052 * For AND and OR filters, with all other things equal, a filter with fewer
053 * components will be ordered before one with more components. For a substring
054 * filter with all other things equal, then a filter missing a substring element
055 * will be ordered before one with that element, and one with fewer subAny
056 * elements will be ordered before one with more subAny elements. For an
057 * extensible match filter with all other things being equal, a filter without
058 * an element will be ordered before one with that element.
059 */
060 @NotMutable()
061 @ThreadSafety(level=ThreadSafetyLevel.COMPLETELY_THREADSAFE)
062 public final class FilterComparator
063 implements Comparator<Filter>, Serializable
064 {
065 /**
066 * The singleton instance of this comparator.
067 */
068 private static final FilterComparator INSTANCE = new FilterComparator();
069
070
071
072 /**
073 * The serial version UID for this serializable class.
074 */
075 private static final long serialVersionUID = 7637416445464620770L;
076
077
078
079 /**
080 * Creates a new instance of this filter comparator.
081 */
082 private FilterComparator()
083 {
084 // No implementation is required.
085 }
086
087
088
089 /**
090 * Retrieves the singleton instance of this filter comparator.
091 *
092 * @return The singleton instance of this filter comparator.
093 */
094 public static FilterComparator getInstance()
095 {
096 return INSTANCE;
097 }
098
099
100
101 /**
102 * Determines a relative order for the provided filter objects.
103 *
104 * @param f1 The first filter for which to make the determination.
105 * @param f2 The second filter for which to make the determination.
106 *
107 * @return A negative value if the first filter should be ordered before the
108 * second, a positive value if the first filter should be ordered
109 * after the second, or zero if there is no difference in their
110 * relative orders.
111 */
112 public int compare(final Filter f1, final Filter f2)
113 {
114 final byte type1 = f1.getFilterType();
115 final byte type2 = f2.getFilterType();
116
117 if (type1 != type2)
118 {
119 return ((type1 & 0x1F) - (type2 & 0x1F));
120 }
121
122 final String name1 = toLowerCase(f1.getAttributeName());
123 final String name2 = toLowerCase(f2.getAttributeName());
124 if ((name1 != null) && (name2 != null))
125 {
126 final int cmpValue = name1.compareTo(name2);
127 if (cmpValue != 0)
128 {
129 return cmpValue;
130 }
131 }
132
133 final byte[] value1 = f1.getAssertionValueBytes();
134 if (value1 != null)
135 {
136 final byte[] value2 = f2.getAssertionValueBytes();
137 final int cmpValue = compare(value1, value2);
138 if (cmpValue != 0)
139 {
140 return cmpValue;
141 }
142 }
143
144 switch (type1)
145 {
146 case Filter.FILTER_TYPE_AND:
147 case Filter.FILTER_TYPE_OR:
148 return compareANDOrOR(f1, f2);
149
150 case Filter.FILTER_TYPE_NOT:
151 return compare(f1.getNOTComponent(), f2.getNOTComponent());
152
153 case Filter.FILTER_TYPE_PRESENCE:
154 case Filter.FILTER_TYPE_EQUALITY:
155 case Filter.FILTER_TYPE_GREATER_OR_EQUAL:
156 case Filter.FILTER_TYPE_LESS_OR_EQUAL:
157 case Filter.FILTER_TYPE_APPROXIMATE_MATCH:
158 // The necessary processing for these types has already been done.
159 return 0;
160
161 case Filter.FILTER_TYPE_SUBSTRING:
162 return compareSubstring(f1, f2);
163
164 case Filter.FILTER_TYPE_EXTENSIBLE_MATCH:
165 return compareExtensible(f1, f2);
166
167 default:
168 // This should never happen.
169 return 0;
170 }
171 }
172
173
174
175 /**
176 * Performs a comparison of the contents of AND or OR filters.
177 *
178 * @param f1 The first filter for which to make the determination.
179 * @param f2 The second filter for which to make the determination.
180 *
181 * @return A negative value if the first filter should be ordered before the
182 * second, a positive value if the first filter should be ordered
183 * after the second, or zero if there is no difference in their
184 * relative orders.
185 */
186 private static int compareANDOrOR(final Filter f1, final Filter f2)
187 {
188 final TreeSet<Filter> set1 = new TreeSet<Filter>(INSTANCE);
189 final TreeSet<Filter> set2 = new TreeSet<Filter>(INSTANCE);
190
191 set1.addAll(Arrays.asList(f1.getComponents()));
192 set2.addAll(Arrays.asList(f2.getComponents()));
193
194 final Iterator<Filter> iterator1 = set1.iterator();
195 final Iterator<Filter> iterator2 = set2.iterator();
196 while (true)
197 {
198 final Filter comp1;
199 if (iterator1.hasNext())
200 {
201 comp1 = iterator1.next();
202 }
203 else if (iterator2.hasNext())
204 {
205 return -1;
206 }
207 else
208 {
209 return 0;
210 }
211
212 final Filter comp2;
213 if (iterator2.hasNext())
214 {
215 comp2 = iterator2.next();
216 }
217 else
218 {
219 return 1;
220 }
221
222 final int compValue = INSTANCE.compare(comp1, comp2);
223 if (compValue != 0)
224 {
225 return compValue;
226 }
227 }
228 }
229
230
231
232 /**
233 * Performs a comparison of the contents of substring filters.
234 *
235 * @param f1 The first filter for which to make the determination.
236 * @param f2 The second filter for which to make the determination.
237 *
238 * @return A negative value if the first filter should be ordered before the
239 * second, a positive value if the first filter should be ordered
240 * after the second, or zero if there is no difference in their
241 * relative orders.
242 */
243 private static int compareSubstring(final Filter f1, final Filter f2)
244 {
245 final byte[] sI1 = f1.getSubInitialBytes();
246 final byte[] sI2 = f2.getSubInitialBytes();
247 if (sI1 == null)
248 {
249 if (sI2 != null)
250 {
251 return -1;
252 }
253 }
254 else if (sI2 == null)
255 {
256 return 1;
257 }
258 else
259 {
260 final int cmpValue = compare(sI1, sI2);
261 if (cmpValue != 0)
262 {
263 return cmpValue;
264 }
265 }
266
267 final byte[][] sA1 = f1.getSubAnyBytes();
268 final byte[][] sA2 = f2.getSubAnyBytes();
269 if (sA1.length == 0)
270 {
271 if (sA2.length > 0)
272 {
273 return -1;
274 }
275 }
276 else if (sA2.length == 0)
277 {
278 return 1;
279 }
280 else
281 {
282 final int minLength = Math.min(sA1.length, sA2.length);
283 for (int i=0; i < minLength; i++)
284 {
285 final int cmpValue = compare(sA1[i], sA2[i]);
286 if (cmpValue != 0)
287 {
288 return cmpValue;
289 }
290 }
291
292 if (sA1.length < sA2.length)
293 {
294 return -1;
295 }
296 else if (sA2.length < sA1.length)
297 {
298 return 1;
299 }
300 }
301
302 final byte[] sF1 = f1.getSubFinalBytes();
303 final byte[] sF2 = f2.getSubFinalBytes();
304 if (sF1 == null)
305 {
306 if (sF2 != null)
307 {
308 return -1;
309 }
310 else
311 {
312 return 0;
313 }
314 }
315 else if (sF2 == null)
316 {
317 return 1;
318 }
319 else
320 {
321 return compare(sF1, sF2);
322 }
323 }
324
325
326
327 /**
328 * Performs a comparison of the contents of substring filters.
329 *
330 * @param f1 The first filter for which to make the determination.
331 * @param f2 The second filter for which to make the determination.
332 *
333 * @return A negative value if the first filter should be ordered before the
334 * second, a positive value if the first filter should be ordered
335 * after the second, or zero if there is no difference in their
336 * relative orders.
337 */
338 private static int compareExtensible(final Filter f1, final Filter f2)
339 {
340 final String name1 = f1.getAttributeName();
341 final String name2 = f2.getAttributeName();
342 if (name1 == null)
343 {
344 if (name2 != null)
345 {
346 return -1;
347 }
348 }
349 else if (name2 == null)
350 {
351 return 1;
352 }
353
354 final String mr1 = f1.getMatchingRuleID();
355 final String mr2 = f2.getMatchingRuleID();
356 if (mr1 == null)
357 {
358 if (mr2 != null)
359 {
360 return -1;
361 }
362 }
363 else if (mr2 == null)
364 {
365 return 1;
366 }
367 else
368 {
369 final int cmpValue = mr1.compareTo(mr2);
370 if (cmpValue != 0)
371 {
372 return cmpValue;
373 }
374 }
375
376 if (f1.getDNAttributes())
377 {
378 if (f2.getDNAttributes())
379 {
380 return 0;
381 }
382 else
383 {
384 return 1;
385 }
386 }
387 else if (f2.getDNAttributes())
388 {
389 return -1;
390 }
391 else
392 {
393 return 0;
394 }
395 }
396
397
398
399 /**
400 * Performs a comparison of the contents of the provided byte arrays.
401 *
402 * @param a1 The first array to be compared.
403 * @param a2 The second array to be compared.
404 *
405 * @return An integer value denoting the comparison value.
406 */
407 private static int compare(final byte[] a1, final byte[] a2)
408 {
409 final int length = Math.min(a1.length, a2.length);
410
411 for (int i=0; i < length; i++)
412 {
413 final int b1 = 0xFF & a1[i];
414 final int b2 = 0xFF & a2[i];
415 if (b1 != b2)
416 {
417 return b1 - b2;
418 }
419 }
420
421 return (a1.length - a2.length);
422 }
423
424
425
426 /**
427 * Retrieves a hash code for this filter comparator.
428 *
429 * @return A hash code for this filter comparator.
430 */
431 @Override()
432 public int hashCode()
433 {
434 return 0;
435 }
436
437
438
439 /**
440 * Indicates whether the provided object is equal to this filter comparator.
441 *
442 * @param o The object for which to make the determination.
443 *
444 * @return {@code true} if the provided object is equal to this filter
445 * comparator, or {@code false} if not.
446 */
447 @Override()
448 public boolean equals(final Object o)
449 {
450 return ((o != null) && (o instanceof FilterComparator));
451 }
452 }