001/*
002 * Copyright 2007-2019 Ping Identity Corporation
003 * All Rights Reserved.
004 */
005/*
006 * Copyright (C) 2008-2019 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;
022
023
024
025import java.io.Serializable;
026import java.util.ArrayList;
027import java.util.Arrays;
028import java.util.Collection;
029import java.util.Collections;
030import java.util.Comparator;
031import java.util.Iterator;
032import java.util.List;
033import java.util.SortedSet;
034import java.util.TreeSet;
035
036import com.unboundid.asn1.ASN1OctetString;
037import com.unboundid.ldap.matchingrules.MatchingRule;
038import com.unboundid.ldap.sdk.controls.SortKey;
039import com.unboundid.ldap.sdk.schema.Schema;
040import com.unboundid.util.Debug;
041import com.unboundid.util.StaticUtils;
042import com.unboundid.util.ThreadSafety;
043import com.unboundid.util.ThreadSafetyLevel;
044
045
046
047/**
048 * This class provides a mechanism for client-side entry sorting.  Sorting may
049 * be based on attributes contained in the entry, and may also be based on the
050 * hierarchical location of the entry in the DIT.  The sorting may be applied
051 * to any collection of entries, including the entries included in a
052 * {@link SearchResult} object.
053 * <BR><BR>
054 * This class provides a client-side alternative to the use of the
055 * {@link com.unboundid.ldap.sdk.controls.ServerSideSortRequestControl}.
056 * Client-side sorting is most appropriate for small result sets, as it requires
057 * all entries to be held in memory at the same time.  It is a good alternative
058 * to server-side sorting when the overhead of sorting should be distributed
059 * across client systems rather than on the server, and in cases in which the
060 * target directory server does not support the use of the server-side sort
061 * request control.
062 * <BR><BR>
063 * For best results, a {@link Schema} object may be used to provide an
064 * indication as to which matching rules should be used to perform the ordering.
065 * If no {@code Schema} object is provided, then all ordering will be performed
066 * using case-ignore string matching.
067 * <BR><BR>
068 * <H2>Example</H2>
069 * The following example may be used to obtain a sorted set of search result
070 * entries, ordered first by sn and then by givenName, without consideration for
071 * hierarchy:
072 * <PRE>
073 * SearchResult searchResult = connection.search("dc=example,dc=com",
074 *      SearchScope.SUB, Filter.createEqualityFilter("sn", "Smith"));
075 *
076 * EntrySorter entrySorter = new EntrySorter(false,
077 *      new SortKey("sn"), new SortKey("givenName"));
078 * SortedSet&lt;Entry&gt; sortedEntries =
079 *     entrySorter.sort(searchResult.getSearchEntries());
080 * </PRE>
081 */
082@ThreadSafety(level=ThreadSafetyLevel.COMPLETELY_THREADSAFE)
083public final class EntrySorter
084       implements Comparator<Entry>, Serializable
085{
086  /**
087   * The serial version UID for this serializable class.
088   */
089  private static final long serialVersionUID = 7606107105238612142L;
090
091
092
093  // Indicates whether entries should be sorted based on hierarchy.
094  private final boolean sortByHierarchy;
095
096  // The set of sort keys for attribute-level sorting.
097  private final List<SortKey> sortKeys;
098
099  // The schema to use to make the comparison, if available.
100  private final Schema schema;
101
102
103
104  /**
105   * Creates a new entry sorter that will sort entries based only on hierarchy.
106   * Superior entries (that is, entries closer to the root of the DIT) will be
107   * ordered before subordinate entries.  Entries below the same parent will be
108   * sorted lexicographically based on their normalized DNs.
109   */
110  public EntrySorter()
111  {
112    this(true, null, Collections.<SortKey>emptyList());
113  }
114
115
116
117  /**
118   * Creates a new entry sorter with the provided information.
119   *
120   * @param  sortByHierarchy  Indicates whether entries should be sorted
121   *                          hierarchically, such that superior entries will
122   *                          be ordered before subordinate entries.
123   * @param  sortKeys         A list of sort keys that define the order in which
124   *                          attributes should be compared.  It may be empty
125   *                          (but never {@code null}) if sorting should be done
126   *                          only based on hierarchy.
127   */
128  public EntrySorter(final boolean sortByHierarchy, final SortKey... sortKeys)
129  {
130    this(sortByHierarchy, null, Arrays.asList(sortKeys));
131  }
132
133
134
135  /**
136   * Creates a new entry sorter with the provided information.
137   *
138   * @param  sortByHierarchy  Indicates whether entries should be sorted
139   *                          hierarchically, such that superior entries will
140   *                          be ordered before subordinate entries.
141   * @param  schema           The schema to use to make the determination.  It
142   *                          may be {@code null} if no schema is available.
143   * @param  sortKeys         A list of sort keys that define the order in which
144   *                          attributes should be compared.  It may be empty
145   *                          (but never {@code null}) if sorting should be done
146   *                          only based on hierarchy.
147   */
148  public EntrySorter(final boolean sortByHierarchy, final Schema schema,
149                     final SortKey... sortKeys)
150  {
151    this(sortByHierarchy, schema, Arrays.asList(sortKeys));
152  }
153
154
155
156  /**
157   * Creates a new entry sorter with the provided information.
158   *
159   * @param  sortByHierarchy  Indicates whether entries should be sorted
160   *                          hierarchically, such that superior entries will
161   *                          be ordered before subordinate entries.
162   * @param  sortKeys         A list of sort keys that define the order in which
163   *                          attributes should be compared.  It may be empty or
164   *                          {@code null} if sorting should be done only based
165   *                          on hierarchy.
166   */
167  public EntrySorter(final boolean sortByHierarchy,
168                     final List<SortKey> sortKeys)
169  {
170    this(sortByHierarchy, null, sortKeys);
171  }
172
173
174
175  /**
176   * Creates a new entry sorter with the provided information.
177   *
178   * @param  sortByHierarchy  Indicates whether entries should be sorted
179   *                          hierarchically, such that superior entries will
180   *                          be ordered before subordinate entries.
181   * @param  schema           The schema to use to make the determination.  It
182   *                          may be {@code null} if no schema is available.
183   * @param  sortKeys         A list of sort keys that define the order in which
184   *                          attributes should be compared.  It may be empty or
185   *                          {@code null} if sorting should be done only based
186   *                          on hierarchy.
187   */
188  public EntrySorter(final boolean sortByHierarchy, final Schema schema,
189                     final List<SortKey> sortKeys)
190  {
191    this.sortByHierarchy = sortByHierarchy;
192    this.schema          = schema;
193
194    if (sortKeys == null)
195    {
196      this.sortKeys = Collections.emptyList();
197    }
198    else
199    {
200      this.sortKeys = Collections.unmodifiableList(new ArrayList<>(sortKeys));
201    }
202  }
203
204
205
206  /**
207   * Sorts the provided collection of entries according to the criteria defined
208   * in this entry sorter.
209   *
210   * @param  entries  The collection of entries to be sorted.
211   *
212   * @return  A sorted set, ordered in accordance with this entry sorter.
213   */
214  public SortedSet<Entry> sort(final Collection<? extends Entry> entries)
215  {
216    final TreeSet<Entry> entrySet = new TreeSet<>(this);
217    entrySet.addAll(entries);
218    return entrySet;
219  }
220
221
222
223  /**
224   * Compares the provided entries to determine the order in which they should
225   * be placed in a sorted list.
226   *
227   * @param  e1  The first entry to be compared.
228   * @param  e2  The second entry to be compared.
229   *
230   * @return  A negative value if the first entry should be ordered before the
231   *          second, a positive value if the first entry should be ordered
232   *          after the second, or zero if the entries should have an equivalent
233   *          order.
234   */
235  @Override()
236  public int compare(final Entry e1, final Entry e2)
237  {
238    DN parsedDN1 = null;
239    DN parsedDN2 = null;
240
241    if (sortByHierarchy)
242    {
243      try
244      {
245        parsedDN1 = e1.getParsedDN();
246        parsedDN2 = e2.getParsedDN();
247
248        if (parsedDN1.isAncestorOf(parsedDN2, false))
249        {
250          return -1;
251        }
252        else if (parsedDN2.isAncestorOf(parsedDN1, false))
253        {
254          return 1;
255        }
256      }
257      catch (final LDAPException le)
258      {
259        Debug.debugException(le);
260      }
261    }
262
263    for (final SortKey k : sortKeys)
264    {
265      final String attrName = k.getAttributeName();
266      final Attribute a1 = e1.getAttribute(attrName);
267      final Attribute a2 = e2.getAttribute(attrName);
268
269      if ((a1 == null) || (! a1.hasValue()))
270      {
271        if ((a2 == null) || (! a2.hasValue()))
272        {
273          // Neither entry has the attribute.  Continue on with the next
274          // attribute.
275          continue;
276        }
277        else
278        {
279          // The first entry does not have the attribute but the second does.
280          // The first entry should be ordered after the second.
281          return 1;
282        }
283      }
284      else
285      {
286        if ((a2 == null) || (! a2.hasValue()))
287        {
288          // The first entry has the attribute but the second does not.  The
289          // first entry should be ordered before the second.
290          return -1;
291        }
292      }
293
294
295      final MatchingRule matchingRule = MatchingRule.selectOrderingMatchingRule(
296           attrName, k.getMatchingRuleID(), schema);
297      if (k.reverseOrder())
298      {
299        // Find the largest value for each attribute, and pick the larger of the
300        // two.
301        ASN1OctetString v1 = null;
302        for (final ASN1OctetString s : a1.getRawValues())
303        {
304          if (v1 == null)
305          {
306            v1 = s;
307          }
308          else
309          {
310            try
311            {
312              if (matchingRule.compareValues(s, v1) > 0)
313              {
314                v1 = s;
315              }
316            }
317            catch (final LDAPException le)
318            {
319              Debug.debugException(le);
320            }
321          }
322        }
323
324        ASN1OctetString v2 = null;
325        for (final ASN1OctetString s : a2.getRawValues())
326        {
327          if (v2 == null)
328          {
329            v2 = s;
330          }
331          else
332          {
333            try
334            {
335              if (matchingRule.compareValues(s, v2) > 0)
336              {
337                v2 = s;
338              }
339            }
340            catch (final LDAPException le)
341            {
342              Debug.debugException(le);
343            }
344          }
345        }
346
347        try
348        {
349          final int value = matchingRule.compareValues(v2, v1);
350          if (value != 0)
351          {
352            return value;
353          }
354        }
355        catch (final LDAPException le)
356        {
357          Debug.debugException(le);
358        }
359      }
360      else
361      {
362        // Find the smallest value for each attribute, and pick the larger of
363        // the two.
364        ASN1OctetString v1 = null;
365        for (final ASN1OctetString s : a1.getRawValues())
366        {
367          if (v1 == null)
368          {
369            v1 = s;
370          }
371          else
372          {
373            try
374            {
375              if (matchingRule.compareValues(s, v1) < 0)
376              {
377                v1 = s;
378              }
379            }
380            catch (final LDAPException le)
381            {
382              Debug.debugException(le);
383            }
384          }
385        }
386
387        ASN1OctetString v2 = null;
388        for (final ASN1OctetString s : a2.getRawValues())
389        {
390          if (v2 == null)
391          {
392            v2 = s;
393          }
394          else
395          {
396            try
397            {
398              if (matchingRule.compareValues(s, v2) < 0)
399              {
400                v2 = s;
401              }
402            }
403            catch (final LDAPException le)
404            {
405              Debug.debugException(le);
406            }
407          }
408        }
409
410        try
411        {
412          final int value = matchingRule.compareValues(v1, v2);
413          if (value != 0)
414          {
415            return value;
416          }
417        }
418        catch (final LDAPException le)
419        {
420          Debug.debugException(le);
421        }
422      }
423    }
424
425
426    // If we've gotten here, then there is no difference in hierarchy or
427    // sort attributes.  Compare the DNs as a last resort.
428    try
429    {
430      if (parsedDN1 == null)
431      {
432        parsedDN1 = e1.getParsedDN();
433      }
434
435      if (parsedDN2 == null)
436      {
437        parsedDN2 = e2.getParsedDN();
438      }
439
440      return parsedDN1.compareTo(parsedDN2);
441    }
442    catch (final LDAPException le)
443    {
444      Debug.debugException(le);
445      final String lowerDN1 = StaticUtils.toLowerCase(e1.getDN());
446      final String lowerDN2 = StaticUtils.toLowerCase(e2.getDN());
447      return lowerDN1.compareTo(lowerDN2);
448    }
449  }
450
451
452
453  /**
454   * Retrieves a hash code for this entry sorter.
455   *
456   * @return  A hash code for this entry sorter.
457   */
458  @Override()
459  public int hashCode()
460  {
461    int hashCode = 0;
462
463    if (sortByHierarchy)
464    {
465      hashCode++;
466    }
467
468    for (final SortKey k : sortKeys)
469    {
470      if (k.reverseOrder())
471      {
472        hashCode *= -31;
473      }
474      else
475      {
476        hashCode *= 31;
477      }
478
479      hashCode += StaticUtils.toLowerCase(k.getAttributeName()).hashCode();
480    }
481
482    return hashCode;
483  }
484
485
486
487  /**
488   * Indicates whether the provided object is equal to this entry sorter.
489   *
490   * @param  o  The object for which to make the determination.
491   *
492   * @return  {@code true} if the provided object is equal to this entry sorter,
493   *          or {@code false} if not.
494   */
495  @Override()
496  public boolean equals(final Object o)
497  {
498    if (o == null)
499    {
500      return false;
501    }
502
503    if (o == this)
504    {
505      return true;
506    }
507
508    if (! (o instanceof EntrySorter))
509    {
510      return false;
511    }
512
513    final EntrySorter s = (EntrySorter) o;
514    if (sortByHierarchy != s.sortByHierarchy)
515    {
516      return false;
517    }
518
519    return sortKeys.equals(s.sortKeys);
520  }
521
522
523
524  /**
525   * Retrieves a string representation of this entry sorter.
526   *
527   * @return  A string representation of this entry sorter.
528   */
529  @Override()
530  public String toString()
531  {
532    final StringBuilder buffer = new StringBuilder();
533    toString(buffer);
534    return buffer.toString();
535  }
536
537
538
539  /**
540   * Appends a string representation of this entry sorter to the provided
541   * buffer.
542   *
543   * @param  buffer  The buffer to which the string representation should be
544   *                 appended.
545   */
546  public void toString(final StringBuilder buffer)
547  {
548    buffer.append("EntrySorter(sortByHierarchy=");
549    buffer.append(sortByHierarchy);
550    buffer.append(", sortKeys={");
551
552    final Iterator<SortKey> iterator = sortKeys.iterator();
553    while (iterator.hasNext())
554    {
555      iterator.next().toString(buffer);
556      if (iterator.hasNext())
557      {
558        buffer.append(", ");
559      }
560    }
561
562    buffer.append("})");
563  }
564}