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    }