001/*
002 * Copyright 2007-2017 UnboundID Corp.
003 * All Rights Reserved.
004 */
005/*
006 * Copyright (C) 2008-2017 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 */
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  public int compare(final Entry e1, final Entry e2)
238  {
239    DN parsedDN1 = null;
240    DN parsedDN2 = null;
241
242    if (sortByHierarchy)
243    {
244      try
245      {
246        parsedDN1 = e1.getParsedDN();
247        parsedDN2 = e2.getParsedDN();
248
249        if (parsedDN1.isAncestorOf(parsedDN2, false))
250        {
251          return -1;
252        }
253        else if (parsedDN2.isAncestorOf(parsedDN1, false))
254        {
255          return 1;
256        }
257      }
258      catch (LDAPException le)
259      {
260        debugException(le);
261      }
262    }
263
264    for (final SortKey k : sortKeys)
265    {
266      final String attrName = k.getAttributeName();
267      final Attribute a1 = e1.getAttribute(attrName);
268      final Attribute a2 = e2.getAttribute(attrName);
269
270      if ((a1 == null) || (! a1.hasValue()))
271      {
272        if ((a2 == null) || (! a2.hasValue()))
273        {
274          // Neither entry has the attribute.  Continue on with the next
275          // attribute.
276          continue;
277        }
278        else
279        {
280          // The first entry does not have the attribute but the second does.
281          // The first entry should be ordered after the second.
282          return 1;
283        }
284      }
285      else
286      {
287        if ((a2 == null) || (! a2.hasValue()))
288        {
289          // The first entry has the attribute but the second does not.  The
290          // first entry should be ordered before the second.
291          return -1;
292        }
293      }
294
295
296      final MatchingRule matchingRule = MatchingRule.selectOrderingMatchingRule(
297           attrName, k.getMatchingRuleID(), schema);
298      if (k.reverseOrder())
299      {
300        // Find the largest value for each attribute, and pick the larger of the
301        // two.
302        ASN1OctetString v1 = null;
303        for (final ASN1OctetString s : a1.getRawValues())
304        {
305          if (v1 == null)
306          {
307            v1 = s;
308          }
309          else
310          {
311            try
312            {
313              if (matchingRule.compareValues(s, v1) > 0)
314              {
315                v1 = s;
316              }
317            }
318            catch (LDAPException le)
319            {
320              debugException(le);
321            }
322          }
323        }
324
325        ASN1OctetString v2 = null;
326        for (final ASN1OctetString s : a2.getRawValues())
327        {
328          if (v2 == null)
329          {
330            v2 = s;
331          }
332          else
333          {
334            try
335            {
336              if (matchingRule.compareValues(s, v2) > 0)
337              {
338                v2 = s;
339              }
340            }
341            catch (LDAPException le)
342            {
343              debugException(le);
344            }
345          }
346        }
347
348        try
349        {
350          final int value = matchingRule.compareValues(v2, v1);
351          if (value != 0)
352          {
353            return value;
354          }
355        }
356        catch (LDAPException le)
357        {
358          debugException(le);
359        }
360      }
361      else
362      {
363        // Find the smallest value for each attribute, and pick the larger of
364        // the two.
365        ASN1OctetString v1 = null;
366        for (final ASN1OctetString s : a1.getRawValues())
367        {
368          if (v1 == null)
369          {
370            v1 = s;
371          }
372          else
373          {
374            try
375            {
376              if (matchingRule.compareValues(s, v1) < 0)
377              {
378                v1 = s;
379              }
380            }
381            catch (LDAPException le)
382            {
383              debugException(le);
384            }
385          }
386        }
387
388        ASN1OctetString v2 = null;
389        for (final ASN1OctetString s : a2.getRawValues())
390        {
391          if (v2 == null)
392          {
393            v2 = s;
394          }
395          else
396          {
397            try
398            {
399              if (matchingRule.compareValues(s, v2) < 0)
400              {
401                v2 = s;
402              }
403            }
404            catch (LDAPException le)
405            {
406              debugException(le);
407            }
408          }
409        }
410
411        try
412        {
413          final int value = matchingRule.compareValues(v1, v2);
414          if (value != 0)
415          {
416            return value;
417          }
418        }
419        catch (LDAPException le)
420        {
421          debugException(le);
422        }
423      }
424    }
425
426
427    // If we've gotten here, then there is no difference in hierarchy or
428    // sort attributes.  Compare the DNs as a last resort.
429    try
430    {
431      if (parsedDN1 == null)
432      {
433        parsedDN1 = e1.getParsedDN();
434      }
435
436      if (parsedDN2 == null)
437      {
438        parsedDN2 = e2.getParsedDN();
439      }
440
441      return parsedDN1.compareTo(parsedDN2);
442    }
443    catch (LDAPException le)
444    {
445      debugException(le);
446      final String lowerDN1 = toLowerCase(e1.getDN());
447      final String lowerDN2 = toLowerCase(e2.getDN());
448      return lowerDN1.compareTo(lowerDN2);
449    }
450  }
451
452
453
454  /**
455   * Retrieves a hash code for this entry sorter.
456   *
457   * @return  A hash code for this entry sorter.
458   */
459  @Override()
460  public int hashCode()
461  {
462    int hashCode = 0;
463
464    if (sortByHierarchy)
465    {
466      hashCode++;
467    }
468
469    for (final SortKey k : sortKeys)
470    {
471      if (k.reverseOrder())
472      {
473        hashCode *= -31;
474      }
475      else
476      {
477        hashCode *= 31;
478      }
479
480      hashCode += toLowerCase(k.getAttributeName()).hashCode();
481    }
482
483    return hashCode;
484  }
485
486
487
488  /**
489   * Indicates whether the provided object is equal to this entry sorter.
490   *
491   * @param  o  The object for which to make the determination.
492   *
493   * @return  {@code true} if the provided object is equal to this entry sorter,
494   *          or {@code false} if not.
495   */
496  @Override()
497  public boolean equals(final Object o)
498  {
499    if (o == null)
500    {
501      return false;
502    }
503
504    if (o == this)
505    {
506      return true;
507    }
508
509    if (! (o instanceof EntrySorter))
510    {
511      return false;
512    }
513
514    final EntrySorter s = (EntrySorter) o;
515    if (sortByHierarchy != s.sortByHierarchy)
516    {
517      return false;
518    }
519
520    return sortKeys.equals(s.sortKeys);
521  }
522
523
524
525  /**
526   * Retrieves a string representation of this entry sorter.
527   *
528   * @return  A string representation of this entry sorter.
529   */
530  @Override()
531  public String toString()
532  {
533    final StringBuilder buffer = new StringBuilder();
534    toString(buffer);
535    return buffer.toString();
536  }
537
538
539
540  /**
541   * Appends a string representation of this entry sorter to the provided
542   * buffer.
543   *
544   * @param  buffer  The buffer to which the string representation should be
545   *                 appended.
546   */
547  public void toString(final StringBuilder buffer)
548  {
549    buffer.append("EntrySorter(sortByHierarchy=");
550    buffer.append(sortByHierarchy);
551    buffer.append(", sortKeys={");
552
553    final Iterator<SortKey> iterator = sortKeys.iterator();
554    while (iterator.hasNext())
555    {
556      iterator.next().toString(buffer);
557      if (iterator.hasNext())
558      {
559        buffer.append(", ");
560      }
561    }
562
563    buffer.append("})");
564  }
565}