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