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