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<Entry> 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}