001    /*
002     * Copyright 2007-2015 UnboundID Corp.
003     * All Rights Reserved.
004     */
005    /*
006     * Copyright (C) 2008-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;
022    
023    
024    
025    import java.io.Serializable;
026    import java.util.ArrayList;
027    import java.util.Arrays;
028    import java.util.Collection;
029    import java.util.Collections;
030    import java.util.Comparator;
031    import java.util.Iterator;
032    import java.util.List;
033    import java.util.SortedSet;
034    import java.util.TreeSet;
035    
036    import com.unboundid.asn1.ASN1OctetString;
037    import com.unboundid.ldap.matchingrules.MatchingRule;
038    import com.unboundid.ldap.sdk.controls.SortKey;
039    import com.unboundid.ldap.sdk.schema.Schema;
040    import com.unboundid.util.ThreadSafety;
041    import com.unboundid.util.ThreadSafetyLevel;
042    
043    import static com.unboundid.util.Debug.*;
044    import 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)
084    public 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    }