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