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