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