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